Research map / Probabilistic and scientific modeling / Variational and generative sampling
Expected Probabilistic Hierarchies
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 Expected Probabilistic Hierarchies (EPH), which optimizes expected Dasgupta cost and Tree-Sampling Divergence over probabilistic hierarchies via differentiable (Gumbel-Softmax) hierarchy sampling and unbiased subgraph sampling for hierarchical clustering.
Problem
Hierarchical clustering is usually solved by discrete heuristics or by continuous relaxations of Dasgupta/TSD scores whose optima need not match the discrete optima.
Approach
Move the expectation outside the score: optimize expected Dasgupta (Exp-Das) and expected TSD (Exp-TSD) under a tree-sampling probabilistic hierarchy, approximated with straight-through Gumbel-Softmax hierarchy samples and unbiased edge subgraph sampling. Proves global optima of expected scores equal discrete optima, unlike Soft-Das.
Key results
- EPH achieves best Dasgupta cost or TSD on 13/16 graph settings and best Dasgupta cost on 7/8 vector datasets.
- On graph datasets EPH (Exp-Das) consistently beats FPH (Soft-Das) in Dasgupta cost, e.g., PolBlogs 235.50 vs 238.65 and Brain 400.20 vs 425.70.
- On HSBMs EPH recovers the first three ground-truth levels with NMI 1.0 at levels 1-2 and inferred Dasgupta cost (121.08) better than ground truth (130.16) on the large HSBM.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Optimize expected scores instead of soft scores | EPH vs FPH · Graph datasets | Dasgupta cost | Helped |
| Optimize expected scores instead of soft scores | EPH vs FPH · Vector datasets | Dasgupta cost | Helped |
| Use constrained projection optimization instead of unconstrained optimization (ablation) | EPH · Graph datasets | Dasgupta cost | Helped |
| Initialize with average linkage instead of random initialization (ablation) | EPH · Graph datasets | Dasgupta cost | Helped |
| Initialize with FPH instead of average linkage (ablation) | EPH · Graph datasets | Dasgupta cost | Mixed |
| Use embedding parametrization with fixed temperature ti = 1 instead of direct parametrization (ablation) | EPH · Graph datasets | Dasgupta cost | Hurt |
| Use embedding parametrization with learnable temperature instead of direct parametrization (ablation) | EPH · Graph datasets | Dasgupta cost | Mixed |
| Increase the number of internal nodes (ablation) | EPH · Graph datasets | Dasgupta cost | Helped |
| Increase sampled hierarchies from N ≤ 10 to N ≥ 20 (ablation) | EPH · Graph datasets | Dasgupta cost | Mixed |
| Increase the number of sampled edges (ablation) | EPH · Vector datasets | Dasgupta cost | Helped |
| Use n√n sampled edges instead of n sampled edges (ablation) | EPH · Vector datasets | Dasgupta cost | Helped |
| Use n² sampled edges instead of n√n sampled edges (ablation) | EPH · Vector datasets | Dasgupta cost | Helped |
Surprising findings
- EPH inferred hierarchies achieve lower Dasgupta cost than the ground-truth hierarchies on the HSBM graphs.
- Linkage algorithms dominate continuous methods on external label-accuracy evaluation for vector datasets despite worse Dasgupta cost.
Limitations
- Gumbel-Softmax gradient estimates are biased even though forward expectations are unbiased, affecting optimization.
- Gradient descent does not guarantee convergence to a global optimum despite matching global optima of expected and discrete scores.
- Exp-Das is neither convex nor concave in the hierarchy parameters.
Experimental setup
Datasets: PolBlogs Brain Citeseer Genes Cora-ML OpenFlight WikiPhysics DBLP Zoo Iris Glass Digits
Benchmarks: PolBlogs Brain Citeseer Genes Cora-ML OpenFlight WikiPhysics DBLP Zoo Iris Glass Digits
Metrics: Dasgupta cost Tree-sampling divergence normalized mutual information cophenetic correlation accuracy (Hungarian-aligned)
Baselines: Average linkage Ward linkage Single linkage Complete linkage Louvain RSC Ultrametric Fitting (UF) HypHC gHHC FPH
Builds on: Flexible Probabilistic Hierarchy (FPH) Gumbel-Softmax Dasgupta cost Tree-Sampling Divergence
Closest papers by meaning
- End-to-End Learning of Probabilistic Hierarchies on Graphs (ICLR 2022 · similarity 0.91)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.88)
- Learning-Augmented Hierarchical Clustering (ICML 2025 · similarity 0.88)
- From Logits to Hierarchies: Hierarchical Clustering made Simple (ICML 2025 · similarity 0.88)
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.87)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.86)
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.