📊 statistics

Simulation-consistent Estimation of the Marginal Likelihood for Block Models

This paper proposes a simulation-consistent, asymptotically normal, and label-switching-invariant estimator for computing marginal likelihoods of block models using MCMC samples, demonstrating its effectiveness through analytical benchmarks and an application to a COP28 social network dataset.

Original authors: Martin Metodiev, Marie Perrot-Dockès, Guilhem Fouetillou, Pierre Latouche, Adrian E. Raftery

Published 2026-07-28

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Martin Metodiev, Marie Perrot-Dockès, Guilhem Fouetillou, Pierre Latouche, Adrian E. Raftery

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

Imagine you are walking into a massive, chaotic party where thousands of people are mingling, shouting, and sharing stories. Your goal is to figure out who belongs to which group. Are the people in the corner discussing the latest sci-fi movie a different crowd from the ones by the punch bowl debating climate change? In the world of data science, this party is a "network," and the groups are called "clusters." Scientists use mathematical tools called "block models" to map these invisible social circles. But here's the tricky part: just like trying to guess the perfect number of groups at a party without knowing the answer, it's incredibly hard to know if you've found the right number of clusters. You might guess there are 5 groups, or maybe 50, and without a reliable way to check, you could be completely wrong. This is a huge problem because if you can't count the groups accurately, you can't understand how information, ideas, or even viruses spread through a network.

This is where a new method called THAMES (Truncated Harmonic Mean Estimator for Block Models) comes in, acting like a super-smart, simulation-powered detective. The researchers behind this paper, led by Martin Metodiev and colleagues, have built a tool that can calculate the "score" of different group configurations to see which one makes the most sense. Unlike older methods that often get stuck, give up, or produce wildly unstable results, THAMES is designed to be "simulation-consistent." Think of it like tasting a soup: if you take one spoonful, you might not know if it's salty enough. But if you keep taking more and more spoonfuls (simulations), your taste gets more and more accurate until you are absolutely sure. THAMES does this for network data, allowing scientists to confidently determine the true number of hidden groups, even in massive, messy datasets. They tested this on a real-world example involving millions of posts about a major climate conference, proving it can find clear patterns where other methods get confused.

The Problem: The "Label Switching" Mix-Up

To understand why this new tool is so special, we first need to look at the messiness of the data. Imagine you are sorting a pile of colored marbles into buckets. You have red, blue, and green marbles. But in the computer's mind, the "red" bucket might be called "Bucket 1" today and "Bucket 3" tomorrow, even though it's holding the exact same marbles. This is a phenomenon called label switching.

In the complex math used to analyze networks, the computer runs a simulation (a bit like a virtual experiment) thousands of times to figure out the groups. Because of label switching, the computer might say, "Okay, in this run, the climate activists are Group A," and in the next run, "The climate activists are Group B." If you try to average these results, you get a giant, confusing mess. It's like trying to calculate the average height of a group of people if, every time you measure someone, you randomly swap their names with someone else's. The average becomes useless.

Most existing methods for counting network groups struggle with this. They either break down when the data gets too big, or they rely on shortcuts (called approximations) that work well in theory but can be wildly inaccurate in real life. Some methods are like guessing the number of jellybeans in a jar by looking at the glass; others are like trying to count them by shaking the jar and hoping they don't stick together. The authors argue that these older ways are often unreliable, especially when the data is finite (not infinite) and the groups are hard to distinguish.

The Solution: THAMES, the "Truncated" Detective

The paper introduces THAMES, a new way to calculate the "marginal likelihood." In plain English, the marginal likelihood is a score that tells you how well a specific number of groups explains the data you have. A higher score means the model is a better fit.

The authors created THAMES by combining two existing ideas but fixing their biggest flaws.

The Harmonic Mean Estimator: This is an old trick that is easy to calculate but notoriously unstable. It's like trying to balance a house of cards in a hurricane; one small gust (a weird data point) can knock the whole thing over.
The Variational Approximation: This is a fast, smart guess based on a simplified version of the problem. It's usually accurate but can be biased (slightly wrong) because it's a simplification.

THAMES takes the best of both worlds. It uses the smart guess to define a "truncation set"—a specific, manageable list of the most likely group configurations to focus on. By ignoring the weird, unlikely outliers (the "tail" of the distribution), it avoids the instability of the old Harmonic Mean method. At the same time, it uses the actual simulation data to ensure the result is accurate, avoiding the bias of the simplified guess.

Crucially, THAMES is symmetric. This means it doesn't care if the computer calls a group "Cluster 1" or "Cluster 100." It treats all the groups as a single, unified set. This solves the "label switching" problem automatically. If the computer swaps the names of the groups, the THAMES score stays exactly the same. It's like a judge who cares only about the quality of the performance, not the name of the contestant.

