Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: ***Paper Summary*** The authors suggest a structural representation model for the task of phylogenetic inference by the utilization of graph neural networks architectures. For the initial node attributes, they propose the construction of raw features based on the Dirichlet energy minimization. Using message passing steps, their model is able to learn structural features of the phylogenetic trees, depending on the downstream task. In an empirical level, the authors evaluate their method in synthetic and real data, highlighting a superior performance. 

***Contribution*** The paper has two main contributing components on the problem of phylogenetic inference. 1) The efficient computation of theoretically expressive tree node features, based on the minimization of the Dirichlet energy. The authors prove that using the computed Dirichlet energy-based features can provide representations, capable of distinguishing different tree topologies (Theorem 2). 2) The utilization of a graph neural network architecture for learning interior node representations, that can later be used in the downstream task. 	
strength_and_weaknesses: ***Strengths***
1. The authors provide an efficient algorithm (based on the Thomas Algorithm [Thomas, 1949]) for computing raw node features of the initial phylogenetic tree nodes, based on the Dirichlet energy minimization objective. This algorithm gives a linear-time complexity for the pre-computation of the graph input of the phylogenetic inference. 
2. The authors suggest the utilization of graph neural networks for learning structural representations of the intermediate states in a tree inference task. They show theoretically that the input raw node features yield representations that can discriminate different tree topologies.
3. Given the learned structural representations, the authors propose two successful ways of their utilization: 1) for the tree probability estimation through an energy-based model, that takes as input the learned node representations, 2)  for the branch length parameterization in the bayesian task, by providing the output GNN representations as statistical measures.

***Weaknesses***
1. The phase of feature initialization (through the linear two-time pass algorithm) is independent of the later graph-based representation learning method. What would be the impact of an initialization method that is dependent on the downstream task? 
2. The experimental evaluation both for the probability estimation and the VBPI tasks is performed more as an ablation study over various graph neural network encoders. To my knowledge, there are some deep learning approaches that deal with the problem of phylogenetic inference [Solis-Lemus 2022, Jiang 2022, Fioravanti 2017]. Could the authors discuss how their method is compared with theirs or explain why these alternative approaches may not be applicable?

- [Thomas 1949] Elliptic problems in linear difference equations over a network. 1949
- [Solis-Lemus 2022] Accurate Phylogenetic Inference with a Symmetry-preserving Neural Network Model. 2022
- [Jiang 2022] Learning Hyperbolic Embedding for Phylogenetic Tree Placement and Updates. 2022
- [Fioravanti 2017] Phylogenetic convolutional neural networks in metagenomics. 2017
clarity,_quality,_novelty_and_reproducibility: ***Clarity*** The paper is fairly written, without any major clarification issues. Both the theoretical and the empirical parts are easy to follow.

***Novelty*** The problem of phylogenetic inference is a very important problem, as it can help towards better understanding  of the evolutionary history of protein sequences, and genes. Although deep learning has been used before for tasks on phylogenetic trees, the utilization of graph-based machine learning methods is, to my knowledge, yet unexplored. The present paper suggests a novel approach based on efficiently computed raw node features and a graph neural network architecture to exploit the bias of the tree topology.

***Quality*** The paper presents both theoretical and empirical validation. The theoretical part solidifies the use of the computed features based on the Dirichlet energy minimization method for the characterization of phylogenetic tree topologies. In the empirical evaluation, the authors, show the effectiveness of the combination of graph-based and energy-based methods for tree topologies.

***Reproducibility*** The code and data are attached in the supplementary material. They are clean, making a rerun of the experiments feasible. 
summary_of_the_review: The paper presents a novel methodology for performing inference on phylogenetic trees. Their main contributions are twofold: they provide an efficient method for computing theoretically expressive initial node features on the phylogenetic trees and they propose a graph neural network-based model for learning representations, that are later used in downstream tasks. Both the theoretical and empirical evaluation seem solid, while the novelty and importance of the method is fair. That being said, I recommend the acceptance of the paper to the venue.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper provides a novel method for an efficient learning of topological features and then leveraging the power of graph neural networks (GNNs) to conduct tree inference (i.e. simultaneously learning good tree topologies and branch lengths). This approach is shown to perform better than several competitors.
strength_and_weaknesses: Strengths:

Rigorous proofs of the main theoretical results (numerical stability of the learned topological features, identifiability of the tree topology from a set of linearly independent features, and the maximum principle) - though many of these are "obvious in hindsight" to anyone familiar with Laplace PDEs, which are worth mentioning as an explicit connection (the matrix equation you are working with being a discrete Laplacian) - also, while I cannot think of a reference off the top of my head, these results are unlikely to all be novel; I derived the first one myself when working with numerical characters (copy numbers) when minimising the squared distance along the edges, but never published the results.

Good exposition overall, very clear explanation of what role every part of the paper plays (but the details of splits and pairwise split pairs would work better if moved into the main text rather than left in the appendix).

Reasonable testing approach which makes it directly comparable with previous work on the topic as well as other state-of-the-art methods.

Weaknesses:

It is not clear how reasonable the assumption of linear independence among the tip vectors would be. If I understand the one-hot encoding  right, having two positions, say x and y, in the alignment where 00, 01, 10 and 11 all occur at least once among the leaves would contradict linear independence. This may be the only possible violation of linear independence; the non-existence of such a pair of positions is a well-known condition, called the "perfect phylogeny" condition. If this is indeed accurate then proving a lemma to that effect would be powerful. As an aside, it is not clear what happens when linear independence fails; does the algorithm break down or can it deal with the situation?

