Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks

This paper studies whether a Graph Neural Network can approximate Subtree Prune and Regraft (SPR) distances between phylogenetic trees, whose exact computation is NP-hard. The authors release 864 trees inferred with UPGMA and Neighbor-Joining across four bacterial species, plus 388 labelled tree pairs. A Siamese Graph Isomorphism Network achieves about R² = 0.87 on a held-out in-distribution split and 0.90 ± 0.19 under stratified cross-validation. Transfer to unseen species is partial, at about R² = 0.37, while extrapolation to larger trees causes accuracy to collapse.