- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This manuscript introduces NN-LINKAGE, a neural agglomerative hierarchical clustering framework algorithmically aligned with the classical Lance-Williams (LW) recurrence. NN-LINKAGE replaces scalar cluster distances with learned merge embeddings, and updates them recursively via permutation-invariant MLPs.
The main results are:
- Thm 4: Universal approximation of continuous linkage functions on compact domains for fixed input size N.
- Thm 5: Exact size-invariant realization of symmetric constant-coefficient LW recurrences.
NN-LINKAGE can use a Transformer leaf encoder to represent global linkage rules such as robust single linkage. Evaluation is performed on synthetic "rings-and-disks" zero-skew VLSI clock-tree routing with the sum-of-diameters objective, and phylogenetic reconstruction from multiple sequence alignments.
Critical strengths
S1. Formulating learned hierarchical clustering via recursive merge embeddings that mimic the LW recurrence is an elegant idea providing natural inductive bias for bottom-up tree construction.
S2. The rings-and-disks experiment demonstrates NN-LINKAGE's ability to learn to perform Single Linkage merges in dense planar manifolds, and Complete Linkage merges in compact clusters within the same instance.
Critical weaknesses
W1. The claim of size-invariant algorithmic alignment is incomplete. The authors prove size invariance only for constant coefficients A=B. Ward's method and UPGMA require tracking cluster cardinalities, so NN-LINKAGE's fixed-size MLPs cannot realize them without feeding explicit size features. There is no formal generalization guarantees for that though.
W2. Ground-truth trees do not usually exist in practice. NN-LINKAGE requires supervision from optimal trees computed via expensive dynamic programming on small instances. At inference time, executing neural network MLPs inside a priority-queue loop results in a large runtime inflation over classical linkage, giving less than a 1% objective improvement on real-world benchmarks.
Questions for authors
Q1. Does NN-LINKAGE achieve size-invariant exact realization for Ward's or Average Linkage when cluster cardinalities are passed into MLPupdate? What happens to size generalization when training on n=20 and evaluating on n=1000 under size-dependent coefficients?
Q2. What is the raw performance and objective reduction of NN-LINKAGE on the 20 benchmark instances when run without using the Complete Linkage tree as fallback?
Q3. How robust is NN-LINKAGE to realistic evolutionary artifacts such as long-branch attraction, heterotachy, and varying sequence lengths?
4 comments
Q3.
We have added experiments addressing all three factors in Appendix F.2 and Figure 11. NN-linkage is robust to moderate rate variation and modest branch-length increases, but performance deteriorates at stronger settings. Shorter alignments also increase error.
For sequence length, we evaluate 256, 512, and 1,024 sites, averaging equally over 20, 50, and 100 taxa. Reducing sequence length from 1,024 to 512 sites increases mean normalized RF from 0.120 to 0.177; at 256 sites, it rises to 0.289 (Figure 11(a)).
For heterotachy, we partition sites into two equal-sized groups on a fixed tree topology. Independently on each branch, we randomly choose one group to evolve faster than the other. Their evolutionary rates are multiplied by and , respectively, preserving their average. Thus, larger means greater heterotachy. Mean RF changes little under moderate variation, from 0.165 at to 0.167 at , but increases to 0.237 at the strongest setting, (Figure 11(b)).
For long-branch attraction, we test whether additional evolutionary change causes NN-linkage to incorrectly group two non-sister taxa. We increase the expected number of substitutions along their terminal branches while leaving all other branches unchanged. Doubling this amount increases the incorrect-grouping rate only modestly from 1.6% to 3.1%. The rate rises to 18.0% at four times the original amount of evolutionary change and 46.1% at eight times that amount (Figure 11(c)).
I appreciate the thorough response and the significant additions in the new draft.
The authors addressed some of the concerns.
- Q2, Q3 are addressed in Appendices D and F.
- Q1 & W1 are partially addressed in the new theorem.
- W2 is not addressed. In my 15+ years of industrial work on (large-scale) hierarchical clustering (both in theory & practice, with perhaps 100+ applications), I have never used DP on small instances and almost never had real ground-truth instances. I did try some sort of supervision to set the parameters of the algorithm automatically, but it didn't work well because of the same reasons: lack of proper data, costly optimization, etc. That's why I say this method is not practical. Some experiments show improvements and I acknowledge the authors are using the framework of the previous work of Zhang et al. (2025) and compare to NeuralNJ and Phyloformer.
I am raising my score from 2 (Weak rejection) to 3 (Weak acceptance), mostly because of the ablations and the new theoretical result.
Thank you for considering our rebuttal and raising your score. We agree that the availability of ground-truth training instances is a key consideration. Training our neural-algorithmic framework through reinforcement learning could provide an alternative to tree supervision and is an important direction for future work.
W1.
Indeed, our exact size-independent theorem does not cover Ward or average linkage. However, our universality theorem shows that both can be approximated arbitrarily accurately for bounded input size.
Also, our model is expressive enough to track cluster sizes exactly as the update MLP can add the sizes of merged clusters recurrently. Thus, adding cluster size inputs does not change the expressivity and computing cluster sizes is therefore not the obstacle to representing Ward and average linkage. Instead, the challenge is that approximating the size-dependent coefficients introduces errors that can accumulate over recurrent updates. Larger instances involve more updates, so the accumulated error can increase with input size.
To clarify the model’s expressivity for these linkage functions, we have added an appendix theorem (Appendix C) proving arbitrarily accurate approximation of a single update by a fixed-size model, uniformly over cluster sizes and for bounded incoming scores. The theorem covers a class containing all standard LW recurrences, including size-dependent rules such as average linkage. By considering only a single update, it avoids the accumulation of error across recurrent updates.
W2.
We acknowledge that supervision can be quite costly. This motivates our focus on size generalization, where the model learns from small instances that can be solved exactly and is then tested on larger instances. Supervision also provides a powerful way to specify complex objectives through examples. In phylogenetics, for instance, simulations can encode complex evolutionary processes even when the corresponding objective is difficult to formulate analytically. Similarly the diameter-sum objective is highly application specific. Although unsupervised methods avoid the cost of generating labels, they only apply to the particular unsupervised objective they optimize. Our approach therefore complements unsupervised methods, which may be better suited to specific settings.
Neural inference does add overhead relative to classical linkage. For clock-tree routing NN-linkage extends the quality–runtime Pareto frontier relative to refined complete linkage (Figure 3b). Although the objective gains are modest, these results are state of the art for this problem.
Q1.
Thank you for the questions. Explicitly providing cluster sizes does not make the size-dependent updates exact. As discussed above, the challenge is that approximation errors can accumulate across recurrent updates. To better illustrate this approximation power, our new additional theorem guarantees arbitrarily accurate size-uniform approximation of a single update (and does not require cluster sizes as explicit input).
Average linkage and Ward’s method are indeed interesting rules to test given their size-dependent coefficients. We have added an experiment training NN-linkage to imitate each rule on n=20 instances and evaluating size generalization up to n=1000 (Figure 12 in Appendix F.4 of the revised manuscript). At each step, we compare the cost of the model’s chosen merge with the minimum cost among all available merges, using the target linkage rule to measure cost. The percentage increase, averaged over merges and test instances, is below 0.1 at n=100 for both rules. At n=250, it is 0.385 for average linkage and 0.747 for Ward, increasing to 4.16 and 7.64, respectively, at n=1000, 50 times the training size. These results show strong generalization and replication of the target linkage up to n=250, with performance deteriorating at larger sizes.
Q2.
We have modified the manuscript to include the performance directly on all 20 VLSI benchmarks, without CL fallback, recursive replacement, or local refinement. NN-linkage improves the objective on 5 instances, but increases it by 5.00% on average. A few severe failures contribute substantially to this average. In particular, the objective increases by 11.31%, 12.85%, and 53.09% on instances s2r1, 06, and 03, respectively. Full per-instance results and runtimes are in Table 7 in Appendix D.2 of the revised manuscript.
These results illustrate a limitation of applying NN-linkage outside its training distribution. The model is trained on uniformly sampled 20-point instances, whereas these benchmarks contain 74 to 3,101 points and have different spatial distributions. This motivates the recursive refinement approach used in the paper.