View PDF HTML (experimental)

Abstract:Spectral clustering and node rankings are commonly reported from one observed network without a finite-sample statement of what the observation supports. We develop a certification protocol that either returns a coverage-guaranteed set or explicitly returns ``no nontrivial certificate.'' For an inhomogeneous Bernoulli graph, a matrix-Bernstein quantile with all numerical constants and its ambient-dimension factor retained is combined with a one-sided spectral-gap certificate. The resulting Grassmann ball is valid at finite \(n\), but is reported as informative only when its radius is below the
diameter of the Grassmannian. We propagate the ball through a
certificate-bearing approximate \(k\)-means map under declared population
separation and minimum-cluster envelopes, derive simultaneous bands and an observed-gap certificate for degree centrality, and give a corrected normalized-Katz extension. A \(12\)-cell simulation study with \(1{,}000\) graphs per cell maps the difference between coverage and usefulness. The submitted \(n=200\) block-model example is shown to be necessarily vacuous after the dimension factor is restored; in the benchmark \(p=0.30,q=0.10\), the
subspace radius first falls below one at
\(n=\ExactRadiusThreshold\), whereas the mean-square clustering certificate
remains unavailable until \(n=\HammingThreshold\). An unequal-block example produces a genuine centrality certificate, while an analysis of the Zachary karate-club network correctly declines to certify despite \(97.1\%\) agreement with the observed factions. These results separate algorithmic success, coverage validity and inferential informativeness.

Submission history

From: Chandrasekhar Gokavarapu [view email]
[v1] Wed, 11 Feb 2026 06:35:08 UTC (36 KB)
[v2] Wed, 29 Jul 2026 15:41:56 UTC (114 KB)