GraphChef: Decision-Tree Recipes to Explain Graph Neural Networks
Authors: Peter Müller
Lukas Faber
Karolis Martinkus
Roger Wattenhofer
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Networks
GNN
Explainability
Decision Trees
Primary area: visualization or interpretation of learned representations
TL;DR: GraphChef integrate Decision Trees into Graph Neural Networks to allow explaining the full decision process.

Abstract: 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, GraphChef  recipes are human understandable.  We also present a new pruning method to produce small and easy to digest trees. Experiments demonstrate that GraphChef reaches comparable accuracy to not self-explainable GNNs and 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.

Published as a conference paper at ICLR 2024
GRAPHCHEF: DECISION-TREI RECIPES TO EXPLAIN GRAPH NEURAL NETWORKS
Peter Müller, Lukas Faber, Karolis Martinkus, Roger Wattenhofer ETH Zurich, Switzerland (1 faber, moarol is, wattenhofer) @ettrreferr@eeeeeeeeee @ethz.ch ch
is,
ABSTRACT
We propose a new self-explainable Graph Neural Network (GNN) model: GraphChef. GraphChef integrates decision trees into the GNN message pass- ing framework. Given a dataset, GraphChef returns 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 connan-ccmmpeheniible... We also present new pruning method produce small and easy-to-digest trees. Experiments demonstrate that GraphChef reaches comparable accuracy non-self-explainnble GNNs, and the produced de- cision 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.
INTRODUCTION
Graphs abstractly represent complex relational data in a myriad of applications and play a crucial role in, e.g., chemistry, engineering, social sciences, or transportation. Graph Neural Networks (GNNs) are a popular but black-box machine learning model for graph-based domains. GNNs classify individual graphs, as in "Is this protein (represented as graph) an enzyme?" Naturally, explaining how these box GNNs make their predictions is also important. Most existing works aim to explain GNN predictions by identifying key nodes (Figure lap and edges (Figure (bb) by finding similar examples or subgraphs (Figure(Tc) Each of these existing methods can highlight the importance of the double "Sheet" motive, but method helps us understand why it is important. In this paper, we want to drive explanation further and 1) understand not only which inputs are important, but also how they are used and 2) understand the dataset as whole to really answer the question "What makes a protein an enzyme?". GraphChef builds a recipe in the form of decision trees (Figures [c). The recipe shows hows Sheets contribute the Enzyme class. The PROTEINS dataset shown an easy example dataset without intermediate layers. In further experiments, we show that GraphChef works equally well for various explanation benchmarks that require graph reasoning. In summary, our contributions are as follows:
While traditional GNNs are based synchronous message passing (Loukas 2020
propose a new layer that is inspired by a simplified distributed computing model known the stone-age model (Emek and Wattenhofer 2013). In this model, the nodes small categorical space for states and messages. The stone-age model is simple and as such suitable for interpretation while retaining high theoretical expressiveness. We call our new layer dish (Differentiable Stone-"H")
We distill the multi-layer perceptrons in all dish layers to decision trees. We call the resulting model GraphChef. GraphChef abstractly expresses the reasoning of the dish GNN with series of decision trees (the recipe). See Figure 1 for a complete example.
We propose a way to collectively prune the decision trees in GraphChef. Pruning may affect accuracy, but also gives simpler explanations. GraphChef hence allows for trade-off between accuracy and simplicity.
We introduce an importance propagation scheme through the recipes to allow GraphChef to compute node-level importance scores similar orthodox GNN explanation methods.

---

Published as a conference paper at ICLR 2024
H
Input UNe Smeet 8
H
H
S
Enzyme
Input Layer
Input 0.5
ASheel s
H
S
Enzyme
Noi Enzyme
No Sheet
Sheet
(a)
(b) (c)
(d)
(e)
Figure 1: PROTEINS is graph classification dataset. Nodes are secondary structural elements of amino acids, either helixes (H, input O), sheets (S, input 1), or turns (T, input 2). Graphs are classified whether they
enzyme not. (a) shows node-level explanation for Enzyme; (b) an edge-level explanation; (c) subgraph explanation. With all three these prior approaches, we can deduce that the two sheets are important, but we do not know why. The explanation does not answer questions such as "Do the sheets have to be connected!" or "Must there be exactly two? (d) The GraphChef recipe for PROTEINS reads as follows: protein is an enzyme it has most nodes that are not sheets, or if it has at most 3 sheets. The example graph has 9 "no sheet" and sheet nodes and is therefore an Enzyme. The second tree (e) explains the terms used in (d). Note that this recipe simultaneously explains the predictions for all the other graphs in the dataset. This recipe using only node features and no message passing matches the current approach in biochemistry (Errica) ct al. 2020
We test GraphChef established GNN explanation benchmarks and real-world graph datasets. We show that our recipes retain high accuracy compared to fully-expressive GNNs. The importance propagation produces competitive results to existing explanation methods. We further validate that the proposed pruning method considerably reduces tree sizes. Last, demonstrate how read GraphChef's recipes to find interesting insights in real-world datasets or flaws in existing explanation benchmarks.
We provide a user interface for GraphChef" This tool allows for the interactive exploration of the GraphChef recipes on the datasets examined in this paper. We provide manual for the interface in Appendix
2 RELATED WORK
2.1 EXPLANATION METHODS FOR GNNS
Recent years have seen many GNN explanation methods being proposed using different ideas. We can roughly group them into five groups based on the main approach. Gradient, Mutual- Informmainn and Counterfactual methods compute node-level edge level importance that we can interpret as heatmaps. These heatmaps highlight which parts the input are important, but not why. On the other hand, Subgraph and Example based methods explain graphs by showing other example graphs or idealized prototype representatives for classes-bur again not why these (sub)graphs influence the GNN prediction. In all five cases, human would need explanations for dozens of example graphs to puzzle together a recipe for a dataset.
Gradient based. Baldassarre and Azizpour 2019) and Popee al. (2019) show that it is possible adopt gradient-based methods known from computer vision, for example Grad-C CAM(Selvaraju et al. 2017). Gradients can be computed on node features and edges (Schlichtkrull et al. 2021).
Mutual-information based. Ying et al. (2019) measure the importance of edges and node features. Edges are masked with continuous values. Instead of gradients, the authors use mutual information
between the inputs and the prediction to quantify the importance. Luo et al. (2020) follow a similar idea but emphasize finding structures that explain multiple instances at the same time.
Counterfactual. Lucic et al. (2021) show that already the deletion of few edges can change the classifier prediction, supporting that these edges are important for the class. The idea is similar to
https://interpretables
appppppp
2

---

Published as a conference paper at ICLR 2024
occluding parts of image in computer vision Zeiler and Fergus 2014). Bajaj al. (2021) propose
a hybrid with an example-based explanation. They compute decision boundaries over multiple instances to find optimized counterfactual explanations.
Subgraph based. Yuan et al. (2021) consider each subgraph as possible explanation. To score subgraph, they use Shapley values (Shapley) (953) and Monte Carlo tree search for guiding the search. Duval and Malliaros (2021) build subgraphs by masking the nodes and edges in the graph. They run their subgraph through the trained GNN and try to explain the differences to the entire graph with simple interpretable models and Shapley values. Zhang et al. (2021) infer subgraphs called prototypes that each represent one particular class. Graphs are classifted and explained through their similarity to the prototypes. Azzolin et al. (2022) propose scheme to combine "local" subgraphs explaining one graph into a "global" logic formula to explain the reasoning in the dataset.
Example based. Huang et al. (2020) proposes graph version of the LIME (Ribeiro et a 2016) algorithm. A prediction is explained through linear decision boundary built by close-by examples. Vu and Thai (2020) aim to capture the dependencies in node predictions and express them in probabilistic graphical models. Faber et al. (2020) explain a node by giving examples of similar nodes with the same and different labels. Dai and Wang (2021) create k-nearest neighbor model and measure similarity with GNNs. Yuan et al. (2020a) and Wang and Shen (2022) generate a representative graph for each class that maximizes the model's confidence in the class prediction. (Azzolin et al. 2022) is a noteworthy approach that constructs formulas that aim not to explain single graphs but also classes for the entire dataset, being the most similar to our dataset-level recipes. However, these formulas do not reveal the GNN decision process either.
Simple GNNs. Another interesting line of research is simplified GNN architectures Cai and Wang (2018); [Chen et al. (2019); Huang et al. (202T). The main goal of this research is to show that simple architectures can perform competitively with traditional complex GNNs, As a side effect, the simplicity of these architectures also makes them slightly more understandable. However, they are not understandable to the extent that we can derive recipes for entire datasets. GraphChef also deliberately sacrifices some expressive power but explicitly to gain explainability.
2.2 EXPLANATION PROPERTIES AND BENCHMARKS.
Complimentary the development of explanation methods is research on how evaluate these methods. Sanchez-Lengeling et al. (2200) and Yuan et al.] (2020b) discuss the desirable properties a good explanation method should have. For example, an explanation method should be faithful to the model, which means that an explanation method should reflect the model's performance and behavior. /Agarwal et al. (2022) provide a theoretical framework to define how strong explanation methods adhere to these properties. They also derive bounds for several explanation methods. Faber jet al. (02T)) and Himmelhuber et al. (202T) discuss deficiencies in the existing benchmarks used for empirical evaluation. We will show recipes by GraphChef how GNNs might exploit such deficiencies in Appendix to produce correct recipes that are not in line with the explanation ground truth.
2.3 COMBINING DECISION TREES WITH NEURAL NETWORKS
Decision trees are popular machine learning models thanks to their inherent explainability (given reasonable tree sizes). Already early works in neural networks research investigated the feasibility of extracting trained neural networks into decision trees to understand what the network learned (Boz)
2002 Craven and Shavlik 1995 Dancey al., 2004 Krishnan et al. 1999).
Recently, this idea has been picked up again. Schaaf et al. (2019) have shown that encouraging sparsity and orthogonality in neural network weight matrices allows for model distillation into smaller trees with higher final accuracy. Ww et al. (2017a) follow a similar idea for time series data: they regularize the training process for recurrent neural networks to penalize weights that cannot be easily modeled by decision trees. Yang et al. (2018a) aim to directly learn neural trees. Their neural layers learn how to split the data and put into bins. Stacking these layers creates trees. Kontschieder et al. (2015) learn neural decision forests by making the routing in nodes probabilistic and learning these probabilities and leaf predictions. A recent work by Aytekin (2022) shows that we can transform any neural network into decision trees. However, this approach creates tree with potentially exponentially many leaves. Even though this method produces decision trees, we cannot use the outputs as humanly understandable recipes for datasets.
3

