Selective inference method improves trust in spectral clustering results
Exact Selective Inference for Spectral Clustering via Piecewise-Constant Graph Perturbation
Machine Learning
Summary
When people group data into clusters, they often use the same data to both find the clusters and test if the groups are really different. This can make the usual tests for differences unreliable. The authors present a new way to make these tests accurate for a popular method called spectral clustering. They analyze how the data and clustering relate and create exact tests that only work when using certain types of graphs. Their method helps people trust the significance of their clustered groups better.
What this means in practice
- •For data science teams: Produce reliable significance tests for groups found by spectral clustering in complex datasets using nearest-neighbor graphs.
- •For bioinformatics analysts: Validate biologically meaningful clusters in single-cell data analysis using exact tests conditioned on the clustering event.
Authors
Naotoshi Nakamura
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.