Learnable Topological Features For Phylogenetic Inference via Graph Neural Networks
Authors: Cheng Zhang
Venue: ICLR 2023 poster (2023)
Keywords: phylogenetic inference
learnable topological features
graph neural network
density estimation
variational inference

Abstract: Structural information of phylogenetic tree topologies plays an important role in phylogenetic inference. However, finding appropriate topological structures for specific phylogenetic inference tasks often requires significant design effort and domain expertise. In this paper, we propose a novel structural representation method for phylogenetic inference based on learnable topological features. By combining the raw node features that minimize the Dirichlet energy with modern graph representation learning techniques, our learnable topological features can provide efficient structural information of phylogenetic trees that automatically adapts to different downstream tasks without requiring domain expertise. We demonstrate the effectiveness and efficiency of our method on a simulated data tree probability estimation task and a benchmark of challenging real data variational Bayesian phylogenetic inference problems.

Published as a conference paper at ICLR 2023
LEARNABLE TOPOLOGICAL FEATURES FOR PHYLOGE- NETIC INFERENCE VIA GRAPH NEURAL NETWORKS
Cheng Zhang
School Mathematical Sciences and Center for Statistical Science Peking University, Beijing, China chengzhang@maath h. pku. edu. cn
ABSTRACT
Structural information of phylogenetic tree topologies plays an important role in phylogenetic inference. However, finding appropriate topological structures for specific phylogenetic inference tasks often requires significant design effort and domain expertise. In this paper, we propose novel structural representation method for phylogenetic inference based on Icarnable topological features. By combining the raw node features that minimize the Dirichlet energy with modern graph representation learning techniques, our learnable topological features can provide efficient structural information of phylogenetic trees that automatically adapts to different downstream tasks without requiring domain expertise. We demonstrate the effectiveness and efficiency of our method simulated data probability estimation task and a benchmark of challenging real data variational Bayesian phylogenetic inference problems.
INTRODUCTION
Phylogenetics is an important discipline of computational biology where the goal is identify the evolutionary history and relationships among individuals or groups of biological entities. In statistical approaches phylogenetics, this has been formulated shared history, i.e., phylogenetic trees, based on observed sequence data (e.g.. DNA, RNA, or protein sequences) under a model of evolution. The phylogenetic tree defines a probabilistic graphical model, based on which the likelihood of the observed sequences can be efficiently computed (Felsenstein 2003). Many statistical inference procedures therefore can be applied, including maximum likelihood and Bayesian approaches (Felsenstein 1981 Yang & Rannala 1997 Mau et al.) 1999 Huelsenbeck ct al. 2001).
inference problem hypotheses of
Phylogenetic inference, however, has been challenging due to the composite parameter space of both continuous and discrete components (i.e., branch lengths and the tree topology) and the combinatorial explosion in the number of tree topologies with the number of sequences. Harnessing the topological information of trees hence becomes crucial in the development of efficient phylogenetic inference algorithms. For example, by assuming conditional independence of separated subtrees, Larget (2013) showed that conditional clade distributions (CCDs) can provide more reliable tree probability estimation that generalizes beyond observed samples. A similar approach was proposed to design more efficient proposals for tree movement when implementing Markov chain Monte Carlo (MCMC) algorithms for Bayesian phylogenetics (Höhna & Drummond 2012). Utilizing more sophisticated local topological structures, CCDs were later generalized to subsplit Bayesian networks (SBNs) that provide more flexible distributions over tree topologies (Zhang & Matsen IV 20088). Besides MCMC, variational Bayesian phylogenetics inference (VBPI) was recently proposed that leveraged SBNs and structured amortization of branch lengths deliver competitive posterior estimates a more timely manner (Zhang & Matsen IV 2019 Zhang 2020 ZZhng & Matsen IV (022)). Azzuri et al. (202I) used a machine learning approach to accelerate maximum likelihood tree-search algorithms by providing more informative topology moves. Topological features have also been found useful for comparison and interpretation of the reconstructed phylogenies (Matsen IV 2007; Hayati et al. 2022). While these approaches prove effective in practice, they all rely heuristic features (e.g.. clades and subsplits) of phylogenetic trees that often require significant design effort and domain expertise, and may be insufficient for capturing complicated topological information.

---