---

Published as a conference paper at ICLR 2024
Pairwise Comparisons
UPDATE
State
Decision Tree
0 1
Message M
Differences
Figure 2: A GraphChef layer. GraphChef updates the state of a node based on its previous categorical
state (left green), the number of neighbors per state (blue, in state 0, 2 in state 1, 1 in state 2), and binary > comparisons between states (yellow, only state outnumbers other states, therefore the third and fourth deltas are 1). A decision tree that receives this information computes the followup categorical state (right green).
GraphChef follows the same underlying idea. Can express what our GNN learned in a decision tree to explain its decision process? In contrast to existing methods which operate on tabular data, GraphChef also needs include the reasoning about the graph structure (for example, finding important edges between nodes). We also emphasize the importance of small trees to ensure that the recipes produced are understandable humans.
THE GRAPHCHEF MODEL
3.1 FROM GIN TO DISH
We follow the general message passing GNN model (Gilmer et al. 2017 Battaglia et al., 2018): Every node has an internal state that modified in the GNN layers. In every layer, every node computes message that it sends to every neighbor. Then every node receives all messages, aggregates the set of messages, and updates its state:
1 1+ UPDATE (H, AGGREGATE e
(MESSAGE((L)) | wEN((u)
Our starting architecture is the GIN model from Xu et al. (2019). In GIN, the MESSAGE function is the identity function. AGGREGATE is element- wise summation, and UPDATE is a learnable neural function fo- Although it is rather simple, the GIN model is already as expressive as the 1 1 Weisfeiler Lehman test. We can notate GIN as follows:
Po
Σ (o)
WEN
We derive the internal state h. for the first dish layer with an encoder on the initial node features Fe- We use the internal states in a decoder layer: For node classification, we use skip connections and use all internal states for the final prediction. For graph classification, we sum-pool all nodes in every layer and make sums available the final prediction.
The internal states are d- dimeennsional real-valued vectors: h1 E Rd. These vectors allow complex relationships between features that make explainability very difficult. We simplify the internal states by applying a Gumbel-Softmax (Jang et al.) 2016 Maddison et al. 2016) to the GNN layers and also to the encoder layer: h Guumbll
Σ
ND(w)
Therefore, the internal states hL become one-hot categorical values and summation in the GNN aggregation step counts how many neighbors are what state. The theoretical motivation for this change comes from distributed computing: Loukas (2020) showed that message passing GNNs such as GIN are equivalent to the LOCAL distributed computing model(Peleg 2000). LOCAL, nodes perform arbitrary local computation. However, there exists also simpler model, coined the stone-age model (Emek and Wattenhoter 2013) where nodes can only transition between categorical states using finite state machine. The nodes count the number of neighbors in each state and only
4

---

Published as a conference paper at ICLR 2024
in limited manner in the spirit of "one, two, three, many". Neighborhood counts above a threshold are indistinguishable from each other. Interestingly enough. such a simplified model can still solve many distributed computing problems. Our proposed GNN architecture the GNN equivalent of this stone-age model. Therefore, we coin our layer "dish": differentiable stone-"h".
Let us look the theoretical expressive power of dish layers: For GIN with log(d) bits of continuous embedding space, we can, in principle, create a dish GNN with d categorical states and the same theoretical expressiveness. Practically, aim for low number of categorical bits ensure human interpretability. We investigate the drop in accuracy in Table Ta
3.2
FROM DISI TO GRAPICCEEF
We can leverage the categorical states of trained dish model to distill all neural blocks decision trees. These are the update functions in the dish layers as well as the functions in the encoder and decoder layers. Since all states are categorical, this distillation becomes a classification problem where decision trees learn to predict the categorical state. A distilled GraphChef layer looks as follows and is also shown in Figure 2
h [+1 TREE (K
Σ
.ENN(1)
Note that the GraphChef layer still follows the message passing framework but instead of neural function plus Gumbel-SSftmax it uses decision tree. We empirically found that GraphChef benefits from one tweak. Decision trees generally struggle with comparing two features (is one feature larger than the other). To help with that and produce small trees, we include pairwise delta features A. These binary features compare every ordered pair of features and are one if the first feature is larger. Let cf be the counts of neighbors in state in layer
A iES.JiiES
11
1d20
h'+ (v) TTEEE (h dy, A(c))).
Decision trees have access to three sets of features: the previous state, the number of neighbors in each state the comparison of two state counts. Figure shows these colored green, blue, and yellow, respectively. For each decision node in GraphChef's decision trees, we can interpret the GNN reasoning based on which feature is used shown 3 We can combine these individual node interpretations to formulate GraphChef's recipes. Figure shows an example recipe with an interpretation in Table More examples of recipes are available Appendix A
Neighbors state
State 8
Neighbors y>y
Neighbors in state
False
True
False
True
False
True
(a)
(b)
(c)
Figure 3: The different branches possible in GraphChef layer. We branch on (a) the state in which a node in, (b) the node has a certain number of neighbors in a certain state, or (c) if the node has neighbors in state than in another state. The colors match the features in Figure 2
3.3 PRUNING GRAPHCHEF
Although sufficiently deep decision trees can be universal function axproximators(Royyde and Fitzpatrick 1988 Aytekin 2022), we prefer small and shallow decision trees, which are much more understandable humans. Shallow trees more akin the finite state machine used in the stone-age distributed computing model. We find that setting an upper bound on leaves for every decision tree is not sufficient and that GraphChef requires further pruning.
We prune these nodes based on the reduced error pruning algorithm (Quinlan 1987). First, we define pruning set. The validation set alone is too small to cover all paths in the trees, which causes over-pruning. On the other hand, we cannot use only the training set since this set created the overfitting artifacts. We propose merging both sets for our pruning set.
5

---

Published as a conference paper at ICLR 2024
We also need a quality criterion when replacing inner decision node with a leaf. We propose the following: If replacing a node with a leaf (i) does not drop the accuracy on the validation set and (ii) does not drop the training accuracy below the validation accuracy, we accept the replacement. Not allowing validation accuracy to drop ensures that we do not over-prune. However, allowing drops in training accuracy allows for removing decision nodes that result from overfitting. Not allowing training accuracy to drop below validation accuracy is another safeguard against over-pruning. We keep iterating over all inner decision nodes, sorted by the number of data points they cover, and try replacing them with leaf nodes until we find no more nodes that we can drop without accuracy loss. Afterwards we keep iterating and remove the node with the smallest drop in validation accuracy. Slight deterioration allows to prune far more nodes. Ultimately, we record 10 pruning levels: after pruning with no validation accuracy loss and pruning the remaining nodes in 10% steps. We make these levels available in the UI and allow users to choose the trade-off between accuracy and tree size.
Computing explanation scores. If we have a GraphChef recipe for the dataset, we can also compute heatmap-style importance scores for single graphs; similar to existing graph explanation methods. We compute these importance scores layer by layer. In the input layer, every node is its own explanation. In each GraphChef layer, we compute Tree-Shap values (Lundberg et al., 2018) for every decision tree feature. We then compute importance updates for every decision tree feature weighted by this Tree-Shap value independently (unused features have value of 0). If the node uses state feature (as in Figure 3a) then we give importance to the node itself. If we use a message feature (as in Figure 3b). we distribute the importance evenly between all neighbors in this state. If we use a delta feature (as in Figure 3c). we distribute positive importance between all neighbors in the majority class and also negative importance between all neighbors in the minority class. Finally, we normalize the scores to sum up to 1. In the decoder layer, we employ skip connections to also consider intermediate states (for node classification) or intermediate pooled node counts (for graph classification). We provide formal computation in Appendix C
4 EXPERIMENTS
GraphChef
Dataset
DT
DT+degrees
GIN
dish GNN
No pruning
Lossless pruning
Infection
0.43=0000
0.43=00.0
0.98=0004
1.00=0.00
1. 1.00=0.00
1.00=0.00
Negative
0.51=0.00
0.50=0.00
1.00=0.00
1.0=0.000
1.00=0.00
1.00=0.00
BA-Shapes
0.43=0000
0.86=0.02
0.97=0.02
1.0000.0
0.09+0.01
0.90=0.01
Cycles
0.50=0.00
0.84+0.04
1.00=0.00
100=0.00
1.00=0.00
1.00=0.00
Tree-Grid
0. 0.58=0.00
0.76=0.03
1.00=0.01
0.99=0.01
0.09+0.01
0.90=0.01
BA MMoMis
0.50=0.00
0.82=0.03
1.00=0.00
1.00=0.00
1.00=0.00
1.00=0.00
MAT
0.83.00.9
0.85
0..05
0.85.0.06
0.88.00.6
0,8510,08
Mutagenicity
0.71=0.02
0.72=0.02
0.8120.02
0.79+0.02
0.75+0.02
0.74=0.02
BBBP
0.83.00.3
0.8310002
0.8110.02
0.8310.03
0.8210.03
0.8310.03
PROTEINS
0.74:0002
0.71=0.04
0.70=0.03
0.71#0.02
0.71#0.04
0.71
IMDB B
0.57-0.04
0.7110004
0.6910.04
0.7010.05
0.69.00.3
0.6910.04
REDDIT-B
0.75=0.03
0.80=0.03
0.87=0.10
0.90+0.03
0.88#0.03
0.87=0.04
COLLAB
0.59-00.11
0.70.0..02
0.72.0.01
0.70.0.02
0.6010.02
0.6910.02
(a)
Table 1: a) Test set accuracies using decision trees (DT) and different GNN layers. One version of decision trees additionally receives the degrees. For graph classification, the decision tree inputs where the number of nodes of each type and potentially of each degree. The gap between dishGNN and both GraphChef versions to a full GNN is low, importantly also in graphs that require sophisticated graph reasoning (and DT+degrees is not enough)
4.1 EXPERIMENT SETUP
Datasets. We first run GraphChef on synthetic GNN explanation benchmarks introduced in previous work. We use the Infection and Negative Evidence benchmarks from Faber et al. 2021). The BA-Shapes, Tree-Cycle, and Tree-Grid benchmarks from Ying et al. (011)). and the MA-2Mssifs dataset from Luo et al. (2020). Second, we experiment with the following real-world datasets: MUTAG (Debnath et al. 1991; y; BBBP (Wu et al., 2017b); Mutagenicity (Kazius et al. 2005);
PROTEINS, REDDIT-BINARY BINAYY, and COLLAB (Borgwardt et al. 2005). We provide

---

Published as a conference paper at ICLR 2024
more information for all datasets, such statistics, descriptions. and examples in Appendix and hyperparameters in Appendix [ Note that all datasets except COLLAB are small enough to train on commodity CPUs. For example, training the PROTEINS dataset for seed laptop trains in minutes for the full 500 epochs, a few seconds for the tree distillation, and 2 minutes for tree pruning. The larger REDDIT-BINARY takes around one hour train dish GNN (if it uses all epochs) few seconds for distilling trees and around 10 minutes for pruning. Computing lossy pruning takes comparable amount of time lossless pruning.
4.2
QUANTITATIVE RESULTS
Method
Infection
Saturation
BA-Shapes
Tree-Cycles
Tree-Grid
Gradient
1.00=0.00
1.00=0.00
0.882
0.905
0.667
GNNExplainer
0.32=0.09
0.32+0.05
0.925
0.948
0.875
PGMExplainer
0.38=#0.06
0.01#0.01
0.965
0.968
0.892
GraphChef
0.95#0.02
1.00=0.00
0.94=0.02
0.84=0.02
0.927=0.01
Table 2: Overlap of identified explanation to explanation ground truth. The numbers for Gradient, GNNExplainer, and PGMExplainer taken from Ying al. (2019), Vu and Thail (2020). and Faher et al. (202I)
(a) GNNExplainer Ba Ba-Shapes
(b)
(c)
(d)
(c)
GNNExplainer Tree- Cycles
GNNExplainer Tree-
GNNExplainer MUTAG
GNNExplainer REDDIT-B
(f) GraphChef
(g) GraphChef Tree-Cycles
(h) GraphChef Tree-Grid
(i GraphChef MUTAG
(i) GraphChef REDDIT-B
Ba-shapes
Figure 4: Subselections of important nodes for GNNExplainer and GraphChef for several datasets.
GraphChef performs comparably to GIN. On both groups of datasets, we measure the perfor- mance of GIN versus dish GNN versus GraphChef. In principle, there may be a drop in accuracy at each step to trade expressive power for explainability. Table Ialswwss shows the average test accuracy over 10 seeds for each method and also for the losslessly pruned version of GraphChef. We find that GraphChef recipes perform very close to GIN. This also holds on datasets that require sophisticated graph reasoning that we cannot solve by a decision tree baseline that has access to degrees. The model simplifications to obtain understandable recipes do not decrease accuracy. We observe that tree pruning can even have a positive effect on test accuracy compared to non-pruned GraphChef. This is likely due the regularization induced by the pruning procedure.
Graph Chef produces competitive explanations. We can use the ground truth available from the first group of datasets evaluate the importance scores of GraphChef (Appendix C). Following existing work such as Ying et al. (2019), we compute importance scores for every node in the graph and consider the nodes with the highest score for the explanation, is the number of nodes in the ground truth. The explanation accuracy for a graph is the ratio of correct nodes in the explanation. Table shows the average accuracy per dataset.
GraphChef explanations are competitive with existing explanation methods with some examples shown in Figure The scores on Tree-Cycles and Tree-Grid suggest room for improvement, but
7

---

Published as a conference paper at ICLR 2024
that is not actually the case as show in Appendix A
GraphChef solves the datasets in legitimate
way that is easier than the creators anticipated and does not require finding the full motif. These alternative solutions are known deficiencies of the datasets (Faber et al. 2021: Himmelhuber et al.) 2021).
No pruning
REP Training
REP Validation
REP Ours
REP Lossy
Dataset
Accuracy
Size
Accuracy
Size
Accuracy
Size
Accuracy
Size
Accuracy
Size
Infection
100=0.00 0.00
205=56
1.00=0.00
26+2
1.00=0.00 00
25+2
1.00=0.00
26=2
0.98=0.01
17+2
Negative
1.00=0.00
18+14
1.00=0.00
5#0
1.00=0.00
5=0
1.00=0.00
5
1.00=0.00
4+4
BA- BA-Shupes
0.99=0000
30=10
0.99=0.01
21+5
0.97 03
15+4
0.99=0.01
21=5
0.98=0.01 0.01
17+4
Tree- Cycles
1.00=0.00
19:5
1.00=0.00
1113
0.90
9=22
1.00=0.000
11:3
0.99=0.01
9:3
Tree- Rei-Grid
0.99=0001
30#13
0.99=0.01
17+8
0.99=0.01
13:4
0.99
15:8
0.99=0.01
15
-Motfii
1.00=0.00
141=48
1.00=0.00
1243
1.00
1.00=00000
13s4
1.00=0.00
1314
MUTAG
0.86=0.06
59:27
0.8G=0.08
19:17
0.83
7=6
0.85##0.08
18:16
0.85=0.08
18:16
Mutagenicity
0.75=0.02
375=13
0.76=0.02
154+19
0.73=0.01
56=16
0.71=0.02
91+336
0.73=0.02
50=19
BBBP
0.82=0.03
366=53
0.84=0.02
88#52
0.79:0.04
8+10
0.83#0.03
46:27
0.82=0.03
31=18
PROTEINS
0.71=0.01
206=90
0.72=0.03
12#13
0.70=0.04
8=6
0.71=0.01
9=6
0.71=0.01
9=6
IMDB-B
0.69=0.03
218=32
0.69=0.04
20+9
0.66=0.06
16:6
0.69=00004
29=9
0. 0.69=0.04
2949
REDDIT-
0.88=0.03
248=28
0.88:0.02
53:14
0.85
28:8
0.87:0.04
49:21
0.87=0.04
38=15
COLLAB
0.69=0.02
3
0.70=0.02
36:11
0.67
22:12
0.69:0.002
30:18
0.68=0.02
21
Table 3: Running reduced emror pruning (REP) on different pruning sets, The threshold for lossy pruning is chosen manually, scores for the remaning considered thresholds are visible in the UI.
Pruning significantly reduces the decision tree sizes. Third, we examine the effectiveness of our pruning method. We compare the tree sizes before pruning, after lossless pruning, and after lossy pruning. We measure tree size as the sum of decision nodes over all trees. Additionally, we verify the effectiveness of using our pruning criterion for reduced error pruning and compare it against simpler setups of using only the training or validation set for pruning. We report tree sizes and test set accuracy for all configurations in Table 3
We can see that reduced error pruning leads to an impressive drop in the number of nodes required in the decision trees. On average, we can prune about 62% of nodes in synthetic datasets and even around 84% of nodes in real-world datasets without loss in accuracy. If we accept small drops in accuracy, we can even prune a total of 68% and 87% of nodes in synthetic and respectively. Among the different setups for reduced error pruning, our proposed approach of using both training and validation accuracy performs the best. As expected, pruning only on the validation set tends to over-prune the trees: Trees become even smaller, but there is also a larger drop in accuracy, especially in the real-world datasets. Using the training set leads to underpruning: there is no drop in accuracy, but decision trees for real-world graphs tend to stay large. Lossy pruning usually allows further decrease in decision tree sizes with virtually no accuracy drop. In this instance, we used the UI (Appendix F) to choose threshold. Alternative options are also available in the UI.
datasets,
4.3 QUALITATIVE RESULTS
25 029075
gid M5
Stale
Neighbour
virgln slac3
FaN
Laper Stan 1414
COME
sergose L:N
Stuta
Deccus
(a)
(b)
Figure 5: GraphChef recipe for the Reddit-Binary dataset. Decision trees in every layer are built provides an interpretation of all states in all layers
using the building blocks from Figure 3 Table 4 and for the entire dataset.
8

---

Published as a conference paper at ICLR 2024
Layer State
Decision Rule
Interpretation
Encoder 2
All nodes
No differentiation due to features. Inactive users
Layer 2
Nodes with at most neigh- bors
Layer
4
Between 4 and 45 neighbors
Active users
Layer 0
More than 45 neighbors
Central users
Layer
0
1) State 0 nodes with more than one state 0 neighbor or 2) Not state 2 nodes that have at most two state neighbors No neighbor in state 0 Not state 2 nodes with at least
I) Inactive users writing with at least 2 central users or Active or central users that write with at most 2 active users.
Layer 1
Users that do no write with central user. Active or central users that write with least 3 active users.
Layer
2
3 state 4 neighbors
Layer 4
Nodes in state with exactly state O neighbor
Inactive users write with one central
Decoder
Q/A
At least 15 nodes in Layer
See interpretation of Layer state O.
state 0
Decoder
Discussion
Otherwise
The GraphChef' model looks for evi- dence of Q/A graph. Discussions "not Q/A" graphs.
Table 4: Analysis of GraphChef recipe in Figure 5 for the Reddit-Binar dataset. A Q/A graph requires central users and 15 users that 1) inactive and write with than one central user or 2) are active or central and write mostly with inactive users.
Finally, let us look at how to read GraphChef recipe for the Reddit-Binary dataset. The recipe is shown in Figure First, we aim to understand every categorical state in every layer, in a fashion similar to dynamic programming. We start by understanding the states in the first layer, taking note of these explanations, and using them to understand the next layer. Table 3 does this for the Reddit-Binary dataset from top bottom. To understand the dataset, inspect the decoder rules.
We can understand that we need to find a certain amount of users (15) fulfilling certain conditions: 1) inactive users writing with least central users active or central
that write with least one central user and at most 2 active users. We can understand 1) as just replying to a single central user is not sufficient. We hypothesize that controversial opinions in discussions can also attract many comments, even by inactive users. Users fulfilling 2) write mostly with inactive users since there are few central users and little communication with active users allowed.
GraphChef's recipe aligns with our belief that Q/A graphs are more "star-like" than discussion graphs (Faber al., 2020p. However, the recipe also defines what we should consider as "star like". We obtain a threshold on what we can consider as centers of the star (central nodes with a degree of 46 or higher). The recipe also tells us to what extent non-star communication acceptable for Q/A graph (two active users). To the best of our knowledge, such insight about the Reddit-Binaa dataset has not been found yet with existing explanation methods. See Appendix for more recipe analyses.
CONCLUSION, LIMITATIONS, AND FUTURE WORK
In this paper, we introduce GraphChef, a new architecture that takes GNN explanations to new level. Instead of only highlighting the important parts of an input, GraphChef produces recipe which reveals the full decision process for the whole dataset. Internally, GraphChef combines GNNs and decision trees to create recipes. We believe that GraphChef will help improve our understanding of graph problems, which is crucial for the adoption of GNNs in safety critical domains such as medicine. We can also identify and reject recipes that make biased or discriminatory decisions.
As limitation, found that GraphChef can struggle to create recipes for datasets with large feature space, discussing details in Appendix [ seems difficult to construct small and accurate decision trees when the input feature space is very large (hundreds or thousands of features).

---

Published as a conference paper at ICLR 2024
REFERENCES
C. Agarwal, M. Zitnik, and H. Lakkaraju. Probing gnn explainers: A rigorous theoretical and empirical analysis of gnn explanation methods. In International Conference on Artificial Intelligence and Statistics (AISTATS), virtual, 2022.
C. Aytekin. Neural networks are decision trees. arXiv preprint arX1v:2210.05188, 2022.
S. Azzolin, A. Longa, P. Barbiero, P. Liò, and A. Passerini. Global explainability of gnns via logic combination of learned concepts. arXiv preprint arXiv:2210.07147, 2022.
M. Bajaj. L. Chu, Z. Y. Xue, J. Pei, L. Wang, P. C.-H. Lam, and Y. Zhang. Robust counterfactual explanations on graph neural networks. In Conference on Neural Information Processing Systems (NeurIPS), volume 34, pages 5644-5655, 2021.
F. Baldassarre and H. Azizpour. Explainabilityy techniques for graph convolutional networks. In International Conference on Machine Learning (ICML) Workshop on Learning and Reasoning with Sraph-Structured Representations, 2019.
W. Battaglia, J. B. Hamrick, V. Bapst, A. Gonzaez- V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, C. Gulcehre, F. Song, A. Ballard, J. Gilmer, G. Dahl, A. Vaswani, K. Allen, C. Nash, V. Langston, C. Dyer, N. Heess, D. Wierstra, Kohli, M. Botvinick, O. Vinyals, Y. Li, and R. Pascanu. Relational inductive biases, deep learning, and graph networks. 2018. URL http:://axxi..oo/////// abs/ 1806. 01261
K. M. Borgwardt, C. S. Ong. S. Schonauer, S. V. N. Vishwanathan, A. J. Smola, and H.-P. Kriegel. Protein function prediction via graph kernels. Bioinformatics, 2005.
O. Boz. Extracting decision trees from trained neural networks. In ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), 2002.
C. Cai and Y. Wang. A simple yet effective baseline for non-attributed graph classification. In Inter- national Conference on Learning Representations (ICLR) Workshop on Representation Learning on Graphs and Manifolds, 2018.
Chen, Bian, and Y. Sun. Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification. ArXiv, 2019.
M. Craven and J. Shavlik. Extracting tree-structured representations of trained networks. In Confer- ence on Neural Information Processing Systems (NeurIPS), 1995.
E. Dai and S. Wang. Towards Self-Explainable Graph Neural Network. In ACM International Conference on Information Knowledge Management (CIKM), 2021.
D. Dancey, D. Mclean, and Z. Bandar. Decision Tree Extraction from Trained Neural Networks. In International Florida Artificial Intelligence Research Society Conference (FLAIRS), 2004.
A. K. Debnath, R. L.. Lopez de Compadre, G. Debnath, A. J. Shusterman, and C. Hansch. Structure- activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 1991.
A. Duval and D. Malliaros. Graphsvx: Shapley value explanations for graph neural networks. In Joint European Conference Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), 2021.
Y. Emek and R. Wattenhofer. Stone age distributed computing. In ACM Symposium on Principles of distributed computing (PODC), 2013.
Errica, M. Podda, D. Bacciu, and A. Micheli. fair comparison of graph neural networks for graph classification. In International Conference on Learning Representations (ICLR 2020), 2020.
L. Faber, A. K. Moghaddam, and R. Wattenhofer. Contrastive Graph Neural Network Explanation. In Proceedings of the 37th International Conference on Machine Learning (ICML) Workshop on Graph Representation Learning and Beyond (GRL+),, 2020.
10

