Research map / Graph learning / Graph algorithms and clustering
From Your Block to Our Block: How to Find Shared Structure Between Stochastic Block Models over Multiple Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes shared stochastic block models (SSBM) that let multiple unaligned graphs share s block connectivity parameters, proves NP-hardness, and gives MCMC, ILP, and greedy fitting methods evaluated on synthetic, ADHD brain, and Wikipedia graphs.
Problem
Finding whether multiple unaligned graphs of different sizes share blocks with similar connectivity structure, i.e., fitting SBMs over several graphs that share parameters for s blocks.
Approach
Model n graphs with separate SBMs whose parameters are constrained to be identical for s blocks chosen across graphs; fit either jointly via MCMC with simulated annealing, or in two stages (per-graph SBM then choose shared blocks via ILP or greedy).
Key results
- Fitting the shared SBM is NP-hard and inapproximable even for n=2 graphs, via reduction from k-clique.
- On synthetic data, MultilevelSBM followed by ILP for shared blocks gives Shared ARI close to ground truth, and BIC recovers the true number of shared blocks (3).
- Greedy shared-block selection runs in under one second on large Wikipedia graphs, and the Shared model achieves a better log-likelihood than single SBM (-5.036e9 vs -5.050e9).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| fit SBMs with shared parameters using MCMC instead of fitting each graph separately | Wikipedia networks · English and Chinese Wikipedia networks | log-likelihood: -5.050×10^9 -> -5.036×10^9 | Helped |
| incorporate shared blocks selected by Greedy | Wikipedia network SBMs · English and Chinese Wikipedia networks | BIC | Helped |
| use MCMC with an agglomeration heuristic to initialize per-graph SBMs, then use ILP to select shared blocks | SSBM inference pipeline · Synthetic graphs | Shared ARI | Helped |
| use ILP rather than Greedy or Random to select shared blocks with true block assignments | SSBM-fixed · Synthetic graphs with true block assignments | Shared ARI | Helped |
| use ILP-selected shared blocks rather than no shared blocks | Multilevel SBM · Synthetic graphs | BIC | Helped |
| use ILP-selected shared blocks rather than no shared blocks | Multilevel-initialized single SBM · Synthetic graphs | BIC | Helped |
| use ILP-selected shared blocks rather than no shared blocks | Multilevel-initialized shared SBM · Synthetic graphs | BIC | Helped |
| use ILP-selected shared blocks rather than no shared blocks | Multilevel-initialized single SBM · Synthetic graphs | log-likelihood | Hurt |
| use ILP-selected shared blocks rather than no shared blocks | Multilevel-initialized single SBM · Synthetic graphs | BIC | No clear effect |
| use Greedy rather than ILP to select shared blocks | SSBM-fixed · Synthetic graphs | runtime | Helped |
| use multilevel initialization for shared MCMC rather than shared MCMC alone | SSBM inference · Synthetic graphs | partition ARI | Helped |
| use multilevel initialization for single-graph MCMC rather than multilevel alone | Single-graph SBM inference · Synthetic graphs | Shared ARI | No clear effect |
Surprising findings
- Running the ILP on large Wikipedia graphs took prohibitively long, while greedy finished in under a second.
- Refining with the MCMC single-SBM step after the multilevel fit did not improve shared-block recovery, unlike multilevel plus ILP.
Limitations
- ILP and greedy complexity grow exponentially with the number of graphs n.
- Shared blocks are restricted to injective one-to-one mappings between blocks of different graphs.
- Wikipedia case study lacks node labels, so shared blocks could not be interpreted.
Experimental setup
Datasets: synthetic SBM graphs (200-500 vertices) NITRC ADHD-200 resting-state brain networks English and Chinese Wikipedia link networks (KONECT)
Benchmarks: synthetic SBM graphs ADHD-200 brain networks English and Chinese Wikipedia networks
Metrics: adjusted Rand index log-likelihood BIC running time
Baselines: SingleSBM (MCMC per graph) MultilevelSBM (agglomerative MCMC) Random block selection Greedy shared-block selection
Builds on: stochastic block model MCMC block inference (graph-tool) Bayesian information criterion
Closest papers by meaning
- Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 2024 · similarity 0.89)
- Network two-sample test for block models (NeurIPS 2025 · similarity 0.88)
- Multi-View Stochastic Block Models (ICML 2024 · similarity 0.87)
- Differentially private exact recovery for stochastic block models (ICML 2024 · similarity 0.87)
- SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.86)
- Convergence Guarantees for the DeepWalk Embedding on Block Models (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.