Published as a conference paper at ICLR 2023
Graph Neural Networks (GNNs) are effective framework for learning representations of graph- structured data. To encode the structural information about graphs, GNNs follow a neighborhood aggregation procedure that computes the representation vector of node by recursively aggregating and transforming representation vectors of its neighboring nodes. After the final iteration of aggrega- tion, the representation of the entire graph also be obtained by pooling all the node embeddings together via some permutation invariant operators (Ying et al. 2018). Many GNN variants have been proposed and have achieved superior performance on both node-level and graph-level representation learning tasks (Kipf & Welling, 2017, Hamilton et al. 2017; Li et al. 2016; Zhang et al., 2018) Ying al. 2018). A natural idea, therefore, adapt GNNs to phylogenetic models for automatic topological feature learning. However, the lack of node features for phylogenetic trees makes it challenging as most GNN variants assume fully observed node features at initialization.
In this paper, we propose a novel structural representation method for phylogenetic inference that automatically learns efficient topological features based on GNNs. To obtain the initial node features
for phylogenetic trees, we follow previous studies (Zhu & Ghahramani 2002 Rossi et al. I02 to minimize the Dirichlet energy, with one hot encoding for the tip nodes, Unlike these previous studies, present fast linear time algorithm for Dirichlet energy minimization by taking advantage of the hierarchical structure of phylogenetic trees. Moreover, we prove that these features are sufficient for identifying the corresponding tree topology, i.e., there is information loss in our raw feature representations of phylogenetic trees. These raw node features are then passed to GNNs for more sophisticated structure representation learning required by downstream tasks. Experiments on a synthetic data tree probability estimation problem and a benchmark of challenging real data variational Bayesian phylogenetic inference problems demonstrate the effectiveness and efficiency of our method.
2 BACKGROUND
Notation A phylogenetic tree is denoted as (T, q) where T is a bifurcating tree that represents the evolutionary relationship of the species and is non-negative branch length vector that characterizes the amount of evolution along the edges of r. The tip nodes of 7 correspond to the observed species and the internal nodes of represent the unobserved characters (e.g., DNA bases) of the ancestral species. The transition probability (1) from character i to character j along an edge of length / is often defined by continuous-time substitution model .ugg-,uukee&& & Cantor (1969), whose stationary distribution is denoted as Let (T) be the set of edges of T, r be the root node (or any internal node if the tree is unrooted and the substitution model is reversible). Let Y {Yr, Y2.... 3 E Q X be the observed sequences (with characters in Q) of length M over N species.
Phylogenetic posterior Assuming different sites Y,, l...., M are independent and identically distributed, the likelihood of observing Y given the phylogenetic tree (T, q) takes the form
M
p q) II PYY 9) II (ay
II
Paget (guv),
(1)
(u.0)E
where at ranges over all extensions of Y. to the internal nodes with of being the assigned character of node u. The above phylogenetic likelihood function can be computed efficiently through the pruning algorithm (Felsenstein) 2003). Given a prior distribution p(r, q) of the tree topology and the branch lengths. Bayesian phylogenetics then amounts to properly estimating the phylogenetic posterior p(T, YY) x p(Y T, (T,))T.))
Variational Bayesian phylogenetic inference Let Q+(T) be an SBN-based distribution over the tree topologies and (q(T) be a non-negative distribution over the branch lengths, VBPI finds the best approximation to P(T, q Y from the family of products of Q (7) and Q (glT) by maximizing the following multi-sample lower bound
K
PY d')((())))) (x(T)))
LK (K6 (b) = Eq (Tl.i log
Σ
< log (oY)(
K
where (T 1:K q ) = I Qu("')))()))>>) To properly parameterize the variational distributions, support of the conditional probability tables (CPTs) is often acquired from sample
2

---

Published as a conference paper at ICLR 2023
Interior Node Embedding
GNN
Downstream Tasks
Leaf Nodes
One Hot Encoding
Unknown Feetures
Interior Nodes
Embedded Featuras
Figure An overview of the proposed topological feature learning framework for phylogenetic inference. Left: A phylogenetic tree topology with one hot encoding for the tip nodes and missing features for the interior nodes. Middle: Interior node embedding via Dirichlet energy minimization. Right: Subsequently, the tree topology with embedded node features are fed into GNN model for more sophisticated tree structure representation learning required by downstream tasks.
of tree topologies via fast heuristic bootstrap methods (Minh et al. 2013 Zhang Matsen IV 2019). The branch length approximation Q (q(T) is taken to be the diagonal I Lognormal distribution
(glT))
II E(r
Lognormal
(ge ple, ((e,)),
where ple, r), ale, 7) are amortized over the tree topology space via shared local structures (i.e., split and primary subsplit pairs (PSPs)), which are available from the support of CPT's. More details about structured amortization, VBPI and SBNs can be found section 3.2.2 and Appendix
Graph neural networks Let G (V, E) denote a graph with node feature vectors X for node E V, and (() denote the set of nodes adjacent v. GNNs iteratively update the representation of node by running message passing (MP) scheme for time steps. During each MP time step, the representation vectors of each node are updated based on the aggregated messages from its neighbors as follows
h (++1) UPDATE() (n!), m (h19,m m((tt)). m (1+1) (G ((n ( E(()))
where he.)) is the feature vector of node at time step with initialization h X (PDATE the update function, and (GG is the aggregation function. A number of powerful GNNs with different implementations of the update and aggregation functions have been proposed (Kipf & Welling 20177; Hamilton al. 2017 Li al. 2016; Veličković et al. 2018 Xu et al. 2019 Wang et al.] 2019). In additional to the local node-level features, GNNs can also provide features for the entire graph. To learn these global features, an additional READOUT function is often introduced to aggregate node features from the final iteration
hG READOUT (n.P:
READOUT can be any function that is permutation invariant to the node features.
PROPOSED METHOD
In this section, we propose a general approach that automatically learns topological features directly from phylogenetic trees. We first introduce a simple embedding method that provides raw features for the nodes phylogenetic trees, together with an efficient linear time algorithm for obtaining these raw features and a discussion on some of their theoretical properties regarding tree topology representation. We then describe how these raw features can adapted to learn efficient representations certain structures of trees (c.g., edges) for downstream tasks.
3.1 INTERIOR NODE EMBEDDING
Learning tree structure features directly from tree topologies often requires raw node/edge features. as typically assumed in most GNN models. Unfortunately, this is not the case for phylogenetic models.
3

---

Published as a conference paper at ICLR 2023
Although use hot encoding for the tip nodes according to their corresponding species (taxa names only, not the sequences), the interior nodes still lack original features. The first step of tree structure representation learning for phylogenetic models, therefore. is to properly input those missing features for the interior nodes. Following previous studies (Zhu & Ghahramani 22002 Rossi al. 202T), make common assumption that the node features change smoothly across the tree lopologies (i.e., the features of every node are similar to those of the neighbors). A widely used criterion of smoothness for functions defined on nodes of graph is the Dirichlet energy. Given tree topology т = (V, E) and a function f V + R the Dirichlet energy is defined as
E(f.T)=
Σ lIf(u) - f(o)11. (a
Let V V y'uve Vo. where 4 denotes the of leaf nodes and V denotes the set of interior nodes. Let X = { E Vh3 be the set of one hot embeddings for the leaf nodes. The interior node features X faolv E Vo) then can be obtained by minimizing the Dirichlet energy
X arg min {(X* X T)
arg min X
Σ
| 2..113. -E,12.
X
(a,))E
3.1.1 A LINEAR TIME TWO-PASS ALGORITHM
Note that the above Dirichlet energy function is convex, its minimizer therefore can be obtained by solving the following optimality condition
O((X X
X = 0.
(3)
0X
turns out that equation 3 has a close-form solution based on matrix inversion. However, as matrix inversion scales cubically in general, it is infeasible for graphs with many nodes. Fortunately, by leveraging the hierarchical structure of phylogenetic trees, we can design a more efficient linear time algorithm for the solution of equation as follows. We first rewrite equation 3 as system of linear equations
EvENTo) (E. - -.) Yu E Vo:
E. = Fv.
Ve VVEV
(4)
where (u) is the set of neighbors of node u. Given topological ordering induced by the tree can obtain the solution within a two-pass sweep through the tree topology, similar to the Thomas algorithm for solving tridiagonal systems of linear equations (Thomas 1949). In the first pass, we traverse the tree in a postorder fashion and express the node features as linear function of those of their parents,
(5) for all the nodes expect the root node, where n. denotes the parent node of More specifically, first initialize cu = 0, ch, = xu for all leaf nodes u E Vb_ For all the interior nodes except the root node, we compute cu, dh, recursively as follows (see detailed derivation in Appendix B
T., C. + dn.
Evech(u) d,
Ca W(ww) -
- Evech(u) Co
d W((1) Evech(u) Cv
(6)
where ch(u) denotes the set of child nodes of u. In the second pass, we traverse the tree in preorder fashion and compute the solution by back substitution. Concretely, at the root node r, given equation for all the child nodes from the first pass, we can compute the node feature directly from equation as below
Evechlrr d. E [V(r) Evecc(r) Co
For all the other interior nodes, the node features can be obtained via equation 5 by substituting the learned features for the parent nodes. We summarize our two-pass algorithm Algorithm Moreover, the algorithm is numerically stable due to the following lemma (proof in Appendix C
Lemma 1. Let À min [W))). For all interior node u E V [o) C. < -
Besides bifurcating phylogenetic trees, the above two-pass algorithm can be easily adapted to interior node embedding for general tree-shaped graphs with given tip node features.
'This is trivial for rooted trees since they are directed. For unrooted trees, can choose interior node as the root node and the topological ordering of the corresponding rooted trees.
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 A Two-pass Algorithm for Interior Node Embedding
1: Input: Tree topology 7 = (V, E.,, where V = Vo; Features for the tip nodes {æ lu E Voj 2: Initialize C. 0, d Tus Vuu V
3: Traverse the tree topology in postorder fashion. For any interior node that is not the root node, compute Cy and d,, as in equation 6
4: Traverse the tree topology in preorder fashion. For the root node compute the node feature as in equation] 7 For any other interior node u, compute the node feature as Tu = C. + du-
5: return {E.,/u i VoJ.
3.1.2 TREE TOPOLOGY REPRESENTATION POWER
In this section, discuss some thcoretical properties regarding the tree topology presentation power of the node features introduced above. We start with useful lemma that elucidates an important behavior of the solution to the linear system [ which is similar the solutions to elliptic equations.
Lemma (Extremum Principle). Ler (T. Rd u E V} be a set of d-dimensional node features that satisfies equations 4 A1 < n S d, let X[n] (āuIniluu
} be the set of the n-th components of node features. Then, v1 S n S we have: the extremum values (i.e., maximum and minimum) of X [n] can achieved at some tip nodes; (ii) if the extremum values are achieved at some interior nodes, then X [m)] has only one member, or in other words, [n] is the same Vu E V.
Theorem 1. Let N be the number of tip nodes. Let (%r, E TR-N/u E VV be the solution to the linear system with one hot encoding for the tip nodes. Then, Vu E VO, we have
N
(i) 0 Lulmi [m]
s n S, and (ii)
[u[n]= =1
The complete proof's of Lemma 2 and Theorem T are provided in Appendix When the tip node features are linearly independent, a similar proposition holds when we consider the coefficients the linear combination of the tip node features for the interior node features instead.
Corollary 1. Suppose that the tip node features are linearly independent, the interior node features obtained from the solution to the linear system all lie in the interior of the convex hull of all tip node features.
The proof is provided in Appendix C The following lemma reveals key property the nodes that adjacent to the boundary of the tree topology in the embedded feature space.
Lemma 3. Let {zulu E V3 be the solution to the linear system with linearly independent tip node features. Let (Zu = Evevs a" E V*) be the convex combination representations of the interior node features. For any tip node v E Vb, we have
u" = aig max a ugV-
+ u² N'v)
Theorem 2 (Identifiability). X (āu/u Vo} and Z = {Zulu E Vo} be the sets of interior node features that minimizes the Dirichlet energy for phylogenetic tree topologies and Ta respectively, given the same linearly independent tip node features. 1f X Z then T2 Tz-
The proofs of Lemma and Theorem 2 are provided Appendix C By Theorem 2 we see that the proposed node embeddings are complete representations of phylogenetic tree topologies with no information loss.
3.2 STRUCTURAL REPRESENTATION LEARNING VIA GRAPH NEURAL NETWORKS
Using node embeddings introduced in section 3.1 raw features, now show how to learn more sophisticated representations of tree structures for different phylogenetic inference tasks via GNNs.
Given a tree topology т, let [h E V} be the raw features and (h, E V) be the output features after the final iteration of GNNs. We feed these output features of GNNs into multi-layer perceptron (MLP) to get set of learnable features for each node
h MLP(0)
VOEV,
before adapting different downstream tasks, demonstrated in the following examples.
5

---

Published as a conference paper at ICLR 2023
3.2.1 ENERGY BASED MODELS FOR TREE PROBABILITY ESTIMATION
Our first example is on graph-level representation learning phylogenetic tree topologies. Let T denote the entire tree topology space. Given learnable node features of tree topologies, one can use permutation invariant function g to obtain graph-level features and hence create an energy function F T + I that assigns each tree topology a scalar value as follows
(T(T) MLP (hc), hg g (( V)).
where g o MLP(()) can be viewed as READOUT function in section energy based models (EBMs) for tree probability estimation
2
This allows construct
(T(T) exp (-F((T) Z(Φ)
Z(Ø)
Σ, TET exp(-Fa(T))
As ((Φ) is usually intractable, we can employ noise contrastive estimation (NCE) Guttmann & Hyvärinen 2010) to train these energy based models. Let pn. be some noise distribution that has tractable density and allows efficient sampling procedures. Let D&(T) = log (T) - log logp..T).. We
can train D& to minimize the following objective function (NCE loss)
(() = (Br log (S (Do(T)) + Er-D..()) log (1 S (D& (T))))
where S(x) Teexp( x is the sigmoid function. is easy to verify that the minimum is achieved at Dø- (T) log Pdata Pm Pm (T). Therefore, Q6" (T) Pdata (T) (T( exp (Dæ- (T)).
3.2.2 BRANCH LENGTH PARAMETERIZATION FOR VBPI
The branch length parameterization in VBPI so far has relied on hand-engineered features (i.e., splits and PSPs) for the edges on tree topologies. Let S, denote the set of splits and Spep denote the set of PSPs. The simple split- based parameterization assigns parameters 26", 2/ for splits in S,. The mean and standard deviation for each edge on T are then given by the associated parameters of the corresponding split e/t as follows
p(e,
dill e/r' (ee V//T
The more flexible PSP parameterization assigns additional parameters for PSPs in Spep and adds the associated parameters of the corresponding PSPs e/fT to equation to refine the mean and standard deviation parameterization
-(e,t)=(l) + E.eest
BEEfT Dht -(e,r)=vee = + Σ Deeegr S.
Although these heuristic features prove effective, they often require substantial design effort, a sample of tree topologies for feature collection, and can not adapt themselves during training which makes it difficult for amortized inference over different tree topologies. Based on the learnable node features, we can design more flexible branch length parameterization that is capable of distilling more effective structural information of tree topologies for variational approximations. For each edge a permutation invariant function obtain
vu,v) u) on similarly as in section 3.2.1 one edge-level features and transform them into the mean and standard deviation parameters as follows
((e,T) MLP (he), (ee MLP (he),
he = f ((h., ((hu,h,)) hb)))
(10)
Compared heuristic feature based parameterizations in Mand learnable topological feature based parameterizations in T0 much richer design for the branch length distributions across different tree topologies and do not require pre-sampled tree topologies for feature collection.
EXPERIMENTS
In this section, we test the effectiveness and efficiency of learnable topological features for phyloge- netic inference on the two aforementioned benchmark tasks: tree probability estimation via energy based models and branch length parameterization for VBPI. Following Zhang & Matsen IV (2019). in VBPI we used the simplest SBN for the tree topology variational distribution, and the CPT supports
Here ((b) is taken free parameter and included into Φb

---

Published as a conference paper at ICLR 2023
10-1
10a
GCN
EBM Approximation
KL Divergence
10
NCE Loss
GONN
10-1
8.4.0mm
MLF GCN
10-3
4x
SAGE
50
100
200
50
150
200
10:
10-2
10-2
10-1
Iterations
Thousand lterations
Ground Truth
Figure 2: Comparison of learnable topological feature based EBMs for probability mass estimation of unrooted phylogenetic trees with leaves using NCE. Left: NCE loss. Middle: KL divergence. Right: EBM approximations vs ground truth probabilities. The NCE loss and KL divergence results were obtained from 10 independent runs and the error bars represent one standard deviation.
were estimated from ultrafast maximum likelihood phylogenetic bootstrap trees using UFBoot MMnh al. 2013). The code available httttps://ggthhu com/ zcrabbit/vbp..bc
Experimental setup. We evaluate five commonly used GNN variants with the following convolu- tion operators: graph convolution networks (GCN), graph isomorphism operator (GIN), GraphSAGE operator (SAGE), gated graph convolution operator (GGNN) and edge convolution operator (EDGE). See more details about these convolution operators in Appendix I In addition to the above GNN variants, we also considered a simpler model that skips all GNN iterations (i.e., T = 0) and referred to it MLP in the sequel. All GNN variants have GNN layers (including the input layer), and all involved MLPs have 2 layers. We used summation as our permutation invariant aggregation function for graph-level features and maximization for edge-level features. All models were implemented in Pytorch (Paszke et al. 2019) with the Adam optimizer (Kingma & Bal 2015). We designed our experiments with the goals of (i) verifying the effectiveness GNN-based EBMs for tree topology estimation and (ii) verifying the improvement of GNN-based branch length parameterization for
VBPI over the baseline approaches (i.e., split and PSP based parameterizations) and investigating how helpful the learnable topological features are for reducing the amortization gaps.
4.1 SIMULATED DATA TREE PROBABILITY ESTIMATION
We first investigated the representative power of learnable topological features for approximating distributions on phylogenetic trees using energy based models (EBMs), and conducted experiments simulated data set. We used the space of unrooted phylogenetic trees with 8 leaves, which contains 10395 unique trees in total. Similarly as in Zhang & Matsen IV (2019), we generated a target distribution po( by drawing sample from the symmetric Dirichlet distribution Dir(31) of order 10395 with pre-selected arbitrary order of trees. The concentration parameter /3 is used to control the diffuseness of the target distribution and was set to 0.008 provide enough information for inference while allowing for adequate diffusion in the target. As mentioned earlier in section 1 used noise contrastive estimation (NCE) train our EBMs where we the noise distribution Pa. (n(T)) to be the uniform distribution. Results were collected after 200,000 parameter updates. Note that the minimum NCE loss in this case
J 2JSD (Po(T))lp,(T)) + 2 2,
where (SI(. the Sensen-Shannon divergence.
Figure 2 shows the empirical performance of different methods. From the left plot, we see that the NCE losses converge rapidly and the gaps between NCE losses for the GNN variants and the best NCE loss J (dashed red line) are close to zero, demonstrating the representative power of learnable topological features on phylogenetic tree probability estimations. The evolution of KL divergences (middle plot) is consistent with the NCE losses. Compared to MLP, all GNN variants perform better, indicating that the extra flexibility provided by GNN iterations crucial for tree probability estimation that would benefit from more informative graph-level features. Although the

---

Published as a conference paper at ICLR 2023
Table 1: Evidence Lower bound (ELBO) and marginal likelihood (MI.) estimates of different methods across 8 benchmark datasets for Bayesian phylogenetic inference. The marginal likelihood estimates of all variational methods are obtained via importance sampling using 1000 samples, and the results (in units of nats) are averaged over 100 independent runs with standard deviation in brackets. Results for stepping-stone (SS) are from Zoang & Matsen IV (usig 10 independent MrBayes (Ronquist et al. 2012) runs, each with 4 chains for 10,000,000 iterations and sampled every 100 iterations).
DAPA SKT
DS1
B82
D18
DS4
D85
D186
DS7
DS8
TAXA
27
36
30
50
Y STrES
1949
2520
1512
1137
378
1133
1524
1008
89)
-51736.820000) 16]
113332,8200710
6600.22)
49(0.47)
-37335,4900117
36661.622.000
PSP
-2111.25(1.21)
-26369
43(0.64)
-33736,7100 (0.445)
-1333242/0.655
-8216.34:0.16
-6729 20(0.44)
-37885.18(0013
-8655.4000.33 32)
MLP
71100.4300.0 10)
26365 15(0.10)
13331199/00099 (3006.2500005)
221152230.12)
6728. 97)
37334,99(0.22)
-3655.33/0.1 15)
7110.33 10)
$3/0.09)
(3.0662500055
-13331 94/0.99
9211.0600.10)
-3334,9200121
-3655.170..1
GIN
-2110.27(0.09)
-26368 8K.0.99)
-37736.2600 (6(007
(3/01.82/0009)
-8217 1))
-6718 59(0.17)
-37334.44(0111
-8655.08(0.15)
SAGE
-2110.2910. 10)
86.06.8440.07))
-39336
06)
-13331 84/0 (0)
4211
-6738 63/0 15)
-3933,9110.11
-3655 05(0, 14)
GONN
-7110.26/0.00)
-26368
-35736200(0066)
-13331.9900.99
-8217
560.156
-37834.87(012)
-8655.01;0.11
EDGE
77100.2600100)
260665.840.099)
-30726,2500.05)
103311.80/0.100
-X217.99000 11/0.22)
570.16)
(37334.4400.44)
-3655.01;0.14
SPEIT
7108,47(0:27)
26367 730008)
13773512(0.12)
13330.010.31)
51:0.11
580048)
18933.
-8651,3910.90
PSP
-7108.41(0.19 19)
-26367 74(0.09)
-31735.1200.00)
-13329 97/0999602222 22)
-8214 66:0.66)
-6734 (100.49)
-37332.05(0039)
-8650.66:2 51)
MLP
-7108.4100.24 24)
26367.74/0.08)
-33735.12/0.101
-13829.9900.22 22)
-8214.77(0.477
4704447(0
33832203(0.34)
-3650.72/0.53)
7108,4300.00 161
26367.7300.05)
12735.12
13329, 97)
37332.04(0.29) 510.47)
3650.65/0.54)
GIN
-2108, 4000 27)
-26367 730 08)
-31735,12(04
-13329 96/0 (8)
-8214 64:0.99)
-673444(00.00)
-37332.0200 02(0 10)
-8650.66/0.45)
SAGE
-7108.4000.1 17)
-2666773440077)
-33735.12(0.09
-13329.9600.1
-8214.6400.44)
-6724 39(0.42)
(0.33)
-3650.66/0.49)
GGNN
7108,40/0.19 19)
26367.73(0.10)
-33735.11(0.09)
13329 95
9214.67:0.36)
6724 (8
37332.03/0.30)
8650.65:0.48)
EDGE
410064410.144
-6.367.3300077
-21735.12(0009)
-13329 14)0.19
-8214 6420.88)
-6714.37(0.40)
.7333204((.226)
-6600.6500455)
S8
-7108.42/00.8 18)
-26367 57(0.48)
-38735.44(0.55 50)
-13330.06/0.54)
-8214.51(0.26)
-6734.07(0.88 86)
-37332.76(2-43)
-8649.88(1.75)
raw features from interior node embedding contain all information of phylogenetic tree topologies, see that distilling effective structural information from them is still challenging. This makes GNN models that are by design more capable of learning geometric representations a favorable choice. The right plot compares the probability mass approximations provided by EBMs using MLP and GGNN (which performs the best among all GNN variants), to the ground truth Po(T). We see that EBMs using GGNN consistently provide accurate approximations for trees across a wide range of probabilities. On the other hand, estimates provided by those using MLP are often of large bias, except for a few trees with high probabilities.
4.2 REAL DATA VARIATIONAL BAYESIAN PHYLOGENETIC INFERENCE
The second task we considered VBPI, where we compared learnable topological feature based branch length parameterizations to heuristic feature based parameterizations (denoted Split and PSP resepectively) proposed in the original VBPI approach (Zhang & Matsen IV
2019). All methods
were evaluated on 8 real datasets that are commonly used benchmark Bayesian phylogenetic
inference methods (Hedges et al. 1990 Garey et al., 1996; Yang & Yoder 2003 Henk et al. 2003)
Lakner et al., 20088 Zhang & Blackwell |001]]]ooer & Yang 2004 Rossman et al. 2001 Höhna
Rossaan
& Drummond 2012 Larget 2013] Whidden & Matsen IV [V[2015) These datasets, which we call
DSI-8, consist of sequences from 27 64 eukaryote species with 378 2520 site observations. We concentrate on the most challenging part of the Bayesian phylogenetics: joint learning of the tree topologies and the branch lengths, and assume a uniform prior on the tree topology, an i.i.d. exponential prior (10) for the branch lengths and the simpleJukes Jukes & Cantor (1969) substitution model. We gathered the support of CPTs from 10 replicates of 10000 ultrafast maximum likelihood bootstrap trees (Minh et al. 2013). We set K = 10 for the multi-sample lower bound, with a schedule An = min( 1, 0.001 + n/ 100000), going from 0.001 to I after 100000 iterations. The Monte Carlo gradient estimates for the tree topology parameters and branch length parameters were obtained via VIMCO (Mnih & Rezende, 2016) and the reparameterization trick (Kingma & Welling 2014) respectively. Results were collected after 400,000 parameter updates.
Table shows the estimates of the evidence lower bound (ELBO) and the marginal likelihood using different branch length parameterizations on the 8 benchmark datasets, including the results for the
8

---

Published as a conference paper at ICLR 2023
Split NLP
PSP FDGF
-7250
Lower Bound
-750
Amortization Gap
Amortization
-12
-8250
PSP
-8500
-8750
EDGE
1.
20
lterations
Tree
Tree
Figure 3: Performance on DS1. Left: Lower bounds. Middle & Right: Amortization gaps on trees the 95% credible sets.
stepping-stone (SS) method (Xie et al. 2011). which is one of the state-of fftte-of-thh-arr sampling based methods for marginal likelihood estimation. For each data set, better approximation would lead to a smaller variance of the marginal likelihood estimates. We see that solely using the raw features, MLP-based parameterization already outperformed the Split and PSP baselines by providing tighter lower bounds. With more expressive representations of local structures enabled by GNN iterations, GNN-based parameterization further improved upon MLPP-based methods, indicating the importance of harnessing local topological information for flexible branch length distributions. Moreover, when used importance distributions for marginal likelihood estimation via importance sampling, MLP and GNN variants provide more steady estimates (less variance) than Split and PSP respectively. All variational approaches compare favorably to and require much fewer samples. The left plot in Figure 3l shows the evidence lower bounds function of the number of parameter updates on DS1. Although neural networks based parameterization adds to the complexity of training in VI, we see that by the time Split and PSP converge, MLP and EDGF aaoGeeee bounds and quickly surpass these baselines as the number of iteration increases.
achieve comparable (if not better) lower
As diagonal Lognormal branch length distributions these variational distributions were amortized over tree topologies under different parameterizations therefore is crucial for the overall approximation performance. To better understand this effect of amortized inference, we further investigated the amortization gf different methods on individual trees in the 95% credible of DS1 as Zhang (2020). The middle and right plots in Figure show the amortization gaps of different parameterization methods on each tree topology т. We see the amortization gaps of ML. and EDGE are considerably smaller than those of Split and PSP respectively, showing the efficiency of learnable topological features for amortized branch length distributions. Again, incorporating more local topological information is beneficial, as evidenced by the significant improvement of EDGE over MLP. More results about the amortization gaps can be found in Table in the appendix.
used for all parameterization methods, how
CONCLUSION
We presented novel approach for phylogenetic inference based on learnable topological features. By combining the raw node features that minimize the Dirichlet energy with modern GNN variants, our learnable topological features can provide efficient structural information without requiring domain expertise. In experiments, we demonstrated the effectiveness of our approach for tree probability estimation on simulated data and showed that our method consistently outperforms baseline approaches for VBPI on a benchmark of real data sets. Future work would investigate more sophisticated GNNs for phylogenetic trees, and applications to other phylogenetic inference tasks where efficiently leveraging structural information of tree topologies is of great importance.
We EDGE example here for branch length parameterization since it can learn edge features (see Appendix F.. All GNN variants (except the simple GCN) performed similarly this example (see Table T).
'The amortization gap on tree topology is defined as L(Q")r) L(Qulr), where L(QxlT) is the ELBO -
of the approximating distribution @ (q) and T,Q") /r) is the maximum lower bound that can be achieved with the variational family. See more details in Zhang 20000;; Cremer al. (2088.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work was supported by National Natural Science Foundation of China (grant no. 12201014), as well as National Institutes of Health grant A1162611. I. The research of the author was support in part by the Key Laboratory of Mathematics and Its Applications (LMAM) and the Key Laboratory of Mathematical Economics and Quantitative Finance (LMEQF) of Peking University. The author grateful for the computational resources provided by the High-performance Computing Platform of Peking University. The author appreciates the anonymous ICLR reviewers for their constructive feedback.
REFERENCES
D. Azouri, S. Abadi, Y. Mansour, Mayrose, and T. Pupko. Harnessing machine learning to guide phylogenetic-tree search algorithms. Nature Communication, 12, 2021.
Chris Cremer, Xuechen Li, and David Duvenaud. Inference suboptimality in variational autoencoders.
In Proceedings of the 35th International Conference on Machine Learning, 2018.
J. Felsenstein. Evolutionary trees from DNA sequences: A maximum likelihood approach. Journal of Molecular Evolution,
1981.
J. Felsenstein. Inferring Phylogenies. Sinauer Associates, 2nd edition, 2003.
D. Fioravanti, Y. Giarratano, V. Maggio, C. Agostinelli, M. Chierici, G. Jurman, and C. Furlanello. Phylogenetic convolutional neural networks in metagenomics. BMC Bioinformatics, 19, 2018.
J. R. Garey, J.J. Near, M. R. Nonnemacher, and S. A. Nadler. Molecular evidence for Acanthocephala as a subtaxon of Rotifera. Mol. Evol., 43:287-292, 1996.
M. Gutmann and A. Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, pp. 297-304, 2010.
W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Maryam Hayati, Leonid Chindelevitch, David Aanensen, and Caroline Colijn. Deep cluster- ing of bacterial tree images. Philosophical Transactions of the Royal Society B: Biologi- cal Sciences, 377(1861):0210233,, 2022. doi: 10.11098/sth.2221..00 org. doii/bs./... 10. 10.0....900 1098 rsth. 2021 12022.000 0231
URL https://
Ioyalsoocettypulliei...
S. B. Hedges, K. D. Moberg, and L. R. Maxson. Tetrapod phylogeny inferred from 18S and 28S ribosomal RNA sequences and review of the evidence for amniote relationships. Mol. Biol. Evol., 7:607-633, 1990.
D. A. Henk, A. Weir, and M. Blackwell. Laboulbeniopsis termitarius, an ectoparasite of termites newly recognized member of the Laboulbeniomycetes. Mycologia, 95:561-564, 2003.
Sebastian Höhna and Alexei Drummond. Guided tree topology proposals for Bayesian phylogenetic inference. Syst. Biol., 61(1):1-11, Jamuary 2012. ISSN 1063-5157. doi: 10. 10.10933syssioo/yy0074. URL http:://t doi org 10w.:/.0.1199///1000 htt.:0.119//yyyssiiooo wwwsio/ssss...ee syr074
Huelsenbeck, Ronquist, R. Nielsen, and P. Bollback. Bayesian inference of phylogeny and its impact evolutionary biology. Science, 294:23 294:2310-231 10-2314, 2001.
Yueyu Jiang, Puoya Tabaghi, and Siavash Mirarab. Learning hyperbolic embedding for phylogenetic tree placement and updates. Biology, (1))), 2022, ISSN 2079-7737. doi: 10.3390/bologyy 1091256.
URL https::t///.mm. www mdpi wtt.c////22000 7011999777777111111
Jukes and C. R. Cantor. Evolution of protein molecules. protein metabolism, III, pp. 21-132, New York, 1969. Academic Press.
Munro (ed.), Mammalian
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
10

