PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian stochastic blockmodeling

Tiago P. Peixoto

arXiv:1705.10225v9stat.MLcond-mat.stat-mechphysics.data-an

TL;DR

The chapter addresses how to extract large-scale network structure while avoiding overfitting and underfitting. It develops Bayesian stochastic blockmodel formulations and inference strategies, showing that increased Bayesian hierarchies can distinguish all 64 cliques in an example where an uninformative approach merges them into 32 groups.

  • Problem

    Large networks require methods that abstract low-level details to reveal large-scale structure, but modular inference must avoid mistaking randomness for structure or structure for randomness.

  • Method

    The chapter develops nonparametric Bayesian stochastic blockmodels, including degree-corrected and overlapping variants, with hierarchical priors and algorithms for posterior sampling, optimization, and model selection.

  • Results

    The nested Bayesian approach successfully distinguishes all 64 isolated cliques, whereas the uninformative approach produces 32 groups containing two cliques each.

  • Takeaways & Limitations

    Bayesian blockmodel inference provides an analytically tractable and computationally efficient framework for extracting network-scale structure while addressing both overfitting and underfitting.

  • Takeaways & Limitations

    Naive Metropolis-Hastings implementations can converge poorly in practical time unless the initial state and proposal distribution resemble the posterior.

Abstract

from arXiv · show

This chapter provides a self-contained introduction to the use of Bayesian inference to extract large-scale modular structures from network data, based on the stochastic blockmodel (SBM), as well as its degree-corrected and overlapping generalizations. We focus on nonparametric formulations that allow their inference in a manner that prevents overfitting, and enables model selection. We discuss aspects of the choice of priors, in particular how to avoid underfitting via increased Bayesian hierarchies, and we contrast the task of sampling network partitions from the posterior distribution with finding the single point estimate that maximizes it, while describing efficient algorithms to perform either one. We also show how inferring the SBM can be used to predict missing and spurious links, and shed light on the fundamental limitations of the detectability of modular structures in networks.

I. INTRODUCTION

Network analysis seeks large-scale building blocks, but random graphs can display convincing, mutually inconsistent modular patterns. Bayesian stochastic blockmodels address this by specifying generative mechanisms and inferring statistically supported structure.

  • I. INTRODUCTION: Large networks require abstractions that summarize global structure beyond low-level details.The chapter frames this challenge across social, biological, and technological systems.
  • II. STRUCTURE VERSUS RANDOMNESS IN NETWORKS: Random Erdős-Rényi networks can exhibit apparently clear modular patterns that are artifacts of node ordering and stochastic fluctuations.The same adjacency matrix can produce distinct visual impressions despite identical edge probabilities.
  • II. STRUCTURE VERSUS RANDOMNESS IN NETWORKS: Treating random fluctuations as generative structure overfits the data and can mislead interpretations from clustering methods lacking statistical significance.The resulting groups need not correspond to the process that generated the network.
  • II. STRUCTURE VERSUS RANDOMNESS IN NETWORKS: The remedy is probabilistic modeling with parsimony, favoring simpler explanations unless data justify added complexity.The approach combines modeling assumptions, statistical evidence, and prior information.
  • III. THE STOCHASTIC BLOCKMODEL (SBM): The SBM groups nodes into building blocks and assigns edge probabilities between groups to generate networks with varied mixing patterns.The model accommodates community structure, bipartiteness, core-periphery, and other patterns.
  • III. THE STOCHASTIC BLOCKMODEL (SBM): The chapter develops the reverse procedure: inferring modular structure from observed network data using SBM-based generative models.It focuses on undirected networks while noting directed extensions.

IV. BAYESIAN INFERENCE: THE POSTERIOR PROBABILITY OF PARTITIONS

Bayesian inference assigns posterior probabilities to network partitions by combining priors with the SBM likelihood. Hierarchical maximum-entropy priors and tractable posterior terms help control overfitting while addressing prior-induced underfitting.

  • IV. BAYESIAN INFERENCE: THE POSTERIOR PROBABILITY OF PARTITIONS: The inference task is to estimate the probability P(b|A) that partition b generated observed adjacency matrix A under the SBM.Bayes’ rule combines the partition prior, model likelihood, and evidence.
  • IV. BAYESIAN INFERENCE: THE POSTERIOR PROBABILITY OF PARTITIONS: Priors shape the posterior and inference results, so the chapter uses maximum-entropy principles when empirical prior information is unavailable.Networks are often unique objects rather than samples from a population, limiting data-driven prior selection.
  • IV. BAYESIAN INFERENCE: THE POSTERIOR PROBABILITY OF PARTITIONS: Refining the group-size prior beyond the information-theoretic limit improves log-probability by only O(lnN), yielding little practical difference.The limiting term is −NH(n), where H(n) is the entropy of the group-size distribution.
  • IV. BAYESIAN INFERENCE: THE POSTERIOR PROBABILITY OF PARTITIONS: A three-level hierarchy samples the number of groups, group sizes, and partition, reducing assumptions embedded in a flat partition prior.The hierarchy uses maximum-entropy distributions at each level.
  • IV. BAYESIAN INFERENCE: THE POSTERIOR PROBABILITY OF PARTITIONS: The exact model evidence is intractable because it sums over all partitions, but the computable posterior numerator suffices for optimization and sampling.It contains the information needed to proceed with inference.
  • IV. BAYESIAN INFERENCE: THE POSTERIOR PROBABILITY OF PARTITIONS: A posterior suppresses partitions unsupported by network evidence, allowing the number of groups B to be inferred without overfitting.This is the chapter’s nonparametric interpretation of Bayesian SBM inference.

