Re-ranking for image retrieval and transductive few-shot classification
Authors: Xi SHEN
Yang Xiao
Shell Xu Hu
Othman Sbai
Mathieu Aubry
Venue: NeurIPS 2021 Poster (2021)
Keywords: meta-learning
few-shot classification
synthetic gradient
image retrieval

Abstract: In the problems of image retrieval and few-shot classification, the mainstream approaches focus on learning a better feature representation. However, directly tackling the distance or similarity measure between images could also be efficient. To this end, we revisit the idea of re-ranking the top-k retrieved images in the context of image retrieval (e.g., the k-reciprocal nearest neighbors) and generalize this idea to transductive few-shot learning. 

We propose to meta-learn the re-ranking updates such that the similarity graph converges towards the target similarity graph induced by the image labels. Specifically, the re-ranking module takes as input an initial similarity graph between the query image and the contextual images using a pre-trained feature extractor, and predicts an improved similarity graph by leveraging the structure among the involved images. We show that our re-ranking approach can be applied to unseen images and can further boost existing approaches for both image retrieval and few-shot learning problems. Our approach operates either independently or in conjunction with classical re-ranking approaches, yielding clear and consistent improvements on image retrieval (CUB, Cars, SOP, rOxford5K and rParis6K) and transductive few-shot classification (Mini-ImageNet, tiered-ImageNet and CIFAR-FS) benchmarks. Our code is available at https://imagine.enpc.fr/~shenx/SSR/.

