Estimating Graph Dimension with Cross-validated Eigenvalues

Abstract

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.

63 pages, 12 figures

References in corpus (18)

• Stochastic blockmodels and community structure in networks
• Level-Spacing Distributions and the Airy Kernel
• Spectral redemption: clustering sparse networks
• Matrix estimation by Universal Singular Value Thresholding
• Spectral Statistics of Erd{\H o}s-Rényi Graphs II: Eigenvalue Spacing and the Extreme Eigenvalues
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Understanding Regularized Spectral Clustering via Graph Conductance
• Construction of the Literature Graph in Semantic Scholar
• Estimating the number of communities in networks by spectral methods
• Bootstrapping Networks with Latent Space Structure
• Using bootstrap for statistical inference on random graphs
• Determining the Number of Communities in Degree-corrected Stochastic Block Models
• Consistency of Maximum Likelihood for Continuous-Space Network Models I
• Bootstrapping Exchangeable Random Graphs
• A central limit theorem for scaled eigenvectors of random dot product graphs
• On the Theoretical Properties of the Network Jackknife
• Community Detection Based on the $L_{\infty }$ convergence of eigenvectors in DCBM
• A note on quickly sampling a sparse matrix with low rank expectation