The Proof: Simulations and Real-World Tests

The authors didn't just build this tool; they put it through the wringer.

The Simulation Test:
They created fake networks where they knew the exact answer (the "true" number of groups). They tested THAMES against other popular methods, including the old Harmonic Mean estimator and a method called ChibPartition.

The Result: As the number of simulations increased (from 1,000 to 10,000), the error in THAMES's calculation went down steadily. It was "simulation-consistent," meaning the more they ran the simulation, the closer they got to the truth.
The Comparison: The old Harmonic Mean estimator was all over the place, sometimes failing completely when the data was tricky. The ChibPartition method worked well only when one specific group was overwhelmingly popular, but it crashed when the groups were more evenly matched. THAMES, however, remained stable and accurate across all scenarios.

The Real-World Test: COP28
To see if THAMES could handle a real, messy situation, the authors applied it to a massive dataset from the 2023 United Nations Climate Change Conference (COP28). They scraped over 4 million posts from the social network X (formerly Twitter), which involved over 1 million users. After cleaning it up, they analyzed a network of about 11,000 users.

The Finding: THAMES determined that the network was best explained by 12 distinct clusters.
The Contrast: They compared this to a popular alternative method called ICL (Integrated Complete Likelihood), which suggested there were 37 clusters.
The Insight: When the authors looked at the 37 clusters from the ICL method, they found them to be "fractured." For example, the ICL method split the core group of influential figures (like Al Gore and UN Climate Change) into multiple tiny, separate groups. It also broke the #SaveSoil movement into four different, disconnected clusters.
The THAMES View: In contrast, the 12 clusters found by THAMES made much more sociological sense. It identified a clear "core-periphery" structure. There was one tiny, central cluster (Cluster 11) containing just 5 users: UN Climate Change, Al Gore, COP28 UAE, Loss and Damage Collaboration, and António Guterres. All other users in the network were "periphery" groups that mostly quoted or reposted this central core. This revealed a star-shaped pattern where a few dominant voices drove the conversation, and everyone else was reacting to them.

The authors note that this structure makes sense in the real world: major climate events often have a few central figures who dominate the narrative, while grassroots movements and bots orbit around them. The fact that THAMES found this clean, logical structure, while the other method found a chaotic mess of 37 tiny groups, suggests that THAMES is better at finding the "true" hidden structure in complex social networks.

Why This Matters

