MDTREE: A Masked Dynamic Autoregressive Model for Phylogenetic Inference

The paper's experimental evaluation is hindered by several aspects. Firstly, the parameter settings for baseline methods are not well-documented, potentially impacting the strength of reported performance. Secondly, the absence of publicly available code limits reproducibility and hinders independent verification of the results. Additionally, the methods compared in each table are inconsistent, lacking clear explanations for these choices. For example, while MrBayes is included in Table 2, it is absent from Table 1, raising questions about the rationale behind these decisions.

While the paper introduces a novel approach to phylogenetic tree inference, the literature review in the introduction appears to conflate different concepts. For instance, the discussion of Solis-Lemus & Ané, 2016 and Zhang et al., 2018, which focus on network inference from gene trees/multiple sequence alignments under the multispecies network coalescent model, seems to be mixed with the concept of gene tree inference from sequence data, the primary focus of the proposed MDTree method. A clearer distinction between these approaches would enhance the paper's clarity and contextual understanding.

Besides the major concerns, below are some minor concerns.

Figure 1: left and right are opposite. Run time unit is missing.

The name of the proposed method is not consistent in tables. E.g., Table 1: MDTree, Table 2: Ours.

There are certain weakness about this study. The complex architecture and multi-layered optimization requirements may limit the practical application. It is worth to consider about pack the framework into a user friendly package or online service. This will not only help people who are interested in this study, but also increase the impact of this impressive work. There are some details about the method and the evaluation metrics are ignored in the paper, such as how does DON determine the node order based on genomic embeddings? What is the impact of sequence divergence and species evolutionary relationship distance to the node order and inferred phylogenies? Why generating highly diverse tree topology is necessary, especially in biological analysis.

TLDR: I am willing to raise my score if the results are clarified and presented more convincingly (1. error bars 2. a clearer results table and figures 3. a better presentation of the baselines); the method is presented in a way that is much much clearer (I think starting from the problem then objective/loss function then the 3 main components, etc might help); and the method is better placed in the related work with a better discussion of the limitations. From my limited understanding of the paper it seems the technical contribution is there (albeit a little hard for me to judge), but the presentation is still far from the quality necessary for acceptance.

It should be said that I cannot judge whether the baselines are chosen appropriately.

Weaknesses:

• There are no statistical error margins (e.g. standard deviation) for the results. This is okay if the computational cost is huge (e.g. often the case in LLMs) if so please state this clearly as well as the running cost in GPU hours, the GPUs used, etc.
• Table 2 confuses me. For instance for DS1: three are numbers are bold, but not even the 3 highest ones (when MLL higher is better according to the caption), e.g. VBPI-GNN also has the third highest score -7108.41. Also the difference between some of the results seem incredibly marginal. Furthermore, negative MLL might be clearer rather than having a minus sign in front of every number.
• The method has many components, which on the hand is impressive that the authors managed to build this system and make it work, but also comes with limitations that aren't adequately discussed in my opinion. There are a great number of hyperparameters, but far too little space is dedicated to ablating them or acknowledging the difficulty of choosing them.
• The related work is quite brief given that the model borrows many techniques related work it compares against. A clearer delineation would be helpful to the reader.

Clarity:

• The way indices i and t are re-used is confusing.
• It is imperative to give the citation of each baseline method considered. In the paper they are merely named, but not cited. This allows for confusion if two methods share the same name for instance and is generally poor practice.
• The Table captions could be improved, what are the numbers in paranthesis in Table 2? What is the grey background mean? Why are multiple numbers in bold per dataset?
• The y-axis range in Figure 3 makes the results really hard to discern.

Minor:

• Line 164 "As discussed, ..." please add a link to where this is discussed, this helps non-linear reading, which is standard for papers.
• Equation 1 LHS says h_i, the text says h_t

The paper studies a very specific task, phylogenetic tree generation problem, within the bioinformatics domain. Although the task might be important in the domain, the introduced methodology seems to be highly specified for this problem alone, which might limit its significance in the general graph generation area.

The biggest concern lies in the writing clarity, particularly the DON description. Multiple key information is missing and several notations are inconsistent across the main text. Firstly, the DON module seems to assume some graph structure already known among the sequence (e.g., figure 2.A has a ring structure). How is this graph constructed? It cannot be the tree structure as the phylogenetic tree has not been generated yet at this stage.

The presentation of DON in 3.1 can be largely improved, with many key notations and parameters unexplained. The biggest gap is the lack of a proper definition of the forward and backward diffusion process, with clear correspondence to time t. It starts with directly “updating node features $h_t$” without defining what t means. It is also not clear what positional encoding $PE_t(g_i)$ means, it is used with subscription $t$ but isn’t the position of node i fixed? How does PE vary with time t and why is it varying with t? It is not clear whether the transition probability in (2) defines a forward corruption process from t=N to 0 or t=0 to N? How can we make sure only a single node is selected to be absorbed at each time step? The notation of $h_t$ is also confusing, is it a single node embedding or embedding matrix for all nodes? There is a mixed use of $h_t$ and $h_i$.

The node order generation process after the entire graph is absorbed is also not explained well. Equation (3) defines a conditional probability between node embeddings $q(h_t|h_0, h_{(<t))}$, how can this be used for order determination? Shouldn’t one predict the probability of unmasking a node in a diffusion setting? It seems the transition matrix Qt only allows jumping from a non-masking state to a mask. How can this be reused for computing a cumulative transition matrix in the opposite direction (i.e. from masked to unmasked)?

