A likelihood-ratio type test for stochastic block models with bounded degrees

Mingao Yuan, Yang Feng, Zuofeng Shang

TL;DR

This paper introduces a novel statistical test for detecting community structures in sparse networks where node degrees are limited. They propose a regularized likelihood-ratio test that overcomes limitations of existing methods, particularly in the "bounded-degree" regime, and demonstrate its effectiveness through simulations and real-world data analysis.

What Problem Does This Paper Address?

Network analysis often involves understanding community structures. A common task is to distinguish between a random graph (Erdös-Rényi model) and a graph with underlying communities (Stochastic Block Model, SBM). While much research has focused on networks where node degrees grow with the network size (the "growing-degree regime"), many real-world networks are "sparse" with bounded degrees. Existing statistical tests struggle in this bounded-degree scenario, often becoming unreliable or computationally intractable. This paper addresses this gap by developing a statistically sound and practical test for SBMs in the bounded-degree regime.

Methods

The core contribution is a regularized likelihood-ratio (LR) test. The standard LR test for this problem suffers from asymptotic orthogonality between the null (random graph) and alternative (SBM) hypotheses, making it unreliable. The authors introduce a regularization parameter ($\epsilon$) into the LR statistic to stabilize it and make it asymptotically valid.

They derive the asymptotic distributions of their test statistic under both the null and alternative hypotheses. These distributions are shown to be power Poisson laws, which are unique to sparse networks with bounded degrees. This theoretical framework allows them to analyze the test's power.

To address computational challenges, they also propose a Monte Carlo approximation method for the test statistic, making it more practical for larger networks. The proofs rely on a contiguity theory for random graphs developed by Janson.

Datasets

The paper uses simulated network data generated from both Erdös-Rényi and bisection SBM models to evaluate the performance of their proposed test. They also apply their method to a real-world dataset: the political book data from [23], which has been previously analyzed in network research.

Key Insights and Ideas

  • Bounded degrees matter: The behavior of statistical tests changes significantly when node degrees are bounded compared to when they grow. Existing methods designed for growing degrees fail here.
  • Regularization is key: Introducing a regularization parameter is crucial for making the likelihood-ratio test robust and statistically valid in sparse networks.
  • Power Poisson laws are unique: The asymptotic distributions of tests in this regime are power Poisson, differing from the Tracy-Widom or Gaussian distributions seen in other network settings.
  • Trade-off between theory and practice: While the theoretical test is powerful, its direct computation is expensive. Monte Carlo methods offer a practical workaround.

Key Results

  • The proposed $\epsilon$-LR test is shown to have valid asymptotic distributions (power Poisson laws) under both null and alternative hypotheses in the bounded-degree regime.
  • The test's power increases with the signal-to-noise ratio ($\kappa$) and can approach one when $\kappa$ is large.
  • The Monte Carlo approximation is shown to be valid under certain conditions on the number of samples, significantly reducing computational cost.
  • In simulations, the $\epsilon$-LR test demonstrates desirable size (correctly rejecting the null when it's false) and power, outperforming existing spectral and subgraph count methods, especially in sparse settings.
  • On the political book data, the $\epsilon$-LR test successfully identified community structures, showing strong performance compared to other methods.

Limitations and Future Work

  • Multi-community extension: The current work focuses on a bisection (two-community) SBM. The authors note that extending this to multi-community settings is an important but non-trivial future direction, as suggested by related work [11].
  • Computational cost: While Monte Carlo approximations help, the computational burden can still be significant. The paper mentions mean-field approximations as a potential avenue for further efficiency improvements, drawing parallels to statistical physics models.
  • Parameter selection: While the regularization parameter $\epsilon$ can be empirically selected, the optimal choice might still require careful consideration.
  • Theoretical assumptions: The proofs rely on specific contiguity theories and assumptions about network properties. Extending these results to more complex network models might require new theoretical tools.

Summary updated

Abstract

<p>A fundamental problem in network data analysis is to test Erdös–Rényi model [Formula presented] versus a bisection stochastic block model [Formula presented], where a,b&gt;0 are constants that represent the expected degrees of the graphs and n denotes the number of nodes. This problem serves as the foundation of many other problems such as testing-based methods for determining the number of communities (Bickel and Sarkar, 2016; Lei, 2016) and community detection (Montanari and Sen, 2016). Existing work has been focusing on growing-degree regime a,b→∞ (Bickel and Sarkar, 2016; Lei, 2016; Montanari and Sen, 2016; Banerjee and Ma, 2017; Banerjee, 2018; Gao and Lafferty, 2017a,b) while leaving the bounded-degree regime untreated. In this paper, we propose a likelihood-ratio (LR) type procedure based on regularization to test stochastic block models with bounded degrees. We derive the limit distributions as power Poisson laws under both null and alternative hypotheses, based on which the limit power of the test is carefully analyzed. We also examine a Monte-Carlo method that partly resolves the computational cost issue. The proposed procedures are examined by both simulated and real-world data. The proof depends on a contiguity theory developed by Janson (1995).</p>
BibTeX
@article{yuan2022likelihood,
  author = {Mingao Yuan and Yang Feng and Zuofeng Shang},
  title = {{A likelihood-ratio type test for stochastic block models with bounded degrees}},
  journal = {Journal of Statistical Planning and Inference},
  year = {2022},
  url = {https://openreview.net/forum?id=Wz0xpjhkDP},
}
Figure