Solving the Tree Containment Problem Using Graph Neural Networks
Authors: Arkadiy Dushatskiy
Esther Julien
Leen Stougie
Leo van Iersel
Venue: Accepted by TMLR ()

Abstract: \textsc{Tree containment} is a fundamental problem in phylogenetics useful for verifying a proposed phylogenetic network, representing the evolutionary history of certain species. \textsc{Tree containment} asks whether the given phylogenetic tree (for instance, constructed from a DNA fragment showing tree-like evolution) is contained in the given phylogenetic network. In the general case, this is an NP-complete problem. We propose to solve it approximately using Graph Neural Networks. In particular, we propose to combine the given network and the tree and apply a Graph Neural Network to this network-tree graph. This way, we achieve the capability of solving the tree containment instances representing a larger number of species than the instances contained in the training dataset (i.e., our algorithm has the inductive learning ability). Our algorithm demonstrates an accuracy of over $95\%$ in solving the tree containment problem on instances with up to 100 leaves.

Published in Transactions on Machine Learning Research (06/2024)
Solving the Tree Containment Problem Using Graph Neural Networks
Arkadiy Dushatskiy
Arkaddy, Dushatskky@ww.....
Centrum Wiskunde & Informatica Amsterdam, the Netherlands
Esther Julien
E.A.T.. Tulieellll
Delft University of Technology Delft, the Netherlands
Leen Stougie
Leen. Cwen.Stougie@Bwv..c ml
Centrum Wiskunde Informatica Vrije Universiteit Amsterdam Amsterdam, the Netherlands
Leo van Tersel
L.J.J.vanlerrooOhhddift.t.
Delft University of Technology Delft, the Netherlands
Reviewed OpenReview: https: openreview. net/ forum? id= Id=nnnMoze.pn
Abstract
TREE CONTAINMENT fundamental problem in phylogenetics useful for verifying a pro- posed phylogenetic network, representing the evolutionary history of certain species. TREE CONTAINMENT asks whether the given phylogenetic tree (for instance, constructed from DNA fragment showing tree-like evolution) is contained in the given phylogenetic network. In the general case, this is an NP-complete problem. We propose to solve it approximately using Graph Neural Networks. In particular, we propose to combine the given network and the tree and apply a Graph Neural Network to this network-troe graph. This way, we achieve the capability of solving the tree containment instances representing a larger number of species than the instances contained in the training dataset (i.e., our algorithm has the inductive learning ability). Our algorithm demonstrates an accuracy of over 95% in solving the tree containment problem on instances with up to 100 leaves.
1 Introduction
Evolutionary trajectories of biological species can be described using directed acyclic graphs called phyloge- netic networks, which allow the representation of common evolutionary events such as lateral gene transfer and hybridization (Rapleste et al. 2013). Leaves of phylogenetic networks are labeled with the names of studied species. In many cases, some parts of the DNA structure evolve graphs that are trees (Jansson & Murakami, 2021). A valid phylogenetic network representing the evolution of certain species should be consistent with the previously built trees, namely, it should contain the trees which represent the evolution- ary history of some pieces of DNA of the considered species. Consequently, mathematical problem arises called TREE CONTAINMENT: the task is to determine whether a given phylogenetic tree is contained by a given phylogenetic network.
In general, the tree containment problem NP-complete (Kanj al. networks (with certain topological restrictions). polynomial-ting time algorithms (in some cases, even linear) were
2008 However, for some classes of
proposed, e.g., by Janssen & Murakami 2020), Gambette et al. 20018) and Janssen & Murakami 2001

---

Published in Transactions on Machine Learning Research (06/2024)
An algorithm that solves the tree containment problem should make use of the labels of the leaves of both the given phylogenetic network and the tree, as the containment property depends on them (the formal definition is provided in Section 3.2). This naturally poses a challenge in using machine learning approaches to solving it. It especially difficult to handle situations when the number leaves the test instances can be larger than the training ones. In this paper, we propose to lackle this challenge and develop an approach to approximately solving TREE CONTAINMENT, including instances for which no polynomial-time algorithms are known. The main contributions of this paper can be formulated as follows:
We propose an approximate solution to the NP-complete tree containment problem using Graph Neural Networks. To the best of our knowledge, this is the first time machine learning approach has been proposed to address this problem. Our approach can be applied to evaluate the quality of a constructed phylogenctic network: it can be used to efficiently and with high accuracy estimate whether trees (e.g,, gene trees) are contained in the built network.
Our proposed approach demonstrates a generalization ability: when trained on smaller instances (phylogenetic networks and trees with smaller number of studied species), achieves high accuracy (on average, over 95%) on larger instances not included in the training dataset. This inductive learning ability is achieved through specific technique: combining the given phylogenetic network and tree into single graph while respecting the labels of the leaves, which is crucial for solving the tree containment problem.
3. This work shows the potential of using GNNs for solving phylogenetic problems. Potentially, ideas from the proposed approach to solving tree containment, might be applied to solving other phylo- genetic problems well.
2
Related work
Graph Neural Networks
Graph Neural Networks (GNNs) are broad class of deep neural networks, which can be applied to solve graph problems (c.g., node and edge classification, graph classification) and can learn mcaningful representa- tions of nodes, edges, and entire graphs. Message Passing Neural Networks (MPNN) (Gilmer et al. 2017) is a general framework of neural wetworks for graphs. In each layer of an MPNN, each node receives messages containing information about its neighbors, then those messages are aggregated and combined with the node information itself. Examples of popular algorithms which use the cassage-passine paradigm are Graph Con- volutional Networks (GCN) (Kipf & Welling 2017), Graph Attention Networks (GAT) (Veličković et. al. 2018), GraphSAGE (Hamilton et al.J (2017], and GIN (Xu et al. 2019). The comprehensive overview of deep learning methods for graphs, including the recently proposed and non-MPNN ones can be found in
Khoshraftar & An (2024).
GNNs for directed graphs
The phylogenetic networks and trees in the tree containment problem are naturally directed graphs. Most of the GNNs work with undirected graphs. However, many real-world graphs are directed, and therefore several approaches have been proposed to adapt GNNs to directed graphs, e.g., (Zhang et al. 2021b). Recently more general approach to using GNNs for directed graphs was proposed in Rossi et al. (2023). This approach called Dir-GNN performs message passing in two directions (basically transforming the graph to an undirected one), but considers each direction of message passing separately with its own learnable weights for each. This ultimately results GNNs with more expressive power (Rossi et al. (003)). Dir-GNN was shown to be a general approach applicable different GNNs such as GCN (Kipf & Welling 2017). GAT VVličković al. 2018). and GraphSAGE (Hamilton et al. 2017)
2

---

