Finite-sample certification and operating envelopes for spectral clustering and graph centrality

Chandrasekhar Gokavarapu, Sekhar Babu Gosala, Rajeev Muthu, Vamsi Pasalapudi, Tarakarama Kapakayala

arXivarxiv/2602.10566Feb 11, 2026math.STscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2602.10566
curl -X POST /api/v1/records/arxiv/2602.10566/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.10566/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'