Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper contributes to the existing Bayesian phylogenetic VI literature with three novel methods which, in combination, lead to better accuracy, lower memory requirements, and faster computation speed when compared to existing VI methods in the space. We now discuss each of the authors' three novel contributions in isolation. 

SLANTIS, a method for generating proposal trees in the multifurcating tree space, is the first contribution. As reported, this method is orders of magnitude faster than existing methods for generating proposal trees, taking far fewer iterations to approximate the relevant expectations than existing methods.

JC sampler uses the computed matrix of expected mutations across branches to sample branch lengths exactly according to the Jukes Cantor model. Sampling branch lengths directly from the underlying substitution model instead of from an arbitrary prior just makes sense, and frankly I'm surprised that this is the first paper to do so.

VaiPhy is the full variational inference method developed in this paper, utilizing both SLANTIS and JC sampler. VaiPhy enjoys significantly lower computational times than existing VI methods, while consistently producing better log-likelihood scores. Additionally, VaiPhy includes an auxiliary variable for ancestral sequences, which helps pave the way for potential future applications which may want to include ancestral data, such as that of fossils.

Bayesian phylogenetic VI is a new and growing methodology, so, while the methods in this paper do not produce the best results among all phylogenetic inference methods, they provide significant contributions towards the development of VI in phylogenetics.
strengths_and_weaknesses: ## Originality

While the classical VI methodology that underlies this paper's work is nothing new, SLANTIS and JC sampler are both completely novel methods. Additonally, ancestral sequence data has been included in previous Bayesian methods as part of the input, not just as auxillary variables. However, VaiPhy is the first VI-based method to take ancestral data into consideration, even if only probabilistically. Thus, this paper contributes a significant body of original material towards the improvement of VI-based phylogenetic inference.

## Quality

The overall quality of the methods presented is very high. Further details are contained in other relevant sections.

## Clarity

The methodology is explained very well; as someone familiar both with phylogenetics and variational inference I felt that I had a very good understanding of the mechanisms behind VaiPhy on my first read, which is not an easy task for a paper on something as computationally heavy as VI.
    
The background section of the paper is devoid of any explanation of sequential Monte Carlo or conditional sequential Monte Carlo, which is a barrier for readers who are interested in the potential phylogenetic applications of the work, but unfamiliar with these concepts. Additionally, while SMC is at least given an introduction, CSMC is not (in fact the word "conditional" does not appear in the paper). While the paper is no doubt intended to appeal to an audience which is already familiar with variational inference, its applications are in phylogenetics, so these concepts should still be given an adequate introduction and brief explanation.

## Significance

VI is a developing field in phylogenetic inference. I do not know whether VI will end up leading the cutting edge in phylogenetics, but, irregardless, this paper's contributions certainly make that reality seem more possible.
questions: Section 3.4 states that "the framework learns its parameters and distributions by maximizing the ELBO [... but] the IWELBO offers a tighter lower bound" and "using SLANTIS and the JC sampler we can easily evaluate our framework using the IWELBO." This statement is confusing: the former states that the ELBO is used in the framework, but the latter seems to imply that the IWELBO is used instead; which is true?

Have you considered utilizing ancestral sequence data (e.g. from fossils) as inputs into the method, instead of featuring them exclusively as auxillary variables?

Why were convergence statistics for SLANTIS not included? When proposing a method which proports to require orders of magnitude fewer iterations than existing methods, convergence seems an important attribute to investigate.

The method improves on memory requirementns of previous VI implementations by utilizing significantly fewer learnable parameters, but what amount of memory does the method actually use at runtime? I.e. how many GiB of ram does the method utilize? This question is very relevant to the current limitations of the method.
limitations: Of all phylogenetic tree inference methods, this is neither the fastest nor the most accurate. The authors very honestly admit this, and though this is a limitation, it is should _not_ be considered a weakness of the paper, as  VI in Bayesian inference is still in its infancy, while their competitor MrBayes is comparatively a full grown adult. That being said, MrBayes should not have been excluded from the wallclock time vs. number of cores plots, as how far modern VI methods lag behind MrBayes is not irrelevant.

A very typical assumption to make in phylogenetic likelihood computations is independence of branch lengths. Computations without this assumption are rarely feasible. This method calculates branch lengths in isolation, though, without respect to topology, which I expect is far too much of a simplifying assumption.