V. MICROCANONICAL MODELS AND THE MINIMUM DESCRIPTION LENGTH PRINCIPLE (MDL)

The microcanonical formulation recasts Bayesian inference through exact group-level edge-count constraints and an information-theoretic description length. Maximizing the posterior is therefore equivalent to minimizing the description length, providing a principled way to select network partitions and avoid overfitting.

  • Microcanonical formulation: The microcanonical SBM fixes intergroup edge counts exactly, contrasting with canonical models whose corresponding parameters specify only average counts.Its edge-count prior still permits fluctuations before conditioning, preserving equivalence between the formulations at the marginal-likelihood level.
  • Minimum description length: Description length measures the information needed to encode the network together with its edge counts and partition.It is based on −log2 probabilities under an optimal lossless coding scheme.
  • Minimum description length: Maximizing the posterior automatically minimizes the description length, balancing improved data fit against the cost of a more complex model.As groups increase, the data-encoding cost decreases while model-description costs constrain overfitting.
  • Empirical illustration: Randomizing the football network yields a trivial B = 1 partition, indicating that the method does not infer groups from fully random connectivity.The contrast supports the statistical significance of the structure found in the original data.

VI. THE “RESOLUTION LIMIT” UNDERFITTING PROBLEM, AND THE NESTED SBM

Uninformative priors can underfit networks by penalizing complex group-level structure so strongly that obvious modules are merged. The nested SBM addresses this by recursively modeling group connections, reducing underfitting while supporting multiscale descriptions.

  • The underfitting problem: The basic Bayesian SBM can underfit by mistaking statistically significant structure for randomness when prior assumptions disagree with the data.For 64 isolated cliques, it infers B = 32 groups, pairing two cliques per group instead of recovering each clique.
  • The underfitting problem: Uninformative priors impose a quadratic description-length penalty as B increases, limiting the number of groups the model can uncover.This limitation can persist even when the groups are obvious in the observed network.
  • The nested SBM: The nested SBM postpones high-level structural choices by modeling the group-level edge-count matrix with another SBM, recursively forming a hierarchy.Each level partitions groups into meta-groups and models their interconnections at the next scale.
  • Empirical consequences: Across empirical networks, systematic underfitting seen with the ordinary SBM virtually disappears under the nested model.The nested construction remains a priori agnostic about the type of large-scale structure while retaining the uninformative prior as a special case.
  • The nested SBM: For the 64-clique example, the nested model distinguishes all 64 cliques and achieves a lower overall description length than the ordinary SBM.Its maximum recoverable group count scales as Bmax ∝ N/logN, larger than under uninformative priors.
  • Multiscale structure: The nested model describes networks at multiple scales, from detailed lower-level routing groups to higher-level patterns such as internet core-periphery organization.This can make complex large-network structure easier to interpret by examining upper levels first.

VII. MODEL VARIATIONS

The SBM framework supports model variations, including degree correction and group overlap, to adapt how group membership shapes edge placement. Unlike disconnected clustering algorithms, its Bayesian formulation enables principled comparison and selection among models.

  • Model variations: Important SBM variations include degree-corrected models and models allowing group overlap, which alter the internal structure of the network model.These variations provide additional ways to adapt model complexity to observed network data.
  • Model comparison: Model multiplicity is treated as a strength because Bayesian inference can compare alternative models principledly and select the best one.This contrasts with network-clustering algorithms that may produce conflicting results without a clear selection procedure.

A. Model selection

