GraphChef: Decision-Tree Recipes to Explain Graph Neural Networks

Thank you for your review and your comments and comments. We hope that our answers below help resolve any questions or potential misunderstandings.

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.

We think there has been a misunderstanding. The models are comparable if we focus on the explanation scores in Table 2. But we think GraphChef offers a superior form of explanation as we show in Figure 1. We see the main improvement and also the main contribution of this paper is that we can not only find the important nodes/edges but also explain why thes nodes/edges are important. Note that standard post-hoc methods only give you a heatmap of importances, which constitutes a fundamental loss of information on why exactly the model made the given choices. So it’s impossible to recover true, not some implied or supposed, decision making logic from these heatmaps. Which is a fundamental limitation of the standard post-hoc methods.

How does the model perform on large datasets?

Larger datasets may also pose problems for interpretability: Generally, larger datasets come with more edge cases which require more states and larger trees to adequately handle. Trees can become harder to interpret. Two approaches to tackle this are using the lossy pruning to aggressively first understand the core predictions paths and slowly grow the trees. Furthermore, GraphChef also offers explanation scores like existing explanation methods that scale to large trees with many states. explanation scores that we compute like existing explanation methods scale with the number of states and layers and can help guide the user like existing methods do.

Thank you for your review and your comments. We agree with you that the novel decision-tree powered explanations are a promising approach for interpretability and that tackling the datasets with large feature spaces is the a very promising direction for future work.

Thank you for your review and your comments and comments. We hope that our answers below help resolve any questions or potential misunderstandins.

I think a theoretical analysis is missing from the work.

We made a maybe too short theoretical argument at the end of the Subsection 3.1. In principle, instead of having a $log(d)$ bits, we can use $d$ many encoded bits. For example, we can represent a GIN that uses just a single embedding that we assume is encoded in 32 bit floats as a stone age GNN with 2^32 = states (which is roughly 4 million). This is of course impractical and impossible to train, but, in principle, the stone-age layers also have 1WL power.

If we only concern ourselves with the graph structure (ignore node features for a moment), one can easily see that actually just O(n) states are enough to achieve 1-WL expressive power, as the original 1-WL algorithm that GIN is able to simulate uses discrete states and at most needs n different colors (states). So theoretically it is straightforward to make GraphChef as expressive as standard GNNs (1-WL). But since the GNN expressive power hierarchy is not fine grained it's hard to characterize precisely the impact of shrinking the categorical space has on expressive power. That is why we focused on the empirical comparison to GIN.

First, how does the model pool the information to get a graph representation?

Let us look at an example graph with two layers and three states. The output layer would get pooled information per layer: How many nodes are in state 1, 2, 3 after the first layer and how many nodes are in state 1, 2, 3. after the second layer. In total, there would be 6 features available to the output layer. Of course, the number of states must not be the same per layer.

Second, 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.

That is correct, the randomness is only used during training to allow exploring a wider decision space. Especially in the beginning of training, the model predictions are purely random and sampling allows us to explore the search space well. We increase the softmax temperature during training to converge the distribution towards a one-hot distribution. Removing the randomness at the start of the training might result in gradient descent getting stuck. During testing we turn the Gumbel-Softmax off completely in favor of a direct argmax.

Third, "We bootstrap the internal state h^0_v with an encoder layer on the initial node features x_v" -- what does "bootstrap" mean? Fourth, what does "encoder" and "decoder" mean? Do you use an autoencoder to recover the input or not?

We used the terms encoder and decoder to emphasize the layers that do not have any GNN message passing. These GNN layers start with categorical values on each node and produce a categorical value on each node. On the other hand, the encoder translates the input features from the input domain (which need not be categorical, for example if we perform regression) to categorical states. The decoder (or readout) layer reads the intermediate and final states (potentially pooled) as outlined above to compute a prediction.

“Bootstrap” was probably a slightly misleading term to use here. We will clarify this to something similar to the above.

