arXiv preprint ·
Exact Selective Inference for Spectral Clustering via Piecewise-Constant Graph Perturbation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Nonparametric GARCH: An Iterated Neural Estimator
Discovering like a scientist: Literature-informed dimensionless learning for physical closure of data-driven equations
Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions
Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities
Statistical Machine Learning for Medicinal Plant Leaves Classification
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.