CS Paper Radar

Bracketing Uncertainty in Clustering Under the Manifold Hypothesis

Savik Kinger, Luciano Dyballa, Steven W. Zucker

cs.LG stat.MLq-bio.QM ·submitted 2026-09-15 22:34 UTC · v1

Abstract

The manifold hypothesis suggests a natural criterion for clustering: partition data according to the manifold component from which each point is drawn. Whether two components are separable depends on a geometric tradeoff: the ambient separation between components versus the largest gap in sampling. In practice, this tradeoff is rarely assessed explicitly, leading standard methods to over-commit to a single clustering assignment even when the data do not support a unique answer. We formalize this tradeoff by combining intrinsic manifold geometry (volume growth and reach) with sample-level quantities (fill distance and density), yielding a threshold phenomenon for mutual-$k$-nearest-neighbor graphs: when the offset-to-fill ratio exceeds a conservative upper threshold, component separation is preserved; below a lower threshold, components fuse. The gap between these thresholds defines a geometric uncertainty zone in which the number of clusters is not identifiable from the data. Nevertheless, conventional approaches still seek one: sweeping parameters (an engineering approach) or fitting a generative mixture model (a model-based approach). Rather than forcing a single estimate of the number of clusters, we propose Manifold-Based Clustering (MBC), which returns an explicit bracket interval to quantify the underlying data uncertainty. This bracket acts as an empirically calibrated diagnostic: it narrows when a single resolution is supported, widens when multiple resolutions coexist, and collapses to one when no separated structure is detectable. Empirically, we find that many real datasets lie within the uncertainty zone rather than admitting one clear answer. Our results suggest that ambiguity in cluster number is often intrinsic, and should be quantified rather than resolved.

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Selective Inference for Spectral Clustering via Piecewise-Constant Graph Perturbation

cs.LG stat.ML ·2026-11-03 ·Naotoshi Nakamura
published similarity 0.61
Abstract · 31 pages, including supplementary material. Accepted at ACML 2026

Cluster labels are often used twice: first to discover groups, and then to test whether the discovered groups differ. This double use of the data makes ordinary two-sample $p$-values anti-conservative. Selective inference fixes this by conditioning on the clustering event, but for spectral clustering the event appears difficult because the algorithm combines an affinity map, an eigendecomposition, and a rounding step. We show that, for spectral clustering based on unweighted $\varepsilon$- or $k$-nearest-neighbor graphs, the obstruction is the affinity construction rather than the eigendecomposition. Along the one-dimensional perturbation used by the truncated-$χ$ selective test, graph changes occur only at finitely many real roots of data-dependent quadratic distance comparisons. Between these breakpoints, the graph, Laplacian spectrum, embedding, rounding, and reported cluster pair are deterministic functions of a finite graph state. Consequently, in real arithmetic and under a known-scale spherical Gaussian model, the selection set is an exact finite union of intervals, yielding finite-sample selective $p$-values for selected spectral-cluster pairs. The same argument gives feature-wise truncated-normal tests. We also record direct extensions to known feature covariance, eigengap-selected $K$, and auxiliary-coordinate graphs. We validate null and partial-null calibration, operational power, numerical sensitivity, and model-scope diagnostics, and give a working-model PBMC algorithmic illustration. Smooth kernels such as RBF affinities fall outside the finite-state guarantee.

0.29

Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy

cs.LG ·2026-08-14 ·Johanna Hillebrand, Jan Höckendorff, Jürgen Kusche, Kelin Luo, Heiko Röglin +3 more
theory similarity 0.60
Abstract

