Source-linked AI summary
Hierarchical information clustering by means of topologically embedded graphs
Won-Min Song, T. Di Matteo, Tomaso Aste
TL;DR
The paper tackles the challenge of extracting meaningful clusters and hierarchies from complex datasets without prior information or supervision. It introduces DBHT, which analyzes topologically embedded graphs containing significant links. DBHT retrieves clustering and hierarchical structure in artificial and real datasets, including biologically meaningful organization in lymphoma gene-expression data.
Problem
Complex datasets contain redundant information, while established clustering methods may require prior cluster counts, thresholds, or expert supervision.
Method
DBHT deterministically builds topologically embedded graphs from similarity measures and analyzes their structure to extract clusters and hierarchies.
Results
DBHT successfully retrieved clustering and hierarchical structure across artificial and real datasets, outperforming established methods in several cases and differentiating lymphoma sample groups with distinct survival rates.
Takeaways & Limitations
The method can identify meaningful sample and gene groups relevant to diagnosis, prognosis, and treatment of lymphoid malignancies.
Abstract
from arXiv · showhide
We introduce a graph-theoretic approach to extract clusters and hierarchies in complex data-sets in an unsupervised and deterministic manner, without the use of any prior information. This is achieved by building topologically embedded networks containing the subset of most significant links and analyzing the network structure. For a planar embedding, this method provides both the intra-cluster hierarchy, which describes the way clusters are composed, and the inter-cluster hierarchy which describes how clusters gather together. We discuss performance, robustness and reliability of this method by first investigating several artificial data-sets, finding that it can outperform significantly other established approaches. Then we show that our method can successfully differentiate meaningful clusters and hierarchies in a variety of real data-sets. In particular, we find that the application to gene expression patterns of lymphoma samples uncovers biologically significant groups of genes which play key-roles in diagnosis, prognosis and treatment of some of the most relevant human lymphoid malignancies.
Introduction
The paper addresses the bottleneck of filtering meaningful structure from complex, redundant datasets without relying on unavailable prior information. It proposes DBHT, a deterministic method using topologically embedded graphs to extract clusters and their hierarchical organization.
- Complex datasets require automated clustering to reduce redundancy and dimensionality, but many methods depend on expert supervision and prior information.Filtering often occurs early, when little system information is available.
- Existing approaches may require the number of clusters or a threshold, which is difficult for multi-scaling phenomena.The paper identifies these requirements as limitations of established clustering methods.
- DBHT extracts clustering subdivisions and hierarchical organization without prior information, supervision, or thresholding.The method is presented as an alternative to parameter-dependent clustering procedures.
- The approach builds sparse graphs by recursively inserting significant links while constraining complexity through topological embedding on a surface.The embedding framework uses graph genus, defined as the number of handles of the surface.
- DBHT analyzes the topological structure of PMFG graphs as the basis for its clustering and linkage procedure.The paper uses DBHT as the name for this clustering and linkage method.
Results
DBHT was evaluated on synthetic, hierarchical, Iris, and lymphoma gene-expression datasets, where it recovered clusters and hierarchies competitively while requiring no prior cluster number or thresholding. In lymphoma data, it identified clinically and biologically meaningful sample and gene clusters.
- Synthetic and benchmark evaluations: DBHT is deterministic and requires no a priori information, unlike the compared clustering methods, which are non-deterministic and require prior information.The comparison included k-means++, kNN-Spectral, SOM, and Q-cut.
- Synthetic and benchmark evaluations: DBHT strongly outperformed competing methods on synthetic datasets with one 64-element cluster and eight 5-element clusters across varied noise settings.The authors report consistent superiority or equivalence across a broad parameter range.
- Synthetic and benchmark evaluations: DBHT recovered the four main clusters in nested synthetic hierarchies, whose partition coincided exactly with the true partition.The simulated hierarchy contained large, medium, and small nested clusters and included power-law noise with α = 1.5 and c = 0.1.
- Synthetic and benchmark evaluations: On Iris data, DBHT separated Iris Setosa and better divided Versicolour from Virginica, achieving an adjusted Rand index of 0.89 versus 0.85 for Qcut and kNN-Spectral.The competing results were the best partitions retained across the tested kNN settings.
- Lymphoma gene-expression analysis: Applied to 96 lymphocyte samples, DBHT yielded 11 sample-clusters and grouped all follicular lymphoma samples together, while DLBCL clusters occupied a common graph branch.The DLBCL-containing clusters had survival rates of 100%, 56%, 15%, and 29%.
- Lymphoma gene-expression analysis: Gene-expression analyses linked significant clusters to lymphoma biology, including CDK1, SYK, TGF-B1, tumor-suppressor genes, and IL-6-related signaling.These associations were discussed in relation to proliferation, prognosis, and potential therapeutic targets.
Discussion
DBHT is a deterministic, parameter-free approach for extracting clusters and hierarchical organization from complex datasets. It retrieves clustering and hierarchy across artificial and real datasets, including meaningful cancer-subtype differentiation in gene-expression data.
- DBHT extracts cluster structure and hierarchical organization from complex datasets using topologically embedded graphs built from similarity measures.
- The technique is deterministic, requires no a-priori parameters, and does not need expert supervision.
- DBHT successfully retrieves clustering and hierarchical structure across artificial and real datasets, outperforming established methods in several cases.
- Applied to gene-expression data, DBHT differentiates cancer subtypes and identifies a meaningful hierarchy, including four distinct DLBCL clusters associated with different survival outcomes.
Methods
The method uses the topology of planar maximally filtered graphs to derive clusters and their hierarchies. It partitions vertices through directed bubbles, then links elements, bubbles, and clusters across three levels.
- A PMFG is a weighted graph whose edges encode similarity weights and associated non-negative dissimilarities; separating 3-cliques divide it into disconnected interior and exterior parts.
- Nested separating 3-cliques generate planar subgraphs called bubbles, which connect through separating 3-cliques to form a bubble tree.
- Directed bubble-tree edges point toward the side with the largest connecting weight, identifying converging, diverging, and passage bubbles.
- Converging bubbles define cluster centers, and bubbles connected to them by directed paths form cluster subtrees.
- Vertices shared by converging bubbles are assigned to the bubble with greatest attachment strength, while remaining vertices are assigned using average shortest-path length.
- Complete-linkage procedures build intra-bubble, intra-cluster, and inter-cluster hierarchies, joining clusters upward and splitting bubbles and elements downward.
A.1 Preparation
The synthetic-data preparation varies cluster structure, multivariate distributions, perturbation types, noise amplitude, and random background elements. These manipulations progressively blur the correlation structure until intra- and inter-cluster correlations become indistinguishable.
- Synthetic time series were generated with multivariate Gaussian and log-normal generators to approximate prescribed Pearson correlation structures.
- For Gaussian and log-normal noise, c varied from 0 to 7; for power-law noise, c varied from 0 to 0.8 with exponent α = 1.5, while α was also varied from 1 to 3 at c = 0.1.
- Increasing noise, decreasing the power-law exponent, or reducing intra-cluster correlation blurs the Pearson correlation matrix until average intra- and inter-cluster correlations become equal.
- The simulations combined regular or irregular partitions with multivariate Gaussian or log-normal variables.
- Perturbations included univariate Gaussian, log-normal, and power-law noise, with relative amplitude c and random background count Nran varied.
A.2 Comparison with different clustering methods
Across broad synthetic conditions, DBHT clustering generally outperformed the compared techniques and remained consistent under severe cluster-size imbalance and background noise.
- Adjusted Rand index results across broad dR > 0.1 combinations show DBHT outperforming the other clustering techniques, with Qcut performing similarly.
- Under extreme cluster-size differentiation, DBHT also outperformed Qcut and was the only technique delivering consistent, quality clustering outcomes.The tested structure contained eight clusters of 5 elements, one cluster of 64 elements, and Nran = 25 random background elements.
B Artificial data with a hierarchical Structure
Hierarchical synthetic data were constructed with nested clusters at multiple scales and distinct within-cluster correlations. The design included both regular and irregular cluster-size partitions.
- The regular hierarchy contained 16 small clusters of 16 elements nested inside medium and larger blocks.
- Small clusters were merged into medium clusters with ρin*₂ = 0.7, then into one cluster with ρout* = 0.15.
B.2 Comparison with different linkage methods
The evaluation compares DBHT with linkage methods across synthetic hierarchical and distributional settings, while also examining biologically meaningful sample classifications. DBHT consistently outperforms linkage methods in the reported hierarchical comparison.
- Synthetic comparisons: Thirty Gaussian datasets were generated for each C value to stabilize average distance and adjusted Rand statistics.The simulations used ρin∗ = 0.9, ρou∗ = 0, and Nran = 5.
- Synthetic comparisons: The synthetic evaluations include Gaussian, log-normal, and mixed-distribution datasets, including highly unequal cluster sizes.One mixed case contains eight clusters of five elements and one cluster of 64 elements.
- Lymphoma classification: ABC-like DLBCL samples dominate the top of the PMFG, whereas GCB-like samples are concentrated toward its center and mainly occupy sample-clusters 1, 5, and 7.ABC-like samples mainly occupy sample-clusters 7 and 9.
C.2 Analysis of significant gene-clusters for sample-clusters
The analysis identifies gene-clusters associated with DBHT-derived sample-clusters by combining differential-expression and enrichment analyses. Statistical significance is assessed by varying differential-expression cut-offs and testing gene-cluster enrichment.
- Gene-cluster identification: The study searches for significant gene-clusters that distinguish each sample-cluster identified by DBHT.The analysis focuses on gene-clusters associated with the sample-clusters found by DBHT clustering.
- Comparison framework: Figure 14 compares adjusted Rand indexes between the synthetic partition and partitions obtained by cutting DBHT, average-linkage, and complete-linkage dendrograms.The comparisons separately assess four large clusters and eight medium clusters.
- Gene-cluster identification: For each sample-cluster, differentially expressed gene-profiles are identified at selected p-value cut-offs before testing enrichment of each gene-cluster.The most significant gene-cluster is identified by varying the cut-off p-values.
C.3 Gene Ontology analysis on significant gene-clusters
Gene Ontology analysis evaluates biological processes associated with significant gene-clusters linked to lymphoma sample-clusters. Most significant processes are reported after multiple-testing correction, while enrichment can identify biologically relevant clusters without significant GO terms.
- GO analysis: GO analysis was performed on lymphoma-associated gene-clusters using a p-value significance level of 0.05 and Bonferroni correction.The analysis used the BiNGO plug-in for Cytoscape.
- CLL-associated cluster: Gene-cluster 102 had no significant GO biological processes but remained enriched at approximately p ≈ 10^-6 for CLL sample-cluster 11.The cluster includes biologically significant CLL-associated genes such as IRF1.
- GO analysis: The analysis reports over-represented GO terms for significant gene-clusters associated with DLBCL, FL, and CLL sample-clusters.The relevant sample-clusters are 1, 5, 7, 9, 4, and 11.