📊 statistics

Hierarchical Clustering of Networks via Hierarchical Distance Matrices

This paper introduces the Hierarchical Distance Matrix and a corresponding data-driven algorithm, NHC-TST, to statistically recover the latent hierarchical organization of network populations through recursive spectral splitting and two-sample testing, demonstrating superior performance in both simulations and real-world migration data compared to conventional flat clustering.

Original authors: Li Chen, Nathaniel Josephs, Eric D. Kolaczyk, Lizhen Lin

Published 2026-08-03

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Li Chen, Nathaniel Josephs, Eric D. Kolaczyk, Lizhen Lin

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 the world of data as a giant, bustling library. Usually, when we organize books, we just sort them into flat piles: "Science," "History," "Fiction." But what if the books themselves are alive, constantly changing their stories, and we need to find out not just which pile they belong to, but how they are related to each other? This is the challenge of "network analysis." Think of a network as a map of connections—like a subway map where stations are cities and lines are the routes between them. Scientists use these maps to understand everything from how brains fire to how viruses spread. But often, researchers have many of these maps, not just one. Maybe they have a map of the internet for every day of the year, or a map of friendships for every month of a school year. The big question is: how do we group these changing maps together? Do they just form random piles, or is there a hidden family tree showing how they evolved from one another? Finding this "family tree" is like trying to figure out the history of a language by looking at how different dialects split and changed over time, rather than just grouping them by which country they are spoken in today.

This paper tackles that exact puzzle: how to take a bunch of changing network maps and build their hidden family tree. The authors, Li Chen and colleagues, realized that existing methods were like trying to sort a messy closet by just throwing everything into one big bin or making a flat list. They wanted a way to see the structure of the mess—how some groups are cousins, some are siblings, and some are distant relatives. To do this, they invented a new mathematical tool called a "Hierarchical Distance Matrix." Think of this as a special ruler that doesn't just measure how far apart two networks are, but measures how deep in the family tree they split apart. If two networks are very different, they split off way back at the root of the tree (like humans and fish). If they are similar, they split off recently (like a cat and a dog). The authors then built a smart, step-by-step detective algorithm called NHC-TST. This algorithm acts like a curious explorer who starts at the top of the tree, splits the group of networks in two, and then asks a statistical question: "Are these two new groups actually different, or are they just the same group looking slightly different?" If they are truly different, the explorer splits them again. If not, the explorer stops and says, "Okay, this is a final family branch."

The paper proves that this method works perfectly in theory, provided the networks follow certain rules about how they are built. In their computer simulations, the authors tested their new "explorer" against other existing methods. They created fake networks with known family trees and watched to see who could rebuild the tree correctly. The results showed that their method was incredibly accurate at finding the right groups and the right tree structure, often outperforming the other methods, especially when the networks were sparse or messy. They also tested it on real-world data: a massive dataset of global migration flows from 2019 to 2022. This dataset included 180 countries and 48 monthly maps of how people moved between them. When they applied their method, it didn't just group the months randomly; it uncovered a clear, interpretable story. It showed how the world's migration patterns were stable before the pandemic, how they collapsed into a single "crisis" state when lockdowns hit, how they began to rebound, and how a new shock (the war in Ukraine) created a distinct pattern in 2022. Other methods that just made flat piles missed these subtle, layered changes. The authors conclude that their approach is a powerful new way to see the hidden history in complex, changing networks, offering a clear, data-driven path to understanding how these systems evolve over time.

Technical Summary: Hierarchical Clustering of Networks via Hierarchical Distance Matrices

1. Problem Formulation

The paper addresses the fundamental yet under-explored problem of clustering populations of networks while recovering their latent hierarchical organization. While numerous methods exist for flat clustering of networks (e.g., random-effects models, measurement-error models, multilayer network approaches, and Bayesian nonparametric methods), they typically produce a flat partition without capturing the nested, multiscale relationships between clusters. Existing hierarchical approaches for networks, such as those based on the Louvain method or hierarchical agglomerative clustering of Stochastic Block Models (SBMs), often generate dendrograms that are merely traces of greedy splits toward a flat solution rather than recovering a meaningful latent hierarchical structure.

The authors formalize the goal as recovering two components simultaneously:

The graph-level cluster assignment for each observed network.
The underlying hierarchical tree structure governing the populations of networks.

To make this statistically well-defined, the paper introduces the concept of a Hierarchical Distance Matrix (HDM). This is a specific class of population-level distance matrices that encodes latent hierarchical organization through recursively nested distance separation. The HDM framework accommodates unbalanced tree depths and requires that clusters separating earlier in the hierarchy exhibit larger population dissimilarities than those separated at deeper levels.

2. Methodology: NHC-TST

The authors propose a fully data-driven, top-down procedure called Network Hierarchical Clustering based on Two-Sample Testing (NHC-TST). The algorithm recursively partitions networks without requiring prior knowledge of the number of clusters or the tree depth.

Core Components

