  We propose the fully explainable Decision Tree Graph Neural Network (DT+GNN)
architecture. In contrast to existing black-box GNNs and post-hoc explanation
methods, the reasoning of DT+GNN can be inspected at every step. To achieve
this, we first construct a differentiable GNN layer, which uses a categorical
state space for nodes and messages. This allows us to convert the trained MLPs
in the GNN into decision trees. These trees are pruned using our newly proposed
method to ensure they are small and easy to interpret. We can also use the
decision trees to compute traditional explanations. We demonstrate on both
real-world datasets and synthetic GNN explainability benchmarks that this
architecture works as well as traditional GNNs. Furthermore, we leverage the
explainability of DT+GNNs to find interesting insights into many of these
datasets, with some surprising results. We also provide an interactive web tool
to inspect DT+GNN's decision making.
