Research map / Graph learning / Graph algorithms and clustering

Multi-View Stochastic Block Models

ICML 2024 · Graph learning › Graph algorithms and clustering · approach: Anchor-based multi-view clustering · 1 citations (OpenAlex)

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.

Formalizes the multi-view stochastic block model, gives a polynomial-time late-fusion algorithm needing only O(log k) views for weak recovery (vs. k^2 for union graph), and an information-theoretic lower bound for black-box algorithms.

Problem

Recovering a shared k-community labeling from multiple graphs (views) that each carry only partial information about the communities, where each view is a 2-community SBM with a view-specific label mapping.

Approach

Run a specialized pairwise weak-recovery estimator on each view separately (late fusion), sum the pairwise estimates across views, and build a neighborhood-intersection graph from which second-moment rounding recovers communities; this beats early fusion (clustering the union graph), which needs k^2 views.

Key results

• Weak recovery in polynomial time with t = O(log k) views, each above the Kesten-Stigum threshold, versus Omega(k^2) views needed when clustering the union graph.
• Information-theoretic lower bound: black-box estimators need t = Omega(log k / C_T) views.
• Synthetic experiments (n=1000, k=10, t=10) show the late-fusion variant outperforms Louvain on the union graph across epsilon and d ranges.

Surprising findings

• Clustering the union graph of views is provably suboptimal: it requires Omega(k^2) views, whereas late fusion needs only O(log k).

Limitations

• The main estimator relies on a high-order sum-of-squares program that is hard to implement in practice; experiments use Louvain as a substitute.
• Analysis restricted to two-community views with k communities overall; extension to views with more than two communities left open.
• Exact phase transition for the multi-view model is not characterized.

Experimental setup

Datasets: synthetic multi-view SBM instances

Benchmarks: synthetic multi-view SBM

Metrics: agreement R(z_hat, z)

Baselines: Louvain on union graph (early fusion)

Builds on: stochastic block model Kesten-Stigum threshold Louvain algorithm

Closest papers by meaning

• A Non-parametric Graph Clustering Framework for Multi-View Data (AAAI 2024 · similarity 0.88)
• From Your Block to Our Block: How to Find Shared Structure Between Stochastic Block Models over Multiple Graphs (AAAI 2025 · similarity 0.87)
• Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.87)
• Multi-View Clustering by Inter-cluster Connectivity Guided Reward (ICML 2024 · similarity 0.87)
• Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 2024 · similarity 0.87)
• SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.87)