Log-likelihood values for the method (as well as its competitors) are provided on 7 real-world datasets, but this metric is not actually very good for evaluating the performance of phylogenetic inference. Better log-likelihood scores do not _necessarily_ equate to a better estimate of the underlying tree, especially when 1) many simplifying assumptions are made in likelihood calculations, and 2) underlying models (such as the substitution model, JC in this case) may very well be misspecified. A better way to evaluate the performance of these methods is through a simulation study where the ground truth trees are known, and prediction accuracy can then be calculated via the Robinson-Foulds distance.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Inferring the posteriors of phylogenetic trees is critical to evaluating uncertainty in tree inference. The most popular method for this is MCMC; however, in some situations effective sampling of the combinatorial tree space can be difficult, and MCMC does not return (straightforwardly) densities for individual trees, meaning that it can have difficulties representing diffuse posteriors. Variational inference, in principle, can solve these issues while decreasing the computational cost of inference. However current methods require lots of resources for training due to the need to perform automatic differentiation.

In this paper, the authors aim to improve the efficiency of variational inference. They make a number of contributions to do so:
1) They introduce an efficient algorithm to sample trees conditional on branch lengths, substitution probabilities, and sequences at every vertex.
2) For a Jukes-Cantor substitution model, they introduce an algorithm to sample branch lengths given the topology of the tree and sequences at every vertex.
3) They introduce an algorithm for iteratively updating the posterior of the sequences at each vertex of the tree, the tree topology, and the branch lengths. They calculate the natural gradients for this algorithm to make training as efficient as possible.
4) Finally, they also combine 1 and 2 to create a more efficient proposal for a tree sampling procedure based on stochastic monte carlo (SMC).

They demonstrate the efficiency of their method, taking substantially less time than another variational inference method and some sampling methods. They also demonstrate that their method in 4 indeed increases the efficiency of sampling.
strengths_and_weaknesses: Strengths:
1) The paper proposes an extremely efficient method for variational inference of phylogenetic trees.
2) In the process of devising this method, the authors propose a new method to sample trees topologies and brnch lengths that is of independent interest.
These points make it a substantial contribution to phylogenetic inference

Weaknesses:
1) It is obvious that classical variational inference methods are extremely inefficient (when first reported these methods were shown to be more efficient that MCMC based on "number of iterations needed to reach a minimum accuracy", however, as iterations come with different computational costs, the method the authors used to measure efficiency here is more sound.) However the number of iterations to run the classical method in this case seem to be arbitrary, or selected to be very large in the original publication to get to convergence. It would be more fair to compare compute time to log likelihood achieved.
This concern is more dire in the comparison between CSMC methods, the author's proposed method and MCMC - although not strictly necessary to demonstrate a contribution as one obtains different things from each methods.
2) I am not 100% on the likelihood evaluations (see questions below).
questions: 1) For the transformed branch length, of course when there are many sites and branch lengths are long this won't matter, what do you do when p<1/4? Do you account for p's that cannot give rise to valid branch lengths when calculating probabilities?
2) Why did you compare to VCSMC instead of VNCSMC, the improved model? And did you perform variational inference on the parameters in phi-CSMC?
3) Did you use the same branch length priors for all models (I believe other models have exponential branch length priors by default)?
4) The likelihood estimation methods used for the VI and SMC methods are biased downwards and so not directly comparable. This lower bound is still useful to report for the SMC methods as it demonstrates more efficient sampling when it is higher, but this isn't a fair comparison to VSMC I believe which also optimises the parameters of its branch length priors and substitution matrix. However this isn't a fair comparison to MCMC which doesn't have a downward-biased marginal likelihood estimate. In other phylogenetics VI papers, samples are usually taken from the VI methods and their marginal likelihood calculated unbiasedly just as with the samples from MCMC. This could also be done for your method I believe, allowing evaluation without the inference of the sequences at internal nodes affecting the bias.

limitations: 1) The mean field approximation to internal nodes may severely limit the ability of this model to fit certain posteriors.
2) This method requires a very efficient way to sample branch lengths, which the authors demonstrate exists for the JC model, but may be more difficult to devise for more complicated substitution models.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors infer the posterior distribution over phylogenetic trees given only the leaves of the tree. To do so, the authors propose a method composed of three elements. A first one (VaiPhy) is a mean-field VI algorithm that returns the posterior distribution of the tree, internal vertices and set of branch lengths. VaiPhy uses the second element (JC sampler) to sample branch lengths and the third element (SLANTIS) to sample trees.  SLANTIS enables them to sample the branches of the tree one after the other, with probabilities proportional to the total weight of the maximum spanning tree. The JC sampler gives access to a normalised distribution over branch lengths, using the Jukes-Cantor model.

The authors compare VaiPhy to several other models, baselines and a VaiPhy-parametrised CSCM, using the IWELBO as metrics and wall-clock runtime. The authors show that among their proposed variants, VaiPhy-parametrised CSCM give the best results. While it is not better than MrBayes or VBNI-NF, it is significantly faster than VBNI-NF.

