PhyloVAE: Unsupervised Learning of Phylogenetic Trees via Variational Autoencoders

Thanks for your constructive feedback! Here are our responses.

W1: It is appreciated that it is clearly stated that the inputs to the encoder are collections of topologies. (...)

Response to W1: Thanks for your suggestion! First, we'd like to clarify that the collections of tree topologies as inputs to PhyloVAE are for representation learning tasks, where these collections are just the data sets whose (low-dimensional) representations are of interest (e.g., for visualization). In [1] and other variational approaches for Bayesian phylogenetics, a collection of pre-computed tree topologies is also required. However, it is used for subsplit support estimation in [1], which is essential for the parameterization of SBNs. In fact, PhyloVAE can also be used for variational Bayesian phylogenetic inference. Similarly to ARTree, PhyloVAE naturally specifies a family of distributions over the entire tree topology space, without requiring pre-computed tree topologies for support estimation. Therefore, we do not need to investigate the efficiency of support estimation as in [1: Figure 5]. One advantage of these support-free VI methods for Bayesian phylogenetics is that they can be applied when support estimation becomes challenging (e.g., diffuse posteriors as discussed in [1] as well). When support estimation can be done efficiently (e.g., good collections of pre-computed tree topologies are available/easy to obtain, using methods suggested in [1]), previous methods that require support estimation can also work well. We will clarify this in our revision.

W2: On the same topic, in Sec. 5.2 the topologies are gathered from a 1 milion MCMC run, (...)

Response to W2: The choice of 1 million simply follows the setting in [Hillis et al., 2005] who considered the same experiment. We have clarified this in our revision.

W3: The collection of trees are tuples of the topologies and their corresponding weights. The weights are then in a footnote described to be the frequency of the topology (right?). Then in all experiments, the weights are explicitly mentioned to be uniform. Why is this? Is a topology never sampled more than once in the pre-processing stage? What would happen if the trees were weighted by scores obtained, for instance, from MrBayes? Or simply the Felsenstein likelihood of the topology, normalized over all samples.

Response to W3: Trees from MrBayes runs can be sampled more than once. They (potentially duplicated) are assigned with uniform weight first, and then the duplicated trees are merged and re-assigned with weights proportional to the number of duplicated trees. For ease of description, we do not describe the merging operation explicitly. In a word, the actual weights of unique trees are indeed the empirical frequencies.

W4: Recently there have been works for applying mixtures of variational distributions (...)

Response to W4: Thank you for providing these related works. We will reference these works in our revision.

W5: There is a clash of notations $w$ for notating both internal node connections in Sec. 3.2 and the weights of the tree topologies.

Response to W5: Thanks for the nice catch! We will use different notations.

W6: I would be good to disambiguate the proposed method to other tree-based VAEs (...)

Response to W6: Although [5,6,7] contain "tree" and "VAE" in their titles, they consider a tree-shaped prior distribution or hierarchical latent variable structure. These papers do not consider modeling any graph or tree objects and thus are clearly distinct from our PhyloVAE. We have clarified this in our revision.

Q1: Relating to the references provided regarding mixtures of variational distributions, I am wondering if your proposed method could benefit from the mixture techniques provided in [2,3,4]?

Response to Q1: For variational inference, the mixture models indeed provide a more powerful variational distribution. Therefore, we can expect improvement in approximation accuracy if applying mixture techniques to PhyloVAE. Note that PhyloVAE itself can be viewed as a mixture model with infinitely many components.

Q2: Is Algorithm 1 parallellizable on a GPU? Can you use batches of tree topologies during training?

Response to Q2: The answer is yes. Algorithm 1 is parallelizable on a GPU.

Thanks for your follow-up questions! Here are our responses:

Response to W1 Thanks for the follow-up question. PhyloVAE mainly aims to learn representations of a pre-given data set of tree topologies, no matter how they are collected. These data sets often come from phylogenetic analysis softwares such as MrBayes and BEAST, but they can also come from observations, open-source data sets, and other biological softwares, as long as they are of scientific interest. What we want to emphasize is that the source of data, the parameters/proposals of the software, etc, are orthogonal of PhyloVAE's task and will not affect the effectiveness of PhyloVAE. (Even if a poor proposal is configured, PhyloVAE is still able to diagnose the underlying divergence of MCMC run, see section 5.2) We added these discussions to footnote 2 on page 3 in our revision.

