Research map / Graph learning / Graph algorithms and clustering
Cluster-Aware Similarity Diffusion 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 Cluster-Aware Similarity (CAS) diffusion, which confines similarity propagation to local neighbor clusters with bidirectional smoothing and neighbor-guided smoothing, improving diffusion-based re-ranking for instance retrieval and person ReID.
Problem
Diffusion-based re-ranking propagates similarity over a pairwise kNN graph, so misinformation from outliers and other manifolds spreads through the whole graph and degrades instance retrieval accuracy.
Approach
Restrict diffusion to local clusters (an instance and its k-reciprocal neighbors), enforce bidirectional (symmetric) smoothness with an inverse constraint term, and refine the similarity matrix with neighbor-guided smoothing before propagating globally and computing a Jensen-Shannon distance.
Key results
- CAS reaches 80.7% mAP on ROxf medium and 64.8% on ROxf hard with R-GeM, and 91.0% on RPar medium (R-GeM baseline 67.3/44.2/80.6).
- With R-MAC on ROxf medium, CAS reaches 62.5% mAP, about 7.8 points above the best diffusion baseline per the text.
- Re-ranking ROxf takes 1,278 ms on a single RTX 3090, versus 8,524 ms for k-reciprocal and 1,857 ms for DFS, with O(n^3) complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply CAS instead of R-GeM baseline ranking | R-GeM · ROxf Medium | mAP: 67.3 -> 80.7 | Helped |
| Apply CAS instead of R-GeM baseline ranking | R-GeM · ROxf Hard | mAP: 44.2 -> 64.8 | Helped |
| Add bidirectional similarity smoothing rather than one-directional SSM (ablation) | BSD with k-reciprocal clusters · ROxf Medium | mAP: 80.2 -> 80.7 | Helped |
| Add bidirectional similarity smoothing rather than one-directional SSM (ablation) | BSD with k-reciprocal clusters · ROxf Hard | mAP: 63.9 -> 64.8 | Helped |
| Use k-reciprocal neighbors instead of k-nn to construct local clusters (ablation) | BSD · ROxf Medium | mAP: 79.3 -> 80.7 | Helped |
| Use k-reciprocal neighbors instead of k-nn to construct local clusters (ablation) | BSD · ROxf Hard | mAP: 62.4 -> 64.8 | Helped |
| Add Neighbor-guided Similarity Smooth (NSS) (ablation) | CAS · ROxf Medium and Hard | mAP: 5.5% in ROxf(M); 8.8% in ROxf(H) | Helped |
| Replace NSS with query-expansion-style neighbor fusion (ablation) | CAS · ROxf | mAP | Hurt |
| Use Jensen-Shannon divergence instead of Euclidean distance (ablation) | CAS retrieval distance · ROxf Medium | mAP: 71.7 -> 80.7 | Helped |
| Vary k2 for the neighbor set (ablation) | CAS · ROxf Medium and Hard | mAP: 78.14, 78.81, 79.7, 80.8, 80.8, 80.7, 80.5, 79.2, 78.3, 78.0; 61.27, 62.44, 64.0, 65.6, 65.3, 64.8, 64.9, 62.7, 61.2, 61 | Mixed |
| Vary omega to balance Euclidean distance and Jensen-Shannon divergence (ablation) | CAS retrieval distance · ROxf Medium and Hard | mAP: 79.1, 80.0, 80.5, 80.7, 80.7, 80.5, 80.1, 79.4, 78.4, 76.5; 64.2, 64.6, 65.2, 65.3, 64.8, 63.9, 63.0, 61.8, 60.4, 58.0 | Mixed |
Surprising findings
- Replacing the neighbor-guided smoothing with AQE-style kNN fusion yields only limited gains, suggesting the specific NSS design matters.
Limitations
- Accurate estimation of the local cluster is still a limitation, as stated by the authors.
- Time complexity remains O(n^3), same level as other diffusion methods.
- Several hyperparameters (k1, k2, omega, mu, kappa) need tuning.
Experimental setup
Datasets: Revisited Oxford5k (ROxf) Revisited Paris6k (RPar) Oxford5k Paris6k Market1501 CUHK03 ROxf+1M distractors RPar+1M distractors
Benchmarks: ROxf RPar ROxf+1M RPar+1M Market1501 CUHK03
Metrics: mAP Rank-1 mINP re-ranking latency
Baselines: AQE alphaQE DQE AQEwD LAttQE kNN DFS FSR RDP EIR GSS EGT
Builds on: Ranking on data manifolds (diffusion) k-reciprocal re-ranking alpha-QE Fusion with Diffusion R-GeM
Closest papers by meaning
- Locality Preserving Markovian Transition for Instance Retrieval (ICML 2025 · similarity 0.88)
- Contextually Affinitive Neighborhood Refinery for Deep Clustering (NeurIPS 2023 · similarity 0.86)
- Re-Ranking via Metric Fusion for Object Retrieval and Person Re-Identification (CVPR 2019 · similarity 0.84)
- Guided Similarity Separation for Image Retrieval (NeurIPS 2019 · similarity 0.84)
- Where's Waldo: Diffusion Features For Personalized Segmentation and Retrieval (NeurIPS 2024 · similarity 0.83)
- Fast Incomplete Multi-view Clustering with Adaptive Similarity Completion and Reconstruction (AAAI 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.