Neural model learns custom rules for efficient clustering trees
Algorithmically Aligned Neural Agglomerative Tree Construction
Machine Learning
Summary
Hierarchical clustering builds trees by grouping items based on how similar they are, but it’s hard to pick the best way to do these groupings. The authors present NN-linkage, a kind of artificial intelligence that learns the best steps to combine groups for specific tasks while keeping clustering fast and scalable. Their method can mimic traditional clustering rules and also learn new ones tailored to different problems. They tested NN-linkage on tasks like organizing clock components and studying evolutionary trees, finding it outperformed classic methods and other neural approaches.
What this means in practice
- •For electronic design teams: Improve clock-tree routing in chip design by learning optimal group merges for timing constraints using NN-linkage.
- •For bioinformatics engineers: Enhance phylogenetic tree reconstruction from genetic data by applying learned merge rules that adapt to specific evolutionary patterns.
Authors
Robert R Nerem, Pranav Singh, Cheyenne Ward, Yusu Wang
Abstract
Linkage algorithms for hierarchical clustering (HC) are a powerful and efficient framework for constructing clustering trees, yet it is often unclear which merge rule best suits a given dataset or task. In contrast, neural approaches can learn from data, but often fail to retain the efficiency and size generalization of classical algorithms. We introduce NN-linkage, a neural network (NN) model that can learn task-specific and locally dependent merge rules while retaining the recursive structure and efficient inference of classical linkage algorithms. In particular, our model is algorithmically aligned with the Lance-Williams (LW) recurrence, a parameterized framework for defining a broad, continuous family of linkage rules for agglomerative HC. Classical methods such as single linkage (SL), complete linkage (CL), and average linkage arise as discrete choices within this broader family. We show that NN-linkage is a universal approximator for continuous linkage functions, including LW recurrences, and, when paired with a transformer encoding, can also approximate globally dependent rules such as robust single-linkage. We further show that NN-linkage can exactly implement any symmetric constant-coefficient LW recurrence across all input sizes. On the empirical front, we evaluate NN-linkage in real-world applications, clock-tree routing and phylogenetic reconstruction, using both synthetic and real datasets, demonstrating its effectiveness over both classical algorithms and other neural approaches. By learning merge rules directly from target trees, NN-linkage extends efficient HC to scientific and engineering objectives not adequately captured by existing hand-designed linkage rules.