Finally, it is not clear whether the DON is trained (e.g., with a certain score matching loss, and if so what is the training target given that optimal order is not available ahead of time?), or it is just a hand-crafted discrete forward diffusion process which is completely determined by the hyperparameters $\beta_{t,i}$. There is no description regarding how network parameters of the relational graph convolutional network used for node feature computation are trained either. There is a large discrepancy between what is described in 3.1 and training loss (10) in 3.4, where $q_\sigma(\sigma_t|G_0,\sigma_{(<t)})$ suddenly appears without definition.

In section 3.2 tree construction, a multi-head attention block with a query matrix Q is introduced MHA($Q, h_i, h_i$), what is the goal of Q here? It is initialized to an Identity matrix with size (N-3)*100, but was not mentioned later.

There are several typos and inconsistencies in naming terminology. E.g., the DON is sometimes referred as Diffusion Ordering Network and sometimes Dynamic Ordering Network.

• Relationship to ARTree is somewhat unclear, and although comparisons favor MDTree, the ARTree score is oftentimes quite close.
  • The authors should make it explicit what distinguishes MDTree from ARTree.
  • The ablations should make it clear which ablated forms of MDTree (if any) are worse than base ARTree
  • Since the benchmark scores of MDTree and ARTree are often quite close together, I am less impressed by "state of the art" results. If the authors could convince me why this position is mistaken, and their method is a significant improvement over ARTree, I would be amenable to improving my score.
• Lack of motivation for specific architectural choices. Most notably, the diffusion ordering network (DON) is justified in terms of the limitations of other autoregressive methods like ARTree; however, the specific choice of architecture is presented as arbitrary/self-evident. To this end, I have several questions:
  • What other options have the authors considered/tested? Why was the DON ultimately chosen?
  • How does the DON compare to a simple baseline that produces biologically meaningful orders without relying on deep learning? The authors may have a better sense of what a good baseline might be. However, I propose the following baseline as a reasonable starting point:
    1. Compute pairwise edit distances between genomic sequences (e.g. Levenshtein distances)
    2. Perform agglomerative clustering on the pairwise distances to get a crude tree
    3. Use an inorder traversal of the resulting tree to sort the leaves. This is your input order.
  • You cite "evidence of robustness across different taxa orders" in ARTree (line 163), but here you simply say "the influence of node orders on phylogenetic accuracy has not been thoroughly examined." The ablation-based evidence presented in Table 7 suggests that node order has a weak influence on model performance, but it would be more convincing to see a non ablation-based characterization (e.g. what is the variance in MLLs for random permutations of node order?)
• Unintuitive choice of representations to seed the DON. It is not apparent that genomic LM representations are the best candidates here, as the LMs are not actually trained to estimate evolutionary distances. Moreover, vector space representations of genetic sequences will always incur distortion, as the geometry of phylogenetic trees is inherently non-Euclidean as a result of the four-point condition.
• The DART formulation seems unnecessary. What is the advantage of reformulating phylogenetic tree construction (which we have a perfectly good description of already: learning a topology and a set of branch lengths), besides that it attempts to justify the use of a DON? If that is all, I would argue that "proper node orders improve phylogenetic inference" is a sufficient claim.
  • If other problems in phylogenetics are better viewed from the DART perspective, I would be interested in such an example. This would go a long way towards changing my mind on the value of this part of the paper.
• Presentation is unrefined throughout:
  • Figures are often cramped, and combined into figures with no clear logic (e.g. Figure 1 includes a cartoon and a runtime comparison)
  • Model details are crammed in pages 4 and 5. It is unclear without substantial cross-referencing and careful reading how all of the pieces fit together. While I understand the need to fit within the page limit, I would be interested in seeing the full architecture described in the Appendix.
    • "Mask rate modulated by a cosine function" (200) seems to be an essential detail of the autoregressive tree, but the equation is not given anywhere
• Related work does not discuss Bayesian methods since VBPI (except for VaiPhy). There have been many developments in this field since then.
• Missing experiments: oftentimes, certain models are missing from evaluations. For instance, MrBayes and structure representation models are missing from Table 1; many models are missing from Table 4; comparisons in terms of runtime, diversity, bipartition, etc., are only run for 2-3 models at a time. It is possible that these results are infeasible to generate, but the authors should make this explicit.

• The paper's main contribution is methodological but compared to the most closely related method, ARTree, there are only marginal improvements across datasets. This is also in light of the fact that the proposed methodology is extremely more computational intensive, both in terms of runtime and carbon footprint. With so much more computation, it is not too unfair to expect a more pronounced difference. Perhaps it is advisable to find conditions where dynamic node ordering strongly affects the tree reconstruction methods. If it is too hard to find such conditions, perhaps it is not as bad a problem as stated in the paper.
• The paper's key insights (compared to literature) is a method to learn an insertion ordering of the taxa. However, it is not clear that the proposed methodology to find such an ordering is clearly advantageous compared to other different orderings. The baseline considered against use a lexicographical ordering, which is just arbitrary. What happens when a different ordering is used?
• Related to the topic of choosing the right taxa ordering: theoretically, given just one correct planar ordering of the taxa (draw the true tree onto the plane and number leaves from left to right, there is a trivial greedy algorithm to find the correct tree structure and branch length from tree distance approximated from DNA sequences. As a result, find the correct order is one of the hardest subproblem of tree inference.
• There are other line of work that uses Prim ordering of the distance matrix between taxa as the ordering to add taxa into the tree and implemented with maximum likelihood heuristics (Zhang, Rao, Warnow 2019 Constrained incremental tree building: new absolute fast converging phylogeny estimation methods with improved scalability and accuracy; Le et al. 2021 Using Constrained-INC for Large-Scale Gene Tree and Species Tree Estimation). These are not deep learning-based methods so it's not directly comparable, but at least a discussion on the existing orders that have been considered is warranted. It would also be interesting to see how the Prim ordering works in these experiments.