---

Published as a conference paper at ICLR 2024
L. Faber, A. K. Moghaddam, and R. Wattenhofer. When Comparing to Ground Truth is Wrong, In ACM SIGKDD Conference on Knowledge Discovery Data Mining (KDD), 2021.
M. Fey and E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural Message Passing for Quantum Chemistry. In International Conference on Machine Learning (ICML), 2017.
A. Himmelhuber, M. Joblin, M. Ringsquandl, and T. Runkler. Demystifying Graph Neural Network Explanations. In Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), 2021.
Q. Huang, M. Yamada, Y. Tian, D. Singh, D. Yin, and Y. Chang, GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks. ArXiv, 2020.
Q. Huang, H. He, A. Singh, S.-N. Lim, and A. R. Benson. Combining Label Propagation and Simple Models Out-performs Graph Neural Networks. International Conference on Learning Representations (ICLR), 2021.
S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML), 2015.
E. Jang, S. Gu, and B. Poole. Categorical Reparameterization with Gumbel-Softmax. International Conference on Learning Representations (ICLR), 2016.
Kazius, R. McGuire, and R. Bursi, Derivation and validation toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 2005.
P. Kontschieder, M. Fiterau, A. Criminisi, and S. R. Bulo. Deep neural decision forests. In IEEE International Conference on Computer Vision (CVPR), 2015.
R. Krishnan, G. Sivakumar, and P. Bhattacharya. Extracting decision trees from trained neural networks. Pattern Recognition, 1999.
A. Loukas. What graph neural networks cannot learn: depth width. In International Conference on Learning Representations (ICLR), 2020.
A. Lucic, M. ter Hoeve, G. Tolomei, M. de Rijke, and F. Silvestri. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. ArXiv, 2021.
S. M. Lundberg, G. G. Erion, and S.-I. Lee. Consistent Individualized Feature Attribution for Tree Ensembles. ArXiv, 2018.
D. Luo, W. Cheng, D. Xu, W. Yu, B. Zong, H. Chen, and X. Zhang. Parameterized explainer for graph neural network. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
C. J. Maddison, A. Mnih, and Y. W. Teh. The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables. In International Conference on Learning Representations (ICLR), 2016.
V. Nair and E. Hinton. Rectified linear units improve restricted boltzmann machines. In Interna- tional Conference on Machine Learning (ICML), 2010.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, 7. Lin, N. Gimelshein, Kopf, E. Yang, Z. Detito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. In Conference on Neural Information Processing Systems (NeurIPS), 2019.
L. Antiga, A. Desmaison,
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel. M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Couraapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 2011.
D. Peleg. Distributed computing: localliy-sensitive approach. SIAM, 2000.
11

