Algorithmically Aligned Neural Agglomerative Tree Construction

Robert R Nerem; Pranav Singh; Cheyenne Ward; Yusu Wang

cs.LGOct 5, 2026

Algorithmically Aligned Neural Agglomerative Tree Construction

Authors: Robert R Nerem, Pranav Singh, Cheyenne Ward, Yusu Wang

Organizations: University of California San Diego · University of Washington

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.

Figures & tables

Panel of Figure 1 — Figure 1: NN-linkage initializes merge embeddings from encoded points and recursively updates them from stored embeddings. A shared linear scorer orders candidate merges in a priority queue.

Figure 2: A single Rings-and-disks test instance. Colors indicate ground-truth clusters; crosses mark misclassified points.

Panel of Figure 3 — Figure 3: Clock-tree results. Mean percentage change in the sum-of-diameters objective relative to raw CL; negative values indicate improvement. (a) Means over 50 held-out point sets per size, with error bars showing one standard error. (b) Mean objective change and runtime over 20 VLSI instances; point labels indicate the refinement parameter $k$ .

Figure 4: Synthetic data comparison. Mean normalized RF distance and runtime over 1,152 instances, equally weighting the nine size–length settings. Dashed lines join nondominated points. Lower RF and runtime are better.

Figure 5: Real phylogenetic data comparison. Mean normalized RF distance and runtime on all 26,136 instances successfully processed by both models. Overall pools individual instances, rather than equally weighting datasets. Lower RF and runtime are better.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Method	$\alpha_{A}$	$\alpha_{B}$	$\beta$	$\gamma$
SL	$\tfrac{1}{2}$	$\tfrac{1}{2}$	$0$	$\tfrac{1}{2}$
CL	$\tfrac{1}{2}$	$\tfrac{1}{2}$	$0$	$-\tfrac{1}{2}$
Group average	$\tfrac{n_{A}}{n_{A}+n_{B}}$	$\tfrac{n_{B}}{n_{A}+n_{B}}$	$0$	$0$
WPGMA	$\tfrac{1}{2}$	$\tfrac{1}{2}$	$0$	$0$
Centroid	$\tfrac{n_{A}}{n_{A}+n_{B}}$	$\tfrac{n_{B}}{n_{A}+n_{B}}$	$-\tfrac{n_{A}n_{B}}{(n_{A}+n_{B})^{2}}$	$0$
Median	$\tfrac{1}{2}$	$\tfrac{1}{2}$	$-\tfrac{1}{4}$	$0$

Appendix

Table 1: Parameter choices for common LW HC methods. Scores are negative dissimilarities, using squared dissimilarities for centroid, median, and Ward. See Milligan (1979) for discussion.

Setting	Clock tree	Phylogenetics
Encoder	Transformer	NeuralNJ axial MSA encoder
Layers / attention heads	2 / 4	6 / 8
Encoder width / feed-forward width	44 / 176	64 / 256
Encoder activation / dropout	ReLU / 0	GELU / 0.4
Leaf and merge dimension $d$	11	64
Merge MLP hidden width	44	128

Appendix

Table 2: Architecture and optimization settings for the reported clock-tree and phylogenetic checkpoints. Times include validation.

Figure 6: Validation curves for the phylogenetic and clock-tree models. (a) Mean RF on 90 held-out 50-taxon alignments per evaluation. (b) Mean sum of

L_{1}

diameters on 250 held-out 20-point sets. Stars mark the selected checkpoints at 196,000 and 1,300,000 training presentations, respectively.

$n$	NN-linkage	Best $\alpha$ -linkage	$\alpha$	SL	CL
120	$0.40\pm 0.16$	$14.82\pm 1.06$	0.00	$14.82\pm 1.06$	$24.58\pm 0.05$
180	$0.46\pm 0.13$	$2.13\pm 0.56$	0.10	$12.34\pm 1.13$	$24.65\pm 0.04$
240	$0.61\pm 0.12$	$0.95\pm 0.35$	0.10	$14.14\pm 1.15$	$24.73\pm 0.03$

Appendix

Table 3: Rings-and-disks point misclassification (%), mean

\pm

