Zhang Xuanmeng ; Jiang Minyue ; Zheng Zhedong ; Tan Xiao ; Ding Errui ; Yang Yi

Abstract

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