Response to W2 To assess the convergence of MrBayes runs, we report the ASDSF at the 1,000,000-th iteration. We see all of these runs have an ASDSF less than 0.01, indicating the underlying convergence. We have clarified this in Section 5.2.

Table: ASDSF of MrBayes run at the 1,000,000-th iteration (seqlen=1000)

Response to W3 Thanks for this suggestion. We have modified the line 157 accordingly.

Response to Q1 The marginal probability of tree topology $\tau$ given by PhyloVAE takes the form $p_\theta(\tau)=\int_{\mathbb{R}^d}p_\theta(\tau|z)p(z)dz = \lim_{n\rightarrow\infty}\frac1n \sum_{i=1}^n p_\theta(\tau|z_i),\; z_i\sim p(z)$. Here the prior $p(z)$ can be viewed as a continuous mixing distribution, leading to a mixture model with infinitely many components.

Please feel free to let us know if you have any further questions!

Thanks for your careful review. Here are our responses to your concerns.

(1) to be convincing, the paper should show a case where ARTree is really too slow for being practical.

Response to (1): Please see Figure 5 for computational times. We want to clarify that although it costs only several seconds for ARTree per 10 iterations, the total training process contains 200,000 iterations! The total training time for reproducing the results in Section 5.3 is reported in the following Table. We see that it costs more than 100 hours to train ARTree on DS7 and DS8.

Table: Total training time (hours) of ARTree and PhyloVAE in Section 5.3.

(2) The experiments reported take on the order of seconds or less than a minute to train, so one wonder if the gain in computing power is so useful, if that would be at the expense of worse modeling of the tree distributions.

Response to (2): Figure 5 reports the training time of 10 iterations, but the total training process requires 200,000 iterations. The total training time is reported in the above table, where we see that it costs more than 100 hours to train ARTree on DS7 and DS8.

(3) Although two different capacities were tested for PhyloVAE (dimension 2 and 10), that was not the case for ARTree, making it unclear if ARTree could have obtained a better KL divergence with a different capacity.

Response to (3): Firstly, we'd like to emphasize that we do not expect an accuracy gain upon baselines, as the major advantages of PhyloVAE are representation learning ability and fast computation speed. Moreover, we tried to use enlarge the ARTree by employing more layers ($L=4$) in message passing. Although $L=4$ achieves a better KL on DS1, it can lead to worse results on DS3 and DS4, which can be attributed to the increased training difficulty or the potential over-fitting problem.

Table KL divergence with different number of layers in the message passing step of ARTree

(4) In terms of modeling power, assuming independence of the actions seems very strong. It is not clear that it will work well for other tree distributions not tested in this paper.

Response to (4): We would like to emphasize that we assume conditional independence instead of independence among actions. Combining a mixing prior distribution $p(z)$ and a conditionally independent $p(s(\tau)|z)$, PhyloVAE has enough capacity to model a complicated marginal distribution $p(s(\tau))$. To see this, consider a standard VAE for image data, where $p(z)$ is standard Gaussian, and $p(x|z)$ is a conditional Gaussian with diagonal covariance matrix, but this can model complicated image data.

About the additional tree distributions, DS1-8 are the most commonly considered benchmark in phylogenetics [1,2,3,4,5]. Moreover, it has been shown in [6] that DS1-8 have all sorts of strange aspects, including multiple modes separated by a difficult-to-cross valley, and duplicated substructures caused by lack of resolution in the data. Therefore, we can expect PhyloVAE to work for other distributions if it works for DS1-8. We will clarify this in our revision.

[1] Zhang, C. and Matsen IV, F. A. "Variational Bayesian phylogenetic inference." International Conference on Learning Representations (2019).

[2] Koptagel, Hazal, et al. "Vaiphy: a variational inference based algorithm for phylogeny." Advances in Neural Information Processing Systems 35 (2022): 14758-14770.

[3] Mimori, Takahiro, and Michiaki Hamada. "GeoPhy: differentiable phylogenetic inference via geometric gradients of tree topologies." Advances in Neural Information Processing Systems 36 (2023).

[4] Xie, T. and Zhang, C. "ARTree: A deep autoregressive model for phylogenetic inference." Advances in Neural Information Processing Systems 36 (2023).