Published in Transactions on Machine Learning Research (06/2024)
The tree containment problem
Different approaches have been proposed to solve TREE CONTAINMENT in polynomial time for some specific classes of networks (that have certain restrictions on the structure). Examples of such classes are binary ncar-stable networks (Gambotte ct al. 2018) and binary tree-child networks (Gunawan 2018). In Jansson & Murakami (2020), a more general version the tree containment problem was considered (a network in network containment instead of tree in network containment), and a linear-time algorithm was proposed solve this problem for semi-binary tree-child networks. In the follow-up work (Janssen & Murakami 2021), linear algorithm for tree (network) containment was also proposed for the so-called cherry picking networks and rigorous prools of algorithm complexity were provided. A different approach was proposed in van Tersel et al. (2023), and Huijsman 2023): the main idea behind it is to design an algorithm that has an exponential time complexity in terms of some input parameter, which results in a polynomial complexity when this parameter constant parammee tractability). Specifically, the treewidth (measuring the tree-likeness of network) was considered as such a parameter.
Solving hard problems with Graph Neural Networks
GNNss have been applied to solving challenging, in many cases, NP-complete and NP-hard combinatorial probloms such as Traveling Salesman, Maximum Cut, Minimum Vertex Cover (Barrctt al.) 2020 Cappart
et al. 2023 Li et al. 2018 Kool al.) 2019). Usually, in such approaches, it proposed to use GNNNs part of the reinforcement learning algorithms: they can extract useful features from a problem instance and partial solution, and help in building high-quality solution further.
GNNs were also applied to solving similar type of combinatorial problem to the considered tree containment problem: graph matching and (sub-)Graph Edit Distance (GED) calculation problems. There is a rather broad collection of works in which GNNs are applied to (sub)graph matching problems. One common approach [Bai et al., 2019 2020 Lou al., 2020) is learn meaningful embeddings of two graphs and then use them inputs to the predictor, which outputs the distance between the graphs. An alternative approach that is used, for instance, in Doan et al. 2021 Bai et al. 20200) is to have explicit algorithm of matching the nodes of one graph with the corresponding nodes of another (using the learned node-wise embeddings). In Zhaagg et al. (2021c) it was proposed to use the hypergraph concept to further improve the algorithm performance. Recently, [Ranjan et al. (202)) proposed essentially a simpler approach to (sub)graph edit distance learning that demonstrated state-of-the-art performance outperforming previous works such as Lou et al. p. : In contrast to previous works, it does not construct an explicit node-to-node similarity matrix, but instead just translates the distance between embeddings of two graphs into their distance function. The embeddings of two graphs are obtained using Siamese GNNs similar to Xu et al. (2019).
We note that the above-mentionel approaches to the graph matching and GED problems are not directly applicable to TREE CONTAINMENT as, in contrast to the standard graph matching formulation, it has some specific rules on node mapping, ie., leaves mapping should respect their labels (more details are provided in Section 3.2)
To the best of our knowledge, applying GNNs to solving phylogenetic problems has not been widely explored yel. The existing works in this field (Zhang, 2022; Mimori & Hamada 2023) mainly focus on the learning node representations in the scope of phylogenetic inference, and note that the phylogenetic problem considered in this work is different from that.
3 Preliminaries
3.1
Phylogenetic networks
A rooted phy poglogene network constructed for a set of taxa X is a directed acyclic graph (DAG) with leaves labelled from the set of labels x E X and with some specific restrictions on the in- and out-degrees of the nodes: the network contains a single root (in-degree zero); all other nodes are either a leaf (in-dogree onc, out-degree zero), tree node (in-degree one, out-degree greater than one), or a reticulation node (in-degree greater than one, out-degree one). In this paper, we consider binary phylogenetic networks, meaning that
3

---

Published in Transactions on Machine Learning Research (06/2024)
in- and out-degrees of all nodes are at most two. A phylogenetic tree is special case of phylogenetic network: it is phylogenetic network that contains no reticulation nodes.
(a) A phylogenetic tree.
(b) A phylogenetic network that contains the given tree (a).
(c) A phylogenetic network that does contain the given tree (a). Note: the leaves' labels have dif- ferent left-to-right order.
Figure/ Examples of the tree containment problem instances: tree (a) and two networks, one (b) does contain the tree, and one (c) does not. Leaves are labeled with letters (representing set of taxa). The mapping between the edges of the tree (a) and the paths of the network (b) (as explained in Section is exists.
depicted with the dashed curves with of corresponding colors. For the second network (c) no such mapping
3.2 Tree containment problem
The tree T (in the general case, network), T
contained (alternative terms embedded and displayed also be used) in network N EX) if there exists injective mapping of the nodes of T to the nodes of N: V" + V and edges of T to node-disjoint paths in N, such that the leaves' labels are preserved and the mapping of the edges respects the mapping of the nodes. In other words, T is contained in N, has a subgraph T', such that it can be obtained by replacing some edges of T by (directed) paths. Examples of cases where a tree is contained and not contained in a network are shown in Figure [] this paper, we consider the problem of determining whether a phylogenctic tree on taxa X contained binary phylogenetie network on the same laxa X: given tree T and network N, the task is to give answer whether I' is contained in N not:
NETWORK CONTAINMENT
Input: binary phylogenetic network N and tree T, both have the same set of leaf labels X Question: is T displayed in N?
In the general casc, when the network does not belong to one of the specific classes, c.g., tree-child networks [Pons & Batle 2021) (such networks that each non-leaf node has child that is either tree vertex leaf), this is NP-complete problem (Kanj et al. 2008).
4 Solving the tree containment problem using a GNN
4.1 The summary of our approach
The primary challenge when applying a GNN lo solve the tree containment problem involves ensuring its awareness of the labels on the leaves while retaining the ability to generalize to instances beyond the training set (inductive lcarning ability). For example, employing the labels of onc-hot encoded leaves as node features, (as, e.g., in Zhang al. (2021a)), does enable inductive learning ability. Completely ignoring the labels of the leaves is naive approach that, generally, not. be expected to work well, because the answer to
4

---

