What Does My GNN Really Capture? On Exploring Internal GNN Representations

1 Introduction

Graphs are a powerful and popular data structure used to represent relational data. One of their specificity is that their underlying structure does not form a Euclidean space, characteristic that facilitates the direct use of generic machine learning techniques. To overcome this difficulty, Graph Neuhv ∈ RK to

represent each node v as a vector of fixed dimension K that eases comparison between similar nodes. GNN methods employ a message propagation strategy that recursively aggregates information from nodes to neighbouring nodes and produce vector representations of ego-graphs centered in a node v with radii equal to the recursion index so that to optimize a classification task based on these vectors.

1.1 RelatedWork

Although GNNs achieve exceptional performance in many tasks, a major drawback is their lack of interpretability. The last five years have witnessed a huge growth in the definition of techniques for explaining deep neural networks [Burkart and Huber, 2021; Molnar, 2020], especially for image and text data. However, these methods cannot be directly used for explaining GNN due to the none grid-like format of graphs [Yuan et al., 2020b]. Nevertheless, a few proposals have been made to explain GNNs according to two distinct approaches and have gained visibility.

Instance-level methods aim to learn a mask seen as an explanation of the model decision for a graph instance. These methods provide explanations specific to an input graph by identifying its important characteristics on which the model builds its prediction. We can identify four different families of methods. The gradient/feature-based methods [Baldassarre and Azizpour, 2019; Pope et al., 2019] - directly adapted from dedicated image and text solutions - use the gradients or hidden feature map values to compute the importance of the input features. The perturbation-based methods [Ying et al., 2019; Luo et al., 2020] aim at learning a graph mask by studying the prediction changes when perturbing the input graphs. The surrogate methods [Huang et al., 2020; Vu and Thai, 2020] explain an input graph by sampling its neighborhood and learning an interpretable model. The decomposition-based methods [Pope et al., 2019; Schnake et al., 2020] start by decomposing the prediction score to the neurons in the last hidden layer. Then, they back-propagate these scores layer by layer until reaching the input space. On top of that, GraphSVX [Duval and Malliaros, 2021] falls into these 4 categories by learning a surrogate explanation model on a perturbed dataset that decomposes the explained prediction among input nodes and features based on their contribution. These methods perform well on metrics evaluating the relationships between explanations and model decisions. However, it appears that these masks can lead to unreliable explanations, and most importantly, can lead to misleading interpretations for the end-user. One can be tempted to interpret all the nodes or features of the mask as responsible for the prediction leading to wrong assumptions. For instance, a node feature may be perceived as important for the GNN prediction, whereas there is no difference between its distribution within and outside the graphs validating the mask.

Model-level methods. The only existing model-level method is XGNN [Yuan et al., 2020a] which aims at training a graph generator to maximize the predicted probability for a class and uses such graphs to explain this class. However, it is based on the strong assumption that each class can be explained by a single graph, which is unrealistic when considering complex phenomena.

Most of the aforementioned methods aim at either explaining the final decision of a GNN or generating a representative graph for a given decision. We believe that focusing only on the model decision does not allow to fully understand how the model behaves and builds its decision. One can provide additional insights about the GNN by not only looking at the output of the model, but also by trying to characterize some representation subspaces that the model has built in the different layers.

1.2 Contribution

We introduce a new method, called DISCERN (DISClosing the IntERnal workings of gNns with graphs), that aims at characterizing interesting internal representations of the GNN with graphs as illustrated in Figure 1. In each hidden layer of the GNN, we identify sets of neurons that are differently activated according to the output variable. Such activation rules capture specific configurations in the embedding space of a given layer that is discriminant for the GNN decision. We believe that such activation rules also catch hidden features of input graphs. However, these activation rules cannot be easily interpreted by human beings. Our goal is then to explain each activation rule by generating a graph that fully embeds in the related subspace identified by the rule. To this end, we define a proximity measure to assess how close a graph is to an activation rule and optimize this measure using a Monte Carlo Tree Search (MCTS).

Our main contributions are as follows. We introduce the novel problem of identifying activation rules and their characterization with subgraphs (Section 2). We report an empirical evaluation on three real-world datasets (Section 3) where we show that our activation rules identify masks of higher quality than SOTA methods and that DISCERN provide good explanations with realistic graphs compared to baselines. The code source of the method is made available: https://github.com/luvf/inside-gnn.

1.3 Targeted Audience

Imagine you are a scientist who has a GNN that accurately predicts the graphs you are studying. This means that the GNN is able to capture interesting features and combine them. Therefore, understanding how the GNN constructs its internal representation would shed new light on your field of research. This is our goal.

2 Method

We propose an introspective method to explain GNN decisions in a post-hoc manner. The method identifies sets of neurons that work together in the decision-making process, called activation rules, and characterizes them with subgraphs.

