Paper deep dive
Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks
Renata Martins Castanheira, Miguel Bugalho, Cátia Vaz
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 7/22/2026, 2:15:11 AM
Summary
This paper investigates using a Siamese Graph Isomorphism Network (GIN) to approximate the Subtree Prune and Regraft (SPR) distance between phylogenetic trees, addressing the NP-hard computational complexity of exact SPR calculation. The authors release a dataset of 864 trees from four bacterial species and validate a heuristic supervision target (phangorn) against exact distances (rspr). The GIN model achieves high accuracy (R² ≈ 0.87-0.90) on in-distribution data but fails to extrapolate to larger tree sizes and shows limited transfer to unseen species.
Entities (13)
Relation Signals (10)
Siamese Graph Isomorphism Network (GIN) → approximates → Subtree Prune and Regraft (SPR) distance
confidence 95% · We investigate whether a Graph Neural Network (GNN) can approximate SPR distances
phangorn::SPR.dist → usedassupervisiontargetfor → Siamese Graph Isomorphism Network (GIN)
confidence 92% · we adopt a polynomial-time heuristic, the unrooted phangorn::SPR.dist, as the supervision target
phangorn::SPR.dist → correlateswith → rspr
confidence 90% · the unrooted phangorn::SPR.dist heuristic correlates almost perfectly with the exact rooted distance computed by rspr
UPGMA → generates → phylogenetic trees
confidence 90% · phylogenetic trees inferred with UPGMA and Neighbor-Joining
Neighbor-Joining → generates → phylogenetic trees
confidence 90% · phylogenetic trees inferred with UPGMA and Neighbor-Joining
midpoint re-rooting → appliedto → Neighbor-Joining trees
confidence 88% · NJ trees are unrooted... so we apply midpoint rooting... This yields the rooted binary trees
Siamese Graph Isomorphism Network (GIN) → trainedon → Clostridium
confidence 85% · dataset of 864 phylogenetic trees inferred... over four bacterial species... Clostridium
Siamese Graph Isomorphism Network (GIN) → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Comparing phylogenetic tree topologies is essential for understanding epidemic dynamics, yet biologically meaningful distances such as the Subtree Prune and Regraft (SPR) distance are NP-hard to compute and intractable on large datasets. We investigate whether a Graph Neural Network (GNN) can approximate SPR distances in near-constant time per comparison after training. Our contributions are fourfold. First, we build and publicly release a dataset of 864 phylogenetic trees inferred with UPGMA and Neighbor-Joining over four bacterial species, spanning up to 9{,}500 isolates, together with 388 labelled tree pairs. Second, we establish a reproducible pre-processing pipeline including midpoint re-rooting, which reduces tree depth and supplies the rooting required for exact distance computation and for the model's root-based features. Third, we validate the supervision target: on small trees, where exact SPR is tractable, the unrooted phangorn::this http URL heuristic correlates almost perfectly with the exact rooted distance computed by rspr (Pearson $0.98$--$0.99$), making it an excellent monotonic surrogate. Lastly, we train a Siamese Graph Isomorphism Network (GIN) regressor. In-distribution, i.e., held-out trees from the same species and size range as training, it explains roughly 87--90% of the variance ($R^2 \approx 0.87$ on a held-out split; $0.90 \pm 0.19$ under stratified cross-validation), with about four times lower error than a mean-predictor baseline, and shows partial transfer to unseen species ($R^2 \approx 0.37$). Its main limitation is extrapolation to trees larger than those seen in training, where accuracy collapses. The released dataset and the validated heuristic versus exact relationship provide a reproducible basis for scaling learned SPR approximation.
Tags
Links
- Source: https://arxiv.org/abs/2607.18311v1
- Canonical: https://arxiv.org/abs/2607.18311v1
Trouble viewing inline? Open PDF directly →
Full Text
35,964 characters extracted from source content.
Expand or collapse full text
Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks Renata Martins Castanheira 1[0009−0005−6690−6707] , Miguel Bugalho 1,2[0000−0002−4630−9615] , and Cátia Vaz 1,3[0000−0001−6074−3074] 1 ISEL – Instituto Superior de Engenharia de Lisboa, Instituto Politécnico de Lisboa, Portugal 2 ALGORITMI Research Center/CCPM, Portugal 3 INESC-ID Lisboa, Portugal 51830@alunos.isel.ipl.pt, miguel.bugalho@isel.pt, cvaz@c.isel.ipl.pt Abstract. Comparing phylogenetic tree topologies is essential for un- derstanding epidemic dynamics, yet biologically meaningful distances such as the Subtree Prune and Regraft (SPR) distance are NP-hard to compute and intractable on large datasets. We investigate whether a Graph Neural Network (GNN) can approximate SPR distances in near- constant time per comparison after training. Our contributions are four- fold. First, we build and publicly release a dataset of 864 phylogenetic trees inferred with UPGMA and Neighbor-Joining over four bacterial species, spanning up to 9,500 isolates, together with 388 labelled tree pairs. Second, we establish a reproducible pre-processing pipeline in- cluding midpoint re-rooting, which reduces tree depth and supplies the rooting required for exact distance computation and for the model’s root- based features. Third, we validate the supervision target: on small trees, where exact SPR is tractable, the unrooted phangorn::SPR.dist heuris- tic correlates almost perfectly with the exact rooted distance computed by rspr (Pearson 0.98–0.99), making it an excellent monotonic surrogate. Lastly, we train a Siamese Graph Isomorphism Network (GIN) regres- sor. In-distribution, em i.e., held-out trees from the same species and size range as training, it explains roughly 87–90% of the variance (R 2 ≈ 0.87 on a held-out split; 0.90± 0.19 under stratified cross-validation), with about four times lower error than a mean-predictor baseline, and shows partial transfer to unseen species (R 2 ≈ 0.37). Its main limitation is extrapolation to trees larger than those seen in training, where accu- racy collapses. The released dataset and the validated heuristic versus exact relationship provide a reproducible basis for scaling learned SPR approximation. Keywords: Phylogenetic Tree Comparison· Graph Isomorphism Net- works· Subtree Prune and Regraft· Benchmark Dataset· Graph Simi- larity Learning. 1 Introduction Determining the origin, evolutionary dynamics and transmission patterns of bac- terial and viral epidemics is among the central challenges of computational bi- arXiv:2607.18311v1 [q-bio.PE] 17 Jul 2026 R. M. Castanheira et al. ology. Phylogenetic inference reconstructs these evolutionary relationships. Its outcome, the phylogenetic tree [17], is an indispensable data structure for tasks such as tracking pathogen strains through an outbreak. Different inference methods, such as Maximum Likelihood [9], Maximum Par- simony [11], Neighbor-Joining (NJ) [25], UPGMA [29], or goeBURST [12], fre- quently produce distinct topologies for the same isolates [31], so evaluating and reconciling them requires comparing trees at scale. The available distance mea- sures trade speed against biological meaning (Section 2): cheap partition-based measures such as Robinson–Foulds [24] saturate quickly and overreact to a sin- gle displaced taxon, whereas the Subtree Prune and Regraft (SPR) distance [13] directly counts the prune-and-regraft operations between two topologies and so models reticulate events such as recombination and horizontal gene trans- fer. That biological fidelity is costly since computing the rooted SPR distance is NP-hard [3], which rules out exact computation for trees with thousands of leaves. This motivates an approximation that is both accurate and fast. Since the exact rooted distance is intractable at scale, it cannot serve as a training sig- nal for large trees; we therefore adopt a polynomial-time heuristic, the un- rooted phangorn::SPR.dist, as the supervision target, after first verifying on small trees—where exact computation is feasible—that it tracks the exact rooted SPR distance almost perfectly (Pearson 0.98–0.99). We then ask whether a GNN [35] can learn to reproduce this surrogate directly from tree structure, so that each comparison reduces to a single forward pass at inference time. Our contributions are: 1. A reproducible pre-processing pipeline that slices genomic profiles into size- stratified sub-datasets, diversifies them through controlled shuffling, infers UPGMA and NJ trees, applies midpoint re-rooting [21], and extracts SPR supervision labels. 2. A publicly released dataset [5] of 864 trees and 388 labelled tree pairs across four bacterial species, with isolates up to 9,500 sequences. 3. A validation of the supervision target against the exact rooted SPR distance computed with rspr [34], clarifying the relationship between the exact metric and the phangorn [26] heuristic. 4. A Siamese GIN [36] regressor with training and inference pipelines 4 , together with an assessment of where it works (in-distribution), where transfer is partial (across species), and where it fails (size extrapolation). 2 Related Work Molecular epidemiology and comparative genomics increasingly reconstruct phy- logenies from typing and whole-genome data for collections reaching thousands of isolates, where the resulting trees drive outbreak investigation and the study of recombination and horizontal gene transfer [17]. Because standard inference 4 publicly available at https://github.com/RenataCastanheira/LearningPhylogeneti cTreeSimilarityWithGraphNeuralNetworks Learning Phylogenetic Tree Similarity with GNNs methods, such as NJ [25], UPGMA [29], goeBURST [12], Maximum Likeli- hood [9] and Maximum Parsimony [11], routinely return different topologies for the same isolates [31], comparing trees is a recurring and increasingly large-scale step in any such analysis. The metric chosen for that comparison is in practice a tooling decision with biological consequences. The Robinson–Foulds distance [24] is the field’s workhorse because it is linear-time and widely implemented, but it saturates on divergent isolates and overreacts to a single misplaced taxon, lim- iting its use for fine-grained outbreak resolution; information-theoretic variants soften this [28]. Quartet [8] and path-difference [30] measures recover more topo- logical detail but report a value that does not translate cleanly into evolutionary events. Rearrangement distances are the biologically literate alternative: the Sub- tree Prune and Regraft (SPR) distance [13], like the related Tree Bisection and Reconnection [1], counts the edit operations between two trees and so directly models reticulate processes such as recombination and horizontal gene transfer. The cost is computational, since rooted SPR is NP-hard [3], and this shapes the available software: rspr [34] delivers exact rooted distances through maximum agreement forests but only for modest trees, whereas phangorn [26] scales by es- timating the unrooted distance heuristically, with no approximation guarantee, based on the algorithm of de Oliveira Martins et al. [23]. We address this lack of a guarantee by validating the heuristic directly against the exact rooted dis- tance (Section 5) before adopting it as our supervision target. A related quantity, the lower bound on the unrooted distance, is similarly tractable via agreement forests [33]. What no existing tool offers is amortized, near-constant-time com- parison: exact methods do not scale, and although the heuristic scales, it must be recomputed for every pair. This is the gap a learned estimator can fill, and graph neural networks [35] are a natural instrument because a phylogeny is a graph. Their behaviour on this data hinges on the aggregation function: the degree-normalised mean of Graph Convolutional Networks [19] and the learned attention of Graph Attention Networks [32] tend to smooth away structure on the near-3-regular topologies of binary trees, whereas the injective sum of Graph Isomorphism Networks [36] preserves exactly the differences the SPR distance depends on, matching the discriminative power of the Weisfeiler–Lehman test. For pairwise comparison, two paradigms dominate. Cross-graph matching networks such as Graph Matching Networks [20] inject node-to-node attention for fine-grained accuracy but scale poorly with graph size. Graph embedding approaches, exemplified by SimGNN [2], encode each graph independently and predict from the pair of embeddings; these Siamese designs [4] are cheaper and scale better. Given our target of trees with thousands of leaves, we adopt the embedding paradigm with a Siamese GIN encoder. To our knowledge, approxi- mating the NP-hard SPR distance on rooted phylogenies with this approach has not previously been addressed. 3 Dataset and Ground-Truth Construction As depicted in Figure 1, the dataset is organised as a five-stage pipeline. R. M. Castanheira et al. cgMLST profiles 4 species (EnteroBase, pubMLST) Size-stratified sub- datasets small - medium - large (up to 9500) Original + shuffled datasets NJ and UPGMA trees Midpoint re-rooted NJ trees SPR distances calculated over a controlled scale-ratio tree pair dataset 2.Shuffle all the dataset to generate alternative topological variants 1. Slice & Stratify the dataset into three distinct size categories 4. Midpoint rooting to standardize tree topology 5. Pairing + labelling 3. UPGMA & NJ tree inference (PhyloLib) Fig. 1: Pre-processing pipeline: dataset slicing, controlled shuffling, UPGMA/NJ inference, midpoint re-rooting, and SPR labelling. Profiles and stratification. We sample core-genome MLST (cgMLST) [22] profiles for four bacterial species: Clostridium, Salmonella and Vibrio from En- teroBase [7], and Streptococcus pneumoniae from PubMLST [16]. A custom R script slices the original profiles sequentially, always from the first row onward, into three size tiers: small (90–1,000 isolates, 25%), medium (2,000–6,000, 25%) and large (7,000–9,500, 50%); see Fig. 2a. Slicing contiguously preserves the implicit temporal and geographic structure of the profiles and ensures smaller sub-datasets are nested within larger ones. Controlled shuffling. Distance-based methods such as NJ and UPGMA are sensitive to input order when breaking ties in the distance matrix. We exploit this with a seeded permutation script that reorders profile rows, forcing the algo- rithms to resolve ties differently and produce topologies with minor, controlled structural variations. Inference and re-rooting. From each (original and shuffled) sub-dataset we compute a Hamming distance matrix and infer UPGMA and NJ trees in Newick format with PhyloLib [27]. NJ trees are unrooted, with a basal trifurcation, so we apply midpoint rooting [21] using Biopython’s Bio.Phylo [6]. This yields the rooted binary trees required by the exact rooted-SPR algorithm and defines the model’s root-based node features. Rooting also balances the topology: on a 469-isolate Salmonella tree it reduced maximum topological depth from 52 to 33 and average depth from ≈ 31.2 to ≈ 16.0, which lowers the cost of the traversal-based heuristic label computation. Pairing and labelling. We form 388 tree pairs following a fixed niche dis- tribution: UPGMA vs. NJ (40%), NJ vs. NJ sh (25%), UPGMA vs. UPGMA sh Learning Phylogenetic Tree Similarity with GNNs (15%), and two zero-distance control blocks NJ vs. NJ and UPGMA vs. UP- GMA (10% each); see Fig. 2b. For each pair we extract the SPR label with phangorn::SPR.dist; the structural trace (the leaves that move between the two topologies) is obtained from the maximum agreement forest (MAF) com- puted exactly with rspr [34], for which the rooted SPR distance equals the number of MAF components minus one. The master table is split into disjoint train, validation and test subsets. (a) Dataset size distribution.(b) Tree pair distribution for pairing and labelling. Fig. 2: Dataset statistics. Notice that the supervision target is a heuristic estimate of the unrooted SPR distance, the phangorn::SPR.dist [23], and although it was originally described as a conservative upper-bound estimate, no error bound was ever formally es- tablished, and in practice it tends to underestimate the true SPR distance when that distance is small relative to tree size, which is precisely our regime. Second, inspection of the phangorn source shows that SPR.dist internally unroots both inputs (it calls clean_phylo(..., unroot=TRUE) and canonicalises bipartitions with SHORTwise) and exposes no rooted option. Passing rooted trees therefore does not yield a rooted SPR distance. In contrast, rspr [34] computes the exact rooted SPR distance. The two tools thus measure related but distinct quantities. In Section 5 we evaluate how the exact rooted SPR distance compares against the unrooted heuristic estimate from the phangorn package. 4 Method Figure 3 gives a high-level overview of the model: a tree representation module produces node features, a shared GIN module encodes each tree, and an output module pools and regresses the pair to an SPR distance. R. M. Castanheira et al. Pre-processing & Node Features GIN (Graph Isomorphism Network) Module Output vector node feature exatraction Embedding Layer Concatenation of features GIN convolution layers Global Pooling Concatenation of embeddings Fully connected network (MLP) Final prediction value .nwk Fig. 3: High-level architecture. Both trees are encoded by the same (Siamese) GIN module (node/edge features, GIN convolution with batch normalisation and ReLU), and the output module pools each tree and regresses the pair to the predicted SPR distance. 4.1 Graph Representation and Node Features Each Newick tree is parsed with Biopython [6] and converted to a directed graph whose root is the unique in-degree-zero vertex. Then, it is encoded as a bidirectional graph in PyTorch Geometric [10] so that messages propagate in both directions. In this context, each node carries a four-dimensional feature vector: node degree, a binary leaf indicator, the topological distance to the root in number of branches, and a categorical taxonomic identifier. The first three are used directly, while the identifier is mapped through a trainable Embedding layer of dimension 16, with vocabulary size set dynamically to max_id + 1 to handle large isolate counts. Concatenation yields a 19-dimensional input per node. Figure 4 illustrates the full encoding, from the Newick string to the per- node feature vector. 4.2 Siamese GIN Regressor The model, detailed in Fig. 5, is a Siamese embedding network: both trees of a pair pass through the same GIN encoder. Each GIN layer [36] updates node features as h (k) i = MLP (k) (1 + ε (k) )h (k−1) i + X j∈N(i) h (k−1) j ,(1) where N(i) is the neighbourhood of node i. We stack two GIN layers of hidden dimension 128; each wraps a two-layer MLP, Linear-ReLU-Linear, followed by batch normalisation [15] and ReLU. A global sum-pooling layer then aggregates node features into a fixed-size graph embedding v g = X i∈V g h i .(2) The two embeddings v a and v b are concatenated into a 256-dimensional vector and regressed by an MLP head 256→128→64→1 with ReLU activations and dropout 0.3, producing the predicted SPR distance. Learning Phylogenetic Tree Similarity with GNNs 4.3 Training To keep training efficient, each tree is parsed and converted to a PyTorch Geo- metric object once and cached in memory, which reduces the per-epoch cost from O(epochs×N) to O(N). The network is trained with the Adam optimiser [18] at a learning rate of 10 −4 and weight decay of 10 −4 , minimising the Huber loss [14], which is robust to the right-skewed distribution of SPR values. The learning rate is halved on plateau after 10 epochs without improvement, and training stops early after 25 such epochs. We split the labelled pairs 70/15/15 into training, val- idation and test sets under a fixed seed. Predicted distances are clamped at zero, since negative distances are biologically meaningless. Performance is reported as Mean Absolute Error (MAE), Root Mean Squared Error (RMSE), Mean Abso- lute Percentage Error (MAPE) and the coefficient of determination R 2 . Figure 6 summarises the full training, validation, testing and inference workflow. 5 Experimental Evaluation This section evaluates the approach along three axes. We first assess the scala- bility of the labelling pipeline; we then quantify how well the phangorn heuristic used for supervision approximates the exact rooted SPR distance; and we finally measure the accuracy and generalization of the trained Siamese GIN across in- distribution, cross-species, and size-extrapolation regimes. 5.1 Scalability of the Pipeline In stress testing on a virtual machine with 240 GiB of RAM and Intel Xeon Silver CPUs, the labelling pipeline scaled to trees of up to 9,500 profiles. Exact rspr Extraction of node features for each node Pos. 0: Node ID (Embedding Layer) Pos. 1: Is Leaf (Binary) Pos. 2: Root Distance (Float) Pos. 3: Root Distance (Float) .nwk Format conversion Directed graph Newick string Definition of topology Edge duplication (u ⇄ v) Bidirectional Graph Loop over EdgesLoop over Nodes Attributes Matrix [N, 4] Connectivity Matrix [2, E] PyG Data Object 3 positions 16 positions concat Fig. 4: Input representation and node encoding. The Newick tree is parsed into a bidirectional graph; each node yields a feature row (degree, is-leaf, distance to root, species id). The three structural features (dim 3) are concatenated with a learned species embedding (dim 16) to form the 19-dimensional node feature. R. M. Castanheira et al. Shared weights Layer 1Layer 2Layer 3 GINConv (MLP) GINConv (MLP) GINConv (MLP) BatchNorm1dBatchNorm1dBatchNorm1d ReLUReLUReLU [N, 128][N, 128][N, 128] Global Add Pooling Graph Embedding vector [128] Layer 1Layer 2Layer 3 GINConv (MLP) GINConv (MLP) GINConv (MLP) BatchNorm1dBatchNorm1dBatchNorm1d ReLUReLUReLU [N, 128][N, 128][N, 128] Global Add Pooling Graph Embedding vector [128] Aggregates N nodes in a single vector of the graph concat Feature concat [N, 19] PyG Data Object Node IDs [N] Continuous Features [N,3] Embedding Layer (Num_species: 16-dim ) Node Embeds [N,16] PyG Data Object Node IDs [N] Continuous Features [N,3] Embedding Layer (Num_species: 16-dim ) Node Embeds [N,16] Feature concat [N, 19] PyG Data Object MLP Regression Linear(256,128) - ReLU - Dropout Linear(128, 64) - ReLU - Dropout Linear(64, 1) Predicted SPR Fig. 5: Detailed Siamese GIN. Each tree passes through the same encoder (two GIN layers, each a GINConv MLP Linear–ReLU–Linear followed by batch nor- malisation and ReLU); global pooling (add) yields a 128-d embedding per tree. The two embeddings are concatenated (256-d) and regressed by the MLP head 256→128→64→1 to the predicted SPR distance. computation, by contrast, was not feasible for all those trees. A trained GNN then predicts a distance in a single forward pass, in a fraction of the heuristic’s time. 5.2 Validating the Supervision Target On small validation trees (20–90 leaves), where exact computation is tractable, we compared the unrooted phangorn heuristic against the exact rooted SPR distance. Table 1 reports the Clostridium pairs. The heuristic is strongly rank- correlated with the exact distance (Pearson 0.983 on Clostridium, 0.9935 on a Vibrio subset, and 0.99 pooled over n = 26 pairs), but it systematically under- estimates the magnitude, returning on average about 65% for Clostridium and 71% for Vibrio of the exact value. This underestimation is expected rather than a heuristic failure, and has two sources. First, phangorn estimates the unrooted SPR distance, which is generally no larger than the rooted distance preserved by midpoint rooting. Second, the heuristic itself carries no proven approximation bound and empirically underestimates the true SPR distance when that distance is small relative to tree size, consistent with the systematic gap we observe. Both effects push the heuristic below the exact rooted value. The very high correlation nonetheless shows it is an excellent monotonic surrogate, which is what matters for training a regressor, even if it is a biased estimator of the rooted magnitude. Learning Phylogenetic Tree Similarity with GNNs Labelled dataset - 388 pairs Training set 70% Validation set 15% Test set 15% Train file .csv (pair + spr dist) Trained Model Inference/ Prediction Siamese GIN (trained)Estimated SPR distance Loads wieghts 1. Get Batch (DataLoaders) - loads graph pairs (A, B) - extracts target SPR from memory 2. Siamese GIN - Forward - Processes trees & Global add pooling 4. Huber Loss & Optimization - Compares estimate value with target SPR; - Adam updates weights; 3. Output - Estimates SPR value per epoch process 1 tree pair new, unseen file of tree pairs same as in test phase forward - val MAE ReduceLROnPlateau adjust LR/ Stop Early Stopping forward - predictions Final Metrics: - MAE - RMSE - MAPE - R^2 Fig. 6: Workflow. The labelled pairs are split (70/15/15, seed 42) into training, validation and test sets. Training back-propagates the Huber loss with Adam; validation drives learning-rate scheduling and early stopping and selects the best model; the held-out test set is used once for the final metrics. At inference, the trained model estimates SPR of a new tree pair in a single forward pass. The trace (relocated leaves) is far larger than the SPR distance itself, for exam- ple 8 operations but 21 leaves moved at size 55, since a single prune-and-regraft move can displace an entire subtree. 5.3 Model Performance Under stratified cross-validation the Siamese GIN reaches R 2 = 0.905± 0.191, MAE = 92.24±7.02, RMSE = 128.14±11.07 and MAPE = 2.16%±0.37%. The standard deviation is driven by occasional right-skewed outliers in small valida- tion splits rather than by instability of the fit. Table 2 reports three single-split configurations that delimit the model’s operating envelope. Three findings stand out. (i) In-distribution, the model explains ≈ 87% of the variance and beats the mean baseline by roughly 4× in MAE, so the GNN genuinely learns to compare topologies. (i) Trained on two species and tested on two unseen ones (Clostrid- ium and Vibrio → Salmonella and S. pneumoniae), it attains R 2 = 0.37. This in- dicates that the learned representation captures some species-agnostic structure, but that cross-species generalization remains challenging. The drop is hard to R. M. Castanheira et al. Table 1: Heuristic (unrooted phangorn estimate) vs. exact rooted SPR (rspr) on the small Clostridium validation pairs (20–90 leaves). Trace is the number of relocated leaves, read from the maximum agreement forest (MAF). Subscript s denotes shuffled input. Size PairHeuristic Exact Trace 20 NJ s vs UPGMA s 6915 30 UPGMA s vs UPGMA122022 40 UPGMA s vs UPGMA172835 45 UPGMA vs NJ s 203337 50 UPGMA vs UPGMA s 223843 55 UPGMA vs NJ5821 60 UPGMA vs NJ5922 65 UPGMA vs NJ6926 70 UPGMA vs NJ71028 75 UPGMA vs NJ71131 80 UPGMA vs NJ101433 85 UPGMA vs NJ141953 90 UPGMA vs NJ152060 Table 2: GIN performance across data regimes. “Baseline” is the mean-predictor MAE. In-distribution results are strong; cross-species transfer is limited and size extrapolation fails. ConfigurationMAE RMSE R 2 Baseline MAE In-distribution (4 species, mixed sizes) 127.13 202.24 0.873485.78 Cross-species (train 2 sp. / test 2 sp.) 208.70 325.72 0.368406.05 Size extrapolation (small+med. → large) 375.90 643.02 −0.14553.65 attribute to domain shift alone, since this split also reduces the training set sub- stantially, so data scarcity is a likely contributing factor. (i) When trained only on small and medium trees and asked to predict on large ones, performance falls below the mean baseline (R 2 =−0.137): the model does not extrapolate to tree sizes outside its training range. The calibration analysis on the in-distribution test set, shown in Figure 7, is consistent with this: predictions cluster around the ideal y = x line but compress towards the mean, overestimating short distances and underestimating long ones. Figure 8 refines this picture through the devia- tion histograms. The absolute-deviation histogram concentrates sharply around zero, so the model predicts most pairs accurately, with a slight right-skew and a tail that indicate an occasional tendency to overestimate on complex topologies. The normalized-deviation histogram is likewise concentrated near zero, showing that the largest absolute errors fall on pairs with inherently large SPR distances, so the relative error stays low across most of the domain. Learning Phylogenetic Tree Similarity with GNNs Fig. 7: Calibration on the in-distribution test set: model-predicted vs. true SPR distance, with the ideal y = x line. Points track the diagonal but compress towards the mean, with short distances overestimated and long distances under- estimated. 5.4 Discussion Taken together, the experiments show that the binding limitation is neither the architecture nor, primarily, the absolute size of the labelled set (388 pairs), but its coverage across tree scales. The model interpolates well and transfers only partially across species, but it cannot yet extrapolate in size, and it inherits a calibration bias from the heuristic labels and from sum pooling. These limitations are addressable: enriching the training distribution with larger trees, exploring size-aware normalisation, and correcting the label offset are concrete next steps. Among the pooling strategies we tested, sum pooling gave the best overall results, but it remains a source of the size-related bias, so alternative aggregation schemes are worth exploring. 6 Final Remarks We presented a reproducible ecosystem for approximating the NP-hard SPR distance between phylogenetic trees: a pre-processing pipeline, an openly released dataset of 864 trees and 388 labelled pairs, and a Siamese GIN regressor with training and inference tools. We validated the supervision target against exact rooted SPR (Pearson 0.98–0.99) and clarified the distinction between phangorn and rspr. The model predicts SPR distances accurately in-distribution (R 2 ≈ R. M. Castanheira et al. Fig. 8: Distribution of prediction deviations from the ground-truth SPR distance. Left: absolute deviation concentrates around zero (ideal prediction), with a slight right-skew. Right: normalized deviation is near zero for most instances, indicat- ing that larger absolute deviations occur mostly at higher baseline distances. 0.87–0.90) and shows partial transfer across species (R 2 ≈ 0.37), while its current weakness is size extrapolation. Future work will expand the dataset towards larger topologies, add size-aware pooling and calibration, and benchmark the learned predictor against exact and approximate SPR tools. A further direction is to predict the SPR trace rather than only its mag- nitude: to identify the specific leaves that must be relocated to transform one tree into the other, recovering the sequence of prune-and-regraft operations re- lating the two topologies. This would let the model report not only how far apart two trees are but where they differ. The trace currently depends on exact MAF extraction via rspr, whose cost grows prohibitive on large trees, so trace supervision at scale would itself require a heuristic or learned approximation of the MAF. Together, these steps target a fast, scalable approximation suitable for large-scale epidemiological and comparative-genomic analyses. Acknowledgments. The authors acknowledge the support by national funds through the Fundação para a Ciência e a Tecnologia, I.P. (FCT) under projects UID/50021/2025, UID/PRR/50021/2025, UID/PRR/00006/2025, and grant 2023.17447.ICDT. Disclosure of Interests. The authors have no competing interests to declare that are relevant to the content of this article. References 1. Allen, B.L., Steel, M.: Subtree transfer operations and their induced metrics on evolutionary trees. Annals of Combinatorics 5(1), 1–15 (2001). https://doi.org/10 .1007/s00026-001-8006-8 2. Bai, Y., Ding, H., Bian, S., Chen, T., Sun, Y., Wang, W.: SimGNN: A neural network approach to fast graph similarity computation. In: Proceedings of the 12th ACM International Conference on Web Search and Data Mining (WSDM). p. 384–392 (2019). https://doi.org/10.1145/3289600.3290967 Learning Phylogenetic Tree Similarity with GNNs 3. Bordewich, M., Semple, C.: On the computational complexity of the rooted subtree prune and regraft distance. Annals of Combinatorics 8(4), 409–423 (2005). https: //doi.org/10.1007/s00026-004-0229-z 4. Bromley, J., Guyon, I., LeCun, Y., Säckinger, E., Shah, R.: Signature verification using a" siamese" time delay neural network. Advances in neural information pro- cessing systems 6 (1993), https://papers.nips.c/paper_files/paper/1993/hash/2 88c0f022877bd3df94bc9360b9c5d-Abstract.html 5. Castanheira, R., Bugalho, M., Vaz, C.: Phylogenetic trees inferred with different algorithms dataset and their SPR comparison. Zenodo (2026). https://doi.org/10 .5281/zenodo.20476872 6. Cock, P.J.A., Antao, T., Chang, J.T., Chapman, B.A., Cox, C.J., Dalke, A., Fried- berg, I., Hamelryck, T., Kauff, F., Wilczynski, B., de Hoon, M.J.L.: Biopython: freely available python tools for computational molecular biology and bioinformat- ics. Bioinformatics 25(11), 1422–1423 (2009). https://doi.org/10.1093/bioinforma tics/btp163 7. Dyer, N.P., Päuker, B., Baxter, L., Gupta, A., Bunk, B., Overmann, J., Diricks, M., Dreyer, V., Niemann, S., Holt, K.E., Rahman, M., Brown, P.E., Stark, R., Zhou, Z., Ott, S., Nübel, U.: EnteroBase in 2025: exploring the genomic epidemiology of bacterial pathogens. Nucleic Acids Research 53(D1), D757–D763 (10 2024). https://doi.org/10.1093/nar/gkae939, https://doi.org 8. Estabrook, G.F., McMorris, F.R., Meacham, C.A.: Comparison of undirected phy- logenetic trees based on subtrees of four evolutionary units. Systematic Zoology 34(2), 193–200 (1985). https://doi.org/10.2307/2413326 9. Felsenstein, J.: Evolutionary trees from DNA sequences: A maximum likelihood approach. Journal of Molecular Evolution 17(6), 368–376 (1981). https://doi.org/ 10.1007/BF01734359 10. Fey, M., Lenssen, J.E.: Fast graph representation learning with PyTorch Geometric. In: ICLR Workshop on Representation Learning on Graphs and Manifolds (2019), https://arxiv.org/abs/1903.02428 11. Fitch, W.M.: Toward defining the course of evolution: Minimum change for a spe- cific tree topology. Systematic Zoology 20(4), 406–416 (1971). https://doi.org/10 .2307/2412116 12. Francisco, A.P., Bugalho, M., Ramirez, M., Carriço, J.A.: Global optimal eBURST analysis of multilocus typing data using a graphic matroid approach. BMC Bioin- formatics 10, 152 (2009). https://doi.org/10.1186/1471-2105-10-152 13. Hickey, G., Dehne, F., Rau-Chaplin, A., Blouin, C.: SPR distance computation for unrooted trees. Evolutionary Bioinformatics 4, 17–27 (2008). https://doi.org/10.4 137/EBO.S419 14. Huber, P.J.: Robust estimation of a location parameter. The Annals of Mathemat- ical Statistics 35(1), 73–101 (1964). https://doi.org/10.1214/aoms/1177703732 15. Ioffe, S., Szegedy, C.: Batch normalization: Accelerating deep network training by reducing internal covariate shift. In: International conference on machine learning. p. 448–456. pmlr (2015). https://doi.org/10.5555/3045118.3045167 16. Jolley, K.A., Bray, J.E., Maiden, M.C.J.: Open-access bacterial population ge- nomics: BIGSdb software, the PubMLST.org website and their applications. Well- come Open Research 3, 124 (2018). https://doi.org/10.12688/wellcomeopenres.1 4826.1 17. Kapli, P., Yang, Z., Telford, M.J.: Phylogenetic tree building in the genomic age. Nature Reviews Genetics 21(7), 428–444 (2020). https://doi.org/10.1038/s41576 -020-0233-0 R. M. Castanheira et al. 18. Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. In: Interna- tional Conference on Learning Representations (ICLR) (2015), https://arxiv.org/ abs/1412.6980 19. Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: International Conference on Learning Representations (ICLR) (2017), https://arxiv.org/abs/1609.02907 20. Li, Y., Gu, C., Dullien, T., Vinyals, O., Kohli, P.: Graph matching networks for learning the similarity of graph structured objects. In: Proceedings of the 36th International Conference on Machine Learning (ICML). p. 3835–3845 (2019), ht tps://proceedings.mlr.press/v97/li19d.html 21. Mai, U., Sayyari, E., Mirarab, S.: Minimum variance rooting of phylogenetic trees and implications for species tree reconstruction. PLoS ONE 12(8), e0182238 (2017). https://doi.org/10.1371/journal.pone.0182238 22. Maiden, M.C.J., van Rensburg, M.J.J., Bray, J.E., Earle, S.G., Ford, S.A., Jolley, K.A., McCarthy, N.D.: MLST revisited: the gene-by-gene approach to bacterial genomics. Nature Reviews Microbiology 11(10), 728–736 (2013). https://doi.org/ 10.1038/nrmicro3093 23. de Oliveira Martins, L., Leal, É., Kishino, H.: Phylogenetic detection of recombi- nation with a Bayesian prior on the distance between trees. PLoS ONE 3(7), e2651 (2008). https://doi.org/10.1371/journal.pone.0002651 24. Robinson, D.F., Foulds, L.R.: Comparison of phylogenetic trees. Mathematical Biosciences 53(1–2), 131–147 (1981). https://doi.org/10.1016/0025-5564(81)900 43-2 25. Saitou, N., Nei, M.: The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular Biology and Evolution 4(4), 406–425 (1987). https: //doi.org/10.1093/oxfordjournals.molbev.a040454 26. Schliep, K.P.: phangorn: phylogenetic analysis in R. Bioinformatics 27(4), 592–593 (2011). https://doi.org/10.1093/bioinformatics/btq706 27. Bernardino da Silva, L., Frutuoso, G., Francisco, A.P., Vaz, C.: PhyloLib: A library of efficient algorithms for phylogenetic analysis (2026), https://github.com/phylo viz/phylolib, command-line application, INESC-ID / Instituto Superior Técnico. 28. Smith, M.R.: Information theoretic generalized Robinson–Foulds metrics for com- paring phylogenetic trees. Bioinformatics 36(20), 5007–5013 (2020). https://doi. org/10.1093/bioinformatics/btaa614 29. Sokal, R.R., Michener, C.D.: A statistical method for evaluating systematic re- lationships. University of Kansas Science Bulletin 38, 1409–1438 (1958), https: //w.sid.ir/paper/549615/en 30. Steel, M.A., Penny, D.: Distributions of tree comparison metrics—some new results. Systematic Biology 42(2), 126–141 (1993). https://doi.org/10.1093/sysbio/42.2. 126 31. Vaz, C., Nascimento, M., Carriço, J.A., Rocher, T., Francisco, A.P.: Distance-based phylogenetic inference from typing data: a unifying view. Briefings in Bioinformat- ics 22(3), bbaa147 (2021). https://doi.org/10.1093/bib/bbaa147 32. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y.: Graph attention networks. In: International Conference on Learning Representations (ICLR) (2018), https://w.chapterpal.com/s/vq6tnqa4/graph-attention-n etworks 33. Whidden, C., Matsen, IV, F.A.: Calculating the unrooted subtree prune-and- regraft distance. IEEE/ACM Transactions on Computational Biology and Bioin- formatics 16(3), 898–911 (2019). https://doi.org/10.1109/TCBB.2018.2802911 Learning Phylogenetic Tree Similarity with GNNs 34. Whidden, C., Zeh, N., Beiko, R.G.: Supertrees based on the subtree prune-and- regraft distance. Systematic Biology 63(4), 566–581 (2014). https://doi.org/10.1 093/sysbio/syu023 35. Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., Yu, P.S.: A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems 32(1), 4–24 (2021). https://doi.org/10.1109/TNNLS.2020.2978386 36. Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How powerful are graph neural networks? In: International Conference on Learning Representations (ICLR) (2019), https: //arxiv.org/abs/1810.00826