cs.LGNov 3, 2026

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

Authors: Naotoshi Nakamura

Organizations: Graduate School of Data Science, Yokohama City University, Yokohama, Japan

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 pp-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 kk-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 pp-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 KK, 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.

Figures & tables

Explore similar work

CardsList
  1. Selective Inference for Clustering Under Unknown Covariance

    Oct 12, 2026Yiqun T. Chen, Lucy L. GaoSelective InferenceStatistical Hypothesis Testing

  2. Spectral graph clustering with inhomogeneous latent geometry

    Aug 11, 2026Konstantin Avrachenkov, Lucas S. Sibemberg, Alexander Van WerdeSpectral ClusteringGraph Clustering

  3. Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering

    Sep 24, 2026Yordan P. Raykov, Max A. LittleClusteringDynamic Programming