PaperlayerView exact revision on arXiv

Source-linked AI summary

Nonparametric Bayesian inference of the microcanonical stochastic block model

Tiago P. Peixoto

arXiv:1610.02703v4physics.data-anphysics.soc-phstat.ML

TL;DR

The paper asks how to infer network modules, their number, and hierarchical organization without restrictive parametric assumptions. It develops a nonparametric Bayesian microcanonical SBM with hard constraints and deeper priors, and reports scalable inference that uncovers small groups in large networks while connecting to canonical SBM formulations.

  • Problem

    Existing network modularity methods face difficulty distinguishing structure from noise and finding small structures in large systems.

  • Method

    The paper uses a nonparametric Bayesian microcanonical SBM with exact degree and structural constraints, hierarchical priors, and posterior inference over partitions.

  • Results

    The hierarchical model is less susceptible to underfitting and can uncover small groups in very large networks, while the microcanonical model is equivalent to a shallow Bayesian canonical SBM.

  • Takeaways & Limitations

    The approach supports multiscale modular inference, posterior sampling, model selection, and inference whose complexity is not explicitly dependent on the number of groups.

Abstract

from arXiv · show

A principled approach to characterize the hidden structure of networks is to formulate generative models, and then infer their parameters from data. When the desired structure is composed of modules or "communities", a suitable choice for this task is the stochastic block model (SBM), where nodes are divided into groups, and the placement of edges is conditioned on the group memberships. Here, we present a nonparametric Bayesian method to infer the modular structure of empirical networks, including the number of modules and their hierarchical organization. We focus on a microcanonical variant of the SBM, where the structure is imposed via hard constraints, i.e. the generated networks are not allowed to violate the patterns imposed by the model. We show how this simple model variation allows simultaneously for two important improvements over more traditional inference approaches: 1. Deeper Bayesian hierarchies, with noninformative priors replaced by sequences of priors and hyperpriors, that not only remove limitations that seriously degrade the inference on large networks, but also reveal structures at multiple scales; 2. A very efficient inference algorithm that scales well not only for networks with a large number of nodes and edges, but also with an unlimited number of modules. We show also how this approach can be used to sample modular hierarchies from the posterior distribution, as well as to perform model selection. We discuss and analyze the differences between sampling from the posterior and simply finding the single parameter estimate that maximizes it. Furthermore, we expose a direct equivalence between our microcanonical approach and alternative derivations based on the canonical SBM.

I. INTRODUCTION

The paper frames network modularity inference as a probabilistic modeling problem and develops a nonparametric, microcanonical SBM for recovering hierarchical structure from data. Hard constraints, Bayesian hierarchies, and posterior inference address scalability, model uncertainty, and limitations of heuristic and parametric approaches.

  • Motivation: Heuristic network-partitioning methods can confuse structure with noise, miss small structures in large systems, and produce divergent results for the same network.These limitations motivate probabilistic generative models and Bayesian inference.
  • Motivation: The framework models modular organization probabilistically and infers model parameters from observed networks using Bayesian inference and statistical physics.Nonparametric priors are used to address the separation of structure from noise.
  • Microcanonical SBM: The microcanonical SBM fixes structural constraints exactly across the network ensemble, rather than enforcing them only in expectation.The degree-corrected formulation fixes the degree sequence and group-to-group edge counts as hard constraints.
  • Nonparametric hierarchy: Deeper priors and hyperpriors support hierarchical inference that can reveal network organization at multiple scales and detect statistically significant structures in large data.The approach replaces simpler parameter choices with conditioned priors and hyperprior distributions.
  • Scalability: The inference algorithm scales to large networks and an unlimited number of modules, unlike methods that slow as the number of groups grows.This scalability is presented as a consequence of the microcanonical formulation.
  • Posterior inference and model comparison: The method samples hierarchical partitions from the posterior, supports model selection by statistical evidence, and establishes an equivalence with a Bayesian canonical SBM formulation.Posterior sampling differs from finding only the single most likely partition.
  • Scope and assumptions: The configuration-model construction permits multiple edges and self-loops, although multiple-edge probabilities decrease as 1/N for sparse networks with E ∝ N.Thus, such edges can be neglected asymptotically for sparse networks.