---

Published as a conference paper at ICLR 2023
D. P. Kingma and M. Welling. Auto-encoding variational bayes. In ICLR, 2014.
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
C. Lakner, P. van der Mark. J. P. Huelsenbeck, B. Larget, and F. Ronquist. Efficiency of Markov chain Monte Carlo tree proposals Bayesian phylogenetics. Syst. Biol., 57:86-103, 2008.
Bret Larget. The estimation of tree posterior probabilities using conditional clade probability distributions. Syst. Biol., 62(4):501-511, July 2013. ISSN 1063-5157. doi: 00.1099/yssbo//sy0114.
URL httt::tt:///x doi http:///www......rr//00000////// http:///.....0////o///o///////// https///sssooooyyo/111/
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In Proceedings of the 4th International Conference on Learning Representations, 2016.
Frederick A Matsen IV. Optimization over class of tree shape statistics. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 4(3):506-512, 2007.
B. Mau, M. Newton, and B. Larget. Bayesian phylogenetic inference via Markov chain Monte Carlo methods. Biometrics, 55:1-12, 1999.
B. Q. Minh, M. Nguyen, and A. von Haeseler. Ultrafast approximation for phylogenetic bootstrap. Mol. Biol. Evol., 30: 1881 2013.
Andriy Mnih and Danilo Rezende. Variational inference for monte carlo objectives. In Proceedings of the 33rd International Conference on Machine Learning, pp. 1791-1799, 2016.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner. Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett (eds.), Advances
Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019. URL http:httpppppprsaa// http:eesss.erii...cceeeeeeeeeeee 9015 hatl--yytrrhcheeh an imperative pdf
annerchharr-mmeratiieeee style high perforranereeeeeeee deepeee-eeeee-eeeeeeneee library.
F. Ronquist, M. Teslenko, P. van der Mark, D. L. Ayres, A. Darling, S. Hohna, B. Larget, L. Liu, M. A. Shehard, and J. P. Huelsenbeck. MrBayes 3.2: efficient Bayesian phylogenetic inference and model choice across large model space. Syst. Biol., 61:539-5442 542, 2012.
Emanuele Rossi, Henry Kenlay, Maria Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael Bronstein. On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features, 2021. URL URL [tttttts///xxiiii www.:worggraaeee abs/ 2111 12128
A. Rossman, J. Mckemy, R. A. Pardo-Schultheiss, and J. Schroers. Molecular studies the Bionectriaceae using large subunit rDNA sequences. Mycologia, 93:100-110, 2001.
C. Solis-Lemus, S. Yang, and L. Zepeda-Nunez. Accurate phylogeente inference with symmetry- preserving neural netwrok model, 2022.
wttp://gg/aa////..a...../// 04663
L. H. Thomas. Elliptic problems in linear difference equations over a network. Technical report, Columbia University, 1949.
Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph CNN for learning on point clouds. ACM Transaction on Graphics, 38(5):1-12, 2019.
Chris Whidden and Frederick A Matsen IV. Quantifying MCMC exploration of phylogenetic tree space. Syst. Biol., 64(3):472 491, May 2015. ISSN 1063-5157, 1076-836X. doi: 10. s0.3 syv006. URL htR.:t doi. wrg.

---

Published as a conference paper at ICLR 2023
W. Xie, P. O. Lewis. Y. Fan, L. Kuo, and M.-H. Chen. Improving marginal likelihood estimation for Bayesian phylogenetic model selection. Syst. Biol., 60:150-1:66 2011.
K. Xu, W. Hu, J. Leskovec, and S. Kegelka. How powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations, 2019.
Z. Yang and B. Rannala. Bayesian phylogenetic inference using DNA sequences: Markov chain Monte Carlo method. Mol. Biol. Evol., 14:717-724, 1997.
Z. Yang and A. D. Yoder. Comparison of likelihood and Bayesian methods for estimating divergence times using multiple gene loci and calibration points, with application to a radiation cute-looking mouse lemur species. Syst. Biol., 52:705-716, 2003.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, 2018.
A. D. Yoder and Yang. Divergence datas for Malagasy lemurs estimated from multiple gene loci: geological and evolutionary context. Mol. Ecol., 13:757-773, 2004.
Cheng Zhang. Improved variational bayesian phylogenetic inference with normalizing flows. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances
in Neural Information Processing Systems, volume 33, pp. 18760-18771, Curran Asso- ciates, Inc., 2020. URL httttpps://rroceeddgg neur i ps. cc cc/pppper//22//F111. 696409bf8943 7686ba
040.0/08899777868222424410022000 - pddf
Cheng Zhang and Frederick Matsen IV. Generalizing tree probability estimation via bayesian networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 1444-455 Curran Associates, Inc., 2018. URL
ni nips cc/paper///ppcccc wet.--stimaaiinn via ba nett works.
7418 generalizing- tree pdf
Cheng Zhang and Frederick A Matsen IV. Variational Bayesian phylogenetic inference. In Interna- tional Conference on Learning Representations, 2019. URL htttp:://opereeritt net/
Sorum?id-SJVmj>> RR9X
Cheng Zhang and Frederick Matsen IV. variational approach to Bayesian phylogenetic inference, 2022. URL https://arxixs
077477
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI Conference on Artificial Intelligence, pp. 4438 4445, 2018.
N. Zhang and M. Blackwell. Molecular phylogeny of dogwood anthracnose fungus (Discula destruc- tiva) and the Diaporthales. Mycologia, 93:355-365, 2001.
X. Zhu and Z. Ghahramani. Learning from labeled and unlabeled data with label propagation. Technical report, Carnegie Mellon University, 2002.
12

---

Published as a conference paper at ICLR 2023
A SUBSPLIT BAYESIAN NETWORKS
0
12
simple subsplit Bayesian network for leaf set that contains species A, B, C Cnd D. Left: Some rooted phylogenetic tree examples. Middle: The corresponding SBN assignments. For ease of illustration, subsplit (W, Z) represented as 2 in the graph. The dashed gray subgraphs represent fake splitting processes where splits are deterministically assigned, and are used purely to complement the networks such that the overall network has a fixed structure. Right: The SBN for these examples. This figure is adapted from Zhhng & Matsen IV (2019).
Figure 4:
W
Subsplit Bayesian networks (SBNs) were introduced by Zhang & Matsen IV (018)) for density estimation on tree topologies and were later used to provide a family of variational distributions for Bayesian phylogenetic inference (Zhang & Matsen IV, 2019). Given leaf set X' of size N, one can define a subsplit Bayesian network Bx to be a Bayesian network whose nodes take on subsplit or singleton clade values that represent the local topological structures of trees (Figure 4. This formulation allows to represent rooted tree topologies as SBN assignments. More specifically, one can follow the splitting process (see the solid dark subgraphs in Figure middle) of the tree and assign the subsplits to the corresponding nodes along the way to get a unique subsplit decomposition of the tree topology. Given the subsplit decomposition of rooted tree T {s1, .2,...). where 81 is the root subsplit, the SBN CdN-induced tree probability of is
Psbn (7 = =T = p(S) = 81) II p(S. = 8: ST = 8T,)
1>1
where S; denote the subsplit- or singleton-clade-valiee index of the parents of S,. As Bayesian networks, SBN-induced distributions are all naturally normalized. We can also adjust the structures of SBNs for a wide range of expressive distributions, as long they remain valid directed acyclic graphs (DAGs). In practice. the simplest SBN (the one with full and complete binary tree structure as shown in Figure 4 is often found to be good enough.
random variables at node i and π; is the
The SBN framework also generalizes unrooted trees, which are the most common type of phyloge- netic trees. The key is to view unrooted trees as rooted trees with missing roots. Marginalizing out the unobserved root nodes leads to the SBN probability estimates for unrooted trees
p(S = $1) II p(S, = s,|S.. 8x.)
Pabn
1>1
where means all root subsplits that are compatible with (i.c., root subsplits of the edges of r).
We can evaluate the SBN probabilities of tree topologies efficiently through a two pass algorithm (Zhang & Matsen IV 2018). As Bayesian networks, SBNs also allow fast sampling procedures (i.e.,
ancestral sampling). These properties make SBNs a natural choice for variational inference.
Parameterizing SBNs in VBPI requires sufficiently large subsplit support of CPTs (i.c., where the associate conditional probabilities are allowed to take nonzero values) that covers favorable parent child subsplit pairs from trees with high posterior probabilities. In practice, simple bootstrap- approach has been found effective for providing such support (Zhang & Matsen IV] 2019). Let S, denote the set of root subsplits (e.g., the splits) in the support and Schipa pa denote the set of parent-child subsplit pairs in the support. The CPTs can be defined via the softmax function as follows
exp(1ss)
exp((aj()
p(S = =1) Eaess )
p(S: = =sSa, =)) Eoes,, exp(()s1)
13