The paper concludes that THAMES is a significant step forward because it is the first method of its kind that is both simulation-consistent (gets more accurate with more computing power) and invariant to label switching (doesn't get confused by naming conventions).

While the authors are careful to note that this is a tool for estimation and model selection rather than a magic bullet that solves every problem in network science, the results are compelling. They show that by combining smart approximations with rigorous simulation, we can finally count the invisible groups in our digital world with much greater confidence. Whether it's understanding how climate information spreads, how political bubbles form, or how diseases move through a population, having a reliable way to count the groups is the first step to understanding the whole picture.

In short, THAMES is the new, reliable ruler for measuring the hidden shapes of our social networks, proving that sometimes, the best way to find the truth is to stop guessing and start simulating with precision.

Technical Summary: Simulation-consistent Estimation of the Marginal Likelihood for Block Models

Problem Statement
The stochastic block model (SBM) is a standard random graph model for node clustering, capable of handling heterogeneous structures like communities or star patterns. However, a major unsolved problem in SBM inference is the estimation of the number of clusters ( $G$ ). From a Bayesian perspective, the optimal model selection criterion is the model that maximizes the product of the marginal likelihood and the prior model probability. Yet, the marginal likelihood $Z(G)$ involves a sum over all possible cluster configurations, which grows exponentially with network size, rendering it computationally intractable.

Existing methods for estimating the number of clusters in SBMs rely on asymptotic approximations or variational approximations. While these may be reasonable in limiting cases where network size grows, there are no known consistency results for these approximations regarding finite data sizes. Furthermore, most simulation-consistent marginal likelihood estimators (which converge as the number of simulations increases) require the evaluation of the likelihood function, which is impossible for the SBM due to the intractable sum over configurations. Additionally, standard Bayesian MCMC estimation of SBM parameters suffers from the "label switching" problem, where parameters randomly switch labels, causing high variance in ergodic estimators.

Methodology: The Truncated Harmonic Mean Estimator (THAMES)
The authors propose the Truncated Harmonic Mean Estimator (THAMES), a simulation-consistent estimator for the marginal likelihood of the SBM that does not require evaluating the intractable likelihood function. The method relies on the "collapsed" distributions of the latent allocation vectors, which are available in simple analytic forms.

The core of the methodology involves the following steps:

Reciprocal Importance Sampling (RIS) Framework: The estimator is framed within the RIS context, where the inverse marginal likelihood is estimated by averaging the ratio of a proposal density $h(C)$ to the posterior density.
Symmetry and Label Switching: To address label switching, the estimator is constructed to be symmetric (invariant to label permutations). This is achieved by averaging over permutations or by defining the proposal density over symmetric sets.
Truncation Strategy: The THAMES combines the uniform density of the ChibPartition estimator with a variational approximation used in Variational Bayes Reciprocal Importance Sampling (RISVB). It defines a truncation set $A$ $A$ (a subset of the allocation vector space) to reduce variance.
- The set $A$ is constructed as the intersection of a Cartesian product set $E_{\hat{C}, \hat{r}}$ (based on the most probable allocation vectors from the first half of the MCMC sample) and a Highest Posterior Density (HPD) region $H_\alpha$ .
- The parameter $\alpha$ is chosen empirically to minimize the sample variance of the estimator.
Efficient Computation: A key contribution is an algorithmic optimization that drastically reduces computational cost. Instead of summing over all $G!$ permutations (which is superexponential), the method identifies a lexicographical ordering of the allocation vectors. Under the condition that there are no empty clusters in the second half of the MCMC sample, the sum over permutations can be reduced to a sum over a much smaller set $\Omega$ , often containing only one element.
Handling Empty Clusters: If empty clusters occur in the MCMC sample, the authors utilize an extension of Nobile's formula to relate the marginal likelihood of a model with $G$ clusters to one with $G-1$ clusters, allowing the estimator to proceed without the empty cluster.

Key Contributions

First Simulation-Consistent Estimator for SBM: To the authors' knowledge, this is the first estimator presented that converges to the marginal likelihood with an increasing number of simulations, even when the network size is fixed and small.
Theoretical Properties: The THAMES is proven to be simulation-consistent and asymptotically normal with finite variance under standard conditions. It is also symmetric, making it invariant to the label switching problem.
Computational Efficiency: The method allows for efficient computation even for models with a large number of components by avoiding the full permutation sum and not requiring the evaluation of the likelihood function.
Applicability: The approach is applicable to the SBM and, by analogy, to the Latent Block Model (LBM) for co-clustering.

Results
The performance of THAMES was evaluated through simulation studies where the true marginal likelihood could be computed analytically (using small networks with $n=10$ and $G=2$ ).

Convergence: The error between the log of the THAMES estimate and the true log marginal likelihood decreased as the MCMC sample size ( $T$ ) increased, confirming simulation consistency.
Comparison: THAMES was compared against the Harmonic Mean Estimator (HME), the ChibPartition estimator, the RISVB estimator, and variational approximations (ILvb).
- The HME was found to be unstable, particularly when the posterior distribution was highly concentrated.
- Variational estimators (ILvb) showed bias, particularly when the variational assumptions did not hold (e.g., in low $\lambda$ regimes), and required a correction factor ( $G!$ ) to account for focusing on a single mode.
- In a specific simulation mimicking the COP28 dataset (where the posterior probability of the Maximum A Posteriori (MAP) estimator was extremely low and no repetitions occurred in the sample), THAMES significantly outperformed other estimators. The ChibPartition estimator failed in this low-probability setting because the set of repeated MAP states was empty.
Real-World Application (COP28): The method was applied to a social network dataset derived from the 2023 United Nations Climate Change Conference (COP28), containing over 1 million nodes and 2 million edges (preprocessed to ~11k nodes).
- THAMES estimated the optimal number of clusters to be $G=12$ .
- In contrast, the Integrated Complete Likelihood (ICL) criterion, using a greedy algorithm, estimated $G=37$ .
- The THAMES clustering revealed a core-periphery structure where a small core cluster (Cluster 11, size 5) containing key figures (e.g., Al Gore, UN Climate Change) was quoted/reposted by all other clusters, while internal connections within other clusters were rare. This structure was interpreted as an "asymmetric disassortative mixing" pattern.
- The ICL result was described as "fractured," splitting the core and specific movements (like #SaveSoil) into multiple small, unstable clusters, whereas THAMES provided a more robust structural identification.

Significance and Claims
The paper claims that THAMES provides the first simulation-consistent tool for determining the number of clusters in block models, addressing a critical gap in Bayesian model selection for network data. By being invariant to label switching and computationally efficient, it enables the use of marginal likelihoods for model comparison in settings where previous methods were either inconsistent or intractable. The application to the COP28 dataset demonstrates its practical utility in identifying meaningful social structures in large-scale, sparse networks, offering insights into the core-periphery dynamics of online climate discourse that alternative methods (like ICL) may obscure through over-segmentation. The authors note that while the method relies on collapsed distributions, future work could explore extending simulation-consistent estimation to models where such distributions are not available.

The Problem: The "Label Switching" Mix-Up

The Solution: THAMES, the "Truncated" Detective

The Proof: Simulations and Real-World Tests

Why This Matters

More like this