A. Sampling vs. optimization and the minimum description length principle (MDL).

The paper interprets Bayesian inference through posterior sampling, posterior maximization, and minimum description length. It also develops priors over partitions and group sizes, showing how model complexity is penalized and how deeper hierarchies offer diminishing gains.

  • Minimum description length: Σ = −log2 P(A, k, e, b) decomposes description length into the network description S and model-parameter description L.The two terms respectively encode the data given the parameters and the parameters themselves.
  • Minimum description length: Maximizing the posterior is equivalent to selecting parameters that minimize description length, linking Bayesian inference directly to MDL.The equivalence is especially direct under the microcanonical formulation.
  • Minimum description length: Increasing the number of groups lowers S but raises L, so the model-description term penalizes overly complex partitions and supports model selection.Description length can compare models with different internal structures and parameter sets.
  • Sampling versus optimization: Posterior maximization gives specific estimates but can suffer from insufficient statistics, parameter degeneracy, or model misspecification.Posterior sampling is less susceptible on average but produces more uncertainty and can overfit individual samples.
  • Sampling versus optimization: Posterior sampling is generally more suitable for generalization and prediction, whereas maximization tends to represent the observed data more accurately.The paper describes this as a bias–variance trade-off.
  • Partition priors: Uniform partition priors tend to assume similarly sized groups, so the framework conditions on group sizes and uses a hyperprior on node counts.The modification avoids empty groups and ties the number of groups to the partition.
  • Partition priors: Deeper hierarchy beyond the noninformative hyperprior yields at most a marginal improvement proportional to ln N when groups are sufficiently large and B ≪ N.The paper therefore stops deepening the hierarchy at that point.

C. Prior for the degrees

The degree prior evolves from a non-degree-corrected model toward conditioned priors that support broader and more arbitrary degree distributions. The conditioned hierarchy can adapt to empirical degree counts while limiting computational cost through approximations to restricted partitions.

  • NDC-SBM: The NDC-SBM removes the explicit degree sequence by randomly distributing group half-edges among nodes, but yields asymptotically Poisson-like within-group degrees.This produces similar degrees within groups and can be unrealistic for heterogeneous empirical networks.
  • Uniform degree prior: A uniform prior over within-group degree sequences still produces relatively similar degrees, with expected standard deviation σ_k = O(⟨k⟩).Its degree variability remains smaller than expected for many empirical networks.
  • Conditioned prior: Conditioning the degree prior on arbitrary degree counts allows the model to represent broader distributions, including a Bose-Einstein-like form with asymptotic p_k ∼ 1/k.The conditioned prior produces broader distributions than the exponential distribution associated with the uniform prior.
  • Computation: The restricted-partition function q(m, n) counts degree-count configurations and can be computed exactly by recurrence or approximated accurately across parameter ranges.For arguments around 10^3, the largest log-ratio error is about 0.1; the implementation uses exact values for m < 10^4 and approximations thereafter, giving O(1) computation.
  • Scope: The conditioned prior favors broad distributions but does not necessarily match real networks, which generally do not follow a Bose-Einstein degree distribution.Its broader support reduces concentration around a single expected distribution and permits substantial deviations.
  • Conditioned prior: For sufficiently many nodes per group, the conditioned prior approaches the empirical degree distribution, whereas the uniform prior cannot learn that underlying distribution.Any advantage from exact prior knowledge of the true distribution is asymptotically only O(√n_r), versus remaining terms scaling as O(n_r).

D. Prior for the edge counts and nested SBM hierarchies

