mlsanityData to 7 Oct 2026

Estimating Graph Dimension with Cross-validated Eigenvalues

arXiv 2108.03336 ↗First posted 6 Aug 2021stat.ME cs.LG cs.SIcited by 6

Not on the map. Why?

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.

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

Builds on

24 of 70 references.

References · 24

  1. 2018Construction of the Literature Graph in Semantic Scholarcited by 118
  2. 2014Exact Recovery in the Stochastic Block Modelcited by 77
  3. 2013Spectral redemption: clustering sparse networkscited by 54
  4. 2013Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodelcited by 45
  5. 2015Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphscited by 26
  6. 2016Network cross-validation by edge samplingcited by 26
  7. 2013Impact of regularization on Spectral Clusteringcited by 25
  8. 2015Concentration and regularization of random graphscited by 24
  9. 2014Network Cross-Validation for Determining the Number of Communities in Network Datacited by 21
  10. 2014A goodness-of-fit test for stochastic block modelscited by 20
  11. 2020Vintage Factor Analysis with Varimax Performs Statistical Inferencecited by 16
  12. 2013Hypothesis Testing for Automated Community Detection in Networkscited by 15
12 more
  1. 2018Understanding Regularized Spectral Clustering via Graph Conductancecited by 14
  2. 2018Determining the Number of Communities in Degree-corrected Stochastic Block Modelscited by 10
  3. 2013Subsampling bootstrap of count features of networkscited by 8
  4. 2018Optimal Bipartite Network Clusteringcited by 8
  5. 2017Strong Consistency of Spectral Clustering for Stochastic Block Modelscited by 7
  6. 2015Community detection in general stochastic block models: fundamental limits and efficient recovery algorithmscited by 5
  7. 2019Subsampling Sparse Graphons Under Minimal Assumptionscited by 5
  8. 2014A unified view of generative models for networks: models, methods, opportunities, and challengescited by 3
  9. 2016Edge-exchangeable graphs and sparsity (NIPS 2016)cited by 3
  10. 2020On the Theoretical Properties of the Network Jackknifecited by 3
  11. 2013A central limit theorem for scaled eigenvectors of random dot product graphscited by 2
  12. 2019Community Detection Based on the L_∞ convergence of eigenvectors in DCBMcited by 2

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2; 2024: 2; 2025: 1.

6 papers.

  1. 2023Data thinning for convolution-closed distributionscited by 12
  2. 2023T-Stochastic Graphscited by 1
  3. 2022Spectral embedding and the latent geometry of multipartite networkscited by 0
  4. 2024Optimizing the Induced Correlation in Omnibus Joint Graph Embeddingscited by 0
  5. 2024Enhancing Blind Source Separation with Dissociative Principal Component Analysiscited by 0
  6. 2025Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)cited by 0