Spectral clustering of network time series via the sample covariance matrix

2026/08/03 by Brendan Martin, Joshua Agterberg, Mihai Cucuringu +2
Mathematics · #math.ST #stat.ME #stat.TH

paper · pdf

arxiv created 2026/08/03 · arxiv updated 2026/08/05

Abstract

Spectral clustering for community detection is analysed in multivariate time series models whose dependence structure is determined by an unobserved stochastic blockmodel. We establish that spectral clustering of the sample covariance matrix achieves exact recovery of the underlying communities. The recovery rates depend explicitly on the network size, sample length, block separation, and degree of data dependence. This demonstrates that exact community recovery under a stochastic blockmodel is possible even when the adjacency matrix is unobserved. Our theory provides extensions of both classical and fine-grained matrix perturbation theory to the setting of dependent data, which may be of independent interest.

Citations

• When can weak latent factors be statistically inferred?
• An Overview of Asymptotic Normality in Stochastic Blockmodels: Cluster Analysis and Inference
• Optimal Network Membership Estimation Under Severe Degree Heterogeneity
• On the Non-Asymptotic Concentration of Heteroskedastic Wishart-type Matrix
• Statistical inference for principal components of spiked covariance matrices
• Heteroskedastic PCA: Algorithm, Optimality, and Applications
• Strong Consistency of Spectral Clustering for Stochastic Block Models
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Community Detection and Stochastic Block Models
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• An Introduction to Matrix Concentration Inequalities
• Consistency of spectral clustering in stochastic block models
• Regularized estimation in sparse high-dimensional time series models
• Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding
• Oracle Inequalities for High Dimensional Vector Autoregressions
• Bernstein inequality and moderate deviations under strong mixing conditions
• A generalized Isserlis theorem for location mixtures of Gaussian random vectors
• Stochastic blockmodels and community structure in networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• Clustering with Spectral Norm and the k-means Algorithm
• A Bernstein type inequality and moderate deviations for weakly dependent sequences
• Mixed membership stochastic blockmodels
• Basic Properties of Strong Mixing Conditions. A Survey and Some Open Questions
• On the distribution of the largest eigenvalue in principal components analysis
• Stochastic blockmodels: First steps
• The Rotation of Eigenvectors by a Perturbation. III