Re-ranking for image retrieval and transductive few-shot classification
Xi Shen', Yang Xiao?, Shell Xu Hu Othman Sbai*. and Mathieu Aubry²
1.2.4.5 (UMR 8049), École des Ponts ParisTech Saasunng AI Center, Cambridge
Abstract
In the problems of image retrieval and few-shot classification, the mainstream approaches focus on learning better feature representation. However, directly tackling the distance or similarity measure between images could also be efficient. To this end, we revisit the idea of re-ranking the top-k retrieved images in the context of image retrieval (e.g.. the k-reciprocal nearest neighbors [48, 75]) and generalize this idea to transductive few-shot learning.
We propose to meta-learn the re-ranking updates such that the similarity graph con- verges towards the target similairty graph induced by the image labels. Specifically, the re-ranking module takes as input an initial similarity graph between the query image and the contextual images using a pre- pre-trained feature extractor, and predicts an improved similarity graph by leveraging the structure among the involved im- ages. We show that our re- re-ranking approach can be applied to unseen images and can further boost existing approaches for both image retrieval and few-shot learn- ing problems. Our approach operates either independently or in conjunction with classical re-ranking approaches. yielding clear and consistent improvements on image retrieval (CUB, Cars, SOP, rOxford5K, rParis6K) and transductive few-shot classification (Mini- Imai-e,ma,,Ne, ticred- Imaee-ee and CIFAR-FS) benchmarks. Our code is available at https: immaiiinnn... enpc. fr fr/-shenx/ SSR/.
1 Introduction
Learning deep image features that generalize beyond the training classes they have been trained on has been a clear success [63]. Using these strong features, recent works have shown that high performances can be obtained simply by computing nearest neighbors, in particular for image retrieval [1, 16, 50, 11, 30, 63] and few-shot image classification [71, 6]. this paper we highlight that, even with these strong features, results can be further improved by large margin through re-ranking images based on the similarity graph between neighbors. To this end, we present graph based deep architecture for re-ranking neighborhood images via a learning approach.
Our method can be seen revisiting and complementing classical approaches to re-ranking with deep learning techniques. These approaches can be broadly classified into query expansion that compute a new query feature based on the top retrieved neighbors [9, 8, 2, 16, 50], and k-reciprocal re-ranking that compute new distance between images based on the Jaccard distance between confident neighbors [48, 75]. The approach we propose is related to both approaches. Since on one side, we focus successively on the neighbors of each sample, and on the other side, we update features to compute new similarities. This achieved by designing neural network architecture that can update the similarity graph by successively focusing different subgraphs (as visualized in Figure 1) and updating features based on synthetic gradients [24, 21J. Our architecture for updating the similarity graph, referred to as Subgraph Similarity Refiner (SSR), operates the adjacency matrices
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

SSR
Figure Idea of our approach for image retrieval. Given an initial similarity graph between query and its top candidates in image retrieval (left), we propose module dubbed Subgraph Similarity Refiner (SSR) to improve the similarity graph (right). For each sample in the dataset we build subgraph by considering only edges with either the sample or the query (middle), order the nodes according to their similarity to the sample and predict an update for the edges of the subgraph. This idea can be applied with minor changes to transductive few-shot classification.
of the subgraphs. We focus successively on each image (as a query image), extract a subgraph, where our key technical insight is to sort all other images according to the similarity to the query image.
We show that approach transductive few-shot classification. We relate both tasks by casting them as a similarity graph refinement problem, where the refined similarity graph is used for task-specific predictions. In image retrieval, based on classical re-ranking techniques query expansion [9, 8, 16, 50) and k-reciprocal [75], method consistently improves the image retrieval performance (mean average precision, mAP) achieved by recent statc-of-the-art features [11, 30, 63]. For example, applying our method with the recent ProxyNCA++ [63] features improves the mAP@1 R from 55.4% 60.6% on Stanford Online Product dataset [62] and combining our approach with k-reciprocal [75] re-ranking further boost them 62.3%. transductive few-shot classification, we show that k-reciprocal [75] based re-ranking yields simple but surprisingly good baseline, while by learning to re-rank our method consistently improves over several competitive transductive approaches, e.g., the synthetic information bottleneck (SIB) [21].
improve different image features for both image retrieval and
2 Approach
Consider the similarity graph among N images, each node of the graph corresponds to one image and each weighted edge represents the similarity between two images. The similarity graph plays important role in computer vision. As example, the k-nearest-neighhor classifier remains a competitive method in image classification if the similarity graph is sufficiently informative. Note that, during training, do have access the target similarity graph, which has similarity 1 if two images belong to the same class and O otherwise, can we learn to improve an initial similarity graph of images given that we have seen the largel similarity matrix for training images?
Motivation
Indeed, in the context of image retrievel, this idea of exploring and improving the similarity graph is called re-ranking, which refers to the case where initial set of images have been retrieved, we then re-rank their relevance to the query image by examining again their similarities. Certainly, this idea can be hardly scaled large set of images as the complexity is quadratic, but it is quite interesting in the case of few-shot learning for unseen categories domains.
In this section, we first present overview of our approach as generalization to re-ranking (Section 2.1); we then introduce our model architecture, called Subgraph Similarity Refiner (SSR) (Section 2.2) and how to combine our approach with the classical k-reciprocal [75] re-ranking approach (Section 2.3); finally, in Section 2.4 we explain how we train our approach and give implementation details.
2.1 Learning improve similarity graph
We assume that we are given set of N images and for each image initial feature. During training, we also assume that we are given label for each image. Our goal is to predict an improved similarity, where images with the same label have higher similarity than images with different labels. We will

---

Similarity
Subgraph Smilarity (SSR)
Refined Similaiity
Terget Similarity
(a) Overview of our update prediction approach
Neighbors
Nearest Neighbors
Sample
Sample
(b) SSR for image retrieval
(c) SSR for transductive few-shot classification
Figure 2: Subgraph Similarity Refiner (SSR) Iearns updates for a similarity graph. It decomposes the similarity graph, that can be represented by its similarity matrix, into N subgraphs where rows and columns the matrix are ordered depending on similarities to the subgraph reference image. The output of SSR is an improved similarity matrix. The final loss is between the predicted similarity matrix and target similarity matrix. The details of subgraphs are shown in (b) for image retrieval:
the rows correspond to the subgraph reference image and the query image and the columns the
test images; and (c) for transductive few-shot classification: the rows correspond to the subgraph reference image and the support set S while the columns the support set S and the query set Q.
represent the similarity graph by its adjacency matrix, which we will refer to as similarity matrix. Note that the similarity matrix allows to explore neighbors of the nearest neighbors (high order nearest neighbors), which is classical and effective way to tackle the re-ranking problem [48, 75].
More formally, for E {L...., N we denote by ff the initial feature of 2 image and yt its label. The initial similarity matrix is given by:
(f 1
S = ( with
(1)
Our goal to predict the target similarity matrix $ = [1 y= J.jje where 1 1 is the indicator function of y, = M/y. We refine the similarity matrix iteratively. First, consider the following update given similarity matrix St-1;
S = 1 bJ. S G(S
where G is the Subgraph Similarity Refiner (SSR) that we will describe in the next section. The issue with such an update is the flexibility. We therefore would like to constraint the updated similarity matrix to have the form
St = ( LJELL... with
(3)
This amounts to construct the update in features rather than in the similarity matrix directly. As such, S always remain positive semidefinite. Now, the question is how we make use of S' to obtain ft. Given ft in fact, we only need move a single gradient step along the projection direction
(f.fz) )². Specifically, we obtain f according to the Euclidean distance (f) ;= 1/4 Ei ( T
by considering St as an intermediate result:
Vi: = ff
OL
(5-)) with Of:
aL aLs ōf.
( -OS +
3st (f--)
(4)
as!
where À is the step size. Indeed, this update can be [21, 24] on the features. Here, we motivate from a different perspective.
applying the synthetic gradient descent
Note that the network G defines meta-model, as the update is supposed to generalize to unseen image categories. We leam G by minimizing spec-f loss between the target similarity matrix and the updated similarity matrix ST. The key for this approach to work the architecture design of the network G. which we detail in the next section.

---

2.2 Subgraph Similarity Refiner (SSR)
The adjacency matrix a natural way to encode a similarity graph. However, is defined up to the order of the nodes, i.c. permutations of its column and rows. For this reason, learning directly to make a prediction from the similarity matrix is challenging. One can simply order the nodes with respect to their distance to a specific sample, such as the query in the case of image retrieval, but this gives one of the nodes specific role and it might be hard for the network to use the similarity structure among the other nodes, especially since S is very high dimensional and overfitting might be an issue. Thus, we propose a permutation-inyee invaariia architecture illustrated in Figure 2a.
Our key idea is to make N update predictions by considering only subgraphs centered on each node i and then to aggregate them obtain an update prediction on the full graph. We can associate similarity matrix M; to the 1t subgraph, where we order nodes according to their similarity to the node i. Note that the order will be different for each subgraph. We then predict updates g(,) for each of the subgraphs using a simple network Finally, we aggregate the predictions on all the subgraphs by summing the updates predicted for each subgraph at the relevant position S:
(5) where g is multi-layer perceptron (MLP) and GraphSum is aggregation operator to account for the summation with respect to graph structure since each node is contained in multiple subgraphs.
G(S) GraphSum (lg())))
We now discuss the exact structure of the subgraph and associated similarity matrix M; that we use in the case of image retrieval or transductive few-shot classification. The choice of structures in both cases are validated by the ablation studies presented in Section 3.3.
Image Retrieval. In image retrieval, we search for images similar to a query image in a pool of test images. We assume that a first algorithm already selected the N - test images most similar to the query and we focus on improving the similarities between the resulting set of N images (the query and its N - nearest neighbors). By increasing the similarities between the query and the positive images against those of the negatives, we aim to obtain a better retrieval result where positives should be ranked before negatives for the N - 1 test images selected for the query. During training, we optimize the InfoNCE loss [44] with a learnable temperature parameter T:
exp(Ts?))
Σ
- -log
(6)
(exp(Ts?)) + Enener exp(Ts
1.j:9 By Berw
where siij signifies the similarity between the ith sample and jth sample after T similarity updates.
As visualized in Figure 2b, we build the 7th subgraph by considering only edges that connect nodes to either the jth sample or the query. Rather than considering M, as the adjacency matrix of this graph, define it as 2 N matrix defined follows. Each column corresponds to different sample and the samples are ordered with respect to their similarity of the jth sample. The values in the first row are the similarities between the ith sample and the samples associated to each column, is thus decreasing. The values in the second row are the similarity between the query and the samples associated with each column. Note that for the subgraph corresponding to the query, the two lines of the matrix are the same and actually correspond to the same edges in the graph.
Transductive few-shot classification. In few-shot classification, the set of N images consider can be divided in two: a support set S with known labels and an unlabelled query set Q for which we want predict labels. Our approach assumes that Q is accessible during the inference. This setting is known as transductive few-shot classification. For each sample in the query set, we aim to increase the similarities between itself and the support images from the same class comparing those from different classes. To this end, we minimize the Cross Entropy loss:
exp(Ts]T)
Σ
- log
exp((T(]) + Ekes. exp(Ts
:EQ.jESy/ "/
where 7 is a learnable temperature parameter, y and y. are labels of query and support samples.
As visualized in Figure 2c, we build the 7th subgraph by considering only the edges that connect nodes either to the 4h sample or to the support set. Similar to the case of retrieval, represent this

---

graph using structured matrix, but we keep the nodes corresponding to the support and query set separated. We define M, as ([S] + 1) ([S) 12] matrix with the number of elements in set. Its first [S] columns and last [2] columns correspond to the samples in support set and query set, respectively. They are both sorted by decreasing similarity with respect to the 7th sample. While the values in the first row of M, represent the similarities between the jth sample and the samples in different columns, the last |S] rows represent similarities between support samples and different columns. Note that if the hd sample comes from the support set, one row will be repeated in M,.
2.3 Combination with k-reciprocal distance [75]
Instead of taking CNN feature similarities as input of G, our approach can be augmented with other distances. In particular, we show that it leads to stronger results when using the k-reciprocal feature distance [75]. We summarize in this section how the k-reciprocal feature distance is obtained and how we update it with our approach.
The k-reciprocal feature is computed from k-reciprocal neighbors [19]. Writing top a, k) the k nearest neighbors of the feature a. the set of k-reciprocal neighbors R(a, k) of a is defined as
R[a, k) (b|b top(a, k) na E top(b, k)).
The backward verification aims at reducing the number of false matches in the k-reciprocal neighbors. To consider potential positive matches excluded from the k nearest neighbors, [75] proposed add the ý-reciprocal neighbors of b R[a, k) into expanded set R* (a if R(b, 5) shares enough neighbors with R(a, k).
The final proposed distance d in k-reciprocal [75] is combination of the euclidean distance between normalized features and the Jaccard distance dy computed with the expanded sets:
b 2 + -11--)0 (a) R²,
d(a, b)
|al
where a is syper-parameter representing the contribution of the feature similarity. For more details about the Jaccard distance, we refer to [75].
Now, we compute the distance matrix J corresponding to the Jaccard distance obtained from the initial features and consider as fixed. We then consider the distance defined by Equation 9 to build our graphs updating only the feature similarity in the first part of the equation. More precisely, at each iteration I, we use D' = 2ax11 - SS) + (1-cx) J as input of the SSR, and consider its output an update to St only and the final objective function remains on S We also tried to use the final objective on D but observed severe overfitting on the training set and worse results.
2.4 Network architecture and implementation details
Architecture. Each subgraph update in our SSR module is performed by a three-layer perceptron with constant hidden-layer size 1,024 for image retrieval and 4,096 for few-shot classification. Further increasing the model size leads to similar performances. All the layers except the last one are followed by ReLU activations and Instance Normalization [64], which we also apply to the input matrix.
Optimization. We optimize our networks using SGD with momentum 0.9. The batch size is set to 1 since there are numerous images to consider in single similarity graph and increasing the batch size does not improve the performance. For image retrieval, we use single update of the model (T' = 1) and training converges in 10K iterations with a fixed learning rate of lc-5. Larger T' leads to similar performance. The analysis of T and À on rOxford5 [49] and rParisóK [49] are available in the supplimentary material. The entire training on CUB [67] takes hours on single GeForce 1080 Ti GPU. For few-shot classification, we first train for 30K iterations with T = 1: the learning rate is set to 0.1 for 5K iterations then to 0.01 for another 25K iterations. Then, keeping a learning rate of 0.01, we train for 10K iterations with T= 2 and 10K more with T = 3. We find that T = 3 leads to the most stable improvement and include this analysis the supplementary material. The whole training process mini- ImageNet [66] takes 20 hours single GeForce 1080 Ti GPU.
5

---

Methed
[11
(67)
PNCAA
PA
PNCAA
GLIDI
PNCA-
Medium
Hard
Medium
Hant
LAnQE (17]
73.4
49.6
56.3
70,6
Regieo Dimusioa (25, 40p"
69.0
44.7
19.5
90.0
Feat. only
24.5
27.0
20.6
27.3
28.3
33.2
46.9
51.0
55.4
67.3
44.3
90.6
61.3
Foor
34.0
19.5
16.1
16.7
45.8
90.9
50.8
08.6
75/6
16.3
66.4
07.5
AQQE
40.0
40.3
53.8
74.
AQFie (15)
26.4
11.4
14.2
$4.
16.1
40.9
-6.3
56.0
56.6
20.3
48.0
64.1
IAQEED v SSR
34.0
35.9
41.2
59.2
39.7
48.4
49.9
562
60.5
74.1
56.1
83.9
07.9
ICE [:]
26.4
30.6
35.0
31.8
36.5
37.0
48.7
55.0
58.3
0935
46.1
84.0
070
IDOE SSR
11:1
19.9
99-4
46.2
.9.8
59.8
716
<QB
SSR
k-noipeceaal [?5]
Eerecppccaal [?5] 55R
40.8
Table 1: Image retrieval. For [67], CARS [3]] and SOP [62], use three features: GL [11]
PA [30] and PNCA++ [63], and report mAP@R, R, which follows [40]. For rOxford5K [49] and
rParis6K [49], we use the feature provided in [17] and report mAP, which follows [17].. The best and the 2nd best results are in red and blue respectively.
3 Experiments
In this section, we cover our experimental setups and results for image retrieval and few-shot image classification. Since these two problems are different in data processing and performance evaluation, we separate the discussions into two sub-sections followed by a joint ablation study.
3.1 Image retrieval
Datasets, We consider five image retrieval datasets, namely, CUB [67], CARS [31], SOP [62]. rOxford5K [49] and rParis6K [49]. For CUB, CARS, SOP, we follow the standard split [11]: for CUB, the first 100 species (5,864 images) are used for training and the remaining 100 species (5,924 images) used for testing, for CARS, the first 98 classes (8,054 images) are used for training and the other 98 classes (8,131 images) are kept for testing; for SOP, the dataset is separated into 11,318 training classes (59,551 images) and 1 1,316 testing classes (60 502 images). For rOxford5K [49] and rParis6K [49], we follow [17] and use the dataset SFM1 20k [50]. which is built with structure-from: motion pipeline, and clusters for the same 3D scene are cast as categories. We take features in [17), which already leads to good performance on the training set. For most training samples, the mAPs on the training set are already quite high and training SSR using the raw nearest neighbors makes perform well only for high mAP queries. To address this problem, we sample only difficult examples. To combine other re-ranking methods and SSR, we directly apply the trained SSR to the top retrieved samples given by other re-ranking methods. More details can be found in the supplementary material.
Evaluation metric. For CUB, CARS, SOP, following [40]. we choose the Mean Average Precision R. (MAP@ R) our main evaluation metrie: MAP@@ R R E P(i) with R the total number of true positive samples and P(t) is the precision at if the jth retrieval correct and otherwise. For rOxford5K and rParis6K, we follow [17] and report stand Mean Average Precision (mAP) on medium and hard queries.
Baselines. We conduct exhaustive experiments with three recent feature representations: a) features trained with group loss [11] (GL), b) features trained with proxy anchor loss [30] (PA) and c) features trained with proxy neighborhood component analysis method [63] (PNCA++). For each feature, we report the baseline results obtained from the k-reciprocal method [75] and four standard query expansion methods [17]: Average Query Expansion (AQE, [9, 16, 50]), Average Query Expansion with Decay (AQEwD, [50], Alpha Query Expansion (aQE [50]) and Discriminative Query Expansion (DQE [2]). The baselines and details are provided in the supplementary material.
Results. Our results are shown in Table 1. Applying our SSR on original features ("Feat. + SSR") largely improves the retrieval performance of using original features ("Feat.") on different datasets for different metric. In almost all cases our method alone outperforms all the query expansion baselines and results can be further improved by applying it to the query-exxandddd results. The performance improvement brought by k-reciprocal [75] should be attributed to the statisties of neighbors of neighbors, while our method can further boost upon that. These results suggest that our method can be combined with many feature extractors for image retrieval to attain better performance. Note that the choices of N are available in the supplementary material.

---

mini-ImageNet [66]
tiered-ImageNet [S]]
CIFAR-FS [45]
Methods
Trans.
Backbone
1-shot
5-shot
1-shot
5-shot
1-shot
5-shot
MatchNet [66]
Conv-4-64
57.0
ProtoNet [60]
Conv-4-64
49.4:10.8
68.2:40.7
53.340.9
72.74:0.7
55.5:00.7
02.0::.6
GNN [13]
Conv-4-64
50.3
66.4
61.9
75.3
Gidaris et al. [14]
Conv-4-64
54.8.40.4
71.9:1.3
63.5+:03
79.8::0.2
MAML [12]
Conv-4-64
48.7:+1.88
63.140.9
51.7.1188
70.3::1.8
TPN [35]
Conv-4-64
55.5::0,9
69.9=1.7
59,9:0099
73.3:10.8
SIB [21]
Conv-4664
58.0=
70.7+0.4
68.7:10.6
77.1
HPNet [53]
Conv-4664
59.3++0.9
73.0++.66
60.0++1.0
73.94-0.8
Baseline
Conv-4-64
52.4200.
69.640.4
55.24:0.5
72.3+004
57,8+0.55
05.3+0.4
k-reciprocal [75]
Conv-4-64
58.6+0.7
72.240.5
63.1++0.8
75.0++0.6
66.6+-0.8
78.1+0066
Ours
Conv-464
62.1=0.6
73.2:104
65.1:10.6
74.1::0.5
72.0:10.6
0..5::0.4
TADAM [45]
ResNet-12
58.520.3
76,720.3
MetaOptNet-RR [33]
ResNet-12
61.4+0.6
77.9+0.5
65.440.77
81,3++0,5
72.6++0.7
84.3-00.
ProoNeetMABAS (28)
ResNet-12
65.1
82.7:0.55
73.5::0.9
8..5
EGNN [29]
ResNet-12
64.0
77.2
66.5
82.5
CAN [20]
ResNet-12
67.2.40.6
80.6:0.4
73.2:40.6
84.9:10.4
EPNet
ResNet-12
66.510.9
81.1:10.6
76.540999
87.311.66
Baseline
ResNet-12
57.6+-0.5
73.5++0.4
68.840055
83,5+004
66.4+-15
00.4
k-reciprocal [75]
/
ResNet-12
6.73:10.7
78.0 78.0 1:055
77.3:10.88
85.7:10.5
73.6:0.88
82.1+0.55
Ours
ResNet-12
68.1+-0.6
76,9+0.4
81,2++0.6
85.7+-0.4
76.8+-0.6
K3.7+0.4
[50
WRN-28-10
61.80011
77.6=00.1
66,345011
81,410.1
Gidaris et al. [14]
WRN 28 10
62.9+0.5
79.9+
70.5++0.5
85.0++0.4
76.1++0.3
87.8+0.2
SIB# [21]
WRN-28-11
70.0+0.6
78,940.4
72.9*
82.8*
80,0-0.66
85.3+0.4
SIB+E*BM [36]
WRN-28-10
71.4
81.2
75.6
84.3
EPNet [S3]
WRN-28-10 10
70.7+0..9
84.3:1.55
78.5:10.9
88.4110.6
Baseline
WRN-28-10
61.950.5
77.840.3
69,440.5
83,4100.4
69.5+00.5
03.5
--rreciprical [75]
WRN-28 28- 10
68.1
79.4+00.5
76.4+00.7
84,8++0.5
76.7+-0.8
84.9
Ours
WRN-28-100 10
72.4110.6
80,240.4
79.5:10.6
84.8:10.4
81.610.6
86.0=0.4
RResults from [33]. Results from [35].
*Results from [36].
we use the same pre-trained features of WRN and Conv-4-64 as [21] mini- ImageNet.
Table 2: Transductive few-shot classification. 5-way few-shot classification accuracies (% ) on mini- ImageNet [66]. fiered-ImageNet [5]], and CIFAR-FS [4]. We report average classification accuracy (with 95% confidence intervals) over 2000 episodes on the test set. We highlight in grey the results of our baseline features with nearest neighbor classifier (entry "Baseline") with k-reciprocal [75] re-ranking (entry "+ k-reciprocal") and with our approach (entry "+ Ours"). The best and the 2nd best results are red and blue respectively.
3.2 Transductive few-shot classification
Dataset. We evaluate our approach on three standard few-shot classification datasets: mini- ImageNet [66], tiered- ImageNe [51], and CIFAR-FS [4]. mini-ImageNer and fiered-Imageny contain a subset of ImageNet images resized 84x84. mini-ImageNNe contains 100 classes and 600 images per class. It is split into 64 classes for training. 16 for validation and 10 for testing. Sered-ImageNee contains a larger subset of ImageNet with 608 classes and 300 images per class. is split into 351 classes for training. 97 for validation and 160 for testing. CIFAR-FS was created by dividing the original CIFAR- [32] into 64 training classes, 16 validation classes and 20 testing classes. Each class has 600 images. The image resolution is 32x32.
Architectures and baseline features. We experimented with three architectures: WRN-28-10 [74, 15, 14, 21], ResNet-12 [38, 45, 33] and Conv-4-64 [15, 14, 21J. WRN-28-10 is commonly evaluated in few-shot classification [74, 15, 14, 21]. ResNet-12 is the architecture used by [38, 45, 33). Conv-4-64 is widely used in few-shot learning [15, 14, 21] and has 4 convolutional modules, with Max
3 convolutions, followed by Batch Normalization [22]. ReLU non-linearity and Pooling. For all architectures and datasets, use a baseline feature obtained by pre-training cosine classifier [15] to initialize our approach. Note that this pre-training is carried out on the train-set with hyper-parameter selection on the validation set. The cosine classifier is trained following a standard training strategy: we use the SGD optimizer with momentum 0.9 and batch size 64 for 120 epochs. The first 50 epochs are with learning rate 0.1. the next 50 with learning rate 0.01, and the last 20 with learning rate 0.001. We adopt standard data augmentation: resizing, cropping and horizontal flipping.
We compare our approach to state-of-the-an methods in Table 2. For all the datasets and backbones, we report the performance of the baseline features ('Baseline " k-reciprocal [75] with the baseline feature ('+ k-reciprocal") and our approach with the bascline features (' ('+ Ours').
Results.
7

---

Interestingly, simple baseline by combining the baseline feature and k-reciprocal, without any learning procedure, achieves comparable performance with recent methods [21, 36, 53] on all three datasets. Moreover, our method achieves the best performance on 1-shot classification and obtains competitive performance on 5-shot classification. In particular, compared to SIB [21], which is also an approach using synthetic gradient and similar baseline features, our approach yields clear and consistent improvement. Note that combining k-reciprocal and our method did not bring any improvement over our method alone for few-shot classification (see results in supplementary material).
3.3 Ablation study
Image retrieval. We provide analysis CARS [31] with using Group Loss features [11] and N = 100 to analyze our approach for image retrieval. The results are presented in Ta- ble 3. This ablation provides several insights. First, using subgraphs is essential: perfor- mance simply using as input and predicting the full similarity matrix (w.o subgraph) leads to performances close to the baseline. Second, sorting the columns in each subgraph is impor- tant, because it makes the information about each sample easier for the network to extract,
be seen in the 1.8% performance loss when the columns are sorted according to their similarity with the query (w:o local sort). Third, the feature update (w.o feat. update), which allows to leverage the input features, also im- portant, removing it degrades the performance by 3.8%. Finally, adding or removing rows in M, shows that using the subgraphs we define is good trade-off: removing connections to the 7th sample (w.o sample) or the query (w.o query) degrades performance, and so does considering the full graph (w.o other). Note that independently of the graph they represent, the matrices M, are still focused on sample which used to sort their rows and columns.
Method
mAP@R
Baseline (Teatures)
27.8
Ours (sample and query)
34,0
Sarpple
w.o sample
32.9
w.o query
28.2
w. other
33.0
Other
w.o local sort
32.2
w.o subgraph
27.9
w.o feat. updato
30.2
Query
(a) mAP@R R on CARS [31]
(b) Variants of M,
Table 3: Image retrieval: Ablation study on
CARS [31].
Transductive few-shot classification. We now present a similar analysis on transductive few- shot classification. The results are in Table 4. We identify variants of the subgraph similarity matrices M; by writing the samples we use in rows and columns. First, note that the optimal choice is the one presented in Sec- tion 2.2, using matrices M, with
Acc
Baseline (Fcatures)
61.9
rows corresponding the 5th sample and the support set and columns cor- responding the support set S and the query set Q. Second, the local sorting is more important for few-shot classification than for image retrieval, removing it (w.o local sort) degrades the performance by 9%. The reason is that in image retrieval we could order images with respect to their similar- ities to the query, while in few-shot classification there is no natural order. Third, similar to image retrieval. the decomposition into subgraphs (w.o subgraph) crucial to obtain improved performance. Finally, updating features (wo feat. update) is also important in this task and brings an extra 1.4% improvement.
Rows
M, Col.
sample, $
S.
72.4
sample
sample, S. Q
S. Q
72.2
Ours
S.
72.0
S
sample sample, S
8,
70.8
71.7
sample, & sample,
S
66.3
local w.o subgruph w.o feat. update
sample, S
S.
63.2
sample, S S. Q
71.0
(b) Variants of M,
(a) 1-shot accuracy
Table 4: Transductive few-shot classification: Ablation study on mini-ImageNet [66] with WRN [74].
4 Related Work
Image Retrieval. Given query image, image retrieval searches for similar images in set of test
images. Traditional approaches [59, 37, 42, 46, 25, 2] seek to match a bag-of ofrdo representation. Recent approaches rather focus on learning a good global representation of images [16, 50, 52] to map similar samples closer to each other against dissimilar ones, which is also addressed by deep metric learning. Pair based loss has a long story in metric learning. Contrastive loss [5, 7, 18, 50] pulls positive pairs together and pushes negatives far apart. Triplet loss [72, 68, 57, 16] enforces the
8

---

distance between of a positive pair to be smaller than negative pair. N-pair [61] and Lifted Structure loss [43] associate an anchor with a positive but multiple negatives. Both Ranked List [70] and Multi- Similarity loss [69] take into account all positive and negative pairs in batch and Multi-Similarity assigns a different weight to each pair. Instead of optimizing on pairs of samples, proxy based losses consider distances between samples and learnable proxies [39, 73, 47, 3, 63]. Proxy-NCA [39] allows to reduce computation by approximating NCA [54] loss with proxies. Proxy Anchor [30] improves Proxy-NCA [39] by assigning a proxy for each class and associating each proxy with the entire batch. ProxyNCA++ [63] further improves ProxyNCA and proposes several enhancements, such as low temperature scaling, Global Max Pooling, etc.
Few-shot classification. Few-shot learning [66, 60, 12] refers to learning from a few annotated examples. Recent works are more focused on meta-learning [56] which aims at learning the ability to solve new tasks from previous experiences. Our work focuses in particular on the transductive setting, which differs from the standard few-shot learning by assuming the unlabelled query set to be accessible during inference. By sharing information between test examples through Batch Normalization [22], MAML [12, 41] is the first method to apply transduction. The goal of MAML is learn parameter initialization that can be fine-tuned quickly on a new task. Reptile [41] approximates MAML with first-order derivatives rather than second-order derivatives. In the same spirit of MAMI., SIB [21] proposed to adapt to a new task by learning to predict synthetic gradient [24]. SIB can be further improved with the ensemble of epoch-wiss wise empirical Bayes models [36]. CAN [20] designs a cross attention module to adaptively extract support and query features. TPN [35] learns to propagate labels with neural network. EGNN [29] takes into account both node and edge feature update the graph. EPNet [53] proposed to use embedding propagation as an unsupervised regularizer for manifold smoothing. While being related to graph based approaches. our method is different to the previous works in the sense that the graph update is done in an implicit way learned automatically by the network, rather than an explicitly designed scheme.
Re-ranking for image retrieval. Image retrieval results are usually improved by re- re-ranking the nearest neighbors [9, 16, 50, 75]. Query expansion is a classic re-ranking approach that constructs an expanded query from the top-k retrieved samples. The expanded query can be linear combination of the top-k retrievals (AQE, AQEwD, alphaQE) [9, 8, 16, 50), or as proposed in [2], linear SVM classifier for each query trained using top ranked features positives, and low ranking features as negatives. Recently, LAuQE [17] proposed to apply several successive explicit aggregators with self-attention [65] to obtain the updated features. Another line of research focuses on exploring higher- order neighbors [34]. The methods can either use explicitly label propagation on the nearest neighbor graph [77, 76, 10, 23]. or directly encode neighbor information into image descriptors [58, 34]. Shen et al. [58] proposed to encode images by their k nearest neighbors. The final rank of a database image is determined by its ranks in the retrieval results of the query and the query's ' k nearest neighbors. The k-reciprocal nearest neighbors is used in [26, 27] by taking into account the symmetry of k- update distances. The concept of k-reciprocal nearest neighbors is formally presented in [48] where two images are k-reciprocal nearest neighbors if both are nearest neighbors of each other. This idea is then further explored and demonstrated to be effective for person re-identification in [75].
neighborhood relationship
5 Conclusion
In this work, we presented deep approach for image re-ranking and an architecture specifically designed to update similarity graphs. We apply it to two problems that are usually tackled by different methods: image retrieval and transductive few-shot classification. Experimental results suggested that our approach can be applied alone or be complementary to classical re-ranking methods in image retrieval and both lead to significant improvements. transductive few-shot classification, we showed that applying a classical re-ranking method to pre-trained features leads to strong results and we can attain state of the art with our approach.
This work was supported in part by ANR project EnHerit ANR-17-CE23-0008 project Rapid Tabasco, and IDRIS under the allocation AD01 101 1160R1 made by GENCI.
Acknowledgment

---

References
[1] Relja Arandjelovic. Petr Gronat, Akihiko Torii, Tomas Pajdla, and Josef Sivie. Netvlad: Can architecture for weakly supervised place recognition. In CVPR, 2016. 1
[2] Relja Arandjelović and Andrew Zisserman. Three things everyone should know to improve object retrieval.
In CVPR, 2012. 1, 6, 8, 9
[3] Nicolas Aziere and Simisa Todorovic. Ensemble deep manifold similarity learning using hard proxies. In
CVPR, 2019. 9
[4] Luca Bertinetto,, Joao F Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-lcarning with differentiable
closed-form solvers. In ICLR, 2019. 7
[5] Jane Bromlcy, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using "siamese" time delay neural network. In Neur/PS, 1994, 8
[6] Yu Chen, Yen-Cheng Liu, Zsolt Kira, Yu-Chiang Frank Wang, and Jia-Bin Huang. A closer look
few-shot classification, In ICLR, 2019. 1
[7] Sumit Chopra, Raia Hadsell, and Yann LeCun. Learning similarity metric discriminatively, with application face verification. In CVPR, 2005. 8
Ondfej Chum, Andrej Mikulik, Michal Perdoch, and Jifí Matas. Total recall ii: Query expansion revisited.
In CVPR, 2011. 1, 9
[9] Ondrej Chum, James Philbin, Josef Sivic, Michael Isard, and Andrew Zisserman. Total recall: Automatic query expansion with a generative feature model for object retrieval. In ICCV, 2007. 1, 2, 6,
[10] Michael Donoser and Horst Bischof. Diffusion processes for retrieval revisited. In CVPR, 2013. 9
[11] Ismail Elezi, Sebastiano Vascon, Alessandro Torcinovich, M. Pelillo, and Leal-Taixé. The group loss
for deep metric learning. In ECCV, 2020. 1, 2, 6, 8
[12] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep
networks. In ICML, 2017. 7.9
[13] Victor Garcia and Joan Bruna. Few-shot learning with graph neural networks. ICIR, 2018.
[14] Spyros Gidaris, Andrei Bursuc, Nikos Komodakis. Patrick Pérez, and Matthieu Cord. Boosting few-shot
visual learning with sulf-super In ICCV, 2019. 7
[15] Spyros Gidaris and Nikos Komodakis. Dynamic few-shot visual learning without forgetting. In CVPR, 2018. 7
[16] Albert Gordo, Jon Almazan, Jerome Revaud, and Diane Larlus. End-to-end learning of deep visual representations for image retrieval. ICV, 2017. 1, 6. 8,
[17] Albert Gordo, Filip Radenovic, and Tamara Berg. Attention-based query expansion learning. In ECCV,
2020. 6.9 9
[18] Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning an invariant mapping. In CVPR, 2006. 8
[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition.
In CVPR, 2016. 5
[20] Ruibing Hou. Hong Chang, MA Bingpeng. Shiguang Shan, and Xilin Chen. Cross attention network for few-shot classification. In NewrlPS, 2019. 7, 9
[21] Shell Xu Hu, Pablo Moreno, Yang Xiao, Xi Shen, Guillaume Obazinski, Neil Lawrence, and Andreas
Damianou, Empirical bayes transductive meta-learning with synthetic gradients. In ICLR, 2019. 1, 2, 3, 7,
8, 9
[22] Sergey loffe and Christian Szegedy. Batch normalization: Accelcrating deep network training by reducing
internal covariate shift. In /CML, 2015. 7,9
[23] Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, Teddy Furon, and Ondrej Chum. Efficient diffusion on region manifolds: Recovering small objects with compact can representations. In CVPR, 2017. 6, 9
[24] Max Jaderberg, Wojeiech Marian Czarnecki, Simon Osindero. Oriol Vinyals, Alex Graves, David Silver, and Koray Kavukcuoglu, Decoupled neural interfaces using synthetic gradients. In ICMI., 2017. 1, 9
[25] Hervé Jégou, Matthijs Douze. Cordelia Schmid, and Patrick Pérez. Aggregating local descriptors into a compact image representation. In CVPR. 2010.
[26] Herve Jegou, Hedi Harzallah, and Cordelia Schmid. A contextual dissimilarity measure for accurate and efficient image search. In CVPR, pages 1-8, 2007. 9
[27] Herve Jegou, Cordelia Schmid, Hedi Harzallah, and Jakob Verbeek. Accurate image search using the contextual dissimilarity measure. TPAMI. 2008
[28] Jackycom Kim, Hyoungseok Kim, and Gunhee Kim. Model-agnostic boundary-adveessrral sampling for test-time generalization in shwtshot learning. In ECCV, 2020. 7
[29] Jongmin Kim, Taesup Kim, Sungwoong Kim, and Chang D Yoo. Edge-labeling graph neural network for few-shot learning. In CVPR, 2019. 7,9
[30] Sungyeon Kim, Dongwon Kim, Minsu Cho, and Suha Kwak. Froxy anchor loss for deep metric learning.
In CVPR, June 2020. 1, 2, 6,9
[31] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei. 3d object representations for fine- -re-ggr categorization. In IEEE Workshop on 3D Representation and Recognition, 2013. 6, 8
[32] Alex Krizhevsky, Vinod Nair, and Geolfrey Hinton. Cifar-10 and cif datasets. URL: https://www. cs.
toronto. edu/kriz/cifur. html, 2009. 7
[33] Kwonjoon Lee, Subhransu Maji. Avinash Ravichandran, and Stefano Soatto. Meta-learning with differen- tiable convex optimization. In CVPR, 2019.
10

---

[34]
Chundi Liu, Guangwei Yu, Maksims Volkovs, Cheng Chang, Himanshu Rai, Junwei Ma. and Satya Krishna
Gorti, Guided similarity separation for image retrieval. In NewrIPS, 2019.
[35]
Yanbin Liu, Juho Lec, Minscop Park, Sachoon Kim, Eunho Yang. Sung Ju Hwang, and Yi Yang. Learning to propagate labels: Transductive propagation network for few-shot learning. In ICLR, 2019. 7,9 Yaoyao Liu, Bernt Schiele, and Qianru Sun. An ensemble of epoch- wiih empirical bayes for few-shot
[36]
learning. ECCV, 2020. 7, 8.8. 9
[37]
David G Lowe. Distinctive image features from scalc-invariant keypeints. IJCV, 2004.
[38]
Nikhil Mishra, Mostafa Rohaninejad, Xi Chen, and Pieter Abbeel. A simple neural attentive meta-learner.
In ICLR, 2018. 7
[39]
Yair Movshovitz-Attias, Alexander Toshev, Thomas K Leung. Sergey Ioffe, and Saurabh Singh. No fuss
distance metric learning using proxies. In ICCV, pages 360-368, 2017. 9
[40]
Kevin Musgrave. Serge Belongie, and Ser-Nam Lim. A metric learning reality check. In ECCV, 2020.
[41] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta- peta-lcaming algorithms. arXiv, 2018.
[42]
tree. In CVPR, 2006. 8 Hyun Oh Song. Yu Xiang. Stefanie Jegelka, and Silvio Savarese. Deep metric learnnng via lifted structured
David Nister and Henrik Stewenius. Scalable recognition with
[43]
feature embedding. In CVPR, 2016.
[44] A. Oord, Y. Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, ArXiv, 2018.
[45] Boris Oreshkin, Pau Rodríguez López, and Alexandre Lacoste. Tadam: Task dependent adaptive metric for improved few-shot learning. In NewrlPS, 2018.
[46]
James Philbin, Ondrej Chum, Michael Isard. Josef Sivic, and Andrew Zisserman. Object retrieval with large vocabularies and fast spatial matching. In CVPR, 2007. 8
[47]
Qi Qian, Lei Shang, Baigui Sun, Juhua Hu, Hao Li, and Rong Jin. Softtriple loss: Deep metric learning
without triplct sampling. In ICCV, 2019. 9
[48] Danfeng Qin, Stephan Gammeter, Lukas Bossard, Till Quack, and Lue Van Gool. Hello neighbor: Accurate
object retrieval with k-reciprocal nearest neighbors. In CVPR, 2011. 3.
[49] Filip Radenović, Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondřej Chum. Revisiting oxford and paris: Large-scale image retrieval benchmarking. In CVPR, 2018. 5, 6
[50] Filip Radenović. Giorgos Tolias, and Ondřej Chum. Fine-tuning cmn image retrieval with no human annotation. TPAMI, 2018. 1, 2, 6, 9
[51] Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B. Tenenbaum, Hugo Larochelle, and Richard S. Zemel. Meta-lcarning for semi-supervised few-shot classification. In ICLR,
2018.7 7
[52] Jerome Revaud. Jon Almazán, Rafael S Rezende, and Cesar Roberto de Souza. Learning with average
precision: Training image retricval with a listwise loss. In ICCV, 2019. 8
[53] Pau Rodríguez, Issam Laradji, Alexandre Drouin, and Alexandre Lacoste. Embedding propagation:
Smoother manifold for few-shot classification. In ECCV, 2020. 7, 8, 9
[54] Sam Roweis, Geoffrey Hinton, and Ruslan Salakhutdinov. Neighbourhood component analysis. In NeurlPS, 2004. 9
[55] Andrei A Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals. Razvan Pascanu, Simon Osindero, and
Raia Hadsell. Meta-learning with latent embedding optimization. In ICLR, 2019. 7
[56] Jurgen Schmidhuber. Evolutionary principles in seff-rcferantial lcarning. On learning how to learn: The meta-mera--e hook.) Diploma thesis, Institut Informatik, Tech. Univ. Munich, 1987. 9
[57] Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In CVPR, 2015. 8
[58] Xiaohui Shen, Zhe Lin, Jonathan Brandt, Shai Avidan, and Ying Wu. Object retrieval and localization with spatially-constraine similarity measure and k-nn re-ranking. In CVPR, 2012. 9
[59] Josef Sivic and Andrew Zisserman. Video google: A text retrieval approach object matching in videos. In ICCV, 2003.
[60]
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In NeurlPS,
2017. 7.9
[61]
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. In NeurIPS, 2016. Hyun Oh Song. Yu Xiang, Stefanic Jegelka, and Silvio Savarese. Deep metric learning via lifted structured feature embedding. CVPR, 2016. 2,
[62]
[63] Eu Wern Teh, Terrance DeVries. and Graham Taylor. Proxynca++:. Revisiting and revitalizing proxy neighborhood component analysis. In ECCV, 2020. 1, 2, 6, 9
[64]
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing ingredient
for fast stylization. In ECCV, 2016. 5
[65]
Ashish Vaswani, Noam Shazcer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NewrIPS, 2017. 9
[66]
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot
learning. In NewrIPS, 2016. 5, 7, 8, 9
[67] C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie. The UCCD Birds-200-205 Dataset.
Technical Report CNS-TR-2011 1-001, California Institute of Technology, 2011. 5, 6
[68] Jiang Wang, Yang Song, Thomas Leung, Chuck Rosenberg, Jingbin Wang. James Philbin, Bo Chen, and
Ying Wu. Learning fine-grained image similarity with deep ranking. In CVPR, 2014. 8
[69] Xun Wang. Xintong Han. Weilin Huang, Dengke Dong, and Matthew R Scott. Multi-similarity loss with general pair weighting for deep metric leamiigg In CVPR, 2019.
11

---

[70] Xinshao Wang, Yang Hua, Elyor Kodirov, Guosheng Hu, Romain Garnier, and Neil M Robertson. Ranked list loss for deep metric learning. In CVPR, 2019. 9
[71]
Yan Wang. Wei-Lun Chao, Kilian Q Weinberger, and Laurens der Maaten. Simpleshot: Revisiting nearest-neighhor classification for few-shot learning. arXiv preprint arXiv: I. 1.06223, 2019.
[72]
Kilian Q Weinberger, John Blitzer, and Lawrence Saul. Distance metric learning for large margin nearest
neighbor classification, NeurIPS, 2005.
[73] Hong Xuan, Richard Souvenir, and Robert Pless. Deep randomized ensembles for metric learning. In
ECCV, 2018. 9
[74]
Sergey Zagoruyko and Nikos Komodakis, Wide residual networks. In BMVC, 2017. 7,
[75]
Zhun Zhong, Liang Zheng. Donglin Cao, and Shaozi Lt. Re-ranking person re-identification with
reciprocal encoding. CVPR, 2017. 1, 2, 3, 6, 7.
[76]
Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with
local and global consistency. NearIPS, 2003. 9
[77] Dengyong Zhou, Jason Weston, Arthur Gretton, Olivier Bousquet, and Berhhard Schölkopf. Ranking on data manifolds. NewrIPS, 2003.
12


Reviews:
[{"review_id": "YBmY8r57os", "reviewer": "Reviewer_STkv", "summary": "This paper applies a type of graph neural network on top of fixed image representations to learn to refine similarity graphs for image retrieval and transductive few-shot classification. A contrastive loss over image pairs is used to optimize the model.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n[S1] Experiments are shown for two different tasks: image retrieval and transductive few-shot classification with significant gains.\n[S2] The proposed approach is shown to work in conjunction with parallel approaches for further performance improvements.\n\nWeaknesses\n[W1] The proposed approach to incorporate similarity matrix is a type of graph neural network applied on top of generated image features. This has been explored before for example in this CVPR paper [1] for image retrieval which this paper has not studied. This paper also fails to review any literature on graph neural networks.\n[W2] Lack of clarity at several places. For example, it is not clear what is the operation \"GraphSum(...)\" [L108]. The final paragraph [L160-165] is also unclear: is the method using D^t for all t except for the last step t=T?\n[W3] Most consistent performance improvements are shown for image retrieval. However, the image retrieval setup is not convincing. All of the methods in table 1 are adopted from different problems: AQE, DQE, and alphaQE test on the landmark retrieval datasets, while reciprocal-k is applied to the person re-id problem. It would make more sense to follow an existing retrieval pipeline for fair comparisons.\n\n[1]Liu, Chundi, et al. \"Guided similarity separation for image retrieval.\" Advances in Neural Information Processing Systems 32 (2019): 1556-1566.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "P1KWMWewOk", "reviewer": "Reviewer_wrsa", "summary": "The paper deals with image retrieval, i.e. the problem of finding images in a database which are the most similar to a given query image. More specifically, the paper describes a method for re-ranking retrieval (and few-shot classification) results in order to improve performance. The technique consists in learning how to refine the retrieval results by first representing them as a similarity matrix, then learning a deep network G that learns how to produce a step that refines this matrix.\n\nThe contributions of the paper could be summarized as follows:\n\n1) A novel method for re-ranking that uses a neural network to enhance the similarity matrix directly (which the authors call a ubgraph Similarity Refiner);\n2) An approach for combining the method above with k-reciprocal re-ranking;\n3) Experiments showing the method above leads to consistent improvements (although with varying levels of significance)", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper reads well and has no typos. The motivation behind the paper is clear and the approach is interesting. The authors experiment on 6 different datasets comprised of both image-retrieval (CUBS, SOP, CARS) and few-shot classification problems (mini-ImageNet, tiered-ImageNet, CIFAR-FS). The authors provide some ablation studies decomposing some of their results to indicate how different steps of their method affect overall performance.\n\nA significant part of the image retrieval literature have benchmarked other re-ranking strategies in the more challenging ROxford/RParis+1M datasets [A] instead of CUB/CARS/SOP. It would be interesting to know how this method would work in such a large-scale scenario.\n\n[A]: Radenovic´ et al, Revisiting Oxford and Paris: Large-Scale Image Retrieval Benchmarking, CVPR 2018\n\n# Very, very minor comments\n\n- Typos: retrievel [l.59], \n- Table 3 and 4 are wrapped around their respective paragraphs, probably due to size constraints, but still they seem a bit off. Their legend/subtitles are a bit packed making it a little bit confusing to read. But again, this is just a very minor comment.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8h"}, "extra_text": {}}, {"review_id": "HGv4XyyEqt", "reviewer": "Reviewer_2iMx", "summary": "The paper is about learning how to re-rank for retrieval with global image descriptors. There is a first step of retrieval to get the top-N neighbors to the query. Then, the NxN adjacency matrix is created which is the input for the re-ranking during training and during testing. The adjacency matrix is refined in an iterative way and by processing different sub-matrices each time. \nDuring training the NxN adjacency matrix is forced to be close to the binary matrix that is contructed according to the class labels. At the same time, with the use of synthetic gradients, the backbone that is used to generate the feature vectors is updated so that the cosine similarity of the feature vectors facilitates the update of the adjacency matrix. \n- this is a novel approach to re-ranking - the whole formulation is new for this task, so does the use of synthetic gradients\n- the method is applied on two different tasks: image retrieval and transductive few-shot learning.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- it's refreshing to see such an approach which includes out of the box thinking to approach the task of re-ranking \n- the ablations included in the paper are nicely conducted, they are informative and convincing\n- the demonstrated improvements seem to be convincing. \n- A missing bit is to see how does this compare with graph-based re-ranking such as  [10][22][75]. It is true that these methods carry a higher cost of having to maintain the graph of the whole dataset, while in the proposed case the NxN adjacency can be also computed on the fly. But anyways also the reciprocal neighbors need to carry out such a cost. This is one of the the main drawbacks of this work.\n- what if the features backbone is not updated with synthetic gradients, but only gets updated according to the gradient of the loss in (6) and (7)? this is an interesting ablation which is missing\n- (5) will accumulate many sub-matrices. The common row (eg in retrieval) is the row of the query. Which means that there are many summands (N actually) to get the result of this row. All other rows will appear only once. This feels that the refined sub-matrices should have much smaller values for the adjacency matrix to make sense. Do the authors verify something like that? This could be a main reason why more iterations do not work. Stopping after 1 iteration is probably still meaningful because the query row is used for re-ranking. \n- \"N = 50 for SOP, because they give the most stable  performance in “Feat. + Ours”\": how these different values are chosen for different datasets? Is a proper validation set used? It is mentioned that the evaluation metric from [39] is used but not if the whole protocol is followed. [39] showed that prior work was tuning hyper-parameters on the test-sets which was leading to invalid comparisons.\n- the training process results in a learned re-ranking process and update backbone. What is the effect of using only the updated backbone without any re-ranking? Is the updated backbone good to use for the similaritites of the adjacency matrix or also for the first step of retrieval to get the top-N results? Is it possible that the initial network (eg one from the group loss) is still beter for the initial ranking?\n- how are the training batches of N samples generated? This information is missing.  \n\n\n\n------\npost-rebuttal:\nThe authors provided a good response and I am still positive about the work\n- there is significant difference between the proposed approach and GSS. GSS is learned and test on the same fixed dataset. This should be pointed out in the paper.\n- [22] performs better but such an approach carries the cost of computing the graph for the whole dataset. this should be clarified and discussed.\n- I now see the misunderstanding about updating the backbone - I agree that this should be properly clarified. \n- The new results for smaller step size are helpful - I suggest to add in appendix.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is not discussed at all", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an interesting approach for re-ranking based on learning similarity graph between data points to be ranked. Reviewers agree that the paper presents interesting ideas. A concern remains which is: comparison with our GNN based ranking methods. It would be important for authors to present strong GNN based ranking baselines. 
Decision: Accept (Poster)