---

Published as a conference paper at ICLR 2023
B THE TWO-PASS ALGORITHM FOR INTERIOR NODE EMBEDDING
Due to the hierarchical structure of phylogenetic trees, we derive a linear time two-pass algorithm for solving the linear equations In the first pass, we traverse the tree postorder fashion and express the node features as linear function of those of their parents as follows
Tx = Cr + dus
for all the nodes except the root node, where Nu is the parent node of For all leaf nodes E Vo, this is straightforward: C. = 0, d, = Tu. For any interior node u that is not the root node, as a result of postorder traversal, Cos dy available Vo E ch(u) when is visited. Therefore, we can rewrite the
equation about u in as
au ET. + Σ Zy
eFch(u)
DT. +
(Co + d.).
vEch(u)
This implies
Evech(u) de [((w) Evech(u) Co
Du
Tr..
[N(u) - Eeh((
which gives the recursive updating formula in equation 6
In the second pass, we traverse the tree in a preorder fashion. We first visit the root node r. From the first pass, Cu. de is available Ve ch(r). Similarly, from equation 4 we have
[ = Σ E
wEch(r)
Σ rEch(()
(crāe + de)
Therefore,
Evech(r) de
+ = [W((r) Evecher) Co
For any other interior node u, as a result of preorder traversal, Ex is available when is visited. We can compute its node feature T,, via equation
C PROOFS FOR LEMMAS, COROLLARIES, AND THEOREMS
Proof for Lemmal 1
Lemma 1. Let X = min [W( For all interior node u E vo)(r, 0 S cu S X-T
Proof. We prove by induction. Since [N(x)] > 2, Yu Va, we have X > 2. Note that C. O, Yu E yb Suppose 0 S cu S - i Vu ch(u), suffices to show that 0 S Cu S x as long as u is not the root node. From recursive updating formula, we have
0 S Cu = [(w) E Evech(w) Co
W Eveechnu)
WW(x)
Nial X-1
As X (((4))
2 (WV())) 2) - 2 20 (N()) - [Wu)) - --1 = (W(1)
W(2)) -
A-1 2 A 1
Therefore, 0 cu v X-I'
1
Remark. For bifurcating phylogenetic trees, have À = 3 = 0 Gv S
14

---

Published as a conference paper at ICLR 2023
Proof for Lemmal 2
Lemma (Extremum Principle). Let f E R E V be a set of d-dimensional node features that satisfies equations 4 L1 S n S d, let X[n] (TuInllu V} be the set of the n-th components of node features. Then, v1 S n S d, we have: (i) the extremum values (i.e., maximum and minimum) of X [n] can be achieved at some tip nodes; (ii) if the extremum values are achieved at some interior nodes, then X [n] has only one member, in other words, Bu[n]] is the same Vu V.
Proof. From equations
we have
Σ Z. eEV(u)
[Wu)]
In other words, for any interior node, its node feature is the mean of those of its neighbors. Therefore, V1 S n S the extremum values of X [n] can be achieved the boundary of the graph, i.c., the tip nodes. On the other hand, if the extremum value of [n|] is achieved at some interior node u, then the extremum also achieved at all the neighbors of u. Since the tree topology is connected, this implies that [n] is constant Vu E V.
Proof for Theorem
Theorem 1. Let N be the number of tip nodes. Let (Tu. IR- E V) be the solution to the linear system with one hot encoding for the tip nodes. Then, Vu E Vo, we have
Σ N
< <1, SInnSN, and (ii)
Duin| =1
Proof. As the tip node features = {o E II æ[n] 1} and Ps be the projection onto S. Since (ā, RR Iu E V solves the linear system it minimizes the Dirichlet energy. Now consider its projection (Ps(@.) RNIu- E V). Since one hot vectors are in S, Ps( Tu, vu E Vd, Note that Ps is projection operator, have
hot vectors, (i) follows immediately from Lemma 2 Let
Σ [Pss( (s( (M,))E
Σ (a.1)E
L. 20.1
Note that ( RR- |u E V) minimizes the Dirichlet energy, the equality has to hold which implies that G. 3. parallel the hyperplane S, V(u, v) E. Therefore, ā., S, Vu E V the tree topology is connected and the tip node features are already in S.
Proof for Corollary
Corollary 1. Suppose that the tip node features are linearly independent. the interior node features obtained from the solution to the linear system 7all lie in the interior of the convex hull of all tip node features.
Proof. Let A be matrix whose columns corresponds the tip node features. From the linear system we see that all interior node features lie in the column space of and hence can uniquely represented
T. = Aÿu, Vu E the columns are linearly independent. Moreover, (Ūn. system
I V} satisfies the linear
Σ (E)
U - v.) = Vu E Vo,
To Yos
Ve Vb
where (yo E ERN td one hot encoding vectors. By Theorem I have Vu V
N v S, N, and (ii) Σ
i 0 J.
< 1,,
[n] = 1.
n=1
which concludes the proof.
15

---

Published as a conference paper at ICLR 2023
Proof for Lemma 3
Lemma 3. Let {Tulu V be the solution to the linear system with linearly independent tip node features. Let (Tn - a. Vo} the convex combination representations of the interior node features. For any tip node v E Vb, we have
u' = arg max dy weV-
+ u =uE
Proof. For any tip node Vd, let & (V)) be the adjacent interior node of v. It suffices to show that oz au, Yu E (o) As {æ,lv V*] are linearly independent, from equations we have
EmeNtng % [(()]
V Vo.
(11)
Now consider for all interior nodes except E, the maximum value of {a-lu E VM therefore can be achieved at either the boundary of or As a 0, Vu (o) and a 0 (by Corollary [ the maximum value hence is achieved at a.) i.e., 0g 2 a. Vu E Vo. Now suppose there exists an interior node o such that a a.. Similarly Lemma this implies a,, az Vu V\fu), which is an obvious contradiction.
topology 7' that has removed from т. Note that equation 11 still holds
Proof for Theorem 2
Theorem 2 (Identifiabilitty. X (āu E Vo] and Z = {Zulu E Vo} be the sets of interior node features that minimizes the Dirichlet energy for phylogenetic tree topologies Ta and respectively, given the same linearly independent tip node features. If X Z", then T2 = T2-
Proof. Consider the case for unrooted trees first. We prove by induction on the number of tip nodes N of the tree topology. For N = 3. the tree topology is trivial. If N > 3, then for each tip node, its adjacent node by convex combination coefficient maximization. As the number of interior nodes is less than the number of tip nodes, there must be tip nodes that connect the same interior node. Merging the two tip nodes into their shared neighbor reduces the problem to size N with the shared neighbor being the new tip node. It is easy check that for this new set of node features, the tip node features are also linearly independent. Therefore, the remaining part of the tree topology can be recovered by induction hypothesis. The proof for rooted trees similar. N
LemmaßBidetiine
D MORE RESULTS ON AMORTIZATION GAPS
Table 2: Amortization gaps trees in the 95% credible of DSI.
SPLIT
PSP
MLP
GCN
GIN
SAGE
GGNN
EDGE
TREE 24
1.53
1.81
0.89
1.28
0.56
0.52
0.54
0.55
TREE 1.66
1.82
1.02
1.29
0.61
0.63
0.56
0.50
TREE 36
4.11
3.79
2.48
2.31
1.68
1.28
1.25
1.00
AVERAGE
2.06
0.89
0.87
0.94
0.63
0.63
0.57
0.53
E RELATED WORKS
Many deep learning approaches have also been proposed for phylogenetic models recently. Sooii Lemus et al. (2022) use cemmetry-preservingg neural networks to explicitly encode permutation invariance of phylogenetic trees. However, their method requires enumeration of all permutations of tip nodes that would leave tree topologies unchanged and hence challenging to extend to datasets with many sequences. Jiang al. (2022) leamn hyperbolic embeddings of gene sequences for phylogenetic tree placement and updates. While these embeddings maybe useful for sequentially updating species trees with only handful of genes, they not suitable for learning representations
16

---

Published as a conference paper at ICLR 2023
of tree topologies and their local structures with given taxa set. Fioravanti al. (2018 CNNs to incorporate phylogenetic information for the classification of metagenomics data where the phylogenetic tree is assumed to be known. Their method, therefore, is also not suitable for phylogenetic inference where the tree topology is unknown and needs to be inferred from the data.
F DETAILS ON GRAPH CONVOLUTIONAL OPERATORS
The followings are the update and aggregate functions for the graph convolutional operators used in experiments.
Graph convolutional networks (GCN)
((()) me (t-1)
h
h (++1)
m
m
(++1)
E
v1 + diy
+I+
uEA(O)U(Ut
where d, is the degree of node u.
Graph isomorphism networks (GIN)
h((+)) MLP(() (1+ + m(t1),,
m
m((1)=
Σ h
(EN(N)
where e(*) can either a learnable parameter or a fixed scalar.
GraphSAGE operator (SAGE)
EveNio) he d,
h (++1) = w/(h
(+) 1 + m
((+1))
Gated graph convolutional operator (GGNN)
h ((+1) = GRU()) (m(+t)) (++1) (1))
(++1)
Σ
1000 (0)
mEN(w)
where GRU(O) is Gated recurrent unit, a gating mechanism in recurrent neural networks.
Edge convolutional operator (EDGE)
(++1)
((+1)
e MLP(() (n. h -1(0))
nn9). Vu (N)
(e)(
where meaas concatenation and e is the edge feature from node to node
17


Reviews:
[{"review_id": "ZdifDOZmYb", "reviewer": "Reviewer_b2oj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n\n***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. \t", "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.", "strength_and_weaknesses": "***Strengths***\n1. 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. \n2. 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.\n3. 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.\n\n***Weaknesses***\n1. 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? \n2. 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?\n\n- [Thomas 1949] Elliptic problems in linear difference equations over a network. 1949\n- [Solis-Lemus 2022] Accurate Phylogenetic Inference with a Symmetry-preserving Neural Network Model. 2022\n- [Jiang 2022] Learning Hyperbolic Embedding for Phylogenetic Tree Placement and Updates. 2022\n- [Fioravanti 2017] Phylogenetic convolutional neural networks in metagenomics. 2017", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3HX2BSu8BGu", "reviewer": "Reviewer_Qbs2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "Strengths:\n\nRigorous 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.\n\nGood 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).\n\nReasonable testing approach which makes it directly comparable with previous work on the topic as well as other state-of-the-art methods.\n\nWeaknesses:\n\nIt 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?\n\nThe 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).\n\nThe 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.\n\nA 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-EyNaIh672m", "reviewer": "Reviewer_uXSY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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. ", "strength_and_weaknesses": "Strength:\nThe 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. \n\nWeakness:\nI 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?\n\nThe 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. \n\nIn 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?\n\nI 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. \n\n\nMinor comment:\nThere is a type after equation (1). I believe the root node is \\tao instead of r?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster