# Understanding Image Retrieval Re-Ranking: A Graph Neural Network Perspective

arXiv: https://arxiv.org/abs/2012.07620 · HTML: https://mlsanity.com/paper/2012.07620/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2020.

## Built on by (most cited first, 24 of 24)

- [The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges](https://mlsanity.com/paper/2407.09618/) (2024)
- [Ada-NETS: Face Clustering via Adaptive Neighbour Discovery in the Structure Space](https://mlsanity.com/paper/2202.03800/) (2022)
- [Triplet Contrastive Representation Learning for Unsupervised Vehicle Re-identification](https://mlsanity.com/paper/2301.09498/) (2023)
- [Using LLM to select the right SQL Query from candidates](https://mlsanity.com/paper/2401.02115/) (2024)
- [Graph Convolution Based Efficient Re-Ranking for Visual Retrieval](https://mlsanity.com/paper/2306.08792/) (2023)
- [Graph Neural Networks in Vision-Language Image Understanding: A Survey](https://mlsanity.com/paper/2303.03761/) (2023)
- [Learnable Pillar-based Re-ranking for Image-Text Retrieval](https://mlsanity.com/paper/2304.12570/) (2023)
- [Towards Writer Retrieval for Historical Datasets](https://mlsanity.com/paper/2305.05358/) (2023)
- [Moving Towards Centers: Re-ranking with Attention and Memory for Re-identification](https://mlsanity.com/paper/2105.01447/) (2021)
- [Dynamic Visual Semantic Sub-Embeddings and Fast Re-Ranking](https://mlsanity.com/paper/2309.08154/) (2023)
- [Clothes-Changing Person Re-Identification with Feasibility-Aware Intermediary Matching](https://mlsanity.com/paper/2404.09507/) (2024)
- [A Re-ranking Method using K-nearest Weighted Fusion for Person Re-identification](https://mlsanity.com/paper/2509.04050/) (2025)
- [Vehicle Re-identification Method Based on Vehicle Attribute and Mutual Exclusion Between Cameras](https://mlsanity.com/paper/2104.14882/) (2021)
- [Cluster-Aware Similarity Diffusion for Instance Retrieval](https://mlsanity.com/paper/2406.02343/) (2024)
- [Content-based 3D Image Retrieval and a ColBERT-inspired Re-ranking for Tumor Flagging and Staging](https://mlsanity.com/paper/2507.17412/) (2025)
- [Homogeneous and Heterogeneous Consistency progressive Re-ranking for Visible-Infrared Person Re-identification](https://mlsanity.com/paper/2603.16165/) (2026)
- [Connecting Images through Time and Sources: Introducing Low-data, Heterogeneous Instance Retrieval](https://mlsanity.com/paper/2103.10729/) (2021)
- [MABNet: Master Assistant Buddy Network with Hybrid Learning for Image Retrieval](https://mlsanity.com/paper/2303.03050/) (2023)
- [Dynamic Textual Prompt For Rehearsal-free Lifelong Person Re-identification](https://mlsanity.com/paper/2411.06023/) (2024)
- [Visual Re-Ranking with Non-Visual Side Information](https://mlsanity.com/paper/2504.11134/) (2025)
- [Locality Preserving Markovian Transition for Instance Retrieval](https://mlsanity.com/paper/2506.05196/) (2025)
- [ReCap: Event-Aware Image Captioning with Article Retrieval and Semantic Gaussian Normalization](https://mlsanity.com/paper/2509.01259/) (2025)
- [Multimodal LLM-Empowered Re-Ranking for Generalizable Person Re-Identification](https://mlsanity.com/paper/2606.16161/) (2026)
- [ANFI: Rethinking Neighbor Feature Interaction in Person Re-ID](https://mlsanity.com/paper/2607.25407/) (2026)

## Abstract (arXiv)

The re-ranking approach leverages high-confidence retrieved samples to refine retrieval results, which have been widely adopted as a post-processing tool for image retrieval tasks. However, we notice one main flaw of re-ranking, i.e., high computational complexity, which leads to an unaffordable time cost for real-world applications. In this paper, we revisit re-ranking and demonstrate that re-ranking can be reformulated as a high-parallelism Graph Neural Network (GNN) function. In particular, we divide the conventional re-ranking process into two phases, i.e., retrieving high-quality gallery samples and updating features. We argue that the first phase equals building the k-nearest neighbor graph, while the second phase can be viewed as spreading the message within the graph. In practice, GNN only needs to concern vertices with the connected edges. Since the graph is sparse, we can efficiently update the vertex features. On the Market-1501 dataset, we accelerate the re-ranking processing from 89.2s to 9.4ms with one K40m GPU, facilitating the real-time post-processing. Similarly, we observe that our method achieves comparable or even better retrieval results on the other four image retrieval benchmarks, i.e., VeRi-776, Oxford-5k, Paris-6k and University-1652, with limited time cost. Our code is publicly available.