---

Published as a conference paper at ICLR 2024
P. E. Pope, S. Kolouri, M. Rostami, C. E. Martin, and H. Hoffmann. Explainability methods for graph convolutional neural networks. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Quinlan. Simplifying decision trees. International Journal of Man-Machine Studies, 1987.
M. T. Ribeiro, S. Singh, and C. Guestrin. " why should trust you?" explaining the predictions of any classifier. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2016.
H. L. Royden and P. Fitzpatrick. Real analysis. Macmillan New York, 1988.
B. Sanchez-Leegelingg J. Wei, B. Lee, E. Reif, P. Wang, W. W. Qian, K. McCloskey, I., Colwell, and A. Wiltschko. Evaluating attribution for graph neural networks. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
N. Schaaf, M. F. Huber, and J. Maucher. Enhancing Decision Tree based Interpretation of Deep Neural Networks through LI -r-Orthogonal Regularization. 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA), 2019.
M. Schlichtkrull, D. Cao, and Titov. Interpreting graph neural networks for NLP with differentiable edge masking. In International Conference Learning Representations (ICLR), 2021.
R. R. Selvaraju, M. Cogswell, A. Das. R. Vedantam, D. Parikh, and D. Batra. Grad-cam: Visual explanations from deep networks via gradient-baut baaseett-bbadddddeee localization, In IEEE International Conference on Computer Vision (CVPR), 2017.
L. S. Shapley. 17. A Value for n- e-Person Games. Contributions to the Theory of Games, 1953.
M. Vu and M. T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
X. Wang and H.WW. Shen. Gnninterpreter: A probabilistic generative model-level explanation for graph neural networks. arXiv preprint arXiv:2209.07924 2022.
M. Wu, M. C. Hughes, S. Parbhoo, M. Zazzi, V. Roth, and F. Doshi-Velez. Beyond Sparsity: Tree Regularization of Deep Models for Interpretability. In AAAI Conference on Artificial Intelligence (AAAI), 2017a.
7. Wu, B. Ramsundar, E. N. Feinberg. J. Gomes, C. Geniesse, A. S. Pappu, K. Leswing, and V. Pande. MoleculeNet: Benchmark for Molecular Machine Learning. Chemical Science, 2017b.
K. Xu, S. Jegelka, W. Hu, and J. Leskovec. How Powerful are Graph Neural Networks? International Conference on Learning Representations (ICLR), 2019.
Y. Yang, I. G. Morillo, and T. M. Hospedales. Deep Neural Decision Trees. ArXiv, 2018a.
Z. Yang, W. Cohen, and R. Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference machine learning (ICML), 2018b.
R. Ying, Bourgeois, You, M. Zitnik, and J. Leskovee. GNNExplainer: Generating Explanations for Graph Neural Networks. In Conference on Neural Information Processing Systems (NeurIPS). 2019.
H. Yuan, J. Tang, X. Hu, and S. Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 430-438, 2020a.
H. Yuan, H. Yu, S. Gui, and S. Jí. Explainability in Graph Neural Networks: A Taxonomic Survey. ArXiv, 2020b.
H. Yuan, H. Yu, J. Wang, K. Li, and S. Ji. On Explainability Graph Neural Networks via Subgraph Explorations. In International Conference Machine Learning (ICML., 2021.
12

---

Published as a conference paper at ICLR 2024
M. D. Zeiler and R. Fergus. Visualizing and understanding convolutional networks. In European conference on computer vision (ECCV), 2014.
Z. Zhang, Q. Liu, H. Wang, C. Lu, and C. Lee. ProIGNN: Towards Self-Explaining Graph Neural Networks. In AAAI Conference Artificial Intelligence (AAAI), 2021.
13

---

Published as a conference paper at ICLR 2024
A MORE GRAPHCHEF RECIPE ANALYSES
A.1 MUTAG
Neighbour
Neight. Neighb.
METON 2700
3100 BF G-IN
State
State
State
State 275
(b)
(c)
(d)
(c)
Figure 6: GraphChef recipe for MUTAG. Table shows interpretation for all states in all layers. For graph to be mutagenic, it requires at least twelve atoms other than O and eight atoms that 1) have three
non-O bindings O atoms, 3) bound O2 atoms.
Table 5 shows an incremental interpretation (from Encoder to Decoder) of the states in all layers that are shown in the trees the GraphChef recipe in Figure/ofor the MUTAG dataset. The encoder shows that graph size is important (we need at least twelve non-O atoms) and O atoms and their connectivity play a role. We need least eight nodes that have three non-O bindings 2) O atoms 3) are connected to O₂ groups. The last two conditions highlight why NO₂ groups are associated with mutagenicty: The atom fulfills the last condition and the two O atoms fulfill the other condition. However, in the MUTAG (Debnath et al. 1991) dataset, these structures are not sufficient for mutagenic molecules.
14

