Source-linked AI summary
Stochastic blockmodels with growing number of classes
David S. Choi, Patrick J. Wolfe, Edoardo M. Airoldi
TL;DR
The paper addresses how reliably stochastic blockmodels can analyze increasingly large and sparse networks when the number of classes grows. It develops uniform finite-sample and asymptotic likelihood results, showing vanishing misclassification under stated growth and identifiability conditions, and applies a covariate-adjusted model to Facebook profiles.
Problem
Network analysis remains challenging, motivating evidence about likelihood-based stochastic blockmodel inference when network size and the number of classes grow.
Method
The paper analyzes maximum-likelihood stochastic blockmodels for independent Bernoulli edges, derives uniform confidence bounds, and fits a logit blockmodel with covariates to Facebook profiles.
Results
Under K = O(N^1/2) and poly-logarithmic degree growth, the fraction of misclassified nodes converges to zero under suitable identifiability conditions; simulations support the bounds and convergence conditions.
Takeaways & Limitations
The results support likelihood-based blockmodel analysis with a growing number of classes and use covariate-adjusted fitting to reveal residual Facebook network structure.
Takeaways & Limitations
The consistency result requires correct specification, class-size growth, row-separation identifiability, and edge-probability and network-growth conditions.
Abstract
from arXiv · showhide
We present asymptotic and finite-sample results on the use of stochastic blockmodels for the analysis of network data. We show that the fraction of misclassified network nodes converges in probability to zero under maximum likelihood fitting when the number of classes is allowed to grow as the root of the network size and the average network degree grows at least poly-logarithmically in this size. We also establish finite-sample confidence bounds on maximum-likelihood blockmodel parameter estimates from data comprising independent Bernoulli random variates; these results hold uniformly over class assignment. We provide simulations verifying the conditions sufficient for our results, and conclude by fitting a logit parameterization of a stochastic blockmodel with covariates to a network data example comprising a collection of Facebook profiles, resulting in block estimates that reveal residual structure.
1. INTRODUCTION
The paper studies stochastic blockmodels for network data, focusing on likelihood-based inference when the number of classes grows with network size. It establishes consistency under milder degree growth than related spectral results and connects the model to exchangeable random graphs.
- 1. INTRODUCTION: Stochastic blockmodels partition N network nodes into K classes whose members interact similarly with the network.The model extends the idea of structural equivalence to stochastic network data.
- 1. INTRODUCTION: Blockmodels have been extended and applied across social network analysis, biology, information networks, and other disciplines.The paper situates its analysis within a broad literature on stochastic blockmodels and related models.
- 1. INTRODUCTION: The paper provides finite-sample confidence bounds for blockmodel estimation and proves that the misclassified-node fraction converges to zero when K grows with N.The guarantees concern independent Bernoulli network data and maximum-likelihood fitting.
- 1. INTRODUCTION: Maximum-likelihood fitting requires only poly-logarithmically increasing degree, whereas a related spectral approach requires nearly linearly increasing degree.Spectral clustering remains a computationally appealing alternative in practice.
- 1. INTRODUCTION: Under exchangeability, an observed network can be viewed as a sample from an infinite random-graph population, with the fitted blockmodel describing one mixture component.The mixture components can be approximated by blockmodels.
2. STATEMENT OF RESULTS
The paper formulates likelihood-based inference for independent Bernoulli edges under a stochastic blockmodel and derives uniform finite-sample and asymptotic guarantees. Under identifiability and growth conditions, maximum likelihood consistently recovers class assignments in fraction.
- Problem formulation and definitions: The adjacency matrix has independent Bernoulli entries, with edge probabilities restricted under a K-class blockmodel to depend only on endpoint classes.The restriction is Pij = θ_zizj for a symmetric K × K parameter matrix.
- Problem formulation and definitions: For each class assignment z, maximum likelihood estimates block probabilities from within- and between-class edge proportions.The resulting estimates are sufficient statistics for the K-class stochastic blockmodel family.
- Statement of results: Uniform deviation control compares observed and expected maximized log-likelihoods across all K^N class assignments.The proof combines type counting and a union bound over assignments.
- Statement of results: With K = O(N^1/2) and M = ω(N(log N)^(3+δ)), the normalized maximized log-likelihood is asymptotically well behaved when edge probabilities remain between 1/N^2 and 1 − 1/N^2.Equivalently, average degree 2M/N grows faster than (log N)^(3+δ).
- Fitting a correctly specified K-class stochastic blockmodel: Under correct specification, class sizes of order N/K and row-separation identifiability imply Ne(ẑ) = oP(N), so the misclassified-node fraction Ne/N tends to zero.The conclusion applies to the maximum-likelihood K-class assignment estimator.
3. NUMERICAL RESULTS
Simulations assess the confidence bounds and asymptotic conditions underlying the theoretical results. The observed errors follow the predicted behavior, including vanishing misclassification under the theorem's identifiability conditions.
- Likelihood convergence: When M = N(log N)^4 and K = N^1/2, normalized likelihood error decreased with network size N.These growth rates match the theorem-prescribed setting tested in the simulation.
- Classification consistency: The classification experiment generated data with equally sized blocks and varied γ to test the identifiability condition governing separation between class parameters.Condition (ii) was met only in the γ = 1 case.
- Simulation design: Figure 1 compares normalized likelihood error across network size and growth rates for M and K, alongside misclassification error under varying γ.The three panels correspond to the simulations illustrating Theorems 1–3.
- Classification consistency: When M = N(log N)^2 and K = N^1/2, the misclassification fraction decayed for γ = 1 and γ = 9/10 but increased for γ = 4/5.The pattern conforms with Theorem 3 and suggests its identifiability conditions are close to necessary as well as sufficient.
4. NETWORK DATA EXAMPLE
The Facebook analysis incorporates covariates into a logit blockmodel and evaluates model order and parameter precision across K. The fitted blocks reveal residual interaction structure beyond covariate-explained patterns, including stable meta-group membership for 199 students.
- Data and motivation: The dataset contains N = 553 undergraduate Facebook profiles, 11 511 edges, and covariates including gender, class year, and residence hall.The network records friendship links between students at the California Institute of Technology.
- Data and motivation: The analysis explicitly incorporates covariates to examine residual community structure beyond patterns explained by those covariates.Links are assumed to be independent Bernoulli variates, and confidence bounds assess fitted blocks through the parameter averages.
- Logit blockmodel parameterization and fitting procedure: The logit blockmodel models edge log-odds using block assignments and covariates, estimating the block parameters, covariate coefficients, and class assignments from the data.Four categorical covariates were used, including gender, class year, residence hall, and an observed-degree range category.
- Logit blockmodel parameterization and fitting procedure: Approximate maximum-likelihood fitting alternated MCMC exploration of class assignments with optimization of block and covariate parameters.Exact maximization of the corresponding log-likelihood was computationally intractable.
- Model selection and precision: Model-order diagnostics suggest a relatively low order beginning around K = 4, while divergence bounds remain small for K = 4–7.For K = 5, the reported divergence bound is 0·0067; normalized root-mean-square error bounds are approximately one order of magnitude larger.
- Data analysis: Across K = 4, 5, 6, and 7, the fitted parameter structure indicates two residual meta-groups that interact less frequently with one another.The corresponding KL divergence bounds are 0·0057, 0·0067, 0·0077, and 0·0086.
- Data analysis: As K increases, groups become more concentrated; 199 students retain constant meta-group membership across the four tested values of K.Residence-hall effects remain visible, with different halls overrepresented in the two groupings.
APPENDIX
The appendix establishes uniform likelihood-deviation bounds and uses them, together with partition refinements, to prove consistency of maximum-likelihood class assignments under growing K.
- Proof strategy: For fixed class assignment z, blockmodel estimates ˆθab are sums of nab independent Bernoulli variables, enabling concentration bounds for parameter estimation.The proof bounds deviations using Chernoff and related inequalities.
- Proof strategy: |L(A; z) − ¯LP(z)| is controlled by a KL-divergence term and a bounded independent-variable term, then extended uniformly over all KN assignments by a union bound.The proof sets ǫ using δ and the number of assignments to obtain the claimed result.
- Theorem 2: If K = O(N 1/2) and M = ω(N(log N)3+δ), then maxz |L(A; z) − ¯LP (z)|/M converges in probability to zero.This is the appendix's uniform likelihood approximation condition.
- Theorem 3: Theorem 3 applies the uniform likelihood result to the maximum-likelihood assignment ˆz and concludes that Ne(ˆz) = oP(N).The proof uses the maximum-likelihood inequality, population likelihood comparison, and the refinement lemmas.
- Theorem 3: A refinement Π∗ is constructed from any assignment z by pairing nodes sharing an estimated class but differing in true class, then regrouping associated edge probabilities.The construction separates misclassified nodes while preserving refinement of the assignment-induced partition.
- Theorem 3: The pairing count satisfies C1 ≥ Ne(z)/2, while class-size and separation conditions yield C2 = C1 Ω(N/K), linking misclassification error to partition refinement.These combinatorial quantities support the likelihood comparison used for consistency.