Published in Transactions on Machine Learning Research (06/2024)
the tree containment problem might differ for two pairs (N. and (N', T') where N and N' have identical topologies but different leaf labeling (similarly for T and T').
Our proposed approach to address the aforementioned challenge of applying GNNs is as follows: we combine a network and a tree into a larger network-tree graph, ensuring shared corresponding leaves. This graph is also called the display graph in the phylogenetic literature (Bryant Lagergren 2006 van Tersel et al. 2023). This process illustrated in Figure 2 (left side). With this technique, the labels of the leaves are taken into account in the network-tree graph construction they should be considered to correctly solve the tree containment. However, do not use the specific leaves' labels (for instance, node features), therefore, this approach, potentially, can work with the labels which have not been seen in the training data. In other words, it holds the potential to enable inductive learning ability.
GNN
Network
Tree
Nade-seee Ientumes
Consaimnned
ambedsings
Nodevalon enthacdings ctrainse with bijens
Crophration writedding
Combined network-Iree graph
+
MPP
Final pradiction
Figure 2: The schematic illustration of our approach ( (Combine-GNN), To solve a tree containment problem for the given network and tree, we start by combining them in a single graph such that the leaves are shared, respecting their labels. Then, GNN is applied. We note that the input node features do not contain the leaves' labels. The GNN consists of multiple layers, then the obtained embeddings concatenated, and node aggregation (graph readout) is applicd. Finally, an MLP is used to produce the final prediction.
After obtaining a network-tree graph, we apply a GNN to it. The architecture of the used GNN is depicted in Figure (right side). The goal of the GNN is to extract the necessary information from the graph structure and produce the answer to the tree containment problem. First, we use a multi-layer message-passingg GNN obtain meaningful emboddings the nodes (a comprehensive survey of various GNNs can be found, for instance, in Hamilton (2020))
As the considered phylogenetic networks and trees are directed graphs, simply transforming them into undirocted ones before passing to GNN might lead to the loss of some information. On the other hand, passing GNNs cannot. be efficiently applied to our problem as, for instance, leaves, would not pass any messages (their out-degree zero) to other nodes, and this also leads to the loss information. To take into account the directed nature of the graphs in the tree containment problem, we use the Dir-GNN approach (Rossi et al.) 2023). It allows bi-directional message-passing,, but has separate learnable weights of AGGREGATE, operations in each direction. The messagepassing part of the GNN in approach is therefore as follows:
if the graphs are kept directed, without special adaptations, message- meesagg-passing
4, + AGGREGATE, -- (L(a)) k-1 111)) (1,)) E))
AGGREGATE 1,4 (I(a) k- 1 (.11)) (i.)) ) E)) COMBINE"
(1/-1, (A
m m

---

Published in Transactions on Machine Learning Research (06/2024)
where z.f is node embedding (associated feature vector) of node at layer k m and m passed messages in two directions. AGGREGATE and COMBINE are crucial operations with usually learnable parameters (weights), and their specific implementations vary in different GNNs. For instance, in GCN Kipp & Welling, 2017), they are implemented as averaging with a consequent linear operation, usually followed by applying a non-linear function (e.g.; ReI.U).
After obtaining node-wise embeddings, we gather and concatenate the embeddings from different layers of the network, similar to the Jumping Knowledge GNN [Xu et al. 2018 and Ranjan et al. 2022
finol < CONCATENATE((::: .... x..,. 1),
where L the number of layers, x are the features passed to the first layer. Here, we pass the normalized original node features of the graph, followed by a linear projection (this projection might, in principle, be omitted). With multiple GNN layers, we obtain a multi-scale representation of the graph nodes. Subse- quently, these concatenated embeddings are utilized to obtain the whole graph representation using one of the readout operations (e.g., an element wise average pooling). Finally, Multilayer Perceptron (MLP) is employed to make the final prediction:
G - (FAADUU((s] fin Finol output t MLP(G)
Final))
We call the proposed approach to solving the tree containment problem Combine-GND This name reflects the two main ideas behind it: combining a network and a tree in a single graph, and applying a GNN to it. The code and used tree containment instances are available at /oalbbbetttfatrs//eeebbbooo///// A
4.2 Node features
The considered phylogenetic graphs naturally do not have node features, except for the leaves (they have the labels). However, we generate some features as a preprocessing step in order to provide additional helpful information to GNN for solving the tree containment problem. We two types of features for the nodes of the obtained network-tree graphs: 1) In- and out-degrees of the nodes; 2) Node origin: for cach node of the network-tree graph, we specily whether the node was leaf, was part of the network or of the tree. This information is provided in the form of one-hot encoding. Without explicitly providing this information, the GNN can try to derive it implicitly, but this might complicate the learning process.
4.3 Time complexity
As analyzed, for instance, in Kipf & Welling (2017), the time complexity of a GNN consisting of multiple GCN layers is O(EE) (assuming the number of layers and node features are constants). In our case, this means [[Enetwwrkk] + [Ereel)), which is equal to O(JEnetwors] + [networkk) tree is larger than the network than it is definitely not contained in it, and we do not have to run the algorithm to determine the containment. O((Enetwork) is, in turn, equal to O(N) (N is the mumber of nodes in the network) duc to the sparse nature of binary phylogenctic networks. The usage of Dir-GNN and data preprocessing (obtaining the network-tree graph) do not change the time complexity of Combine-GNN, The data processing step (including the network- tree graph creation) has ((N) complexity: creating node features (specifically, indicators of the node origin, see Section 4.2 has linear complexity as the features need to be created for each node.
((Enetvorrk) because if a
5 Experiments
5.1 Data
Our datasets consist of network-tree pairs (N, T) along with corresponding labels indicating tree containment (label "one" indicating the network contains the tree, label "zero" indicating containment).

---

Published in Transactions on Machine Learning Research (06/2024)
Synthetic data
The data generation process is similar to the one used in Bernardini et al. (202)). First, we generate a network using a Lateral Gene Transfer (I.GT) generator from Pons el al. (2019) and randomly select a tree subgraph of it. This way, we obtain a positive example (the tree is contained in the network). To obtain nogative example (a tree is not contained in the network), we perform number of so-called tail moves (Janssen 2021 A tail move is defined on two edges edge f. with respect to the corresponding edges. A valid tail move guarantees that all necessary properties of the phylogenetic network (listed in Section (3) are kept intact. Furthermore, tail move does not change the main graph properties (number of nodes, number of edges, etc.). After performing a number of tail moves the tree containment is checked using the exact algorithm called BOTCH (van Tersel et al. 2023 Huijsman
(u,v) and J: it simply moves the node to the
2023).
Intuitively, determining whether tree is contained within network becomes more challenging when the network under consideration resembles another network that contains the specified tree. Thus, we can adjust the difficulty of the problem by varying the number of tail moves performed. A higher number of tail moves means greater modifications to the network, resulting in a network more dissimilar lo the original, which contains the given tree. We create rather challenging instances by using the number of tail moves sampled uniformly at random from the integers in the range [1:5].
We vary the number of leaves in the generated datasets. We consider two different scenarios: 1) Transduclive learning: the number of leaves in the validation/tes: instances does not exceed the number of leaves in the training data; 2) Inductive learning: the number of leaves in the validation instances is in the interval (Lerain: 2Ltrain), while the number of leaves in the training set is in [Lmin Lirain]. The minimum number of leaves Timin in all instances is 5, and the maximum number considered is 100. We sample the parameter a of the LGT generator uniformly randomly from [0.1;0.2]. The summary statistics of the generated graphs are provided in Appendix, Figure I0
In each setup (defined by the number of leaves in the training and validation/test instances), we have 10000 training samples (network-tree pairs), 1000 samples used as validation dataset, and 1000 for the test dataset.
Real-world data
For the the real-world experiments, we use the dataset of gene trees from bacterial and archaeal genomes (proposed in Beiko (2011). binarized in yan Iersel ct al.] (2022)). For each set of input troes, we construct a network with the minimized number of reticulations such that it contains all given trees using the TrivialRand algorithm from Bernardini et al. (2023). Then, to obtain negative examples, network similar to the synthetic datasets construction. As obtaining the correct tree containment labels using BOTCH is becoming extremely time consuming for large networks (that have large number of leaves and/or high number of reticulations), we limit the considered instances to maximum 50 leaves and 5 input trees. As we have limited number of real-world instances (less than 300 network-tres pairs for each value of L E (10, 20, 30, 40, 50}, we use them only as validation and test data while using the synthotic LGT data for training. We also do not specifically tune any hyperparameters on the real-world data. For this experiment, we sample the parameter of the LGT generator uniformly randomly from [0.3; 0.5] (to increase the number of reticulation nodes in the networks). The number of leaves in the train instances is from [5; 50) for all test instances.
perform tail moves the
5.2 Baselines
The first baseline we consider is a naive approach that disregards the labels of the leaves. Instead, it attempts to predict the tree containment property based on mamually generated features from both the network and the tree, such as the average distance from the root to the leaves. The complete list of used features is listed in Appendix, Table 2 We train an XGBoost model CChn & Guestrin 2016) using these features.
Next, we consider a Siamese GNN (similar to the GREED algorithm (Ranjan et al. 2022) applicd to the tree containment problem. We make it aware of the labels of the leaves by using one-hot encoding of the labels the node features. This approach does not enable the inductive learning ability, but could potentially
7

---

Published in Transactions on Machine Learning Research (06/2024)
work well in the transductive learning setting. Moreover, in theory, it use the automatically extracted features from the network and the tree (in contrast to the manually constructed features used in the first considered baseline).
5.3 GNN architecture and training hyperparameters tuning
We train GNNs using the AdamW optimizer (Loshchilov & Hutter 2017 with the cosine annealing learning rale schedule, number of training steps is 5000; batch size is 200 (similar parameters were used in Rossi el al. h2023))
We performed a grid search to find the best performing architecture and the corresponding training hy- perparameters for Combine-GNN. The tuned hyperparameters and their ranges are the following (the best values are underlined): initial learning rate: {10-4, 10-3, 10 10-3); weight decay: {0, 10-4, 10 10-3}: dropout: {0.0, 0.2}; number of GNN layers: {3,5), size of node embeddings: {32, 64, 128}; type of GNN operation: {GCN, GIN, GAT); readout operation: {mean, max, sum}. Grid search hyperparameter tuning was also performed for the baselines. The best hyperparameters for them are provided in Appendix, Table 1 During hyperparameter tuming, we used validation subsets and random seeds different from those used to report our main results.
5.4 Performance evaluation
We use the balanced accuracy score (Brodersen et al. 2010 as our quality metric. Although we aimed at creating as balanced datasets as possible (as shown in Appendix, Figure I0), they are not perfectly balanced (multiple tail moves could still result in a network that contains the trec, though this is unlikely). Thus, we use balanced accuracy instead of standard accuracy. In all experiments, we report the results of test datasets using the epoch at which the best performance on the validation dataset was achieved.
We compare the performance of Combine-GNV with the aforementioned basclines. Furthermore, we study the scalability of Combine-GNN in terms of the training dataset size and increasing size of the test instances (in the inductive learning sctup). Finally, we specifically study how the different design choices of the GNN used in our algorithm affect the performance. The results of statistical significance testing are provided in Appendix, Table 3
We also empirically study the time-wise complexity of Combine-GNN (inference time) compared to the exact algorithm for the tree containment problem, namely, BOTCH (van lersel et al. 2023 Huijsman 2023 For this analysis, specifically consider more challenging instances, excluding tree-child phylogenetic networks, because for them the tree containment can be solved in linear time. We note that, for rigorous time analysis, we adopt a conservative approach in estimating the time performance of Combine-GNN: processing one sample at a time (without using batching) and assuming that both data and the GNN need to be transferred to the GPU each time a sample is processed. This approach differs from a more practically realistic scenario where the model is created and transferred the GPU only once. We use a system with Intel(R) Xe) Silver 4110 CPU and Nvidia GeForce RTX 2080 Ti GPUs (for this experiment, only one GPU is utilized).
6
Results
The main results are shown in Figure g inductive and transductive learning settings: the average balanced accuracy is 0.958 and 0.970 respectively, in most runs across datasets of different sizes the accuracy is 0.95. Notably, its performance does not substantially deteriorate on larger instances.
We see that Combino-GNN shows good performance in both
As anticipated, the baseline GNN approach, utilizing one-hot encoding of the leaves, exhibits better per- formance in the transductive setting (albeit substantially lower than Combine-GNNY than in the inductive setting. The baseline which uses XGBoost on the manually engincered fcatures shows reasonably good performance, but its underperfornance compared to Combine-GNN indicates that relying solely on general network and tree characteristics does not suffice to accurately determine tree containment.
8

---

Published in Transactions on Machine Learning Research (06/2024)
Inductive
transductive
1.00
Combine
0.95
Baseline: GNN
Baseline: XGBoost
0.90
0.85
0.80
accurso
0.60
0.55
0.50
Loan [5.10]
[5,20]
[5,30]
15, |0
[5,50] (50,100]
[5.10] [5,10]
[5,20]
[5.30]
[5,40]
[5.50]
Fest (10,20)
(20,40)
(30,60]
(40,80)
[5,20]
[5,30]
[5,40]
[5,50]
number of leaves in training and sets
Figure Main results: performance of our algorithm and the baselines in terms of (balanced) accuracy on different datasets; the left part of the graph shows the results in the inductive setting, the right part of the graph shows the results in the transductive setting. For each dataset and each algorithm, perform five runs with different seeds. Bar height denotes the average values; error bars denote the 95% confidence interval.
Performance on much larger instances then used for training
The performance of GNmbine-GNN on test datasets with instances of increasing size (including those which are much larger than the instances contained in the corresponding training dataset) is presented in Figure 4 We observe that while the performance deteriorates with the difference between size of the training and test instances increasing, Combine- GNN demonstrates rather robust behaviour, for instance, when trained on instances with up leaves, the balancod accuracy score on datasots with instances with up to 100 leaves, stays above 0.9. This highlights the generalization ability of the proposed approach.
number of leaves the train instances
[5, 10]
[5, 20]
0.95
accuracy
0.9
0.85
0.8
[5,10] (10.20)
(30,40]
(50, 60]
[70,80]
(90,100]
number of leaves the test instances
Figure Performance (balanced accuracy) for test datasets containing instances with increasing number of leaves. The leftmost point in each line shows the performance in the transductive setup, the remaining ones show the performance in the inductive setup. The number of leaves in the test instances are sampled randomly uniformly from the specified interval. The results are averaged over five runs with different seeds.
Impact of the training dataset size
The performance Combine-GNi using training datasets of varying sizes is presented Figure 5 For a smaller number of samples, the number epochs has boen adjusted accordingly, so that the total number of processed samples during training is equal all cases (10%). We can conclude that a larger number of samples is clearly beneficial for the performance. It is plausible that using more than 10000 samples in

---

Published in Transactions on Machine Learning Research (06/2024)
1.0
Setup
inductive
transductive
0.95
accuracy
0.9
1k
2k
5k
10k
number of training samples
Figure 5: Performance (balanced accuracy) for training datasets of different sizes. The results are averaged over five inductive and five transductive learning setups with a different number of leaves and five runs with different seeds for each of them.
training datasets can result in higher accuracy scores. However, did not generate larger datasets due to the computational costs of generating true labels (scaling exponentially with the instance size).
Impact of the number of reticulation nodes
accuracy
0.9
0.85
Setup transductive inductive
0.8
8
10
12
14
16
18
20
percentage of reticulation nodes
Figure 6: Performance (balanced accuracy) for training and testing datasets with varying percentage of reticulation nodes. Here, the transductive setup denotes the test instances with from [5; 10) and inductive denotes the instances with from [LI;20]: The training instances in both setups have the from with [5; 10). The results are averaged over five runs with different seeds for each setup and each percentage of reticulation nodes.
The performance of Combine-GNN with training and testing datasets of varying number of reticulation nodes is presented in Figure 6 We use training datasets the datasets with instances with [5; 10] leaves and varying number of reticulations (by controlling the parameter in the LGT generator). The test datasets have been generated using the same correspondingly. We conclude that larger percentage (number) of reticulations makes the task much more difficult for Combine-GNI to solve. However, we note that in the transductive setup, the accuracy stays above 0.9 even for the dataset. with 200 reticulation nodes.
Real-world data results
The results for real-world data. experiments are shown Figure 7 experiment: the training data synthetic dataset generated using LGT generator (real-world data used only validation / test subsets); furthermore, the used hyperparameters were tuned synthetic datasets
We note the challenges posed in this
10

---

Published in Transactions on Machine Learning Research (06/2024)
1.00
Combine-GNN
Baseline:
0.90
Baseline: XGBoost
accureey
0.80
0.75
0.65
0.55
20
[10: 50]
number lnaves set instances worldd data)
Figure 7: Performance (balanced accuracy) for real-world data. The training data was generated using LGT generator. The results are averaged over five runs with different seeds for different inst sizes.
only; the real-world validation subsets are rather small causing potential overfitting on them (we choose the best epoch based on the validation performance).
Nevertheless, under all above-mentioned challenges, Combine- GoN demonstrates reasonably good accuracy, in particular, 0.798 (averaged over five seeds) when all considered real-world data (L {10, 20, 30, 40, 50)), is used for validation and test subsets. It also outperforms the baselines by substantial margin. Thus, we can conclude that Combine-GNi can generalize to the real-world data as well (in contrast to the baselines). Potentially, its performance might. likely be further improved by, for instance, specific hyperparameter tuning, or using more and/or diffcrent training data.
One of the reasons for lower performance of Combine- GNN on the real-world data the higher percentage of reticulation nodes (20% for L 10, 17.6% for L 50, slighly decreasing with the increase of L) than in the datasets used in main experiments (Figure 3 and hyperparameter tuning (the percentage of reticulation nodes there was less than 8%). Moreover, it was shown in Bernardini et al. (2023 that the LGT generalor does not generate the data that has exactly the same properties as this real-world dataset.
6.1 Runtime performance
The time performance (inference) results are shown in Figure First, we observe that the exact algorithm (BOTCH), as anticipated, takes exponential time to solve tree containment (on instances that are not tree- child networks). Our algorithm shows polynomial time complexity, namely, the best linear (in the log-log axes) fit. indicates the complexity of ((N0.21). Tn particular, we observe that for the considered graph sizes, the inference time itself scales extremcly well (sublincarly). The data processing step (including network-tree graph creation) has approximately linear complexity, as expected. The model creation time demonstrates approximately constant time complexity (the model size does not depend on the graph size).
6.2 Ablation studies
The results of all ablation studies shown in Figure g
Taking into account the direction of the edges
The use Dir-GNN demonstrates its advantage over a simpler approach that treats graphs as undiroctod. This is a reasonable behavior since relaining information about the edge directions in the given network and tree is expected to be helpful in solving the tree containment problem.
Node features
We observe that adding the origin of the node (whether it belongs the network, the tree, or a leaf node) to the nodes of the network-tree graph features leads to performance improvement. This is
11

---

Published in Transactions on Machine Learning Research (06/2024)
10.0
Combine-GNe cata processing Inference model creation
Combine-GNN
0.1
llnear fit: time -2200222
time (seconds)
time (seconds)
0.01
0.001
80
160
320
number of nodes
number nodes
Figure 8: Left: scalability of Combine-GNY (along with the best lincar fit in the log-log axes), and the exact algorithm (BOTCH) in terms of the required time to solve tree containment instances. Right: the breakdown of time consumption by Combine-GNN. We average all measurements over 10 runs, and use averaging the x-axis over 10 bins (the points denote the centers of the bins).
directions
using different features
GNN operation
readout
embedding
0.95
0.80
0.85
0.60
0.55
DI-ONN 25 undracadd grapts
type
Iype degrees
no
OCN
GN
GAT
max
Fum
maan
125
32
15
dagress
Figure 9: Effects of different design choices of Combine-GNN to the performance (balanced accuracy). Performance is averaged over five datasets in the inductive learning setup and five random seeds for cach dataset (25 values in total for each shown bar). Bar height denotes the average values; error bars denote the 95% confidence interval.
anticipated result, since these supplementary features explicitly convey to the GNN whether a node pertains to the network or the tree. We note that adding the node in- and out-degrees as additional features does not increase the performance further.
GNN architecture design choices
We study how different GNN operations (GCN, GAT, GIN) affect the performance. We can conclude that, while the GCN operation works better than the considered alternatives, both GAT and GIN operations also demonstrate reasonable performance. This highlights that our algorithm not strongly reliant on the GCN operation and suggests the potential for achieving even better performance by exploring different GNN operations.
Similar conclusions can be made about the graph-level aggregation operation: the used maximum pool- ing operation performs better than the considered alternatives (specifically, we note that the summation aggregation underperforms compared to the alternatives).
The embodding size appears be a rather important hyperparameter, while there no substantial differ- ence between performance of embedding size 128 and 64, the performance substantially deteriorates with embedding size 32, and especially, 16.
12

---

Published in Transactions on Machine Learning Research (06/2024)
7 Discussion
In this work, we demonstrated that GNNs can be used as approximate solvers of the tree containment problem, iee, they can predict whether a phylogenetic network contains the given phylogenetic tree or not with high accuracy. While this capability is valuable, for practical applications, an algorithm that not only provides containment predictions but also offers a solution representation might be advantageous. For instance, such an algorithm could generate a mapping between the nodes of the tree and the network, enabling solution verification. This verification process might help in filtering out false positíves in determining tree containment: ensuring that positive answer consistently reflects the true containment, although not all true positive cases may be correctly identified such. We consider this direction practically important direction of future research.
Another important direction of future work is exploring whether the proposed approach (or adaptations of it) can be applied to solving more general formulations of the tree containment problem, e.g., non-binary phylogenetic networks and the network (instead of a tree) containment. Such an adaptation might ease the application of the proposed approach to real-world phylogenetic datasets.
There are other problems in phy logenetics related to TREE CONTAINMENT, for instance, HYBRIDIZATION. For that problem, the input consists of multiple trees and the aim is to construct a phylogenetic network with at most à reticulation nodes such that it contains all input trees. Potentially, at least some of the ideas proposed in this work can be used to solve other phylogenetic problems such as HYBRIDIZATION, though we acknowledge that this non-trivial task and requires additional research.
8 Conclusion
In this work, we demonstrated how GNNs can be used to approximately solve an important NP-complete problem from the phylogenotics field: TREE CONTAINMENT. We proposed an approach named Combine- GNN that allows inductive learning: it consists of combining the given phylogenetic network and tree in single graph and applying a GNN to it. This way, we achieve the inductive learning ability: it work for instances with larger number of leaves (i.e., studied species) than the number of leaves of the training instances. Combine-Gai demonstrates high accuracy in both transductive and inductive learning setups with instances having to 100 leaves, clearly outperformigg more simple baseline approaches. Furthermore, we carefully studied how different design choices of our algorithm affect its performance. Overall, our results demonstrate that GNNs have grate potential phylogenetics.
Acknowledgements
The work in this paper is supported by the Dutch Research Council (NWO) through project OCENW.GROOTE 2019.015 'Optimization for and with Machine Learning (OPTIMAL)".
13

---

Published in Transactions on Machine Learning Research (06/2024)
References
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the twelfth ACM international Conference on Web Search and Data Mining, pp. 384 392, 2019.
Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning- based efficient graph similar- ily computation via multi-scale convolutional set matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34:4, pp. 3219 3226, 2020.
Eric Bapteste, Leo van lersel, Axel Janke, Scot Kelchner, Steven Kelk, James O Mclnerney, David A Mor- rison, Luay Nakhleh, Mike Steel, Leen Stougie, and James Whitfield. Networks: expanding evolutionary thinking. Trends in Genetics, 29(8):439 441, 2013.
Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial opti- mization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34:4, pp. 1443-2250, 2020.
Robert G Beiko. Telling the whole story in a 10,000-genome world. Biology Direct, 6:1 36, 2011.
Giulia Bernardini, Leo van lersel, Esther Julien, and Leen Stougie. Constructing phylogenetic networks via cherry picking and machine learning. Algorithms for Molecular Biology, 18(1):13, 2023.
Kay Henning Brodersen, Cheng Soon Ong, Klaas Enno Stephan, and Joachim M Buhmann. The balanced accuracy and its posterior distribution. In 2010 20th International Conference on Pallern Recogrition, pp. 3121-3124 IEEE, 2010.
David Bryant and Jens Lagergren. Compatibility of unrooted phylogenetic trees is FPT. Theoretical Com- puler Science, (3):2996 2006.
Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličkovié. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(13)):1-61, 2023.
Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785 794, 2016.
Khoa D. Doan, Saurav Manchanda, Suchismit Mahapatra, and Chandan K. Reddy. Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp.
665 674, 2021.
Philippe Gambette, Andreas D.M. Gunawan, Anthony Labarre, Stéphane Vialette, and Louxin Zhang, Solving the tree containment problem in linear time for nearly stable phylogenetic networks. Discrete Applied Mathematics, 246:62 79, 2018.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp. 1263-1272. PMLR, 2017.
Andreas DM Gunawan. Solving the tree containment problem for retieulation--viiibee networks in linear time. In Algorithms for Computational Biology: 5th International Conference, AlCoB 2018, Hong Kong, China, June 25-26, 26, 2018, Proceedings 5, pp. 24 36. Springer, 2018.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30, 2017.
William L Hamilton. Graph representation learning. Morgan & Claypool Publishers, 2020.
Robbert Huijsman. Treewidth based algorithms for tree containment in phylogenetics. 2023. URL http: //resolver furessllver..udef.... 20e
14

---

Published in Transactions on Machine Learning Research (06/2024)
Remie Janssen. Heading in the right direction? Using head moves to traverse phylogenetic network space. Journal of Graph Algorilhms and Applications, 10:263-310) 01 2021.
Remie Janssen and Yukihiro Murakami. Linear time algorithm for tree-child network containment. In Algorithms for Computational Biology, pp. 93-107, Cham, 2020. Springer International Publishing.
Remie Janssen and Yukihiro Murakami. On Sherry-picking and network containment. Thcoretical Computer Science, 856:121 150, 2021.
Iyad A Kanj, Luay Nakhleh, Cuong Than, and Ge Xia. Seeing the trees and their branches in the network is hard. Theoretical Computer Science, 401 (11(133:153-164, 2008.
Shima Khoshraftar and Aijun An. A survey on graph representation learning methods. ACM Transactions on Intelligent. Systems and Technology, 15(1):1-50 1-5,, 2024.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Wouter Kool, Herke van Hoof, and Max Welling. Attontion, learn to solve routing problems! In International
Conference on Leurning Representations, 2019.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks
and guided tree search. Advonces in Neural Information Processing Systems, 31, 2018
Πya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference Learning Representations, 2017.
Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovee, et al. Neural subgraph matching. arXiv preprint arXix:2007.0888 03092, 2020.
Takahiro Mimori and Michiaki Hamada. Geophy: Differentiable phylogenetic inference via geometric gra- dients of tree topologies. In ICML 2023 Workshop on Differentiable Almost Everything: Differentiable Relozations, Algorithms, Operators, and Simulators, 2023.
Joan Carles Pons, Celine Scornvvccaa, and Gabriel Cardona. Generation of level-k LGT networks. IREE/ACM Transactions on Computational Biology and Bioinformalics, 17(1):158-166 164, 2019.
Miquel Pons and Josep Batle. Combinatorial characterization of certain class of words and a conjectured conncction with general subclasses of phylogenctic tree-child networks. Scientific reports, 11(1):21875, 2021.
Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabharwal, and Sayan Ranu. Greed: neural framework for learning graph distance functions. Advances in Neural Information Processing Systems, 11:22518-22531 2022.
Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günnemann, and Michael Bronstein. Edge directionality improves learning heterophilic graphs. arXio preprint arXiv:2305. 10498, 2023.
Leo van Tersel, Remie Janssen, Mark Jones, Yukihiro Murakami, and Norbert Zeh. A practical fixed- parameter algorithm for constructing tree-child networks from multiple binary trees. Algorithmica, 84(4): 917-960, 2022.
Leo van lersel, Mark Jones, and Mathias Weller. Embedding phylogenetic trees in networks of low treewidth. Discrete Mathematics & Theoretical Computer Science, 22(2,, 2023.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Represendations, 2018.
15

---

Published in Transactions on Machine Learning Research (06/2024)
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning on graphs with jumping knowledge networks. Tn International Conference Machine Learning, pp. 5453 5462. PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? Tn International Conference on Learning Representations, 2019.
Cheng Zhang. Learnable topological features for phylogenetic inference via graph neural networks. International Conference on Learning Representations, 2022.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34: 9061-9073, 2021a.
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Malthew Hirn. Magnet: A neural network for directed graphs. Advances in Neural Information Processing Systems, 34:27003-2700 2021b.
Zhen Zhang, Jiajun Bu, Martin Ester, Zhao Li, Chengwei Yao, Zhi Yu, and Can Wang. H2mn: Graph similarity learning with hicrarchical hypergraph matching networks. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Dala Mining, pp. 2274 2284, 2021c.
16

---

Published in Transactions on Machine Learning Research (06/2024)
Appendix
250
network
Tranic network
250
200
Tost: network
Test network
Heb:: Iree
200
Text: trew
150
130
100
50
[5.10] (10,20)
[5,20] 120,40]
[5.30] (30
[3,40] (02,00]
5,50] (30,100)
[5.10] (10,20)
[5,20] (20,00)
[330] (50,00)
[5,40] (60,80)
[5.30] (50.100]
Setup.
Secup,
networe netwodk
1.000
(525) (20.00
150,000)
(5.05)
(5.20) 40) 15
(3.20119180)
15,50350.300
Figure 10: Number of nodes (upper left), number of edges (upper right), number of reticulation nodes (bottom left) and label (whether the tree is contained or not) statistics of the graphs in the used datasets.
GNN-based baseline
XGBoost-based based baseline
Hyperparameter
Considered values
Hyperparameter
Considered values
initial learning
{10-4 10-3, 10-2) [0,10- 10=3)
cstimators
[50, 300)
weight decay dropout
depth
[3,5, 10, None)
(..0.0.2}
learning rate
{10-4 10-3, 10-2 10-1)
number of GNN layers
[3.5]
mumber of leaves
{0, 10, 100)
size of node embeddings
[32, 64, 128)
subsample
{0.5, 0.9)
type of GNN operation
[GCN, GIN, GAT)
readout operation
mean, max, sum}
Table 1: Search spaces of hyperparameters for the considered baselines. The best values are underlined.
basic calculated values
calculated features
#N, #T: number of nodes in the network and the tree spectively
#T/#N
Ndepth/ #N
Ndepth network depth, deepth depth
Téepth/ #T
min( (dmetioork)) ) /edept
mean(dnetunn ))/Ndetth
min (dsree) /
mean (ean(deree) TTdepth
duetworks diree: arrays of distances the corresponding leaves network and tree respectively
min (nnewoork)
max(dtree)
(min (nstwork))
max (drree)))
//#
min dnnetwork
deree)
max max(d (dnetworkk
deree)
mcan (dnetwork
derce)
Table 2: The features used in the XGBoost-basee baseline.
17

---

Published in Transactions on Machine Learning Research (06/2024)
Experiment
Hypothesis
p-
value
Combine-GNN performs better than GNN haseline Combine-GNN performs better than XGBoost baseline
0.000
Main resulss
0.000
performs better than GIN GCN performs better than GAT
0.011
Ablation: GNN operation
max performs better than max performs better than
0.001
Ablation: readout operation
0.000
embedding size 128 performs better than embedding size 64
0.063
Ablation: embedding size
embedding size 128 performs better than embedding size 32
0,000
embedding size 128 performs better than embedding size 16
0.000
Ablation: using graph directionality
Dir-GNN performs better standard CNN (on undirocted graphu)
0.000
Using node type features node degree features performs better than using node type features Using node type features node degree features performs better than using degree features Using node type features and node degree features performs better than using no features
0.336
Ablation:
using different features
0.000
0.000
Table 3:
The results of stafistical significance tests. We the one-sided Wilcoxon test, testing differences between the balanced accuracy scores. Statistically significant results at 0.05 and applied Bonferroni correction (in each experiment, we apply the correction with set to the number of tested hypotheses) are highlighted with bold font. The p-values are rounded to three decimal places.
Setup
Balanced accuracy
Precision
Recall
transductive
0.970
0.958
0.986
inductive
0.957
0.942
0.976
Table 4: Balancod accuracy along with precision and recall metrics for Combino-GNN, These numbers are averaged over all inductive and transductive setups from Figure (main results).
18


Reviews:
[{"review_id": "DBzR0pY2aw", "reviewer": "Reviewer_FHbL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n• Applying Graph Neural Networks to solve the tree containment problem in phylogenetics is novel.\n• Based on the experimental results, the proposed approach shows a good generalization ability and achieves high accuracy, even though the training dataset is small.\n\nWeaknesses\n• The introduction of the background and the problem is brief. As a result, it is less accessible to people who are not in this specific field.  \n• The authors need to provide more technical analysis and more comparisons in experiments to convince readers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new approach to dealing with the tree containment problem in phylogenetics. It combines network and tree to generate a graph first, and then uses GNNs for prediction. The resultant model achieves a high accuracy of over 95% for instances with up to 100 leaves. Its performance is much better than baseline methods.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "• In Section 4, it is claimed that “implicitly incorporate the labels of the leaves without directly using specific leaves’ labels. This approach holds the potential to enable inductive learning ability since the labels of specific leaves are not utilized in any form.” Besides the empirical results, it would be better to provide theoretic analysis on generalization ability to support this claim. \n• Only using GNN and XGBoost as baseline methods for comparison is not sufficient for comparison. Please include more SOTA methods.\n• In Section 6.2, it seems that some experimental results for ablation studies are close to each other. Please also provide standard deviation in addition to accuracy.\n• Based on the experimental results, the performance of the proposed method is much better than that of baselines. Is there any limitation of this method? Please discuss it.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6vdJL1Pgww", "reviewer": "Reviewer_Yakq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pos: \n- the idea of combining the needle (tree) and the haystack (the network) so not to have to provide an explicit identity to the nodes is interesting \n- the ablation study shows which elements are important in the solution (as it turns out, the only important choice is to use a max or mean readout rather than a sum).\n\nNeg:\n- (acknowledged by the authors) the approach does not provide a mapping between the nodes of the tree and the nodes of the network so no verification can easily be carried out, i.e. the method is a black box oracle\n- no explanation is offered into understanding what can possibly have the model learned to be so successful in its predictions: the presence of reticulation nodes (up to 15 in a 200 nodes network) should exponentially mix the messages coming from the nodes, and the model would have to propagate information from (distant) tree nodes (without suffering from squashing effects) to learn to which nodes to pay attention to when aggregating information (although GATs are shown to be actually  performing worst than GCNs in this problem!). Without such knowledge it's hard to understand the limitations of the approach, i.e. have an intuition on when it will fail, or how it will degrade.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose to approximately solve the NP-complete problem of tree containment using a graph neural network approach. They empirically show excellent predictive performance, even in an inductive setting.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The dataset is constructed generating random binary trees with 5 to 100 leaves (and up to 200 nodes in total) and generating 10k examples for training and 1k examples for testing. With this amount of training the predictive performance is ~ 95% in the inductive setting, i.e. when training is done on graphs that are half of the size of the graphs used in test. \n\nI wonder if one could try to asses if the trees in the test set are not subgraphs of the trees in the training set. Wouldn't that constitute a form of data leak between the train and test if that would occur? \n\nIt would be informative to see some notion of performance degradation profile:\n- a learning curve would show the performance when increasingly less material is used for training \n- a graph that shows the performance vs the increase of the size ratio between the training and the test set should also be of interest (in the experiments reported the ratio is always 1:2)  \n- increasing the fraction of reticulations w.r.t. total nodes would be of interest as this affects the complexity of the problem to solve (in the experiments the ratio seems also fixed to ~ 1:10)\n- showing the relation between the predictive performance and the size of the node embeddings would also be informative", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ymlzSuGNdc", "reviewer": "Reviewer_zcx7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1.\tThe paper is the first to study the binary containment problem using a graph neural network approach. \n\n2.\tThe application of a directed GNN to the constructed display graph is innovative and effective.\n\n3.\tThe paper is clearly written. The binary containment problem is clearly explained for a non-expert (which is likely the case for most of the TMLR readership).\n\nWeaknesses\n\n1.\tAlthough the approach is innovative and appears effective, the technical contribution is \nrelatively minor. It amounts to constructing a display graph (which the authors state is common in the phylogenetics literature) and then applying a directed GNN (without any modification of the algorithm). The paper does not provide any insightful discussion or experimental analysis to explain why this approach is effective. \n\n2.\tThe paper does not provide a motivating text that explains why an approximate inference algorithm is satisfactory and how it would be used in practice. With this in mind, there is no clear justification of the selected performance metric. \n\n3.\tThe experiments are conducted for a single synthetic dataset. The paper does not provide any evidence that the proposed generation mechanism leads to networks that display the same important properties as the networks that would be encountered in a practical setting. With this in mind, it is not clear whether the proposed algorithm is only exploiting some distributional aspect of the generative mechanism that would disappear in a real dataset.\n\n4.\tThe ablation analysis does not contain enough detail. There are concerning experimental outcomes (outperformance of GCN, underperformance of summation). Given that there are no node features, the intuition is that the structural aspects of the constructed graph should be most important. Under such circumstances, an algorithmic combination such as GIN and summation would be expected to be the best choice. The paper should explain why this is not the case. Without such an analysis, there is a concern that the algorithm is learning some artefact of the synthetic data generation process.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the tree containment problem for binary phylogenetic networks and provides the first approximate inference algorithm based on a graph neural network. A key insight of the proposed technique is that the construction of a “display graph”, by merging the tree and the network into a single graph, making the leaf nodes common, is a vital step in rendering the GNN effective. The paper provides the results of an experimental analysis using synthetic data. These results indicate that the approach significantly outperforms a naïve GNN method or a xgboost method trained on handcrafted features. Results of ablation studies are provided to demonstrate the importance of different design choices.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.\tThe paper does not adequately motivate the use of a machine learning algorithm for this application. In particular, there is no explanation of how an approximate solution is useful. If the task is to determine “whether a given phylogenetic tree is contained…”,  under which circumstances is it useful/acceptable to provide an answer that is only correct 95 percent of the time? Please provide a clearer explanation of how the approximate algorithm can be used satisfactorily in practice. Does the false-alarm rate matter? Is accuracy the most appropriate metric?\n\n2.\tThe related work section on GNNs should be expanded to include more recent works. Given the enormous amount of work over the past 4 years, it is not reasonable to cite papers from 2017-2019. Yes, these are important papers that should be cited, but there have been major advances since then. By citing only a single paper (Rossi et al., 2023), the paper gives a misleading impression of the field. Requested change: Since the development of a novel GNN is not the focus of the paper, it would suffice to cite a recent review paper and include a couple of sentences that acknowledge that MPNNs are not the only approach. \n\n3.\tThe sentence “Through this technique, we implicitly incorporate the labels of the leaves without directly using specific leaves’ labels. This approach holds the potential to enable inductive learning ability since the labels of specific leaves are not utilized in any form.” \nThese two sentences are difficult to understand. They appear contradictory and it is not clear what support there is for the claim in the second sentence. The first sentence states that “we implicitly incorporate the labels”. The second sentence states that “the labels of specific leaves are not utilized in any form”. If they are not utilized (in any form), then why and how are they implicitly incorporated? Or is the word “specific” supposed to be important? \n\nThe second sentence is a relatively strong claim and it is not supported by any argument or citation. Perhaps the claim should be reversed? There is a different meaning to the sentence “By avoiding the explicit use of the labels of specific leaves, this approach does not prevent inductive learning from occurring”. \n\n4.\tI don’t understand the purpose of presenting the application of the undirected GNN in Section 4.1 if the following Section states that the method actually uses a directed GNN. It would be much clearer just to present the directed GNN directly. If the authors feel that is important to present the operation of an undirected GNN as background material, then it would be better to include it in a separate section. I think the TMLR readership has sufficient familiarity with GNNs that there is no need. Readers who are unfamiliar can consult the paper by Gilmer or Hamilton’s book, for example. Requested change: Please move Section 4.2 into Section 4.1 so that the summary of the technique is consistent with what is actually implemented. \n\n5.\tThe approach appears heuristic in nature, amounting to “we construct a display graph and apply a directed GNN”. Can the authors provide a stronger argument as to why this approach works? Even if it is not possible to provide theory, the paper would be much stronger if it could provide an explanation of how the GNN can learn whether an injective mapping exists or not. Please provide some additional explanation or analysis that provides considerably greater insight into what is being learned. \n\n6.\tPlease explain why the paper only considers binary phylogenetic networks. It is not obvious that there is any aspect of the methodology that prevents application beyond the binary case. \n\n7.\tThe proposed technique is only tested on one synthetic dataset. Presumably the intention of developing this approach is not to apply the technique to synthetic data. Where is the evidence that this synthetic generation process leads to data that has the same distribution as real data? Why is it not possible to provide some example experimental results for real data? \n\n8.\tPlease provide more discussion and analysis of the dataset. Is it clear/known that the tail operations do not lead to an obviously different structure (in terms of basic graph properties)? \n\n9.\tThe discussion of the ablation study is insufficiently detailed. It is not enough to state that “summation aggregation underperforms” without any explanation. Why does it underperform? Summation is supposed to exhibit stronger inference capability than an averaging operation (see, e.g., the GIN paper). A result like the one presented here is concerning and needs to be explained. Please explain why summation underperforms and justify the explanation.\n\n10.\tAlong the same lines, it is not enough to state that “GAT and GIN operations also demonstrate reasonable performance”. Is GCN’s performance difference statistically significant? If so, why is it the case? Usually, we expect GIN to be superior when it comes to learning structural properties of a graph. A GCN is usually able to process feature-information better. Does this imply that the feature information is more important for this problem? The ablation that removes the node origin suggests that this is not the case. Please explain why GCN achieves a better performance and justify the explanation.\n\n11.\tPlease add the results (or at least a summary) of a similar ablation study for removing the node degree feature. \n\n12.\tPlease confirm that the degree distributions for the positive and negative samples in the dataset are indistinguishable. Does the xgboost baseline (or a simple MLP) perform better if it is trained using the degree distributions?\n\n13.\tPlease explain why simple graph features are not used in the xgboost baseline? For a graph with hundreds of nodes, it is relatively straightforward to determine numerous basic graph statistics.  \n\n14.\tPlease conduct statistical significance tests where appropriate.\n\nMinor\n\n15.\tThe text on the right-hand-side of Figure 2 is far too small. Please increase the font size. The text in the dark-coloured boxes is very hard to read. Please change the colour or move the text. \n\n16.\tNot mandatory, but suggested: In Figure 1, it is not obvious that leaf nodes A and B have been re-ordered in (c). The leaf node labels are small – perhaps the reordering can be highlighted by adding colours or larger labels. \n\n17.\tThe font size in Figure 8 is far too small.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: As described above, the submission's claims are supported by accurate, convincing, and clear evidence. Moreover, at least some individuals in TMLR's audience would be interested in knowing the findings of this paper.
Decision: Accept (poster)