# Optimal hypothesis testing for stochastic block models with growing degrees

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2017.

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

- [Testing network correlation efficiently via counting trees](https://mlsanity.com/paper/2110.11816/) (2021)
- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)
- [Network Estimation by Mixing: Adaptivity and More](https://mlsanity.com/paper/2106.02803/) (2021)
- [Precise Error Rates for Computationally Efficient Testing](https://mlsanity.com/paper/2311.00289/) (2023)
- [Low degree conjecture implies sharp computational thresholds in stochastic block model](https://mlsanity.com/paper/2502.15024/) (2025)
- [Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models](https://mlsanity.com/paper/2602.08173/) (2026)
- [Higher-order accurate two-sample network inference and network hashing](https://mlsanity.com/paper/2208.07573/) (2022)
- [SIMPLE-RC: Group Network Inference with Non-Sharp Nulls and Weak Signals](https://mlsanity.com/paper/2211.00128/) (2022)
- [Detection problems in the spiked matrix models](https://mlsanity.com/paper/2301.05331/) (2023)
- [Counting Cycles with AI: Counting Cycles with AI: Computationally Efficient Equivalent Forms with Applications](https://mlsanity.com/paper/2505.17964/) (2025)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)
- [A Smooth Computational Transition in Tensor PCA](https://mlsanity.com/paper/2509.09904/) (2025)
- [Two-Sample Testing for Random Graphs without Vertex Correspondence](https://mlsanity.com/paper/2610.07503/) (2026)

## Abstract (arXiv)

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(n3 log n) time complexity in the contiguous regime when n2 pn,av3 →∞ where pn,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 pn,av →∞. These tests remain powerful when the alternative becomes a more general stochastic block model with more than two blocks.