[5] Zhou, Mingyang, et al. "PhyloGFN: Phylogenetic inference with generative flow networks." arXiv preprint arXiv:2310.08774 (2023).

[6] Chris Whidden and Frederick A Matsen IV. Quantifying MCMC exploration of phylogenetic tree space. Systematic Biology, 2015.

Thanks for your careful review! Here are our responses to your concerns.

W1: Need for Generalizability Testing Across Datasets

Response to W1: Like general VAE models, in the current format, we do not expect PhyloVAE to provide universal representation across distinct datasets, as the models are trained specifically for each dataset. It's like doing a PCA on a data set, where the coefficients of principle components are also dataset-specific. However, we admit that exploring the generalization ability of representation models is valuable and will consider this in future works (maybe a sequence embedding scheme is needed).

W2: Lack of Comparison with True Phylogenetic Trees

Response to W2: We would like to clarify that all the phylogenetic trees are from statistical inference, instead of biological experiments. In fact, the underlying “biological” phylogenetic trees are never available except in some very unusual circumstances (e.g., directed evolution experiments). As a submission to an AI conference, this paper understands phylogenetics as a computational and statistical problem, instead of a biological problem. From this perspective, we construct the "ground truth" posterior trees by running sufficiently long-run MrBayes, which is a common practice in this field. Afterward, we compute the KL divergence from PhyloVAE to this ground truth, as reported in Table 1, to verify that PhyloVAE indeed generates good posterior trees.

To provide an in-depth analysis between PhyloVAE and the ground truth, we added the scatter plot between probability estimates and the ground truth, in Figure 13. We see that PhyloVAE indeed provides good estimates for these high-quality ground truth trees.

W3: Marginal Improvements in Performance Metrics

Response to W3: Thanks for pointing this out. We agree that PhyloVAE shows marginal improvement upon ARTree in terms of KL divergence, however this is not the central advance reported here. However, the superiority is summarized in the following two aspects:

• As specifically described in the Introduction, the main focus of PhyloVAE is the representation learning, and PhyloVAE is the first deep model to do this. We also conducted extensive experiments to support this point.
• PhyloVAE shows a great improvement in terms of computational efficiency, as shown in Figure 5. This is the most critical advantage of PhyloVAE for generative modeling.

Q1: How does PhyloVAE perform when trained on one set of datasets (e.g., DS1-DS4) and tested on a distinct dataset like DS5?

Response to Q1: Thanks for this insightful question. We have to admit this is not possible for our current model setting. Please find a more detailed explanation in our response to W1.

Q2: Has PhyloVAE been directly compared to real, experimentally derived species trees?

Response to Q2: Please see our response to W2. In Figure 13, we provide an additional comparison between the tree probability estimates of PhyloVAE and the ground truth. This ground truth is statistically inferred from a long-run MrBayes, which is a common practice in this field.

Q3: While PhyloVAE offers efficiency gains, it appears not to outperform traditional models like ARTree in terms of accuracy metrics (...)

Response to Q3: About the minor improvement of KL, we would like to emphasize that the main advantages of PhyloVAE lie in representation learning ability and computational efficiency. Please see our response to W3 for a detailed explanation.

To show the trade-off between effectiveness and efficiency, we provided an additional ablation study on $d$ and $K$ in Table 3 in our revision. We also put it here for your ease. We see that increasing $K$ can generally improve the approximation accuracy, while sometimes a large $d$ may increase the training difficulty and lead to overfitting.

Table: KL divergence on DS1

Table: KL divergence on DS2

Table: KL divergence on DS3

Table: KL divergence on DS4

Q4: Where is the hyper-parameter experiment, e.g., how to decide the parameters $d$, $K$, $L$, Iterations, and batch size?

Response to Q4: Thanks for this question. We explain the choice of hyper-parameters as follows:

• the latent dimension $d=2$ is for ease of visualization; $d=10$ serves as an ablation study with large model capacity.
• $K=32$ is a just experiential choice, which is fixed across all experiments.
• The number of layers $L=2$ and iterations simply follows ARTree, the most relevant baseline.
• Number of iterations and batch size are kept the same as SBN and ARTree.

