Research map / Graph learning / Graph algorithms and clustering
TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization
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 TANGO, a clustering method that uses a global-view "typicality" score over density-ascending dependencies to decide modes without thresholds, then aggregates sub-clusters via graph-cut (spectral clustering) on a path-based similarity.
Problem
Mode-seeking clustering methods (Quick Shift, DPC and variants) decide modes from local density and distance, requiring case-by-case thresholds or human intervention to work across datasets.
Approach
Define a recursive typicality T = B^T T + rho over a hierarchical leader-based dependency graph, break dependencies where a point's typicality is at least its leader's to form modes, then merge mode-centered sub-clusters with spectral clustering on an improved path-based (minimax-connectivity) similarity weighted by densities.
Key results
- On 16 real-world datasets TANGO achieves the best ARI on all datasets versus 10 baselines; e.g., banknote ARI 96.53 vs 95.39 (CPF) and MNIST (AE) ARI 83.4 vs 73.8 (USPEC).
- Friedman test p=2.9e-16 and Nemenyi post-hoc test shows TANGO's mean rank differences exceed CD=2.30.
- Time complexity stated as O(nk^2 d), dominated by similarity computation; segmentation of 154,401-pixel images runs in under 4 seconds beyond similarity computation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use TANGO instead of KNN-SC | real-world clustering · wdbc | ARI: 81.76 -> 85.01 | Helped |
| use TANGO instead of QKSPP | real-world clustering · heartEW | ARI: 36.62 -> 39.4 | Helped |
| use TANGO instead of DEMOS | real-world clustering · segmentation | ARI: 61.19 -> 64.21 | Helped |
| use TANGO instead of LDP-SC | real-world clustering · semeion | ARI: 55.58 -> 65.37 | Helped |
| use TANGO instead of USPEC | real-world clustering · semeionEW | ARI: 55.95 -> 63.49 | Helped |
| use TANGO instead of QKSPP | real-world clustering · ver2 | ARI: 37.62 -> 42.85 | Helped |
| use TANGO instead of USPEC | real-world clustering · synthetic-control | ARI: 68.86 -> 72.23 | Helped |
| use TANGO instead of LDP-MST | real-world clustering · waveform | ARI: 31.34 -> 39.77 | Helped |
| use TANGO instead of KNN-SC | real-world clustering · CongressEW | ARI: 61.35 -> 69.54 | Helped |
| use TANGO instead of LDP-SC | real-world clustering · mfeat-zer | ARI: 62.7 -> 66.33 | Helped |
| use TANGO instead of DPC-DBFN | real-world clustering · ionosphereEW | ARI: 26.29 -> 49.15 | Helped |
| use TANGO instead of CPF | real-world clustering · banknote | ARI: 95.39 -> 96.53 | Helped |
Surprising findings
- Authors note TANGO underperforms when low-density points lie uniformly around high-density points with extreme density discrepancy, since typicality of low-density points is insufficient to break dependencies.
Limitations
- Performs worse when low-density points surround high-density points with extreme density discrepancy, so dependencies are not broken.
- Single hyperparameter k still has to be chosen; automatic selection is left to future work.
Experimental setup
Datasets: wdbc heartEW segmentation semeion semeionEW ver2 synthetic-control waveform CongressEW mfeat-zer ionosphereEW banknote
Benchmarks: wdbc heartEW segmentation semeion semeionEW ver2 synthetic-control waveform CongressEW mfeat-zer ionosphereEW banknote
Metrics: ARI NMI ACC
Baselines: LDP-SC DCDP-ASC LDP-MST NDP-Kmeans DEMOS CPF QKSPP DPC-DBFN USPEC KNN-SC
Builds on: Quick Shift Density Peaks Clustering Normalized Cut PageRank
Closest papers by meaning
- Scalable Laplacian K-modes (NeurIPS 2018 · similarity 0.87)
- Efficient Testing for Correlation Clustering: Improved Algorithms and Optimal Bounds (ICLR 2026 · similarity 0.85)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.84)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.83)
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.83)
- THESAURUS: Contrastive Graph Clustering by Swapping Fused Gromov-Wasserstein Couplings (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.