Title: 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.