Optimal hypothesis testing for stochastic block models with growing degrees

Abstract

The present paper considers testing an Erdos--Renyi random graph model against a stochastic block model in the asymptotic regime where the average degree of the graph grows with the graph size n. Our primary interest lies in those cases in which the signal-to-noise ratio is at a constant level. Focusing on symmetric two block alternatives, we first derive joint central limit theorems for linear spectral statistics of power functions for properly rescaled graph adjacency matrices under both the null and local alternative hypotheses. The powers in the linear spectral statistics are allowed to grow to infinity together with the graph size. In addition, we show that linear spectral statistics of Chebyshev polynomials are closely connected to signed cycles of growing lengths that determine the asymptotic likelihood ratio test for the hypothesis testing problem of interest. This enables us to construct a sequence of test statistics that achieves the exact optimal asymptotic power within $O(n^3\log n)$ time complexity in the contiguous regime when $n^2{p}_{n,av}^3\to \infty$ where $p_{n,av}$ is the average connection probability. We further propose a class of adaptive tests that are computationally tractable and completely data-driven. They achieve nontrivial powers in the contiguous regime and consistency in the singular regime whenever $n{p}_{n,av}\to \infty$. These tests remain powerful when the alternative becomes a more general stochastic block model with more than two blocks.

References in corpus (15)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Parsimonious module inference in large networks
• Spectral Statistics of Erd{\H o}s-Rényi Graphs II: Eigenvalue Spacing and the Extreme Eigenvalues
• The largest eigenvalue of rank one deformation of large Wigner matrices
• Asymptotic power of sphericity tests for high-dimensional data
• Optimal hypothesis testing for high dimensional covariance matrices
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Estimating the number of communities in networks by spectral methods
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Information-theoretic thresholds for community detection in sparse networks
• Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence
• Sharp detection in PCA under correlations: all eigenvalues matter
• Community Detection in Degree-Corrected Block Models
• Network Cross-Validation for Determining the Number of Communities in Network Data
• Comparison of Cross-Validation Methods for Stochastic Block Models

Cited by in corpus (14)

• Statistical inference for network samples using subgraph counts
• Testing network correlation efficiently via counting trees
• Two-sample Test of Community Memberships of Weighted Stochastic Block Models
• Testing Community Structures for Hypergraphs
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Weak Detection in the Spiked Wigner Model with General Rank
• Universal Rank Inference via Residual Subsampling with Application to Large Networks
• Asymptotic normality and analysis of variance of log-likelihood ratios in spiked random matrix models
• Weak detection in the spiked Wigner model
• Testing Changes in Communities for the Stochastic Block Model
• Central limit theorem for linear spectral statistics of block-Wigner-type matrices
• Random geometric graphs and the spherical Wishart matrix
• Permutation Tests for Infection Graphs
• Precise Error Rates for Computationally Efficient Testing