Hierarchical Clustering of Networks via Hierarchical Distance Matrices
TL;DR
The Hierarchical Distance Matrix is introduced, a specific class of population-level distance matrices that encodes latent hierarchical organization through recursively nested distance separation, accommodating unbalanced tree depths, in a fully data-driven top-down procedure: network hierarchical clustering based on two-sample testing (NHC-TST).
Abstract
Clustering populations of networks while recovering their latent hierarchical organization is a fundamental yet largely unexplored problem in network analysis. To formalize this, we introduce the Hierarchical Distance Matrix, a specific class of population-level distance matrices that encodes latent hierarchical organization through recursively nested distance separation, accommodating unbalanced tree depths. Building on this framework, we propose a fully data-driven top-down procedure: network hierarchical clustering based on two-sample testing (NHC-TST). The algorithm recursively splits networks via spectral clustering and uses a graph-based two-sample stopping rule. The procedure adaptively determines the branching structure without requiring prior knowledge of the number of clusters or tree depth. Theoretically, we establish exact recovery of the population-level hierarchical structure and statistical consistency in the empirical procedure. Simulation studies demonstrate highly accurate recovery of both cluster memberships and hierarchical relationships across a wide range of settings. Applied to a global migration dataset, NHC-TST uncovers interpretable multi-resolution temporal structures that are not revealed by conventional flat clustering approaches.