A uniform prior over intergroup edge counts creates a resolution limit in large networks. Nested SBM priors address this by recursively modeling edge-count matrices while avoiding bias from dense upper-level multigraphs.

  • Prior for edge counts: A uniform prior over symmetric edge-count matrices can limit detection of small groups, imposing a resolution limit on the maximum inferable number of groups.The resulting upper bound scales with network size as described in the text.
  • Nested hierarchy: Deepening the Bayesian hierarchy addresses the edge-count resolution problem by recursively applying an SBM to the intergroup edge-count matrix.The matrix is interpreted as the adjacency matrix of a multigraph whose groups are recursively assigned to higher-level groups.
  • Nested hierarchy: At each hierarchy level, the number of edges remains fixed while the number of nodes decreases, making upper-level multigraphs increasingly dense and parallel edges predominant.Using the bottom-level configuration likelihood unchanged at upper levels would introduce bias and cause successive levels to cancel in the likelihood.
  • Upper-level prior: A uniform non-degree-corrected multigraph SBM provides an unbiased, maximally noninformative upper-level prior under these dense multigraph constraints.The hierarchy enforces B_L = 1, and setting L = 1 recovers the uniform prior as a special case.
  • Hierarchy depth: The hierarchy depth L is itself inferred from the data, with a noninformative prior that can be omitted when it contributes only an overall multiplicative constant.One stated choice is P(L) = 1/L_max with L_max sufficiently large, such as N.

E. Model summary

The hierarchical microcanonical DC-SBM combines the likelihood with priors over degrees, edge counts, and hierarchy parameters. Its local likelihood updates depend only on the moved node and its neighbors, and simpler variants are recovered by prior replacement or a one-level hierarchy.

  • Joint model: The joint distribution factors into the network likelihood and priors over the degree sequence, edge counts, and hierarchy partitions.This factorization is given for the hierarchical microcanonical DC-SBM.
  • Inference efficiency: Moving one node between groups requires updating only terms involving that node and its neighbors, with worst-case cost O(k_i), independent of the total number of groups.This local computation supports efficient likelihood evaluation during inference.
  • Model variants: The NDC-SBM and uniform-degree DC-SBM variants are obtained by replacing the degree prior without changing the likelihood-computation efficiency.The non-hierarchical version of each model is recovered by enforcing a single hierarchy level, L = 1.

IV. ENSEMBLE EQUIVALENCE

The microcanonical and canonical SBM formulations differ in their generative constraints, but Bayesian marginalization can make their likelihoods exactly equivalent under a specific parametrization and prior. Alternative parametrizations remain distinct model choices that can be compared by marginal likelihood.

  • Canonical versus microcanonical: The canonical SBM imposes degree and edge-count constraints only in expectation, whereas the microcanonical SBM fixes the corresponding structures exactly.The two formulations therefore represent different generative processes before marginalization.
  • Asymptotic relation: Under a compatible parametrization, Stirling’s approximation makes canonical and microcanonical likelihoods asymptotically equivalent when degrees and intergroup edge counts are sufficiently large.For smaller or sparser networks, ensemble differences can remain important.
  • Bayesian equivalence: Bayesian integration over canonical parameters θ and λ with suitable priors yields an exact equivalence to the microcanonical likelihood.The resulting factorization includes the microcanonical likelihood, the noninformative degree-sequence prior, and an edge-count prior.
  • Parametrization choices: The two canonical parametrizations differ in whether expected intergroup edge counts scale with group sizes or remain independent of them.These assumptions generate different ensembles and should therefore be treated as a model-selection problem.
  • Model comparison: For increasingly many groups, structured planted partitions generally favor option 2, with confidence scaling as ln Λ = O(B^2) over most assortativity values.Near a fully random network, option 1 is favored; for equal-sized groups, option 2 is favored when c > (2 ln 2)/B ≈ 1.4/B.
  • Model comparison: Option 2 is preferred for additional reasons because it supports conditioned hyperpriors and more efficient likelihood changes than option 1.The text states that option 1 requires updating O(B) terms when moving a node, while option 2 is more efficient.

V. HOW MANY GROUPS CAN BE INFERRED?

The section examines when inference underestimates the true number of groups and shows that hierarchical priors substantially raise the maximum identifiable group count.

  • Prior choice: Bmax = O(N) with noninformative edge-count priors, whereas hierarchical priors yield Bmax = O(N/ ln N).The logarithmic improvement arises from replacing the noninformative prior with a hierarchical prior over edge counts.
  • Analysis setup: A degree-corrected planted partition with B equal-sized groups and exactly E/B internal edges per group is used to analyze underfitting.There are no edges between distinct planted groups in this construction.
  • Inference limitations: B∗ = min(B, Bmax) for planted partitions, so inference underestimates the true group count when B exceeds Bmax.The analysis compares the true partition with fitted partitions formed by merging planted groups.
  • Prior choice: The noninformative prior incurs a description-length cost −ln P(e) ∼ (B^2/2) ln E when B^2 ≫ E.This prior-driven cost limits the number of groups that can be inferred as networks grow.
  • Prior choice: The hierarchical prior identifies far more groups while retaining protection against overfitting and reducing susceptibility to underfitting.The hierarchical prior includes the noninformative prior as a special case.

