GraphChef: Learning the Recipe of Your Dataset

We propose a new graph model, GraphChef, that enables us to understand graph datasets as a whole. Given a dataset, GraphChef returns a set of rules (a recipe) that describes each class in the dataset. Existing GNNs and explanation methods reason on individual graphs not on the entire dataset. GraphChef uses decision trees to build recipes that are understandable by humans. We show how to compute decision trees in the message passing framework in order to create GraphChef. We also present a new pruning method to produce small and easy to digest trees. In the experiments, we present and analyze GraphChef's recipes for Reddit-Binary, MUTAG, BA-2Motifs, BA-Shapes, Tree-Cycle, and Tree-Grid. We verify the correctness of the discovered recipes against the datasets' ground truth.