Spectral Certificates Separate Accuracy From Inference

Spectral clustering and graph centrality are often reported from a single observed network as if the computed partition or ranking were the population answer. This paper asks a narrower inferential question: when does one graph support a nontrivial finite-sample confidence statement about the population eigenspace, clustering labels, or top-degree vertices? The answer is deliberately conservative. The protocol returns a coverage-guaranteed set when the data and declared model envelopes support one, and otherwise returns “no nontrivial certificate.”

Core Contribution

The main contribution is not a new clustering algorithm. It is an auditable certification pipeline for inhomogeneous Bernoulli graphs, with every constant in the operator-norm tail bound retained. The authors combine a Matrix-Bernstein quantile for $\lVert A-P\rVert$ with a one-sided spectral-gap certificate, then express uncertainty as a Grassmann ball around the observed top-$k$ eigenspace. The key editorial point is that the ball is reported as informative only when its raw radius is below one, the diameter of the Grassmannian under projector norm.

Figure 1 shows why that accounting matters: restoring the ambient dimension factor and numerical constants changes a previously plausible balanced-SBM example into a vacuous certificate.

Technical Approach

The sampling model fixes a symmetric Bernoulli probability matrix $P$ and observes an adjacency matrix $A$ with independent upper-triangular edges. For the selected eigenspace, the relevant population quantity is the boundary gap $g_k(P)=\lambda_k(P)-\lambda_{k+1}(P)$, not eigenvalue separation within the selected subspace. The Matrix-Bernstein quantile uses $x_{n,\alpha}=\log(2n/\alpha)$ and a variance envelope, producing a radius of the form $r_{raw}=2q/g$. The reported radius is capped at one, but the uncapped value is kept because it determines whether the certificate says anything useful.

The paper then propagates this eigenspace ball downstream. For clustering, it gives a certificate-bearing approximate $k$-means transfer: under declared population separation, minimum-cluster retention, and a verified approximation factor, the eigenspace ball becomes a permutation-invariant Hamming ball for labels. For centrality, the authors derive simultaneous degree bands and an observed-gap rule for top-$m$ selection. A corrected normalized-Katz extension is also included; the correction matters because the Lipschitz bound needs the normalized seed and the previously omitted $\sqrt{n}$ factor.

Results and Analysis

The numerical results are best read as an operating-envelope study, not as a claim that the method often certifies common small graphs. In the balanced two-block SBM with $p=0.30$, $q=0.10$, $n=200$, and $\alpha=0.05$, the exact variance calculation gives $v(P)=29.79$, $g_2(P)=20$, $q_{200,0.05}=29.131$, and $r_{raw}=2.913$. The confidence set is therefore the whole Grassmannian. With the exact variance, the first even $n$ at which the subspace radius falls below one is 1,610; the degree-envelope version crosses at 2,106; the mean-square Hamming clustering certificate does not become available until $n=58,508$.

Figure 3 makes the central empirical distinction visible. Across 12 simulation cells with 1,000 graphs each, empirical subspace coverage is 1.000 in every row, while the realized Grassmann errors are far smaller than the certified radii. At $n=200$, $p=0.30$, $q=0.10$, the mean realized error is 0.270 and the 95th percentile is 0.293, but the corrected certified radius is 2.913 and therefore capped at one. Only 1 of the 12 cells has a nontrivial subspace certificate, and none has the model-envelope Hamming certificate.

The bootstrap comparison is useful because it shows the price of distribution-free finite-sample validity. At $n=200$, $p=0.30$, $q=0.10$, the analytic certificate has empirical coverage 1.000 with mean radius 1.000. A plug-in SBM bootstrap also covers all 100 outer targets with mean radius 0.402, while a simplified ASE-$k$NN bootstrap has mean radius 0.288 but only 0.870 coverage. The smaller number is not automatically better; it changes the inferential contract.

The real-network diagnostic reaches the same conclusion. On the 34-node Zachary karate-club network, spectral $k$-means makes one label error after permutation, giving 0.971 agreement with the recorded factions. But the certified gap test fails: the boundary gap is 2.061, the split-level operator quantile is 28.119, and the Weyl lower bound is negative. Degree centrality also fails because the observed top-two degree margin is 1, below twice the simultaneous half-width 16.695. The method is doing what it is designed to do: separate a good descriptive fit from a finite-sample confidence claim.

Limits in Practice

The guarantees assume a fixed Bernoulli probability matrix and independent edges. They do not cover temporal dependence, degree-preserving sampling, missing edges, or choosing the network after looking at the data. The certificates are also uniform operator-norm statements, so they ignore graph-specific entrywise structure that may make a particular SBM or random-dot-product graph easier. Ordinary Lloyd $k$-means is used descriptively in the simulations, but it does not itself verify the approximation factor required by the clustering theorem. The practical value is therefore clearest for analysts willing to report both the computed network summary and the diagnostic saying whether that summary is certifiable.