Distance Estimation: The procedure begins by estimating the link-probability matrix for each network using Neighborhood Smoothing (NBS) or Modified Neighborhood Smoothing (MNBS). A normalized population distance matrix $\hat{D}$ is then constructed using the Frobenius norm of the differences between these estimated matrices.
Spectral Bipartitioning: At each recursive step, the algorithm partitions the current set of networks into two subgroups using spectral clustering. Two variants are proposed:
- NHCL-TST: Operates on the Laplacian of the estimated distance matrix ( $L_{\hat{D}}$ ). It uses the dominant eigenvector to assign binary labels.
- NHCD-TST: Operates directly on the estimated distance matrix $\hat{D}$ . It uses the minimal eigenvector to assign binary labels.
Adaptive Stopping Rule: A graph-based two-sample test (based on Chen et al., 2024) is employed to determine if the current partition is statistically significant. If the test rejects the null hypothesis (that the two subgroups come from the same population), the procedure recurses on each subgroup. If the test fails to reject, the branch terminates.

3. Theoretical Contributions

The paper establishes rigorous theoretical guarantees for the proposed methods:

Exact Recovery (Population Level): Assuming the true distance matrix $D$ is an HDM, the authors prove that both NHCL and NHCD exactly recover the true bipartition at every recursive split. This relies on the spectral properties of the Laplacian (for NHCL) and specific separation conditions on the distance matrix entries (for NHCD).
Statistical Consistency (Empirical Level): The paper proves that when the true distance matrix is replaced by an estimator $\hat{D}$ (derived via NBS), the methods remain consistent. Specifically, under bounded estimation error and sufficient separation margins, the sign pattern of the empirical eigenvectors converges to the population sign pattern with probability approaching 1.
Full Topology Recovery: By integrating the two-sample testing stopping rule, the authors establish that the full NHCL-TST algorithm recovers the true underlying hierarchical topology with probability tending to 1 as the number of nodes $n$ increases, provided the embedded two-sample test is asymptotically powerful.

4. Experimental Results

The authors evaluate NHC-TST against state-of-the-art competitors (HICL-SBM, ALMA, NCGE, NCLM, NSBM) across three simulation scenarios and a real-world application.

Simulations

Settings: Experiments were conducted on hierarchical smooth graphons, hierarchical SBMs, and non-uniform hierarchical smooth graphons (with unbalanced tree depths and mild violations of HDM monotonicity). Both dense and sparse network regimes were tested.
Metrics: Performance was measured using Normalized Mutual Information (NMI) for clustering accuracy, the estimated number of clusters, the Cophenetic Correlation Coefficient (CPCC) adapted for hierarchical topology recovery, and computational efficiency.
Findings:
- Accuracy: NHC-TST variants (both NHCL and NHCD) consistently achieved high NMI scores, often outperforming competitors, particularly as the number of nodes increased.
- Topology Recovery: NHC-TST variants demonstrated superior CPCC scores (approaching 1), indicating accurate recovery of the latent hierarchical structure, whereas flat clustering methods and HICL-SBM showed lower topological fidelity.
- Efficiency: NHC-TST was highly efficient, ranking second only to NCLM in speed, while HICL-SBM incurred significantly higher computational costs.
- Robustness: The methods maintained performance even in non-uniform hierarchical settings with mild violations of the HDM monotonicity assumption.

Real-World Application: Global Migration Networks

The method was applied to a dataset of 48 monthly global migration networks (180 countries) from January 2019 to December 2022.

Results: NHC-TST successfully identified interpretable multi-resolution temporal structures.
- NHCL-TST identified three clusters, isolating the severe COVID-19 crisis period as a distinct state and grouping pre-pandemic and post-rebound periods together.
- NHCD-TST provided a finer-grained four-cluster structure that aligned with key historical markers: pre-pandemic, pandemic onset, rebound, and the post-rebound period (which included the Russia-Ukraine war).
Interpretation: The hierarchical splits revealed that migration networks reverted to pre-shock structures after the pandemic stabilized, but were subsequently altered by geopolitical conflicts. Flat clustering methods failed to capture these nested temporal relationships or produced fragmented, uninterpretable partitions.

5. Significance and Claims

The paper claims to provide the first method capable of recovering a hierarchical structure that is meaningfully related to cluster splits, rather than simply tracing a greedy optimization path.

Novelty: The introduction of the Hierarchical Distance Matrix formalizes the geometry of tree-organized network populations, and the NHC-TST algorithm offers a fully data-driven approach that adaptively determines the branching structure.
Statistical Rigor: The work provides theoretical guarantees for exact recovery and consistency, bridging the gap between spectral clustering and hypothesis testing in the context of network populations.
Practical Utility: The application to global migration data demonstrates the method's ability to uncover interpretable, multi-resolution temporal dynamics that flat clustering approaches miss, offering valuable insights for policymakers regarding the permanence of structural shifts in global systems.

The authors conclude that the combination of structural insight (via HDM) and statistical adaptivity (via two-sample testing) translates into state-of-the-art practical performance for hierarchical network clustering. Future work is suggested to extend the framework to non-binary trees, weighted networks, and dynamic network models.