Graph Trees with Attention
When dealing with tabular data, models based on regression and decision trees
are a popular choice due to the high accuracy they provide on such tasks and
their ease of application as compared to other model classes. Yet, when it
comes to graph-structure data, current tree learning algorithms do not provide
tools to manage the structure of the data other than relying on feature
engineering. In this work we address the above gap, and introduce Graph Trees
with Attention (GTA), a new family of tree-based learning algorithms that are
designed to operate on graphs. GTA leverages both the graph structure and the
features at the vertices and employs an attention mechanism that allows
decisions to concentrate on sub-structures of the graph. We analyze GTA models
and show that they are strictly more expressive than plain decision trees. We
also demonstrate the benefits of GTA empirically on multiple graph and node
prediction benchmarks. In these experiments, GTA always outperformed other
tree-based models and often outperformed other types of graph-learning
algorithms such as Graph Neural Networks (GNNs) and Graph Kernels. Finally, we
also provide an explainability mechanism for GTA, and demonstrate it can
provide intuitive explanations.