Hyperbolic Continuous Structural Entropy for Hierarchical Clustering

AI summary

Overview

Research area: Unsupervised machine learning, specifically graph-based hierarchical clustering, combined with hyperbolic representation learning, graph neural networks, and information theory (structural entropy). Technical level: Advanced — the paper relies on Riemannian geometry (Lorentz and Poincaré models), structural entropy (SE), and graph structure learning. Scope: This paper introduces HypCSE, a neural network that learns hierarchical clusterings (dendrograms) by minimizing a differentiable, continuous relaxation of structural entropy over hyperbolic embeddings of an adaptively learned graph.

What This Paper Is About

Most hierarchical clustering methods build dendrograms either procedurally, without optimizing a single global quality objective, or they optimize a global cost on a graph that is fixed in advance or fully connected, which limits how much they can use the actual data features. The paper's goal is to define a differentiable global objective — a continuous structural entropy (CSE) — and optimize it over hyperbolic embeddings of a graph whose structure is itself learned during training, so that the resulting binary partitioning tree is both globally well-scored and built on a structure that reflects the data.

Key Contributions

1. Continuous Structural Entropy (CSE): The authors reformulate discrete structural entropy as a function of the lowest common ancestor (LCA) of leaf pairs, then relax the non-differentiable indicator term into a softmax-based expression using the analogy between hyperbolic graph embeddings and binary partitioning trees.
2. The HypCSE model: A Hyperbolic CSE Neural Network that encodes graph vertices with hyperbolic graph neural networks, minimizes CSE via gradient descent, and decodes the resulting Poincaré embeddings into a binary partitioning tree using a Single Linkage-like procedure.
3. A graph structure learning (GSL) strategy: To avoid optimizing CSE on a predefined static graph, the model maintains an anchor graph and a learner graph, updates the anchor from the learner through bootstrapping with decay rate τ, and guides the learner with hyperbolic contrastive learning.
4. Empirical validation: Experiments on 7 standard UCI datasets against 6 discrete and 3 continuous hierarchical clustering baselines, plus ablation and parameter sensitivity studies, with code and datasets released at the linked repository.

Main Findings

• Best dendrogram purity across all datasets: HypCSE achieves the highest DP on all 7 datasets, with values of 97.9 (Zoo), 95.1 (Iris), 93.9 (Wine), 96.8 (Br. Cancer), 86.4 (OpticalDigits), 75.5 (Spambase), and 81.4 (PenDigits).
• Improvement over the discrete SE-based baseline: HypCSE outperforms HCSE on both metrics; for example, HCSE scores 71.1 DP on Wine versus 93.9 for HypCSE, and 55.2 versus 75.5 on Spambase.
• Structural entropy performance is split: HypCSE attains the best SE on 4 datasets and runner-up on 1, while DPClusterHSBM achieves the lowest SE on Spambase (5.194) and the second lowest on 4 datasets; the authors argue SE depends heavily on the quality of the constructed similarity graph.
• Metric disagreement on Br. Cancer: HypCSE reaches the highest DP (96.8) on Br. Cancer but a poor SE (4.342), which the authors attribute to the constructed graph failing to capture class-discriminative features — the motivation for the GSL module.
• Ablation shows both GSL components contribute: Adding graph learning alone gives only a minimal gain (e.g., Spambase 70.1 → 72.1), adding contrastive learning alone gives a larger gain (Spambase → 75.4), and combining both gives the best result (97.9, 95.1, 93.9, 96.8, 86.4, 75.5 across the six reported datasets).
• Contrastive learning supplies discriminative features: The authors state that the contrastive component improves overall performance by learning more discriminative features, and that GL without CL guidance has minimal effect on its own.
• Robustness to most hyperparameters: τ = 0.9999 yields the best performance on 5 datasets and is adopted as default; τ sensitivity is notably higher on Spambase, which the authors suggest has an ambiguous hierarchical structure. η₁ rarely affects performance except on Spambase, where larger values help; the number of retained edges k matters mainly for Iris and Spambase, where keeping more edges lowers performance (attributed to added noise).
• Consistency with Dasgupta's cost: The authors report Dasgupta's costs of trees from all methods in the appendix and state the method rankings are similar to those under SE, indicating consistency between the two metrics.
• Efficiency claim: With K-nearest neighbor graph construction and a minimum spanning tree trick, the tree decoding time complexity is reduced to O(n log n).

Methodology in Plain English

The pipeline has three moving parts.

First, the input data points are turned into a weighted undirected similarity graph: pairwise similarities are measured with a Gaussian kernel of width σ = 1, and the graph is sparsified by keeping the top k = 10 edges per vertex.

Second, the graph is encoded into hyperbolic space. The encoder f(·) stacks 3 layers of Lorentz Convolution (LConv), which combines a Lorentz linear layer and a Lorentz attention-based aggregation layer, to produce embeddings in the Lorentz model before converting them to the Poincaré model. Hyperbolic space is chosen because it naturally accommodates tree-like, hierarchical structure: the deeper a node sits in a hierarchy, the closer it lies to the boundary of the disk.

