# Affinity Graph Connectivity in Convex Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 23 May 2026.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Splitting Methods for Convex Clustering](https://mlsanity.com/paper/1304.0499/) (2013)
- [Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm](https://mlsanity.com/paper/1810.02677/) (2018)
- [Statistical Properties of Convex Clustering](https://mlsanity.com/paper/1503.08340/) (2015)
- [Provable Convex Co-clustering of Tensors](https://mlsanity.com/paper/1803.06518/) (2018)
- [Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization](https://mlsanity.com/paper/1901.01477/) (2019)
- [Integrative Generalized Convex Clustering Optimization and Feature Selection for Mixed Multi-View Data](https://mlsanity.com/paper/1912.05449/) (2019)
- [From graph cuts to isoperimetric inequalities: Convergence rates of Cheeger cuts on data clouds](https://mlsanity.com/paper/2004.09304/) (2020)
- [Biconvex Clustering](https://mlsanity.com/paper/2008.01760/) (2020)
- [Local versions of sum-of-norms clustering](https://mlsanity.com/paper/2109.09589/) (2021)
- [Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering](https://mlsanity.com/paper/2211.01877/) (2022)
- [Convex Hierarchical Clustering for Graph-Structured Data](https://mlsanity.com/paper/1911.03417/) (2019)
- [Supervised Convex Clustering](https://mlsanity.com/paper/2005.12198/) (2020)
- [Sum-of-norms clustering does not separate nearby balls](https://mlsanity.com/paper/2104.13753/) (2021)
- [The Why and How of Convex Clustering](https://mlsanity.com/paper/2507.09077/) (2025)
- [Low Rank Convex Clustering For Matrix-Valued Observations](https://mlsanity.com/paper/2412.17328/) (2024)

## Abstract (arXiv)

We generalize finite-sample bounds for convex clustering to the setting where affinity weights appearing in the objective correspond to a general connected graph. These bounds and their analysis lead to a better understanding of clustering behavior under various implied connectivity structures behind the data and to new rates of convergence for centroid recovery. The new theoretical framework is based on random walks, which allow application of concentration inequalities related to random graph models, and formalizes the relationship between the clustering performance and the connectivity of the graph structures. Through the form of the bound and empirical results, we argue proper tuning of hyperparameters to convex clustering problems should also include tuning of input affinity weights.