strengths_and_weaknesses: ### Originality
The methods proposed by the authors is novel as it combines and adapts several techniques to a specific problem, which is phylogeny inference in single-cell data. 

### Significance
Phylogeny inference is an important problem and is in need of approaches that scale to the size of current single-cell datasets for example. The authors do a step in this direction. However, MrBayes SS seems to both perform better and is faster than the proposed approach.

### Clarity 
The paper is overall well-written, apart from a few sentences / typos that are mentioned at the next section. 

### Quality
While the overall quality of the paper is good, including maths and structure of the paper, I think that some points need to be better explained. They are the subject of the next section. 


questions: I believe that the paper is overall well-written and structured. I have nevertheless a few clarification questions concerning the method and questions regarding the benchmark. Additionally, the method MrBayes SS seems to perform better than the proposed approach. Therefore, I think that the work is not ready for publication at NeurIPS in its current form but I would be happy to increase the score if the following questions were answered.

*****



### VaiPhy
One step in VaiPhy is to compute the expected number of mutations of an edge. The authors claim that the maximum number of mutations between two vertices is the number of sites. I believe that it is possible to have unobserved mutations, for example when the time step between two vertices is large compared to the mutation rate. I would be interested to know if this is something the authors are accounting for, and how or why not if it is not taken into account. 

VaiPhy seems to consider that the nucleotides are independent. However, it is possible that some mutations co-occur or are mutually exclusive. Could these first order interactions be taken into account in VaiPhy?

### SLANTIS
The separation between previous work and proposed approach is unclear for SLANTIS. The authors could perhaps make a better distinction between the two in the document.

Due to the probabilistic nature of SLANTIS, is it possible that the leaves are not always all included in the reconstructed tree? If yes, how does this affect the performance?

### Parameterized CSMC
I believe that using VaiPhy to parameterize CSMC instead of using directly VaiPhy is impactful for a small number of taxa but could be less so for larger number of taxa. Have the authors compared the two models when the number of taxa is larger than 100?

### Experiments
I think that the experiments are interesting but I would like to better understand how the proposed approach performs and scales in terms of number of taxa or sites for example compared to the baselines. 

Figure 1, which compares the number of mutations with branch length, is an interesting plot. I was wondering if it would be possible to also evaluate the reconstructed tree. This could be done on simulated data where the tree (and sequences of the ancestors) are known but only the leaves are used for phylogeny reconstruction. 




**Minor comments**
- Line 4: change the word formidable for something less positive 
- Line 14: "the, to the best" -> phrasing to change
- Line 22, 102: "phylogentic" -> phylogenetic
- Line 76: define CSMC
- Equation 6: define the subscript -i
- Equation 7: the right hand side is missing the dependency in T
- Equation 9: it is worth repeating what $Q_{\alpha\beta}$ is
- line 146: Algorithm B -> algorithm 3
- The sentence line 153-154 is very unclear, it is worth reformulating it.

---------
In light of the authors' response to the reviewers, I am in favor of accepting the paper and increase the grade to 6.


limitations: I think that the authors could better address the limitations of their work in a few sentences.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces two methods for inference of phylogenetic trees from sequence data. Taking a variational inference approach, the VaiPhy method is constructed using two new samplers: SLANTIS and JC. The ability to estimate the expected number of mutations over edges leads to a variant of the CSMC method denoted \phi-CSMC. The methods are experimentally tested and compared to state-of-the-art methods on 7 datasets.
strengths_and_weaknesses: Strengths:
* introduction of several new techniques for variational inference in phylogenetic analysis
* important, high impact application area
* well-presented and technically sound paper (as far as I can evaluate)
* while the two methods only outperform existing methods in some cases, the techniques show a path to future advances with potential to significantly improve the state-of-the-art

Weaknesses:
* variational inference has been used before for phylogenetic analysis, so in that sense the underlying idea is not fundamentally new. However, as far as I can judge, the proposed methods still presents significant novelty and originality
questions: * The sentence "VaiPhy is remarkably much faster than all other methods for all numbers of cores (except for
278 MrBayes in special cases, see further down)" seems a little strong when it is followed by "MrBayes is the fastest algorithm when allowed multiple cores." Can the first sentence can be expressed more clearly?
limitations: yes
review_title: null

Meta-review: metareview: The authors propose a novel variational inference method for phylogenetic inference with a specific focus towards improving the speed of variational inference. The reviewers agree that the paper makes significant contributions to an important problem. The authors are encouraged to take the reviewer feedback carefully in preparing the next version of the manuscript. 
confidence: Certain
Decision: Accept