Research map / Label-efficient and robust learning / Recognition and long-tail
Hierarchical Correlation Clustering and Tree Preserving Embedding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Hierarchical Correlation Clustering (HCC), an agglomerative clustering that handles positive and negative pairwise similarities, and extends it with ultrametric-based tree-preserving embedding and minimax dissimilarities for correlation clustering.
Problem
Hierarchical clustering and representation learning typically assume non-negative pairwise (dis)similarities, while correlation clustering only produces flat clusters; no hierarchical method handles signed pairwise similarities.
Approach
Defines an inter-cluster dissimilarity inspired by the flat correlation clustering cost (sum of pairwise dissimilarities between clusters) for agglomerative merging, embeds the resulting dendrogram via level-based ultrametric and classical MDS to get features, and shows minimax dissimilarities on signed graphs reduce correlation clustering to connected components of positive-edge graph.
Key results
- On UCI Breast Tissue with noise-free-to-noisy oracle setup, HCC+GMM reaches MI 0.914 vs AL+GMM 0.550 and SL+GMM 0.093.
- On Fashion-MNIST subset 1, HCC+GMM achieves MI 0.581 and Rand 0.586 vs AL+GMM 0.608/0.551 (mixed results).
- Minimax + correlation clustering achieves perfect clustering (MI = Rand = 1) on all four arbitrarily shaped datasets and the vehicle trajectory data, where plain correlation clustering scores are very low.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use HCC instead of the strongest non-HCC method | Hierarchical clustering · Breast Tissue | MI: 0.542 -> 0.903 | Helped |
| Use HCC instead of the strongest non-HCC method | Hierarchical clustering · Cardiotocography | MI: 0.391 -> 0.987 | Helped |
| Use HCC instead of the strongest non-HCC method | Hierarchical clustering · Image Segmentation | MI: 0.518 -> 0.945 | Helped |
| Use HCC instead of the strongest non-HCC method | Hierarchical clustering · ISOLET | MI: 0.257 -> 0.938 | Helped |
| Use HCC instead of the strongest non-HCC method | Hierarchical clustering · Leaf | MI: 0.181 -> 0.429 | Helped |
| Use HCC instead of the strongest non-HCC method | Hierarchical clustering · One-Hundred Plant | MI: 0.066 -> 0.159 | Helped |
| Use HCC instead of the strongest non-HCC method | Hierarchical clustering · Fashion MNIST 1 | MI: 0.464 -> 0.499 | Helped |
| Use HCC instead of the strongest non-HCC method | Hierarchical clustering · Fashion MNIST 2 | MI: 0.602 -> 0.666 | Helped |
| Apply GMM to the HCC tree-preserving embedding instead of using HCC alone | HCC · Breast Tissue | MI: 0.903 -> 0.914 | Helped |
| Apply GMM to the HCC tree-preserving embedding instead of using HCC alone | HCC · Cardiotocography | MI: 0.987 -> 0.979 | Hurt |
| Apply GMM to the HCC tree-preserving embedding instead of using HCC alone | HCC · Image Segmentation | MI: 0.945 -> 0.960 | Helped |
| Apply GMM to the HCC tree-preserving embedding instead of using HCC alone | HCC · ISOLET | MI: 0.938 -> 0.941 | Helped |
Surprising findings
- HCC+GMM embeddings often outperform HCC alone on clustering quality.
- Plain average linkage or single linkage can be applied to signed dissimilarities via shift invariance, yet HCC is still reported to outperform them on signed data.
Limitations
- Experiments use simulated noisy oracle signed similarities on UCI data rather than real signed-similarity applications.
- HCC linkage is not shift-invariant, so the shift trick cannot be used; level-based embedding is used instead.
- Mixed results on Fashion-MNIST where AL+GMM beats HCC+GMM on one subset.
Experimental setup
Datasets: Breast Tissue Cardiotocography Image Segmentation ISOLET Leaf One-Hundred Plant Fashion-MNIST vehicle motion trajectories
Benchmarks: UCI datasets (Breast Tissue, Cardiotocography, Image Segmentation, ISOLET, Leaf, One-Hundred Plant) Fashion-MNIST subsets arbitrarily shaped synthetic clustering datasets DS1-DS4 vehicle motion trajectories
Metrics: normalized mutual information normalized Rand score
Baselines: single linkage complete linkage average linkage SL+GMM CL+GMM AL+GMM correlation clustering
Builds on: correlation clustering tree preserving embedding agglomerative hierarchical clustering minimax dissimilarity
Closest papers by meaning
- Joint Hierarchical Representation Learning of Samples and Features via Informed Tree-Wasserstein Distance (NeurIPS 2025 · similarity 0.86)
- Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering (NeurIPS 2025 · similarity 0.86)
- Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy (ICLR 2025 · similarity 0.84)
- Clustering Properties of Self-Supervised Learning (ICML 2025 · similarity 0.84)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.84)
- From Logits to Hierarchies: Hierarchical Clustering made Simple (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.