Locality Preserving Markovian Transition for Instance Retrieval
Jifei Luo, Wenzheng Wu, Hantao Yao, Lu Yu, Changsheng Xu, Jifei Luo, Wenzheng Wu, Hantao Yao, Lu Yu, Changsheng Xu · 2025
Read Locality Preserving Markovian Transition for Instance Retrieval by Jifei Luo, Wenzheng Wu, Hantao Yao, Lu Yu, Changsheng Xu, Jifei Luo, Wenzheng Wu, Hantao Yao, Lu Yu, Changsheng Xu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-05196.txt.
Introduction
Jifei Luo and four co-authors present a method for searching image collections by example, in this 2025 computer science paper. Given one picture, instance retrieval asks a system to find the same object or place in a huge database. A common refinement spreads similarity scores across a graph of related images, but the useful signal fades after a few hops, so distant matches are judged poorly.
Their framework, LPMT, runs a longer, heat-like diffusion process that preserves local structure. First, diffusion runs across separate graphs in both directions to firm up similarity links. Each image is then encoded as a distribution that sharpens local consistency. A thermodynamic transition process connects those distributions, allowing global search without losing local accuracy. Tests across varied retrieval tasks confirmed the gains. Better retrieval powers everything from product search to recognizing a landmark from a tourist's snapshot.
Catalog record
| CREATOR | Jifei Luo, Wenzheng Wu, Hantao Yao, Lu Yu, Changsheng Xu, Jifei Luo, Wenzheng Wu, Hantao Yao, Lu Yu, Changsheng Xu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-05196
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Locality Preserving Markovian Transition for Instance Retrieval Jifei Luo, Wenzheng Wu, Hantao Yao, Lu Yu, Changsheng Xu, Jifei Luo, Wenzheng Wu, Hantao Yao, Lu Yu, Changsheng Xu Abstract Diffusion-based re-ranking methods are effective in modeling the data manifolds through similarity propagation in affinity graphs. However, positive signals tend to diminish over several steps away from the source, reducing discriminative power beyond local regions. To address this issue, we introduce the Locality Preserving Markovian Transition (LPMT) framework, which employs a long-term thermodynamic transition process with multiple states for accurate manifold distance measurement. The proposed LPMT first integrates diffusion processes across separate graphs using Bidirectional Collaborative Diffusion (BCD) to establish strong similarity relationships. Afterwards, Locality State Embedding (LSE) encodes each instance into a distribution for enhanced local consistency. These distributions are interconnected via the Thermodynamic Markovian Transition (TMT) process, enabling efficient global retrieval while maintaining local effectiveness. Experimental results across diverse tasks confirm the effectiveness of LPMT for instance retrieval. Figure 1: Illustration of Locality Preserving Markovian Transition. Each instance is embedded as a distribution within the manifold, with its characteristics shaped by the intrinsic local neighborhood structure. Distant distributions are bridged via multiple intermediate states, where each transition is confined to a local region and governed by the master equation. The minimum transition cost then serves as an effective distance measure for improved retrieval. 1 Introduction Instance retrieval aims to identify images visually similar to a given query image on a large scale. Typically, the global image features are obtained through the aggregation of local descriptors ( Jégou et al. 2012 ; Noh et al. 2017 ) or leveraging deep neural networks ( Cao et al. 2020 ; Yang et al. 2021 ; Lee et al. 2022 ; Lee et al. 2023 ) . After that, a ranking of images can be generated by computing the similarity or distance between these features. However, the feature extraction process inevitably loses some important information, and the capability of models often limits the expressiveness of the features. Consequently, refining the initial ranking results can improve the overall retrieval performance, referred to as re-ranking. A prominent approach is the Query Expansion (QE) ( Chum et al. 2007 ; Shao et al. 2023 ) , which uses high-confidence samples from the top-ranked results to generate a more robust query feature for secondary retrieval. However, these methods fail to effectively capture the latent manifold structure within the data space, limiting the performance. Recently, diffusion-based methods ( Iscen et al. 2017 ; Iscen et al. 2018 ; Prokopchik et al. 2022 ; Bai et al. 2019a ; Bai et al. 2019c ; Luo et al. 2024 ; Yang et al. 2019 ; Zhang et al. 2023 ) have been utilized to investigate the manifold structure of data for re-ranking, a process also known as manifold ranking. These methods begin with the initial retrieval results and construct a k -nearest neighbor graph ( Zhou et al. 2003 ; Donoser & Bischof 2013 ) to model the intrinsic data manifold. Once the graph is created, similarity information is iteratively propagated along the edges, allowing for the consideration of higher-order relationships between instances. The resulting manifold-aware similarity matrix demonstrates improved retrieval performance as the process converges. However, existing methods often rely heavily on graph construction strategies, e.g. , errors can propagate throughout the graph if the adjacency relationships are incorrect, while missing connections between high-confidence nodes can disrupt the flow of positive information. As a result, valuable information may diminish over multiple diffusion steps for instances outside the local region, leading to a loss of discriminative power. Therefore, improving the reliability of knowledge transmission in long-distance nodes is critical for effective manifold ranking. The adverse effects of inaccurate propagation in diffusion-based methods can be substantially attenuated by modeling each instance as a probability distribution within the data manifold for distance measurement, while the importance of reliable neighborhoods can be emphasized at the same time. Additionally, building on the foundation of previous studies ( Evans et al. 1993 ; Barato & Seifert 2015 ; Ito 2018 ; Van Vu & Saito 2023 ) , a long-term thermodynamic Markovian transition process consisting of multiple states can be utilized to quantify manifold distances. This approach effectively reduces information decay during the propagation across distributions. As demonstrated in Figure 1 , two distant distributions are bridged through a series of intermediate states, each representing a probability distribution of an instance. By restricting each transition to a local region, the method ensures that information remains coherent and locally relevant throughout the process. The Markovian transition process governing each stage that connects two consecutive states is defined by the master equation ( Seifert 2012 ) , which offers a more precise representation of the manifold structure than traditional metrics, such as total variation. This multi-state thermodynamic process creates a transition flow within the manifold, wherein the minimal cost effectively serves as a distance metric. In this paper, we introduce a novel approach called Locality Preserving Markovian Transition (LPMT), which consists of Bidirectional Collaborative Diffusion (BCD), Locality State Embedding (LSE), and Thermodynamic Markovian Transition (TMT). The Bidirectional Collaborative Diffusion mechanism extends the reference adjacency graph into a graph set by systematically adding and removing some connections. This integration allows for a robust similarity matrix to be constructed through the joint optimization of combination weights and the equivalent objectives of the diffusion process, as highlighted in previous work ( Luo et al. 2024 ) . Subsequently, Locality State Embedding assigns a probability distribution to each instance within the manifold space, utilizing information from neighboring instances to enhance local consistency. Finally, the Thermodynamic Markovian Transition establishes a multi-state process on the manifold, wherein distant distributions navigate through several intermediate states within their respective regions. This approach elucidates the underlying manifold structure by capturing the minimum transition cost while preserving local characteristics. To compute the final distance, a weighted combination of this cost and the Euclidean distance is employed, enabling efficient global retrieval. Experimental results on various instance retrieval tasks validate the effectiveness of the proposed Locality Preserving Markovian Transition. Specifically, LPMT achieves mAP scores of 84.7%/67.8% on R Oxf and 93.0%/84.1% on R Par under medium and hard protocols, respectively, demonstrating its superior performance. 2 Related Work Instance Retrieval . The objective of instance retrieval is to identify images in a database that resemble the content of a query instance. With the rapid advancement of deep learning, global features extracted by deep neural networks ( Radenović et al. 2019 ; Cao et al. 2020 ; Yang et al. 2021 ; Lee et al. 2022 ; Lee et al. 2023 ) have gradually replaced local descriptors ( Lowe 2004 ; Jégou et al. 2012 ; Noh et al. 2017 ) . Despite their effectiveness, the retrieval performance can be further refined through a post-process known as re-ranking. Re-ranking . Specifically, re-ranking can be broadly divided into Query Expansion, Diffusion-based Methods, Context-based Methods, and Learning-based Methods. Query expansion . The higher relevance maintained by the top-ranked images leads to the development of Query Expansion (QE), which integrates neighboring features to build a more effective query. While AQE ( Chum et al. 2007 ) simply averages the features of top returned images, AQEwD