Constrained optimization extends classical optimization by integrating side information, making it widely applicable across scientific and engineering domains. Consider a setting where we measure variables at different physical locations. When grouping these measurements, we often want clusters that are both internally similar and physically coherent. Thus, we have a constrained clustering problem where the constraint models coherence. Motivated by an application in geodesy, where contiguous regions of the sea surface must be identified for principal component analysis, we introduce the Connected Subspace Clustering problem: given high-dimensional points and a connectivity graph, partition them into $k$ connected clusters, minimizing their total squared distance to the clusters' best-fit $m'$-dimensional affine subspaces. We prove that, even for $m' = 0$ and a grid graph with holes, the problem is NP-hard to approximate within $Ω(n^{1/2-\varepsilon})$ for every $\varepsilon>0$, where $n$ is the number of measurements. We then introduce an efficient Lloyd-style heuristic that alternates subspace fitting with an iterative merging procedure to enforce connectivity. Our method returns exactly $k$ connected regions by construction, whereas unconstrained methods leave up to $1{,}966$ disconnected fragments at higher cost. In a study of 160 configurations on global sea level time series, our merging-based repair is the strongest of four strategies in $73.75\%$ of cases, and consistently outperforms competitors such as (connected) Ward's method across all tested cluster counts. The resulting regions isolate signals aligning with climate indices such as the El Nino-Southern Oscillation and Indian Ocean Dipole. Although developed for geodesy, the approach applies to other spatially embedded multivariate time series, such as climate fields, remote sensing, neuroimaging, and sensor networks.

0.04

Interpretable Graph Partitioning for Spatial Prediction

cs.LG ·2026-10-12 ·Yuta Shikuri
similarity 0.59
Abstract

Spatial prediction estimates unobserved values from spatially distributed observations. Although flexible predictive models are increasingly available, their practical use remains limited when interpretability is essential. In this study, we formulate a graph partitioning problem to construct a global surrogate model that approximates black-box predictions with simpler representations. Specifically, we select connected subgraphs to minimize within-cluster residuals in vertex-level predictions. Although this formulation can be viewed as a variant of spatial regionalization, it operates on model-based predictions at individual locations rather than predefined areal units. With many locations, this point-level formulation may produce artificial connections between regions, reducing interpretability. We therefore introduce a constraint that excludes such connections while retaining flexible partition boundaries. We theoretically analyze how this constraint affects the resulting partition. We also develop a computational procedure for adjusting partition boundaries. Experimental results show that the proposed method yields spatially coherent partitions with flexible boundaries.

0.15

Alleviating Limited Effectiveness and Multi-Class Collapse in Deep Graph-level Clustering

cs.LG ·2026-11-04 ·Xiaoyang Lin, Renchi Yang, Yuqi Chen, Xin Huang
benchmarktheoryhot direction similarity 0.58
Abstract

Given a collection of $N$ graphs, graph-level clustering (GLC) seeks to partition the $N$ graphs into semantically meaningful groups, which serves as a fundamental task in analyzing graph-structured data. While Graph Isomorphism Networks (GINs) have become the de facto encoders for GLC, they still fail to distinguish graphs due to their neglect of global topology. On top of that, existing deep clustering frameworks suffer from severe "clustering collapse" issues, particularly in imbalanced multi-class scenarios. To address these challenges, we propose S$^3$GLC, a novel framework that integrates global topological characteristics with local neighborhood features for balanced GLC. Theoretically, we leverage the Hoffman-Wielandt inequality to construct Spectral Signature as a rigorous lower bound for graph edit distance (GED), providing a computationally efficient proxy for global topological features. We additionally propose a joint manifold-preserving sparse regression module to fuse Spectral Signature with Spatial Representation, eliminating noise while preserving the complementary information. Furthermore, to mitigate clustering collapse, we introduce a balanced clustering objective based on optimal transport, harnessing the Sinkhorn-Knopp normalization to enforce equipartition constraints on cluster assignments. Extensive experiments on 10 real-world datasets demonstrate that S$^3$GLC significantly outperforms 15 state-of-the-art baselines, achieving remarkable improvements on benchmark datasets such as REDDIT-12K and OGBG-PPA.

0.23

Minimax Rates and Improved Spectral Convergence for Multi-Manifold Clustering

cs.LG stat.ML ·2026-10-11 ·Haoyu Chen, Chenghui Li
similarity 0.58
Abstract

