Reproduce “Hierarchical Linkage Clustering Beyond Binary Trees and Ultrametrics” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Maximilien Dreveton, Matthias Grossglauser, Daichi Kuroda, Patrick Thiran
Researchers at EPFL developed a framework defining "valid clusters" and the "finest valid hierarchy" based purely on data similarity, enabling the discovery of non-binary structures and the detection of absent hierarchies. Their "trimmed linkage" algorithm, when combined with single, complete, or average linkage methods, is proven to consistently recover this finest valid hierarchy, addressing the long-standing issue of linkage function sensitivity.
Key insights
- Any two valid clusters are necessarily laminar (disjoint or nested), which is a fundamental property for forming a consistent hierarchical tree.
- Necessary and sufficient conditions (Monotonicity across merges and Dominance preservation) were derived for linkage functions to guarantee that the trimmed linkage algorithm recovers the exact finest valid hierarchy (T*).
- The framework generalizes the classical relationship between ultrametric dissimilarity functions and dendrograms, extending the concept of a consistent hierarchy to arbitrary similarity functions.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.