Third, the model minimizes CSE. Structural entropy measures how much uncertainty a partitioning tree removes from a graph. The authors rewrite SE as a sum over edges involving the volume of the LCA of each pair of leaves. The indicator "is node k a descendant of the LCA of i and j" depends on comparing distances, which is not differentiable — so the authors replace it with a scaled softmax over distances of the geodesic to the origin, producing a differentiable objective. Minimizing this pushes embeddings so that the geometry of the hyperbolic space mimics a good binary tree.

After optimization, the Poincaré embeddings are decoded into a discrete binary partitioning tree: each point starts as its own cluster, and the two closest clusters are repeatedly merged, where closeness is the minimum geodesic-to-origin distance of an LCA pair.

Fourth, because optimizing on a fixed heuristic graph is a weakness, a GSL module learns a better graph. The constructed graph acts as an anchor graph; a graph learner produces a learner graph from features; the anchor's edges are refreshed by sampling from the learner and the anchor with decay rate τ = 0.9999 after each epoch; and hyperbolic contrastive learning aligns the two views of the same vertex while separating different vertices, using distance-based losses in the Lorentz model. A centroid loss pulls the mean leaf embedding toward the origin to encourage more balanced trees.

The total objective combines the CSE term with the contrastive loss and the centroid loss, weighted by η₁ and η₂, both set to 1. The hyperbolic encoder and projector use curvature κ = −1 and are optimized with Riemannian Adam in Geoopt, while the GSL encoder lives in Euclidean space and uses Adam. Hyperparameters t₁ = 1000, r₁ = 2, t₂ = 1, r₂ = 0 are used across all datasets except PenDigits (t₁ = 1, t₂ = 1000). All experiments are run 5 times and mean values reported.

Why This Matters

The paper connects two lines of work that are usually separate: information-theoretic global objectives for hierarchical clustering (structural entropy) and continuous, differentiable representation learning in hyperbolic space. It shows that a discrete, combinatorial objective can be relaxed smoothly enough to be optimized end-to-end alongside a graph learner, which matters for research on objective-driven clustering and for hyperbolic neural network design.

Real-world applications of hierarchical clustering cited by the paper include:

• Image analysis — organizing image collections or visual features into nested groups.
• Bioinformatics — structuring biological data such as gene or sequence relationships into hierarchies.
• Medicine — grouping patient or clinical data into nested clusters for analysis.
• General exploratory data analysis — producing dendrograms without pre-specifying the number of clusters.

Industry relevance comes from the fact that continuous methods integrate into end-to-end gradient-based pipelines, and from the model's claimed O(n log n) decoding complexity, which suits settings where clustering must scale to many items. The graph structure learning component also matters where a similarity graph must be inferred from raw features rather than supplied by a domain expert.

Future Directions

• Reliability of the structural entropy metric: Because SE depends on the quality of the constructed similarity graph and diverged from DP on Br. Cancer, a natural next step is a graph construction or metric that stays meaningful when pairwise similarities are noisy.
• Scaling beyond the tested range: The paper's datasets span 101 to 10,992 points, so the O(n log n) claim invites validation on much larger graphs and on data where the hierarchy is not clean.
• Ambiguous hierarchies: Spambase was the outlier in both the τ and η₁ sensitivity analyses, which raises the question of how the model should behave when the underlying data have no clear hierarchy.
• Flexibility beyond clustering: The paper begins a flexibility analysis applying HypCSE with a classification loss on 4 UCI datasets using 30/60/10% train/test/validation splits, but the provided content is truncated before the results — extending the method to downstream supervised and similarity-based tasks remains to be evaluated.

Target Audience

Researchers and graduate students working on hierarchical clustering, graph representation learning, or hyperbolic neural networks, particularly those interested in objective-driven clustering rather than procedural algorithms. It is also relevant to practitioners who need differentiable clustering modules inside end-to-end pipelines and who are comfortable with the mathematical prerequisites of Riemannian geometry and information theory. Readers looking for a beginner-level introduction to clustering will find the method sections demanding.

Authors’ abstract

Hierarchical clustering is a fundamental machine-learning technique for grouping data points into dendrograms. However, existing hierarchical clustering methods encounter two primary challenges: 1) Most methods specify dendrograms without a global objective. 2) Graph-based methods often neglect the significance of graph structure, optimizing objectives on complete or static predefined graphs. In this work, we propose Hyperbolic Continuous Structural Entropy neural networks, namely HypCSE, for structure-enhanced continuous hierarchical clustering. Our key idea is to map data points in the hyperbolic space and minimize the relaxed continuous structural entropy (SE) on structure-enhanced graphs. Specifically, we encode graph vertices in hyperbolic space using hyperbolic graph neural networks and minimize approximate SE defined on graph embeddings. To make the SE objective differentiable for optimization, we reformulate it into a function using the lowest common ancestor (LCA) on trees and then relax it into continuous SE (CSE) by the analogy of hyperbolic graph embeddings and partitioning trees. To ensure a graph structure that effectively captures the hierarchy of data points for CSE calculation, we employ a graph structure learning (GSL) strategy that updates the graph structure during training. Extensive experiments on seven datasets demonstrate the superior performance of HypCSE.