Research map / Image generation / Fast diffusion sampling
Locality Preserving Markovian Transition for Instance Retrieval
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LPMT, a training-free re-ranking framework for instance retrieval combining bidirectional collaborative diffusion, locality state embedding, and a thermodynamic Markovian transition distance, reaching new SOTA on RParis/ROxford re-ranking.
Problem
Diffusion-based manifold re-ranking loses positive similarity signal over multiple diffusion steps for instances beyond the local region and is sensitive to affinity graph construction errors.
Approach
Integrates diffusion over multiple graphs with learned weights (BCD), embeds each instance as a local-neighborhood probability distribution (LSE), and measures distance as the minimum cost of a multi-state Markov transition path through local regions, approximated by Wasserstein-1 distances (TMT), then fuses with Euclidean distance.
Key results
- On RParis with R-GeM, LPMT reaches 93.0% mAP (medium) and 84.1% (hard), versus 91.0 and 80.7 for the best prior method CAS.
- With DOLG features on ROxford, LPMT improves from 93.4/81.2/62.6 to 99.7/91.4/78.2 (easy/medium/hard).
- On ROxford hard with R-GeM, LPMT reaches 67.8% mAP, 3.0 points above CAS (64.8%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply LPMT re-ranking | R-GeM · ROxf Medium | mAP: 80.7 -> 84.7 | Helped |
| Apply LPMT re-ranking | R-GeM · ROxf Hard | mAP: 64.8 -> 67.8 | Helped |
| Apply LPMT re-ranking | R-GeM · RPar Medium and Hard | mAP: 91.0 -> 93.0; 80.7 -> 84.1 | Helped |
| Apply LPMT re-ranking | DOLG · ROxf Easy, Medium, and Hard | mAP: 93.4 -> 99.7; 81.2 -> 91.4; 62.6 -> 78.2 | Helped |
| Apply LPMT | unsupervised image retrieval · CUB200, Indoor, and Caltech101 | mAP | Helped |
| Add BCD instead of using BSD (ablation) | R-GeM retrieval · ROxf Medium, k=10 | mAP: 83.6% to 84.7% | Helped |
| Add BCD instead of using BSD (ablation) | R-GeM retrieval · ROxf Hard, k=10 | mAP: 65.2% to 67.8% | Helped |
| Use BCD similarity with k-reciprocal LSE rather than BSD similarity (ablation) | R-GeM retrieval · ROxf Hard | mAP: 65.2 -> 67.8 | Helped |
| Use BCD similarity with k-reciprocal LSE rather than BSD similarity (ablation) | DOLG retrieval · ROxf Hard | mAP: 77.2 -> 78.2 | Helped |
| Use BCD similarity with k-reciprocal LSE rather than BSD similarity (ablation) | CVNet retrieval · ROxf Hard | mAP: 73.8 -> 75.2 | Helped |
| Use k-reciprocal rather than k-nn LSE with BCD (ablation) | R-GeM retrieval · ROxf Medium and Hard | mAP: 84.2 -> 84.7; 66.1 -> 67.8 | Helped |
| Use thermodynamic transition distance rather than total variation (ablation) | R-GeM retrieval · ROxf Medium and Hard | mAP: 79.5 -> 84.7; 61.7 -> 67.8 | Helped |
Limitations
- Time complexity is O(n^3); re-ranking restricted to top-k images for practicality.
- Many hyperparameters (k1, k2, kappa, theta, mu, sigma, lambda) must be tuned.
- Wasserstein-1 is used as an approximation to the thermodynamic transition cost, with theoretical justification in the appendix only.
Experimental setup
Datasets: ROxford5k RParis6k ROxford+1M RParis+1M CUB200 Indoor Caltech101
Benchmarks: ROxford5k RParis6k ROxford+1M RParis+1M CUB200 Indoor Caltech101
Metrics: mAP R@1
Baselines: AQE alphaQE DQE AQEwD LAttQE DFS RDP EIR EGT CAS GSS SSR
Builds on: Bidirectional Similarity Diffusion alpha-QE k-reciprocal re-ranking master equation
Closest papers by meaning
- Cluster-Aware Similarity Diffusion for Instance Retrieval (ICML 2024 · similarity 0.88)
- Regularized Diffusion Process for Visual Retrieval (AAAI 2017 · similarity 0.85)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.84)
- What Matters for Diffusion-Friendly Latent Manifold? Prior-Aligned Autoencoders for Latent Diffusion (NeurIPS 2026 · similarity 0.83)
- Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models (ICML 2024 · similarity 0.83)
- Provable Maximum Entropy Manifold Exploration via Diffusion Models (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.