  When dealing with tabular data, models based on decision trees are a popular
choice due to their high accuracy on these data types, their ease of
application, and explainability properties. However, when it comes to
graph-structured data, it is not clear how to apply them effectively, in a way
that incorporates the topological information with the tabular data available
on the vertices of the graph. To address this challenge, we introduce TREE-G.
TREE-G modifies standard decision trees, by introducing a novel split function
that is specialized for graph data. Not only does this split function
incorporate the node features and the topological information, but it also uses
a novel pointer mechanism that allows split nodes to use information computed
in previous splits. Therefore, the split function adapts to the predictive task
and the graph at hand. We analyze the theoretical properties of TREE-G and
demonstrate its benefits empirically on multiple graph and vertex prediction
benchmarks. In these experiments, TREE-G consistently outperforms other
tree-based models and often outperforms other graph-learning algorithms such as
Graph Neural Networks (GNNs) and Graph Kernels, sometimes by large margins.
Moreover, TREE-Gs models and their predictions can be explained and visualized
