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

As a prevailing post-processing tool for image retrieval, re-ranking typically leverages high-confidence retrieved samples to refine the initial ranking list. However, a significant challenge persists: existing re-ranking methods are computationally intensive, leading to impractical time costs for real-world applications. To overcome this limitation, we first review current re-ranking techniques and then introduce a novel real-time approach by reformulating the re-ranking process as a highly-parallel Graph Neural Network (GNN). Specifically, we decompose the traditional neighbor-based re-ranking into two distinct stages: retrieving high-quality gallery samples and refining neighbor similarity. We propose that the first stage can be effectively replaced by constructing a k-nearest neighbor (knn) graph, while the second stage can be implemented by propagating messages within this graph. In practice, since the knn graph is sparse, the GNN only considers a limited number of vertices and their connected edges, enabling efficient updates of vertex features. We validate the effectiveness and efficiency of our approach through extensive experiments on five datasets. For example, on the Market-1501 dataset, our method accelerates the re-ranking process to 9.4ms using a single K40m GPU. Additionally, we observe similar acceleration results on the other four retrieval benchmarks, Paris-6k, Oxford-5k, VeRi-776, and University-1652, while maintaining competitive performance.