# Graph Convolution Based Efficient Re-Ranking for Visual Retrieval

Yuqi Zhang∗,Qi Qian∗, Hongsong Wang∗†, Chong Liu, Weihua Chen, Fan Wang
${\dagger}$ Corresponding author. * indicates equal contributions.This
research is supported in part by Southeast University Start-Up Grant for New
Faculty under Grant RF1028623063. Y. Zhang, Q. Qian, W. Chen, and F. Wang are
with Machine intelligence Technology Lab, Alibaba Group (email:
qi.qian@alibaba-inc.com;kugang.cwh@alibaba-inc.com).H. Wang is with Department
of Computer Science and Engineering, Southeast University, Nanjing, China
(email: hongsongwang@seu.edu.cn).

###### Abstract

Visual retrieval tasks such as image retrieval and person re-identification
(Re-ID) aim at effectively and thoroughly searching images with similar
content or the same identity. After obtaining retrieved examples, re-ranking
is a widely adopted post-processing step to reorder and improve the initial
retrieval results by making use of the contextual information from
semantically neighboring samples. Prevailing re-ranking approaches update
distance metrics and mostly rely on inefficient crosscheck set comparison
operations while computing expanded neighbors based distances. In this work,
we present an efficient re-ranking method which refines initial retrieval
results by updating features. Specifically, we reformulate re-ranking based on
Graph Convolution Networks (GCN) and propose a novel Graph Convolution based
Re-ranking (GCR) for visual retrieval tasks via feature propagation. To
accelerate computation for large-scale retrieval, a decentralized and
synchronous feature propagation algorithm which supports parallel or
distributed computing is introduced. In particular, the plain GCR is extended
for cross-camera retrieval and an improved feature propagation formulation is
presented to leverage affinity relationships across different cameras. It is
also extended for video-based retrieval, and Graph Convolution based Re-
ranking for Video (GCRV) is proposed by mathematically deriving a novel
profile vector generation method for the tracklet. Without bells and whistles,
the proposed approaches achieve state-of-the-art performances on seven
benchmark datasets from three different tasks, i.e., image retrieval, person
Re-ID and video-based person Re-ID. Code is publicly available:
github.com/WesleyZhang1991/GCN_rerank.

###### Index Terms:

Visual retrieval, re-ranking, person re-identification, video-based person re-
identification

##  I Introduction

Given a query image, the goal of visual retrieval is to effectively and
efficiently find relevant images that share similar content or depict the same
instance from a large-scale visual corpus. The typical tasks include content-
based image retrieval, person re-identification (Re-ID) and vehicle Re-ID.
Visual retrieval has become an increasingly important field of research with
the fast development of Internet and the universal popularity of digital
cameras. Although this problem has been extensively explored by researchers
over the past decades, it is still very challenging to trade between the
efficiency and accuracy while deploying a retrieval method in realistic
applications.

When training models for image retrieval or person Re-ID, most approaches only
consider the identity label of an image and the relationship between two
images while ignoring the contextual information among multiple relevant
images. Re-ranking approaches [1, 2] mitigate this issue by utilizing global
similarity measures which could analyze an ample amount of relevant images and
take the underlying global manifold structure into account. The re-ranking
process reorders the retrieved results based on the information or specific
patterns mined from the initial ranked list. With additional computation cost,
re-ranking as a post-process step has been experimentally validated to be very
effective for content-based image retrieval, person or vehicle re-
identification and so on.

Figure 1: Comparison of the computation time and the gained performance of
different re-ranking methods for person Re-ID on the Market-1501 dataset. The
computation time of our approach is only one third of that of KR [3] or ECN
[4], while the performance is even dramatically improved. Although some
methods such as QE [5] enjoy less computation time, their retrieval
performances are rather limited to meet the realistic demand. Figure 2: A
comparison between most conventional re-ranking methods and the proposed GCR.
Previous methods such as KR [3] and ECN [4] directly calculate the similarity
matrix based on nearest neighbors and their reciprocal or expanded neighbors.
In contrast, our approach indirectly refine initial ranking results by
updating and improving the features.

Previous re-ranking methods can be roughly categorized into two types:
learning based and non-learning based approaches. The former one jointly
optimizes image features and pairwise relationships in a single network [6, 7,
8]. These approaches are tightly restricted to the feature extraction
backbone, and cannot be used as an off-the-shelf re-ranking module. The latter
one only focuses on the post-processing step and is more flexible for
different applications. Typical non-learning based approaches are Query
Expansion (QE) [5], K-Reciprocal Encoding (KR) [3] and ECN [4]. Although KR
and ECN evidently improve the retrieval performance, they are inefficient for
large-scale applications due to the requirement of computing sophisticated
distance metrics between the query and all samples in the database with
respect to reciprocal or expanded neighbors.

Graph Convolution Networks (GCN) have been applied for content-based image
retrieval and person Re-ID [6, 7, 8], mostly in order to learn pairwise
similarity information or contextual interactions. These approaches
appropriately utilize relationships between probe and gallery images to learn
powerful features. However, existing GCN based re-ranking methods are not
plug-and-play as they often combine the GCN based contextual relationship with
the CNN based appearance feature learning to form a unified framework.
Recently, the standalone re-ranking process in image retrieval is also re-
formulated from a GCN perspective [9]. Although this approach shares some
similarities with ours in the target of GCN based re-ranking, there exist
considerable differences in mathematical modelling of relation graph
construction and feature propagation formulas as well as potential
applications.

This paper targets at a more scalable and efficient re-ranking that is
flexible for various visual retrieval tasks. We novelly establish the
intrinsic connection between GCN and nearest neighbors based re-ranking, and
propose a new re-ranking paradigm by updating features based on GCN. As shown
in Fig. 1, the proposed re-ranking could improve the performance over the
widely used KR [3] and ECN [4] while being much more efficient. Different from
previous methods that handle the similarities directly, our approach
indirectly refines the initial search results by updating and improving the
features. A brief comparison between our approach and conventional re-ranking
methods is illustrated in Fig. 2. Different from conventional methods that
refine the similarity matrix, our approach improves the features by aligning
them across similar instances. Most conventional re-ranking methods require
the storage of the intermediate similarity matrices. When the size of the
gallery set is very large, these similarity matrices become extremely large
and bring heavy memory burdens. In contrast, our approach only stores the
feature matrices which are much smaller and more memory friendly.
Additionally, previous approaches inevitably rely on inefficient set
comparison operations which are difficult to be accelerated. Our approach only
depends on matrix operations which can be easily deployed on the GPU.

More specifically, we propose a novel Graph Convolution based Re-ranking (GCR)
for visual retrieval based on GCN. In this framework, undirected graphs based
on nearest neighbors are constructed to facilitate semantically contextual
feature propagation. To meet the demand for efficiency for large-scale
retrieval tasks, a decentralized and synchronous feature propagation algorithm
is presented to fit for parallel or distributed computing. Moreover, the
proposed GCR is extended for two specific tasks: cross-camera retrieval and
video-based retrieval. For the former task, an improved GCR is established by
deliberately constructing cross-camera nearest neighbor graphs and aligning
features from different cameras. For the latter task, a novel profile vector
generation method is proposed to learn the profile vector for each tracklet,
and the Graph Convolution based Re-ranking for Video (GCRV) is presented to
fully utilize spatial and temporal contextual relationships.

The work is an extension of the published conference paper [10]. Compared to
the preliminary version, the major differences are as follows.

  * •

Compared with the previous GCR which is solely designed for person Re-ID, we
present a more general re-ranking method for different visual retrieval tasks.

  * •

We propose a decentralized and synchronous feature propagation suitable for
parallel or distributed computing.

  * •

We derive the formulation of the profile vector generation from the
perspective of feature alignment.

  * •

We conduct extensive experiments on four more benchmarks of visual retrieval,
and provide more thorough analyses about efficiencies and parameter
sensitivities.

The rest of this paper is organized as follows. Section II reviews the related
work. Section III elaborates feature propagation and the proposed re-ranking
methods for different tasks. Section IV provides extensive experimental
results and analyses on different benchmark datasets. Section V concludes this
work with the future direction.

##  II Related Work

We briefly review approaches that are mostly related to ours from three
aspects: person Re-ID, re-ranking for person Re-ID, and re-ranking for image
retrieval.

###  II-A Person Re-Identification

Many recent works of person Re-ID focus on global or local feature learning.
The global approaches [11, 12, 13, 14, 15] straightforwardly learn
representations for the entire image. In contrast, local approaches [16, 17,
18, 19, 20] learn representations for the image parts based on the assumption
that person images are roughly aligned. Compared with global feature learning,
local feature learning could alleviate the impact of occlusion or inaccurate
detection.

The feature learning methods often use the Softmax loss or its modifications
[21, 22, 23]. Metric learning approaches such as the contrastive loss [24] and
triplet loss [25] are also applied for person Re-ID. The widely used open-
source re-ID strong baseline [14] combines both softmax loss and triplet loss.
Equipped with some tricks including random erasing [26], dropout [27] and so
on, this baseline achieves competitive results compared with recent state-of-
the-art approaches. A semi-supervised feature learning method is proposed to
learn apparel-invariant feature embedding against appearance changes [28]. In
our experiments of person Re-ID, this baseline model is used for feature
extraction in order to make a fair comparison with other re-ranking methods.

Recently, there are also graphical models or Graph Convolution Networks (GCN)
based feature learning approaches for person Re-ID [6, 7, 8]. Shen et al. [6]
apply similarity transformation on the graph to model the similarity
relationship among the query image and the gallery images. Shen et al. [7]
propose Similarity Guided Graph Neural Neural (SGGNN) to incorporate the pair-
wise similarity information into the training process of person Re-ID. Wu et
al. [8] use GCN to learn the contextual interactions between the relevant
regional features for video based person Re-ID. However, these methods are
often embedded into the training phase and thus could not serve as a re-
ranking method in the post-process stage. Moreover, they do not take the
cross-camera relationship into account. In this work, we reformulate the re-
ranking based on GCN and also incorporate the cross-camera semantic
similarities into the proposed re-ranking framework.

###  II-B Re-Ranking for Person Re-Identification

Re-ranking is often used as a post-processing step to improve initial ranking
results. The re-ranking methods can be generally split into two types:
learning based and non-learning based approaches.

Learning based methods jointly optimize image features and pairwise
relationships in a single network. Typical approaches are [6, 7, 29, 8]. For
example, Luo et al. [29] propose a lightweight re-ranking method to make the
underlying clustering structure around the query set more compact. However,
most of these approaches are based on supervised similarity propagation which
is integrated into the training pipeline. Conversely, our approach is a pure
feature similarity propagation based and plug-and-play re-ranking technique,
which is applicable for various visual retrieval tasks.

Non-learning based approaches only focus on the re-ranking post-processing.
Since the original top-ranked data might be polluted by false positives,
k-reciprocal nearest neighbors [30, 31] can be regarded as highly relevant
candidates. Zhong et al. [3] introduce the concept of k-reciprocal nearest
neighbor and design a re-ranking method for person Re-ID by combining the
Jaccard distance of k-reciprocal encodings with the original feature distance.
Sarfraz et al. [4] present a relatively effective re-ranking method which
reinforces the original pairwise distance by aggregating distances between
expanded neighbors of image pairs. To address the high computational
complexity and unaffordable time cost for large-scale applications, Zhang et
al. [9] re-formulate the re-ranking process as a GCN function. These
approaches require sophisticated and complicated distance metrics rather than
Euclidean distance with respect to reciprocal or expanded neighbors. In
addition, most of these approaches could hardly achieve fast retrieval for
massive data in real applications due to their high computational
complexities. In contrast, our approach only relies on Euclidean distance for
similarity measure which is more flexible and scalable to downstream tasks,
and is specially designed for large-scale applications.