---

Published as a conference paper at ICLR 2024
Layer
State
Decision Rule
Interpretation
Encoder
All nodes receive state
GraphChef drops atom types (and rediscovers them later via degrees). Degree nodes, H atoms are im- plicit these represent O atoms. Nodes with at least two electron bindings, predominantly C and N. Atoms with majorly bindings to O atoms.
Layer 0
Less than two neighbors
Layer 0
At least two neighbors
Layer
More neighbors in state than state 3
Layer 5
At least as many state 3 state 1 neighbors No neighbor in state 5
Atoms not connected to O, mainly to other atom types.
Layer 2 0
Rediscovers almost all O atoms, es- pecially those in O2 groups. They have one neighbor each and that neighbor has bindings to mostly O. Atoms other than O and some O atmons that are not in O2 groups. 1+3) Nodes with at most one O neighbor and at most two other neighbors Nodes with only O neighbors.
Layer 2
At least one neighbor in state
Layer 3
1) Exactly two state 3 neighbors 2) Nodes with state 3 neighbors 3) Nodes with state 3 neighbor but most state 0 neighbor
Layer 3
Nodes with least state 3 neighbors 2) not state 3 nodes 3) state nodes with one state 3 and state neighbors At least twelve atoms in layer 2 state and at least eight nodesin layer 3 state
Atoms with at least 3 connec- tions to atoms other than O 2) O atmons 3) atoms connected to O2 groups.
Decoder
Mutagenic
At least twelve atoms other than O and 1) Atoms with at least con- nections atoms other than 0 2) O atmons 3) atoms connected to O₂ groups.
Decoder
Not Mutagenic
otherwise
otherwise
Table 5: Analysis of the GraphChef recipe in Figure 6 for the MUTAG dataset. For a graph to be mutagenic, it requires least twelve atoms other than O and eight atoms that 1) have three more non-O bindings 2) are O atoms, 3) bound to O₂ atoms.
15

---

Published as a conference paper at ICLR 2024
A.2 BA- 2MOTIFS
(a)
(b)
(d)
(c)
Figure 7: Layers of GraphChef for the decision process BA-2MOTIFS. Table 6 shows interpretation for all states in all layers. The model learns to identify house nodes and classify such graphs Cycle graphs graphs which are not house graphs, thus solved with the bias term. Explanation scores for cycles are therefore off (e).
Layer Encoder
State
Decision Rule
Interpretation
3
All nodes
No node features available for differenti- ation.
Layer 0
2
Two state 3 neighbors
Degree 2 nodes.
Layer
4
Three or more state neigh- bors
Degree 3 or higher nodes.
Layer 5
Less than two neighbors
Degree nodes (graphs are connected).
Layer 0
State 2 nodes
Degree 2 nodes.
Layer 3
State 5 nodes
Degree nodes.
Layer
5
Neither state 2 nor
Degree 3 higher nodes.
Layer 1
Not state 3 nodes with more state than state 3 neighbors.
House candidates: nodes with a degree of least with at least one degree
3 or higher neighbor and no degree I neighbor.
Layer 2
4
State 3 nodes Not state nodes with state neighbors
Degree nodes.
Layer 5
At least degree 2 nodes but connected to at least degree neighbor (which house nodes do not have).
Layer 2
More state 4 than state neigh- bors
Nodes that have majorly degree neigh- bors (not house nodes).
Layer
3
At least state 1 neighbors
House nodes: connected to more house candidates.
Layer 4
At most one state neighbor
Nodes connected most one house candidate (wrong for every node in the house).
Decoder
House
At least five nodes in layer 3 state 3.
Graphs with at least five house nodes.
Decoder
Cycle
otherwise
otherwise.
Table 6: Analysis of the GraphChef recipe in Figure 7 for the BA-Motifs dataset. The model learns to identify house nodes and classify such graphs. Cycle graphs are graphs which are not house graphs, thus solved with the bias term.
Table 6 shows an interpretations of the states in all layers for the GraphChef recipe for BA-2MOTIFS. Figure ( shows the recipe. GraphChef only learns to identify house nodes. The important step is state I in the second layer. Due to the Barabasi-Aler base graph structure, house nodes stand out with their degree of 2 or 3. The next layer confirms the house as house candidates that are connected to house candidates. The model does not learn about cycles at all, Cycles are "not houses" We can that GraphChef found and exploited the pitfall about bias terms noted by Faber et al. (2020); Himmelhuber et al. (20I)) Figure 7 shows that we cannot trust explanation scores for cycles.
16

---

