Hierarchical information clustering by means of topologically embedded graphs

Won-Min Song, Tiziana di Matteo, Tomaso AstearXiv 2011 · arXiv

Abstract

Clustering is a fundamental task in data analysis, yet traditional methods often struggle with the "parameter problem"—requiring prior knowledge of cluster numbers—and the "scale problem"—failing to capture hierarchical relationships. This paper presents the Directed Bubble Hierarchical Tree (DBHT), a deterministic, parameter-free approach that leverages the intrinsic topology of data. By embedding correlation matrices into Planar Maximally Filtered Graphs (PMFG), DBHT identifies multi-scale structures and information flow. The method outperforms state-of-the-art algorithms on synthetic benchmarks and demonstrates significant clinical utility by identifying lymphoma subtypes with distinct survival profiles.

Introduction: The Bottlenecks of Clustering

Modern data science relies heavily on clustering to organize complex information. However, two major limitations persist:

  1. The Parameter Problem: Algorithms like k-means require users to specify the number of clusters ($k$) or distance thresholds beforehand. In exploratory research, these values are rarely known.
  2. The Scale Problem: Real-world systems are inherently hierarchical. Information exists at both local and global scales. Most methods force a single level of granularity, often obscuring the global organization that dictates system behavior.

The DBHT technique addresses these issues by providing a "hands-off" approach that filters noise while simultaneously capturing both "the forest and the trees."

The DBHT Methodology

The core of the DBHT approach involves a two-step process rooted in graph theory and topology.

1. Graph Embedding via PMFG

The algorithm first represents the dataset as a Planar Maximally Filtered Graph (PMFG). It processes a correlation matrix, retaining only the most significant links such that the graph can be embedded on a sphere without edge crossings (genus $g=0$). This topological constraint acts as a powerful filter, preserving essential relationships while maintaining sparsity.

2. The Bubble Tree and Information Flow

In a PMFG, the fundamental units are 3-cliques (triangles), which form "bubbles." By analyzing the strength of connections between these bubbles, the authors construct a Directed Bubble Tree.

Hierarchical organization captured by DBHT, showing the correlation matrix (a) and resulting dendrograms (b-d) representing different levels of granularity.
  • Converging Bubbles: These act as cluster centers where information flow meets.
  • Diverging/Passage Bubbles: These serve as connectors or peripheral elements.
  • Hierarchy Generation: The tree structure naturally yields both intra-cluster (internal organization) and inter-cluster (relationships between groups) hierarchies.

Crucially, this process is deterministic and unsupervised, requiring no random initialization or parameter tuning.

Performance Benchmarks

The authors evaluated DBHT against several state-of-the-art methods, including k-means++, Spectral clustering, Self-Organizing Maps (SOM), and Q-cut, using both synthetic and real-world datasets.

Synthetic Data and Noise Robustness

On synthetic datasets featuring multivariate Gaussian and Log-Normal distributions with varying noise levels, DBHT consistently achieved higher Adjusted Rand Index (ARI) scores. Its topological approach makes it particularly robust against "fat-tailed" noise that often degrades the performance of stochastic algorithms.

Comparison of Adjusted Rand Index (ARI) for DBHT and other clustering methods across synthetic datasets with varying noise levels.

Classic Benchmarks

In the classic Fisher’s Iris dataset, DBHT misplaced only 6 elements (ARI 0.89), outperforming Q-cut and kNN-Spectral, which both misplaced 8 elements (ARI 0.85).

Clinical Application: Lymphoma Subtyping

The true power of DBHT was demonstrated on a referential lymphoma gene expression dataset. While standard clinical classifications at the time identified two main types of Diffuse Large B-Cell Lymphoma (DLBCL), DBHT uncovered four distinct groups. These groups were found to have drastically different survival rates: 100%, 56%, 15%, and 29%. This finer-grained classification provides a significantly clearer picture for prognosis and potential therapeutic targeting.

Conclusion and Future Directions

DBHT introduces planarity not just as a visualization tool, but as a mathematical filter for information. By prioritizing local connections within a global skeleton, it uncovers structures that other methods miss.

Future work may involve extending the method to higher-genus surfaces to capture overlapping information structures or utilizing topologically embedded directed graphs to model asymmetric relationships like causality. While computationally intensive for massive datasets, DBHT offers a robust, parameter-free alternative for high-stakes exploratory data analysis.

Summary updated

BibTeX
@misc{song2011hierarchical,
  author = {Won-Min Song and Tiziana di Matteo and Tomaso Aste},
  title = {{Hierarchical information clustering by means of topologically embedded graphs}},
  year = {2011},
  eprint = {1110.4477},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1110.4477},
}
Figure