Locality Preserving Markovian Transition for Instance Retrieval
Authors: Jifei Luo
Wenzheng Wu
Hantao Yao
Lu Yu
Changsheng Xu
Venue: ICML 2025 poster (2025)
Keywords: Retrieval
Manifold ranking
Re-ranking
Diffusion
Primary area: general_machine_learning

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.

Locality Preserving Markovian Transition for Instance Retrieval
Jifei Luo' Wenzheng Wu
Hantao Yao
Lu Yu ?
Changsheng Xu
Abstract
Minimum Transition Flow Cost
Diffusion-based re-ranking methods are effective in modeling the data manifolds through similarity propagation in affinity graphs. However, positive signals tend diminish over several steps away from the source, reducing discriminative power beyond local regions. To address this issue, we in- troduce the Locality Preserving Markovian Tran- sition (LPMT) framework, which employs a long- term thermodynamic transition process with mul- tiple states for accurate manifold distance mea- surement. The proposed LPMT first integrates diffusion processes across separate graphs using Bidirectional Collaborative Diffusion (BCD) establish strong similarity relationships. After- wards, Locality State Embedding (LSE) encodes each instance into a distribution for enhanced lo- cal consistency. These distributions are intercon- nected via the Thermodynamic Markovian Tran- sition (TMT) process, enabling efficient global re- trieval while maintaining local effectiveness. Ex- perimental results across diverse tasks confirm the effectiveness of LPMT for instance retrieval.
9:
TT
Thermsdhaanie
Pi
Pg
Pix-1
Pix
Figure I. Illustration Locality Preserving Markovian Transition. Each instance is embedded as distribution within the manifold, with its characteristics shaped by intrinsic local neighborhood structure. Distant distributions are bridged via multiple intermedi- ate 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.
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 al., 2007; Shao al., 2023), which uses high- confidence samples from the top-ranked results to generate 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.
1. Introduction
Instance retrieval aims to identify images visually similar to given query image on 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 lever- aging deep neural networks (Cao et al., 2020; Yang al., 2021; Lee et al., 2022; 2023). After that, ranking of images be generated by computing the similarity or distance between these features. However, the feature extraction pro- cess inevitably loses some important information, and the capability of models often limits the expressiveness of the
Recently, diffusion- methods (Iscen et al., 2017; 2018; Prokopchik et al., 2022; Bai et al., 2019a;e; 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, process also known as manifold ranking. These meth- ods begin with the initial retrieval results and construct 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 considera- tion of higher-order relationships between instances. The resulting manifold- similarity matrix demonstrates improved retrieval performance as the process converges. However, existing methods often rely heavily on graph con- struction strategies, e.g., errors can propagate throughout the graph if the adjacency relationships are incorrect, while missing connections between high-confidence nodes can
University of Science and Technology of China, Hefei, China "Tianjin University of Technology. Tianjin, China "Institute of Automation, Chinese Academy of Sciences, Beijing, China. Cor- respondence to: Hantao Yao <yaohantao@ @us.eeeuooutt............
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Locality Preserving Markovian Transition for Instance Retrieval
disrupt the flow of positive information. As result, valu- able information may diminish over multiple diffusion steps for instances outside the local region, leading to loss of discriminative power. Therefore, improving the reliability of knowledge transmission in long-distance nodes is critical for effective manifold ranking.
Experimental results on various instance retrieval tasks vali- date the effectiveness of the proposed Locality Preserving Markovian Transition. Specifically, LPMT achieves mAP scores of 84.7% .7%% on ROxf and 93.0% I 1% on RPar under medium and hard protocols, respectively, demonstrat- ing its superior performance.
The adverse effects of inaccurate propagation in diffusion- based methods can be substantially attenuated by modeling each instance 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 stud- ies (Evans et al., 1993; Barato & Seifert, 2015; Ito, 2018; Van Vu & Saito, 2023), a long-term thermodynamic Marko- vian transition process consisting of multiple states can be utilized to quantify manifold distances. This approach effectively reduces information decay during the propaga- tion across distributions. As demonstrated in Figure 1, two distant distributions are bridged through a series of interme- diate 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.
2. Related Work
Instance Retrieval. The objective of instance retrieval is to identify images in 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; 2023) have gradually replaced local de- scriptors (Lowe, 2004; Jégou et al., 2012; Noh et al., 2017). Despite their effectiveness, the retrieval performance can be further refined through post-process known as re-ranking.
Re-ranking, Specifically, re-ranking can be broadly divided into Query Expansion, Diffusion-bart 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 Ex- pansion (QE), which integrates neighboring features to build more effective query. While AQE (Chum et al., 2007) simply averages the features of top returned images, AQEwD (Gordo et al., 2017), DQE (Arandjelović & Zisser- man, 2012), aQE (Radenović et al., 2019), and SG (Shao et al., 2023) apply diminishing aggregation weights the subsequent ones, leading enhanced retrieval performance.
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 Thermodyaamic Markovian Transition (TMT). The Bidirectional Collaborative Diffu- sion mechanism extends the reference adjacency graph into graph set by systematically adding and removing some connections. This integration allows for robust similarity matrix to be constructed through the joint optimization of combination weights and the equivalent objectives of the dif- fusion process, as highlighted in previous work (Luo et al., 2024). Subsequently, Locality State Embedding assigns a probability distribution to each instance within the mani- fold space, utilizing information from neighboring instances to enhance local consistency. Finally, the Thermodynamic Markovian Transition establishes 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 presery- ing local characteristics. To compute the final distance, a weighted combination of this cost and the Euclidean dis- tance is employed, enabling efficient global retrieval.
Difsusiio-bbsed Methods. Leveraging the intrinsic mani- fold structure of data, diffusion-basee methods serve as a powerful technique for re-ranking. After the theory has orig- inally been developed (Zhou et al., 2003; Yang et al., 2009; Donoser & Bischof, 2013), it has been successfully intro- duced to the field of instance retrieval (Iscen et al., 2017: 2018: 8; Yang et al., 2019). To further capture the underly- ing relationships, researchers (Zhou et al., 2012; Bai et al., 2019a;e; Yang et al., 2013; Zhang et al., 2015) seek to aggre- gate higher-order information by propagating messages on a hypergraph or integrating information from distinct graphs. Additionally, EGT (Chang et al., 2019) and CAS (Luo et al., 2024) adjust the diffusion strategy to address the problem of unreliable connections, resulting in improved effectiveness.
Context-hased Methods. Given that the contextual informa- tion contained by nearest neighbors can lead to notable im- provements in retrieval performance. Pioneer works (Jégou et al., 2007; Shen et al., 2012; Sarfraz et al., 2018) adjust the distance measure by using the ranking or similarity rela- tionships in the neighborhood, while recent approaches (Bai & Bai, 2016; Zhong et al., 2017; Zhang et al., 2020; Yu et al., 2023; Liao et al., 2023; Kim et al., 2022) encode each
2

---

Locality Preserving Markovian Transition for Instance Retrieval
Dusaur
LLMs are further integrated into Retrieval-Augmenic Gen- eration (RAG) systems (Chen al., 2024; Borgeaud et al., 2022; Asai et al., 2024), enabling the extraction of relevant content from external knowledge bases to produce coherent and factually accurate responses. Given the modern empha- sis on logical reasoning and deeper understanding in textual retrieval (Su et al., 2025), leveraging powerful LLMs (Xiao et al., 2023) to dynamically re-evaluate query- similarity for re-ranking yields superior quality, surpassing approaches solely based on semantic feature embeddings.
(a) Fuclidion ranking
(b) Manifild ranking
Figure 2. Comparison of ranking results based on (a) Euclidean distance and (b) manifold-aware distance in the feature space.
3. Preliminary
instance into a manifold-aware space to perform re-ranking, where similar images exhibit higher contextual consistency.
Given a query image, instance retrieval aims to sort the gallery image set ascending order, where images at the front are more similar the query. Formally, define the whole image set containing query and gallery images as X' = (2,, ......... Jaa J. A d-dimensional image feature for each image in X' can be extracted with pretrained model to measure the pairwise distance. Denote the image feature corresponds to Iy as f:, the Euclidean distance between 2; and 2y the feature space can be calculated by:
Learning-based Methods. Recently, deep learning methods have also been introduced to assist with re-ranking. For example, Gordo et al. (2020) and Ouyang et al. (2021) lever- age the robust encoding power of self-attention mechanisms to learn weight relationships for aggregating representative descriptors. Meanwhile, Liu et al. (2019) and Shen et al. (2021) seek to perform information propagation via optimiz- ing graph neural network (Gasteiger et al., 2018), allowing the ranking result to capture the intrinsic manifold structure.
d(i,j) = Ilf - -fyll.
(1)
Large Pre-trained Models for Information Retrieval. In- formation retrieval in both visual and textual modalities has undergone fundamental shift with the emergence of large pre-trained models, often referred to as foundation models.
The distance between the query x; and images in X com- puted by Eq. (1) can be directly used for ranking the gallery set concerning 24. However, the retrieval result based on Fu- clidean distance always reflects sub-optimal performance.
VLMs Image Retrieval. Trained on colossal web-scale image-text datasets, Vision-Language Models (VLMs) (Rad- ford et al., 2021: Jia et al., 2021; Yao et al., 2022; Li et al., 2022; 2023; Liu et al., 2023) serve as foundational back- bones for diverse vision and language tasks. These models provide semantically rich and discriminative features for both modalities, aligned within a shared semantic space, en- abling sophisticated cross-modal retrieval. However, unlike precise instance-level retrieval, VLMS inherently prioritize broad conceptual understanding, often yielding initial re- sults that are semantically relevant but lack fine-gre ane-grained in- stance discrimination (e.g., query for "Eiffel Tower" may retrieve range of related images without accurately dis- tinguishing between highly similar photographic instances). Nevertheless, the latent manifold structure present in the feature space of semantically similar samples offers a com- pelling basis for subsequent re-ranking methods aimed at refining retrieval precision.
Drawing from the prior knowledge that similar images are distributed along a low-dimensional manifold induced by the whole image set X. Prioritizing images that simultane- ously exhibit higher proximity in Euclidean and manifold spaces can improve retrieval results. To achieve this, a gen- eral approach is to model the underlying manifold structure with k-nearest neighbor graph g {V,E), each vertex e; in V = (V1, u2,..., ) represents the corresponding position of x; within the data manifold, while & = V x V denotes the edges weighted by:
Wiy iy = 1 exp (-d (i_())))//")
(2)
where 1.V is indicator matrix to represent the k-nearest neighbors, i..., 1 1, if E Ni k). otherwise 1. O.
To exploit the underlying manifold geometry encoded in the adjacency matrix W, diffusion- based methods (Iscen et al., 2017; Bai et al., 2019a; Luo et al., 2024) spread information along neighboring edges within the graph in an unsuper- vised manner, producing a similarity matrix that captures the manifold relationships for re-ranking. A comprehensive visual explanation of manifold ranking is shown in Fig. 2. Nevertheless, the diffusion process is susceptible to interfer- ence from inaccuracies in the adjacency graph construction and struggles to maintain discriminative power beyond the local region, thereby limiting the overall performance.
LLMs for Textual Retrieval. Moving beyond lexical statis- tics, Large Language Models (LLMs) (Thakur et al., 2021; Devlin et al., 2019) empower deep semantic understanding of both queries and documents. Through the encoding of queries and documents into a high-dimensional embedding space, LLMs are broadly applied within dense information retrieval paradigms. Building on these retrieval capabilities,
3

---

