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 ε- 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.
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
{Ca,Cb}∈A(C(⋅)) for the reporting rule
primary test
Pair appearance
{Ca,Cb} appears among cluster pairs
valid when the pair is user chosen
Table 1: Conditioning levels used in the paper. The valid event must match the reported target; conditioning on more information is valid but can be conservative.
Setting
N
mean p
P(p≤.01)
P(p≤.05)
P(p≤.10)
KS p
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
Table 2: Primary type-I calibration under the global null for k -NN, Lsym , K=3 , and matched A2lg conditioning ( d=5 , σ=1 ). Brackets give exact binomial 95% confidence intervals for tail probabilities.
Figure 1: Quantile–quantile plot under the primary n=32,d=5 global-null configuration ( 5000 attempted and usable replicates). The gray band is the pointwise 95% beta band for uniform order statistics. Matched selective p -values track the diagonal, whereas the naive selected-cluster test collapses to the floor. The supporting n=18 plot is in the supplement.
Figure 2: Power curves for three Gaussian clusters under k -NN, Lsym , K=3 , and the two-largest target rule, with 500 fixed attempts per separation (all usable) and exact binomial 95% confidence intervals. Matched target-selection conditioning retains substantially more power than fixing the realized graph, while the naive test is already invalid at δ=0 .
Figure S1: Global-null p -value diagnostics for the n=18,d=5 primary design. The selective curves track the uniform reference; the naive curve reflects selection-induced anti-conservatism.
Alternative policy
Attempted
Evaluable
Set differences
Discrete changes
Max. ∣Δp∣
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. 10−10
400
399
0
0
0.00e+00
0.00e+00
Eigengap tol. 10−6
400
399
0
0
0.00e+00
0.00e+00
Explicit deterministic ties
400
399
121
0
1.10e-13
5.35e-16
Table S1: Aggregate numerical-sensitivity audit. “Set differences” counts comparisons with nonzero symmetric-difference probability mass between the two computed selection sets. “Discrete changes” counts changes in evaluation status, selected target, or eigengap validity.
Design
δ
Attempts
Usable
Pr(reject∣usable)
Pr(usable∩reject)
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]
Table S2: Operational usability and matched-rule power. Brackets are exact binomial 95% confidence intervals.
n
Graph
Laplacian
Cond.
Attempts
Pr(usable)
Pr(reject∣usable)
Pr(usable∩reject)
16
ε
Lrw
matched
2099
0.953 [0.943, 0.962]
0.050 [0.041, 0.060]
0.048 [0.039, 0.058]
16
ε
Lsym
matched
2101
0.952 [0.942, 0.961]
0.056 [0.046, 0.066]
0.053 [0.044, 0.063]
16
k -NN
Lrw
matched
2000
1.000 [0.998, 1.000]
0.048 [0.039, 0.058]
0.048 [0.039, 0.058]
16
k -NN
Lsym
graph
2000
1.000 [0.998, 1.000]
0.044 [0.036, 0.054]
0.044 [0.036, 0.054]
16
k -NN
Lsym
matched
2000
1.000 [0.998, 1.000]
0.048 [0.039, 0.058]
0.048 [0.039, 0.058]
32
ε
Lrw
matched
2000
1.000 [0.998, 1.000]
0.050 [0.041, 0.060]
0.050 [0.041, 0.060]
Table S3: Attempt-based operational quantities for graph and Laplacian variants. Brackets are exact binomial 95% confidence intervals.
δ
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
Table S4: Feature-wise partial-null calibration at nominal level .05. Brackets are exact binomial 95% confidence intervals.
Conditioning event
N
mean p
P(p≤.01)
P(p≤.05)
P(p≤.10)
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
Table S5: Target-rule equivalence sanity check under the global null ( n=32,d=5,K=3 , k -NN, Lsym , σ=1 ).
n
Graph
Laplacian
Cond.
N
mean p
P(p≤.05)
KS p
16
k -NN
Lsym
Matched
2000
0.499
0.048 [0.039, 0.058]
0.896
16
k -NN
Lsym
Graph
2000
0.499
0.044 [0.036, 0.054]
0.802
16
k -NN
Lrw
Matched
2000
0.498
0.048 [0.039, 0.058]
0.977
16
ε
Lsym
Matched
2000
0.499
0.056 [0.046, 0.066]
0.992
16
ε
Lrw
Matched
2000
0.498
0.050 [0.041, 0.060]
0.571
32
k -NN
Lsym
Matched
2000
0.502
0.043 [0.035, 0.053]
0.817
Table S6: Robustness matrix under the global null ( d=5 , K=3 ). Brackets give exact binomial 95% confidence intervals for the level .05 tail probability.
Design
Method
δ=0
1
2
3
4
5
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
Table S7: Rejection rates at level .05 for the matched selective test, graph-conditioned selective test, and Gaussian data-thinning baseline. Each entry uses 500 usable replicates. The thinning baseline controls type-I error but targets the randomized clustering of Xsel .
Scale used in pivot
Theorem-backed?
N
mean p
P(p≤.05)
KS p
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
0.9σ
No
500
0.457
0.078 [0.056, 0.105]
0.003
1.1σ
No
500
0.533
0.042 [0.026, 0.063]
0.016
Table S8: Scale sensitivity under the global null ( n=32,d=5,K=3 , k -NN, Lsym ). Brackets give exact binomial 95% confidence intervals for the level .05 tail probability.
Scenario
Theorem-backed?
N
mean p
P(p≤.05)
KS p
Gaussian, spherical
Yes
300
0.486
0.073 [0.047, 0.109]
0.501
Standardized t5
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
Table S9: Distributional stress tests under the global null ( n=32,d=5,K=3 , k -NN, Lsym ). Brackets give exact binomial 95% confidence intervals for the level .05 tail probability.
Scenario
Theorem
Usable
Rejection
Operational joint
KS p
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 ( ρ=.2 )
No
500/500
0.028 [0.015, 0.047]
0.028
0.00112
0.000604
Feature-correlated ( ρ=.1 )
No
500/500
0.066 [0.046, 0.091]
0.066
0.472
6.86e-05
Feature-correlated ( ρ=.25 )
No
500/500
0.068 [0.048, 0.094]
0.068
0.0214
2.71e-05
Feature-correlated ( ρ=.5 )
No
500/500
0.144 [0.114, 0.178]
0.144
4e-15
1.92e-05
Table S10: Fixed-attempt model-scope diagnostics at nominal level .05. Brackets are exact binomial 95% confidence intervals. The KS column tests the full p -value distribution against uniformity.
Graph
d
n
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%
Table S11: Scaling diagnostics for the finite-state homotopy computation under the global null. Entries are averages over successful replicates; Reps is the number of successful replicates used in the averages, and Fail is the fraction of attempted replicates that failed the deterministic validity checks. Peak memory is Python-side tracemalloc peak memory.
Graph
n
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%
k -NN
32
6,890
107.3
0.18
83.9%
13.9%
k -NN
64
59,083
240.3
5.89
97.3%
2.4%
k -NN
128
497,839
482.0
244.59
99.6%
0.3%
Table S12: Component timing for the current proof-of-concept implementation (three fixed attempts per graph/ n cell). Percentages are fractions of total wall-clock time in the recorded environment and are not hardware-independent complexity constants.
Figure S2: Scaling of runtime, candidate breakpoint intervals, and spectral solves for d=5 and d=20 . The main paper reports the same diagnostics in compressed form; Table S11 gives the numerical summaries. This figure visualizes the separation between candidate intervals and graph states requiring spectral recomputation.
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
Table S13: Smallest working-model feature-wise values in the fixed 16-gene PBMC panel. “Adjusted” means Bonferroni multiplication within this fixed panel. The table is an algorithmic diagnostic, not confirmatory biological inference.
Figure S3: Working-model PBMC diagnostics. Left: naive versus feature-wise selective values. Right: genes ranked by the working-model selective value. The plots illustrate numerical execution only; they do not establish marker significance under a defensible PBMC sampling model.