VI. INFERENCE ALGORITHM

The inference algorithm samples hierarchical partitions with MCMC, using reversible level-wise moves and efficient proposals whose cost does not grow with the number of groups.

  • Posterior sampling: MCMC moves node memberships across hierarchy levels and accepts or rejects them so equilibrated partitions follow the posterior distribution.The posterior can be sampled level by level while conditioning on the remaining levels.
  • Move proposals: Neighbor-informed proposals sample groups connected to a node’s neighbors while retaining a small random component ϵ to preserve ergodicity.The proposals do not bias partitions toward assortative or non-assortative mixing patterns.
  • Efficiency: O(k_i) proposal generation is independent of B_l, keeping the overall algorithmic complexity O(E).Continuous bookkeeping of edges incident to each group enables this scaling.
  • Efficiency: The proposals improve mixing times and remove explicit dependence on the number of groups, unlike fully random moves.A heat-bath alternative probes all possible moves and incurs complexity that grows linearly with the number of groups.
  • Posterior optimization: Introducing β and taking β → ∞ converts posterior sampling into a greedy heuristic for estimating the maximum.Repeated runs are used to obtain a reliable estimate of the maximum.
  • Efficiency: The algorithm avoids the usual O(EB^2) or O(EB) group-count dependencies without approximating the likelihood.Agglomerative initialization is used to reduce metastable behavior from random starting partitions.

VII. MODEL COMPARISON

The paper compares SBM variants using posterior-based evidence and description length, while distinguishing individual-partition selection from averaging over whole model classes.

  • Partition comparison: Λ1 compares individual hierarchical partitions and model variants through posterior odds, with its logarithm linked to description-length differences under equal prior model probabilities.Λ1 < 1 favors the degree-corrected variant in the comparison described, while larger values favor the alternative.
  • Partition comparison: Λ1 = 1/2 indicates modest evidence for DC-SBM, whereas Λ1 = 1/105 clearly indicates it is much better than NDC-SBM.The criterion quantifies confidence while selecting a model according to MDL.
  • Model-class comparison: Comparing whole model classes requires summing over partitions, because many alternative fits can have similar posterior probabilities.The resulting Bayesian comparison averages statements about the generative model over fits weighted by posterior probability.
  • Model-class comparison: The exact model-class sum is intractable, so the paper estimates it variationally using mean-field and Bethe approximations to posterior entropy.The first-level Bethe approximation retains correlations between adjacent network nodes.

VIII. RESULTS FOR EMPIRICAL NETWORKS

Empirical-network experiments compare hierarchical partitions, posterior sampling, and model variants. The results show that model choice and posterior uncertainty depend on network structure, while the DC-SBM with uniform degree hyperpriors is often favored.

  • Political blogs: In the political-blogs network, all variants recover the liberal–conservative split at the hierarchy’s top level but produce different lower-level subdivisions.The NDC-SBM, DC-SBM with a uniform prior, and DC-SBM with a uniform hyperprior yield B1 values of 42, 23, and 20, respectively.
  • Political blogs: 42, 23, and 20 bottom-level groups are inferred by the NDC-SBM, DC-SBM with a uniform prior, and DC-SBM with a uniform hyperprior, respectively.Their description lengths are approximately 89938, 87162, and 84890 bits in the same order.
  • Model selection: For Email and arXiv hep-th citations, the degree distributions are fairly narrow and are well approximated by exponential distributions.Figure 9 overlays geometric distributions with p = 1/⟨k⟩ on the degree histograms.
  • Political blogs: The DC-SBM is favored for the political-blogs network because its smaller-group solutions also have smaller description lengths.The authors suggest that larger group counts can compensate for models unable to explain degree heterogeneity, while MDL still selects the DC-SBM.
  • Posterior sampling: For scientist collaborations, posterior samples resemble the MDL partition but vary noticeably, and their typical group counts exceed those of the optimal partition.The paper attributes this shift toward more complex models to an entropic effect involving many models with smaller yet comparable likelihoods.
  • Posterior sampling: Across other networks, disagreement between MDL and posterior sampling depends strongly on network structure, while MDL often lies near the posterior mode.The reported agreement concerns the inferred number of groups.
  • Model selection: The DC-SBM with uniform degree hyperpriors most often has the smallest description length, although simpler or alternative variants win for networks with limited evidence or narrow degree distributions.The model-comparison results are broadly consistent when using full posterior probability instead of MDL, but not identical.

