📊 statistics

Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models

This paper bridges maximum likelihood and optimal transport by demonstrating that unregularized semi-relaxed Gromov-Wasserstein estimators consistently recover Stochastic Block Model parameters and, when augmented with sparsity-promoting mechanisms, enable efficient simultaneous inference and model selection without costly grid searches.

Original authors: Simon Queric, Cédric Vincent-Cuaz, Charles Bouveyron, Marco Corneli

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Simon Queric, Cédric Vincent-Cuaz, Charles Bouveyron, Marco Corneli

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Organizing a Chaotic Party

Imagine you walk into a massive, noisy party with thousands of people. You don't know anyone, and there are no name tags. However, you notice a pattern: people tend to stand in groups, and the people in one group talk to each other much more often than they talk to people in other groups.

Your goal is to figure out who belongs to which group and what the "rules" of conversation are for each group (e.g., "Group A loves jazz," "Group B loves sports").

In the world of data science, this is called a Stochastic Block Model (SBM). It's a mathematical way to describe networks (like social media friends or biological proteins) where nodes (people) are hidden in clusters.

The Problem: The "Fuzzy" Map

Traditionally, scientists try to solve this by finding the "most likely" arrangement of groups. The paper calls this Maximum Likelihood.

Think of this like trying to draw a map of the party. The old method uses a "fuzzy" approach. It tries to smooth out the edges to make the math easier to solve.

The Analogy: Imagine trying to sort a pile of mixed Lego bricks into buckets. The old method says, "Let's put a little bit of every brick into every bucket so the math works out."
The Result: You get a map where every bucket has a tiny bit of everything. This is great for finding the general shape, but it's terrible for deciding how many buckets you actually need. If you have 5 groups, the fuzzy map might say you need 5.1 buckets, or it might spread the 5 groups across 10 buckets, making it impossible to know the true number of groups.

The New Idea: The "Optimal Transport" Move

The authors of this paper introduce a new way to solve this puzzle using a concept called Optimal Transport (OT).

The Analogy: Imagine you are a logistics manager. You have a warehouse full of boxes (the people at the party) and a set of delivery trucks (the groups). Your job is to move the boxes onto the trucks so that the "distance" between how the boxes interact with each other and how the trucks interact with each other is minimized.
The Twist: The authors realized that the old "fuzzy" math they were using was actually a specific, slightly messy version of this logistics problem. They called it a "semi-relaxed" version.

The Breakthrough: Making the Map "Sparse"

The paper's main discovery is that the "fuzziness" (mathematically called entropic regularization) is actually the enemy when you want to know the exact number of groups.

The Fix: The authors decided to remove the "fuzziness" and force the logistics manager to be strict. Instead of putting a little bit of every brick in every bucket, they forced the manager to put only the right bricks in the right buckets.
The Result: This creates a sparse solution. Some buckets end up completely empty.
- If you start with 20 buckets and only 5 are needed, the math naturally empties out 15 of them.
- This allows the computer to automatically figure out the number of groups without needing a human to guess or try different numbers one by one (which is slow and expensive).

What They Proved and Tested

The Theory: They proved mathematically that if you have enough people at the party (a large number of nodes), this new "strict logistics" method will eventually find the exact correct groups and the exact correct conversation rules. It's consistent.
The Experiment: They tested this on computer-generated parties with different types of social structures:
- Assortative: People stick with their own kind (like-minded groups).
- Hub: One super-popular person connects to everyone, while others stay in their own circles.
- Disassortative: People actively avoid their own kind.
The Outcome: Their new method was just as good at finding the groups as the best existing methods, but it was much faster (10 to 100 times faster on a standard computer). Crucially, it successfully identified the correct number of groups automatically, whereas other methods often struggled with this or required slow, trial-and-error searching.

Summary

The paper bridges two complex fields: Optimal Transport (logistics of moving things) and Stochastic Block Models (finding hidden groups in networks).

They showed that by treating the problem as a strict logistics puzzle rather than a fuzzy probability problem, they can:

Find the hidden groups accurately.
Automatically count how many groups exist (by letting empty groups disappear).
Do it all in a single, fast calculation, avoiding the need for slow, repetitive guessing games.

It's like upgrading from a blurry, guess-and-check map to a precise GPS that tells you exactly where you are and how many stops you need to make, all in one go.

Technical Summary: Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models

