Finite-sample confidence regions for spectral clustering and graph centrality
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910018793635840 |
|---|---|
| author | Gokavarapu, Chandrasekhar Gosala, Sekhar Babu Pasalapudi, Vamis Kapakayala, Tarakarama |
| author_facet | Gokavarapu, Chandrasekhar Gosala, Sekhar Babu Pasalapudi, Vamis Kapakayala, Tarakarama |
| contents | Let a graph be observed through a finite random sampling mechanism. Spectral methods are routinely applied to such graphs, yet their outputs are treated as deterministic objects. This paper develops finite-sample inference for spectral graph procedures.
The primary result constructs explicit confidence regions for latent eigenspaces of graph operators under an explicit sampling model. These regions propagate to confidence regions for spectral clustering assignments and for smooth graph centrality functionals. All bounds are nonasymptotic and depend explicitly on the sample size, noise level, and spectral gap.
The analysis isolates a failure of common practice: asymptotic perturbation arguments are often invoked without a finite-sample spectral gap, leading to invalid uncertainty claims. Under verifiable gap and concentration conditions, the present framework yields coverage guarantees and certified stability regions. Several corollaries address fairness-constrained post-processing and topological summaries derived from spectral embeddings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10566 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Finite-sample confidence regions for spectral clustering and graph centrality Gokavarapu, Chandrasekhar Gosala, Sekhar Babu Pasalapudi, Vamis Kapakayala, Tarakarama Statistics Theory Combinatorics Rings and Algebras Spectral Theory 62G15, 62H30, 05C80, 15A18, 68Q32 Let a graph be observed through a finite random sampling mechanism. Spectral methods are routinely applied to such graphs, yet their outputs are treated as deterministic objects. This paper develops finite-sample inference for spectral graph procedures. The primary result constructs explicit confidence regions for latent eigenspaces of graph operators under an explicit sampling model. These regions propagate to confidence regions for spectral clustering assignments and for smooth graph centrality functionals. All bounds are nonasymptotic and depend explicitly on the sample size, noise level, and spectral gap. The analysis isolates a failure of common practice: asymptotic perturbation arguments are often invoked without a finite-sample spectral gap, leading to invalid uncertainty claims. Under verifiable gap and concentration conditions, the present framework yields coverage guarantees and certified stability regions. Several corollaries address fairness-constrained post-processing and topological summaries derived from spectral embeddings. |
| title | Finite-sample confidence regions for spectral clustering and graph centrality |
| topic | Statistics Theory Combinatorics Rings and Algebras Spectral Theory 62G15, 62H30, 05C80, 15A18, 68Q32 |
| url | https://arxiv.org/abs/2602.10566 |