Published as a conference paper at ICLR 2024
A.3
TREE CYCLE
(d)
Figure 8: GraphChef recipe for TREE-CYCLE Table 6 shows an interpretation for all states in all layers. degree check for degree nodes finds the eycles quickly without considering the whole structure. Therefore, the explanation scores for the cycles are off (e).
Layer
State
Decision Rule
Interpretation
Encoder 0
All nodes
No node features available for differenti- ation.
Layer 0
Three more state 0 neigh- bors
Degree 3 or higher nodes (inner nodes in the tree, cycle node connecting the cycle the tree).
Layer
2
Two neighbors in state O
Degree 2 nodes (root node and cycles nodes).
Layer 3
One or zero neighbors in state
Degree nodes (leaves in the connected graph).
0
Layer
1
At least as many state 3 as state neighbors
As least as many leaves as cycle neigh- bors (true for inner nodes as well having zero of both).
Layer 3
More state 2 than state neigh- bors
Most cycle nodes, nodes connected to degree nodes.
Layer 4
Not previous state and at least state 1 neighbor 1) Previous state 3 or 2) no state neighbors In layer 2 state 1 otherwise
Not already a cycle node and connected non-cycle node.
Layer 1
1) already cycle node or 2) only con- nected to cycle nodes. See previous state. otherwise.
Decoder
Cycle No Cycle
Decoder
Table 7: Analysis of the GraphChef recipe in Figure Figure&ffor for the Tree-Cycle dataset. The base graph contains only one degree two node that not part of a cycle. A degree check quickly finds the cycles.
Table 7 shows interpretations of the states in all layers for the GraphChef recipe for BA-2Motiis Figure [ shows the recipe. Due to the base graph being a binary tree, degree two nodes (especially degree GraphChef can identify if they are part of the cycle after two layers. Therefore, we do not even need the whole cycle. This is consistent with the previous analysis on Tree-Cycle that the whole cycle is not necessary (Faber et al.) 2020 Himmelhuber et al. (02I). FigureBee Selws that we cannot trust explanation scores for cycles since they find only a subset of the motif.
those connected
nodes) are a strong indicator for cycles. For almost all nodes,
17

---

Published as a conference paper at ICLR 2024
A.4
TREE GRID
H5ghhorts25
SOM ES
SETON O011
(b)
(c)
Laver Madr-503
Neigho, 2eighb.
Neighbour 3515
Lopee 2
Gr
State
Stutks
senelca
(d)
(e)
(I)
Figure 9: GraphChef recipe for TREE-GRID. Table 8 shows an interpretation for all states in all layers. A degree check for degree 2 nodes find the corner nodes in the grid, after which we explore the remaining motif.
The Tree-Grid (Ying et al. 2019) dataset is similar to the Tree-Cycles dataset we discussed in the main body of the paper. The base graph a balanced binary tree to which we append 3 grids. As in the Tree-Cycles example. there are (apart from the root node) other nodes with degree 2 which makes bootstrapping the grid discovery easier. As in the Tree-Cycles example, a GNN does not need the whole grid make prediction. Table& shows the interpretation of the layers and states of GraphChef shown Figure A.4 The corner nodes in the grid can be quickly found with a degree check. The remaining grid can be found by exploring the neighborhood.
Some nodes can identify that they are part of the grid in just three layers - importantly the corner nodes generally belong this group. This means that these nodes do not need consider the opposite corner node at distance 4. GraphChef does not include this node in its explanation. This is consistent with the explanation accuracy Table 2 GraphChef achieves a bit more than which means that one node is missing.
18

---

Published as a conference paper at ICLR 2024
Layer
State
Decision Rule
Interpretation
Encoder
0
All nodes
No node features available for differenti- ation.
Layer
Three more state 0 neigh- bors
Degree 3 or higher nodes. (Inner tree nodes and grid nodes except corners) Degree nodes (leaves in the tree).
Layer
Less than two state neigh- bors
Layer
Two state 0 neighbors
Degree 2 nodes (root node, corner nodes in the grid).
Layer
At least as many state as state 4 neighbors and least two state neighbors More state 4 than state neigh- bors
Inner nodes in the tree and grid, except parents of leaf nodes.
Layer
Nodes connected to the root grid cor- ners. Leaves and their parent nodes.
Layer
At least many state as state 4 neighbors and at most one state neighbors Previous state 4 nodes Previous state nodes
Layer 2 Layer
Leaves and their parents.
Nodes connected the root or grid cor- ners.
Layer 2
Otherwise
Inner nodes in the tree and grid, except parents of leaf nodes. More corner and root nodes in the dis- tance 2 (can be the node itself) than leaves. This captures corner and cen- ter nodes in the grid Most nodes since they are connected to leaves not to the root.
Layer 3
More state 2 than state neigh- bors
Layer 3
4
At least as many state as state neighbors. At least two state 3 neighbors
Layer 4
2
Nodes with two grid neighbors, finding the remaining grid nodes.
Layer 4
4
At most one state 3 neighbor Layer 3 state 3 or layer state 2
Nodes with at most one grid neighbor. Corner or center grid node or nodes con- nected to two such nodes.
Decoder
Grid
Table 8: Analysis of the GraphChef recipe in Figure A.4 the Tree-Grid dataset. The base graph contains only one degree two node that is not part a cycle. degree check for two quickly finds the corner nodes of grids as starting point to discover the motif.
19

---

Published as a conference paper at ICLR 2024
A.5 BA- AA-SHAPES
5.5
Neighbour $33
1731 E-R-E
Clasr WITT
Cless
Stals
State
semppue 554
Laper
Stnk
Seges Neight
Nighbear
Stae
Paxk Sadte 0585
Sark
Dlonk 4
Yor
(e)
(L)
Figure 10: GraphChef recipe for BA-SHAPES. Table & shows an interpretation for all states in all layers. Degrees below 4 connected to more nodes with such degrees finds the general house. Middle nodes are degree 3 in this structure; Top nodes are connected both middle nodes; Bottom nodes are connected to one.
Let us now look at the BA-SHAPES dataset to classify each node with position in a house motif, or if the node is part of the Aerabasi-Albert base graph. Nodes in the base graph generally have high degree, we can find house nodes as being connected almost no high-degree nodes, but only among each other. From there subdivide house nodes: The middle nodes have 3 house neighbors, top node connected to both the middle nodes, and the bottom nodes only to one.
20

---

Published as a conference paper at ICLR 2024
Layer
State
Decision Rule
Interpretation
Encoder
0
All nodes
No node features available for dif- ferentiation.
Layer 0
0
Less than four state 0 neighbors
Degree 3 or lower nodes. (lower degree)
Layer 0
At least four state 0 neighbors
Degree 4 or higher nodes. (high degree)
Layer
2
At most neighbors of state 1
At most three high-degree neigh- bors. (House candidates, all nodes in the house have lower degree, the basegraph has many high-degree nodes).
Layer
4
At least four neighbors in state 1
At least four high-degree neigh- bors.
Layer 2
0
Three state 2 neighbors
Three house candidates in the neighborhood (middle nodes in the house).
Layer 2
At most state neighbors Previous state 4 nodes
Top or bottom of the house. At least four high-degree neigh- bors.
Layer 2
4
Layer 3
0
At most state neigh- bor
Nodes connected to zero middle house node. Middle house nodes. Top house nodes.
Layer
3
Previous state O At least two state neigh- bors
Layer 3
4
Layer 4
0
At least one state neigh- bor and previous state No state 3 neighbors At least one state neigh- bor but not previous state
Bottom house node: nodes con- nected to one house middle node. Nodes not connected to the house. Top node the house.
Layer 4 1
Layer
Decoder
Not in house
Layer state 4
At least four high-degree neigh- bors.
Decoder
Middle of House
Not above and layer 3 state 3
Three house candidates in the neighborhood.
Decoder
Bottom of House
Not above and layer state O
Nodes connected to house mid- dle node.
Decoder
Top of House
(but could have used layer state 4)
Otherwise GraphChef
Otherwise (or nodes connected two house middle nodes).
Table Analysis of the GraphChef recipe in Figure A.5 for the BA-Shapes dataset. The base graph has many edges, house nodes stand out by having a degree of or lower and being connected to such nodes.
21

---

Published as a conference paper at ICLR 2024
B GRAPHCHEF ON DATASETS WITH MANY INPUT FEATURES
GraphChef
Dataset
Features
GIN
Differentiable
No pruning
Lossless pruning
CORA
1433
0.87+0.02
0.82+0.03
0.69=0.04
0.68=0.03
CiteSeer
3703
0.77=00.01
0.70+0.03
0.61#0.04
0.61=0.02
PubMed
500
0.8811.011
0.8710.01
0.85+0.01
0.85
OBGN-Arxiv
128
0.68=0.02*
0.68+
0.28=0.11
Table 10: GraphChef results for citation datasets with high-degree counts. *Since the dataset has 40 classes, we use state-size of 50 for GraphChef variants and 128 wide embeddings for GIN.
In the following, we want to discuss GraphChef on gigh-dimensional datasets such Cora (1433) features. Table [O] a comparison of GIN, dish GNN and GraphChef similar to Table la The results are mixed: on Pubmed, GraphChef performs comparable GIN, on Cora there is small drop for dish GNN but significant drop when converting to trees. For CiteSeer, both dish GNN and converting to trees cause clear drops in accuracy.
see two factors that make this dataset challenging: Large feature spaces make it harder to reduce to a categorical state. For example, for Cora dataset, the encoder needs to reduce from 1433 to 10 features. This effect increases in GraphChef when limit the number of leaves: Having 100 decision leaves means that tree have 99 decision nodes and look at most at 99 features. But such trees are already impractical to interpret. We found that even after pruning, trees often contain long paths of depth 20 more. The problems aggravate on the larger OBGN-Arxiv dataset: dish GNN performs decently with a drop comparable to CiteSeer, but GraphChef drops drastically accuracy. Furthermore, this dataset reveals the scalability limits for GraphChef's pruning method: Pruning requires the number of leaves squared many runs over the dataset and does not scale to this dataset.
Therefore, we believe that handling such datasets requires a different approach. In future work, we imagine that these issues could be addressed through approaches such as PCA, clustering, or special MLP construction techniques (Wu et al. 2017a; [Schaaf et al. (201)) to reduce the input space without breaking the interpretability chain before applying GraphChef.
22

---

Published as a conference paper at ICLR 2024
C GENERATING EXPLANATIONS
In this section, we describe in detail how we can use GraphChef recipes to derive importance scores for the classification of single node/graph. As many existing explanation methods, these scores form a heatmap over all nodes to identify important inputs.
Formally, we are going compute scores of the form R where N is the number of nodes and S the number of categorical states. For simplicity, we assume that every layer has the same number of states. For one node u and one state s the explanation e(u, s) is real-valued vector that assigns every other node an importance how much contributes to u being in state We accumulate the importance over layers.
The importance of every node for the encoder layer is initialized as c(u, v) = 1, for every state where 1,, a vector that is 1 the index of u and 0 everywhere else. In other words, every node is its own explanation after the encoder.
To compute the explanation update for node u GraphChef layer, we investigate decision tree. First, we compute the Tree-Shap values for u in the decision tree. These values reveal how important each decision feature in the tree for predicting u, a value of 0 corresponds to an unused decision. Depending the type of decision feature
state feature, a message feature, delta feature (see possible cases in Figure 3) we will add explanation to nodes differently. We handle each decision feature independently and weigh it with its Tree-Shap value.
State features. There are possible state features that can each lead to S different new states. This yields S x S Tree-Shap values that we denote with (s, To compute explanations, additionally require the indicator variable sign(s (8) that is 1 u is in state s at the start of the layer, and -1 otherwise. This indicator allows to measure negative evidence that u is not in a certain state. The "propagation" of state features is then easy, since all importance stays with the node.
(l,,'')
Σ Ts( 8') e(u, 8) sign(s) SES
Message features. There are also S message features that can lead to S different states; thus, we have S S Tree-Shap values TM (s, s'). Computing the explanations for neighbor feature gives importance to each neighbor in the state s, normalized by the number of neighbors. Let N (s) denote u's neighbors in state s:
e(v, s)
p(u,8') = Σ ST)(s, #ES
Σ VEN(s)
[N(s)
Delta feeatures. We have 5 - S delta features where (s, s') encodes the feature that there are more neighbors in state s than neighbors in s'. Here, we use the Tree-Shap values TA ( s', s"). We also need the indicator variables (1l>(s.s)) that are 1 if indeed more neighbors are in the state rather than and 0 not. Now, explanation for delta features similar to that of neighborhood features, where the majority class contribution positive and the minority class contribution is negative:
8(,,8")= = E Σ T EVEN(S) e(v, s) EmENGy) e(u,s') 1 (2)0)))
"x,,"")=
[N(s) + [N()))
BES s'FEE
These explanations added to those of the previous layers: e(u, s) = e(us, s) + au,, s) + ulu, s) + 8(u,s).
Decoder layer The decoder layer is slightly special since uses skip connections. For node classification, directly concatenate all intermediate features and use the same computation scheme to compute the final explanations. For graph classification, we additionally need to pool the nodes. We do this layer-wise and supply the decoder layer with per-layer node counts per state. The decoder can then use counting and comparison features similar to M and A features in the GraphChef layers. The only difference that instead of propagating the explanation to neighbors, we now need to propagate it to all of the nodes in the graph that were in the corresponding states.
23

---

Published as a conference paper at ICLR 2024
D DATASETS
D.1 SYNTHETIC DATASETS
Infection Faber et al. (2021) synthetic node classification dataset. This dataset consists randomly generated directed graphs, where each node can be healthy or infected. The classification task predicts the length of the shortest directed path from infected node.
Negative Evidence Faber al. 2021)) synthetic node classification dataset. A random graph is created with ten red nodes, ten blue nodes, and 1980 white nodes. The task is to determine whether the white nodes have more red blue neighbors.
BA Shapes Ying al. 2019) synthetic node classification dataset. Each graph contains a Sarabasi-Alber (BA) base graph and several house-lite like motifs attached to random nodes of the base graph. The node labels are determined by the node's position the house motif or base graph.
Tree Cycle Ying et al. 2019) is synthetic node classification dataset. Each graph contains an 8-level balanced binary tree and six-node cycle motif attached to random nodes of the tree. The classification task predicts whether the nodes part of the motif tree.
Tree Grid Ying al. (2019) is synthetic node classification dataset. Each graph contains an 8-level balanced binary tree and a 3-by-3 grid motif attached to random nodes of the tree. The classification task predicts whether the nodes part of the motif the tree.
BA 2Motifs Luo al. (2020) is synthetic graph classification dataset. Barabasi-Alba graphs are used as the base graph. Half of the graphs have house-like motif attached to random node, and other half have five-node cycle. The prediction task is classify each graph whether it contains a house or a cycle.
(a) Infection Input
(b) Infection Prediciton
(c) Saturation Input
(d) Saturation Prediciton
(e) BA Shapes Input
(f) BA Shapes Prediciton
(g) Tree Grid Input
(h) Tree Grid Prediction
(i) BA 2Montif's House
(j) BA 2Montifs Cycle
Input
Input
Figure 11: Synthetic Benchmarks
Example Graphs
24

---

Published as a conference paper at ICLR 2024
Dataset
Graphs
Classes
Avg. Nodes
Avg. Edges
Features
Infection
1
1000
3973
2
Negative Evidence
1
2000
102394
BA Shapes
1
700
4110
Tree Cycle
1
871
1942
Tree Grid
1
1231
3130
BA 2Motifs
1000
2
25
50.96
Table 11: Statistics of Synthetic Datasets
D.2 REAL- WORLD DATASETS
MUTAG Debnath et al. (991)) is a molecule graph classification dataset. Each graph repre- sents a nitroaromatic compound, and the goal predict its mutagenicity Salmonella typhimurium. Mutagenicity is the ability of a compound to permanently change the genetic material, usually DNA, an organism and therefore increase the frequency of mutations. The nodes in the graph represent atoms and are labeled by atom type. The edges represent bonds between atoms.
Mutagenicity Kazius al. 2005) is molecular graph classification dataset. Each graph represents the chemical compound of drug, and the goal is to predict its mutagenicity, The nodes the graph represent atoms and are labeled by atom type. The edges represent bonds between atoms.
BBBP Wu et al. (b01 is a molecule graph classification dataset. Each graph represents the chemical compound of drug and the goal predict its blood- boain barrier permeability, The nodes in the graph represent atoms and are labeled by atom type. The edges represent bonds between atoms.
PROTEINS Borgwardt al. (2005) is protein graph classification dataset. Each graph represents protein that is classified as an enzyme not as an enzyme. The nodes represent the amino acids, and an edge connects two nodes if they are less than angstroms apart.
REDDIT BINARY (Brrwwrrtt et al. 2005) is social graph classification dataset. Each graph represents the comment thread of a post on subreddit. The nodes in the graph represent users, and there is an edge between users one responded least one of the other's comments. A graph is labeled according to whether it belongs to question-/answer. based discussion- based subreddit.
IMDB BINARY Borgwardt et al. (2005) social graph classification dataset. Each graph represents the ego network of an actor/actress. In each graph, the nodes represent actors/actresses, and there is an edge between them if they appear in the same film. A graph is labeled according to whether the actor/actress belongs to the Action or Romance genre.
COLLAB Borgwardt et al. (2005) is a social graph classification dataset. A graph represents researcher's ego network. The researcher and his collaborators
nodes, and edge indicates collaboration between two researchers. A graph is labeled according to whether the researcher belongs to the field of high-energy physics, condensed matter physics, or astrophysics.
Cora, CiteSeer, and PubMed are popular citation networks (Yang et al. 2018b). Nodes are papers, and citations edges. Nodes contain features that represent words of their contents and are labeled by subfields.
25

---

Published as a conference paper at ICLR 2024
(a) MUTAG Input
(b) Mutagenicity Input
(c) PROTEINS Input
(d) Reddit Binary Discussion
(e) Reddit Binary Q/A
(f) IMDB Binary Input
(g) COLLAB Input
Figure Real-world benchmarks Exxmmle graphs
Dataset
Graphs
Classes
Avg. Nodes
Avg. Edges
Features
MUTAG
188
2
17.93
39.59
Mutagenicity
4337
30.32
61.54
14
BBBP
2039
2
24.06
51.91
9
PROTEINS
1113
2
39.06
145.63
REDDIT BINARY
2000
2
429.63
995.51
IMDB BINARY
1000
2
19.77
193.06
COLLAB
5000
3
74.49
4914.43
Cora
2485
5069
1433
CiteSeer
6 2110
2668
3703
PubMed
3
19717
44324
500
Table 12: Statistics of Real-World Datasets
26

---

Published as a conference paper at ICLR 2024
E EXPERIMENT SETUP
We do a 10-fold cross-validation of the data with different splits and train both GraphChef and baseline GIN architecture. GNNs are trained on the training for 1500 epochs, allowing early stopping on the validation loss with patience of 100. Each split uses early stopping on the validation score. Both GNNs use 2- layer MLP for the update function, with batch normalization (lofte and ] 2015) and ReLu (Nair and Hinton 2010) in between the two linear layers. We use 5 layers of graph convolution. GIN uses a hidden dimension of 16, GraphChef uses state space of 10. We also further divide the training set for GraphChef to keep holdout set for pruning decision trees. After we train dish GNN with gradient descent, we distill the ML.s into decision trees. Each tree limited to having maximum of 100 nodes.
GraphChef allows us to self-tune some hyperparameters. After training, we can inspect how many layers and categorical states are actually used in the recipe for dataset. Table shows the layers and states used for each dataset. After training, we can inspect the recipes from GraphChef and validate if all states and layers necessary. If we find that the recipe uses fewer layers or states, retrain with that number of layers or states. Table 13 shows the number of layers and states that we find per dataset. A full model is used for GIN.
Layers
States
Infection
5
Negative
1
BA-Shapes
5
Tree-Cycles
5
Tree-Grid
5
BA-2Motifs
MUTAG
4
Mutagenicity
3
BBBP
3
PROTEINS
3
IMDB-B
3
REDDIT-B
COLLAB
3
Table 13: Tuned hyperparameters through GraphChef self-inspection
27

---

Published as a conference paper at ICLR 2024
F
USING THE TOOL
States per node for the current layer
Decision tree for the current layer
Layer O: State
samples girl 0.500
1073
054
1455
722
31
Closs Class 1
Input: State
903
cemples 1030
samples 7920
611
377
1539
1002
1823
919
Class: Class
Class: Class
sumplis 8000
sumplea
Switch between the layers
CaN Lswer
Ne
Oio Mel Oten
Frew Berr
ACC Tan Lod. Tept (106)
Connet Foiedin
Genge Kuger 2017
Toggle between showing the states of nodes before or after the selected layer
Train and test accuracy. Use the "Prune Trees" slider to apply the lossy pruning
Switch between datasets
Switch between graphs per dataset
Figure 13: Initial page for the web tool. We can the decision trees for GraphChef per dataset and which node for a graph is in what state. We can switch layers, graphs, and datasets. We can also see the test accuracy for the current setting and choose an amount of lossy pruning. with the slider.
An example instance of the tool is deployed and available via Netlify and can be accessed under the link tailhhtp:::// /ttp:::::/i/eeeeeeeeeeeeeette centerrretbble / wwweeetbbleenn.....ee www.ify. app/] The supplementary material also contains code to host the interface yourself, in you want to try variations of GraphChef. In the backend, we use Py'oorch (Paszke et al. 2019 3 and PyTorch Geometric (Fey and Lenssen 2019 to to train the decision trees.
train GraphChef and ePederoPPaae al. 2011
The tool is built with React, in particular the Ant Design library We visualize graphs with the Graphin library The interface is single page that will look similar Figure 13
The largest part of the interface is taken up by two different panels at the top. In the right panel, you see the decision tree for the currently selected layer. The trees the three branching options from Figure 3 In the interface, evaluating the branching to true means taking the left path (this is opposite Figure which
will flip). In the left panel, you can see an example graph and which nodes end up in which state after this layer (on the bottom left you can toggle to see the input states instead). This panel does not show the full graph (most graphs in the datasets are prohibitively large), but rather an excerpt around an interesting region. Directly below these two graphics, you have the option to switch between layers by clicking on the respective bubble.
In the bottom right, you can switch to different graph in the same dataset or to different dataset. In the center, you can see the accuracy of GraphChef with the displayed layers. The slider allows one to apply the lossy pruning from Section 3.3 and the accuracy values update to the selected pruning level.
https://netlify.
28

---

Published as a conference paper at ICLR 2024
The interface also allows examine single node closely by clicking on it (see Figure 14 here we clicked on the blue node on the very right). Selecting reveals two things: In the graph panel. you the explanation scores from Section for this node in this layer. In the tree panel, you can see the decision path in the tree for this node. This particularly helpful multiple leaves in the tree would lead to the same output state in this example.
Layer State
gett
963
Ciee: Class
Input: State
0.53T
7030
1350
Saz9
Clicked Node
257
Class
Class Class
Figure 14: Interface when clicking on a node for closer examination. We can see node-level importance scores for this node the left and the decision path taken the right. Two paths end in the blue state, shown by the red boxes. The path the node takes is highlighted, the other path is blurred out.
29


Reviews:
[{"review_id": "ZMh9O1PKV1", "reviewer": "Reviewer_U2So", "summary": "This paper integrates decision trees into the message-passing framework of GNNs and proposes a self-explanatory GNN model called GraphChef. Inspired by the Stone-age model, GraphChef utilizes the Gumbel-Softmax function to induce categorical latent states for GNN layers, then uses the categorical inputs and outputs and distills them into decision trees. Since the decision-making process of decision trees is comprehensible to humans, GraphChef is able to provide a series of recipes to help us understand the behavior of GNNs. The authors have designed a series of pruning strategies for training decision trees to prevent overfitting, and experiments show that while providing interpretability, GraphChef also ensures expressive power on par with GIN on certain datasets.", "questions": "- Regarding the training process of the decision trees, how are the three different types of branches (as shown in Figure 3) chosen during the training procedure? Also, which training algorithm is employed, C5.0 or CART?\n\n- Why does the structure of GraphChef often require more than five layers?\n\n- Why does the expressive power of GraphChef surpass GIN on certain datasets, and can you provide some qualitative analysis?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Unlike previous approaches that identify substructures or sub-features of the original input most relevant to the output, GraphChef offers a unique perspective for interpreting GNNs. The \"recipes\" it returns reflect higher-level behaviors of the model. Concurrently, GraphChef still provides a method to calculate heatmap-style importance scores for individual graphs.\n- The authors have designed a diverse and comprehensive set of network architectures for GraphChef, ensuring its suitability for both graph classification and node classification tasks.\n- The authors have developed pruning strategies for GraphChef that enhance readability and prevent overfitting, while only sacrificing a minimal amount of performance.\n- The recipes extracted by GraphChef on some small datasets are in alignment with human intuition.", "weaknesses": "- As the authors mentioned, a limited number of categorical states may restrict its expressive and interpretive power on large datasets, since the feature space of the inputs in large datasets is often vast. It is conceivable that the decision trees generated by GraphChef would also be immense, and an overly large decision-making process can be difficult for humans to directly comprehend.\n- For self-explanatory models, we usually need to understand the trade-off between interpretability and expressive power. However, I did not see such an analysis in this paper, which means we are unable to comprehend the model's balance between expressiveness and interpretability.\n- Pairwise Comparisons require O(n^2) space complexity, which is impractical for large-scale datasets (if a large state size is needed).\n- Although GraphChef can provide a series of decision rules to help us understand the behavior of GNNs at a higher level, the authors' experiments are all based on small-scale datasets (most of which are synthetic), and for complex real-world datasets, these decision rules may still be complex and difficult for humans to understand, especially when the decision trees are deep.\n- While the introduction of decision trees into the interpretation of GNNs is novel, concepts such as the Stone-age model, transforming categorical states to decision trees, and decision tree pruning are not new.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j5u3jKqnKO", "reviewer": "Reviewer_2TRZ", "summary": "This paper proposes an explainable GNN model by combining decision trees into message passing framework. The idea is interesting and novel. The paper is well written and easy to understand. The main advantage of the proposed method is its ability to explain the whole dataset as compared to the existing methods that focus on explaining individual graphs in the data.", "questions": "1. Please clarify the usage of Gumbel-Softmax to the latent embeddings in detail. I had a hard time understanding this.\n\n2. Why is performance of GIN and GraphChef is similar as listed in Table 1?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The main strength is its ability to explain the whole dataset as compared to the existing methods that focus on explaining individual graphs in the data.", "weaknesses": "n/a", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1U3PRh6gEz", "reviewer": "Reviewer_VFKG", "summary": "The paper presents an interesting idea of learning decision trees to get explainable models for graph learning tasks. Tree models have a long history and are well known for their explainability. Direct training of tree models on a graph is not straightforward. This work proposes a method of casting a decision tree from a trained neural model. In the empirical evaluation, the tree model shows slight accuracy drop but provides much better explanations.", "questions": "A few key steps are missing from the paper. Here are two questions. \n\nFirst, how does the model pool the information to get a graph representation? \n\nSecond, the dish model uses \"Gumbel-Softmax\" to GNN layers. As far as I know \"Gumbel-Softmax\" is designed for sampling continuous variables that approximate the categorical distribution. I don't understand why randomness is needed here. \n\nThird, \"We bootstrap the internal state h^0_v with an encoder layer on the initial node features x_v\" -- what does \"bootstrap\" mean?\n\nFourth, what does \"encoder\" and \"decoder\" mean? Do you use an autoencoder to recover the input or not?\n\nFifth, how many layers do you use in your model?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The idea of training decision trees from graph data is novel. It distills neural models to decision trees. It has several designs (e.g. via the dish network) that make the distilling possible. \n\nThe results of the paper show that the proposed method can provide better explanations while has slight performance drop.", "weaknesses": "In the empirical evaluation the work shows good performance. However, there should be some theoretical bound over the ability of the tree model. For example, it cannot exceed the expressiveness of the 1-WL algorithm. At the same time, it is unknown whether it can even match the ability of the 1-WL algorithm. I think a theoretical analysis is missing from the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QajRDej9sU", "reviewer": "Reviewer_8CuG", "summary": "This paper introduces GraphChef, a Graph Neural Network (GNN) model that integrates decision trees to provide human-comprehensible explanations for each class in a dataset. The authors note that while GNNs are popular for graph-based domains, they are often black-box models that lack interpretability. GraphChef aims to address this issue by generating decision trees that show how different features contribute to each class. The authors demonstrate the effectiveness of GraphChef on the PROTEINS dataset and other explanation benchmarks that require graph reasoning. They also highlight the importance of small trees to ensure that the generated recipes are understandable to humans. Overall, GraphChef provides a promising approach for generating interpretable explanations for GNNs.", "questions": "I have no question.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\n- The integration of decision trees with GNNs to provide human-comprehensible explanations is a novel approach that has not been explored extensively in the literature.\n- The authors also introduce a new benchmark dataset for graph-based explanation methods, which can be used to evaluate the effectiveness of different models.\n\nQuality:\n- The authors provide a thorough evaluation of GraphChef on multiple datasets and benchmarks, demonstrating its effectiveness in generating interpretable explanations for GNNs.\n- The paper includes detailed discussions of the limitations and future work of GraphChef, which can guide future research in this area.\n\nClarity:\n- The paper is well-organized and clearly written, making it easy for readers to follow the authors' arguments and understand the technical details of GraphChef.\n- The authors provide several examples and visualizations to illustrate the effectiveness of GraphChef in generating human-comprehensible explanations.\n\nSignificance:\n- The lack of interpretability of GNNs is a significant challenge in many graph-based domains, and GraphChef provides a promising approach for addressing this issue.\n- The authors highlight the potential applications of GraphChef in safety-critical domains such as medicine, where it is important to understand how decisions are made.\n- The paper also contributes to the broader goal of developing explainable AI methods, which can increase trust and transparency in machine learning models.", "weaknesses": "The authors note that GraphChef can struggle to create recipes for datasets with a large feature space, which limits its applicability in some domains. Future work could investigate alternative methods for combining multiple features into one split to address this limitation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N8UfEj89Hk", "reviewer": "Reviewer_2W2r", "summary": "The described work presents GraphChef, a method for achieving explainability in Graph Neural Networks (GNNs). It distills GNNs into decision trees with categorical hidden states using Gumbel softmax, essentially creating interpretable decision trees from the trained GNN. The decision trees are then pruned for interpretability based on accuracy. Evaluations on benchmark datasets show that while GraphChef maintains accuracy on some tasks, it may sacrifice performance on others in favor of obtaining an interpretable decision tree.", "questions": "How does the model perform on large datasets?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The article presents an innovative approach to achieving interpretability in Graph Neural Networks (GNNs) by replacing original network modules with interpretable ones, demonstrating that this approach maintains comparable learning performance. This is a novel solution to a significant problem in GNN research.\n\n2. The paper differentiates itself from previous work by focusing on the extraction of global decision rules for entire datasets rather than providing localized explanations for individual outputs. This unique perspective on GNN interpretability is practical and valuable.\n\n3. The article is well-structured, easy to understand, and supported by comprehensive empirical evaluations. It also offers a user-friendly web interface for visualizing decision trees, making it accessible for downstream usage. This approach is both novel and promising for improving the interpretability of GNNs.", "weaknesses": "1. The method's applicability is restricted to graphs with very few features, making it unsuitable for more complex datasets. The authors acknowledge this limitation, but addressing it could involve techniques like dimension reduction or prototype learning when discretizing the hidden states to handle more feature-rich graphs.\n\n2. The proposed method's use of one-hot hidden states may reduce the model's expressiveness, especially for complex problems. For these, the resulting decision trees could become overly complex and challenging to interpret.\n\n3. The method's performance in terms of explanation is described as only \"comparable\" to post-hoc methods, and it may not offer significant advantages over using standard GNN models followed by post-hoc interpretability techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)