###  II-C Re-Ranking for Image Retrieval

Most approaches for image-retrieval often follow the retrieve-and-rerank
paradigm which deploys a two-stage framework, i.e., first use global features
to get the initial rank list, and then use local features to re-rank the
candidates. Geometric verification is a popular image re-ranking approach and
is widely used in both traditional work [32] and recent deep learning based
works [33, 34]. The DELG [34] jointly learns global and local features into a
single deep model. However, the matching algorithm is still classic RANSAC
which limits the performance and efficiency. SuperGlue [35] improves the local
matching algorithm by solving a differentiable optimal transport problem with
graph neuron networks. Reranking Transformer (RRT) [36] uses transformers to
learn matched or unmatched labels based on global and local features from two
images. These approaches only consider pairwise local relationships and ignore
informative relationships among multiple images. In addition, they are mostly
developed for retrievals of rigid objects such as buildings and landmarks, and
may not be applicable for other visual retrieval tasks such as person Re-ID.
This work is targeted at a general and effective re-ranking approach for
different visual retrieval problems.

###  II-D Graph Structure Learning and Subspace Learning

Graph Structure Learning (GSL) aims to jointly learn a graph structure and
corresponding graph representations. A general pipeline of GSL has four steps:
graph construction, structure modeling, message propagation and joint
optimization learning [37]. For example, Pro-GNN [38] jointly learns a
structural graph and a robust GCN model from the perturbed graph. The
$k$-nearest neighbors and the GCN are usually used in graph construction and
message propagation, respectively. For this reason, the proposed GCR can be
regarded as a special type of the GSL where the joint optimization learning is
omitted and the GCN parameters are fixed.

The proposed GCN based re-ranking is also related to Subspace Representation
Learning (SRL) which assumes a data instance can be expressed as a linear
combination of other data instances from the same subspace. SRL maps high-
dimensional features onto low-dimensional subspaces, and GCN can also be used
to learn latent subspace presentations. Ji et al. [39] introduce a novel self-
expressive layer for unsupervised subspace clustering and directly learn the
affinities between all data points. Zhang et al. [40] propose a collaborative
learning paradigm for unsupervised subspace clustering. A deep $k$-subspace
clustering algorithm is presented to scale subspace clustering to large-scale
datasets [41].

##  III Proposed Approach

We first describe the proposed Graph Convolution based Re-ranking (GCR) from
the perspective of Graph Convolution Network (GCN). Then we detail different
feature propagation algorithms based on nearest neighbor graphs. Finally, we
extend the basic approach for both cross-camera retrieval and video-based
retrieval.

###  III-A Graph Convolution Based Re-Ranking

The graph convolution operator in a standard Graph Convolution Networks (GCN)
[42] layer can be written as

$\displaystyle\mathbf{\widetilde{X}}=\mathbf{D}^{-\frac{1}{2}}\mathbf{AD}^{-\frac{1}{2}}\mathbf{XW}$
(1)

where $\mathbf{X}\in\mathbb{R}^{n\times d}$ is the input features, $n$ is the
number of samples and $d$ is the feature dimensionality. $\mathbf{A}$ is the
${n\times n}$ similarity matrix and $\mathbf{D}$ is the degree matrix which is
a diagonal matrix with $D_{i,i}=\sum_{j}A_{i,j}$.
$\mathbf{W}\in\mathbb{R}^{d\times d^{\prime}}$ denotes the weight parameters
of the convolution operator and $\mathbf{\widetilde{X}}$ is the output
features.

When the parameter matrix $\mathbf{W}$ is an identity matrix, the graph
convolution can be considered as feature propagation on the graph
characterized by the similarity matrix. The mathematical formulation is

$\displaystyle\mathbf{\widetilde{X}}=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}\mathbf{X}$
(2)

where $\mathbf{X}$ and $\mathbf{\widetilde{X}}$ have the same feature
dimensionality. This operator is parameter-free, and can be directly used to
update features based on existing feature vectors for visual retrieval tasks
such as image retrieval and person Re-ID.

For image retrieval, $\mathbf{X}$ contains image features from both the query
set and gallery set. The GCN based operator explicitly propagates and updates
features over a given graph. As a result, the retrieval results would be
updated using the new features. It should be noted that most previous re-
ranking methods directly update the ranked candidates or the original
similarity matrix between the query set and the gallery set. In contrast, our
approach implicitly renews the ranked results by updating and improving the
features via a parameter-free graph convolution.

As the GCN layers can be stacked to build deep architectures and learn high-
level representations, the feature propagation can be iterated. Assume $T$ is
the number of iterations. This process is represented by

$\displaystyle\mathbf{X}_{t}=G(\mathbf{X}_{t-1})$ (3)

where $G(\cdot)$ denotes the feature propagation in Eq. (2), $1\leq t\leq T$,
$X_{0}$ is the original input features, and $\mathbf{X}_{T}$ is the final
updated features.

The key of GCR is to design an appropriate similarity matrix. We impose
locality constraints on the connected graph between the query and gallery
samples. The details of feature propagation are elaborated in Section III-B.

###  III-B Feature Propagation on Graph

Given the query and gallery samples, an undirected graph is constructed where
each node denotes a sample and an edge denotes the relationship between two
samples. The $k$-nearest neighbor graph is adopted to fully utilize the
$k$-nearest neighbors of a sample for feature propagation.

For an image sample index by $i$, we first obtain its $k$-nearest neighbors
$\mathcal{N}_{i}$ based on the original features. Then, the similarity matrix
$\widetilde{\mathbf{A}}$ is computed as