The GNN's are not very well-described, a lot of prior knowledge is taken for granted; I understand that this is a conference paper with a page limit, but a bit more explanation would still be helpful (in particular, what makes EDGE different from other models, or what the aggregation and summarisation functions look like, could help the reader make more sense of the approach).

The optimal results in the table seem to differ only a tiny amount relative to the sub-optimal results; this is worth mentioning explicitly and also speculating about the implications (i.e. sure, the new method seems to be performing better, but only by a tiny amount); maybe this is due to the small tree size. Alternatively, a secondary evaluation metric could be considered in order to showcase the method's advantages.

A number of relevant papers that also carry out machine learning or automated inference of tree topology features (Matsen's 2007 "Optimization over a class of tree shape statistics", and Hayati et al, Royal Society B, 2022 for a more modern example) are not cited - this is not necessarily an issue as they are looking at a different class of problems, but it would be helpful for setting the context to mention that this (broadly speaking) is an active area of research, especially as many of the other references used are somewhat dated.
clarity,_quality,_novelty_and_reproducibility: Clarity: good to excellent

Quality: good to excellent

Originality: good, some results that are "obvious in hindsight" but nevertheless important to state; the adoption of GNNs is novel I believe

Reproducibility: no code has been provided, but a clear enough description is given to allow for the results to be reproduced by a sophisticated practitioner.
summary_of_the_review: This is a strong paper, both theoretically and experimentally, and with a bit of clean-up to address the comments above it could really shine.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of phylogenetic inference. The authors proposed a structural representation method for phylogenetic inference based on learnable topological features. The learnable topological features are constructed by minimizing the Dirichlet energy. The authors use the combined node features to infer structural information of phylogenetic trees and for downstream tasks. The authors conducted experiments on a simulated data and a benchmark of real data variational Bayesian phylogenetic inference problem to demonstrate the effectiveness of the proposed method. 
strength_and_weaknesses: Strength:
The paper studies an interesting problem of phylogenetic inference. The author adopted graph neural networks to help learn the structure information of phylogenetic trees, and perform inference on downstream tasks. 

Weakness:
I found the paper hard to read. While I understand that the authors might expects some knowledge of phylogenetics, it is necessary to provide a good background and clear explanations of the notations. For example, does the paper focus on rooted phylogenetic trees or including the unrooted one? The illustration figure showed an unrooted phylogenetic tree, while some discussions assume a root node?

The concepts and notations are also confusing. For example, in the phylogenetic model description, the author use Y to represent some "observed sequences", but the concept was never mentioned before. Also, what are the "characters" here refer to? The author never explained what "sites" refers to, but gives the assumption "different sites are independent and identically distributed". It would be good to explain what it means. 

In the proposed method section, it is hard to tell which part describes the existing work and which part is proposed by the authors. And if I understand correctly, the learning of node features based on the Dirichlet energy does require the knowledge of the phylogenetic tree structure. However, I thought the original problem is to find the appropriate topological structure?

I also found the experiment results not convincing enough. First, the author tested multiple GNN algorithms to compare with the results. The authors need to consider the multiple hypothesis testing effect. Second, in table 1, many results are not significant even though it is highlighted in bold. The difference between the proposed method with the original SPLIT and PSP is quite small in most cases. 


Minor comment:
There is a type after equation (1). I believe the root node is \tao instead of r?
clarity,_quality,_novelty_and_reproducibility: The presentation of the paper can be improved. While I believe the idea of this paper is relatively novel, the paper should provide more clarity on the background the models for the ICLR audiences. 
summary_of_the_review: The authors presented a novel idea to use graph learning for phylogenetic analysis. The authors claimed that their learned features has good representation power of the tree topology, and conducted some theoretical analysis on the representation power. The authors did experiments with several GNN algorithms, but the results look not strong enough (and interestingly GIN does not have much advantage in this case). More clarification on the background and method is also needed for this paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper adopts GNNs to help learn the structure information of phylogenetic trees and perform inference on downstream tasks. For initial node features, the approach transforms raw input features using the Dirichlet energy minimization. The model uses MPNN layers to learn the structural features of the phylogenetic trees, depending on the downstream task.

**Strengths:**

* Reviewers appreciate that authors showed theoretically that the input raw node features yield representations that can discriminate different tree topologies. The efficient computation of theoretically expressive tree node features is based on the minimization of the Dirichlet energy. The authors prove that using the computed Dirichlet energy-based features can provide representations capable of distinguishing different tree topologies. 
* The MPNN is used for learning interior node representations that can later be used in the downstream tree inference tasks.
* Reviewers agree that the paper is well-written overall and nicely organized with a very clear explanation of what role every part of the paper plays. 

**Weaknesses:**
* The optimal results in the table seem to differ only a tiny amount relative to the sub-optimal results. The new method seems to perform better, but only by a tiny amount, which might be due to the small tree size.  Several reviewers pointed out that experimental results are not particularly strong, however, the method also has other advantages over heuristic methods. 
* Secondary evaluation metrics could be considered in order to better showcase the method's advantages.
justification_for_why_not_higher_score: See the above-mentioned weaknesses. 
justification_for_why_not_lower_score: See the above-mentioned strengths.
Decision: Accept: poster