Exact Selective Inference for Spectral Clustering via Piecewise-Constant Graph Perturbation
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 -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 - or -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 -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 , 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
| Level | Event fixed along the path | Role |
|---|---|---|
| Graph-conditioned | realized graph state | cheapest, most conservative |
| Full partition | exact spectral partition | intermediate diagnostic |
| Matched rule | for the reporting rule | primary test |
| Pair appearance | appears among cluster pairs | valid when the pair is user chosen |
| Setting | mean | KS | ||||
|---|---|---|---|---|---|---|
| current_n18_d5 | 5000 | 0.497 | 0.010 [0.008, 0.014] | 0.051 [0.045, 0.057] | 0.096 [0.088, 0.105] | 0.222 |
| larger_n32_d5 | 5000 | 0.498 | 0.010 [0.008, 0.013] | 0.053 [0.047, 0.059] | 0.104 [0.096, 0.113] | 0.911 |
| Alternative policy | Attempted | Evaluable | Set differences | Discrete changes | Max. | Max. symmetric mass |
|---|---|---|---|---|---|---|
| Stable quadratic formula | 400 | 399 | 121 | 0 | 1.10e-13 | 5.35e-16 |
| Long-double roots | 400 | 399 | 121 | 0 | 1.10e-13 | 5.35e-16 |
| Relaxed root merging | 400 | 399 | 121 | 0 | 1.10e-13 | 5.35e-16 |
| Eigengap tol. | 400 | 399 | 0 | 0 | 0.00e+00 | 0.00e+00 |
| Eigengap tol. | 400 | 399 | 0 | 0 | 0.00e+00 | 0.00e+00 |
| Explicit deterministic ties | 400 | 399 | 121 | 0 | 1.10e-13 | 5.35e-16 |
| Design | Attempts | Usable | |||
|---|---|---|---|---|---|
| Balanced | 0 | 500 | 500/500 | 0.046 [0.029, 0.068] | 0.046 [0.029, 0.068] |
| 1 | 500 | 500/500 | 0.052 [0.034, 0.075] | 0.052 [0.034, 0.075] | |
| 2 | 500 | 500/500 | 0.158 [0.127, 0.193] | 0.158 [0.127, 0.193] | |
| 3 | 500 | 500/500 | 0.448 [0.404, 0.493] | 0.448 [0.404, 0.493] | |
| 4 | 500 | 500/500 | 0.832 [0.796, 0.864] | 0.832 [0.796, 0.864] | |
| 5 | 500 | 500/500 | 0.952 [0.929, 0.969] | 0.952 [0.929, 0.969] |
| Graph | Laplacian | Cond. | Attempts | ||||
|---|---|---|---|---|---|---|---|
| 16 | matched | 2099 | 0.953 [0.943, 0.962] | 0.050 [0.041, 0.060] | 0.048 [0.039, 0.058] | ||
| 16 | matched | 2101 | 0.952 [0.942, 0.961] | 0.056 [0.046, 0.066] | 0.053 [0.044, 0.063] | ||
| 16 | -NN | matched | 2000 | 1.000 [0.998, 1.000] | 0.048 [0.039, 0.058] | 0.048 [0.039, 0.058] | |
| 16 | -NN | graph | 2000 | 1.000 [0.998, 1.000] | 0.044 [0.036, 0.054] | 0.044 [0.036, 0.054] | |
| 16 | -NN | matched | 2000 | 1.000 [0.998, 1.000] | 0.048 [0.039, 0.058] | 0.048 [0.039, 0.058] | |
| 32 | matched | 2000 | 1.000 [0.998, 1.000] | 0.050 [0.041, 0.060] | 0.050 [0.041, 0.060] |
| Usable | Selective rejection | Operational joint | Naive rejection | Median truncation mass | |
|---|---|---|---|---|---|
| 0 | 1000/1000 | 0.050 [0.037, 0.065] | 0.050 [0.037, 0.065] | 0.447 [0.416, 0.478] | 0.03007 |
| 2 | 1000/1000 | 0.048 [0.036, 0.063] | 0.048 [0.036, 0.063] | 0.275 [0.248, 0.304] | 0.101 |
| 4 | 1000/1000 | 0.043 [0.031, 0.057] | 0.043 [0.031, 0.057] | 0.059 [0.045, 0.075] | 0.9171 |
| 5 | 1000/1000 | 0.054 [0.041, 0.070] | 0.054 [0.041, 0.070] | 0.051 [0.038, 0.067] | 1 |
| Conditioning event | mean | ||||
|---|---|---|---|---|---|
| Pair appears | 500 | 0.526 | 0.012 | 0.046 | 0.104 |
| Two largest | 500 | 0.526 | 0.012 | 0.046 | 0.104 |
| Full partition | 500 | 0.526 | 0.012 | 0.046 | 0.104 |
| Realized graph | 500 | 0.518 | 0.008 | 0.042 | 0.096 |
| Graph | Laplacian | Cond. | mean | KS | |||
|---|---|---|---|---|---|---|---|
| 16 | -NN | Matched | 2000 | 0.499 | 0.048 [0.039, 0.058] | 0.896 | |
| 16 | -NN | Graph | 2000 | 0.499 | 0.044 [0.036, 0.054] | 0.802 | |
| 16 | -NN | Matched | 2000 | 0.498 | 0.048 [0.039, 0.058] | 0.977 | |
| 16 | Matched | 2000 | 0.499 | 0.056 [0.046, 0.066] | 0.992 | ||
| 16 | Matched | 2000 | 0.498 | 0.050 [0.041, 0.060] | 0.571 | ||
| 32 | -NN | Matched | 2000 | 0.502 | 0.043 [0.035, 0.053] | 0.817 |
| Design | Method | ||||||
|---|---|---|---|---|---|---|---|
| balanced | Matched selective | 0.046 | 0.052 | 0.158 | 0.448 | 0.832 | 0.952 |
| balanced | Graph-conditioned | 0.050 | 0.042 | 0.068 | 0.134 | 0.418 | 0.660 |
| balanced | Gaussian thinning | 0.046 | 0.086 | 0.234 | 0.728 | 0.964 | 0.998 |
| mildly unbalanced | Matched selective | 0.054 | 0.058 | 0.172 | 0.486 | 0.842 | 0.958 |
| mildly unbalanced | Graph-conditioned | 0.060 | 0.038 | 0.076 | 0.216 | 0.512 | 0.770 |
| mildly unbalanced | Gaussian thinning | 0.054 | 0.072 | 0.292 | 0.808 | 0.976 | 0.992 |
| Scale used in pivot | Theorem-backed? | mean | KS | ||
|---|---|---|---|---|---|
| True | Yes | 500 | 0.497 | 0.056 [0.038, 0.080] | 0.765 |
| Same-data plug-in | No | 500 | 0.496 | 0.052 [0.034, 0.075] | 0.701 |
| Independent-pilot | No | 500 | 0.496 | 0.056 [0.038, 0.080] | 0.744 |
| No | 500 | 0.457 | 0.078 [0.056, 0.105] | 0.003 | |
| No | 500 | 0.533 | 0.042 [0.026, 0.063] | 0.016 |
| Scenario | Theorem-backed? | mean | KS | ||
|---|---|---|---|---|---|
| Gaussian, spherical | Yes | 300 | 0.486 | 0.073 [0.047, 0.109] | 0.501 |
| Standardized | No | 300 | 0.530 | 0.013 [0.004, 0.034] | 0.081 |
| Gaussian, correlated features | No | 300 | 0.408 | 0.143 [0.106, 0.188] | 0.000 |
| Scenario | Theorem | Usable | Rejection | Operational joint | KS | Median truncation mass |
|---|---|---|---|---|---|---|
| Spherical Gaussian | Yes | 500/500 | 0.052 [0.034, 0.075] | 0.052 | 0.809 | 6.57e-05 |
| Row heteroskedastic | No | 500/500 | 0.052 [0.034, 0.075] | 0.052 | 0.253 | 9.23e-05 |
| Row-correlated ( ) | No | 500/500 | 0.028 [0.015, 0.047] | 0.028 | 0.00112 | 0.000604 |
| Feature-correlated ( ) | No | 500/500 | 0.066 [0.046, 0.091] | 0.066 | 0.472 | 6.86e-05 |
| Feature-correlated ( ) | No | 500/500 | 0.068 [0.048, 0.094] | 0.068 | 0.0214 | 2.71e-05 |
| Feature-correlated ( ) | No | 500/500 | 0.144 [0.114, 0.178] | 0.144 | 4e-15 | 1.92e-05 |
| Graph | Reps | Breakpoints | Intervals | Solves | Skipped | Time (s) | Peak MB | Fail | ||
|---|---|---|---|---|---|---|---|---|---|---|
| eps | 5 | 16 | 3 | 72 | 73 | 73 | 0.0% | 0.04 | 0.1 | 0.0% |
| eps | 5 | 32 | 3 | 297 | 298 | 298 | 0.0% | 0.21 | 0.2 | 0.0% |
| eps | 5 | 64 | 3 | 1176 | 1177 | 1177 | 0.0% | 1.22 | 0.7 | 0.0% |
| eps | 5 | 128 | 3 | 4877 | 4878 | 4878 | 0.0% | 25.53 | 2.5 | 0.0% |
| eps | 20 | 16 | 2 | 39 | 40 | 40 | 0.0% | 0.03 | 0.1 | 33.3% |
| eps | 20 | 32 | 3 | 237 | 238 | 238 | 0.0% | 0.16 | 0.3 | 0.0% |
| Graph | Candidate intervals | Spectral solves | Total sec. | Graph walk | Eigen/rounding | |
|---|---|---|---|---|---|---|
| 32 | 273 | 273.3 | 0.06 | 9.4% | 87.8% | |
| 64 | 1,186 | 1,186.0 | 0.56 | 6.8% | 92.8% | |
| 128 | 4,989 | 4,989.0 | 6.54 | 5.5% | 94.5% | |
| -NN | 32 | 6,890 | 107.3 | 0.18 | 83.9% | 13.9% |
| -NN | 64 | 59,083 | 240.3 | 5.89 | 97.3% | 2.4% |
| -NN | 128 | 497,839 | 482.0 | 244.59 | 99.6% | 0.3% |
| Gene | Mean diff. | Naive value | Selective value | Adjusted selective value |
|---|---|---|---|---|
| LTB | 1.27 | 6.61e-06 | 9.72e-06 | 1.56e-04 |
| CD3E | 1.40 | 6.98e-07 | 2.44e-04 | 3.90e-03 |
| IL7R | 1.05 | 2.15e-04 | 4.29e-04 | 6.87e-03 |
| CCR7 | 0.93 | 9.99e-04 | 4.44e-03 | 7.10e-02 |
| CD74 | -0.87 | 2.20e-03 | 4.95e-03 | 7.93e-02 |
| CD3D | 1.54 | 5.41e-08 | 7.14e-03 | 1.14e-01 |
Selective Inference
Selective inference develops valid statistical conclusions after data-dependent choices such as feature selection, clustering, or adaptive evaluation.
See all 25 papers