PhyloVAE: Unsupervised Learning of Phylogenetic Trees via Variational Autoencoders

Tianyu Xie, Harry Richman, Jiansi Gao, Frederick A. Matsen Iv, Cheng Zhang

TL;DR

PhyloVAE is the first deep generative framework that applies Variational Autoencoders (VAEs) to phylogenetic tree topologies. By mapping discrete, complex evolutionary trees into a continuous latent space, it enables high-resolution visualization and representation learning while achieving massive training and generation speedups via a non-autoregressive architecture.

What Problem Does This Paper Address?

Phylogenetic trees describe the evolutionary relationships between biological entities. However, analyzing collections of these trees (such as posterior samples from Markov Chain Monte Carlo runs) is notoriously difficult. The space of tree topologies is discrete, non-Euclidean, and explodes combinatorially—for $N$ leaf nodes, there are $(2N - 5)!!$ possible unrooted tree shapes.

Traditional methods rely on calculating pairwise distances between trees and projecting them onto a 2D plane using Multidimensional Scaling (MDS). This approach suffers from two major flaws:

  1. Poor Resolution: Distinct groups of trees often overlap heavily in the visualization, obscuring true structural differences.
  2. No Inverse Mapping: You cannot pick an arbitrary point on an MDS plot and translate it back into an actual tree topology.

Recent autoregressive models (like ARTree) offer high-resolution density estimation but are computationally expensive and lack representation learning capabilities. PhyloVAE bridges this gap by providing a unified framework for both representation learning and fast generative modeling.

Methods

PhyloVAE adapts the standard VAE architecture to the unique constraints of bifurcating tree graphs through three core components:

  1. Linear-Time Encoding Mechanism ($O(N)$): To bypass the quadratic complexity of previous graph-to-vector methods, the authors introduce a bijective encoding mechanism. It uses a "decomposition loop" to strip leaf nodes sequentially and record edge decisions, and a "reconstruction loop" with a smart indexing strategy to map trees to integer vectors (and vice-versa) in linear time.
  2. Non-Autoregressive Generative Model (Decoder): Instead of generating trees step-by-step, the decoder factorizes the probability of edge decisions so they are conditionally independent given the latent variable $z$. This allows for highly parallelized, fast topology generation. A mask vector is applied to ensure that the generated vectors always correspond to valid tree structures.
  3. Collaborative Inference Model (Encoder): The encoder uses a Graph Neural Network (GNN) built on learnable topological features (minimizing Dirichlet energy) to map a discrete tree topology into a low-dimensional continuous Gaussian latent space.
Figure 2: The decomposition loop and reconstruction loop for encoding the tree topology with leaf nodes X = {A,B,C,D,E,F} in Figure 1. Starting from the tree topology in the upper left, we remove the pendant edges f6, f5, f4 (associated with the leaf nodes F, E, and D) sequentially, and record edge decision e5, e4, e3. Then starting from the three-leaf tree topology in the lower right, we add back f4, f5, f6 and index these nodes (except for the root) sequentially. The resulting encoding vector is (3, 7, 5), which are the indexes associated with e3, e4, e5.

Datasets

The authors evaluated PhyloVAE on both synthetic and real-world biological datasets:

  • Simulated Data: All 15 possible five-leaf tree topologies, and a mixture of three peaked distributions comprising all 10,395 eight-leaf topologies.
  • Real Phylogenies:
  • Mammal Gene Trees: 44 leaves across 5 different genes with varying sequence lengths (1000, 2000, and 5000) simulated from early placental mammal data.
  • Rabies Genomes: 10,000 posterior tree topologies derived from 290 rabies genomes analyzed via BEAST software.
  • Fossil Datasets: 6,000 tree topologies describing 42 types of Paleozoic crinoids.
  • Benchmark Datasets (DS1–DS8): Standard benchmark sequence datasets containing 27 to 64 eukaryote species, widely used for testing tree topology density estimation.

Key Insights and Ideas

  • Generative Objectives Improve Representations: The main "aha" moment is that forcing the model to reconstruct the tree from the latent space (the generative task) is precisely what forces the latent space to learn high-resolution features. This prevents the overlapping issues seen in distance-based MDS plots.
  • Continuous Space, Discrete Output: By pairing a continuous latent space with a masked discrete decoder, PhyloVAE allows researchers to smoothly traverse the latent space and watch one tree topology continuously deform into another.
  • Parallelization via Factorization: Moving from an autoregressive architecture to a factorized conditional decoder unlocks massive parallelization, drastically lowering the computational footprint of phylogenetic deep learning.

Key Results

  • Superior Visualization Resolution: When mapping mammal gene trees, PhyloVAE cleanly separated different gene groups in the latent space. In contrast, traditional MDS plots caused the groups to collapse and overlap near the origin.
Latent space representations of mammal gene trees and rabies phylogenies, comparing PhyloVAE's clear clustering against MDS overlapping.
  • Comparable Accuracy, Drastic Speedups: On the benchmark datasets DS1–DS8, PhyloVAE achieved comparable (and sometimes superior) KL divergence to the ground truth compared to the state-of-the-art ARTree model. Crucially, it did so with a massive reduction in both training and generation times.
Runtime comparison showing significant speedups in both training and generation for PhyloVAE compared to ARTree.

Limitations and Future Work

While PhyloVAE represents a major step forward, some limitations remain:

  • Fixed Leaf Sets: The current model assumes that all trees in the collection share the exact same set of leaf nodes (taxa). It cannot naturally handle trees with missing or varying species.
  • Latent Capacity Constraints: While a 2-dimensional latent space ($d=2$) is excellent for visualization, it suffers from reduced capacity on highly complex datasets. Increasing the dimension to $d=10$ restores accuracy but sacrifices direct visual interpretability.

Future work includes extending PhyloVAE to handle trees with differing leaf sets and applying the framework to downstream tasks like phylogenetic placement and Bayesian phylogenetic inference.

Summary updated

Abstract

Learning informative representations of phylogenetic tree structures is essential for analyzing evolutionary relationships. Classical distance-based methods have been widely used to project phylogenetic trees into Euclidean space, but they are often sensitive to the choice of distance metric and may lack sufficient resolution. In this paper, we introduce phylogenetic variational autoencoders (PhyloVAEs), an unsupervised learning framework designed for representation learning and generative modeling of tree topologies. Leveraging an efficient encoding mechanism inspired by autoregressive tree topology generation, we develop a deep latent-variable generative model that facilitates fast, parallelized topology generation. PhyloVAE combines this generative model with a collaborative inference model based on learnable topological features, allowing for high-resolution representations of phylogenetic tree samples. Extensive experiments demonstrate PhyloVAE's robust representation learning capabilities and fast generation of phylogenetic tree topologies.
BibTeX
@inproceedings{xie2025phylovae,
  author = {Tianyu Xie and Harry Richman and Jiansi Gao and Frederick A. Matsen IV and Cheng Zhang},
  title = {{PhyloVAE: Unsupervised Learning of Phylogenetic Trees via Variational Autoencoders}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=Z8TglKXDWm},
}
Figure