# Estimating Graph Dimension with Cross-validated Eigenvalues

arXiv: https://arxiv.org/abs/2108.03336 · HTML: https://mlsanity.com/paper/2108.03336/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 70 references that are in the map.
- First posted on arXiv 6 Aug 2021.

## Builds on (most cited first, 24 of 24)

- [Construction of the Literature Graph in Semantic Scholar](https://mlsanity.com/paper/1805.02262/) (2018)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs](https://mlsanity.com/paper/1501.06087/) (2015)
- [Network cross-validation by edge sampling](https://mlsanity.com/paper/1612.04717/) (2016)
- [Impact of regularization on Spectral Clustering](https://mlsanity.com/paper/1312.1733/) (2013)
- [Concentration and regularization of random graphs](https://mlsanity.com/paper/1506.00669/) (2015)
- [Network Cross-Validation for Determining the Number of Communities in Network Data](https://mlsanity.com/paper/1411.1715/) (2014)
- [A goodness-of-fit test for stochastic block models](https://mlsanity.com/paper/1412.4857/) (2014)
- [Vintage Factor Analysis with Varimax Performs Statistical Inference](https://mlsanity.com/paper/2004.05387/) (2020)
- [Hypothesis Testing for Automated Community Detection in Networks](https://mlsanity.com/paper/1311.2694/) (2013)
- [Understanding Regularized Spectral Clustering via Graph Conductance](https://mlsanity.com/paper/1806.01468/) (2018)
- [Determining the Number of Communities in Degree-corrected Stochastic Block Models](https://mlsanity.com/paper/1809.01028/) (2018)
- [Subsampling bootstrap of count features of networks](https://mlsanity.com/paper/1312.2645/) (2013)
- [Optimal Bipartite Network Clustering](https://mlsanity.com/paper/1803.06031/) (2018)
- [Strong Consistency of Spectral Clustering for Stochastic Block Models](https://mlsanity.com/paper/1710.06191/) (2017)
- [Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms](https://mlsanity.com/paper/1503.00609/) (2015)
- [Subsampling Sparse Graphons Under Minimal Assumptions](https://mlsanity.com/paper/1907.12528/) (2019)
- [A unified view of generative models for networks: models, methods, opportunities, and challenges](https://mlsanity.com/paper/1411.4070/) (2014)
- [Edge-exchangeable graphs and sparsity (NIPS 2016)](https://mlsanity.com/paper/1612.05519/) (2016)
- [On the Theoretical Properties of the Network Jackknife](https://mlsanity.com/paper/2004.08935/) (2020)
- [A central limit theorem for scaled eigenvectors of random dot product graphs](https://mlsanity.com/paper/1305.7388/) (2013)
- [Community Detection Based on the L_∞ convergence of eigenvectors in DCBM](https://mlsanity.com/paper/1906.06713/) (2019)

## Built on by (most cited first, 6 of 6)

- [Data thinning for convolution-closed distributions](https://mlsanity.com/paper/2301.07276/) (2023)
- [T-Stochastic Graphs](https://mlsanity.com/paper/2309.01301/) (2023)
- [Spectral embedding and the latent geometry of multipartite networks](https://mlsanity.com/paper/2202.03945/) (2022)
- [Optimizing the Induced Correlation in Omnibus Joint Graph Embeddings](https://mlsanity.com/paper/2409.17544/) (2024)
- [Enhancing Blind Source Separation with Dissociative Principal Component Analysis](https://mlsanity.com/paper/2411.12321/) (2024)
- [Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)](https://mlsanity.com/paper/2506.02825/) (2025)

## Abstract (arXiv)

In applied multivariate statistics, estimating the number of latent dimensions or the number of clusters, k, is a fundamental and recurring problem. We study a sequence of statistics called "cross-validated eigenvalues." Under a large class of random graph models, including both Poisson and Bernoulli edges, without parametric assumptions, we provide a p-value for each cross-validated eigenvalue. It tests the null hypothesis that the sample eigenvector is orthogonal to (i.e., uncorrelated with) the true latent dimensions. This approach naturally adapts to problems where some dimensions are not statistically detectable. In scenarios where all k dimensions can be estimated, we show that our procedure consistently estimates k. In simulations and data example, the proposed estimator compares favorably to alternative approaches in both computational and statistical performance.