Model comparison should use posterior odds or Bayes factors rather than only the most likely partition, with description length providing a compression-based preference whose strength depends on the odds ratio.

  • A. Model selection: Posterior odds compare two model-partition choices using their relative plausibility given the observed network.The comparison incorporates each model's posterior partition and prior model belief.
  • A. Model selection: The preferred choice generally has the smallest description length, but a ratio close to one provides weak evidence against the alternative.The decision should reflect the actual magnitude of the odds ratio rather than treating every difference as decisive.
  • A. Model selection: Bayes factors compare model classes after averaging over all possible partitions rather than considering only their most likely partitions.This criterion uses the model evidence and has an interpretation analogous to posterior odds.
  • A. Model selection: Exact model evidence is difficult to compute for the models of interest, making the averaged criterion harder to use in practice.Approximations have been proposed, and the chapter contrasts optimization with posterior sampling later.

B. Degree correction

Degree correction addresses the SBM’s tendency to group nodes by degree when empirical networks have heterogeneous degree distributions. The DC-SBM separates degree variation from group structure and often achieves shorter description lengths despite its extra parameters.

  • B. Degree correction: The ordinary SBM assumes nodes in the same group have the same average degree, which can misrepresent networks with strongly heterogeneous degrees.In the political-blog example, forcing two groups makes the SBM separate high-degree and low-degree nodes instead of political factions.
  • B. Degree correction: The DC-SBM separates community structure from degree heterogeneity, allowing two-group inference on the political-blog network to identify the two political factions.Its additional parameters capture degree variation rather than forcing degree differences into the partition.
  • B. Degree correction: The microcanonical DC-SBM generates networks sequentially by sampling intergroup edge counts, node degrees, and then the network itself.This factorization is represented as P(e|b), P(k|e,b), and P(A|k,e,b).
  • B. Degree correction: A nested degree model with a more realistic degree prior can use degree-distribution regularities to inform group division and generally fit better than the uniform degree model.The hierarchical variants address underfitting associated with uninformative priors.
  • B. Degree correction: The DC-SBM yields shorter description lengths for a majority of empirical datasets, while the political-blog example shows the degree-prior variant achieving the smallest value among the displayed models.The figure reports approximately 89,938, 87,162, and 84,890 bits for the three variants.

C. Group overlaps

Overlapping SBMs allow nodes to belong to multiple groups, but Bayesian model selection is needed because their greater flexibility can overfit. Across most empirical networks, nonoverlapping variants generally remain more parsimonious.

  • C. Group overlaps: Overlapping SBMs replace disjoint memberships with soft memberships, modeling each node’s connections as a mixture of pure groups.The nonoverlapping degree-corrected model is recovered by choosing κ_ir = θ_iδ_r,b_i.
  • C. Group overlaps: The overlapping formulation introduces an auxiliary half-edge-label matrix G because direct computation of the marginal likelihood for κ is intractable.G decomposes each edge into endpoint labels and permits posterior sampling or maximization over compatible labelings.
  • C. Group overlaps: Overlapping models add flexibility and parameters, so their apparent fit improvement cannot be treated as evidence of pervasive overlap without model selection.The political-books example favors an overlapping SBM with B = 3, but the description-length differences among variants are small.
  • C. Group overlaps: Most empirical networks, especially larger ones, have larger description lengths under overlapping models than under nonoverlapping variants.This systematic result suggests overlap is less pervasive than degree heterogeneity under the chapter’s modeling framework.
  • C. Group overlaps: Any overlapping SBM can be represented by a nonoverlapping SBM with more groups encoding the individual mixture types, so model selection does not eliminate representational equivalence.As overlap increases, the nonoverlapping representation can sometimes have the smaller description length.

D. Further model extensions

The Bayesian framework extends to richer network data, including weighted and multilayer networks, while retaining the same conceptual approach to inference and model selection.

  • D. Further model extensions: SBM extensions cover continuous edge covariates, multilayer networks, and other realistic network features.These variations broaden the model beyond simple single-layer unweighted networks.
  • D. Further model extensions: The general Bayesian approach, including model selection, applies to these variations without conceptual difficulty.

VIII. EFFICIENT INFERENCE USING MARKOV CHAIN MONTE CARLO (MCMC)

The chapter develops scalable MCMC inference for SBM partitions by combining locally informed proposals with initialization near posterior modes. These strategies make inference practical on very large networks and across SBM variants.

  • Exact posterior sampling and maximization are generally intractable because fully characterizing or optimizing SBM posteriors is typically NP-hard.
  • Detailed balance and ergodicity ensure convergence to the posterior, while acceptance ratios can be computed without the intractable normalization constant.
  • Computational scaling: Posterior-ratio updates require O(k_i) time independently of the number of groups, allowing a full node sweep in O(E).
  • Efficient proposals: Locally informed proposals inspect a node’s neighborhood and favor groups connected to its neighbors, while retaining random moves to preserve ergodicity.
  • Initialization: An agglomerative heuristic and Fibonacci search provide starting partitions close to posterior modes, improving practical MCMC performance.
  • Computational scaling: The combined strategies scale to networks with 10^7–10^8 edges and up to B = N groups, with implementations available in graph-tool.