To more comprehensively evaluate the effect of $d$ and $K$, we provided an additional ablation study in our revision (see Table 3). We also put it here for your convenience. We see that increasing $K$ can generally improve the approximation accuracy, while sometimes a large $d$ may increase the training difficulty and lead to overfitting.

Table: KL divergence on DS1

Table: KL divergence on DS2

Table: KL divergence on DS3

Table: KL divergence on DS4

Thanks for your constructive feedback! We addressed your concerns as follows.

W1: Some important assertions are unclear (...)

Response to W1: Thanks for your question. For the argument of high-resolution representations, please refer to Figure 4. In Figure 4, we see that PhyloVAE gives representations that are clearly separated, and subgroups are observed within each group. In contrast, the representations from MDS show a merging tendency among groups, and each group is latently represented as an isotropic disc area, lacking the subgroup information. This is why we say PhyloVAE can provide high-resolution representations compared to distance-based methods.

In the introduction, we did mention that the effectiveness of these distance-based methods (not PhyloVAE) heavily depends on the choice of distance metric and can sometimes exhibit counterintuitive behaviors. [Kuhner & Yamato, 2015] give an example of such counterintuitive behaviors where distanced-based methods can provide somewhat discordant results when analyzing trees with different levels of similarity. Similar drawbacks of distance-based methods are also discussed in [Kendall & Colijn, 2016].

W2: The specific application scenarios described in the manuscript are vague (...)

Response to W2: Just like the general VAE framework, PhyloVAE can perform generative modeling and representation learning simultaneously. We think this is a nice property of our method.

Although the main purpose of PhyloVAE is indeed for representation learning of phylogenetic topologies, we want to emphasize it is the generative modeling perspective of PhyloVAE (inherited from variational autoencoders) that enables more capacity for high-resolution representations. More specifically, PhyloVAE tries to learn the overall distribution of trees instead of just maintaining pairwise distances between them as typically done in distance-based methods. This generative modeling perspective forces PhyloVAE to learn high-resolution representations to retain more distributional information (see Figure 4 for an example). Moreover, the generative modeling nature also allows PhyloVAE to map the latent space back to the tree space, which is impossible for previous distance-based approaches. This can be used in various tasks such as designing novel tree topology proposals from the latent space for more efficient exploration in the tree space. For generative modeling, PhyloVAE can be used as an alternative to ARTree, which is much faster to train and sample from, while maintaining the approximation accuracy. We will add these discussions to our revision.

W3: This paper mentions the limitations of (...)

Response to W3: Thanks for your question! The main setting for the PhyloVAE model that makes it better at representation learning and visualization than distance-based and density-based methods is that it combines representation learning and generative modeling in a satisfying and useful way, which is inherited from variational autoencoders (VAE). As mentioned in our response to W2, the generative modeling perspective forces PhyloVAE to learn high-resolution representations that retain the distributional information of tree topologies, which contain more information than the pairwise distances used in distance-based methods. Compared to density-based methods, PhyloVAE has a latent space that allows representation learning of tree topologies, while the density-based method only provides estimated densities that contain no structural information of the tree shape distributions. We expect models/methods that share the same hybrid settings of latent representation and generative modeling to perform well in representation learning and visualization.

W4: More minor issues could be clarified

Response to W4:

(a) Different software choices may lead to samples with different accuracies. This is an independent task from representation learning. We only make an effort to show that PhyloVAE can give reliable representations of whatever training samples are given.

(b) There is only a constraint $\sum_i w_i = 1$ without other priori constraints. This is just an empirical distribution, defined by a weighted sum of Diracs.

(c) We select only 5 and 8 because the posterior distribution can be freely designed and analytically computed (This is impossible for more than 8 leaves which can have more than $10^6$ different trees). For larger data sets, please see the results in Sections 5.2 and 5.3.

(d) To plot Figure 3 (left), we (i) select $11\times 11$ grid points on the square $(0,1)^2$ (These grid points are the quantiles of the standard Gaussian). (ii) For each grid point $(x,y)$, we compute the tree topology encoding vector $s(\tau)$ through the generative model $p_\theta(s(\tau)|(x,y))$. (iii) Convert $s(\tau)$ to $\tau$ through the reconstruction loop (Algorithm 3). (iv) Plot $\tau$ on the position $(x,y)$.

(e) Yes, they represent the same variable.