one standard error over 100 held-out clouds per size. Lower is better. The baseline uses one evaluation-set-tuned

\alpha

per size.

Figure 7: Rings-and-disks classification error at 120, 180, and 240 total points, evaluated over 100 held-out instances at each size; error bars show one standard error. Annotations give the evaluation-set-tuned mixing parameter for the

\alpha

-linkage baseline. Lower is better.

$n$	Clouds	Mean % vs CL	Median % vs CL	Std. dev.
20	50	-0.541	0.000	1.672
30	50	-0.601	-0.038	1.261
40	50	-0.294	-0.195	1.508
50	50	-0.468	-0.209	1.472
100	50	-0.265	-0.046	1.136
250	50	-0.392	-0.396	0.980

Appendix

Table 4: Uniform-point size generalization without recursive replacement or local refinement. Statistics summarize per-cloud percentage objective changes versus CL; negative is better.

$k$	CL mean %	CL time (s)	Model mean %	Model time (s)	Model median %
8	-1.187	1.001	-2.085	5.200	-1.776
10	-1.456	1.242	-2.231	5.636	-1.999
12	-1.726	1.483	-2.402	6.282	-2.277
14	-1.957	2.045	-2.599	8.722	-2.456
16	-2.109	4.768	-2.598	22.885	-2.437
17	-2.114	10.387	–	–	–

Appendix

Table 5: VLSI quality and runtime comparison. Objective changes and runtimes are averaged over the same 20 instances. One timed pass per instance uses one CPU thread and an RTX A6000 GPU for NN-linkage . Times include CL construction and all applicable refinement and recursive replacement, but exclude parsing, model loading, and startup warmup.

Dataset	Taxa	Median sites	Site range
JarvD5a	38–48	1,522	66–16,942
SongD1	37	2,588	486–14,659
TarvD7	10–36	1,749	288–16,812
WickD3b	51–97	887	278–3,868

Appendix

Table 7: Dimensions of the 26,136 matched empirical alignments.

		NN-linkage		NeuralNJ
Dataset	Trees	RF	Time (s)	RF	Time (s)
JarvD5a	14123	0.7203	0.418	0.7070	2.052
SongD1	423	0.3972	0.418	0.4371	2.461
TarvD7	11166	0.4751	0.240	0.5259	1.251
WickD3b	424	0.5414	0.251	0.5094	1.125
Overall	26136	0.6075	0.339	0.6221	1.701

Appendix

Table 8: Full neural-method evaluation underlying Fig. 5 : mean normalized RF and runtime on 26,136 shared successful alignments. Overall pools individual alignments.

Figure 8: Synthetic phylogenetic quality–runtime panels for all combinations of 20, 50, and 100 taxa with 256, 512, and 1024 sites. Each point averages the same 128 held-out instances within a panel. Dashed lines join nondominated points; numerical results are given in Tab. 9 .

		NN-linkage		NeuralNJ		BIONJ		RAxML-NG
Taxa / sites	Trees	RF	Time (s)	RF	Time (s)	RF	Time (s)	RF	Time (s)
20 / 256	128	0.2463	0.030	0.2514	0.089	0.3681	0.037	0.3373	0.617
20 / 512	128	0.1319	0.033	0.1356	0.122	0.2638	0.048	0.2068	1.080
20 / 1024	128	0.0901	0.047	0.1144	0.187	0.2307	0.080	0.1494	2.090
50 / 256	128	0.2565	0.078	0.2286	0.260	0.4327	0.087	0.3632	3.174
50 / 512	128	0.1772	0.100	0.1589	0.381	0.3605	0.117	0.2550	5.696

Appendix

Table 9: Complete synthetic evaluation: mean normalized RF and runtime on 128 held-out alignments per setting, using the generating trees as references. Overall pools all 1,152 alignments, equally weighting the nine settings.

		NN-linkage		NeuralNJ		BIONJ		RAxML-NG
