Source-linked AI summary
Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
Peter Bickel, David Choi, Xiangyu Chang, Hai Zhang
TL;DR
Stochastic blockmodels lack satisfactory inference theory for maximum likelihood and computationally difficult latent-variable estimation. The paper establishes consistency and asymptotic normality for maximum likelihood and variational likelihood in sparse blockmodels, showing that both support classical optimality properties under the stated conditions. The conclusions apply subject to identifiability restrictions and fixed-block, polylogarithmic-degree settings.
Problem
Stochastic blockmodels present computational challenges from latent-variable marginalization and lack satisfactory inference theory for maximum likelihood and related procedures.
Method
The paper analyzes maximum likelihood and a variational approximation for stochastic blockmodels, including sparse models and restricted sub-models.
Results
The methods have the same behavior as when block identities are observed, and variational likelihood has the same properties as ordinary likelihood under the stated conditions.
Takeaways & Limitations
Classical optimality properties, including achievement of the information bound, hold for these procedures under the stated conditions.
Takeaways & Limitations
The analysis assumes average degree grows at least at a polylog rate and the number of blocks K remains fixed; increasing K makes classical rates unlikely.
Abstract
from arXiv · showhide
Variational methods for parameter estimation are an active research area, potentially offering computationally tractable heuristics with theoretical performance bounds. We build on recent work that applies such methods to network data, and establish asymptotic normality rates for parameter estimates of stochastic blockmodel data, by either maximum likelihood or variational estimation. The result also applies to various sub-models of the stochastic blockmodel found in the literature.
1. Introduction.
Network models pose unresolved computational and statistical challenges, while stochastic blockmodels have emerging consistency results but lack satisfactory inference theory. This paper establishes consistency and asymptotic normality for maximum likelihood and variational estimation in sparse and restricted blockmodels.
- Network-data models present both computational and statistical challenges because fitting methods and large-sample properties remain poorly understood.
- Stochastic blockmodels model network connections through a latent discrete class variable associated with each node.
- Consistency results for stochastic blockmodels cover profile likelihood, spectral clustering, and other methods under varying sparsity and class-number assumptions.
- Formal inference theory remains unsatisfactory for maximum likelihood and procedures whose computation may be NP-hard in worst-case analysis.
- The paper establishes consistency and asymptotic normality for maximum likelihood and variational estimation in sparse models and restricted sub-models.
2. Preliminaries.
The preliminaries define latent blockmodels, their parameterizations, identifiability, extensions, and estimation procedures. Maximum likelihood is difficult because of latent-variable marginalization and local optima, motivating variational approximation.
- Stochastic blockmodel: The complete graph model assigns latent classes to vertices and generates adjacency entries through a symmetric matrix of class-pair probabilities.
- Parameterization: Restricted parameter spaces allow parametric submodels of the blockmodel to be studied.
- Parameterization: Parameters θ=(ρ,φ) separate sparsity from class structure, with λ=nρ interpreted as expected degree and ρ as edge probability.
- Identifiability: Latent-class labels are nonidentifiable up to permutation, so estimates and asymptotic normality are defined through equivalence classes.
- Identifiability: The analysis excludes identical rows of H because indistinguishable classes create additional nonidentifiability and reduce the effective blockmodel order.
- Submodels: Degree-corrected blockmodels use paired latent variables to represent subblocks and within-block degree affinities with fewer parameters than a fully free UV blockmodel.
- Estimation: Maximum likelihood faces local optima and generally intractable marginalization over latent labels.
- Estimation: Variational estimation replaces the difficult marginal likelihood with an approximate objective over product distributions, enabling tractable local optimization such as EM.
3. Results.
The paper establishes asymptotic normality for complete-graph and generalized stochastic blockmodel maximum likelihood estimates, including restricted submodels and variational approximations. For poly-log expected degree, complete- and generalized-model likelihood inference are asymptotically equivalent under stated identifiability conditions.
- Complete graph blockmodel: Under (log n)^-1λ0 → ∞, complete-graph blockmodel maximum likelihood estimates have asymptotically normal components.The result follows from exponential-family theory, a Lindeberg central limit theorem, and the delta method.
- Complete graph blockmodel: Restricted submodels generally yield parameter error O_P(n^-1/2), while freely varying block-interaction parameters can attain the faster rate.The interaction component is asymptotically normal at the faster rate involving nλ.
- Generalized blockmodel: When nρn/log n → ∞ and S0 has no identical columns, complete- and generalized-model likelihood ratios are asymptotically equivalent.The equivalence holds locally around the true parameter and both likelihood ratios vanish uniformly outside appropriate neighborhoods.
- Generalized blockmodel: The maximum likelihood estimator under the generalized blockmodel inherits the complete-model consistency and asymptotic normality, up to label-identifiability restrictions.A corresponding submodel estimate has equivalent behavior when the parameter mapping is smooth and the complete-model estimate exists and is consistent.
- Variational estimates: Variational likelihood estimates satisfy the same asymptotic conclusions as maximum likelihood under the conditions of Theorem 1 and Lemma 2.Theorem 3 controls the variational likelihood approximation uniformly through an error term εn whose supremum is o_P(1).
4. Some statistical applications.
The paper uses the asymptotic results to justify standard inference for blockmodels, including tests, likelihood-ratio procedures, and parametric bootstrap methods. These procedures apply to variational estimates as well as maximum likelihood estimates, with variational computation potentially easier.
- Asymptotic tests: Asymptotic normality permits tests based on plug-in estimates of the variance–covariance matrices for variational and maximum likelihood estimators.The variance matrices are evaluated at estimated parameters, with average observed degree used for the rate estimate.
- Likelihood-ratio testing: The Wilks statistics for generalized and complete blockmodels have the same asymptotic distribution, enabling tests against a notional Sθ0 when labels are latent.The generalized-model likelihood ratio can therefore support testing despite the unobserved node labels.
- Likelihood-ratio testing: The variational Wilks statistic has a similar result and may be easier to compute than the maximum likelihood version.The comparison uses the variational likelihood’s inequality relative to the generalized likelihood together with Theorem 3.
- Parametric bootstrap: A parametric bootstrap for variational estimates is valid under the conditions of Theorem 2.The procedure estimates θ by variational likelihood, generates blockmodel graphs, and uses the resulting estimator vectors to approximate uncertainty.
- Parametric bootstrap: Bootstrap validity follows from convergence to the Gaussian limits with probability tending to 1 under the fitted parameter.The argument uses uniform convergence on contiguous neighborhoods and smoothness of the covariance mapping.
5. Conclusions.
For fixed-K block and extended blockmodels with average degree diverging at least polylogarithmically, maximum-likelihood and variational procedures inherit tractable exponential-family behavior under identifiability restrictions, although likelihood computation remains difficult.
- The analysis studies stochastic block and extended blockmodels with fixed K and average degree tending to infinity at least at a polylogarithmic rate.
- Maximum-likelihood estimation and parameter testing have the same behavior as when block identities are observed, subject to identifiability restrictions.The argument uses a corrected version of the approach of Bickel and Chen (2009).
- Likelihood computation is as difficult as NP-complete modularity computation, while nonconcavity makes optimization starting points critical.Spectral-clustering approaches are identified as promising starting-point methods.
- The variational likelihood has the same properties as the ordinary likelihood under these conditions.It can be computed in O(n^3) operations, making it more attractive computationally.
- The results imply classical optimality properties, including achievement of the information bound.
- Allowing the number of blocks K to increase introduces model-selection and regularization issues, making perfect classification and classical parameter-estimation rates unlikely.The paper notes that statistical approximation goals remain unclear in this setting.
- The results also extend to sufficiently smoothly parameterized submodels, with possible applicability to models containing vertex or edge covariates.
Part 1: e for which F is small.
This part separates assignments whose population criterion is substantially suboptimal from assignments close to the true labeling, using uniform convergence and continuity arguments.
- For assignments in E_δn, the criterion F(O(e)/μn,π(e)) is suboptimal by at least δn/2 up to a vanishing error.The argument uses uniform convergence of O(e)/μn to RSRT(e) and continuity of F.
- The set E_δn collects assignments for which the population criterion remains separated from the optimum.
- Assignments outside E_δn require a separate argument because some may be very close to the true assignment.
Part 2: A concentration inequality.
This part establishes the needed concentration control by applying a Bernstein inequality to centered independent sums and then using a union bound.
- The argument uses μn/n ≫ log n to choose ε tending to zero while retaining sufficient exponential concentration.
Part 3: e when F is large.
For assignments near the true labeling, the proof lower-bounds criterion loss through the confusion matrix and directional behavior of the population objective.
- The criterion loss is bounded using the change h(e)=RSRT(e)−RSRT(c), together with the third property of F.
- The population criterion is expressed as G(R(e),S), where R(e) is constrained by the true class proportions.
- The proof obtains a probabilistic lower bound on the relevant quantity through an ΩP(bn) rate.
- Convergence of (O(c)/μn,π(c)) and continuity of directional derivatives provide uniform control over assignments.
- The nearest representative assignment satisfies h(ē)=Ω(∥ē−c∥/n), linking criterion separation to labeling distance.
Part 4: Putting the parts together.
The section combines preceding equations and a likelihood identity to complete the theorem’s proof.
- Combining equations (23) and (20) yields an intermediate result used in the proof.
- Combining equations (24) and (25) supplies another step in the argument.
- The final equality uses a fact that holds for all θ.
- F0 is identified with the MLE likelihood under the CGM model, supporting the concluding comparison.
- These steps prove the theorem.