Affinity Graph Connectivity in Convex Clustering

• URL: http://arxiv.org/abs/2605.24673v1
• Date: Sat, 23 May 2026 17:17:36 GMT
• Title: Affinity Graph Connectivity in Convex Clustering
• Abstract summary: We generalize finite-sample bounds for convex clustering to the setting where affinity weights appearing in the objective correspond to a general connected graph.<n>These bounds and their analysis lead to a better understanding of clustering behavior under various implied connectivity structures behind the data.
• Score: 2.788593861900701
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Introducing the Correlation Concentration Ratio (CCR): Quantitative Framework for Comparing Quantum Cluster States [0.0]
  The process of generating cluster states with linear, square, and T-shaped topologies has been systematically modeled.<n>The simulation results show that the cluster graph structure is directly reflected in the pattern of quadrature correlations.<n>A metric titled CCR is introduced that quantifies the concentration of effective correlations on the graph edges relative to the total correlations of the system.
  arXiv  Detail & Related papers  (2026-04-25T11:50:43Z)
• Differentiable Tripartite Modularity for Clustering Heterogeneous Graphs [0.0]
  We introduce a differentiable formulation of tripartite modularity for graphs composed of three node types connected through mediated interactions.<n>Community structure is defined in terms of weighted co-paths across the tripartite graph, together with an exact factorized computation that avoids the explicit construction of dense third-order tensors.<n>We validate the proposed framework on large-scale urban cadastral data, where it exhibits robust convergence behavior and produces spatially coherent partitions.
  arXiv  Detail & Related papers  (2026-02-10T15:06:53Z)
• Topology Identification and Inference over Graphs [61.06365536861156]
  Topology identification and inference of processes evolving over graphs arise in timely applications involving brain, transportation, financial, power, as well as social and information networks.<n>This chapter provides an overview of graph topology identification and statistical inference methods for multidimensional data.
  arXiv  Detail & Related papers  (2025-12-11T00:47:09Z)
• Unifying Information-Theoretic and Pair-Counting Clustering Similarity [51.660331450043806]
  Clustering similarity measures are typically organized into two principal families, pair-counting and information-theoretic.<n>Here, we develop an analytical framework that unifies these families through two complementary perspectives.
  arXiv  Detail & Related papers  (2025-11-04T21:13:32Z)
• Quantum-Assisted Correlation Clustering [3.8448698053186843]
  This work introduces a hybrid quantum-classical method to correlation clustering, a graph-based unsupervised learning task.<n>We adapt GCS-Q, a quantum-assisted solver originally designed for coalition structure generation, to maximize intra-cluster agreement in signed graphs.<n> Empirical evaluations on synthetic signed graphs and real-world hyperspectral imaging data demonstrate that, when adapted for correlation clustering, GCS-Q outperforms classical algorithms in robustness and clustering quality.
  arXiv  Detail & Related papers  (2025-09-03T12:14:35Z)
• HeNCler: Node Clustering in Heterophilous Graphs via Learned Asymmetric Similarity [48.62389920549271]
  HeNCler learns a similarity graph by optimizing a clustering-specific objective based on weighted kernel singular value decomposition.<n>Our approach enables spectral clustering on an asymmetric similarity graph, providing flexibility for both directed and undirected graphs.
  arXiv  Detail & Related papers  (2024-05-27T11:04:05Z)
• Revealing Decurve Flows for Generalized Graph Propagation [108.80758541147418]
  This study addresses the limitations of the traditional analysis of message-passing, central to graph learning, by defining em textbfgeneralized propagation with directed and weighted graphs. We include a preliminary exploration of learned propagation patterns in datasets, a first in the field.
  arXiv  Detail & Related papers  (2024-02-13T14:13:17Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolation [0.0]
  We build a unifying framework to interpolate between density-driven and geometry-based algorithms for data clustering. We seek this connection through the introduction of Fokker-Planck equations on data graphs. We provide new theoretical insights on the behavior of the family of diffusion maps in the large sample limit.
  arXiv  Detail & Related papers  (2021-08-18T02:00:33Z)
• Amortized Probabilistic Detection of Communities in Graphs [39.56798207634738]
  We propose a simple framework for amortized community detection. We combine the expressive power of GNNs with recent methods for amortized clustering. We evaluate several models from our framework on synthetic and real datasets.
  arXiv  Detail & Related papers  (2020-10-29T16:18:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.