Locality Preserving Markovian Transition for Instance Retrieval
4. Locality Preserving Markovian Transition
Affinity Grophs
Adjarenz Mazices
To overcome the limitations that traditional diffusion models are sensitive to graph construction and struggle to generalize across varying data distributions, we propose Bidirectional Collaborative Diffusion (BCD) to integrate diffusion pro- cesses on multi-level affinity graphs automatically. To fur- ther enhance global discriminative power without compro- mising local effectiveness, we introduce the Locality State Embedding (LSE) strategy, which represents each instance as local consistent distribution within the underlying man- ifold. Afterwards, Thermodynamic Markovian Transition (TMT) is proposed to perform constrained time evolution transition process within the local regions at each stage. The minimal cost of multi-step transitions can effectively cap- ture the intrinsic manifold structure, providing a powerful distance metric for instance retrieval. In the following, we give detailed description of each proposed component.
G¹
Raduce Connections
Similarty Matnx
BCD
ge
Incresse Connections
W
Figure 3. An illustration of the proposed Bidirectional Collabora- tive Diffusion (BCD) algorithm with three scales, where different connection strategies are employed to accommodate diverse data distributions. BCD automatically performs diffusion and integra- tion generate robust similarity matrix.
The optimization problem in Eq. (3), which simultaneously depends on / and F, is inherently complex and imprac- tical for direct solution. To resolve this, we propose numerical method that decomposes the target function into two sub-problems: Optimize F with Fixed 33 and Optimize 3 with Fixed F. This allows for a systematic iterative ap- proximation of the optimal result through the -eint scheme.
4.1. Bidirectional Collaborative Diffusion
Given a reference adjacency matrix W. we can generate an extended set (W', W ,..., W } by adding and remov- ing some connections, Their contribution to the total dif- fusion process is denoted by {3. = {Bi, 82, ........ Bm)] J. which can be dynamically adjusted. As shown in Fig. 3, BCD seeks to automatically perform diffusion and integra- tion to produce a robust result. The smoothed similarity F and weights 3 are jointly optimized follow by:
Optimize F with Fixed B. Assuming that (B: (1 are fixed, such that they can be directly omitted during the optimiza- tion process of F. Incorporating the definition of H into the objective yields the following formulation:
min B.F
Σ
m
1 H +
11
min
W
F
ki
F
kij
2
D
D
s.t. 05 < 1,
Σ B. 1,
(5)
F ik
Fyk
3 W
+ 14
F
E.
26 VDJ
where H denotes the objective value of Bidirectional Simi- larity Diffusion (Bai et al., 2019a;e; Luo et al., 2024) process with respect to W", followed as:
This formulation is still hard to deal with, refer to the deriva- tion in Appendix A. we transform it into a vectorized formulation to facilitate the solution follows,
n
FRi
Fej
2
Hd
W
4
VDJ
Brveel ()T(T))(TTT (I (I-3"))eel 33")oc(( FF) allvee((F EEIB (6)
k= 1.) 11
(4)
F VDW 1
Fjk
+
+ |1|| F E
VD jj
where I E gnn2x?? is an identity matrix, and St is the mean Kronecker product form of normalized matrix S". calculated by Sa (I @ S S T)/2, in which the corresponding normalized matrix to W is denoted as S (D") 1D"--//W""(D (D")-1/2, Additionally, vec(-) denotes the vectorization operator, with its inverse function as vec (-).
As for each adjacency matrix 8d in Eq. (4), D" is the diagonal matrix with its i-th diagonal element equal to the summation of the i-th row in W" The regularization term is weighted by a > O, where the matrix E is positive and semi- definite and is used to avoid F from being extremely smooth. For given triplet of vertices UR. Ui and Uy in graph G, the smoothed similarities F&, and Fay are regularized by the affinity weight W Meanwhile, the bidirectional strategy also takes the reverse pair F F and F2 into consideration, ensuring the symmetric of the target matrix F.
The Hessian matrix of J in Eq. (6) is proved to be positive- definite in Appendix 1. such that the optimal solution is achieved when the first order is equal to zero, that is:
V Vooet [) Σ Bo 8" (")vec((F) + 22[(vec(F F E)). (7)
4

---

Locality Preserving Markovian Transition for Instance Retrieval
By substituting the hyper-parameter By with a2 = and introduce a 1+11 the simplified closed form solution F can be expressed as:
___- μ+I
Algorithm 1 Bidirectional Collaborative Diffusion
Input: extended adjacency matrices set {W") T hyper-
parameters X, Jr, max number of iterations maziler. Output: adaptive smoothed similarity matrix F.
F (1- - (II -
Σ 0 "on"")'''cccl vec(E)) EE).
(8)
I: initialize t 0, {Bu) 1/m and F(0) EE
2: repeat
3: update F with fixed 3 following Eq. (9)
Directly solving the inverse of a matrix with n² n² di- mensions is still computationally infeasible. To address this problem, we adopt the iterative approach to gradually approach the optimal solution, followed by':
4: compute {H following Eq. (4)
5: set (3e Jom with 0
6: filter the valid index set following Eq. (11)
7: update {Be) Joez with fixed F following Eq. (13)
- Σ a.
F0)) + +11 ++)"
E. (9)
++++1
until convergence or maziter
Inspired by Iscen et al. (2017), the rate of convergence can be further enhanced using the conjugate gradient method, requiring fewer iterations as shown in Algorithm 2.
Overall Optimization. As shown in the Algorithm 1, the overall optimization problem for Bidirectional Collaborative Diffusion can be solved by recursively optimizing F and B until convergence. The resulting F* can effectively capture the underlying manifold structure and is less sensitive to the construction strategy of the affinity graph.
Optimize B with Fixed F. In the situation when F is fixed, we can directly compute the objective value for each H" with Eq. (4), and we only need to optimize 3 by solving:
min
+ 2 3
11
1=1
(10)
4.2. Locality State Embedding
s.t. S B, S 1, > B =1
The obtained smooth similarity matrix F" demonstrates significant improvements in accurately capturing neighbor- hood relationships, especially in local regions. To preserve local reliability and facilitate further exploration of potential manifold structure information, the proposed Locality State Embedding (LSE) leverages this similarity matrix to map each instance into the manifold space with an n-dimensional distribution, where each dimension is coupled with a node in graph G. To effectively mitigate the negative impact of noise within neighborhoods, we employ the k-reciprocal strategy to determine local regions for weight assignment, which can be formally expressed as:
Deriving an analytical solution for this Lasso-form optimiza- tion problem is still challenging due to incquality constraints. Therefore, a general approach involves iteratively updating each 3g through coordinate descent. However, in this case, we propose more efficient strategy that allows updating all 3 values simultaneously, explicitly eliminating the need for iteration. As demonstrated in Appendix A.2, we can estab- lish an equivalent condition that identifies the valid index set where the inequality constraints are slack, as follows:
I= [u|H < ( H + x)/ZZ, 1,2,
(11)
(14) To avoid ambiguity, we use k to represent the size of the local region. For each instance, only the indices belonging to the local region are preserved and assigned the weights by utilizing the corresponding row of F followed by an 4 regularization, resulting in sparse matrix f followed by:
R k) = {11 E (ii A (i E (().))))
while other (3x) Jegz can be proved to be 0. All the (Bubeer will not violate the inequality constraint 0 S 3, < 1, such that it can be ignored for a simpler formulation. By intro- ducing a Lagrangian multiplier 77, the Lagrangian function C(3, 17) corresponds to the primal optimization problem in Eq. (10) without inequality constraints is formulated as:
P
F 5//
Σ Fi if E R(i,k)),
1(, - 3
+ + - + n11 - Bo). (12)
-EB). VEI
(15)
JER(L.))
where P= P .p....... p..
and each p; represents a state distribution for x;, sense, alongside the BCD process described in Section 4.1, the mapping process driven by LSE serves as a kernel function that transforms d-dimensionnl feature into an n n-dimensional manifold-aware state distribu- tion. Given that the close neighbors have high confidence in belonging to the same category, such that the probability dis- tributions within the local neighborhood. M/ii, (i, k2) (h2 < k))
The optimal result can then be obtained by solving the KKT conditions, with the optimal weight set {m given by:
Evez H' - -I +
IE
8
A|I V (1.2...., m///
(13)
For a comprehensive derivation, refer to Appendix A.
5

---

Locality Preserving Markovian Transition for Instance Retrieval
Table Evaluation performance on ROxf, RPar, ROxf+IM, RPr++IM Using R-GeM (Radenović et al., 2019) baseline.
Medium
Hard
Method
ROxf
ROxf+IM
RPar
RPar+IM
ROxf
ROxf+IM
RPar
RPar+ IM
R-GeM (Radenović al., 2019)
67.3
49.5
80.6
57.4
44.2
25.7
61.5
29.8
AQE (Chum et al., 2007)
72.3
56.7
82.7
61.7
48.9
30.0
65.0
35.9
oQE (Radenović et al., 2019)
69.7
53.1
86.5
65.3
40.2
DQE (Arandjelović & 7isserman, 2012)
70.3
56.7
85.9
66.9
45.9
30.8
69.9
43.2
AQEwD (Gordo al., 2017)
72.2
56.6
83.2
62.5
29.8
65.8
36.6
LAuQE (Gordo et al., 2020)
73.4
58.3
86.3
67.3
49.6
31.0
70.6
42.4
ADBA+AQE
72.9
52.4
84.3
59.6
53.5
25.9
68.1
30.4
aDBA+aQE
71.2
55.1
87.5
68.4
50.4
31.7
73.7
45.9
DDBA+DQE
69.2
52.6
85.4
66.6
50.2
29.2
70.1
42.4
ADBAWD++AQEWD
74.1
56.2
84.5
61.5
54.5
31.1
68.6
33.7
LArDBA+LAuQQ
74.0
60.0
87.8
70.5
54.1
36.3
74.1
48.3
DFS (Iscen al., 2017)
72.9
59.4
89.7
74.0
50.1
34.9
80.4
56.9
RDP (Bai et al., 2019a)
75.2
55.0
89.7
70.0
58.8
77.9
48.0
EIR (Yang et al., 2019)
74.9
61.6
89.7
73.7
52.1
36.9
79.8
56.1
RGT (Chang et al., 2019)
74.7
60.1
87.9
72.6
76.6
51.3
CAS (I.o al., 2024)
80.7
61.6
91.0
75.5
64.8
39.1
80.7
59.7
GSS (Liu al., 2019)
78.0
61.5
88.9
71.8
60.9
38.4
76.5
50.1
SSR (Shen et al., 2021)
74.2
54.6
82.5
60.0
29.3
65.6
35.0
CSA (Ouyang et al., 2021)
78,2
61.5
88.2
71.6
59.1
38.2
75.3
51.0
STML (Kim et al., 2022)
74.1
53.5
85.4
68.0
57.1
70.0
42,9
ConAff (Yu et al., 2023)
74.5
53.9
88.0
61.4
56.4
30.3
73.9
33.6
LPMT
84.7
64.8
93.0
76.1
67.8
41.4
84.1
60.1
can be aggregated to strengthen the local consistency. Ad- ditionally, if the neighbor satisfies the reciprocal condition, emphasize its importance using parameter In this case, the final neighbor-aware probability distribution p, for each v; is given by:
continuous time variable, this dynamics evolving over the graph 9 = (V, 8} represents Markov process governed by the Langevin equations, with the corresponding discretized master equation (Seifert, 2012) expressed as:
d. TT
(17)
P: Σ (R1 + 1)2) k2), (16)
where á, represents the derivative with respect time. Ad- ditionally. T, denotes the transition rate matrix, with its di- agonal components satisfying Trlr, r] E Te(s, r).
JEN().kg)
where the element 13 = j E R(i, k2). and otherwise 15 = O. The resulting probability state distributions for each instance in X' can be organized as fp, E R
Since p; and Pj may not reside within the same local region, we additionally require the long-term transition qe to follow path linking P; and Pj- This path comprises multiple tem- perate states, ensuring that each state is reachable from its predecessor only within the local region. Formally, given the set of distributions {pr the strategy systematically selects a sequence of temperate states (P;, Jk=o that satisfy local constraints. The resulting path can be expressed as {P., P........ Pix ==TT (p,),.)) Each stage q, spans time interval of T/K with q = P.. Consequently, for two given distributions p; and pj. the minimum cost of Markovian transition flow is defined by optimizing overall potential paths and transition rate matrices T, follows:
4.3. Thermodynamic Markovian Transition
Despite the ability of the obtained probability distributions to preserve local effectiveness, traditional distance metrics such as total variation fail to effectively discriminate in- stances outside the local region. To address this issue, we formulate stochastic thermodynamic process perform Markovian transition flow over the graph, where the time evolution cost can serve distance for instance retrieval. For the two distributions P., P, characterizing instances F; Fy. we present a time-dependent probability distribution q, on the graph from qo P; to q, = P, in time interval [0, 7] to represent the transition flow. With representing the
K-1
d' d'
((),s,t)dd(rss (18)
k=0
PKs
6

---

Locality Preserving Markovian Transition for Instance Retrieval
Table 2. Evaluation of the retrieval performances based global image features extracted by DOLG (Yang et al., 2021).
Table 3. Evaluation of the retrieval performances hased on global image features extracted by CVNett (Lee et al., 2022).
Easy
Medium
Hard
Easy
Medium
Hard
Method
Method
ROxf
RPar
ROxf
RPar
ROxf
RPar
ROxt
RPar
ROxf
RPar
ROxf
RPar
DOLG
93.4
95.2
81.2
90.1
62.6
79.2
CVNet
94.3
93.9
81.0
88,8
62.1
76.5
AQE
96.0
95.6
83.5
90.5
67.5
80.0
AQE
94.7
94.4
82.1
90.2
64.4
78.8
<QE
96.7
95.7
83.9
91.4
67.6
81.7
eQE
95.8
94.8
95.8
90.9
63.5
80.4
SG
97.7
95.7
85.1
91.7
70.3
82.9
SG
99.0
95.0
86.1
90.6
69.3
80.5
STML
97.6
95.4
86.0
91.5
70.8
82.3
STML
98.5
94.9
86.2
90.8
69.3
80.5
AQEwD
97.5
95.6
84.7
91.2
68.7
81.1
AQEWw)
96.2
94.9
84,0
90.8
66.4
80.0
DFS
87.3
93.6
76.1
90.8
53.5
82.4
DFS
83.5
93.5
70.8
89.8
47.4
79.6
RDP
95.7
95.0
87.2
93.0
72.0
84.8
RDP
96.9
94.5
87.8
92.4
71.5
83.3
CAS
96.8
95.7
89.5
93.6
76.7
86.7
CAS
97.6
95.0
87.6
92.8
72.7
84.8
GSS
98.0
95.3
86.9
90.6
72.9
81.2
GSS
99.0
94.0
87.6
87.1
70.4
76.9
ConAff
93.0
84.6
66.7
79.9
ConAff'
98.3
92.4
87.5
90.2
70.3
77.7
LPMT
99.7
95.9
91.4
95.3
78.2
89.8
LPMT
99.5
95.9
90.2
94.5
75.2
88.0
Table 4. Evaluation of unsupervised content- based image retrieval.
5. Experiment
Method
CUB200
Indoor
Caltech101
5.1. Experiment Setup
mAP
R@1
mAP
R@ 1
mAP
R@1
Baseline
27.9
55.8
51.8
79.0
77.9
92.3
Datasets. To demonstrate the effectiveness of the proposed Locality Preserving Markovian Transition (LPMT) method, we conduct experiments on the revised (Radenović et al., 2018) Oxford5k (ROxf) (Philbin et al., 2007) and Paris6k (RPar) (Philbin et al., 2008) datasets, respectively. To fur- ther evaluate performance at scale, an extra collection of one million distractor images is incorporated, forming the large-scale ROxf+IM and RPar+ I M datasets. Additionally, following the split strategy of Hu et al. (2020), we perform unsupervised content- based image retrieval on datasets like CUB200 (Wah al., 201 1). Indoor (Quattoni & Torralba, 2009), and Caltech101 (Fei-Fei et al., 2004) to identify im- ages belonging to the same classes.
AQE
35.9
62.5
78.1
85.5
91.8
aQE
35.9
$4.8
62.4
79.1
85,7
92.5
STMI.
34.1
58.4
58.6
80.5
83.2
93.4
AQEwD
36.4
62.4
86.8
92.8
DFS
34.1
56.0
59.3
79.2
83.4
92.6
RDP
39.6
59.3
63.9
80.9
85.9
93.1
CAS
41.9
60.9
86.8
93.3
ConAlT
40.7
57.3
64.2
79.4
86.8
93.0
LPMT
42.1
39.7
64.9
81.0
87.3
93.6
where J (r, 8, t) denotes the transition current from v, to 6s with the cost d(r; 8) in Eq. (1) at time 1, obtained by:
J(r s) Tr s) [ T.(s, [r).
(19)
Note that at each stage, the master equation Eq. (17) of the time derivative of the flow should be satisfied. Furthermore, to facilitate a finer analysis of the transition cost, an addi- tional power term can be applied to the distance in Eq. (18), yielding better empirical performance. Theoretically, as shown in Appendix B, in the case of microscopically re- versible dynamics, the minimum flow cost is fundamentally related to the entropy production during the transition. More- over, the time variation problem is still hard to be directly solved; therefore, under the assumption that each transition only takes place in local regions, the Wasserstein distance Wi can serve as a valid equivalency, followed by:
Evaluation Metries. As the primary evaluation metric, we adopt the mean Average Precision (mAP) to assess the re- trieval performance. For classical instance retrieval tasks, the image database further divided into Easy (E), Medium (M), and Hard (H) categories based on difficulty levels. Given that the positive samples are limited in unsupervised content-based retrieval tasks, Recall @ (R @ 1) is also re- ported to quantify the accuracy of the first retrieved image.
Implementation Details. We employ the advanced deep retrieval models, including R-GeM (Radenović et al., 2019), MAC/R-MAC (Tolias et al., 2016), DELG (Cao al., 2020), DOLG (Yang et al., 2021), CVNet (Lee al., 2022), and SENet (Lee al., 2023), to extract global image features for instance retrieval. The Fuclidean distance between features is the baseline measure, while refined retrieval performance is evaluated using various re-ranking methods. For unsu- pervised retrieval tasks aimed at identifying similar classes, we follow Hu et al. (2020) by extracting image features using the same pretrained backbone and applying the same pooling strategy to evaluate retrieval performance.
K-1 d' d((i,)) min Σ Wi(p:. P
(20)
To maintain the important information in Euclidean space and enhance robustness, the final distance d' (i.j) is ob- tained by introducing a balance weight 0 to integrate d' (i and dii, j), as follows:
d' (i,j) Od(i.)) + O)d'(i.)
(21)
7

---

Locality Preserving Markovian Transition for Instance Retrieval
woochinnonn 14
Table 5. Ablations of LSE.
183
61
ROdiM)
ROxE.)
Mihhod
R-GiM
DJLG
CVNet
R.G:M
DOLG
CVNet
Baseline
67.3
81.2
$1.0
44.2
02.6
62.1
5
25000006
10
15
20
35
Incrations
Cosiness-an
Goussinn--an
75.8
88.8
86.1
88.7
96.4
54.9
58.0
75.5
70.4
09.5
(6) compuoiiso BSD
(t) axm.aggeeeaaaallliii
BSD+k-on
81.6
90.1
59.5
63.0
76,9
74.9
BCD+k-no
84.2
91.3
90.1
66.1
78.1
75.2
Figure 4. Ablations of BCD. (a) Performance comparison with
Cosinesk-szcip
50.6
57.5
61.3
73.7
Gouscinns--rceip
81.9
80.5
88.8
63.1
75.8
73.1
BSD. (b) Convergence analysis of BCD towards the target matrix.
BSD+k-nccip
83.6
90.3
89.5
65.2
77.2
73.8
BCD+k-recip
84.7
91.4
90.2
67.5
78.2
75.2
5.2. Main Results
Table 6. Ablations of TMT.
ROd(M
ROsf(H
Comparison of Instance Retrieval. As summarized in Ta- ble 1, we evaluate our proposed LPMT against wide range of re-ranking approaches. including query expansion methods (AQE, OQF, DQE, AQEwD) w/ and w/o database augmentation (DBA), diffusion- based methods (DFS, RDP, EIR, EGT, CAS), context-based methods (STML, ConAff), and learning-bayee based methods (GSS, SSR, CSA, LAnQE), based on the global image features extracted by R-GeM. Notably, under the medium and hard evaluation protocols on ROxf, LPMT improves mAP by 4.0% and 3.0% compared to the top-performing CAS, respectively. Additional results in Table 2 and Table 3 further show that LPMT consis- tently delivers superior performance across various retrieval models and settings. Even with high initial performance, our method can still bring further improvements, e.g., from 93,4% htt///...%/6.666... to 99.7% (t6/91.4%/78.22 on ROxf with DOLG. More comparison results based MAC/R-MAC, DELG, and SENet are shown in Appendix C; the significant improvement in performance highlights its effectiveness and robustness.
Method
R-G
DOLG
CVNet
R.GeM
DOLG
CVNet
Baseline
67.3
81.2
81.0
44.2
62.6
62.1
Cosine
78.0
86,9
85.3
60.0
72.7
69.3
Euclickan
78.5
87.3
85.6
60.7
73.2
69.5
Inccard
78.8
87.4
X5.9
60.5
74.1
70.6
Total Viriation
79.5
87.8
86.4
61.7
74.5
71.1
TMT
84.7
91.4
90.2
67.8
78.2
75.2
particularly under challenging scenarios. For example, per- formance improves from 83.6% to 84.7% in ROxf(M) and 65.2 65.2% to 67.8% in ROxf(H) when k = 10. These improve- ments underscore the effectiveness of BCD in mitigating the negative impact of inappropriate connections by synthe- sizing information from different graphs. Furthermore, in our implementation of BCD, we perform the updating strat- egy of Eq. (9) for three iterations, followed by a refreshing of the weight set / in each cycle. As shown in Fig. 4(b), the residue norm of the target similarity matrix decreases rapidly within a few iterations, demonstrating its efficiency.
Effectiveness of Locality State Embedding. As depicted in Section 4.2, the proposed LSE aims to encode each instance into manifold- distribution using the obtained BCD similarity matrix and k-reciprocal strategy. To validate its effectiveness, we conduct experiments to test various com- binations of Cosine (Bai & Bai, 2016), Gaussian kernel, BSD (Luo et al., 2024), and our BCD similarity, along with the embedding strategies based on k-nn and k-recipreal. Table 5 reveals that LSE (BCD+k-recip)) consistently outper- forms other methods across diverse deep retrieval models, particularly under the hard protocol. Notably, with the same k-reciprocal strategy, LSE surpasses Cosine, Gaussian, and BSD by 6.5% 7%662 on R-GeM ROxf(H), highlighting its superiority in exploiting manifold information.
Comparison of Unsupervised Content-based Image Re- trieval. Compared with classical instance retrieval tasks on landmark datasets, the primary challenge of this task is to find images from datasets with smaller inter-class and larger intra-class variances. Accurately identifying similar contextual neighbors is also essential for self-supervised and unsupervised learning. As shown in Table 4, LPMT achieves the mAP of 42.1% 9144499%//773% on CUB200, In- door, and Caltech 101, respectively, proving its effectiveness and potential for diverse machine learning applications.
5.3. Ablation Study
Effectiveness of Bidirectional Collaborative Diffusion. Bidi- rectional Collaborative Diffusion (BCD) proposed au- tomatically integrate the diffusion processes on graphs con- structed with different strategies. For referenced nearest neighbor graph parameterized by k. we extend it into graph set by scaling i with factors [1/v2, 1, v2) (rounded to the nearest integer) to adjust edge connectivity levels. The ablation study in Fig. 4(a) reveals that BCD delivers consis- tent improvements over Bidirectional Similarity Diffusion,
Effectiveness of Thermodynamic Markovian Transition. As discussed in Section 4.3, the minimum transition flow cost between distinct distributions is effective distance mea- sure for instance retrieval. To verify this, we benchmark it against common metrics such as Cosine, Euclidean, Jac- card, and Total Variation distance, with results detailed in Table 6. Under the ROxf(M) and ROxf(H) protocols, LPMT achieves superior performance, surpassing other metrics by
8

---

Locality Preserving Markovian Transition for Instance Retrieval
to fuse the original Euclidean distance with the thermody- namic transition flow cost. Fig. 5(d) reveals that 0 0.5 yields the optimal result, demonstrating that incorporating the original distance enhances the retrieval robustness. Ad- ditional analyses of hyyper-parameted such as and a are provided Fig. 5(c) and (f), confirming the robustness of our approach towards their variations.
EE oo 903 Go
31
40
66
110
120
(a) effect
effect
6. Conclusion
MA 033
To address the problem of decaying positive information and the influence of disconnections during the diffusion pro- cess, we propose a novel Locality Preserving Markovian Transition (LPMT) framework for instance retrieval. LPMT embeds each instance into a probability distribution within the data manifold and then derives a long-term stochastic thermodynamie transition process to transport the distribu- tions along the graph, with each stage constrained within a local region. The minimum transition flow cost can main- tain the local effectiveness while capturing the underlying manifold structure, serving as an effective distance measure. Extensive evaluations on several benchmarks validate the consistently superior performance of LPMT, indicating its effectiveness for instance retrieval and potential to adapt various unsupervised machine learning models.
2: 12
00 01 02 05 06 25
effectol
H4
ap 09 de
100 021
61 03
05 05 09
05 on on
(e) effect of
effect of
Figure 5. Scnsitivity analysis of parammersssserss based on image features extracted by R-GeM. (a) Effect of k1. (b) Effect of k2. (c) Effect of k. (d) Effect of 0. (e) Effect of μ. (1) Effect of a.
% based on R-GeM. This suggests that the time evolution process can effectively capture the underlying manifold structure, benefiting the overall global retrieval performance.
and
Acknowledgements
Time Complexity Analysis. LPMT consists of three core components: BCD, LSE, and TMT, with the computational cost primarily driven by BCD and TMT. Specifically, BCD optimizes for the robust similarity matrix via a two-step iterative approach following Algorithm 1, which has a time complexity of O O(n"). As for TMT, we introduce an entropy regularization term in Appendíx B, resulting in a fixed-point iterative solution with Onz²) complexity. Consequently, the overall complexity of LPMT is On²)). To improve ef- ficiency in practical scenarios, we re-rank only the top-k images, reducing the complexity to (lk*), and the execu- tion time remains under 3 seconds when A = 5000.
This work was supported by the National Science and Tech- nology Major Project (2021ZD01 12202), the National Nat- ural Science Foundation of China (62376268, 62476199, 62202331, U23A20387, 62036012, U21B2044).
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Effect of kj and lig The hyper-parameters k and by intro- duced in LSE determine the size of the local region and the number of confident neighborhoods. As shown in Fig, 5(a), retrieval performance peaks at k1 = 60, suggesting that selecting a moderate region size is crucial to incorporate sufficient informative instances. Similarly, Fig. 5(b) shows that 4 = 7 yields optimal performance, highlighting the im- portance of balancing neighborhood size and the proportion of correct samples for improved representation.
References
Arandjelovié, R. and Zisserman, A. Three things everyone should know improve object retrieval. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012.
Asai, A., Wu, Z. Wang, Y., Sil, A., and Hajishirzi, H. Self- RAG: Learning to retrieve, generate, and critique through self-reffection. In The Twelfth International Conference on Learning Representations, 2024.
Sensitivity of Hysper-parmmters. In Eq. (16), the reciprocal neighbors enhance the LSE distribution, controlled by a k. As illustrated in Fig. 5(c), performance increases with x and reaches its maximum at Æ = 2. Mean- while, the hyper- parameerr 0 serves as a balancing weight
Bai, S. and Bai, X. Sparse contextual activation for effi- cient visual re-ranking. IEEE Transactions on Image Processing, 1056-1001- 2016.

---

Locality Preserving Markovian Transition for Instance Retrieval
Bai, S., Bai, X., Tian, Q. and Latecki, L. J. Regularized diffusion process for visual retrieval. In Proceedings of the AAAI Conference on Artificial Intelligence, 2017a.
Cui, X., Qin, Y., Gao, Y., Zhang, E., Xu, Z.,, Wu, T., Li, K., Sun, X., Zhou, w., and Li, H. Sinkd: Sinkhorn distance minimization for knowledge distillation. IEEE Transactions on Neural Networks and Learning Systems, 2024a.
Bai, S., Zhou, Z.,, Wang. J., Bai, X., Latecki, I.. J., and Tian,
Q. Ensemble diffusion for retrieval. In Proceedings of
the IEEE International Conference on Computer Vision 2017b.
Cui, X., Qin, Y., Gao, Y., Zhang, E., Xu, Z., Wu, T., Li, K., Sun, X., Zhou, W., and Li, H. Sinkhorn distance mini- mization for knowledge distillation. In LREC-COLING, pp. 14846-14858, 2024b.
Bai, S., Bai, X., Tian, Q. and Latecki, L. J. Regularized dif- fusion process on bidirectional context for object retrieval. IEEE Transactions Pattern Analysis and Machine In- telligence, 41(5):1213-1235 2019a.
Cui, X., Qin, Y., Xie, I.., Zhou, W., Li, H.,, and Li, H. Opti- cal: Leveraging optimal transport for contribution alloca- tion in dataset distillation. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2025a.
Bai, S., Tang, P., Torr, P. H., and Latecki, L.. J. Re- ranking via metric fusion for object retrieval and per- son re-identification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019b.
Cui, X., Sun, Q. Wang, M., Li, L.,, Zhou, W., and Li, H. Lay- outene: Leveraging enhanced layout representations for transformer-basee complex scene synthesis. ACM Trans- actions Multimedia Computing. Communications and Applications, 2025b.
Bai, S.. Zhou, Z., Wang. J., Bai, X., Latecki, L. J., and Tian, Q. Automatic ensemble diffusion for 3d shape and image retrieval. IEEE Transactions on Image Processing. 28(1): 88-101, 2019c.
Cui, X., Zhu, M., Qin, Y., Xie, L., Zhou, W., and Li, H. Multi-level optimal transport for universal cross-tokendnn knowledge distillation on language models. Proceedings of the AAAI Conference on Artificial Intelligence, 2025c.
Barato, A. C. and Seifert, U. Thermodynamic uncertainty relation for biomolecular processes. Phys. Rev. Lett., 114: 158101, Apr 2015.
Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, 2013.
Borgeaud, S., Mensch, A., Hoffmann, J., Cai, T., Rutherford,
E., Millican, K., Van Den Driessche, G. B., Lespiau, J.- B., Damoc, B., Clark, A., De Las Casas, D., Guy. A., Menick, J., Ring, R., Hennigan, T., Huang, S., Maggiore, L., Jones, C., Cassirer, A., Brock, A., Paganini, M., Irving, G., Vinyals. O., Osindero, S., Simonyan, K., Rae, J., Elsen, E., and Sifre, L. Improving language models by retrieving from trillions of tokens. In Proceedings of the 39th International Conference on Machine Learning.
Cuturi, M. and Doucet, A. Fast computation of wasserstein barycenters. In Xing, E. P. and Jebara, T. (eds.), Proceed- ings of the 31st International Conference on Machine Learning, Proceedings of Machine Learning Research, pp. 685-693. PMLR, 2014.
Devlin, J., Chang. M.-W., Lee, K., and Toutanova, K. BERT: Pre- traitraining of deep bidirectional transformers for lan- guage understanding. In Proceedings of the 2019 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, Volume I (Long and Short Papers), 2019.
PMLR, 2022.
Cao, B., Araujo, A., and Sim, J. Unifying deep local and global features for image search. In European Conference Computer Vision (ECCV), 2020.
Chang, C., Yu, G., Liu, C., and Volkovs, M. Explore-exploit graph traversal for image retrieval. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Donoser, M. and Bischof, H. Diffusion processes for re- trieval revisited. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013.
Chen, J., Lin, H., Han, X., and Sun, L. Benchmarking large language models in retrieval-augmennté generation. Proceedings of the AAAI Conference on Artificial Intelli- gence, 2024.
Evans, J. Cohen, E. G. D., and Morriss, G. P. Probability of second law violations in shearing steady states. Phys. Rev. Lett., 71:2401-2404, Oct 1993.
Chum, O., Philbin, J., Sivic, J., Isard, M., and Zisserman, A. Total recall: Automatic query expansion with a generative feature model for object retrieval. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2007.
Fei-Fei, L.., Fergus, R., and Perona, P. Learning generative visual models from few training examples: An incremen- tal bayesian approach tested on 101 object categories. In IEEE Conference on Computer Vision and Pattern Recognition Workshop, pp. 178-178. IEFE, 2004.
10

---

Locality Preserving Markovian Transition for Instance Retrieval
Gasteiger, J., Bojchevski, A., and Günnemann, S. Predict then propagate: Graph neural networks meet personal- ized pagerank. In International Conference on Learning Representations (ICLR), 2018.
Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
Lee, S., Lee. S., Scong, H., and Kim, E. Revisiting self- similarity: Structural embedding for image retrieval. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2023.
Gordo, A., Almazan, J., Revaud, J., and Larlus, D. End- to-end learning of deep visual representations for image retrieval. International Journal of Computer Vision, 124 (2):237-254, 2017.
Li, J., Selvaraju, R., Gotmare, A., Joty, S., Xiong, C., and Hoi, S. C. H. Align before fuse: Vision and language rep- resentation learning with momentum distillation. In Ad- vances in Neural Information Processing Systems, 2021.
Gordo, A., Radenovic, F., and Berg. T. Attention- query expansion learning. In European Conference on Computer Vision (ECCV), 2020.
Li, J., Li, D., Xiong, C., and Hoi, S. BLIP: Bootstrapping language-iman image pre-training for unified vision-language understanding and generation. Proceedings of the 39th International Conference on Machine Learning. PMLR, 2022.
Hu, B., Song, R.-.,, Wei, X.-S., Yao, Y., Hua, X.-S., and Liu, Y. Pyretri: A pytorch-based library for unsupervised image retrieval by deep convolutional neural networks. In Proceedings of ACM International Conference on Mul- timedia, pp. 4461 146414444222 2020.
Li, J., Li, D., Savarese, S., and Hoi, S. BLIP-2: Boot- strapping language-image pre-training with frozen image encoders and large language models. In Proceedings of the 40th International Conference on Machine Learning. PMLR, 2023.
Iscen, A., Tolias, G., Avrithis, Y., Furon, T., and Chum, O. Efficient diffusion on region manifolds: Recovering small objects with compact enn representations. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2017.
Liao, C., Tsiligkaridis, T., and Kulis, B. Supervised met- rie learning to rank for retrieval via contextual similarity optimization. In Proceedings of the 40th International Conference on Machine Leurning, Proceedings of Ma- chine Learning Research. PMIR, 2023.
Iscen, A., Avrithis, Y., Tolias, G., Furon, T., and Chum, O. Fast spectral ranking for similarity search. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2018
Ito, S. Stochastic thermodynamic interpretation of informa- tion geometry. Phys. Rev. Lett., 121:030605, Jul 2018. Jia, C., Yang, Y., Xia, Y., Chen, Y.TT., Parekh, Z., Pham, H., Le, Q. Sung, Y.-H., Li, Z., and Duerig. T. Scaling up visual and vision-language representation learning with noisy text supervision. In Proceedings of the 38th International Conference on Machine Learning. PMLR, 2021.
Liu, C., Yu, G., Volkovs, M., Chang. C., Rai, H., Ma, J., and Gorti, S. K. Guided similarity separation for image retrieval. In Advances in Neural Information Processing Systems, 2019.
Liu, H., Li, C., Wu, Q., and Lee, Y. Visual instruction tuning. In Advances in Neural Information Processing Systems, 2023.
Lowe, D. G. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60: 91 91-110, 2004.
Jégou, H., Harzallah, H., and Schmid, C. contextual dis- similarity measure for accurate and efficient image search. In Proceedings of the IEEE Conference on Computer Vi- sion and Pattern Recognition (CVPR), 2007.
Luo, J., Yao, H., and Xu, C. Cluster-aware similarity dif- fusion for instance retrieval. In Proceedings of the 41st International Conference on Machine Learning. PMI.R, 2024.
Jégou, H., Perronnin, F., Douze, M., Sánchez, J., Pérez, P., and Schmid, C. Aggregating local image descriptors into compact codes. IEEE Transactions on Patlern Analysis and Machine Intelligence, 3409):1004-1716, 2012.
Noh, H., Araujo, A., Sim, J., Weyand, T., and Han, B. Large- scale image retrieval with attentive deep local features. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2017.
Kim, S., Kim, D., Cho, M., and Kwak, S. Self-taught metric learning without labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
Ouyang, J., Wu, H., Wang, M., Zhou, W., and Li, H. Contex- tual similarity aggregation with self-attention for visual re-ram re-ranking. In Advances in Neural Information Process- ing Systems, 2021.
Lee, S., Seong, H., Lee, S., and Kim, E. Correlation verifica- tion for image retrieval. In Proceedings of the IEEF/CVF

---

Locality Preserving Markovian Transition for Instance Retrieval
Philbin, J., Chum, O., Isard, M., Sivie, J., and Zisserman, A. Object retrieval with large vocabularies and fast spatial matching. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2007.
Shen, X., Xiao, Y., Hu, S. X., Sbai, O., and Aubry, M. Re-ranking for image retrieval and transductive few-shot classification. In Advances in Neural Information Pro- cessing Systems, 2021.
Philbin, J., Chum, O., Isard, M., Sivic, J., and Zisserman, A. Lost in quantization: Improving particular object retrieval in large scale image databases. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2008.
Su, H., Yen, H., Xia, M., Shi, W., Muennighoff, N., yu Wang, H., Haisu, I.,, Shi, Q. Siegel, Z. S., Tang, M.. Sun, R., Yoon, J., Arik, S. O., Chen, D., and Yu, T. BRIGHT: A realistic and challenging benchmark for reasoning
iassoning-intensieee intensive retrieval. In The Thirteenth Interna- tional Conference on Learning Representations, 2025.
Prokopehik, K., Benson, A. R., and Tudisco, F. Nonlinear feature diffusion on hypergraphs. In Proceedings of the International Conference on Machine Learning. PMLR, 2022.
Thakur, N., Reimers, N., Rücklé A., Srivastava, A., and Gurevych, I. BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Thirty-fifth Conference on Neural Information Process- ing Systems Dalasets and Benchmarks Track (Round 2), 2021.
Quattoni, A. and Torralba, A. Recognizing indoor scenes. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 413-420. IEEE, 2009.
Tolias, G., Sicre, R., and Jégou, H. Particular object re- trieval with integral max-pooling of enn activations. In International Conference on Learning Representations (ICLR), 2016.
Radenović, F., Iscen, A., Tolias, G., Avrithis, Y., and Chum, O. Revisiting oxford and paris: Large-scale image trieval benchmarking. In Proceedings of the IEEE Con- ference on Computer Vision and Pattern Recognition (CVPR), 2018
Van Vu, T. and Saito, K. Thermodynamic unification of optimal transport: Thermodynamic uncertainty relation, minimum dissipation, and thermodynamic speed limits. Phys. Rev. X, 13:01 1013, Feb 2023.
Radenović, F., Tolias, G., and Chum, O. Fine-tuning cnn image retrieval with no human annotation. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, (7):1655-1668, 2019.
Wah, C., Branson, S., Welinder, P., Perona, P., and Belongie, S. The caltech-uesd birds-200-2011 dataset, 2011.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J.. Krueger, G., and Sutskever, I. Learning transferable visual models from natural language supervision. In Proceedings of the International Conference on Machine Learning. PMLR, 2021.
Xiao, S., Liu, Z., Zhang, P., and Muennighoff, N. C-pack: Packaged resources to advance general chinese embed- ding, 2023.
Yang. F., Hinami, R., Matsui, Y., Ly, S., and Satoh, S. Effi- cient image retrieval via decoupling diffusion into online and offline processing. In Proceedings of the AAAI Con- ference on Artificial Intelligence, 2019.
Sarfraz, M. S., Schumann, A., Eberle, A., and Stiefel- hagen, R. A pose-sensitive embedding for person re-identification with expanded cross neighborhood re- ranking. In Proceedings of the IEEE Conference Com- puter Vision and Pattern Recognition (CVPR), 2018
Yang, M., He, D., Fan, M., Shi, B., Xue, X., Li, F., Ding, E., and Huang, J. Dolg: Single-stage image retrieval with deep orthogonal fusion of local and global features. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2021.
Seifert, U. Stochastic thermodynamics, fluctuation theorems and molecular machines. Reports on Progress in Physics, 126001, nov 2012.
Shao, S., Chen, K., Karpur, A., Cui, Q., Araujo, A., and Cao, B. Global features are all you need for image retrieval and reranking. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2023.
Yang, X., Koknar--Tzzel, S., and Latecki, I. J. Locally con- strained diffusion process on locally densified distance spaces with applications to shape retrieval. In Proceed- ings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
Shen, X., Lin, Z., Brandt, J., Avidan, S., and Wu, Y. Ob- ject retrieval and localization with constaly similarity measure and k-nn re-ranking. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012.
Yang, X., Prasad, L., and Latecki, L. J. Affinity learning with diffusion on tensor product graph. JEEE Transac- tions on Pattern Analysis and Machine Intelligence. 35 (1):28-33 -38, 2013.
12

---

Locality Preserving Markovian Transition for Instance Retrieval
Yao, L., Huang, R.,, Hou, L.,, Lu, G., Niu, M., Xu, H., Liang, X., Li, Z.,, Jiang, X., and Xu, C. FILIP: Fine-grained interactive language-image pre-training. In International Conference on Learning Representations, 2022.
Yu, C., Shi, Y., and Wang, J. Contextually affinitive neigh- borhood refinery for deep clustering. In Advances in Neural Information Processing Systems, 2023.
Zhang, S., Yang, M., Cour, T., Yu, K., and Metaxas, D. N. Query specific rank fusion for image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelli- gence, 87 2015.
Zhang, X., Jiang, M., Zheng, Z., Tan, X., Ding, E., and Yang. Y. Understanding image retrieval re-ranking: A graph neural network perspective. arXiv preprint arXiv:2012.07620, 2020.
Zhang. Y., Qian, Q. Wang, H., Liu, C., Chen, W., and Wan, Graph convolution based efficient re-ranking for visual retrieval. IEEE Transactions on Multimedia, 2023.
Zhong, 7.,, Zheng, I.., Cao, D., and Li, S. Re-ranking person re-identification with k-reciprocal encoding. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Zhou, D., Weston, J., Gretton, A., Bousquet, O., and Schölkopf, B. Ranking on data manifolds. In Advances in Neural Information Processing Systems, 2003.
Zhou, Y., Bai, X., Liu, W., and Latecki, L. Fusion with diffusion for robust visual tracking. In Advances in Neural Information Processing Systems, 2012.
13

---

Locality Preserving Markovian Transition for Instance Retrieval
A. Bidirectional Collaborative Diffusion
Given a reference affinity graph with its adjacency matrix denoted by W, we can extend into graph set with the corresponding adjacency matrices {W") J== by adding and removing some connections. Inspired by prior work (Zhou et al., 2012; Bai et al., 2019;;b;e), aim to integrate the Bidirectional Similarity Diffusion (Luo et al., 2024) process across these individual graphs automatically generate robust similarity matrix. Such that the resulting matrix can not only effectively capture the underlying manifold structure, but also mitigate the negative impact caused by suboptimal graph construction strategies. To this end, we associate each adjacency matrix W with learnable aggregation weight 8 collectively forming the weight set {Be 1 Additionally, we impose a normalization constraint such that the summation of 3, equal to I, ie., Ex=1 Bo = Under this framework, our proposed Bidirectional Collaborative Diffusion can then be formally expressed as:
min F,8
Σ
B +
1111112
2
(A.1)
m
s.t.
0 Bo S 1,
Σ
3, 1,
where H" denotes the Bidirectional Similarity Diffusion process (Luo et al., 2024) with its objective function follows as:
H
Σ M
n
W
FRi
FRj
2
W
Fik
jk
+ + F E
(A.2)
D
DD
D
D
For each adjacency matrix W D the corresponding diagonal matrix with its i-th diagonal element equal to the summation of the i-th row in W The regularization term is weighted by a positive constant 14 > 0, and E is a positive semi-definite matrix introduced to prevent F from being extremely smooth. Given that the regularization term is shared across all H we can factor out derive an equivalent optimization problem, thereby simplifying the subsequent analysis:
m
Σ R + A|| F -P- 1
min F.8
(A.3)
0 B.
3 =1,
where
F is D
Fkj
Fix
Fj
W
(A.4)
VD.
DD
VD
1,j=
The above optimization problem involves both & and F, making it inherently complex and impractical to solve directly. To resolve this, we propose a numerical approach that decomposes the objective function into two subproblems, allowing for a systematic iterative approximation of the optimal result by recursively optimizing and 3. In the following, we first describe the update of F with fixed 3 in Section A. followed by the update of 3 with fixed F in Section A.2. Finally, in Section A.3, we introduce fixed- fixed-point iteration scheme to progressively approach the optimal solution.
A.1. Optimize F with Fixed B
In the case when {Bo) ) are fixed, such that the constraint of || can be omitted when finding the optimal value of F. bring Eq. (A.4) into the target function, the optimization problem be rewritten into:
min ΣΣΣ 8 =1
m
W
F Rs
F
2
W
Fi
F
)*)
+ +
E
(A.5)
D
D
D
D
14

---

Locality Preserving Markovian Transition for Instance Retrieval
The natrix-based formulation is still difficult to deal with. In the following, will first reformulate it into vectorized form simplify the derivation of the closed-form solution, and then demonstrate that the optimal solution can be iteratively approximated with reduced computational cost.
Vectorized Formulation. To facilitate the vectorized transformation, we first introduce an identity matrix I into Eq. (A.4),
such that Hº can be rewritten into:
FRi VDR
Fij VDJs
+ HLWW (
Fik F VDR VD
)
H
W Wiy
(A.6)
R.I=
1,j=1
Afterwards, we introduce the vectorization operator vec(-), which can stack the columns in a matrix one after another to formulate a single column vector, and the Kronecker product @. which combines two matrices to produce a new one. By taking advantage of these two transformations, we proceed define the Kronecker product Wo(1) W @ I, De(1)= D" for the former part, and ()((2
& W", D=(22 I D" for the latter part. The corresponding items between the original and Kronecker formation are associated with the newly defined corner markers p n(i 1) k, n2l 1) + j. In addition, define the normalized matrix of w as S" = (D")) 122"--12W"' (D") 1/2, / go(1) = S" @ I and (2) = I @ S The following facts can be easily established:
q n(j 1) + I, r n(k- 1) + i, and
1. beo(F); Fii and vec( F)g Fij; (ec(F), Fik and vec( (F), F(y--
2. wrll) W kt, Dop D% and D2( Djj Wi! Iui W ij. D D and D D'j
3. Egen pq = Dip and Eper WH( = -D E W = Dit and E wi! = D
4. gu(1) =
and S²(2)
(DO(2))
By substituting the above transformations into Eq. (A.6), the representation of H can be equivalently reformulated in the Kronecker product form as follows:
n
Woll) vec(F)) P
vec
2
Wor()
Dec( DEc(F),
vec( 1ec(F)s)
p-q=1
Deg
1,3=1
V VIDIFa)
()(2))
=Fec(F) (1-
T(I
2 (1/2)))11122111111111
1
2 (D 1110))111230000 (122))))))()) (//)oc(FFF)))
(De(2))
(A.7)
=vec( (F) (1- gu(1)
1 2
(ec()))
Basically, the Frobenius norm of F E within the regularization term is equivalent the Lg-norm of vec( (F E), combine the Kronecker matrix based HD and the regularization term together, the objective function Eq. (A.5) can be rewritten into:
min F
B.
min
EB F)T ( F
m
1 (0()) - 1 - vee) (eeo(F)))))))) F) + u ullleec F -
(A.8)
Lemma A.1. Let A E Raxx, the spectral radius of A is denoted as p(A) = max([>|, E (AA),, where (AA the spectrum of A that represents the set of all the eigenvalues. Let || || be a matrix norm on Raxa, given square matrix A Raxn, X is arbitrary eigenvalue of A, then we have [>| ((A) S ||A|]]
Lemma A.2. Let A E Bgxxm B E Ruxn denote {hi, am and (ui, y as the eigen-pairs of A and B respectively.
The set of mn eigen-pairs of A & B is given by:
Daag, aq @ y yyJi=i,..... J= j=1....-
Closed-form Solution. Suppose the objective function in Eq. (A.8) that needs to be minimized is J. To prove that J is convex, it is equivalent to show that its Hessian matrix is positive. To get started, we first consider the matrix (D")-' W whose induced lsc norm is equal to 1, i.e., [I(D") W' = 1, since the i-th diagonal element in matrix D equal to the summation of the corresponding i-th row in matrix n Lemma A.I gives that p((D)) S As for the
15

---

Locality Preserving Markovian Transition for Instance Retrieval
matrix S" =
we concerned about, since can rewrite it (D"'"""""--
thus it is similar to ( ie.. 5 (D")-IW* This implies that the two matrices share the eigenvalues, such that p(S)) < 1. By applying Lemma A.2, we can conclude that both the spectral radius of the Kronecker product (0(1) = 5 @ I and g²(2) = -I ② 5" is no larger than 1, L.e., (1) S 1, ((8)(2)) 1
W
The Hessian matrix of Eq. (A.8) can be obtained as 2( + 1)T E. (. + S-(2), where (5 = go(1) + (S)(1) T
and 28x(2) = (-(2) + (ST Given that μ > 0, >nmm 3, = 1, and each p(S") S 1, such that the eigenvalues are greater than 0, indicating that the Hessian matrix is positive-definit and the objective function J is convex. Consequently, we can take the partial derivative of vec( F) to obtain the optimal result of Eq. (A.8), followed by:
M Σ
veee(F) J
- (-(1) - (e))) F) + 21((ve( F - E)).
(A.9)
The optimal solution F" is found by setting the above partial derivative zero, yielding:
2p
B
B 5u(z)) Dec(E).
Fec(F")= =
21
(e(
(A.10)
1
To get simpler representation, we substitute ag with in the closed-form solution of the optimal F* when {3p) am are fixed, which be expressed
8. S" with ($r(1) + (u(2)) //2, and denote a 2v=1 Czz resulting
m
p+1
F (1 - a)vec Soaeece((I ((I
Σ aa (- vec veel vE)(
(A.11)
Lemma A.3. Let E Rmxn X E guxp and B E 12p4 respectively, then
veel AXB) (B' e A)eec(X)
Lemma A.4. Let A Raxn, then limg--oo A if and only if ((A)
Lemma A.5. Given a matrix A Rexn and ((A) 1. the Neumann series I + A+ A +... converges (I A)-
Iterative Solution. Utilizing the relationship given by Lemma A.3, we could put all the matrices in Eq. (A.9) into the vee(.) operator. Additionally, setting the derivative to O, we can obtain the following equivalent relationship:
2F
Σ
B.F - F E) =0
(A.12)
By making some small changes to the above formula, the optimum result F* is actually the solution to the following Lyapunov equation:
m a O Σ S") 2(1 o.
(A.13)
Directly solving this equation incurs significantly high time complexity, but we can approximate the optimal solution at lower cost in iterative manner. Inspired by (Zhou al., 2003; Iscen et al., 2017; Bai al., 2017a; Luo et al., 2024), can develop an iterative function to infinitely approach the optimal result as follows:
F(++1)
Σ 2 ==1
F (1 (S") + =()) + (1
(A.14)
where 5" "D"" and 5" = (S" + ((*) By applying Lemma A.3, we can add a vec(-) operator
on both left-hand and right-hand sides, reformulating the iteration process as:
vec(F((+1))
a S" @ 3II S" ((e(((()))) "ELI&S""eec(FFa
(1 a)vec(E)
(A.15)
S" vecl ((t)) + (1 ax)ec(())
16

---

Locality Preserving Markovian Transition for Instance Retrieval
Algorithm 2 Effective Solution of Eq. (A.13)
J==1 initial estimation of similarity matrix F normalized Kronecker matrix /=")== identity matrix E R xn² max number of iterations maziter, hypee--prammeter μ., X, iteration tolerance Output: F = vec (f*)
Input: Adjacency matrix set { [W"
substitute D 0r 5 with S, and Ex= Opp 2 with $
2: initialize ((u) and R
R! with 2(1 - a) E -I-
( - -F (I-a5)
3: denote f, vec F())) Ti vec vec(R R. P: vec(
4: repeat
r, r.
5: compute 2p, (I as) )::
6: refresh f S+1 = f: +a:p:
7: update T++1 =T; 20 aB)
P241
8: compute B, r.
9: refresh P++1 T141
B.P:
10: f f ++1
11: until f mariter or ||r++1l| <
Assume the iteration starts with an initial value F(0), which can be chosen as either the diagonal matrix I or the regularization matrix E. Through iteratively applying the update rule, we derive an expression in which F(++)) is explicitly formulated in terms of (0)), the normalized matrix S, and the regularization matrix without any direct dependence on the immediate previous value F(t) following:
veo(F = - (a, (1
o.S") Veec EE).
(A.16)
Since we have already proved that the spectral radius of S" is no larger than 1, by taking advantage of Lemma A.4 and A.5, we can easily demonstrate that the following two expressions hold true:
lim 1-00
aa S")' = O.
(A.17)
1=1
lim
a. Suy (1 - Σ 8")-1
(A.18)
Therefore, the iterative sequence of vec( F()) asymptotically approaches stable solution, converging to:
vec(F") (1 (1-a)(II Σ vec()))
(A.19)
By performing the inverse operator vec-1() on both side, the optimal result for Eq. (A.5) can be derived, which yields:
F = (1 avvec ((I Σ a vec(()) -
(A.20)
The above expression is identical to Eq. (A.11), which implies that the time complexity of solving the Lyapunov equation in Eq. (A.13) can be receded to O(n²), where denotes the dimension of the matrix. Inspired by Iscen et al. (2017; 2018); Luo et al. (2024), the convergence rate can be further accelerated with the conjugate gradient method. In other words, the solution to the equation can be estimated with fewer iterations following Algorithm 2. Specifically, starting from an initial estimation (()) the iteration in the Bidirectional Collaborative Diffusion process will cease when the maximum count masiter is reached or the norm of the residue is less than predefined tolerance 6.
17

---

Locality Preserving Markovian Transition for Instance Retrieval
A.2. Optimize 3 with fixed F
When F is fixed, the objective value of He for each adjacency matrix W in Eq. (A.2) can be directly computed. As result, the optimization of / reduces to solving the following problem:
1
min Σ
B,
2
(A.21)
s.t. 0 Bo 1,
3 1.
v=1
Specifically, the objective function in Eq. (A.21) takes the form of Lasso optimization problem, which can be solved by utilizing the coordinate descent method following (Bai et al., 2017b; 2019c), as demonstrated below:
0 A(8 ((++)))((0'''
2x
(A.22)
( = 5, B3 8,.
During the updating procedure, both 8; and B, should not violate the inequality constraint 0 v 8 1. To achieve this, we explicitly set 2 be zero if (3 (H) H < O, and truncate it be 5,+ + H > 2,)B)+5,) However, this strategy requires multiple iterations since only a pair of elements in {B, can be updated together. To address this issue, we propose a more efficient solution that allows updating all the 3, simultaneously, explicitly eliminating the need for iteration. By taking advantage of the coordinate descent method, we can filter out the valid elements that are not governed by the boundary constraints, formally denoting the valid index set as I. Consequently, the inequality constraints of 0 < B, < are slack to the weight set {3.)vez and the optimization problem can be directly solved. By introducing a Lagrangian multiplier 1). the Lagrangian function [(3, 17) can be formally defined as:
((3,1) = 3B, 3H + 2 111111 + nn(1 Σ Bo).
(A.23)
VEI
VEZ
The corresponding Karush-Kuhn-Tucce (KKT) conditions can then be formulated as:
V 3. [(3 AL(B.n) n)
Hº + AB, =
VEI,
03, @C(3,1) =
(A.24)
V V ((3 = On
Σ 3. =0
VEI
Note that we have already taken the equation constraint ΣWET B. into consideration when deriving the representation of B, C(3 17). The optimal result can be obtained by solving the [Z] + equations. By summing up all the B, C(3,)) along within I, the Lagrangian multiplier 7) can be obtained
Evez H +
(A.25)
[
Therefore, by taking 77 back into the KKT conditions, we can obtain the optimal solution of B., following:
B = EwEz H H + X
I.
(A.26)
A|Z
Since all the weight 3, should satisfy the inequality constraint 0 S 3, S 1, the above relationships provide an effective strategy to determine the valid index set I, i.e., the corresponding H" in I should satisfy H" < (EVEz H" + +)/l Therefore, we can develop a formalize definition of the valid index set, as follows:
I [ < < H x)/ZZ v = 1, ..2........ m)
(A.27)
J'EI
In practical implementation, we first sort all Hº in descending order and then sequentially remove the indices that fail to satisfy the constraint of Eq. (A.27), leading to the valid set I. The optimal result can be obtained in a single round of iteration, with the resulting weight set {8 Jm given by:
EvEr HV - H +
I
B
(A.28)
0, v E m1) /I.
18

---

Locality Preserving Markovian Transition for Instance Retrieval
A.3. Overall Optimization
The overall optimization problem for Bidirectional Collaborative Diffusion can be solved by recursively optimizing F and B until convergence following Section A.I and Section A.2, respectively. Additionally, by leveraging the conjugate gradient method, the iterative update of F achieves faster convergence rate, outlined in Algorithm 2. The resulting F effectively captures the underlying manifold structure while automatically reducing the adverse effects of inappropriate connections. As a result, it exhibits lower sensitivity to the affinity graph construction strategy and ensures a more robust similarity representation.
B. Thermodynamic Markovian Transition
Discrete Wasserstein Distance Given two discrete probability mass distributions Pstnt Pend R", transport problem can be formulated from Pstart moving towards Pend Define C' E IR**" as the cost matrix, where Cli.j] 2 0 represents the cost required to transport unit from the i-th position Psun [+] to the j-th position Penalj] (also denoted as edge (i.j)). The matrix Q E R quantifies the transport strategy, where Q [ indicates the amount being transported from Psmal [i] to
Pena j], subject to the following requirements:
Paturi =
Qii,].
j=1
(B.1)
Pead Lil = Σ
Qi.,j]
The Wasserstein distance is defined as the smallest cost required to transport one distribution to another, considering all possible transportation matrices:
Wi (P Pend)
min Σ
(B.2)
Indeed, the transport matrix Q' that yields the optimal solution in Eq. (B.2) represents the optimal transport between the two distributions, under the cost defined by C.
Definition of Thermodynamic Markovian Transition Cost Each instance H; in the set X is assigned probability distribution p; E IR" on X- For two distinct distributions P, and pj. we have defined their distance by introducing a thermodynamic Markovian transition between them. We first pick path {Pip P.,. Pix = π ((p with each succeeding distribution Pa+. lying within the local region of P., Then, time-dependent transition flow q, is present to go through the temporary states the path ग,, satisfying the discretized master equation of flow dynamics. More specifically, given p;, Pj and a path ,, we define the flow q, to satisfy the following conditions:
(Flow Dynamies)
d, Ti for E [0, a.e
(Temperate States)
q # Pia:
for l: 0, 1, ...., K,
(B.3)
(Boundary Conditions)
Pio = Piv q, = Pix = Pjr
where T2 is transition rate matrix satisfying the following condition:
Tel, r] ET.(s,) for 1,,,=........ 1,2....,
(B.4)
The entire transition cost C(q.) for the flow q, at time t is determined by summing the transition costs across all graph edges, and it can be divided into K stages:
K-1
(kel)r n
C(q.) = [' Σ
((.
Σ
d(r
(B.5)
PCB
where s( is the transition current from the r-th position to the s-th position at time
J(r, 8, 1) = s.(r,slg.i s]q. T-ss, [))r))
(B.6)
19

---

Locality Preserving Markovian Transition for Instance Retrieval
and the Euclidean distance in feature space d(r;s) serves as the cost of this current. The distance between p; and q; is defined by taking the minimum of ((q)) over all feasible path and transition matrix Ta:
di == min C(q.). n.T.
(B.7)
We have the following equivalency between d' (i. and L' Wasserstein distance Wi:
K-1
d' d'(i,)) min
Wi Piet))
(B.8)
B.1. Entropy Production
In this section, we will discuss the relationship between our flow transition cost and the entropy production of stochastic thermodynamics. Briefly, the probability current [r, s) bridges this relationship, inspired by the previous physically based analysis (Van Vu Saito, 2023; Seifert, 2012; Barato & Seifert, 2015; Ito, 2018).
The entropy production AS during the process consists of two components, the changes the entropy of the system and the environment,
AS ASys + AS
(B.9)
The system entropy, characterized by the Shannon entropy, can be expressed as
Skys (q0) + L. Σ (log q.lr) 1)df.
(9.) Σ
Ir] log (r]r]
(B.10)
And the change of the system entropy is
ASys = Ssys(g-) - Ssy)(90) = ['
q. (rog + 1)dt f
Σ
Telr slq. q.(r] + 1)dt.
(B.11)
r,a=1
By substrituting Te(r, r] using Eq. (B.4), the system entropy change can be further simplified:
ASgs
(T r/ [rlr] + 1)d
r,s=1
rts
(B.12)
n
qe [r] [log
-T
de.
9:
To compute the system entropy production, we should consider how the transition contributes to the entropy change in the environment. According to Van Vu & Saito (2023), assume the transition rates T; further satisfy the local detailed balance condition, in the case of microscopically reversible dynamics:
T Tel 8] T, [s, r]
log
Sr s). and (r(r,)) > 0 if and only T, (s, 0,
(B.13)
where Se(r, s] denotes the environmental entropy change due to the transition from the r-th position to the s-th position. The total environment entropy change is obtained by multiplying S, s) and the amount transferred from position to
AS
Σ r,s=1 r
Telr S,r,, s]dt
(B.14)
/ Σ
(T.r..qq..l) T((s,rla.(r) sldt.
r==1 PC
20

---

Locality Preserving Markovian Transition for Instance Retrieval
Consequently, the entropy production can be obtained:
Tr s 9 Ta ( [.(r)
AS = ASys + ASe
Σ
log
dl.
(B.15)
r,am1
Compare the expression of the entropy production Eq, (B.15) and the transition cost Eq. (B.5). Both take the form of weighted summation over the flow current s,,,,,,) s,t). For entropy production. the weighting factor corresponds the so-called thermodynamic force on the edge (r,s). s). In contrast, for our transition cost, we replace this factor with the transport cost associated with the edge (r,s).
B.2. Proof of Eq. (B.8)
For given path æ,, it suffices demonstrate that each step of the transition flow within the local region, the transition cost matches the Wasserstein distance:
min T:
d(r, = Wi(Pi, Piun))
(B.16)
where we define 4u = kr/K for simplicity. It important to note that the optimization is only concerned with the values of T' within the interval [tx. fR+1). Inspired by the physically based results in Van Vu & Saito (2023). we establish this equivalence by proving LHS2RHS and LHS&RHS.
The integral on left in Eq. (B.16) can expressed using Riemann sums. We partition the time interval [ty, tx+1] into M equal segments. Defining At (tx+1 tx)/M, the expression for the sub-interval [tx + mt,, + (m + 1) in the Riemann sum becomes:
Proof of LHS> RHS
8 & + mmD) d(r,))d((rs))) s)Lt, m = O.I, M 1.
(B.17)
r,a=1
PCB
Consider Eq. (B.17) in the context of transportation. It outlines the movement of an amount [J s, tu + mAt)| At along the edge (r, s), incurring a cost of C'r, s] = C(ss, r| d(r, s). Additionally, if the transition current is positive, this mass moves from position r to position s. Conversely, if negative, the direction is from s to r. Consequently, we can construct a matrix Q to represent the transported quantity during the interval [tx, (41]). defined as follows:
M
Qir, 8]
[J(r, 8, la + ma()) At.
m==0
(B.18)
M-1
[[s,r] = Σ
(, s, t4 + mAt)] At,
m==
where [z]+ = x if is positive, and vanishes if x negative, while [x]- = |z| [x]+ captures the negative component.
The Riemann sum SM can thus expressed using Q and C, connection with the definition of Wi:
M-1 m
SM
Σ
Σ
|rr,
mAt) 8) Σ
Qrr,s]Crr, Wilp, Pin11) RHS.
(B.19)
1= P.a=1
r,a=1
r<a
As M + oo and At 0, the Riemann sum SM approaches the integral on the left-hand side of Eq. (B.16), resulting in LHS>RHS.
Proof of LHS&RHS Given a matrix Q that optimally determines the transportation amount, solving Wi (Pi, Pi. ) our task is to formulate a valid T, for the flow g, over the interval [&,, fx+1] to also attain this value. According to the definition, every element Qir, s] indicates the total amount moved from the r-th to the s-th position. We can break down the optimal transport plan into a series of M' vertex-to- vertex transfers, each occurring over a time span At' = (fx+1 + Specifically, the transport within [te, (++] can be described follows:
21

---

Locality Preserving Markovian Transition for Instance Retrieval
Within Pk 4 + At", transport Yo from ro spi
Within [/ + AV' la + 2 transport qi from ri to 81;
Within [ts + (M' 1) la + M'A'', transport gM from TM to SM'-1
For each step m S M' 1, the transported quantity 9m must not exceed the available mass at position rk- The optimal Wasserstein distance can be expressed in terms of ym and the pairs (Tm, 8m) by summing them up:
M
qm (T sm).
(B.20)
We can now define a transition flow q: for E [tx, te+il using the decomposition approach: initialize at qr, = Pia- During m-th sub-interval [4x + mAl' tu + (m + 1)At",, the flow evolves linearly,
t L/ mAt
Le [mm]
at. tt [[m]]
Qm
Av'
4 mAt
(B.21)
qe [8m]] Quetme [9m] +
Om:
Al'
g. [r]] = Aretmar [r], for r + Tmm
The corresponding time-derivative is 9,, where all channels are zeros except at I'm and Ts+
delmml -m AV' d. [.[sm]= qm At'.
(B.22)
Hence, we can obtain the transition matrix T, derived from qe. where most entries are zero except for four specific channels: I'm, Fm) [Im, sm]. [8m: sm]. and 8m: Fm]. These channels comply with the following equations, dictated by the discrete
master equations:
T mm Tm]
T [smm mm].
T Te(sms m. 8m)
TT mm],
(B.23)
d [m]] T, Ti(rm, T'm gellagg [mm] + Tr [rlm 8m 8m. [elmmmm
qe [m]m + T felmm sm]q. [9m]. q, [9m] T, [m mm
Through straightforward calculations, it found that any T [Tm, 8m]] and T (e(mmm r'm] satisfying the following condition:
T [r/mm [s] T [sm, Im mm].mmmml = qm At
(B.24)
constitutes the solution. By introducing a parameter 0 > O, we can guarantee the existence,
0qm
(0 + 1)4m
T T [Im, 8m]
T [Sm, Fm]]
(B.25)
qr 8m AF
q, [mm At'
Now that the transition matrix T, is determined. We can compute the transition cost the interval [tx, fx+1] by decomposing the integral into the M' stages:
txt1
M
(m+)))
Σ
Σ
s, d(t)) d(r,s)dtt
(B.26)
1
m=D
At each stage, the current [r, s,t) vanishes unless it is the current on the edge (rm sm). Hence, we can simplify the integral as:
tt 1x (m+1)AA
to + 1)At'
[r 8, d(r,
[](mm, 8m, 1) d(rm 8m dt.
J
(B.27)
1=211
22

---

Locality Preserving Markovian Transition for Instance Retrieval
Substitute the results in Eq. (B.24) into the definition of J to obtain that
J ('m Sm: t)1 [T [T 9m qt [sm] Telsm
T (mlq = 9m
At At'.
(B.28)
This results in the simplification of transition cost as:
Te41
M''1
Qm Σ L
2/ (m++)ar
M'
F,511 [[r, d( =
d(rm: 8m mm)df
Σ
4m And(rm 8m).
(B.29)
uutmar
Av'
m=0
m=0
Compare the result with Eq. (B.20), we have construct transition flow q, that definitely achieves the Wasserstein distance (I Pic+1): Consequently, we have proved that LHS$RHS in Eq. (B.16).
B.3. Iterative solution for W1
At this point, the complicated task of resolving the thermodynamic energy in Eq. (B.7) has been reformulated into the optimal transport problem in Eq. (B.8). To efficiently solve this optimal transport problem and determine W1, we incorporate an additional entropy regularization term. Given that the two distributions involved are sttn and Pend- this regularization introduced as follows:
Wi, Wi,e(Pstnr Pend)
min
Qi-iC - eH{
(B.30)
1,j=1
where the conditions in Eq. (B.1) also required. Following (Cuturi, 2013; Cuturi & Doucet, 2014), the following entropy regularization term is incorporated,
H(Q) = Σ
L log Q[t,]] Q Q[,
(B.31)
We obtain with the Lagrange function L(Q,f.g)
((Q.f.9) Σ Qb.jCCii.ll - Σ fli Σ Qii
Pstan [i] - Σ9
اiوو
Σ Qii [
Pemali]
=
(B.32)
where f and g are Lagrangian multipliers. By taking the derivative with respect to Q, we obtain the first-order condition
((Q.f.9) iQ[i,j]
C(i,j] + log Qii.]] f[i] glil 0,
(B.33)
and the solution
diag(e C/s d
(B.34)
Here, the operation diag(-) takes the input vector to a diagonal matrix. The expression for Q can be determined using a fixed-point iteration method as outlined below:
(1) Begin by initializing (9) and (0) as n--dimensional vectors where each element is set 1. Define K e C/e such that [[ Cbiil/e
-C/c
(2) In each iteration, perform the following computations:
u (f+1) Paann @ (K (K.v(t))
(B.35)
(1+1) Pend 2 K ul(+1)))
and continue until convergence, which results in the pair (u", v²). The Wasserstein distance Wi,e can be then derived after the optimal matrix Q = diag(u"). K diag(v") is determined. Such that the overall time complexity is O(r²).
23

---

Locality Preserving Markovian Transition for Instance Retrieval
C. Experiments
C.I. Visualization
Euclidean
LPMI
Fuciidem
LPMI
Euclidkan
LPMI
Fuclidren
LPMI
Figure 6. This tigure showeases the quantitative evaluation of proposed LPMT in comparison with retrieval results based on Euclidean distance. The region of interest in the query image is highlighted by an orange bounding box on the left. On the right, we visualize the retrieval performance of LPMT against Euclidean distance by displaying the top 10 ranked images for both approaches. Correct matches (true positives) are enclosed in green bounding boxes, whereas incorrect ones (false matches) are marked in red, demonstrating the offectiveness of LPMT as accurate and reliable distance metric for instance retrieval.
(a) original features
(b) Locality State Embedding
Figure 7. (a) The (-SNE visualization of the original image features directly extracted by the deep retrieval model. (b) The L-SNE
visualization of the distributions produced by the Locality State Embedding (LSE) strategy using cosine similarity weights. Compared the original image features, LSE helps mitigate the influence of outliers and leads to improved clustering and retrieval performance.
24

---

Locality Preserving Markovian Transition for Instance Retrieval
C.2. Extended Results
Table Evaluation of the retrieval performances based on global image features extracted by MAC (Tolias et al., 2016).
Table 8, Evaluation of the retrieval performances based on global image features extracted R-MAC (Tolias al., 2016).
Easy
Medium
Hard
Easy
Medium
Hard
Method
Method
ROxf
ROxf
ROxf
ROxf
ROxt
Rlar
MAC
34.6
55.7
32.6
R-MAC
61.2
79.3
63.8
10.1
54.4
80.9
40.6
67.0
43.2
AQE
69.4
85.7
47.8
71.1
15.9
47.9
eQE
50.3
77.8
37.1
64.4
16.3
43.0
aQE
64.9
84.7
42.8
70.8
11.4
47.8
SG
46.1
75.9
36.1
60.4
16.6
38.8
SG
60.1
84.9
42.7
68.4
16.5
45.4
STML.
61.4
86.8
46.7
76.9
22.3
59.5
STML
71.8
88.7
53.2
78.2
23.4
58.8
AQEwD
39.7
AQEwD)
70.5
70.7
RDP
59.0
85.2
45.3
76.3
21.4
58.9
RDP
73.7
88.8
54.3
79.6
22.2
61.3
CAS
68.6
90.1
52.9
82.3
30.4
68.1
CAS
82.6
90.0
62.5
82.5
34.1
67.4
GSS
60.0
87.5
45.4
76.7
22.8
59.7
GSS
75.0
89.9
54.7
78.5
24.4
60.5
79.3
ConAff
77.6
LPMT
LPMT
Table Evaluation of the retrieval performances based on global image features extracted by DELG G (Cao et al., 2020).
Table 10. Evaluation the retrieval performances based on global image features extracted by SENct (Lee al., 2023).
Easy
Medium
Hard
Easy
Medium
Hard
Method
Method
DELG
77.4
SENet
63.0
96.1
82.6
79.5
AQE
95.1
92.3
65.2
aQE
94.5
96.0
81,5
90.7
63.9
80.8
aQE
96.0
95.8
84.1
92.6
67.7
84.0
SG
95.5
95.7
83.3
90.0
66.9
79.6
SG
96.5
96.2
85.5
92.1
70.3
83.1
STML
93.3
95.1
80.3
88.2
62.1
75.3
STML
95.7
95.1
84.1
89.9
67.1
77.9
AQEwD
AQEwD
82.0
RDP
94.4
95.0
84.7
91.6
66.3
81.8
RDP
94.2
94.8
86.8
93.0
72.5
84.8
CAS
97.6
94.7
87.0
91.6
72.1
82.6
CAS
94.9
94.8
87.3
93.6
74.0
86.4
GSS
97.3
95.7
84.7
90.9
66.4
81.6
GSS
96.4
95.9
86.5
91.0
71.6
82.8
ConAff
95.5
92.4
84.2
89.4
66.7
76.3
ConAff
96.1
93.2
87.7
92.1
74.0
LPMT
88.6
94.0
LPMT
96.5
96.5
95.0
76.9
25


Reviews:
[{"review_id": "tvNVMizMQK", "reviewer": "Reviewer_dYaJ", "summary": "In this paper, the authors focused on the diffusion-based re-ranking for instance retrieval. Considering the issue of decaying positive signals and the impact of disconnections in the existing methods, the authors proposed the Locality Preserving Markovian Transition (LPMT) framework. The proposed method consists of three key modules, including BCD, LSE, and TMT. Specifically, BCD integrates diffusion processes across separate graphs to establish strong similarity relationships. LSE encodes each instance into a distribution to enhance local consistency, and TMT connects these distributions through a thermodynamic Markovian transition process for efficient global retrieval while maintaining local effectiveness. Extensive experiments prove the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: Concerns about the involvement of multiple components and hyperparameters.** \n\nRegarding the concern about multiple components and hyperparameters. Although our method consists of multiple modules, each can be implemented in a relatively straightforward manner. For example, the BCD objective can be iteratively solved following Algorithm 1, while TMT reduces to solving an optimization problem (Eq. 20) for the optimal transition strategy. These processes require simple inputs (e.g., BCD only needs the adjacency matrix $W$), ensuring low coupling and easy deployment. Ablation studies demonstrate the robustness of LPMT, showing that most hyperparameters have minimal impact on performance. When adapting to new tasks, only a few key parameters ($k_1$, $k_2$, $\\theta$) need adjustment, reducing the tuning effort when adapting to new tasks. Additionally, high-complexity steps can be decoupled and precomputed (see Q2), further improving efficiency in resource-limited scenarios.\n\n**Q2: Simplify the implementation for practical applications.** \n\nThanks for the concern about the accessibility to practical applications. While our primary focus in this work is to improve the effectiveness of manifold ranking, there are some feasible optimizations to simplify the implementation or enhance efficiency. \n\nFirstly, BCD module can be replaced with Gaussian kernel function to approximate the manifold-aware similarity when computation resource is limited. Additionally, we can adopt an offline strategy to precompute high complexity operations within the database, such that each image can be embed with the diffusion-based similarity in advance. When a new query arrives, we can approximate its diffusion-based similarity with other instances by linearly aggregating neighboring samples. Similarly, the TMT distance can also be precomputed within the graph, allowing us to perform online reranking with an efficiency close to kNN. We will continue to investigate methods to simplify the deployment of the reranking system without sacrificing performance.\n\n**Q3: How to ensure the convergence when jointly optimize $\\beta$ and $F$ in BCD.** \n\nThe convergence of the optimization is ensured by the following factors: \n\n(1) When $\\beta$ is fixed, the objective function (denoted as $J(\\beta, F) = \\lambda\\|\\beta\\|_2^2/2 + \\sum\\beta _ {v}H^{v}$) is convex with respect to $F$ and admits a unique minimum point. Similarly, when $F$ is fixed, the function is convex with respect to $\\beta$ and also has a unique minimum. \n\n(2) In our optimization, we construct a sequence of $\\beta^{(k)}$ and $F^{(k)}$ using the following update rules:\n$$\n\\beta^{(k)} = \\arg\\min\\limits_{\\beta} J(\\beta, F^{(k)}),$$\n$$\nF^{(k+1)} = \\arg\\min\\limits_{F} J(\\beta^{(k)}, F).$$\nThe resulting variable sequence is $\\{(\\beta^{(0)}, F^{(0)}), ..., (\\beta^{(k)}, F^{(k)}), (\\beta^{(k)}, F^{(k+1)}), (\\beta^{(k+1)}, F^{(k+1)}), ...\\}$. The corresponding sequence of objective values $J$ is non-increasing. \n\n(3) If $J(\\beta^{(k)}, F^{(k)}) = J(\\beta^{(k)}, F^{(k+1)})$, then by the uniqueness of the optimal point discussed in (1), we have $F^{(k)} = F^{(k+1)}$, and subsequent updates of $F$ and $\\beta$ will remain unchanged. The same holds if $J(\\beta^{(k)}, F^{(k+1)}) = J(\\beta^{(k+1)}, F^{(k+1)})$.\n\n(4) If the condition in (3) never occurs, then the sequence of objective values strictly decreases at each iteration. Since $J \\geq 0$, the sequence converges to a finite value $J^*$.\n\n**Q4: Assumptions for TMT component and their influence to the performance.** \n\nIn our proposed TMT component, we assume that each transition is governed by a master equation and occurs within a local region. As demonstrated in Appendix B, we prove that the transition cost between two neighboring distributions is equivalent to the Wasserstein distance, where the distance on the graph serves as the cost matrix. This locality assumption mitigates information loss over multiple iterations of the diffusion process and effectively models long-term transitions between distributions in the graph. Compared to directly computing the flow cost between distant distributions, our approach ensures the reliability of each transition while reducing the computational complexity over the entire graph, thereby improving both performance and efficiency.\n\n**Q5: Suggestions for providing more intuitive explanations and improving the organization of supplementary materials and image labels.** \n\nThank you very much for the valuable feedback. We appreciate your suggestions and will incorporate more intuitive explanations of the theoretical concepts to enhance clarity. In the revised version, we will also reorganize the image captions and supplementary materials for better readability and coherence.", "claims_and_evidence": "The authors present a comprehensive set of experiments on multiple datasets with different difficulty levels and using various deep retrieval models. For example, in Table 1, LPMT shows significant improvements in mAP compared to other methods such as AQE, αQE, and CAS under the medium and hard evaluation protocols on ROxf and RPar datasets. The ablation studies also provide evidence for the effectiveness of each component of LPMT.", "methods_and_evaluation_criteria": "The proposed methods make sense for the problem of instance retrieval. The use of diffusion-based processes in BCD is a well-established approach in the field, and the innovation of integrating multiple graphs through bidirectional collaborative diffusion helps to capture the manifold structure more effectively. LSE's encoding of instances into distributions and TMT's use of a thermodynamic transition process are novel and address the limitations of traditional diffusion-based methods.", "theoretical_claims": "The theoretical claims in the paper seem to be well-founded. The authors provide a detailed mathematical derivation for each component of LPMT. It would be beneficial if the authors could provide more intuitive explanations for some of the theoretical concepts, especially for readers who are not familiar with the complex mathematical theories of stochastic thermodynamics.", "experimental_designs_or_analyses": "The experimental designs are sound. The authors compare LPMT with a wide range of re-ranking methods, including query expansion methods, diffusion-based methods, context-based methods, and learning-based methods.", "relation_to_broader_scientific_literature": "The key contributions of the paper may add a new perspective to the field of instance retrieval.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strong points:\nThe paper has a solid theoretical foundation, with detailed mathematical derivations and proofs for the proposed methods.\n\nWeak points:\nThe proposed method is relatively complex, with multiple components and hyperparameters. This may limit its practical application in some scenarios where computational resources are limited.", "other_comments_or_suggestions": "Given the complexity of the method, it would be beneficial if the authors could explore ways to simplify it without sacrificing performance. This could make the method more accessible for practical applications.", "questions_for_authors": "1. In the BCD component, the optimization process involves iteratively updating the similarity matrix F and weights β. How to ensure the stability of this iterative process?\n2. In the TMT component, the use of the Wasserstein distance as an approximation for the minimum transition flow cost is based on certain assumptions. How sensitive is the performance of LPMT to these assumptions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fclPxNuG5Z", "reviewer": "Reviewer_ij2o", "summary": "Existing re-ranking methods tend to reduce discriminative power over several steps. This paper proposes the LPMT framework for accurate manifold distance measurement, thereby enhancing the retrieval process. The proposed method is supported by several theoretical analyses, and experiments demonstrate significant performance improvements over baseline methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable comments on the advanced applications of retrieval in the NLP domain. However, we believe that the key focus of retrieval tasks differs between the fields of image and NLP. We hope the following response will be helpful to emphasize our contribution to manifold ranking and explain why our experiments focus on image retrieval. \n\n**Q1: Motivation for focusing on image retrieval and its challenges.** \n\nOur proposed method addresses a fundamental problem in manifold ranking, which aims to **utilize the inherent structure of the data space** to improve retrieval performance (as discussed in Section 1, 3). Specifically, manifold ranking assumes that instances within a dataset exhibit intrinsic similarities, and when embedded into a semantic feature space, **similar instances tend to form a low-dimensional manifold**. Unlike the conventional approach that relies solely on pairwise similarity between the query and individual samples, manifold ranking **capitalizes on the latent relationships among instances within the database** to improve retrieval performance.\n\nIn image retrieval, each image is represented by a global feature, forming a vector database for retrieval. Refining initial search results by re-extracting image features with a more powerful model is often **computationally expensive and impractical**. Therefore, an efficient strategy is required to enhance retrieval performance by **leveraging the structural relationships among existing feature representations, rather than relying on additional feature extraction.** This characteristic aligns well with the principles of manifold ranking, such that existing algorithms predominantly use it as their primary evaluation benchmark.\n\nConversely, modern NLP tasks tend to go beyond measuring retrieval effectiveness solely based on textual semantic similarity. For instance, recent benchmarks like \"Bright\" place greater emphasis on **logical reasoning and deep text comprehension**. These tasks require finer-grained semantic alignment and reasoning ability between words in the query and documents, **which differs from our task setting that relies solely on original global semantic features.** To enhance the quality of retrieval results, current NLP-driven re-ranking methods primarily leverage more advanced models, such as LLMs and Cross Encoders, to **conduct a deeper analysis of the interactions between queries and documents at the token level.** Given that our method is focused on exploring the semantic relationships among candidates based on global features, it is not well-suited for NLP retrieval tasks that necessitate a fine-grained linguistic understanding.\n\nNevertheless, our approach still remains effective for textual retrieval tasks focused on content search, including text-image retrieval and specific dense model-based information retrieval applications.\n\n**Q2: Broader applications.**\n\nRegarding the concern in Weakness 1 about the applicability of our method to broader retrieval tasks, while it is primarily designed for image retrieval, it is also effective for various textual retrieval tasks with a semantically dense feature database. Leveraging VLMs and pretrained dense retrieval models to process the image and corpus databases, our method can be applied to text-image retrieval and information retrieval tasks. As shown in Tab. 1, 2, our method effectively improves retrieval performance, particularly in text-image retrieval tasks. \n\nTab 1. Zero-shot text-image retrieval on Flickr30k, based on CLIP and BLIP.\n\n||R@1|R@5|R@10|\n|:-: |:-:|:-:|:-:|\n|CLIP|55.7|80.8|88.3|\n|CLIP+Ours|66.7|93.6|96.8|\n|BLIP| 68.3 |89.4|94.2|\n|BLIP+Ours|70.4|95.5|98.4|\n\nTab 2. Information retrieval on ArguAna, based on the pretrained model from BEIR.\n\n||nDCG@1|nDCG@5|nDCG@10|\n|:-:|:-:|:-:|:-:|\n|Baseline|20.6|37.5|42.6|\n|Ours|27.3|47.0|52.2|\n\n**Q3: Evaluation and datasets.** \n\nROxf and RPar are among the most widely used datasets in image retrieval, with the hard protocol posing significant challenges. Nearly all retrieval models report their performance on these benchmarks to ensure fair comparisons, and prior reranking studies consistently use R-GeM as a baseline. Additionally, since different retrieval models yield varying levels of feature representations, it is beneficial to assess the generalizability of LPMT. \n\nEvaluating our method on NLP and RAG benchmarks such as Bright and RGB falls beyond the scope of this study. Our approach applies graph theory to model feature databases, ensuring more reliable results by exploiting the underlying manifold information. We believe these benchmarks are more suited for evaluating LLMs and NLP-based rerankers.\n\n**Q4: Literature review.** \n\nWe appreciate the recommendation to further discuss NLP-focused studies, which could enhance the overall understanding of the retrieval landscape. We will further discuss their distinctions in the revised version.", "claims_and_evidence": "The proposed research problem lacks clear articulation and would benefit from more precise formulation. The writing throughout the manuscript requires improvement to enhance readability and comprehension. Regarding empirical validation, the experimental section needs strengthening with more rigorous evaluation protocols and comprehensive analysis of results.", "methods_and_evaluation_criteria": "The proposed methods appear to address the stated problem effectively. However, the evaluation criteria require further explanation, as several metrics are not clearly defined or justified in the current presentation.", "theoretical_claims": "The theoretical claims presented in the paper appear sound; however, the work would benefit significantly from more thorough comparison with existing literature.", "experimental_designs_or_analyses": "Yes. The experimental design appears comprehensive and provides reasonable support for the work’s central claims.", "relation_to_broader_scientific_literature": "Retrieval technology has emerged as a critical advancement across various domains. Consequently, this work on retrieval methods has potential applications spanning multiple scientific areas, underscoring its broader impact beyond the immediate field of study.", "essential_references_not_discussed": "The discussion on retrieval methods for textual data requires further expansion.\n\n[1] Su, H., Yen, H., Xia, M., Shi, W ., Muennighoff, N., Wang, H. Y., ... & Yu, T. (2024). Bright: A realistic and challenging benchmark for reasoning-intensive retrieval. arXiv preprint arXiv:2407.12883.\n[2] Chen, J., Lin, H., Han, X., & Sun, L. (2024, March). Benchmarking large language models in retrieval-augmented generation. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 16, pp. 17754-17762).", "other_strengths_and_weaknesses": "Strengths：\n\n1. The research problem addressed in this paper is significant, as retrieval technology represents an important area of investigation across multiple fields.\n2. The experimental results demonstrate performance improvements over the selected baseline methods.\n\nWeakness：\n\n1. The stated claim could be made clearer. For instance, the authors note that instance retrieval focuses on identifying images visually similar to a given query image at a large scale. However, retrieval methods have already been widely used in Large Language Model (LLM) contexts, such as Retrieval-Augmented Generation (RAG). Therefore, it would be beneficial to clarify why the work specifically focuses on image-only retrieval, and whether or how lessons from broader retrieval applications (e.g., text-based retrieval) might be incorporated or contrasted.\n\n2. The motivation for focusing on image retrieval should be more compelling. Highlighting the unique challenges of image retrieval—such as differences from natural language processing (NLP) retrieval tasks—would emphasize the distinctiveness and importance of this work.\n\n3. The datasets used in the experiments appear to be outdated. Recent benchmarks have been introduced for retrieval tasks, including:\n[1] Su, H., Yen, H., Xia, M., Shi, W ., Muennighoff, N., Wang, H. Y., ... & Yu, T. (2024). Bright: A realistic and challenging benchmark for reasoning-intensive retrieval. arXiv preprint arXiv:2407.12883.\n[2] Chen, J., Lin, H., Han, X., & Sun, L. (2024, March). Benchmarking large language models in retrieval-augmented generation. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 16, pp. 17754-17762).\nIncluding or comparing against these newer benchmarks could strengthen the evaluation and demonstrate the method’s relevance to current retrieval challenges.\n\n4. The discussion of retrieval-related research is not sufficiently comprehensive, especially regarding developments in the NLP domain. Incorporating relevant NLP-focused retrieval studies and explaining how they align or differ from this work would offer a clearer picture of the broader retrieval landscape.", "other_comments_or_suggestions": "It likewise appears to be a weakness.", "questions_for_authors": "It likewise appears to be a weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g5dgvSf3Wu", "reviewer": "Reviewer_3HVn", "summary": "The paper introduces the Locality Preserving Markovian Transition (LPMT) framework to improve instance retrieval by overcoming the limitations of traditional diffusion-based re-ranking methods. Standard methods suffer from diminishing positive signals over long diffusion paths, which weakens their discriminative power. LPMT addresses this by combining Bidirectional Collaborative Diffusion to build robust similarity matrices, Locality State Embedding to encode instances as probability distributions for enhanced local consistency, and a Thermodynamic Markovian Transition process that bridges distant instances via local intermediate states. This integrated approach effectively preserves local relationships while ensuring accurate global retrieval, leading to notable improvements in performance on benchmark datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: Will the incorporation of extra distractor images introduce an inductive bias?** \n\nAn additional one million distractor images are introduced to simulate a large-scale image database. Compared to the original ROxf and RPar datasets, the expanded database includes a larger number of hard negative samples for each query, significantly increasing retrieval difficulty (ROxf-M baseline drops from 67.3 to 49.5). When applying reranking methods, these distractors introduce noise into the manifold structure, disrupting information propagation and posing a greater challenge to the algorithm.\n\n**Q2: The role of Lemma A.1 and A.5 in the proof.**\n\nWe explicitly present Lemma A.1 and A.5 because they are essential to establish the convexity of the objective function and the convergence of the iterative formulation. In Section A.2, when constraining $\\beta$ and updating $F$, we reformulate the objective function as Eq. (A.8) using properties of the Kronecker product. The convexity proof hinges on demonstrating that the Hessian matrix is positive-definite, which is a nontrivial step that requires Lemma A.1 to derive the nature the matrix $S$. Lemma A.5 is instrumental in proving the convergence of the iterative process in Eq. (A.14) and establishing its equivalence to the closed-form solution. Specifically, in Eq. (A.16), the second summation follows the structure of a Neumann series, necessitating the result of Lemma A.5. \n\nWhile these steps may be derivable for experts in matrix analysis, we include these lemmas to ensure a rigorous and self-contained exposition.\n\n**Q3: Question about the assumption of local transition.** \n\nLimiting each transition to a local region aims to mitigate information loss over multiple iterations in the diffusion process, ensuring reliability at every step. Experiments on various feature databases have demonstrated its effectiveness. We believe that maintaining local characteristics in complex manifold spaces contributes to better overall performance.\n\n**Q4: Explanation of proof B.2.** \n\nWe clarify Proof B.2 by summarizing its main idea and then explaining the derivation of Eqs. (B.21) and (B.24).\n\n(1) The core idea is to prove Eq. (B.16) by establishing both directions: RHS ≤ LHS and LHS ≤ RHS. For RHS ≤ LHS, we show that the transition cost of any flow $T_t$ is no less than the Wasserstein distance (We bridge this by introducing a Riemann sum, which is also in the form of a transportation cost). For LHS ≤ RHS, we aim to construct a flow $T_t$ whose cost matches that of a given transport plan $Q$. Note that many such flows may exist; we only need to show existence.\n\n(2) To prove LHS ≤ RHS, we construct $T_t$ through the following steps:\n$Q$ → $(q _ m)$ (B.20) → $q_t$ (B.21) → $T_t$ (B.22–25). In (B.21), we construct a flow $q_t$ with constant velocity for each vertex-to-vertex transport. That’s why we use a linear time parameter $t$ at the vertices $r_m$ and $s_m$, while keeping the other vertices fixed. Eq. (B.24) follows directly from substituting the first and second equations in (B.23) into the third. By replacing $\\dot{q}_t$ on the left-hand side with the expression in (B.22), and substituting $T_t[r_m, r_m]$ with $-T_t[s_m, r_m]$, we obtain that $T_t$ satisfies (B.24).\n\nWe emphasize again that **we only need to prove the existence** of a valid $T_t$ via construction, uniqueness is not required.\n\n**Q5: Robustness of the proposed method.** \n\nTo verify the robustness of our algorithm across different feature databases, we employ not only the classic R-GeM for feature extraction but also more advanced models such as DOLG/CVNet and weaker models like MAC/R-MAC. This enables evaluation across both stronger and weaker features, with our method consistently outperforming these benchmarks (see Appendix C). Additionally, our algorithm also demonstrates reliability in text-image retrieval tasks, as discussed in our response to reviewer ij2o.\n\n**Q6: Time cost and computational optimizations.** \n\nThank you for raising this important concern. While our primary focus is on improving the effectiveness of manifold ranking, we have some feasible optimizations to address the essential problem of practical deployment. \n\nThe BCD component incorporates a diffusion process that operates with a time complexity of $O(n^3)$. Empirically, for a graph with 5000 nodes, executing 12 iterations requires approximately 0.3s. To enhance computational efficiency, we can adopt an offline strategy to precompute high-complexity operations within the database, wherein each image is encoded with a diffusion-based similarity in advance. Upon receiving a query, its diffusion-based similarity can be approximated by linearly aggregating neighboring samples. Similarly, the TMT distance can be precomputed within the graph, enabling reranking with efficiency comparable to kNN. While approximation introduces some performance overhead, we will continue exploring the trade-off between accuracy and efficiency.", "claims_and_evidence": "The paper claims a novel image retrieval strategy based on extracted image features. It constructs an improved similarity matrix using Collaborative Diffusion (BCD), which automatically integrates diffusion processes on multi-level affinity graphs. To enhance global discriminative power without sacrificing local effectiveness, the authors introduce the Locality State Embedding (LSE) strategy, representing each instance as a locally consistent distribution within the underlying manifold. Finally, Thermodynamic Markovian Transition (TMT) is proposed to perform a constrained time evolution process within local regions at each stage. The definition and formulation is easy to follow.", "methods_and_evaluation_criteria": "Yes, the paper conducts large-scale evaluations on standard datasets, such as Oxford5k (ROxf) and Paris6k, using the standard retrieval metric (mAP), and further divided into Easy, Medium and Hard categories.  I have concerns regarding the setting where an extra collection of one million distractor images is incorporated to form the large-scale ROxf+1M and RPar+1M datasets. Will this operation introduce an inductive bias toward positive results?", "theoretical_claims": "Lemma A.1 to Lemma A.5 are well-known results in matrix analysis, how does they relate to Section A.2? Would the assumption of \"each\ntransition only takes place in local regions\" be too strong to be generalized?  I would like the authors and other reviewers to double check proof B.2, especially B.21 and B.24 which are not convincing to me.", "experimental_designs_or_analyses": "Please check evaluation part comment.", "relation_to_broader_scientific_literature": "No", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "This method is based on extracted features by off-the-shell models, which could be a limitation for downstream methods though sound theoretical framework has been proposed in this paper. Robustness of this method to weaker features or ablations might be a strong proof of the effectiveness of this framework.", "other_comments_or_suggestions": "I would like the author to add a pipeline figure to visualize the pipeline in future versions.", "questions_for_authors": "1. I have concerns regarding the setting where an extra collection of one million distractor images is incorporated to form the large-scale ROxf+1M and RPar+1M datasets. Will this operation introduce an inductive bias toward positive results?\n\n2. I also have concerns about the time cost associated with building the initial similarity diffusion, as well as whether additional computational optimization is required for incoming data. This could potentially affect the practical application value of this work.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mPIbi3LED3", "reviewer": "Reviewer_4j2p", "summary": "This paper tackles the problem of instance retrieval, or finding the image most similar in a dataset to a query image. Existing methods suffer from long-range propagation of similarity information, which the authors improve on with three components. BCD- They improve similarity propagation by combining multiple adjacency graphs rather than relying on a single all-to-all graph.  LSE- transforms distances between pairs into probability distribution between a set of k nearest elements. TMT- they define a new cost metric as the transition cost between 2 elements, which is the term they minimize. They show impressive results across a range of datasets and against a large number of baselines.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your positive assessment and recognition of our contribution to manifold reranking. In this work, we address the fundamental challenge of manifold ranking by introducing the proposed **Locality Preserving Markovian Transition (LPMT)**. Our approach establishes a structured, long-term transition process that effectively connects distinct distributions within the graph, ensuring reliable information propagation at each step. To mitigate the impact of unreliable connections, BCD adaptively ensembles diffusion processes across multi-level graphs to generate a robust similarity matrix. This is achieved through a joint optimization framework that refines both the combination weights and the diffusion objective, which we solve efficiently using a fixed-point iterative approach. Subsequently, LSE embeds each instance as a probability distribution within the manifold space, and LPMT bridges distant distributions through a sequence of locally constrained transitions. This design not only preserves the intrinsic manifold structure but also maintains essential local characteristics, with the minimal transition cost serving as a principled metric for enhanced retrieval performance.\n\nBuilding on this foundation, **migrating the manifold ranking algorithm to Transformers presents an intriguing research direction.** As the core of the Transformer architecture, the self-attention mechanism models pairwise token relationships via dot-product similarity between query and key vectors. While stacking Transformer layers facilitates deeper integration of information, it does not inherently capture the underlying manifold structure of token embeddings within each layer. Given the extensive adoption of Transformers, incorporating manifold ranking, despite its additional computational cost, could improve the reliability of similarity estimation. Since our current algorithm is designed for complex manifold spaces and deep learning-based retrieval tasks, further simplifications are necessary to enhance its robustness for broader applications. We will further investigate these aspects in the future.\n\nRegarding **practical deployment**, while our primary focus is on improving manifold ranking effectiveness, several optimizations can enhance efficiency. For computationally intensive operations such as diffusion, an **offline strategy** can be employed to precompute and store results in a database, allowing the LSE distribution of each instance to be maintained in advance. Upon receiving a new query, its probability distribution can be efficiently estimated via linear aggregation of neighboring samples, significantly reducing online computation. Likewise, the exact computation of TMT cost can also be approximated to improve efficiency. By decoupling complex operations into **offline preprocessing and efficient online retrieval**, we can partition the main workload accordingly, making real-world deployment more practical. We will continue investigating these optimizations in future work.\n\nIn conclusion, he proposed LPMT framework serves as a strong foundation for effective manifold ranking, demonstrating high performance across multiple retrieval benchmarks. Future work will focus on integrating it with Transformer architectures and optimizing efficiency for practical deployment.", "claims_and_evidence": "Yes, the authors provide extensive and impressive quantitative results against existing works.", "methods_and_evaluation_criteria": "Yes, the authors provide a comprehensive list of benchmarks and evaluate their proposed method on a set of datasets.", "theoretical_claims": "The methods proposed in this paper are well established in other areas. They borrow ideas from graph theory, probabilistic methods, and optimal transport. When applied to this setting, they all seem fitting.", "experimental_designs_or_analyses": "I am unfamiliar with the current state of the art in instance retrieval, but it all looked reasonable.", "relation_to_broader_scientific_literature": "While they apply their idea to instance retrieval, I would be very curious to see if their idea can be applied to the attention operation in transformers. A transformer's similarity matrix might be sensitive to exact similarity values between pairs, but a more informed similarity could improve performance. This would increase computational complexity but, depending on the application, could be a worthwhile tradeoff. This could hypothetically be interesting follow-up work.", "essential_references_not_discussed": "The works they include in the paper seem reasonable and comprehensive.", "other_strengths_and_weaknesses": "This is only a slight weakness, but the task of instance retrieval has limits as far as applicability to real-world scenarios. I can see this work being an interesting basis for future work.", "other_comments_or_suggestions": "This paper is very well laid out and easy to follow.", "questions_for_authors": "I am impressed with the paper presented. I have no recommendations for rebuttal.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces the Locality Preserving Markovian Transition (LPMT) framework, employing a long-term thermodynamic transition process with multiple states for accurate manifold distance measurement. After the rebuttal, it received two accept and two weak accept. Its merits, including the clear motivation, solid theoretical foundation, and good experimental results, are well recognized by the reviewers. The response well addresses the reviewers' concerns about the convergence, broader application, and so on. I think the current manuscript meets the requirement of this top conference and recommend for acceptance. Please incorporate the revision in the updated manuscript.
Decision: Accept (poster)