We study eigenpair estimation for the tensorized, density-weighted Laplace--Beltrami operator from $n$ independent data points sampled from a multi-manifold mixture distribution where manifolds may intersect. Let $d$ denote the largest intrinsic dimension of the manifold components and $s\geq2$ the smoothness of the sampling densities. For simple, nontrivial eigenpairs, we establish the minimax rate $n^{-s/(d+2s)}$ for approximating the eigenvalue and eigenfunction of the tensorized Laplace--Beltrami operator, and show that a continuum plug-in estimator based on kernel density estimation attains the same rate when the supporting manifolds are known. We further analyze a manifold-agnostic graph Laplacian estimator and prove that its eigenpairs converge to those of the tensorized Laplace--Beltrami operator at rate $n^{-1/(2.5d-1)}$, up to logarithmic factors, improving upon previously known spectral convergence rates for multi-manifold learning. Numerical experiments on synthetic multi-manifold data corroborate the rates guaranteed by our theorems. These results characterize the information-theoretic difficulty of multi-manifold spectral estimation and quantify the additional cost of learning without oracle component information.

0.23

Automatic depth-based local center clustering via $β$-integrated local depth and adaptive grouping

cs.LG stat.MEstat.ML ·2026-09-22 ·Siyi Wang, Alexandre Leblanc, Paul D. McNicholas
similarity 0.58
Abstract

Clustering is an unsupervised learning technique that partitions unlabeled data into groups. Most existing methods require user-specified parameters, such as the number of clusters or neighborhood size. Conversely, we propose automatic depth-based local center clustering (A-DLCC), a fully data-driven method that eliminates numerical parameter tuning. A-DLCC uses the $β$-integrated local depth to identify stable exemplars, points consistently central across multiple locality levels, termed local centers, which are ranked by their representativeness. Each local center induces a group of similar points, with group-level similarity measured by a proposed nonparametric metric called group-level local similarity. To guide merging, we incorporate the bottleneck path idea from graph theory, which forms the basis of our adaptive merging criterion. Based on this criterion, we design a single agglomeration rule in which a group is either absorbed by a neighbor it reaches better than itself or bonded to a neighbor that both sides find more reachable than their own background, every merge being additionally required to be carried by a contact stronger than a configuration-model null expects. The rule automatically estimates the number of clusters and decides when to stop merging. Experiments on synthetic and real data show that A-DLCC produces interpretable clustering results without parameter tuning.

0.22

Topological Equivalence of Spectral and Density Cluster Hierarchies

cs.LG ·2026-10-22 ·Sajjad Hashemian
similarity 0.57
Abstract

We compare two canonical ways to recover hierarchical clustering from an underlying density $f$: the \emph{density cluster tree} given by connected components of superlevel sets $\{f\geλ\}$, and a \emph{spectral hierarchy} obtained by applying single linkage to diffusion distances induced by a Laplacian operator. We give conditions under which, at an appropriate diffusion time, the diffusion hierarchy is \emph{topologically equivalent} to the density cluster tree up to a monotone rescaling of heights. It further shows that a $k$-NN graph implementation inherits this equivalence from uniform approximation of diffusion distances, yielding a finite-sample reduction from spectral graph constructions to density-level-set topology.

0.25

Spectral graph clustering with inhomogeneous latent geometry

cs.SI cs.LGmath.PRstat.ML ·2026-08-11 ·Konstantin Avrachenkov, Lucas S. Sibemberg, Alexander Van Werde
similarity 0.57
Abstract · 28 pages, 11 figures

We study spectral clustering in the presence of a confounding latent geometry. The leading eigenvectors may then be dominated by the latent geometry rather than by the communities. Nevertheless, we show in a block latent-space model that communities can be recovered from eigenvectors deeper in the spectrum. We analyze the spectral properties of the adjacency matrix through a limiting integral operator and use its structure to develop DBSPEC, a density-based spectral clustering algorithm that requires only approximate localization of the informative eigenvalue and is robust to poor eigenvalue separation. Crucially, this approach handles general latent geometries, overcoming restrictions to homogeneous toroidal models in prior works. Our theoretical predictions for the location of the informative eigenvalue notably align with observations in real-world experiments.

0.10