Theory and applications of non-hierarchical multiscale clustering: from graph diffusion to higher-order topological autocorrelation
Author(s)
Schindler, Juni
Type
Thesis
Abstract
In many real-world applications, datasets possess an intrinsic multiscale structure, whereby meaningful descriptions exist at different levels of coarseness. In such cases, natural descriptions go beyond a single clustering and instead require multiscale clusterings: a multi-resolution sequence of potentially non-hierarchical partitions parametrised by a scale parameter. This thesis addresses three interrelated questions: 1) how to compute non‑hierarchical multiscale clusterings efficiently; 2) how to select scales that reveal robust partitions of the data; and 3) how to analyse and compare multiscale clusterings. The two main mathematical paradigms of this thesis are graph diffusion to extract multiscale sequences of partitions from data and persistent homology to reconcile the overall structure of such descriptions.
The contributions are as follows: the PyGenStability software for efficient diffusion-based Markov Stability analysis for non-hierarchical multiscale clustering and an unsupervised scale‑selection algorithm that detects robust partitions through information-based measures; an application of this framework to human mobility data collected during the first UK COVID‑19 lockdown, revealing intrinsic mobility scales and quantifying lockdown‑induced shocks; the introduction of the Multiscale Clustering Filtration (MCF), a filtration of abstract simplicial complexes that encodes cluster intersection patterns in multiscale clusterings and whose persistent homology measures hierarchy and higher-order cluster inconsistencies; an extension to the Multiscale Clustering Bifiltration (MCbiF), a 2‑parameter filtration that measures the topological autocorrelation of multiscale clusterings, and whose multiparameter persistent homology yields topological feature maps with state-of-the-art performance in downstream regression and classification tasks; and finally, Local Graph‑based Dictionary Expansion (LGDE), a method that leverages graph diffusion on word similarity graphs to discover overlapping semantic communities and enrich keyword dictionaries for information‑retrieval tasks.
These contributions form a comprehensive computational and mathematical framework for non‑hierarchical multiscale clustering, with demonstrated impact in network science, machine learning, computational linguistics, and computational social science.
The contributions are as follows: the PyGenStability software for efficient diffusion-based Markov Stability analysis for non-hierarchical multiscale clustering and an unsupervised scale‑selection algorithm that detects robust partitions through information-based measures; an application of this framework to human mobility data collected during the first UK COVID‑19 lockdown, revealing intrinsic mobility scales and quantifying lockdown‑induced shocks; the introduction of the Multiscale Clustering Filtration (MCF), a filtration of abstract simplicial complexes that encodes cluster intersection patterns in multiscale clusterings and whose persistent homology measures hierarchy and higher-order cluster inconsistencies; an extension to the Multiscale Clustering Bifiltration (MCbiF), a 2‑parameter filtration that measures the topological autocorrelation of multiscale clusterings, and whose multiparameter persistent homology yields topological feature maps with state-of-the-art performance in downstream regression and classification tasks; and finally, Local Graph‑based Dictionary Expansion (LGDE), a method that leverages graph diffusion on word similarity graphs to discover overlapping semantic communities and enrich keyword dictionaries for information‑retrieval tasks.
These contributions form a comprehensive computational and mathematical framework for non‑hierarchical multiscale clustering, with demonstrated impact in network science, machine learning, computational linguistics, and computational social science.
Version
Open Access
Date Issued
2025-10-31
Date Awarded
2026-06-01
Copyright Statement
Attribution-Non Commercial-No Derivatives 4.0 International Licence (CC BY-NC-ND)
Advisor
Barahona, Mauricio
Sponsor
Engineering and Physical Sciences Research Council
Publisher Department
Department of Mathematics
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)