IX. DISCUSSION

The microcanonical approach supports deeper Bayesian hierarchies and inference whose complexity is not explicitly dependent on the number of groups. It also separates degree regularities from modular organization and reveals that the shallow microcanonical model matches a Bayesian canonical formulation.

  • IX. DISCUSSION: Deeper Bayesian hierarchies alleviate underfitting and enable efficient inference without explicit dependence on the number of inferred groups.The hierarchical model can uncover small groups in very large networks.
  • IX. DISCUSSION: Degree-corrected SBM priors based on the degree distribution better decouple modular organization from degree regularities.
  • IX. DISCUSSION: The shallow microcanonical model with uniform priors is identical to a Bayesian version of the typical canonical formulation.The paper identifies higher-order Bayesian considerations as the main strength of the approach.
  • IX. DISCUSSION: Bayesian inference can contrast maximizing a single posterior estimate with sampling hierarchical partitions from the posterior.The supplied passage introduces this contrast but does not include the full discussion of its consequences.

Appendix A: Asymptotic degree distributions sampled from uniform priors and hyperpriors

The appendix derives degree distributions from uniform priors and hyperpriors using maximum-entropy constructions. These derivations produce geometric or Bose-Einstein forms and an asymptotic 1/k regime with an exponential cutoff.

  • Appendix A: Asymptotic degree distributions sampled from uniform priors and hyperpriors: The expected degree counts under the relevant constrained ensemble follow the Bose-Einstein distribution.The parameters λ and µ are determined by the imposed constraints.
  • Appendix A: Asymptotic degree distributions sampled from uniform priors and hyperpriors: The canonical ensemble obtained by maximizing entropy under an average-edge constraint yields a geometric degree distribution with mean E/N.Its normalization and constraint are handled through a partition function and Lagrange multiplier.
  • Appendix A: Asymptotic degree distributions sampled from uniform priors and hyperpriors: The canonical degree distribution approaches the microcanonical one asymptotically when the numbers of nodes and edges become sufficiently large.
  • Appendix A: Asymptotic degree distributions sampled from uniform priors and hyperpriors: For small arguments, the asymptotic degree distribution follows 1/k, while larger arguments receive an exponential cutoff.This follows from the large-E and large-N approximation and the resulting asymptotic expression.
  • Appendix A: Asymptotic degree distributions sampled from uniform priors and hyperpriors: Maximum-entropy ensembles with simple constraints can generate 1/k distributions without requiring a non-equilibrium or critical mechanism.The passage attributes this form to randomly choosing among discrete distributions with a fixed average.

Appendix B: Directed networks

The appendix extends the model family to directed networks by adapting likelihoods, priors, and hyperpriors to directed edges and joint in- and out-degree structure.

  • Appendix B: Directed networks: Directed degree-corrected SBM variants use a model likelihood adapted to directed networks.
  • Appendix B: Directed networks: Hierarchical edge-count priors treat the associated multigraphs as directed.
  • Appendix B: Directed networks: The uniform degree prior factors into separate priors for in-degree and out-degree sequences.
  • Appendix B: Directed networks: The conditioned degree prior accounts for the joint in- and out-degree distribution.
  • Appendix B: Directed networks: The NDC-SBM directed variant is obtained analogously through a degree probability and corresponding model likelihood.
Loading 1610.02703v4…