Source-linked AI summary
Likelihood-based model selection for stochastic block models
Y. X. Rachel Wang, Peter J. Bickel
TL;DR
Choosing the number of communities in an SBM has received less attention than estimating labels and parameters. The paper analyzes likelihood-ratio behavior under underfitting and overfitting, then uses those rates to construct a consistent penalized-likelihood criterion. The results also cover polylogarithmically growing average degree and extend to the DCSBM.
Problem
Selecting the number of blocks remains less studied than estimating SBM labels and parameters, although existing estimation methods require K to be known or suitably bounded beforehand.
Method
The paper analyzes the maximum log likelihood and likelihood-ratio statistic under model misspecification, then constructs a penalized likelihood criterion from the resulting rates.
Results
The statistic is asymptotically normal under underfitting, has a derived convergence rate under overfitting, and yields an asymptotically consistent criterion.
Takeaways & Limitations
The criterion can be applied using variational likelihoods or consistent label-estimation algorithms, including for regular SBM and DCSBM settings.
Takeaways & Limitations
The analysis assumes a fixed true block number as the number of nodes grows, while practical networks may have an increasing number of communities.
Abstract
from arXiv · showhide
The stochastic block model (SBM) provides a popular framework for modeling community structures in networks. However, more attention has been devoted to problems concerning estimating the latent node labels and the model parameters than the issue of choosing the number of blocks. We consider an approach based on the log likelihood ratio statistic and analyze its asymptotic properties under model misspecification. We show the limiting distribution of the statistic in the case of underfitting is normal and obtain its convergence rate in the case of overfitting. These conclusions remain valid when the average degree grows at a polylog rate. The results enable us to derive the correct order of the penalty term for model complexity and arrive at a likelihood-based model selection criterion that is asymptotically consistent. Our analysis can also be extended to a degree-corrected block model (DCSBM). In practice, the likelihood function can be estimated using more computationally efficient variational methods or consistent label estimation algorithms, allowing the criterion to be applied to large networks.
1. Introduction.
Networks often contain communities, motivating generative models such as the SBM, but selecting the number of blocks remains an important unresolved problem. This paper addresses that problem through asymptotic analysis of likelihood under misspecification and proposes a consistent penalized-likelihood criterion.
- Communities are groups of nodes with high internal connectivity that provide a natural division of networks into subunits.
- Generative models are needed to study community detection from a theoretical perspective, beyond heuristic algorithms.
- The SBM assigns each node a latent block and determines connectivity levels from block memberships, but can oversimplify real network structure.
- Many SBM methods estimate labels and parameters but require knowing, or suitably bounding, the number of blocks K beforehand.
- The paper analyzes likelihood-ratio asymptotics under underfitting and overfitting, deriving a consistent penalized-likelihood criterion valid when average degree grows at a polylog rate.
2. Results.
The paper develops likelihood-based asymptotic analysis for comparing correct, underfit, and overfit stochastic block models, then uses the resulting rates to construct a consistent block-number selection criterion.
- 2.1. Preliminaries.: The SBM assigns latent node blocks and models connectivity through block memberships, with parameters θ = (π, H).H is a symmetric K × K matrix of within- and between-block connectivities; the framework also permits a fitted model with K′ blocks.
- 2.1. Preliminaries.: Likelihood-ratio analysis compares the correct K-block model with a misspecified K′-block model, despite the likelihood summing over exponentially many labelings.For underfitting, the likelihood is controlled through the optimal merging of two true blocks and analyzed using a tractable complete-likelihood bound.
- 2.2. Underfitting.: Underfitting by merging blocks yields an asymptotically normal log likelihood ratio under the stated identifiability and unique-optimal-merging assumptions.The merging operation combines connectivity parameters using block proportions, and the theorem gives the limiting mean and covariance through the multinomial block-proportion covariance and Jacobian.
- 2.3. Overfitting.: Overfitting with K+ > K has a more difficult likelihood analysis because exponentially many label splits remain, but its log likelihood ratio has a controlled convergence order.The general result is OP(n^(3/2)ρ_n^(1/2)), and under an additional balanced-design assumption it is refined to OP(n).
- 2.4. Model selection.: A penalized likelihood criterion selects the correct block number asymptotically by using a complexity term based on edge-probability parameters and a penalty order growing slightly faster than n.The criterion is asymptotically consistent, although tuning the constant λ remains challenging in finite samples and the overfitting lower bound is not tight.
- 2.5. Extension to a degree-corrected stochastic block model.: The analysis extends to the degree-corrected SBM under the stricter condition n^(1/2)ρ_n / log n → ∞, with the resulting criterion remaining asymptotically consistent.The condition ensures sufficient edges for parameter estimation despite worst-case node-degree variation.
Variational likelihood for regular SBM.
For regular SBM, the variational log likelihood simplifies likelihood optimization and can replace the exact likelihood without changing asymptotic consistency, subject to a bounded optimization-gap condition.
- The variational log likelihood J(q, θ; A) can be optimized using the EM algorithm and is easily evaluated after simplification.
- Replacing the likelihood with J preserves the model-selection criterion’s asymptotic consistency.
- The variational objective is a lower bound on log g(A; θ), while its optimized value differs from the exact optimum by OP(1).
- Asymptotic consistency remains valid when the algorithm’s local optimum differs from the global optimum by oP(n log n).
- Likelihood approximation is motivated by the computational difficulty of direct likelihood optimization, whose summands grow exponentially with network size.
Label estimation.
The paper uses estimated labels and likelihood-based quantities to support block-number selection, with computational approximations used in practice.
- Pseudo-likelihood provides a computationally efficient label-estimation method for both regular SBM and DCSBM.Weak consistency for label estimation was established, while plug-in block-parameter estimates remain consistent.
- The maximum complete likelihood is evaluated using estimated labels for each candidate block number.
- The resulting criterion is asymptotically consistent.
- Simulations approximate regular-SBM likelihoods with variational EM and DCSBM likelihoods with pseudo-likelihood.
3. Simulations.
Simulations examine the finite-sample behavior of the likelihood statistic, tune the penalty parameter, and compare penalized likelihood with alternative selection methods under regular SBM and DCSBM.
- Goodness of fit: At n = 500, the empirical distributions of the underfitting statistic are well approximated by the normal limit, although finite-sample bias appears at n = 200.Convergence to the Gaussian shape appears faster than convergence to the mean.
- Selection of tuning parameter: The tuning algorithm selects λ by maximizing the entropy of normalized penalized-likelihood profiles across candidate block numbers.It searches λ over [0, 0.3] in increments of 1 × 10^-3, with Kmax = 10 in simulations.
- Performance comparison with other methods: For regular SBM, plh outperforms variational Bayes and network cross validation across simulated settings, although success rates decline as networks become sparser and K increases.The simulations use 50 networks of size 500, with average degrees ranging from around 12 to 75.
- Performance comparison with other methods: For DCSBM, plh shows a significant improvement over ncv in almost all simulated parameter settings despite degree-induced sparsity making the problem harder than regular SBM.The DCSBM simulations use degree parameters drawn from Unif(0.2, 1) and normalized before generating networks.
4. Real world networks.
Real-network analyses compare selected community counts and partitions against manual labels, showing that plh produces generally sensible but sometimes finer-grained structures.
- Facebook ego networks: On Facebook ego networks, plh estimates are closer to the true community counts for reasonably large networks with a moderate number of communities.Variational Bayes performs better with many communities but overfits in some cases, while ncv tends to select fewer communities.
- Political book network: For the 105-book political network, plh selects K = 6 and splits each manually labeled community into two sub-communities with more uniform degree distributions.Variational Bayes selects 4 communities and ncv selects 2, each merging some manually labeled clusters.
- Political blog network: For the political blog DCSBM, plh selects K = 4 by splitting one manually labeled community into three, whereas ncv selects K = 2.The analyzed network is the largest connected component containing 1222 nodes.
- Overall findings: Across regular SBM and DCSBM, the likelihood-based criterion produces sensible results on real networks and performs better than vb and ncv on simulated data.The paper notes that vb is unavailable for DCSBM and ncv can vary substantially because it uses random partitions.
5. Discussion.
The discussion identifies extensions to other block-model variants and to settings where the number of communities grows with network size as open problems.
- Extending the results to overlapping stochastic block models remains an open direction.
- The analysis assumes a fixed number of blocks as the number of nodes tends to infinity.
- Allowing the number of communities to grow with expanding networks is identified as an important practical direction.
- Incorporating dynamic community structures into network modeling remains an open direction for time-course network data.
APPENDIX A: PROOFS OF LEMMAS AND THEOREMS
The appendix proves the main theoretical results by analyzing likelihood expansions, concentration, convexity, and label configurations under underfitting and overfitting.
- Underfitting a (K−1)-block model can be analyzed by considering configurations that merge two existing blocks.The maximizer over feasible confusion matrices occurs at a vertex corresponding to a block merge.
- Convexity, strict convexity, identifiability, and uniqueness determine the relevant maximizing label configurations.These properties reduce the underfitting analysis to merging one pair of true labels while mapping the others one-to-one.
- Concentration inequalities and Taylor expansions control likelihood fluctuations and establish the theorem-level asymptotic expansions.The proof uses concentration of block counts and edge statistics, followed by Taylor expansion.
- The appendix extends the overfitting analysis through bounds based on feasible label configurations and superadditivity.For overfitted models, the likelihood contribution is bounded uniformly over labelings.
SUPPLEMENTARY MATERIAL
The supplementary material provides a proof sketch extending the paper’s main results to the degree-corrected stochastic block model.
- The supplement sketches how the main results extend to the degree-corrected stochastic block model.
SUPPLEMENT TO “LIKELIHOOD-BASED MODEL SELECTION FOR STOCHASTIC BLOCK MODELS”
The DCSBM supplement adapts the likelihood and confusion-matrix analysis, then uses concentration and convexity arguments to recover the principal block-selection results.
- The DCSBM proof sketch defines likelihood-related counts and a confusion matrix conditional on true labels and degree parameters.The confusion matrix represents assignments from fitted labels to true blocks.
- Chernoff bounds show that normalized edge counts concentrate around expectations determined by the confusion matrix and the true connectivity matrix.
- Convexity of the DCSBM objective allows the earlier polyhedral argument to identify maximizing configurations.
- For equal block numbers, the true labeling uniquely maximizes the objective; for one fewer block, the maximizer merges the correct pair under a comparable assumption.
- The supplement states that the underfitting likelihood-ratio statistic remains asymptotically normal after scaling, with changed mean and variance terms.