2.1 GNN Embedding Vectors

We consider a set of graphs G with labels, G = (V,E,L) with V a set of vertices, E a set of edges in V × V , and L a mapping between vertices and labels of T: L ⊆ V × T. We study GNNs that classify each graph of G into two categories {0, 1}: GNN : G→ {0, 1}. The GNN takes decisions at the level of each graph on the basis of vectors, the neurons, computed at the level of the nodes of each graph. For each node, ego-graphs of increasing radii are embedded in a Euclidean space in such a way that similar ego-graphs are associated to similar vectors. Indeed, we consider Graph Convolutional Networks (GCN) [Kipf and Welling, 2017] that compute vectors hℓv associated to the ego-graph centered in vertex v with radius ℓ, recursively by the following formula: hℓv = ReLU (Wℓ · ∑w∈N(v) ew,v √dvdw hℓ-1 v ), ev,w is the weight of the edge between nodes v and w, N(v) is the set of neighboring nodes of v including v, ReLU is the rectified linear activation function, and Wℓ are the parameters learnt during the training phase of the model. We also have dv = ∑w∈N(v) ev,w and h0v is the initial feature vector for node v with the one-hot encoding of its label from T. Each vector is of size K and ℓ varies from 0 up to L (the maximum number of layers in the GNN), two hyperparameters of the GNN.

Once the GNN learnt, the vectors hℓv capture the key characteristics of the corresponding graphs on which the classification decision is made. When one of the vector components is of high value, it plays a role in the decision process. More precisely, activated components of the vectors - the indices k such that (hℓv )k > 0 - are combined by the neural network in a path leading to the decision, either 0 or 1. For a given layer ℓ, the activated components of the embedding hℓv correspond to the part of the ego-graph centered in v and of radius ℓ that triggers the decision.

2.2 Activation Rules

To shed light on the inner workings of GNN, we seek to identify sets of neurons that are co-activated for a given class. Activation rules are groups of vector components that are mostly activated together in graphs having the same GNN decision. We say that a rule R ≡ Aℓ → c, with Aℓ a binary vector of size K and c ∈ {0, 1}, is activated for a graph gi = (Vi,Ei,Li) ∈ G if there exists a node v in Vi whose components in layer ℓ that correspond to the activated components of the rule are also co-activated, that is iff ∃v ∈ Vi such that if Aℓk = 1 then (hℓv )k > 0. The graphs of decision c for which Aℓ is activated constitute the sup-

We evaluate the interest of a rule using an interestingness measure based on the FORSIED framework [De Bie, 2011] that makes possible to measure the subjective interest of a rule using information theory to quantify both its informativeness and its complexity. Suppose that knowledge of the distribution of activated neurons over the nodes is formalized by a probability distribution P, called background distribution. From this distribution, we can define an optimal code to transmit a pattern, a set of activated neurons, to a user. This optimal code is specified as -log(P(x)) for data x. The more probable the user judges the data to be, the shorter the code describing it would be. Thus, by estimating the probability P((hℓ )k, v) that the component (hℓ )k is activated for a node v, we can evaluate the interest of a rule by the length of the code for communicating the rule to the user using the sum of -log(P((hℓ )k, v)) over all (hℓ )k of the rule and v, an activated node in its support graphs. The more probable the pattern - and therefore the less interesting - the shorter the code. As there may exist several nodes activated in a single graph, we choose the one that maximizes the above value and define the Information Content as: IC(R) = ∑g=(V,E)∈supp(R) maxv∈V - ∑x∈Aℓ log(P(x, v)).

The initial background distribution P is estimated using the Maximum Entropy Principle (other distributions introducing additional knowledge unduly [De Bie, 2011]) coercing the distribution by the frequency of activation of each component on the nodes of the graphs and by the average number of activated components per nodes. The explicit mathematical MaxEnt model solution can be found in [De Bie, 2009].

A rule with a large IC is more informative, but it may be more difficult for the user to assimilate it, especially when its description is complex. To avoid this drawback, the IC measure is contrasted by the description length which measures the complexity of communicating the rule to the user. The higher the number of components in Aℓ , the more difficult to communicate it to the user. Therefore, we propose to measure the description length of an activation rule by DL(Aℓ ) = a(|Aℓ |) + b with a the cost for the user to assimilate each component and b a fixed cost for the rule. We set b = 1 and a = 0.6, as the constant parameter b does not influence the relative ranking of the rules, and with a value of 1, it ensures that the DL value is greater than 1. With a = 0.6, we express a slight preference toward shorter rules. Hence, the subjective interestingness measure of an activation rule is SI(R) = IC(R) DL(Aℓ ) .

