GraphChef: Decision-Tree Recipes to Explain Graph Neural Networks

We propose a new self-explainable Graph Neural Network (GNN) model: GraphChef. GraphChef integrates decision trees into the GNN message passing framework. Given a dataset, GraphChef returns a set of rules (a recipe) that explains each class in the dataset unlike existing GNNs and explanation methods that reason on individual graphs. Thanks to the decision trees, the GraphChef recipes are human-comprehensible. We also present a new pruning method to produce small and easy-to-digest trees. Experiments demonstrate that GraphChef reaches comparable accuracy to non-self-explainable GNNs, and the produced decision trees are indeed small. We further validate the correctness of the discovered recipes on datasets where explanation ground truth is available: Reddit-Binary, MUTAG, BA-2Motifs, BA-Shapes, Tree-Cycle, and Tree-Grid.