mlsanityData to 7 Oct 2026

Affinity Graph Connectivity in Convex Clustering

arXiv 2605.24673 ↗First posted 23 May 2026stat.ML cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

16 of 40 references.

References · 16

  1. 2017Community Detection and Stochastic Block Modelscited by 317
  2. 2013Splitting Methods for Convex Clusteringcited by 28
  3. 2018Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithmcited by 26
  4. 2015Statistical Properties of Convex Clusteringcited by 19
  5. 2018Provable Convex Co-clustering of Tensorscited by 13
  6. 2019Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularizationcited by 10
  7. 2019Integrative Generalized Convex Clustering Optimization and Feature Selection for Mixed Multi-View Datacited by 8
  8. 2020From graph cuts to isoperimetric inequalities: Convergence rates of Cheeger cuts on data cloudscited by 6
  9. 2020Biconvex Clusteringcited by 6
  10. 2021Local versions of sum-of-norms clusteringcited by 4
  11. 2022Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clusteringcited by 4
  12. 2019Convex Hierarchical Clustering for Graph-Structured Datacited by 3
4 more
  1. 2020Supervised Convex Clusteringcited by 3
  2. 2021Sum-of-norms clustering does not separate nearby ballscited by 3
  3. 2024Low Rank Convex Clustering For Matrix-Valued Observationscited by 2
  4. 2025The Why and How of Convex Clusteringcited by 2

Built on by

Not cited yet.