Problem Statement
The paper addresses the challenge of inference and model selection in Stochastic Block Models (SBMs), a generative framework for random graphs where nodes are partitioned into hidden clusters, and edge probabilities depend on cluster membership. While SBMs offer advantages over alternative clustering methods (such as modularity maximization or spectral clustering) by recovering diverse structures and providing tools for estimating the number of clusters, standard inference often relies on Variational Expectation-Maximization (VEM). A critical limitation of VEM is its reliance on entropic regularization to ensure optimization smoothness. This regularization prevents transport plans from becoming sparse, thereby hindering "intrinsic model selection"—the ability to automatically deactivate unnecessary clusters (assigning them zero mass) within a single optimization problem. Consequently, current approaches often require computationally expensive grid searches or heuristic procedures to determine the optimal number of clusters ( $K$ ).

Methodology
The authors propose a novel framework that interprets Maximum Likelihood Variational Inference (MLVI) in SBMs through the lens of Optimal Transport (OT), specifically utilizing the Semi-Relaxed Gromov-Wasserstein (srGW) divergence.

Reformulation as srGW: The paper establishes that the ELBO (Evidence Lower Bound) maximization in SBM is equivalent to minimizing a srGW divergence with an entropic regularization term. The loss function corresponds to the negative log-likelihood of the generative model.
Unregularized Estimators: Recognizing that entropic regularization prevents sparsity, the authors investigate unregularized srGW estimators. They define estimators for the connectivity matrix ( $\Theta$ ) and the transport plan ( $T$ , representing cluster assignments) by minimizing the srGW loss without the entropy term.
Sparsity-Promoting Regularization for Model Selection: To enable automatic model selection (estimating $K$ ) without grid search, the authors introduce an $\ell_{1/2}$ pseudo-norm penalty on the transport plan. This penalty encourages the estimated cluster proportions to be sparse, effectively setting the mass of non-optimal clusters to zero.
Optimization: The parameters are estimated using a Block Coordinate Descent algorithm. This alternates between:
- Updating the connectivity matrix $\Theta$ using closed-form solutions derived from the first-order optimality conditions.
- Updating the transport plan $T$ using a Majorization-Minimization (MM) algorithm, which linearizes the sparsity penalty and solves the resulting quadratic problem (e.g., via Frank-Wolfe).

Key Contributions

Theoretical Link: The paper proves that MLVI in SBMs can be interpreted as a semi-relaxed Gromov-Wasserstein projection with entropic regularization.
Consistency Results: The authors prove that the unregularized srGW estimators consistently recover both the true SBM connectivity matrix and the latent cluster assignments in the asymptotic regime ( $N \to \infty$ ).
Automatic Model Selection: By incorporating a sparsity-promoting penalty, the method allows for the simultaneous recovery of model parameters and the selection of the number of clusters in a single optimization step. This avoids the need for costly grid searches or greedy heuristics.
Algorithmic Efficiency: The proposed solver is designed for efficiency, with a theoretical complexity dominated by gradient computation ( $O(N^2K + K^2N)$ ), and is shown to be significantly faster on CPUs compared to state-of-the-art variational estimators.

Results
The authors evaluate their approach on synthetic data generated from Bernoulli SBMs under three connectivity regimes: Assortative, Hub, and Disassortative.

Clustering Performance: The proposed srGW estimator using a negative log-likelihood loss (srGW-NLL) consistently outperforms or matches state-of-the-art baselines (including Louvain, Infomap, Greed, and Variational Estimators) in terms of Adjusted Rand Index (ARI), particularly in Hub and Disassortative regimes where structural assumptions of other methods are violated.
Model Selection: The method successfully recovers the true number of clusters ( $K^*$ ) across various hyperparameter settings, demonstrating a plateau in performance when the sparsity parameter is tuned appropriately.
Efficiency: The srGW-NLL method is reported to be 1 to 2 orders of magnitude faster on CPU than the Variational Estimator and Greed methods, primarily because it bypasses the iterative model selection loops required by those approaches.

Significance and Claims
The paper claims to provide a unified theoretical and practical bridge between Optimal Transport and Stochastic Block Models. Its primary significance lies in demonstrating that OT-based estimators are not only consistent for parameter recovery but can also perform intrinsic model selection through sparsity promotion. This offers a computationally efficient alternative to traditional likelihood-based methods that struggle with the combinatorial complexity of selecting the number of clusters. The authors position their work as a step toward more robust and efficient graph partitioning, particularly in scenarios where the number of communities is unknown and the graph structure is complex (e.g., containing hubs or disassortative patterns). They note that while the asymptotic consistency is proven, the tuning of the sparsity hyperparameter remains an area for future investigation, and the method's performance on real-world networks is a subject for further study.