Dataset	Trees	RF	Time (s)	RF	Time (s)	RF	Time (s)	RF	Time (s)
JarvD5a	250	0.7223	0.413	0.7010	2.016	0.6750	0.229	0.4964	22.133
SongD1	250	0.4002	0.451	0.4411	2.651	0.4468	0.215	0.1844	15.947
TarvD7	250	0.4702	0.237	0.5202	1.279	0.4867	0.155	0.2358	8.733
WickD3b	250	0.5440	0.248	0.5109	1.098	0.5444	0.209	0.1957	18.328
Overall	1000	0.5342	0.337	0.5433	1.761	0.5382	0.202	0.2781	16.285

Appendix

Table 10: Four-method empirical comparison: mean normalized RF and runtime on 250 sampled alignments per dataset, using per-locus best-observed trees as references. Overall pools all 1,000 alignments, equally weighting the four datasets.

Panel of Figure 9 — Figure 9: The optimal tree $(AC)(BD)$ , also returned by NN-linkage , and a possible CL tree $((AB)C)D$ on the original point set. Filled nodes retain the point locations. Hollow nodes show merges and are labeled by cluster diameter. Branches are schematic, not routing wires.

Explore similar work

Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning
Nov 30, 2025Dongyue Li, Zhenshuo Zhang, Minxuan Duan +2Graph Neural Networks Reasoning Benchmark
†Northeastern University, Boston, Massachusetts · ‡University of Pennsylvania, Philadelphia, Pennsylvania
Writhe-Based Polymer Link Classification Using Machine Learning
Jul 22, 2026Jack Beda, Djordje Mihajlovic, Kasturi Barkataki +1Polymer Property Prediction Neural Network
School of Physics and Astronomy, The University of Edinburgh, Peter Guthrie Tait Road, Edinburgh, EH9 3FD, UK. · School of Mathematics, The University of Edinburgh, Peter Guthrie Tait Road, Edinburgh, EH9 3FD, UK. · MRC Human Genetics Unit, Institute of Genetics and Cancer, University of Edinburgh, Edinburgh EH4 2XU, UK
Code evolution for link prediction in complex networks
Jun 18, 2026Alexey Vlaskin, Eduardo G. AltmannZero-Shot Link Prediction Network Science
School of Mathematics and Statistics & Centre for Complex Systems The University of Sydney, 2026, NSW & Sydney, Australia.

Nov 30, 2025, cs.LGJ/K move · Enter open · S save

Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning

Dongyue Li, Zhenshuo Zhang, Minxuan Duan, Edgar Dobriban+1

†Northeastern University, Boston, Massachusetts · ‡University of Pennsylvania, Philadelphia, Pennsylvania

Graph Neural Networks Reasoning Benchmark

Open paper AskPDF arXiv

Algorithmic reasoning -- the ability to perform step-by-step logical inference -- is a synthetic benchmark for evaluating multi-step reasoning abilities, designed for graph neural networks and also for transformer models. Prior work has evaluated reasoning for executing a single algorithmic task, whereas a more desirable objective is to perform multiple algorithmic reasoning tasks simultaneously. We start by noting that this is inherently difficult due to differences arising from the execution traces of the algorithms (such as depth- vs. breadth-first search), which cause interference when they are trained together. In this paper, we introduce {branching neural networks}, a new architecture for multitask algorithmic reasoning. The main idea is to search for a recursive tree-structured partition of

n

algorithmic tasks into a

k

-ary tree (divided into

L

layers). Naive search requires

O(k^{nL})

complexity; we develop an algorithm that reduces this to

O(nL)

by solving a convex relaxation at each layer to approximate an optimal partition. Our approach clusters these tasks using gradient-based affinity and can be used on top of any base model. We validate our approach on algorithmic reasoning benchmarks and their extensions with text descriptions. We show that gradient-based affinity scores help estimate true performance with less than 5% error, measured across eight different architectures with up to 34 billion parameters. On the CLRS benchmark, our approach outperforms existing graph neural networks by 3.7% and baselines by 1.2%, while reducing runtime by 48% and memory usage by 26%. The learned branching structure shows a hierarchical clustering of related algorithms. On three text-based graph reasoning benchmarks, our approach improves over baseline methods by 3.2%. Finally, we validate our approach for overlapping community detection.

Abstract

Explore similar work

Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning

Writhe-Based Polymer Link Classification Using Machine Learning

Code evolution for link prediction in complex networks