# Doubly Stochastic Adaptive Neighbors Clustering via the Marcus Mapping

arXiv: https://arxiv.org/abs/2408.02932 · HTML: https://mlsanity.com/paper/2408.02932/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 21 references that are in the map.
- First posted on arXiv 6 Aug 2024.

## Builds on (most cited first, 5 of 5)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Sinkformers: Transformers with Doubly Stochastic Attention](https://mlsanity.com/paper/2110.11773/) (2021)
- [GLCC: A General Framework for Graph-Level Clustering](https://mlsanity.com/paper/2210.11879/) (2022)
- [SNEkhorn: Dimension Reduction with Symmetric Entropic Affinities](https://mlsanity.com/paper/2305.13797/) (2023)
- [Doubly Stochastic Graph-based Non-autoregressive Reaction Prediction](https://mlsanity.com/paper/2306.06119/) (2023)

## Built on by (most cited first, 4 of 4)

- [A Margin-Maximizing Fine-Grained Ensemble Method](https://mlsanity.com/paper/2409.12849/) (2024)
- [Riemannian Optimization on Relaxed Indicator Matrix Manifold](https://mlsanity.com/paper/2503.20505/) (2025)
- [Double-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clusterin](https://mlsanity.com/paper/2501.18143/) (2025)
- [Multi-Task Curriculum Graph Contrastive Learning with Clustering Entropy Guidance](https://mlsanity.com/paper/2408.12071/) (2024)

## Abstract (arXiv)

Clustering is a fundamental task in machine learning and data science, and similarity graph-based clustering is an important approach within this domain. Doubly stochastic symmetric similarity graphs provide numerous benefits for clustering problems and downstream tasks, yet learning such graphs remains a significant challenge. Marcus theorem states that a strictly positive symmetric matrix can be transformed into a doubly stochastic symmetric matrix by diagonal matrices. However, in clustering, learning sparse matrices is crucial for computational efficiency. We extend Marcus theorem by proposing the Marcus mapping, which indicates that certain sparse matrices can also be transformed into doubly stochastic symmetric matrices via diagonal matrices. Additionally, we introduce rank constraints into the clustering problem and propose the Doubly Stochastic Adaptive Neighbors Clustering algorithm based on the Marcus Mapping (ANCMM). This ensures that the learned graph naturally divides into the desired number of clusters. We validate the effectiveness of our algorithm through extensive comparisons with state-of-the-art algorithms. Finally, we explore the relationship between the Marcus mapping and optimal transport. We prove that the Marcus mapping solves a specific type of optimal transport problem.