Source-linked AI summary
Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
Tiago P. Peixoto
TL;DR
Inferring modular structure with stochastic block models requires efficient partition inference and principled control of model complexity. The paper combines optimized MCMC with an agglomerative procedure that can also operate as a greedy heuristic. The heuristic produces results comparable to MCMC across many generative-model settings and empirical networks while being significantly faster, though it does not fully saturate MCMC’s detectability range.
Problem
Inferring stochastic block models in large networks requires a method that can search partitions efficiently while controlling the number of blocks and avoiding metastable states.
Method
The paper combines optimized MCMC moves with an agglomerative procedure that becomes a greedy heuristic as β →∞.
Results
The agglomerative heuristic delivers results comparable to MCMC for many empirical networks while being significantly faster.
Takeaways & Limitations
The heuristic is suitable for a large range of generative-model parameters and can be combined with model-selection techniques because it allows control of B.
Takeaways & Limitations
The heuristic does not fully saturate the detectability range of the MCMC method and may require MCMC near the detectability transition.
Abstract
from arXiv · showhide
We present an efficient algorithm for the inference of stochastic block models in large networks. The algorithm can be used as an optimized Markov chain Monte Carlo (MCMC) method, with a fast mixing time and a much reduced susceptibility to getting trapped in metastable states, or as a greedy agglomerative heuristic, with an almost linear $O(N\ln^2N)$ complexity, where $N$ is the number of nodes in the network, independent on the number of blocks being inferred. We show that the heuristic is capable of delivering results which are indistinguishable from the more exact and numerically expensive MCMC method in many artificial and empirical networks, despite being much faster. The method is entirely unbiased towards any specific mixing pattern, and in particular it does not favor assortative community structures.
I. INTRODUCTION
Generative models, especially stochastic block models, provide a principled framework for inferring modular structure while accommodating arbitrary mixing patterns. The paper develops optimized MCMC and agglomerative procedures for efficient inference.
- Stochastic block models divide network nodes into blocks and specify edge probabilities between every pair of blocks.This generalizes community structure to arbitrary mixing patterns, including assortative, bipartite, and core-periphery structures.
- Generative-model inference converts module detection into statistical inference of model parameters from observed network data.The framework can separate noise from structure and avoid spurious communities.
- The paper presents optimized MCMC for efficient sampling and an agglomerative heuristic for fast inference in large networks.The heuristic has O(N ln^2 N) complexity, while the MCMC method reaches the detectability range of arbitrary modular structure at greater computational cost.
II. THE STOCHASTIC BLOCK MODEL
The stochastic block model represents networks through block assignments and inter-block edge counts, with likelihood-based inference selecting partitions that best explain observed data. Model selection is required separately to choose the number of blocks and avoid overfitting.
- Model definition: The stochastic block model divides N nodes into B blocks characterized by edge counts between block pairs.A degree-corrected variant additionally specifies the graph’s degree sequence to capture within-block degree variability.
- Inference: Module detection searches for the node partition maximizing posterior likelihood, equivalently minimizing the microcanonical entropy.The likelihood depends on block edge and node counts through the number of compatible network realizations.
- Inference: The entropy expressions include block halfedge counts and, where relevant, degree-based quantities and the binary entropy function.The formulation assumes n_r ≫1 in the stated expression and extends directly to directed networks.
- Model selection: Minimizing entropy for a fixed B cannot determine the best number of blocks because the optimum decreases toward the trivial B = N partition.Model selection methods such as MDL or Bayesian model selection separate structure from noise and avoid overfitting.
- Inference: Directly finding the entropy-minimizing partition is generally intractable because it requires testing all possible partitions.Approximate or stochastic procedures are therefore needed except for very small networks.
III. MARKOV CHAIN MONTE CARLO
The optimized MCMC updates block assignments using neighbor information while preserving the desired equilibrium distribution. It mixes faster than fully random moves, but random initialization can still produce metastable states.
- The MCMC modifies node block memberships and accepts or rejects moves according to the entropy difference, sampling partitions with probability proportional to e^-St/c after equilibration.
- Neighbor-informed proposals estimate a node’s likely block from a randomly chosen neighbor and current model parameters without inherently favoring assortative structure.
- Metropolis-Hastings acceptance probabilities enforce reversibility, using the entropy change and an inverse-temperature parameter that can help escape local minima.
- The optimized moves require operations independent of the number of blocks and node degree for proposal sampling, while acceptance evaluation costs O(ki) per moved node.
- 10 sweeps versus 100 sweeps: optimized moves have an autocorrelation time of order 10 sweeps, compared with roughly 100 for fully random moves, while both sample the same distribution.
- The relative mixing-time improvement can reach two orders of magnitude, and optimized mixing remains approximately independent of block count in the detectable regime.
IV. AGGLOMERATIVE HEURISTIC
The agglomerative heuristic progressively merges blocks from an overpartitioned configuration, using greedy node moves to reduce metastability while retaining near-linear complexity. It often approaches planted solutions and agrees with MCMC over much of the detectable regime, but can fail near the detectability transition.
- Agglomerative construction: Blocks are merged progressively from B′ > B toward the desired B to escape metastable configurations associated with large blocks.The heuristic supplements each merge step with individual node moves at β →∞.
- Complexity: O(N ln^2 N) is the overall complexity for sparse graphs when B ≪ N, with a worst-case reduction to O(N ln N) when B ∼ N.The complexity is independent of the inferred block count under the stated sparse-graph assumptions.
- Quality: The heuristic almost always avoids metastable configurations and often comes close to or exactly reaches the planted partition.Figure 6 contrasts a locally optimized random initialization with the agglomerative outcome for a PP network.
- Implementation choices: Setting ε = 0 preserves graph-component and bipartite-partition structure throughout the merging procedure, while ε > 0 disables this property when undesired.The parameter choice can therefore preserve structural invariants or allow them to be crossed.
- MCMC counterpart: Using β = 1 between merge steps converts the procedure into a slower, more exact MCMC method that waits for equilibration.After equilibration, β →∞ can be used to find the minimum entropy.
- Detectability: The heuristic and optimal MCMC produce identical results above certain modular strengths, but the heuristic does not saturate the full detectable parameter region.Its poor behavior is confined to a relatively small range where distinguishing the graph from a random graph becomes harder.
- Limitations: The MDL model-selection threshold lies close to the region where the agglomerative algorithm cannot discover the optimal partition.Near the detectability transition, the heuristic is recommended as a component of the full MCMC procedure when higher precision is needed.
V. PERFORMANCE ON EMPIRICAL NETWORKS
On empirical networks, the agglomerative heuristic generally produces partitions comparable to MCMC while running significantly faster, although some optimal partitions show degeneracy. In one case, abrupt MCMC cooling allowed the heuristic to outperform MCMC.
- Empirical comparisons: On the PGP network, the agglomerative heuristic led to better results than MCMC despite being much faster.The MCMC run was more likely to become trapped after abrupt cooling to β →∞, whereas the heuristic avoided β = 1 configurations.
- Empirical comparisons: The agglomerative heuristic delivers results comparable to MCMC for many empirical networks while being significantly faster.Comparisons of normalized mutual information indicate that differences in objective values can arise from minor partition differences.
- Partition similarity: NMI values were generally high but rarely near 1 except for the smallest networks, suggesting degeneracy among optimal partitions.The paper leaves a more detailed analysis of this degeneracy for future work.
VI. CONCLUSION
The paper combines an optimized MCMC method with an agglomerative heuristic for stochastic block-model inference. The heuristic has near-linear complexity in sparse networks and often finds partitions indistinguishable from MCMC, while supporting model-selection workflows.
- Conclusion: The optimized MCMC improves mixing time through optimized proposed node-membership moves, while the agglomerative procedure reduces trapping in metastable states.The heuristic is obtained by increasing the inverse temperature to β →∞.
- Conclusion: O(N ln^2 N) complexity in sparse networks makes the agglomerative heuristic fast for large-network inference.The stated complexity is associated with the β →∞ agglomerative version.
- Evaluation measure: The normalized mutual information NMI is defined using mutual information and the entropies of two network partitions.NMI compares the similarity of partitions {bi} and {ci}.
- Implementation: An efficient C++ implementation is freely available through the graph-tool Python library.The implementation is identified in the paper's note.
- Conclusion: The heuristic finds indistinguishable partitions across a very large range of generative-model parameters and many empirical networks, although it does not fully saturate MCMC's detectability range.The method also permits detailed control of the inferred number of blocks B.
- Conclusion: The heuristic is suitable for use with model-selection techniques because it allows detailed control of the number of inferred blocks B.The conclusion links this capability to established model-selection techniques.
- Comparison with prior methods: Unlike modularity-based agglomerative methods restricted to assortative structures, this algorithm permits node moves between blocks and can correct early bad merges.The comparison concerns the heuristic's flexibility relative to the Clauset et al. algorithm and variants.