To measure how a rule R is specific to a GNN decision, we compare SI(Aℓ → c) with SI(Aℓ → 1 - c): SI SG(Aℓ → c) = ωcSI(Aℓ → c)-ω1-cSI(Aℓ → 1-c). The weights ω0 and ω1 are used to counterbalance the measure in unbalanced decision problems. The rational is to reduce the SI values of the majority class. We set ω0 = max(1, |GNN(gi)=1| |GNN(gi)=0| ) and ω1 =max(1, |GNN(gi)=0| |GNN(gi)=| ).

Activation rules are computed in an iterative way. First, the activation rule that maximizes SI SG is computed with an enumerate-and-rank approach. Then, the knowledge bring by the rule is integrated into the background distribution P to force the extraction of diversified rules. Once the rule is known, its subjective interest falls down to 0. This consists in setting the probabilities corresponding to the rule components and its supporting nodes to 1. Then, the process is iterated a fixed number of times or until there is no more rule with a positive SI SG value. Details can be found in [Veyrin-Forrer et al., 2021].

2.3 Characterizing Activation Rules with Subgraphs

For each activation rule, we seek to identify a subgraph whose presence in an input graph triggers the rule. For this, we are looking for a subgraph whose GNN embedding in layer ℓ is as close as possible to the activation rule. This requires defining a measure of proximity between embedding and activation rule and finding the subgraph that maximizes it.

We propose two measures to evaluate the proximity between an ego-graph embedding hℓv and an activation rule Aℓ → c, with Aℓ = {a1, . . . , aK}, ai ∈ {0, 1}. We denote by Eg = {ϵ1, . . . , ϵK} the ego-graph embedding truncated to fit the interval [0, 1]: ϵk = min (max(0, (hℓv )k), 1). The truncation avoids distorting our measurements by extreme values. The cosine measure evaluates the similarity between Eg and Aℓ : Cos(Eg,Aℓ ) = Eg . Aℓ ‖Eg‖ ‖Aℓ ‖ = ∑ aiϵi √∑ a2i √∑ ϵ2i . It

is equal to the cosine of the angle between the two vectors, or identically be the inner product of the vectors normalized to length 1. We can also use the cross-entropy measure (equivalently the log-likelihood) to evaluate this similarity: CE(Eg,Aℓ ) = ∑ ai log(ϵi). It increases with the number of components that have a large value in the embedding of the ego-graph for the components activated in the activation rule.

We also define a realism score that depends both on the probability that two vertices are connected according to their type. This score is added to the similarity measure to form the final score used to evaluate the adequacy of a graph to represent an activation rule.

We use Monte Carlo Tree Search (MCTS) to find an egograph gt that maximizes the above mentioned measure. Each node of the tree is obtained by adding an edge to the graph of its parent node. This process stops when either (1) the diameter of the graph is greater than ℓ, or (2) the number of edges is greater than min-edges, or (3) the number of vertices is greater than min-vertices. The tree is partially explored using the classical the Upper Confidence Bound UCB1 to guide the selection of the node to be expanded [Auer et al., 2002]. The possible actions to extend a non-terminal ego-graph gt are the different edges that it is possible to add to the graph so that it remains connected: (1) those with an endpoint in Vt, the other one being a new node (v ̸∈ Vt) labeled with one label of T , or (2) the ones whose two endpoints are in Vt. Thus, there are #Vt × (#Vt +#T) possible actions. To improve the search, we cut down this set of available actions. The goal is to reduce the breadth of the tree, to avoid the generation of some isomorphic graphs, while obtaining more homogeneous values of measure score on the graphs obtained in the subtree.

3 Experiments

We evaluate DISCERN through several experiments. We first describe the datasets and the experimental setup. Then, we compare our method against several instance-level and model-level baselines. Finally, we discuss some examples of subgraphs generated by our method and the baselines. Experiments are performed on three graph classification datasets (Aids [Morris et al., 2020], BBBP [Wu et al., 2017], Mutagen [Morris et al., 2020]) depicting molecules and important properties in Chemistry or Drug Discovery (class). A 3-convolutional layer GNN (with K = 20) is trained on each dataset.

We mine 10 activation rules per layer and for each class. This experimental study aims to answer the following questions: Are the activation rules good? How does DISCERN behave against baselines? To that end we compare our method against both instance-level and model-level methods. For instance-level methods, we consider 3 SOTA methods: GNNExplainer [Ying et al., 2019], PGExplainer [Luo et al., 2020] and PGM-Explainer [Vu and Thai, 2020]. We also examine 3 model-level baselines: Random generates graphs randomly by calling the Roll-out function 250x. XGNN++ is an extension of XGNN [Yuan et al., 2020a] to our problem. We integrate both Cos and CE metrics as function optimized by XGNN. We set a budget that corresponds to 5000 calls to the GNN to do a fair comparison with DISCERN. DISCGSPAN is a sound and complete method that aims at discovering discriminant subgraphs within a collection based on GSPAN enumeration [Yan and Han, 2002] while exploiting some tight upper bounds on the WRAcc measure. The input dataset contains the set of ego-network of nodes that support the activation rule as the "positive class" and the ego-network of nodes not involved in the support of the rule as the negative class. Then, DISC-GSPAN consists in computing the top-k subgraphs that are discriminant for the positive class.

