Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.

main_review: Strengths
[S1] Experiments are shown for two different tasks: image retrieval and transductive few-shot classification with significant gains.
[S2] The proposed approach is shown to work in conjunction with parallel approaches for further performance improvements.

Weaknesses
[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.
[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?
[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.

[1]Liu, Chundi, et al. "Guided similarity separation for image retrieval." Advances in Neural Information Processing Systems 32 (2019): 1556-1566.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

The contributions of the paper could be summarized as follows:

1) 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);
2) An approach for combining the method above with k-reciprocal re-ranking;
3) Experiments showing the method above leads to consistent improvements (although with varying levels of significance)
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.

A 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.

[A]: Radenovic´ et al, Revisiting Oxford and Paris: Large-Scale Image Retrieval Benchmarking, CVPR 2018

# Very, very minor comments

- Typos: retrievel [l.59], 
- 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.
limitations_and_societal_impact: Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
During 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. 
- this is a novel approach to re-ranking - the whole formulation is new for this task, so does the use of synthetic gradients
- the method is applied on two different tasks: image retrieval and transductive few-shot learning.
main_review: - it's refreshing to see such an approach which includes out of the box thinking to approach the task of re-ranking 
- the ablations included in the paper are nicely conducted, they are informative and convincing
- the demonstrated improvements seem to be convincing. 
- 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.
- 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
- (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 = 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.
- 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?
- how are the training batches of N samples generated? This information is missing.  



------
post-rebuttal:
The authors provided a good response and I am still positive about the work
- 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.
- [22] performs better but such an approach carries the cost of computing the graph for the whole dataset. this should be clarified and discussed.
- I now see the misunderstanding about updating the backbone - I agree that this should be properly clarified. 
- The new results for smaller step size are helpful - I suggest to add in appendix.
limitations_and_societal_impact: This is not discussed at all
review_title: null

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)