Optimality of variational inference for stochasticblock model with missing links

Solenne Gaucher, Olga KloppNeurIPS 2021 · OpenReview

This paper addresses a fundamental tension in network science: the trade-off between computational efficiency and statistical precision. Specifically, it explores how to accurately estimate the structure of a network when many of its links are missing.

The Dilemma of Missing Data in Networks

In network analysis, the Stochastic Block Model (SBM) is the gold standard for representing community structures. It assumes nodes belong to hidden groups, and the probability of a link between two nodes depends solely on their group assignments.

However, real-world data is rarely perfect. We often face "missing links"—situations where we don't know if an edge exists because of experimental costs (e.g., protein interactions) or sheer data volume (e.g., social media sub-sampling).

Statisticians face a dilemma when trying to infer network structure from incomplete data:

  1. Maximum Likelihood Estimators (MLE) are theoretically perfect but computationally "NP-hard." They require searching through every possible way to assign $n$ nodes to $k$ communities ($k^n$ combinations).
  2. Tractable methods (like spectral clustering or least squares) are fast but often fail to reach the "minimax" rate—the mathematical limit of how much information can be extracted from a noisy dataset.

This paper asks a critical question: Can we bridge this gap? Is there an algorithm that is both fast and statistically optimal for networks with missing data?

Bridging the Gap with Variational Inference

The authors prove that Variational Inference (VI)—a computationally efficient "shortcut" for complex statistical models—is actually minimax optimal for SBMs with missing data. This means that researchers now have an estimator that is both practically fast and theoretically as accurate as any possible algorithm could be.

Instead of trying to solve the impossible MLE directly, Mean-Field Variational Inference approximates the complex posterior distribution of node labels with a simpler, factorized distribution. The authors propose a specific two-step estimator:

  1. Labeling: Use a Variational EM (Expectation-Maximization) algorithm to estimate the community labels for each node.
  2. Probability Estimation: Once labels are fixed, calculate the connection probabilities between communities using a simple empirical mean (counting observed edges vs. possible edges).

The core of the paper is a rigorous mathematical proof showing that the error of this estimator converges at the minimax rate. This closes a long-standing open question about whether a "computational gap" exists for this specific problem.

Key Results and Performance

The authors validated their theory using both simulations and real-world networks, including a primary school interaction dataset and a co-authorship network.

Superior Performance

In simulations across Assortative, Disassortative, and Mixed SBM scenarios, the proposed VI estimator consistently outperformed softImpute (a popular matrix completion method) and missSBM (the previous standard VI implementation).

Error rates for the Mixed SBM scenario. The Variational Estimator (blue) consistently outperforms SoftImpute (green) and MissSBM (red), approaching the Oracle (black).

On the real-world primary school dataset, the new estimator reduced link prediction error by 1.4% to 12.4% compared to existing methods. By accurately estimating the underlying community connection probabilities, the model becomes a powerful tool for link prediction—identifying which "missing" links are most likely to actually exist.

Robustness to Sparsity

The estimator remains optimal even as the network becomes sparser, provided the sampling rate $p$ stays above a certain threshold (roughly $p \gg \log(n)/n$).

Error as a function of the sampling rate p. The Variational Estimator maintains low error even at high sparsity levels, unlike baseline methods.

Unlike other methods that diverge as data becomes sparser, the VI estimator's error remains low until it hits the fundamental "information-theoretic" limit where clustering becomes impossible.

Limitations and Future Work

While groundbreaking, the approach has a few limitations:

  • Initialization Sensitivity: Like most EM-based algorithms, VI can get stuck in "local optima." It requires a decent starting point (the authors suggest using spectral clustering first) to guarantee convergence to the global solution.
  • Known $k$: The current proofs assume the number of communities ($k$) is known or can be correctly estimated via cross-validation.
  • Model Complexity: While SBMs are versatile, they don't capture every nuance of real networks (like degree heterogeneity). Extending this optimality proof to more complex models, like the Latent Block Model, is a promising next step.

Summary updated

Abstract

Variational methods are extremely popular in the analysis of network data. Statistical guarantees obtained for these methods typically provide asymptotic normality for the problem of estimation of global model parameters under the stochastic block model. In the present work, we consider the case of networks with missing links that is important in application and show that the variational approximation to the maximum likelihood estimator converges at the minimax rate. This provides the first minimax optimal and tractable estimator for the problem of parameter estimation for the stochastic block model with missing links. We complement our results with numerical studies of simulated and real networks, which confirm the advantages of this estimator over current methods.
BibTeX
@inproceedings{gaucher2021optimality,
  author = {Solenne Gaucher and Olga Klopp},
  title = {{Optimality of variational inference for stochasticblock model with missing links}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=qDBLEXAIXM},
}
Figure