3.1 Comparison to Instance-Level Methods

We consider a ground-truth free metric to compare the methods. We opt for the Fidelity [Pope et al., 2019] which is defined as the difference of predicted probability between the predictions on the original graph and the one obtained when masking part of the graph based on the explanations: Fid. = 1N × ∑Ni=1 (f(gi)yi - f(gi \ mi)yi ), where mi is the mask, gi \ mi is the complementary mask and f(g)yi is the prediction score for class yi. Similarly, we study the prediction change by keeping important features (i.e., the mask) and removing the others as Infidelity measure does: Infid. = 1N × ∑Ni=1 (f(gi)yi - f(mi)yi ). The higher the fidelity, the lower the infidelity, the better the explainer.

Obviously, masking all the input graph would have important impact to the model prediction. Therefore, the former measures should not be studied without considering the Sparsity metric that aims to measure the fraction of graph selected as mask by the explainer: Spars. = 1N ∑Ni=1 (1 - |mi| |gi | ), where |mi| denotes the size of the mask mi and |gi| is the size of gi (the size includes the number of nodes, of edges and the attributes associated to them). Based on these measures, a better explainability method achieves higher fidelity, lower infidelity while keeping a sparsity close to 1.

Several policies to build a mask from an activation rule are possible. We opt for the simplest policy AR(node) which takes as a mask only the nodes that are covered by the activation rule and the edges adjacent to these nodes. This policy allows to assess how relevant are the activation rules. We also consider masks built thanks to DISCERN, i.e., that associates a unique interpretable graph to each activation rule. To this end, for an instance graph, we select among all the rules that are activated, the related generated graph that maximizes the trade-off between Fidelity and Infidelity. The selected subgraph is used as a mask for explanation.

Table 1(a) outlines the performance of the explainers based on the Fidelity measures. Results show that AR(node) outperforms the baselines. These results must be analysed while considering the sparsity (see Table 1(c)). AR(node) provides sparser explanation than the baselines. The quality of the explanations are also assessed with the Infidelity metrics in Table 1(b). AR(node) is outperformed by GNNExplainer and PGExplainer. This suggest that a rule taken in isolation does not allow a correct classification of a graph. It is undoubtedly necessary to consider combinations of graphs to explain a decision. Interestingly, DISCERN that builds on activation rules provides better results in term of Indfidelity than AR(node), achieving score that are similar to the SOTA methods while having better fidelity and sparsity scores than these methods in most of the cases. Finally, the generated graph brings further interpretability on activation rules without altering too much the performance of the explainer directly built from these rules. All together, these results suggest that the activation rules allow to identify relevant representation space within the GNNs.

3.2 Comparison against Model-Level Baselines

The three baselines (i.e., Random, DISC-GSPAN, and XGNN++) optimizes either Cos or CE metrics. We compare them against DISCERN. For each activation rule, we study the L2 norm between the GNN embedding of the best graph generated by each method and the activation rule Aℓ . Results are reported in Table 2. For both CE and Cos, DISCERN provides graphs that better embed within the target space than any other method.

3.3 Examples

We report in Figure 2 the best graphs for each method for two activation rules on Mutagen. These rules are highly correlated to the decision "Mutagenicity". Graphs generated by Random are not shown as they are unrealistic. For the first rule (left column), DISC-GSPAN and DISCERN identify parts of toxycophores (Bay-region, K-region) [Kazius et al., 2005]. XGNN++ provides either unrealistic (i.e., Cos) or too general graphs (i.e., only one carbon). Note that the graph generated by DISCERN for CE is not entirely realistic since a hydrogen atom cannot have two bonds. Nevertheless, duplicating this atom and binding it to another carbon (dashed node and edge)

leads to a similar representation which is realistic. For the second activation rule, both DISC-GSPAN and DISCERN(CE) depict a part of amine group (NH2). These molecules are known to be toxicophore. DISCERN(Cos) generates a Vinylidene group also known to be toxic. Graphs generated by XGNN++ are unrealistic.

4 Conclusion

We have introduced a novel method for explaining internal representations of GNNs. Given some activation rules that define internal representations having a strong impact on the classification process, DISCERN generates, with a MCTS based approach, realistic graphs that fully embed in the related sub-space identified by the rules. Experiments demonstrate that (i) the activation rules identify relevant representation spaces built by the GNN and (ii) DISCERN makes it possible to describe these activation rules with realistic graphs and then to capture insights about the internal representations built by the GNN. We believe that such method can support knowledge discovery from powerful GNNs and provide insights on object of study for scientists.