IX. TO SAMPLE OR TO OPTIMIZE?

The chapter contrasts MAP optimization with posterior sampling and marginal estimation. It shows that multiple plausible partitions can make a single point estimate misleading, especially when posterior uncertainty is substantial.

  • A loss function compares an inferred partition with the true generating partition, providing a basis for evaluating inference quality.
  • Point estimators: The MAP estimator maximizes posterior-average exact agreement and is equivalent here to the minimum-description-length principle.
  • Point estimators: The marginal estimator uses each node’s posterior membership distribution, incorporating information from the entire posterior rather than selecting one partition.
  • Posterior uncertainty: For the karate club network, the posterior is multimodal, with three competing explanations that network evidence alone cannot decisively distinguish.
  • Posterior uncertainty: Choosing one partition introduces bias toward a likely scenario, whereas representing the full posterior increases variance across divergent explanations.
  • Estimator choice: In nonparametric models, MAP estimates can underfit because posterior uncertainty often corresponds to a more conservative partition with fewer groups.
  • Estimator choice: Posterior sampling is favored for prediction and generalization when resources permit, while MAP is suited to precise summaries under computational constraints.

X. GENERALIZATION AND PREDICTION

The SBM’s generative formulation supports probabilistic prediction of missing and spurious network links. The approach models an unobserved complete network and infers which edge discrepancies are most plausible.

  • The SBM represents a possible mechanism generating the network, enabling predictions about unobserved structure when the model fits the data.
  • Generative formulation: The complete network is decomposed into the observed network and a discrepancy set, where positive entries denote missing edges and negative entries denote spurious edges.
  • Posterior prediction: The method computes a posterior over missing and spurious edges under an SBM-generated complete network and an error model.
  • Posterior prediction: Importance sampling from the observed-network partition posterior improves convergence because the discrepancy set is typically much smaller than the observed edge set.
  • Example: For American college football, a same-conference missing edge was almost 100 times more likely than a different-conference missing edge.
  • Applications: SBM-based link prediction has been applied to drug interactions, social conflicts, and user recommendations, often outperforming competing methods.

XI. FUNDAMENTAL LIMITS OF INFERENCE: THE DETECTABILITY-INDETECTABILITY PHASE TRANSITION

The chapter examines when planted network structure can be recovered and identifies a detectability threshold. Belief propagation is asymptotically exact on suitable sparse, locally tree-like graphs, but sparse networks can remain fundamentally information-limited.

  • Detectability undergoes a phase transition: planted structure becomes recoverable only when its strength crosses a non-trivial threshold.
  • Belief propagation: The BP method computes posterior node-membership marginals through iterated self-consistent messages on network edges.
  • Belief propagation: BP is asymptotically exact when the graph is sufficiently large and locally tree-like, a property satisfied by networks sampled from the SBM.
  • Detectability threshold: In the planted partition model, recovery depends on ε = N(λ_in − λ_out), with the uniform posterior appearing beyond the detectability threshold.
  • Information limits: For sparse graphs with E = O(N), increasing network size does not guarantee sufficient data because the number of partition parameters also grows with N.
  • Computational hardness: Above the threshold, recovery is possible in polynomial time; an intermediate glassy regime can make finding the planted partition conjecturally NP-hard.
  • Scope and caveats: The BP analysis is not fully rigorous mathematically, although it can remain accurate for real networks that violate local tree-likeness.

XII. CONCLUSION

The chapter presents Bayesian SBM inference as a framework for extracting network structure while controlling overfitting and underfitting. It also identifies unresolved modeling, goodness-of-fit, and computational challenges, while motivating continued extensions.

  • The Bayesian framework extracts large-scale network structure while avoiding both overfitting and underfitting.It is designed to remain analytically tractable and computationally efficient.
  • Bayesian inference tests whether large-scale network patterns are supported by statistical evidence.The approach also provides a theoretical basis for studying fundamental limits of network analysis.
  • The SBM remains simplistic for most systems and falls short of providing mechanistic explanations.The chapter compares its role in network data to that of a histogram in spatial data.
  • There is no good absolute method for assessing SBM fit or systematically understanding how well it reproduces empirical-system properties.These methodological gaps leave the main sources of deficiencies and their remedies unresolved.
  • SBM generalizations, including models for dynamic networks, remain open-ended, while inference is generally NP-hard and likely lacks a general solution.The chapter therefore anticipates continued development of more realistic models and efficient algorithms.
Loading 1705.10225v9…