Fifth, how many layers do you use in your model? We allow the model to use up to five layers. Afterwards, we inspected the recipes how many layers the model actually use - Table 13 in Appendix E shows how many layers were actually used.

Thank you for your review and your comments and comments. We hope that our answers below help resolve any questions or potential misunderstandins.

Please clarify the usage of Gumbel-Softmax to the latent embeddings in detail. I had a hard time understanding this. The Gumbel-Softmax happens at the very end of the embedding computation. In principle, you could imagine that we first run a normal GIN to produce embeddings which are $d$ numbers. Now we additionally apply the Gumbel Softmax on those numbers to instead sample a one-hot encoded vector of size $d$. Now this has the following implications:

We already do this to the inputs before the first message passing layer (and every subsequent one). Therefore, the node embeddings (which are the messages) for all of the message passing layers are already one-hot encoded. The summation of neighborhood messages becomes counting the neighbors in each state. When we want to replace the neural functions by a decision tree, we can treat each layer like a tabular classification problem: In the beginning of each layer we have three inputs: the previous one-hot state, the message counts, and the pairwise differences. We want to predict the output of the layer, which is a categorical variable.

Why is performance of GIN and GraphChef is similar as listed in Table 1? The selling point of Table 1 is precisely that we can have a fully interpretable model that performs similarly to standard GNNs (i.e. GIN). Note that GraphChef has the same expressive power as GIN if sufficiently many categorical states are used ( O(n) ). To have an easily interpretable model we do use smaller embedding spaces, but the similar performance of GIN and GraphChef hints that a very high information throughput in the messages (high-dimensional embeddings) is not necessary for these tasks in particular.

Thank you for your review and your comments and comments. We hope that our answers below help resolve any questions or potential misunderstandins.

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.

Theoretically, the differentiable categorical layer is actually as expressive as a standard GNN (e.g. GIN) if sufficiently many states are used. The original 1-WL test that upperbounds the standard GNN expressive power as proposed originally actually uses categorical states (colors) and needs up to N of them. As GNN expressive power hierarchy is not very fine grained, besides the k-WL levels, it’s hard to analyze the gradual expressive power loss when reducing the number of categorical states below N. However it is worth noting that in very many cases one can get away with running the 1-WL algorithm successfully with the number of colors << N.

Practically, we do not have to heavily pre-constrain the model to a particular tradeoff of expressiveness and interpretability. Rather, we ask the decision trees to maximize expressiveness with a weak constraint for interpretability: Every decision tree is limited to 100 nodes (for computational efficiency). We leave the balance to the human after trees are trained through pruning: By choosing which level of deterioration is acceptable we can trade-off large but accurate trees versus smaller and more interpretable ones. This dynamic pruning can also be easily seen and experimented with in our provided web interface.

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?

The branches are chosen by the decision tree learning algorithm. Let us assume the state size of 3 as in Figure2: This means that decision trees receive a 12 long input vector to predict the categorical output. By the way we order the 12 features: the first 3 features correspond to the one-hot encoded previous state and we use a branch like Figure 3a). The next 3 features correspond to the message aggregation with a branch like Figure 3b) and the remaining features are delta features as in Figure 3c).

We used the sklearn version of CART https://scikit-learn.org/stable/modules/tree.html#tree-algorithms-id3-c4-5-c5-0-and-cart

Why does the structure of GraphChef often require more than five layers?

GraphChef actually uses five or less layers: Table 13 in the Appendix shows the number of layers per dataset. We trained an initial version with 5 layers for all dataset, but inspecting the recipes shows that GraphChef does not always use all 5 available layers.

Why does the expressive power of GraphChef surpass GIN on certain datasets, and can you provide some qualitative analysis?

Does this question refer to the results in Table 1 for the datasets Infection, BA-Shapes, BBBP, PROTEINS, or REDDIT-B? The scores are very close and overlapping when we consider the standard deviations. We attributed these to chance. The perhaps only substantial outperformance is by GIN on the Mutagenicity dataset.