$\displaystyle\widetilde{A}_{i,j}=\left\\{\begin{array}[]{lc}{\rm\exp}(-\|\mathbf{x}_{i}-\mathbf{x}_{j}\|_{2}^{2}/\gamma)&j\in\mathcal{N}_{i}\\\
1&j=i\\\ 0&\textrm{otherwise}\end{array}\right.$ (7)

where $\mathbf{x}_{i}$ is the input feature of the $i\textrm{-th}$ image, and
$\gamma$ is the temperature parameter.

The similarity matrix $\widetilde{\mathbf{A}}$ originally obtained from Eq.
(7) is not symmetric due to the fact that the $i\textrm{-th}$ image may not in
the $k$-nearest neighbors $\mathcal{N}_{j}^{k}$ of the $j\textrm{-th}$ image
when $j\in\mathcal{N}_{i}$. Two degree matrices can be computed by summing of
the entries of the respective column or row. The formulations of row degree
matrix $\mathbf{D_{r}}$ and column degree matrix $\mathbf{D_{c}}$ are

$\displaystyle\left\\{\begin{array}[]{l}D_{r}(i,i)=\sum\nolimits_{j}{{\widetilde{A}_{i,j}}}\\\
D_{c}(j,j)=\sum\nolimits_{i}{{\widetilde{A}_{i,j}}}\end{array}\right.$ (10)

With the input features $\mathbf{X}$, the similarity matrix
$\widetilde{\mathbf{A}}$, and degree matrices $\mathbf{D_{r}}$ and
$\mathbf{D_{c}}$, the propagation criterion becomes

$\displaystyle\mathbf{\widetilde{X}}=\mathbf{D_{r}}^{-\frac{1}{2}}\mathbf{\widetilde{A}}\mathbf{D_{c}}^{-\frac{1}{2}}\mathbf{X}$
(11)

As the similarity matrix contains pairwise similarity values which should be
symmetric from an intuitive perspective. To make the similarity matrix
symmetric, we simply add it with its transpose. The output symmetric matrix
$A$ is

$\displaystyle\mathbf{A}=\left(\widetilde{\mathbf{A}}+\widetilde{\mathbf{A}}^{\top}\right)/2$
(12)

For the symmetric matrix, the row degree matrix and the column degree matrix
are identical. Thus, the feature propagation criterion can be described in Eq.
(2). The constructed nearest neighbor graph of the query and gallery samples
is a sparse graph constrained on the nearest neighbors.

The conventional feature propagation is computed with all images, which is
inefficient to update features on a large-scale data set. To accommodate for
large-scale retrieval, we present a decentralized and synchronous feature
propagation method which is fit for parallel or distributed computing. This
method is summarized in Algorithm 1.

Algorithm 1 Decentralized and Synchronous Feature Propagation (DSFP)

Input: $\mathbf{X}_{0}$ – Original input features.
Output: $\mathbf{X}_{T}$ – Final updated features.

1: For the $i$-th image, obtain its $k$-nearest neighbors $\mathcal{N}_{i}$
with the provided features.

2: Augment the $k$-nearest neighbors $\mathcal{N}_{i}$ with
$\mathbf{x}_{i},i.e.,\widetilde{N}_{i}=N_{i}\cup\\{i\\}$.

3: Generate the symmetric $(k+1)\times(k+1)$ local similarity matrix
$\mathbf{A}^{i}$ for the $i$-th image as  $\forall
u,v\in\widetilde{N}_{i}^{k},A_{u,v}^{i}=\exp(-|\mathbf{x}_{u}-\mathbf{x}_{v}\|_{2}^{2}/\gamma)$

4: Prepare the local input features corresponding to $\widetilde{N}_{i}$,
which is a $(k+1)\times d$ matrix denoted by $\mathbf{X}^{i}_{0}$.

5: Calculate the local $(k+1)\times(k+1)$ degree matrix $\mathbf{D}^{i}$ with
$D^{i}(i,i)=\sum\nolimits_{j}{A^{i}_{i,j}}$

6: Iteratively update the features based on the feature propagation
formulation,
$\mathbf{X}^{i}_{t+1}=(\mathbf{D}^{i})^{-\frac{1}{2}}\mathbf{A}^{i}(\mathbf{D}^{i})^{-\frac{1}{2}}\mathbf{X}^{i}_{t}$
where $1\leq t\leq T$, and $T$ is the number of iterations.

The proposed decentralized and synchronous feature propagation renew features
for each image with a compact and local similarity matrix. Compared with the
conventional global feature propagation, this distributed variant would be
more efficient for large-scale applications.

Figure 3: The pipeline of the proposed GCR applied for person re-
identification.

###  III-C Extension for Cross-Camera Retrieval

For cross-camera retrieval tasks such as person Re-ID, samples from different
cameras with similar contents should be emphasized while learning
representations. We aim to align features from different cameras, which is
very important for reducing feature divergences across different cameras.
Cross-camera nearest neighbor graphs are additionally constructed only for
samples from different cameras. The details are described as follows.

For the $i$-th image, we first obtain its $k$-nearest neighbors
$\mathcal{N}_{i}^{\textrm{cr}}$ from different cameras based on the original
features. We then compute the corresponding cross-camera similarity matrix
$\widetilde{A}^{\textrm{cr}}$ as

$\displaystyle\widetilde{A}^{\textrm{cr}}_{i,j}=\left\\{\begin{array}[]{lc}\exp(-\|\mathbf{x}_{i}-\mathbf{x}_{j}\|_{2}^{2}/\gamma)&j\in\mathcal{N}_{i}^{\textrm{cr}}\\\
1&j=i\\\ 0&\textrm{otherwise}\end{array}\right.$ (16)

Similar to $\widetilde{A}$, the matrix $\widetilde{A}^{\textrm{cr}}$ is not
symmetric, and the corresponding symmetric cross-camera similarity matrix
$A^{\textrm{cr}}$ can be obtained in the similar way as Eq. (12).

With the two similarity matrices $\widetilde{\mathbf{A}}$ and
$\mathbf{\widetilde{A}^{\textrm{cr}}}$, the feature propagation is

$\displaystyle\widetilde{\mathbf{X}}=\alpha\mathbf{D_{r}}^{-\frac{1}{2}}\widetilde{\mathbf{A}}\mathbf{D_{c}}^{-\frac{1}{2}}\mathbf{X}+(1-\alpha)({\mathbf{D_{r}^{\textrm{cr}}}})^{-\frac{1}{2}}\mathbf{\widetilde{A}^{\textrm{cr}}}({\mathbf{D_{c}^{\textrm{cr}}}})^{-\frac{1}{2}}\mathbf{X}$
(17)

where $\alpha$ is the parameter to balance the weights between global
propagation and cross-camera propagation. Similarly, the feature propagation
formulation for symmetric similarity matrices $\mathbf{A}$ and
$\mathbf{A^{\textrm{cr}}}$ can be deduced.

The whole pipeline for the proposed GCR applied for person Re-ID is
illustrated in Fig. 3. As discussed in Eq. (3), the re-ranking process can be
iterated to get better representations. The similarity matrices as well as
nearest neighbor graphs also change during different iterations.

It should be noted that most existing methods [4, 3] leverage information from
the global nearest neighbors to refine the results for person Re-ID, while
building graphs only for nearest neighbors from different cameras is rarely
investigated. Simple as it is, this step is important for cross-camera person
Re-ID. Feature propagation on cross-camera graphs emphasizes the relationship
between the image and its nearest neighbors from different cameras, and
ultimately eliminates the bias from cameras in the similarity matrix and
aligns features across multiple cameras.

###  III-D Extension for Video-Based Retrieval

In subsection III-C, we extend the GCR to cross-camera retrieval scenarios. In
this subsection, we further extend this approach to video-based retrieval,
typically for video-based person Re-ID. Different from image-based re-
identification, each sample in video-based re-identification is a tracklet,
which consists of a set of images of a moving object.

Suppose $\mathbf{x}_{i}$ and $y_{i}$ are the feature vector and identity label
for the $i$-th image, respectively, and the tracklet which consists a sequence
of images is indexed by the identity label. Given images
$\\{\mathbf{x}_{i},y_{i}\\}$ from all tracklets in a video, a simple profile
for the $c$-th tracklet is the mean feature vector

$\displaystyle\hat{\mathbf{x}}_{c}=\frac{1}{m_{c}}\sum_{j|y_{j}=c}\mathbf{x}_{j}$
(18)

where $y_{j}$ indicates the identification of the tracklet and $m_{c}$ is the
number of images in the $c$-th tracklet.

It is important to take full advantage of these multiple images in the
tracklet to build a robust feature vector of this tracklet. Therefore, we
propose a novel profile vector generation method to extract the profile vector
for each tracklet. Based on the generated profile vector, the GCR can be
easily applied for the video-based retrieval tasks.

We expect the new profile vector should be near to the features of images in
the tracklet, and meanwhile far away from the other features in the same
camera. Assume $\mathbf{w_{c}}$ is the profile vector of the ${c}$-th
tracklet, a simple objective is to minimize the differences between
$\mathbf{w_{c}}$ and images that share the same identity as the tracket and
maximize the differences between $\mathbf{w_{c}}$ and other unrelated images.
Thus, the objective function is formulated as

$\displaystyle\min_{\mathbf{w_{c}}}\frac{1}{nm_{c}}\sum_{i}\sum_{j|y_{j}=c}\left\|\mathbf{x}_{j}-\mathbf{w_{c}}\right\|_{2}^{2}-\left\|\mathbf{x}_{i}-\mathbf{w_{c}}\right\|_{2}^{2}$
(19)

where $m_{c}$ is the number of frames in the $c$-th tracklet, and $n$ is the
total number of frames of images from all the tracklets.

By rearranging terms and assume $\left\|\mathbf{x}_{i}\right\|_{2}=1$, the
problem is equivalent to

$\displaystyle\min_{\mathbf{w_{c}}}\frac{1}{nm_{c}}\sum_{i}\sum_{j|y_{j}=c}\mathbf{x}_{i}^{\top}\mathbf{w}_{c}-\mathbf{x}_{j}^{\top}\mathbf{w}_{c}$
(20)

Inspired by the fact that the dot product between irrelevant vectors on the
unit ball equals to 0, we focus on pushing $\mathbf{w}_{c}$ to its
corresponding frames and reduce the influence from negative examples by
employing a hinge loss

$\displaystyle\min_{\mathbf{w_{c}}}\frac{1}{nm_{c}}\sum_{i}\sum_{j:y_{j}=c}\max(0,\mathbf{x}_{i}^{\top}\mathbf{w_{c}})-\mathbf{x}_{j}^{\top}\mathbf{w_{c}}$
(21)

By replacing the hinge loss with a smoothed version, a pair-wise smoothed
hinge loss is defined as

$\displaystyle\min_{\mathbf{w_{c}}}\frac{1}{nm_{c}}\sum_{i}\sum_{j|y_{j}=c}-\log\left(\frac{\exp\left(\mathbf{x}_{j}^{\top}\mathbf{w}_{c}\right)}{1+\exp\left(\mathbf{x}_{i}^{\top}\mathbf{w}_{c}\right)}\right)$
(22)

According to Taylor expansion at $\mathbf{w}_{c}=0$, this minimized objective
function can be bounded by the formulation

$\displaystyle\frac{1}{n}\sum_{i}\mathbf{x}_{i}^{\top}\mathbf{w}_{c}-\frac{1}{m_{c}}\sum_{j|y_{j}=c}\mathbf{x}_{j}^{\top}\mathbf{w}_{c}+\frac{1}{n}\left\|\mathbf{X}\mathbf{w}_{c}\right\|_{2}^{2}+\frac{\lambda}{2}\left\|\mathbf{w}_{c}\right\|_{2}^{2}$
(23)

where $\mathbf{X}$ is feature matrix which consists of all images from the
tracklets, and $\left\|\mathbf{w}_{c}\right\|_{2}^{2}$ is a regularization
term with a weight parameter $\lambda$.

The above quadratic objective function has a closed-form solution. Therefore,
the formulation of the new profile is

$\displaystyle\mathbf{w}_{c}=\left(\mathbf{X}\mathbf{X}^{\top}+\lambda
n\mathbf{I}\right)^{-1}\left(\frac{1}{m_{c}}\sum_{j|y_{j}=c}\mathbf{x}_{j}-\frac{1}{n}\sum_{i}\mathbf{x}_{i}\right)$
(24)

where $\mathbf{I}$ is the identity matrix.

Compared with the mean vector in Eq. (18), the profile vector in Eq. (24)
eliminates the mean vector $\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}$ of images
of all tracklets from the same camera to reduce the bias from different
cameras. It also leverages the geometric information by calculating the
covariance matrix $\mathbf{X}^{\top}\mathbf{X}$.

After obtaining the profile vector, the proposed re-ranking method can be
further used to re-rank video tracklets. The whole process is called Graph
Convolution based Re-ranking for Video (GCRV), which is summarized in
Algorithm 2.

Algorithm 2 Graph Convolution based Re-ranking for Video (GCRV)

Input: A set of tracklets from videos of different cameras, $\mathbf{X}$ – The
corresponding original features of images in the tracklets, $T$ – The number
of iterations.
Output: $\mathbf{W}$ – Updated profile vectors of all tracklets.

1: For each tracklet, generate the profile vector $\mathbf{w}_{c}$ as in Eq.
(24).

2: for $t=1$ to $T$ do

3: For each tracklet, build two nearest neighbor graphs: global $k$-nearest
neighbor graph and $k$-nearest neighbor graph from different cameras.

4: Generate the global similarity matrices $\mathbf{A}$ and cross-camera
similarity matrix $\mathbf{\widetilde{A}^{\textrm{cr}}}$ based on profile
vectors $\mathbf{W}=\\{\mathbf{w}_{c}\\}$.

5: Update features $\mathbf{W}$ with the corresponding criterion as in Eq.
(17) by substituting $\mathbf{X}$ with $\mathbf{W}$.

6: end for

##  IV Experiments

###  IV-A Datasets

For image-based person ReID, we evaluate the proposed re-ranking approach on
four popular benchmarks, i.e., Market-1501 (Market) [43], Duke-MTMC-re-ID
(Duke) [44], CUHK03 [45] and MSMT17 [46].

For video-based person ReID, we evaluate the proposed approach on the MARS
[47], which is one of the largest dataset for video based person Re-ID. It
consists of $17,503$ tracklets and $1,261$ identities.

For image retrieval, we conduct experiments on the popular ROxford and RParis
[48] datasets. Each dataset contains 70 query images, which are divided into
three splits: Easy, Medium and Hard. The Easy split ignores hard queries, the
Medium split contains both easy and hard ones, while the Hard split only
considers hard queries.

TABLE I: Comparison with state-of-the-art methods for person Re-ID.  Method | Reference | Market | Duke | MSMT17 | CUHK03
---|---|---|---|---|---
Rank-1 | mAP | Rank-1 | mAP | Rank-1 | mAP | Rank-1 | mAP
Deep GSRW [6] | CVPR18 | 92.7 | 82.5 | 80.7 | 66.4 | - | - | 94.9 | 94.0
SGGNN [7] | ECCV18 | 92.3 | 82.8 | 81.1 | 68.2 | - | - | 95.3 | 94.3
RED [49] | CVPR19 | 94.7 | 91.0 | - | - | - | - | - | -
UED [50] | CVPR19 | 95.9 | 92.8 | - | - | - | - | - | -
SFT + KR [29] | ICCV19 | 93.5 | 90.6 | 88.3 | 83.3 | 76.1 | 60.8 | 71.7 | 68.7
SFT + LBR [29] | ICCV19 | 94.1 | 87.5 | 90.0 | 79.6 | 79.0 | 58.3 | 74.3 | 71.7
ISP [51] | ECCV20 | 95.3 | 88.6 | 89.6 | 80.0 | - | - | 76.5 | 74.1
MPN [52] | TPAMI20 | 96.3 | 89.4 | 91.5 | 82.0 | 83.5 | 62.7 | 85.0 | 81.1
MGN + CircleLoss [53] | CVPR20 | 96.1 | 87.4 | - | - | 76.9 | 52.1 | - | -
Resnet50 + CircleLoss [53] | CVPR20 | 94.2 | 84.9 | - | - | 76.3 | 50.2 | - | -
Deep-Person [54] | PR20 | 92.3 | 79.6 | 80.9 | 64.8 |  |  |  |
OSNet [55] | TPAMI21 | 94.8 | 86.7 | 88.7 | 76.6 | 79.1 | 55.1 | 72.3 | 67.8
AGW [56] | TPAMI21 | 95.1 | 87.8 | 89.0 | 79.6 | 68.3 | 49.1 | 63.6 | 62.0
LAG-Net [57] | TMM21 | 95.6 | 89.5 | 90.4 | 81.6 | - | - | 85.1 | 82.2
MGN + FIDI [58] | TMM21 | 95.4 | 86.9 | 89.7 | 79.8 | - | - | 78.9 | 76.3
OSNet + AutoLoss-GMS [59] | CVPR22 | 95.7 | 88.9 | – | – | 83.7 | 62.6 | 74.5 | 72.6
RANGEv2 [60] | PR22 | 94.7 | 86.8 | 87.0 | 78.2 | - | - | - | -
SDN [61] | PR22 | 95.8 | 89.6 | 90.9 | 81.0 | - | - | 76.9 | 74.5
BoT [14] | CVPRW19 | 94.5 | 85.9 | 86.5 | 76.4 | 63.4 | 45.1 | 58.0 | 56.6
BoT + KR [3] | – | 95.4 | 94.2 | 90.2 | 89.1 | 64.3 | 57.7 | 68.7 | 68.1
BoT + ECN [4] | – | 95.8 | 93.2 | 90.9 | 87.0 | 64.1 | 57.1 | 68.1 | 68.0
BoT + LBR [29] | – | 95.7 | 91.3 | 89.7 | 84.4 | 63.5 | 45.5 | 66.2 | 61.5
BoT + GCR | – | 96.1 | 94.7 | 91.5 | 89.7 | 64.9 | 58.5 | 69.8 | 68.4
MPN [52] | TPAMI20 | 96.3 | 89.4 | 91.5 | 82.0 | 83.5 | 62.7 | 85.0 | 81.1
MPN + KR [3] | – | 95.6 | 94.5 | 90.5 | 89.6 | 85.6 | 76.4 | 89.2 | 89.0
MPN + ECN [4] | – | 95.1 | 94.0 | 90.8 | 88.3 | 85.3 | 76.1 | 88.2 | 88.2
MPN + GCR | - | 96.6 | 95.1 | 92.9 | 91.3 | 86.8 | 76.9 | 89.7 | 89.0
TABLE II: Comparison with state-of-the-art methods for video-based person Re-
ID.

Method | Reference | MARS
---|---|---
Rank-1 | mAP
DSAN [62] | TMM18 | 73.5 | –
AGRL [8] | TIP20 | 89.5 | 81.9
VKD [63] | ECCV20 | 89.4 | 83.1
MGH [64] | CVPR20 | 90.0 | 85.8
PhD [65] | CVPR21 | 88.9 | 86.2
STRF [66] | ICCV21 | 90.3 | 86.1
DenseIL [67] | ICCV21 | 90.8 | 87.0
PiT [68] | TII22 | 90.2 | 86.8
SINet [69] | CVPR22 | 91.0 | 86.2
MSTAT [70] | TMM22 | 91.8 | 85.3
SGWCNN [71] | PR22 | 90.0 | 85.7
BoT [14] | CVPRW19 | 85.8 | 79.7
BoT + KR [3] | – | 84.3 | 85.2
BoT + ECN [4] | – | 88.1 | 85.6
BoT + LBR [29] | – | 87.4 | 82.5
BoT + GCRV | – | 89.0 | 87.0
MGH [64] | CVPR20 | 90.0 | 85.8
MGH + KR [3] | CVPR17 | 88.8 | 90.7
MGH + ECN [4] | CVPR18 | 92.7 | 90.5
MGH + GCRV | - | 93.8 | 92.8

TABLE III: Comparison with state-of-the-art methods for content-based image
retrieval.

Methods | Reference | Medium | Hard
---|---|---|---
ROxford | RParis | ROxford | RParis
DSM [33] | CVPR19 | 65.3 | 77.4 | 39.2 | 56.2
IRT [72] | arXiv21 | 67.2 | 80.1 | 42.8 | 60.5
HOW+ASMK [73] | ECCV20 | 79.4 | 81.6 | 56.9 | 62.4
DOLG [74] | ICCV21 | 81.5 | 91.0 | 61.1 | 80.3
DALG [75] | arXiv22 | 79.9 | 90.0 | 57.6 | 79.1
GRAP-CD [76] | IVC21 | 70.8 | 81.2 | 31.2 | 62.6
MDA [77] | ICCV21 | 81.8 | 83.3 | 62.2 | 66.2
CSD [78] | CVPR22 | 77.4 | 87.9 | 59.0 | 75.7
TBR [79] | AAAI22 | 82.3 | 89.3 | 66.6 | 78.6
DELG global [34] | ECCV20 | 73.6 | 85.7 | 51.0 | 71.5
DELG global + $\alpha$QE [80] | – | 76.6 | 86.7 | 54.6 | 73.2
DELG global + GV [34] | – | 79.2 | 85.5 | 57.5 | 67.2
DELG global + RRT [36] | – | 78.1 | 86.7 | 60.2 | 75.1
DELG global + GCR | – | 82.1 | 89.2 | 63.1 | 72.4
Our global feature | – | 79.3 | 84.4 | 62.8 | 74.4
Our global feature + GCR | – | 84.3 | 91.9 | 69.7 | 79.9

###  IV-B Implementation Details

For person Re-ID, the original features are extracted using the pre-trained
models of [14, 15, 81], as [14] provides public pre-trained weights for the
Market and Duke datasets, and [81] provides pre-trained weights for the MARS
dataset. The dimensionality of the extracted features is $2,048$.

The default values of the temperature parameter $\gamma$, the number of
nearest neighbors $k$, and the number of iterations $T$ are 0.2, 15 and 3,
respectively. The weight parameter $\lambda$ of the regularization term in the
profile vector generation is 10 on the MARS dataset.

###  IV-C Results of Person Re-identification

We first apply the proposed method for person Re-ID. The results on four
popular datasets are summarized in Table I.

As representatives, we use the pretrained models of BoT [14] and MPN [52] on
the corresponding dataset to extract features. GCR denotes our re-ranking
method which utilizes both global and cross-camera neighborhood affinities for
person Re-ID. To make a fair comparison, we also reproduce results of most
commonly used re-ranking methods, i.e., k-reciprocal (KR) [3], ECN [4] and LBR
[29], based on the same features as those of our approach.

It can be found that $BoT\\!+\\!GCR$ outperforms the origin baseline $BoT$ by
a large margin. Meanwhile, $BoT\\!+\\!GCR$ has better performances those of
other re-ranking methods for both Rank-1 and mAP and on four datasets. We can
also see that, augmented with state-of-the-art features such as MPN [52], our
approach dramatically outperforms the recent state-of-the-art methods, and
also consistently beats the other re-ranking methods. The results evidently
demonstrate the superiority of our approach over previous re-ranking
counterparts.

###  IV-D Results of Video-Based Person Re-identification

The results of video-based person Re-ID on the popular MARS dataset are
provided in Table II. Recent state-of-the-art methods for this task are PIT
[68] and SINet [69], which utilize multi-direction and multi-scale pyramid in
transformer and salient-to-broad transition with enhancement, respectively.
The proposed Graph Convolution based Re-ranking for Video-based retrieval is
denoted as GCRV. We choose the recent representative video-based person Re-ID
approach MGH [64] and the widely used BoT [14] as baselines. Using BoT [14] as
the baseline, our approach significantly beats the widely used re-ranking
approaches, i.e., KR [3], ECN [4] and LBR [29], and improves the baseline by
3.2% and 7.3% for the criterion of Rank-1 and mAP, respectively. The mAP of
our approach is even higher than that of the Transformer based PIT [68] and
the salient-to-broad transition based SINet [69]. While using the strong
baseline MGH [64], our approach yields the state-of-the-art performance on
this dataset and outperforms previous approaches by considerable margins.

###  IV-E Results of Image Retrieval

As the proposed plain GCR in Section III-A is dedicated for general visual
retrieval tasks, we conduct experiments on image retrieval to verify the
effectiveness of this approach. For content-based image retrieval (CBIR) such
as building retrieval, a typical strategy is to first generate an initial rank
list by global features. And then, local features are used to re-rank the
candidates in the rank list. Due to the rigid characteristic of buildings, the
re-ranking methods are often based on geometric verifications. In other words,
two images should be semantically closer if they have more matched points
generated by the affine operation. Typical re-ranking methods for CBIR include
Query Expansion [80] ($\alpha$QE) and geometric-based methods such as GV [34],
RRT [36] and SuperGlue [35]. Different from person Re-ID, similarity or
feature based re-ranking methods have seldom been exploited for building
retrieval.

The ROxford and RParis datasets focus on building retrieval where the
buildings might be occluded or not salient in the image. This setting of CBIR
is more complicated than person Re-ID, as images of Re-ID are tightly cropped.
The results on the two datasets are given in Table III. We first use the same
global features as DELG [34], and evaluate our approach as well as the re-
ranking counterparts. As can be seen from the table, geometric-based re-
ranking methods perform better than the naive similarity-based query
expansion. However, the proposed GCR outperforms the geometric-based re-
ranking. The results indicate that the internal appearance relationships among
multiple building images are also important when compared with geometric
relationships.

We also train a global image feature extractor based on [14]. The proposed GCR
based on these features achieves state-of-the-art performances on both
datasets, outperforming the recent state-of-the-art approaches by large
margins. Particularly, GCR improves the baseline of global features by 5.0%
and 7.5% for the Medium split on the ROxford and RParis datasets,
respectively.

TABLE IV: Effect of global or cross-camera affinity graphs in the proposed GCR
for person Re-ID. For simplicity, Cross and Global denote the cross-camera
similarity graph and global similarity graph, respectively.

Method | Market | Duke
---|---|---
Rank-1 | mAP | Rank-1 | mAP
GCR w/o Cross | 95.9 | 94.6 | 90.1 | 89.4
GCR w/o Global | 96.2 | 93.1 | 91.6 | 86.8
GCR | 96.0 | 94.7 | 91.5 | 89.7

(a) rank-1 curve

(b) mAP curve

Figure 4: The performance curves under different $\alpha$. Figure 5: Ablation studies for the GCRV and performance comparisons of the GCR with different graphs. TABLE V: The computation time of re-ranking methods on the Market-1501 dataset. Method | KR [3] | ECN [4] | GCR | GCR_Local
---|---|---|---|---
Time (s) | 76 | 72 | 24 | 10

(a) Rank-1 ($k=5$)

(b) Rank-1 ($k=15$)

(c) Rank-1 ($k=50$)

(d) mAP ($k=5$)

(e) mAP ($k=15$)

(f) mAP ($k=50$)

Figure 6: Sensitivity analysis of parameters in the proposed GCR.

###  IV-F Experimental Analysis

####  IV-F1 Ablation Study

We evaluate the effectiveness of the two nearest neighbor graphs for person
Re-ID. The results are shown in Table IV. We find that only using the cross-
camera similarity graph yields a high Rank-1, but a low value of mAP. In
contrast, the global similarity graph achieves a high mAP. By combining the
two graphs, ideal performance is achieved with both good performances of mAP
and Rank-1 with the help of global and cross-camera similarity graphs,
respectively.

As shown in Eq. (17), there is a trade-off hyper-parameter between the two
graphs. We plot accuracy curves with respect to different $\alpha$ in Fig. 4.
It can be seen that Rank-1 saturates for $\alpha<0.7$, while mAP reaches the
peak at $\alpha=0.7$. Since mAP is often more important for retrieval cases,
we select the hyper-parameter for the sake of better mAP and set $\alpha=0.7$.
As human pose and view orientation are two main factors that affect the visual
appearance in the image, the global and cross-camera similarity graphs
successfully align representations from both human poses and view
orientations, thus getting the best retrieval performances.

The proposed GCRV for video based person Re-ID combines techniques of both
Profile Vector Generation (PVG) and Graph Convolution based Re-ranking (GCR).
The ablated studies of GCRV on the MARS dataset are shown in Fig. 5(a). The
baseline uses the mean feature vector in Eq. (18) to represent the tracklet,
and does not adopt re-ranking. Baseline + GCR is the variant that uses the
mean feature vector instead of the PVG. Baseline + PVG is the variant of GCRV
without the GCR re-ranking. We find that PVG improves the performances of the
mean feature vector for Rank-1 and mAP by 2.4% and 1.7%, respectively, which
clearly demonstrates the effectiveness of the proposed profile vector
generation and its superiority over the commonly used mean feature vector.

(a) T=1

(b) T=3

(c) T=5

Figure 7: Feature distributions for GCR with different iterations.

(a) Ours

(b) KR [3]

(c) ECN [4]

(d) LBR [29]

(e) QE [5]

Figure 8: Feature visualizations of different re-ranking methods. Figure 9:
The visualization of results of person Re-ID for the proposed GCR with
different iterations. $T=0$ indicates the baseline without re-ranking, and
correctly retrieved persons are marked with blue bounding boxes. Figure 10:
The visualization of results of person Re-ID for different re-ranking methods.
The baseline involves no re-ranking. The top-10 retrieval results of the query
are provided and correctly retrieved persons are marked with blue bounding
boxes. Figure 11: The visualization of results of video-based person Re-ID for
different re-ranking methods on the MARS [47] dataset. Each video is
represented by a sequence of six frames which are stitched into a large image.
The top-5 results are provided from left to right and correctly retrieved
videos of the query person are marked with blue bounding boxes.

####  IV-F2 Efficiency Analysis

In Algorithm 1, we propose a decentralized and synchronous feature propagation
method based on local similarity matrices. This method is designed for
parallel or distributed computing at the possible sacrifice of accuracy. Fig.
5(b) shows performance comparisons of the proposed GCR for person Re-ID with
different similarity graphs on the Market dataset. For simplicity,
_asymmetric_ , _symmetric_ and _local_ denotes that the feature propagation
adopts the asymmetric, symmetric and local similarity matrices, respectively.
The performances of symmetric matrices are a little better than those of
asymmetric ones. Compared with symmetric matrices, local matrices only
slightly degrade the retrieval performance. The results demonstrate the
effectiveness of the decentralized and synchronous feature propagation and
suggest its vast potential applications for large-scale visual retrieval
applications.

Efficiency is an important goal for algorithm design in real-world retrieval
applications. Existing re-ranking methods such as KR [3] suffer from the heavy
computation. Table V lists the computation time of different re-ranking
methods with the same hardware settings of 24 cores Platinum 8163 CPU. For
simplicity, GCR_Local denotes the decentralized and synchronous feature
propagation variant. As can be seen, KR [4] and ECN [3] suffer from low
computation speed due to complex set operations. In contrast, our approach
only relies on simple matrix operations and achieves both excellent accuracy
and efficiency.

It should be noted that most of the computation costs of the proposed method
focus on nearest neighbor graph construction which requires pairwise distance
computing for all gallery pairs. Like other re-ranking methods such as KR [3]
and ECN [4], the time complexity of the proposed GCR is $O({N^{2}}\log N)$,
where $N$ denotes the number of samples in the database. The computation
complexity of this variant in Algorithm 1 is the same as the original method.
However, nearest neighbor graphs in the database can be calculated and stored
in advance, so the computation complexity can be reduced to $O(N\log N)$ in
practical applications.

####  IV-F3 Parameter Sensitivity

There are three parameters in the proposed GCR: the temperature parameter
$\gamma$, the number of nearest neighbors $k$, and the number of iterations
$T$. The parameter sensitivity on the Market-1501 dataset is illustrated in
Fig. 6. We observe that a small value of $k$ leads to poor performance as the
propagated information from such a small number of nearest neighbors is rather
limited. In addition, the performance is saturated or even degraded when $k$
is too large (e.g., $k\geq 50$ ), as it increases the computational burden and
introduces additional noises from semantically unrelated images. Thus,
choosing an appropriate number of nearest neighbors is a bit important for the
proposed method. For the sake of simplicity and good performance, we set
$k=15$ for all datasets.

The best values of $\gamma$ and $T$ are somewhat related to the choice of $k$.
Generally, when $k$ is small, a large $gamma$ and a relatively large $T$
(e.g., $T=3$) is preferred to achieve good performance. And when $k$ is large
(e.g., $k=50$), smaller values of $\gamma$ and $T$ yield better performance.
It can be interpreted that a smaller $\gamma$ lets the proposed method focus
on more similar images, and hurts performance if only a small number of top
nearest neighbors are selected. However, the setting of a smaller $\gamma$
would improve the performance when the nearest neighbors are redundant and
noisy. More iterations allow feature propagation among more distant neighbors,
which could increase the performance when $k$ is small and useful nearest
neighbors are limited, however, decrease the performance when $k$ is large
with the influence of noisy features. Since $\gamma$ and $T$ are relatively
not sensitive to the final performance, we keep them as $\gamma=0.2$ and $T=3$
in all experiments.

Changing the parameters such as the number of iterations does not affect the
time complexity. Our approach accelerates the re-ranking process by avoiding
inefficient computational operations and only using matrix operations. In
addition, our approach is very suitable for GPU acceleration.

####  IV-F4 Visualization

To further prove the superiority of the proposed method, we visually
investigate the changes of features in the intermediate process of the GCR and
compare visualized features among different feature propagation based re-
ranking methods. Samples on the MARS dataset are selected and features are
visualized using t-SNE [82]. Fig. 7 shows the feature distributions for GCR
with different iterations.

It can be seen that features from the same person become more aggregated with
the propagation of features. With more iterations $T>3$, the samples in blue
are over-clustered into three points as seen in Fig. 7(c). Such over-
clustering might cause matching mistakes. Similar results can be found in Fig.
6, where more iterations $(T>3)$ no longer improve the accuracy.

Fig. 8 visualizes and compares refined data points of different re-ranking
approaches.  Query Expansion (QE) [5] treats each neighbour equally, and LBR
[29] performs local blurring on the gallery features while keeping query
features unchanged. As can be seen, cyan data points in the bottom right
corner of the Fig. 8(d) and 8(e) are more scattered than those in Fig. 8(a).
It is indicated that both QE and LBR could not pull features of the same
person similar enough to achieve discriminative representations. Data points
of the same color in Fig. 8(a), 8(b) and 8(c) are well clustered and have
compact distributions, which demonstrates the effectiveness of feature or
distance updating. It should be noted that the input of the t-SNE is the
updated similarity matrix instead of refined features for the re-ranking
methods which do not involve feature propagation.

We also compare the retrieval results of person Re-ID among different
approaches with examples on the Market dataset. The results of the GCR with
different iterations are shown in Fig. 9. For both query (a) and (b), four of
the top-5 results are correct when $T=3$, while no more than three are correct
for other counterparts. In general,  the proposed re-ranking method pushes
correct persons in the front of retrieved results, and $T=3$ has the best
overall retrieval results.

For person Re-ID, retrieval results of different re-ranking methods are shown
in Fig. 10. Compared with the widely adopted re-ranking methods such as KR [3]
and ECN [4], our approach obtains comparable or even better refined ranked
results. In Fig. 10, the top-1 retrievals are all wrong except for ours for
the query (a), while ours is the only approach where the top-3 retrievals are
all correct for the query (b).

Retrieval results of video-based person Re-ID are also shown in Fig. 11. For
the query (a) and (c), only our results are correct for the top-1 retrieval.
Particularly, given the query (c) which contains images of the person taken
from the back view, the other approaches fail while our approach correctly
finds images of the same person taken from the front view. The results vividly
demonstrate the effectiveness of our approach for visual retrieval tasks such
as person Re-ID.

##  V Conclusion and Future Works

In this paper, we propose a general Graph Convolution based Re-ranking (GCR)
method for visual retrieval. We extend this approach for cross-camera
retrieval as well as video-based retrieval, and accordingly propose Graph
Convolution based Re-ranking for Video (GCRV). Extensive experiments on three
retrieval tasks, i.e., content-based image retrieval, person Re-ID, and video
based person Re-ID evidently demonstrate the effectiveness of the proposed re-
ranking method. Further ablation studies are analyzed to verify the
effectiveness of the composed component, and parameter sensitivities are also
conducted to analyze the robustness to hyper-parameters. Although this paper
addresses the problems of inefficiency and inflexibility of existing re-
ranking approaches, the performance of the variant for parallel computing
deteriorates slightly. In the future, we will continue improving GCN based re-
ranking and mainly focus on more efficient re-ranking algorithms on the GPU.

## References

  * [1] T. Mei, Y. Rui, S. Li, and Q. Tian, “Multimedia search reranking: A literature survey,” _ACM Computing Surveys (CSUR)_ , vol. 46, no. 3, pp. 1–38, 2014\.
  * [2] D. Tao _et al._ , “Visual reranking: From objectives to strategies,” _IEEE MultiMedia_ , vol. 18, no. 3, pp. 12–21, 2011.
  * [3] Z. Zhong, L. Zheng, D. Cao, and S. Li, “Re-ranking person re-identification with k-reciprocal encoding,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. Honolulu, HI, USA: IEEE, 2017, pp. 1318–1327.
  * [4] M. Saquib Sarfraz, A. Schumann, A. Eberle, and R. Stiefelhagen, “A pose-sensitive embedding for person re-identification with expanded cross neighborhood re-ranking,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. Salt Lake City, UT, USA: IEEE, 2018, pp. 420–429.
  * [5] O. Chum, J. Philbin, J. Sivic, M. Isard, and A. Zisserman, “Total recall: Automatic query expansion with a generative feature model for object retrieval,” in _IEEE International Conference on Computer Vision_. Rio de Janeiro, Brazil: IEEE, 2007, pp. 1–8.
  * [6] Y. Shen, H. Li, T. Xiao, S. Yi, D. Chen, and X. Wang, “Deep group-shuffling random walk for person re-identification,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. Salt Lake City, UT, USA: IEEE, 2018, pp. 2265–2274.
  * [7] Y. Shen, H. Li, S. Yi, D. Chen, and X. Wang, “Person re-identification with deep similarity-guided graph neural network,” in _Proceedings of the European conference on computer vision (ECCV)_. Munich, Germany: Springer, 2018, pp. 486–504.
  * [8] Y. Wu, O. E. F. Bourahla, X. Li, F. Wu, Q. Tian, and X. Zhou, “Adaptive graph representation learning for video person re-identification,” _IEEE Transactions on Image Processing_ , vol. 29, pp. 8821–8830, 2020.
  * [9] X. Zhang, M. Jiang, Z. Zheng, X. Tan, E. Ding, and Y. Yang, “Understanding image retrieval re-ranking: A graph neural network perspective,” _arXiv preprint arXiv:2012.07620_ , 2020.
  * [10] Y. Zhang, Q. Qian, C. Liu, W. Chen, F. Wang, H. Li, and R. Jin, “Graph convolution for re-ranking in person re-identification,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 2704–2708.
  * [11] Y. Sun, L. Zheng, W. Deng, and S. Wang, “Svdnet for pedestrian retrieval,” in _Proceedings of the IEEE International Conference on Computer Vision_. Venice, Italy: IEEE, 2017, pp. 3800–3808.
  * [12] Z. Zheng, L. Zheng, and Y. Yang, “A discriminatively learned cnn embedding for person reidentification,” _ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM)_ , vol. 14, no. 1, pp. 1–20, 2017.
  * [13] W. Chen, X. Chen, J. Zhang, and K. Huang, “A multi-task deep network for person re-identification,” in _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence_. San Francisco, California, USA: AAAI, 2017, pp. 3988–3994.
  * [14] H. Luo, Y. Gu, X. Liao, S. Lai, and W. Jiang, “Bag of tricks and a strong baseline for deep person re-identification,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_. Long Beach, CA, USA: IEEE, 2019, pp. 0–0.
  * [15] H. Luo, W. Jiang, Y. Gu, F. Liu, X. Liao, S. Lai, and J. Gu, “A strong baseline and batch normalization neck for deep person re-identification,” _IEEE Transactions on Multimedia_ , vol. 22, no. 10, pp. 2597–2609, 2019\.
  * [16] Y. Sun, L. Zheng, Y. Yang, Q. Tian, and S. Wang, “Beyond part models: Person retrieval with refined part pooling (and a strong convolutional baseline),” in _Proceedings of the European Conference on Computer Vision (ECCV)_. Munich, Germany: Springer, 2018, pp. 480–496.
  * [17] Y. Suh, J. Wang, S. Tang, T. Mei, and K. Mu Lee, “Part-aligned bilinear representations for person re-identification,” in _Proceedings of the European Conference on Computer Vision (ECCV)_. Munich, Germany: Springer, 2018, pp. 402–419.
  * [18] D. Li, X. Chen, Z. Zhang, and K. Huang, “Learning deep context-aware features over body and latent parts for person re-identification,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. Honolulu, HI, USA: IEEE, 2017, pp. 384–393.
  * [19] X. Zhang, H. Luo, X. Fan, W. Xiang, Y. Sun, Q. Xiao, W. Jiang, C. Zhang, and J. Sun, “Alignedreid: Surpassing human-level performance in person re-identification,” _arXiv preprint arXiv:1711.08184_ , vol. arXiv, no. preprint, pp. 1–1, 2017.
  * [20] Y. Zhang, Y. Huang, S. Yu, and L. Wang, “Cross-view gait recognition by discriminative feature learning,” _IEEE Transactions on Image Processing_ , vol. 29, pp. 1001–1015, 2019.
  * [21] W. Liu, Y. Wen, Z. Yu, M. Li, B. Raj, and L. Song, “Sphereface: Deep hypersphere embedding for face recognition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. Honolulu, HI, USA: IEEE, 2017, pp. 212–220.
  * [22] H. Wang, Y. Wang, Z. Zhou, X. Ji, D. Gong, J. Zhou, Z. Li, and W. Liu, “Cosface: Large margin cosine loss for deep face recognition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. Salt Lake City, UT, USA: IEEE, 2018, pp. 5265–5274.
  * [23] J. Deng, J. Guo, N. Xue, and S. Zafeiriou, “Arcface: Additive angular margin loss for deep face recognition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. Long Beach, CA, USA: IEEE, 2019, pp. 4690–4699.
  * [24] R. Hadsell, S. Chopra, and Y. LeCun, “Dimensionality reduction by learning an invariant mapping,” in _IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , vol. 2. New York, NY, USA: IEEE, 2006, pp. 1735–1742.
  * [25] F. Schroff, D. Kalenichenko, and J. Philbin, “Facenet: A unified embedding for face recognition and clustering,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. Boston, MA, USA: IEEE, 2015, pp. 815–823.
  * [26] Z. Zhong, L. Zheng, G. Kang, S. Li, and Y. Yang, “Random erasing data augmentation.” in _AAAI_. New York, NY, USA: AAAI, 2020, pp. 13 001–13 008.
  * [27] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, “Dropout: a simple way to prevent neural networks from overfitting,” _The Journal of Machine Learning Research_ , vol. 15, no. 1, pp. 1929–1958, 2014.
  * [28] Z. Yu, Y. Zhao, B. Hong, Z. Jin, J. Huang, D. Cai, and X.-S. Hua, “Apparel-invariant feature learning for person re-identification,” _IEEE Transactions on Multimedia_ , vol. 24, pp. 4482–4492, 2021.
  * [29] C. Luo, Y. Chen, N. Wang, and Z. Zhang, “Spectral feature transformation for person re-identification,” in _Proceedings of the IEEE International Conference on Computer Vision_. Seoul, Korea: IEEE, 2019, pp. 4976–4985.
  * [30] H. Jegou, H. Harzallah, and C. Schmid, “A contextual dissimilarity measure for accurate and efficient image search,” in _IEEE Conference on Computer Vision and Pattern Recognition_. Minneapolis, MN, USA: IEEE, 2007, pp. 1–8.
  * [31] D. Qin, S. Gammeter, L. Bossard, T. Quack, and L. Van Gool, “Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors,” in _IEEE Conference on Computer Vision and Pattern Recognition_. Colorado Springs, CO, USA: IEEE, 2011, pp. 777–784.
  * [32] J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, “Object retrieval with large vocabularies and fast spatial matching,” in _IEEE Conference on Computer Vision and Pattern Recognition_. IEEE, 2007, pp. 1–8.
  * [33] O. Siméoni, Y. Avrithis, and O. Chum, “Local features and visual words emerge in activations,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 11 651–11 660.
  * [34] B. Cao, A. Araujo, and J. Sim, “Unifying deep local and global features for image search,” in _European Conference on Computer Vision_. Springer, 2020, pp. 726–743.
  * [35] P.-E. Sarlin, D. DeTone, T. Malisiewicz, and A. Rabinovich, “Superglue: Learning feature matching with graph neural networks,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 4938–4947.
  * [36] F. Tan, J. Yuan, and V. Ordonez, “Instance-level image retrieval using reranking transformers,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 12 105–12 115.
  * [37] Y. Zhu, W. Xu, J. Zhang, Y. Du, J. Zhang, Q. Liu, C. Yang, and S. Wu, “A survey on graph structure learning: Progress and opportunities,” _arXiv e-prints_ , pp. arXiv–2103, 2021.
  * [38] W. Jin, Y. Ma, X. Liu, X. Tang, S. Wang, and J. Tang, “Graph structure learning for robust graph neural networks,” in _ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020, pp. 66–74.
  * [39] P. Ji, T. Zhang, H. Li, M. Salzmann, and I. Reid, “Deep subspace clustering networks,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [40] T. Zhang, P. Ji, M. Harandi, W. Huang, and H. Li, “Neural collaborative subspace clustering,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 7384–7393.
  * [41] T. Zhang, P. Ji, M. Harandi, R. Hartley, and I. Reid, “Scalable deep k-subspace clustering,” in _Asian Conference on Computer Visio_. Springer, 2019, pp. 466–481.
  * [42] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _International Conference on Learning Representations_. Toulon, France: OpenReview.net, 2016, pp. 1–1.
  * [43] L. Zheng, L. Shen, L. Tian, S. Wang, J. Wang, and Q. Tian, “Scalable person re-identification: A benchmark,” in _Proceedings of the IEEE International Conference on Computer Vision_. Santiago, Chile: IEEE, 2015, pp. 1116–1124.
  * [44] E. Ristani, F. Solera, R. Zou, R. Cucchiara, and C. Tomasi, “Performance measures and a data set for multi-target, multi-camera tracking,” in _European Conference on Computer Vision_. Amsterdam, The Netherlands: Springer, 2016, pp. 17–35.
  * [45] W. Li, R. Zhao, T. Xiao, and X. Wang, “Deepreid: Deep filter pairing neural network for person re-identification,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2014, pp. 152–159.
  * [46] L. Wei, S. Zhang, W. Gao, and Q. Tian, “Person transfer gan to bridge domain gap for person re-identification,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 79–88.
  * [47] L. Zheng, Z. Bie, Y. Sun, J. Wang, C. Su, S. Wang, and Q. Tian, “Mars: A video benchmark for large-scale person re-identification,” in _European Conference on Computer Vision_. Amsterdam, The Netherlands: Springer, 2016, pp. 868–884.
  * [48] F. Radenović, A. Iscen, G. Tolias, Y. Avrithis, and O. Chum, “Revisiting oxford and paris: Large-scale image retrieval benchmarking,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 5706–5715.
  * [49] S. Bai, Z. Zhou, J. Wang, X. Bai, L. Jan Latecki, and Q. Tian, “Ensemble diffusion for retrieval,” in _Proceedings of the IEEE International Conference on Computer Vision_. Venice, Italy: IEEE, 2017, pp. 774–783.
  * [50] S. Bai, P. Tang, P. H. Torr, and L. J. Latecki, “Re-ranking via metric fusion for object retrieval and person re-identification,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. Long Beach, CA, USA: IEEE, 2019, pp. 740–749.
  * [51] K. Zhu, H. Guo, Z. Liu, M. Tang, and J. Wang, “Identity-guided human semantic parsing for person re-identification,” in _Proceedings of the European conference on computer vision (ECCV)_. Glasgow, UK: Springer, 2020, pp. 346–363.
  * [52] C. Ding, K. Wang, P. Wang, and D. Tao, “Multi-task learning with coarse priors for robust part-aware person re-identification,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 44, no. 3, pp. 1474–1488, 2020\.
  * [53] Y. Sun, C. Cheng, Y. Zhang, C. Zhang, L. Zheng, Z. Wang, and Y. Wei, “Circle loss: A unified perspective of pair similarity optimization,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. Seattle, WA, USA: IEEE, 2020, pp. 6398–6407.
  * [54] X. Bai, M. Yang, T. Huang, Z. Dou, R. Yu, and Y. Xu, “Deep-person: Learning discriminative deep features for person re-identification,” _Pattern Recognition_ , vol. 98, p. 107036, 2020.
  * [55] K. Zhou, Y. Yang, A. Cavallaro, and T. Xiang, “Learning generalisable omni-scale representations for person re-identification,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 44, no. 9, pp. 5056–5069, 2022.
  * [56] M. Ye, J. Shen, G. Lin, T. Xiang, L. Shao, and S. C. Hoi, “Deep learning for person re-identification: A survey and outlook,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 44, no. 6, pp. 2872–2893, 2021\.
  * [57] X. Gong, Z. Yao, X. Li, Y. Fan, B. Luo, J. Fan, and B. Lao, “Lag-net: Multi-granularity network for person re-identification via local attention system,” _IEEE Transactions on Multimedia_ , vol. 24, pp. 217–229, 2021\.
  * [58] C. Yan, G. Pang, X. Bai, C. Liu, X. Ning, L. Gu, and J. Zhou, “Beyond triplet loss: Person re-identification with fine-grained difference-aware pairwise loss,” _IEEE Transactions on Multimedia_ , vol. 24, pp. 1665–1677, 2021\.
  * [59] H. Gu, J. Li, G. Fu, C. Wong, X. Chen, and J. Zhu, “Autoloss-gms: Searching generalized margin-based softmax loss function for person re-identification,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 4744–4753.
  * [60] G. Wu, X. Zhu, and S. Gong, “Learning hybrid ranking representation for person re-identification,” _Pattern Recognition_ , vol. 121, p. 108239, 2022.
  * [61] T. Si, F. He, H. Wu, and Y. Duan, “Spatial-driven features based on image dependencies for person re-identification,” _Pattern Recognition_ , vol. 124, p. 108462, 2022.
  * [62] L. Wu, Y. Wang, J. Gao, and X. Li, “Where-and-when to look: Deep siamese attention networks for video-based person re-identification,” _IEEE Transactions on Multimedia_ , vol. 21, no. 6, pp. 1412–1424, 2018.
  * [63] A. Porrello, L. Bergamini, and S. Calderara, “Robust re-identification by multiple views knowledge distillation,” in _European Conference on Computer Vision_. Glasgow, UK: Springer, 2020, pp. 93–110.
  * [64] Y. Yan, J. Qin, J. Chen, L. Liu, F. Zhu, Y. Tai, and L. Shao, “Learning multi-granular hypergraphs for video-based person re-identification,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. Seattle, WA, USA: IEEE, 2020, pp. 2899–2908.
  * [65] J. Zhao, F. Qi, G. Ren, and L. Xu, “Phd learning: Learning with pompeiu-hausdorff distances for video-based vehicle re-identification,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 2225–2235.
  * [66] A. Aich, M. Zheng, S. Karanam, T. Chen, A. K. Roy-Chowdhury, and Z. Wu, “Spatio-temporal representation factorization for video-based person re-identification,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 152–162.
  * [67] T. He, X. Jin, X. Shen, J. Huang, Z. Chen, and X.-S. Hua, “Dense interaction learning for video-based person re-identification,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 1490–1501.
  * [68] X. Zang, G. Li, and W. Gao, “Multidirection and multiscale pyramid in transformer for video-based pedestrian retrieval,” _IEEE Transactions on Industrial Informatics_ , vol. 18, no. 12, pp. 8776–8785, 2022.
  * [69] S. Bai, B. Ma, H. Chang, R. Huang, and X. Chen, “Salient-to-broad transition for video person re-identification,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 7339–7348.
  * [70] Z. Tang, R. Zhang, Z. Peng, J. Chen, and L. Lin, “Multi-stage spatio-temporal aggregation transformer for video person re-identification,” _IEEE Transactions on Multimedia_ , 2022.
  * [71] Y. Yao, X. Jiang, H. Fujita, and Z. Fang, “A sparse graph wavelet convolution neural network for video-based person re-identification,” _Pattern Recognition_ , vol. 129, p. 108708, 2022.
  * [72] A. El-Nouby, N. Neverova, I. Laptev, and H. Jégou, “Training vision transformers for image retrieval,” _arXiv preprint arXiv:2102.05644_ , 2021\.
  * [73] G. Tolias, T. Jenicek, and O. Chum, “Learning and aggregating deep local descriptors for instance-level recognition,” in _European Conference on Computer Vision_. Springer, 2020, pp. 460–477.
  * [74] M. Yang, D. He, M. Fan, B. Shi, X. Xue, F. Li, E. Ding, and J. Huang, “Dolg: Single-stage image retrieval with deep orthogonal fusion of local and global features,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 11 772–11 781.
  * [75] Y. Song, R. Zhu, M. Yang, and D. He, “Dalg: Deep attentive local and global modeling for image retrieval,” _arXiv preprint arXiv:2207.00287_ , 2022.
  * [76] X. Zhu, H. Wang, P. Liu, Z. Yang, and J. Qian, “Graph-based reasoning attention pooling with curriculum design for content-based image retrieval,” _Image and Vision Computing_ , vol. 115, p. 104289, 2021.
  * [77] H. Wu, M. Wang, W. Zhou, and H. Li, “Learning deep local features with multiple dynamic attentions for large-scale image retrieval,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 11 416–11 425.
  * [78] H. Wu, M. Wang, W. Zhou, H. Li, and Q. Tian, “Contextual similarity distillation for asymmetric image retrieval,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 9489–9498.
  * [79] H. Wu, M. Wang, W. Zhou, Y. Hu, and H. Li, “Learning token-based representation for image retrieval,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 36, no. 3, 2022, pp. 2703–2711.
  * [80] F. Radenović, G. Tolias, and O. Chum, “Fine-tuning cnn image retrieval with no human annotation,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 41, no. 7, pp. 1655–1668, 2018.
  * [81] C.-T. Liu, C.-W. Wu, Y.-C. F. Wang, and S.-Y. Chien, “Spatially and temporally efficient non-local attention network for video-based person re-identification,” in _British Machine Vision Conference_. Cardiff, UK: BMVA Press, 2019, p. 243.
  * [82] L. v. d. Maaten and G. Hinton, “Visualizing data using t-sne,” _Journal of Machine Learning Research_ , vol. 9, no. Nov, pp. 2579–2605, 2008.


# Quantum Annealing for Automated Feature Selection in Stress Detection

Rajdeep Kumar Nath1, Himanshu Thapliyal1∗ and Travis S. Humble2 2Oak Ridge
National Laboratory, Oak Ridge, TN, USA
*Corresponding Author<EMAIL_ADDRESS>1Department of Electrical and Computer Engineering, University of Kentucky, Lexington, KY, USA

###### Abstract

We present a novel methodology for automated feature subset selection from a
pool of physiological signals using Quantum Annealing (QA). As a case study,
we will investigate the effectiveness of QA-based feature selection techniques
in selecting the optimal feature subset for stress detection. Features are
extracted from four signal sources: foot EDA, hand EDA, ECG, and respiration.
The proposed method embeds the feature variables extracted from the
physiological signals in a binary quadratic model. The bias of the feature
variable is calculated using the Pearson correlation coefficient between the
feature variable and the target variable. The weight of the edge connecting
the two feature variables is calculated using the Pearson correlation
coefficient between two feature variables in the binary quadratic model.
Subsequently, D-Wave’s clique sampler is used to sample cliques from the
binary quadratic model. The underlying solution is then re-sampled to obtain
multiple good solutions and the clique with the lowest energy is returned as
the optimal solution. The proposed method is compared with commonly used
feature selection techniques for stress detection. Results indicate that QA-
based feature subset selection performed equally as that of classical
techniques. However, under data uncertainty conditions such as limited
training data, the performance of quantum annealing for selecting optimum
features remained unaffected, whereas a significant decrease in performance is
observed with classical feature selection techniques. Preliminary results show
the promise of quantum annealing in optimizing the training phase of a machine
learning classifier, especially under data uncertainty conditions.

###### Index Terms:

Machine Learning, Feature Selection, Quantum Annealing (QA), Physiological
Signals, Stress

##  I Introduction

Stress detection is an important research topic in health informatics.
Experiencing frequent stress can be a major health concern that can pose a
threat to the physical and mental stability of an individual in the long run.
Chronic effects of stress can cause physiological abnormalities such as
hypertension, stroke, obesity, and diabetes, and psychological conditions such
as cognitive impairments which might lead to the development of Alzheimer’s
Disease in older adults [1][2]. Although stress is an unavoidable aspect of
our daily lives, monitoring and managing stress can significantly reduce the
long-term negative effects of stress. Monitoring and quantifying stress
reliably is not a trivial task as stress is a complex phenomenon and is
influenced by several factors such as environmental factors, mental workload,
task-specific stressors, etc. Researchers have adopted various methods for
detecting stress. The most popular methods for detecting stress are through
monitoring of physiological signals such as EDA (Electrodermal Activity), ECG
(Electrocardiogram), PPG (Photoplethysmogram), RESP (Respiration) and EEG
(Electroencephalogram). Together with these, researchers have also analyzed
behavioral and activity-based features for stress detection [3][4]. Further,
other physiological measures such as eye activity, pupil diameter, speech,
etc. have also been used for stress detection [5]. Figure 1 shows some of the
various measures adopted for monitoring stress levels.

Figure 1: Some of the various physiological measures used for stress
detection.

Although studies have been found that combining different physiological
measures usually increases the performance of the stress classification model,
this might increase the complexity of the system. Moreover, the usefulness of
a particular physiological measure in characterizing stress depends on the
application [6]. For example, it has been found that EDA-based features are
better in detecting stressed states during tasks that involve physical
activity [7]. Similarly, it is found that ECG features are sensitive to
changes in the context of physical activity [7]. Hence, identifying the
optimal set of physiological parameters that can most accurately correlate the
changes in the physiological response with stress is an important research
topic [6].

Usually feature selection methods are used for reducing the set of extracted
features before training a machine learning classifier. Once the important set
of features are identified in the training phase, subsequently, we will only
need to extract those features for prediction in the deployment phase.
Typically, features are selected by ranking the features based on their
association with the target variable. This association is usually quantified
by some statistical measures such as correlation coefficient, mutual
information, p-value, etc. Subsequently, the best set of features is selected
by following a greedy search technique [8][3]. However, a major problem with
greedy search is that it is not guaranteed to reach the global minimum of the
solution space because it does not evaluate all the possible combinations. To
evaluate all the possible combinations, an exhaustive greedy search is
required which is computationally very expensive. For example, if we want to
choose the best performing 20 features from a set of 50 features, there will
be approximately $4.7\times 10^{13}$ combinations.

In this work, we explore the application of quantum annealing for selecting
the optimal set of features from EDA signals collected from hand and foot,
ECG, and RESP signals. The EDA, ECG, and RESP signals were downloaded from a
publicly available database [9]. These physiological signals were collected
during a driving task. During the driving task, the driver was required to
start from rest and then drive through a series of city and highway driving
segments. The physiological signals were annotated with ”Low”, ”Medium”, and
”High” stress for driving segments during rest, highway, and city
respectively. The quantum annealing algorithm is implemented using a physical
quantum computer realized by D-Wave systems [10].

The contribution of this work is as follows:

  * •

A hybrid classical-quantum machine learning pipeline is proposed for
optimizing the number of features used for training the machine learning
classifier.

  * •

The proposed hybrid classical-quantum machine learning pipeline is used to
solve the problem of selecting an optimum subset of features from a pool of
physiological signals for detecting stress in automobile drivers.

  * •

Performance of the QA-based feature selection technique is compared with
typically adopted classical feature selection techniques for stress detection
under limited training data.

The paper is organized as follows: Section II will discuss the background on
quantum annealing briefly. Section III will outline the proposed classical-
quantum hybrid training pipeline. Section IV will discuss the results, and
finally Section V will conclude the work.

##  II Background on Quantum Annealing and Quantum Processing Unit

Quantum annealing is a noisy variant of the adiabatic model of quantum
computation that allows relaxation on the strict requirements of the ideal
adiabatic condition. It is a heuristic search technique to find the global
minimum of an objective function. Theoretically, it has been proven that
quantum annealing is always guaranteed to reach the global minimum with a
faster rate of convergence than classical annealing [11]. In greedy search
techniques, the solution can get stuck in local minima. Quantum annealing
escapes local minima by tunneling through the long energy barriers.

In D-Wave’s quantum annealer, the quantum computation is performed by the QPU
(Quantum Processing Unit). The QPU is mainly a collection of qubits which are
arranged in graph structures. Some of the qubits are interconnected to each
other through couplers. While solving an optimization problem, the qubits are
initialized with the bias of the variables that needs to be optimized. The
strength of the couplers connecting any two qubits are initialized with the
weight of the connection between the two variables. After the annealing the
final values of the biases and weights are returned as the solution to the
optimization problem. The optimized solutions are those that have the lowest
energy configuration. The underlying solutions can be then be re-sampled
n-times to obtain different solutions to the same problem.

##  III Proposed Work

Figure 2 shows the design of the proposed hybrid classical-quantum machine
learning pipeline. This hybrid pipeline consists of a classical subroutine and
a quantum subroutine. We will discuss these subroutines in detail in this
section.

Figure 2: Overview of the proposed work.

###  III-A Classical Subroutine

The classical subroutine executes the preprocessing and feature extraction
stages of the machine learning pipeline.

####  III-A1 Preprocessing

In this module, the EDA signals from hand and foot, ECG, and RESP signals are
normalized and filtered using a low-pass Butterworth filter of order 5 and the
signal components greater than 1 Hz for EDA, 40 Hz for ECG, and 10 Hz for Resp
signals were cut off.

####  III-A2 Feature Extraction

Features were extracted using a running window of 100 seconds and an overlap
of 50 seconds for all four physiological signals. Six features each were
extracted from the EDA signal collected from hand and foot. These six features
comprised of the mean, variance, number of peaks in a time window, sum of the
EDA peaks, and the sum of the response duration of the EDA signal.

For the ECG signal, a total of 15 time-domain features and 6 frequency domain
features were extracted. The time-domain features comprised of the various
statistical measure of the R peaks of ECG signal and the mean, maximum,
minimum, and standard deviation of the heart rate extracted from the ECG
signal. The frequency-domain features comprised of low power, high power, and
very low and high power components of ECG signals, along with their ratios.

For the RESP signal, a total of 6 features were extracted, which included the
mean and variance of the respiration signal. The remaining four features were
the average power in the four frequency bands, (0-0.1 Hz), (0.1-0.2 Hz),
(0.2-0.3 Hz), and (0.3-0.4 Hz). More details on the feature extraction from
these signals can be found in [9].

####  III-A3 Train and Test Split

The entire feature set is first annotated with their respective stress labels,
that is low stress, medium stress, and high stress. Subsequently, the feature
set is divided into train and test sets in the approximate ratio of 70-30. The
train set is then used to compute the bias and weight matrix by computing the
pair-wise feature-target correlation, and feature-feature correlation
respectively. In this work, we have used the Person correlation coefficient to
quantify the feature-feature and feature-target correlation. It is to be noted
that only the weight and the bias matrices are offloaded to the quantum
subroutine and not the entire training dataset.

###  III-B Quantum Subroutine

The quantum subroutine is comprised of a classical software interface that
maps problem instances to the D-Wave QPU. The quantum subroutine consists of a
software interface that translates the real-world problem instance into a
representation that can be solved by the D-Wave’s QPU. To translate the
problem, a binary quadratic model is initialized. The nodes represent the
features, and the strength of the connection between the nodes represents the
interaction between the feature variables. The values of the nodes are
initialized with the biases obtained from the feature-target bias matrix from
the training phase, and the strength of the connection between the nodes is
initialized with the feature-feature weight matrix from the training phase.

After the initialization of the weights and biases, D-Wave’s clique sampler is
used to sample cliques with the lowest energy configuration. The solution
returned by the D-Wave clique sampler is resampled multiple times to obtain
multiple close-to-good solutions and the clique with the lowest energy is
chosen as the best solution. The nodes that form the cliques with the lowest
energy configuration is hypothesized as the best performing optimum subset of
features.

##  IV Results and Analysis

In this section, we will discuss the performance of the QA-based feature
selection technique with typically adopted feature selection techniques for
stress detection such as Pearson correlation ranking-based feature selection,
p-value based feature selection, and mutual-information-based feature
selection. For simplicity, the default parameters of the quantum annealer was
used in this work.

###  IV-A Evaluation Objective

The objective of our analysis is to verify the effectiveness of the QA-based
feature selection algorithm in selecting the optimum set of features for
stress level prediction. In this section, we will perform a quantitative and
qualitative evaluation of the QA-based feature selection method. A comparison
with classical feature selection techniques under 100%, 30%, 20%, and 10% of
the training data will also be analyzed.

Figure 3: Clockwise from top: (a) quantum annealing based selection, (b)
mutual information based selection, (c) Pearson correlation based feature
selection, and (d) p-value based feature selection.

###  IV-B Qualitative Evaluation

In this section, we will perform a qualitative evaluation of the features
selected using four techniques namely quantum annealing, mutual information,
p-value, and Pearson correlation feature selection technique. These four
techniques were used to extract features using 100%, 30%, 20%, and 10% of the
training data. For each of the techniques, the feature selection procedure was
repeated n-times (n=10 in our case) to provide less importance to features
that got selected just by random chance. The selected features were
categorized according to their sources such as ECG-based features, H-EDA-based
features, F-EDA-based features, and RESP-based features. Figure 3 shows the
contribution of specific signal sources in terms of the percentage of total
features selected.

From Figure 3, we can visualize that quantum annealing based feature selection
returned a more stable set of features from mainly two signal sources (ECG and
RESP) for 100% training data and 30% training data. Even with 20% and 10% of
the training data, ECG and respiration-based features contributed to more than
95% and 88% of the total feature count. This shows that QA-based feature
selection consistently found EDA-based features less important than ECG and
RESP-based features. This consistency is not affected when only 30% of the
training data is available for feature selection. This consistency
deteriorates only slightly even when 10% and 20% of the training data are
available.

###  IV-C Quantitative Evaluation

The quantitative evaluation will be based on the average F1-score computed
under all training data scenarios. The training data scenarios are 100%
training data, 30% training data, 20% training data, and 10% training data.
The effectiveness of a particular feature selection algorithm will be
estimated by the ability of the selected features to classify a feature sample
in low, medium, and high stress classes using classical classification. The
metric used to quantify the classification performance is the F1-score. Figure
4 shows the average F1-score achieved when features were selected using the
different training data sizes for QA-based feature selection technique,
mutual-information-based feature selection, Pearson-correlation-based feature
selection, and p-value-based feature selection.

Figure 4: Clockwise from top: (a) quantum annealing based selection, (b)
mutual information based selection, (c) p-value based feature selection, and
(d) pearson correlation based feature selection . Trend line is shown in black
and is obtained by connecting the F1-scores obtained under different training
sizes for high, medium, and low stress.

From Figure 4, it can be visualized that the F1-score for quantum-annealing-
based feature selection technique is more or less constant when features are
selected using different training sizes for high, medium, and low-stress
classes. The trend line of the F1-score obtained using different training
sizes does not follow a clear increasing or decreasing trend. This implies
that the average F1-score did not drop significantly as training samples were
reduced. Moreover, no significant statistical difference (p-value$>$0.05) was
observed between the F1-scores obtained under 30%, 20%, and 10% training data
and the F1-score obtained when 100% of the training data was used for feature
selection. This implies that the performance of QA-based feature selection was
not affected to a significant extent under the presence of limited training
data when the quantum-annealing-based feature selection technique was used.

In the case of the mutual-information-based feature selection technique, the
trend line follows a decreasing trend as training sizes are reduced. Moreover,
except for low stress, a significant statistical difference (p-value$<$0.05)
is observed between the F1-scores obtained under 30%, 20%, and 10% training
data and the F1-score obtained when 100% of the training data was used.
Similarly, for the p-value-based feature selection technique, a clear
decreasing trend is observed with the average F1-score as the size of training
data is reduced. An exception to this observation is the situation where
p-value-based features were used to detect low stress. For the p-value-based
feature selection technique, no significant statistical difference was
observed between the F1-scores obtained under 30%, 20%, and 10% training data
and the F1-score obtained when 100% of the training data. However, the average
F1-score obtained using the p-value-based feature selection technique is
significantly lower than that obtained using quantum annealing and mutual-
information-based feature selection technique. Pearson-correlation-based
feature selection technique did not perform as well as compared to other
feature selection techniques which are evident from the overall low average
F1-score across all groups and training data size.

##  V Conclusion and Future Work

In this paper, a novel method for automated feature selection using quantum
annealing is explored. We have proposed a hybrid classical-quantum machine
learning pipeline that integrates D-Wave’s QPU through a software interface
that allows interaction with the physical QPU. The problem of selecting
optimal features is formulated as selecting a clique with the lowest energy
from a binary quadratic model. The nodes forming the lowest energy clique are
returned as the set of optimal feature space. As a case study, QA-based
feature selection was used to select the optimum feature subset for detecting
stress in a driving scenario and compared with mutual information, Pearson
coefficient, and p-value based feature selection techniques. Results show that
QA based feature selection technique performed equally well as the classical
techniques. In conditions where training data was limited, a slight advantage
is observed when QA based feature selection algorithm was used. However,
future investigation on large-scale datasets and/Or on different application
domain will help us understand how quantum-annealing-based optimization
techniques generally performs better than the classical techniques.

Preliminary results from this study shows the promise of quantum annealing as
an efficient alternative to classical feature selection techniques. QA-based
feature optimization technique was found to return consistent results both in
terms of performance and the consistency of features selected even when
training sizes were reduced in size. In the future, we plan to extend our
analysis of quantum-annealing based feature selection techniques in solving
diverse problems where feature selection is an important step in the machine
learning pipeline.

## References

  * [1] B. S. McEwen, “Stress, adaptation, and disease: Allostasis and allostatic load,” _Annals of the New York academy of sciences_ , vol. 840, no. 1, pp. 33–44, 1998.
  * [2] S. M. Rothman and M. P. Mattson, “Adverse stress, hippocampal networks, and alzheimer’s disease,” _Neuromolecular medicine_ , vol. 12, no. 1, pp. 56–70, 2010.
  * [3] J. Aigrain, M. Spodenkiewicz, S. Dubuisson, M. Detyniecki, D. Cohen, and M. Chetouani, “Multimodal stress detection from multiple assessments,” _IEEE Transactions on Affective Computing_ , vol. 9, no. 4, pp. 491–506, 2016\.
  * [4] D. S. Lee, T. W. Chong, and B. G. Lee, “Stress events detection of driver by wearable glove system,” _IEEE Sensors Journal_ , vol. 17, no. 1, pp. 194–204, 2016.
  * [5] G. Giannakakis, D. Grigoriadis, K. Giannakaki, O. Simantiraki, A. Roniotis, and M. Tsiknakis, “Review on psychological stress detection using biosignals,” _IEEE Transactions on Affective Computing_ , 2019.
  * [6] E. Smets, W. De Raedt, and C. Van Hoof, “Into the wild: the challenges of physiological stress detection in laboratory and ambulatory settings,” _IEEE journal of biomedical and health informatics_ , vol. 23, no. 2, pp. 463–473, 2018.
  * [7] M. van Dooren, J. H. Janssen _et al._ , “Emotional sweating across the body: Comparing 16 different skin conductance measurement locations,” _Physiology & behavior_, vol. 106, no. 2, pp. 298–304, 2012.
  * [8] A. O. Akmandor and N. K. Jha, “Keep the stress away with soda: Stress detection and alleviation system,” _IEEE Transactions on Multi-Scale Computing Systems_ , vol. 3, no. 4, pp. 269–282, 2017.
  * [9] J. A. Healey and R. W. Picard, “Detecting stress during real-world driving tasks using physiological sensors,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 6, no. 2, pp. 156–166, 2005.
  * [10] “The D-wave 2000q™ quantum computer technology overview,” 2019. [Online]. Available: https://www.dwavesys.com/sites/default/files/D-Wave%202000Q%20Tech%20Collateral0117F.pdf
  * [11] S. Morita and H. Nishimori, “Mathematical foundation of quantum annealing,” _Journal of Mathematical Physics_ , vol. 49, no. 12, p. 125210, 2008.