Higher-Order Explanations of Graph Neural Networks via Relevant Walks

Introduction

Many interesting structures found in scientific and industrial applications can be expressed as graphs. Examples are lattices in fluid modeling, molecular geometry, biological interaction networks, or social / historical networks. Graph neural networks (GNNs) have been proposed as a method to learn from observations in general graph structures and have found use in an ever growing number of applications . While GNNs make useful predictions, they typically act as black-boxes, and it has neither been directly possible (1) to extract novel insight from the learned model nor (2) to verify that the model has made the intended use of the graph structure, e.g. that it has avoided Clever Hans phenomena .

Explainable AI (XAI) is an emerging research area that aims to extract interpretable insights from trained ML models . So far, research has focused, for example, on full black-box models , or deep neural networks , where in both cases, the prediction can be attributed to the input features. For a GNN, however, the graph being received as input is deeply entangled with the model itself, hence requiring a more sophisticated approach.

In this paper, we propose a theoretically founded XAI method for explaining GNN predictions. The conceptual starting point of our method is the observation that the function implemented by the GNN is locally polynomial with the input graph. This function can therefore be analyzed using a higher-order Taylor expansion to arrive at an attribution of the GNN prediction on collections of edges, e.g. walks into the input graph. —Such an attribution scheme goes beyond existing XAI techniques for GNNs that are limited to identifying individual nodes or edges.

Furthermore, we find that the higher-order expansion can be expressed as a nesting of multiple first-order expansions, starting at the top layer of the GNN and moving towards the input layer. Specifically, we start with a node attribution task in the top layer and then grow these nodes into walks by recursively pursuing the expansion process w.r.t. quantities in the layers below. Practically, we can insert at every step any standard first-order explanation technique, in particular, the well-adopted Layer-wise Relevance Propagation (LRP) . The resulting procedure that we propose and that we denote by GNN-LRP is shown in Figure 1.

GNN-LRP applies directly to a broad range of GNN architectures, without need to learn a surrogate function, nor to run any optimization procedure. We demonstrate GNN-LRP on a variety of GNN models from diverse application fields: (1) a sentiment prediction model receiving sentence parse trees as input, (2) a state-of-the-art GNN for quantum mechanically accurate prediction of electronic properties from molecular graphs, and (3) a widely adopted image classifier that we view as a GNN operating on pixel lattices.—For each GNN model, our explanation method produces detailed and reliable explanations of the decision strategy from which novel application insights can be obtained.

We focus here on the related work that most directly connects to our novel GNN explanation approach, in particular, (1) explanation techniques based on higher-order analysis, and (2) explanation techniques that are specialized for GNNs. For a more comprehensive set of related works, we refer the reader to the review papers for XAI and for GNNs.

Second-order methods (e.g. based on the model’s Hessian) have been proposed to attribute predictions to pairs of input features . Another work incorporates an explicit sum-of-interactions structure into the model, in order to obtain second-order or higher-order explanations. Another approach detects higher-order feature interaction as an iterative algorithm which inspects neural network weights at the different layers. In the context of NLP, a special joint convolution-LSTM model was designed to extract n-ary relations between sentences .

Our work proposes instead to use the framework of Taylor expansions to arrive in a principled manner to the higher-order explanations, and it identifies GNNs as an important use case for such explanations.

1.2 Explaining Graph Neural Networks

The work extends explanation techniques such as Grad-CAM or Excitation Backprop to the GNN model, and arrives at an attribution on nodes of the graph. In an NLP context, graph convolutional networks (GCNs) have been explained in terms of nodes and edges in the input graph using the LRP explanation method . The ‘GNNExplainer’ , extracts the subgraph that maximizes the mutual information to the prediction for the original graph, and the identified subgraph gives the explanation. Further recently proposed methods that map the GNN prediction to graph substructures include XGNN , Trap2 and GraphMask .

Our GNN-LRP method differs from these works by finding a scoring for sequences of edges (i.e. walks in the graph) instead of individual nodes or edges. This considerably enhances the informativeness of the produced explanations.

Towards Explaining GNNs

Graph neural networks (GNNs) are special types of neural networks that receive a graph as input. In practice, graphs can take a variety of forms, e.g. directed, undirected, labeled, unlabeled, spatial, time-evolving, etc. To handle the high heterogeneity of graph structures, many variants of GNNs have been developed (e.g. ). One commonality of most GNNs, however, is that the input graph is not located at the first layer, but occurs instead at multiple layers, by defining the connectivity of the network itself.

where $\bm{\Lambda}$ is the input graph given as a matrix of size $n\times n$, e.g. the adjacency matrix to which we add self-connections. We denote by $\bm{Z}_{t,K}$ the row of $\bm{Z}_{t}$ associated to node $K$, and $\mathcal{C}_{t}$ is a ‘combine’ function, typically a one-layer or multi-layer neural network, that produces the new representation for each node in the graph.

The whole input-output relation implemented by the GNN can then be expressed as a function

Consider first a ‘classical’ approach to explanation where we attribute the output of the neural network to variables in the first layer. In the case of the GNN, the first layer is given by the initial state $\bm{H}_{0}$.

Let us now view the GNN as a function of the initial state, i.e. $f(\bm{H}_{0})$. We will also denote by $\bm{H}_{0,I}$ the row of $\bm{H}_{0}$ associated to node $I$. A Taylor expansion of the function $f$ at some reference point $\widetilde{\bm{H}}_{0}$ gives:

where ‘$\dots$’ represents the zero-, second- and higher-order terms that have not been expanded, and where the sum represents the first-order terms. Because the sum runs over all nodes $I$ in the input graph, Eq. (4) readily provides an attribution of the GNN output to these nodes.

It is arguable, however, whether this attribution can truly be interpreted as identifying node contributions. Indeed, the attribution may only reflect the importance of a node in the first layer, and not in the higher layers. Furthermore, an attribution of the prediction on nodes may not be sufficient for the application needs. For example, it does not tell us whether a node is important by itself, or if it is important because of its connections to other nodes or some more complex structure in the graph.

These limitations can be attributed to the fact that we have performed the decomposition w.r.t. the initial state $\bm{H}_{0}$ instead of the ‘true’ input $\bm{\Lambda}$.

2 Higher-Order Explanation

Consider now the true input $\bm{\Lambda}$ of the GNN. Since it occurs at multiple layers and because layers are generally composed in a multiplicative manner (cf. Eqs. (1) and (2)), a first-order analysis of the GNN function $f(\bm{\Lambda})$ would not be suitable to identify the multiplicative interactions. These interactions can however be identified by applying a higher-order Taylor expansion.

In the following, we will use the additional notation $\lambda_{\mathcal{E}}$ to denote the element of the matrix $\bm{\Lambda}$ associated to a particular edge $\mathcal{E}$ of the graph. Assuming that $f(\bm{\Lambda})$ is smooth on the relevant input domain, we can compute at some reference point $\widetilde{\bm{\Lambda}}$, a $T$-order Taylor expansion:

where we define $\alpha_{\mathcal{B}}!\vcentcolon=\prod_{\mathcal{E}}\alpha_{\mathcal{B},\mathcal{E}}!$ with $\alpha_{\mathcal{B},\mathcal{E}}$ denoting the number of occurrences of edge $\mathcal{E}$ in the bag $\mathcal{B}$. The sum runs over all bags $\mathcal{B}$ of $T$ edges. Hence, the terms of the sum capture the joint effect of multiple edges on the GNN output. The last line ‘$+\dots$’ represents the non-expanded terms of order lower or higher than $T$.

Note that with this formulation, one still faces the difficult task of specifying a meaningful reference point $\widetilde{\bm{\Lambda}}$ at which to perform the expansion and for which the Taylor expansion approximates the function well. In the following, we will leverage certain properties of the GNN model, to arrive at a simpler form of the Taylor expansion where the GNN output fully decomposes on bags of $T$ edges.

Let $f(\bm{\Lambda})$ have the structure of Eqs. (1)–(3), with $\mathcal{C}_{t}$ and $g$ piecewise linear and positively homogeneous with their respective inputs. If we perform a Taylor expansion of $f(\bm{\Lambda})$ as in (5) at the reference point $\widetilde{\bm{\Lambda}}=s\bm{\Lambda}$ for an $s>0$, then all terms of the expansion which are of higher or lower order than the network depth $T$ vanish in the limit of $s\to 0$, and we arrive at a decomposition $f(\bm{\Lambda})=\sum_{\mathcal{B}}R_{\mathcal{B}}$ with

The proof of this proposition can be found in Appendix A in the Supplement. This attribution technique can also be seen as a higher-order generalization of ’Gradient $\times$ Input’ and ’Hessian $\times$ Product’ .

Explaining GNNs in Practice

The higher-order Taylor expansion presented above is simple and mathematically founded. However, systematically extracting higher-order derivatives of a neural network is difficult and does not scale to complex models.

To address this first limitation, we introduce the concept of a walk $\mathcal{W}$, which we define to be an ordered sequence of edges which connect nodes in consecutive layers of the GNN. The relation between bag-of-edges and walks is illustrated for a simple graph in Fig. 2.

Because each walk maps to a particular bag-of-edges, a walk-based explanation inherits all information contained in the bag-of-edges explanation. In particular, it is always possible to recover the bag-of-edges explanation from a walk-based explanation. However, using walks brings two further advantages: First, a walk-based explanation gives more information on way the multiple layers of the GNN have been used to arrive at the prediction. For example, as illustrated in Fig. 2, it can reveal whether message passing between two nodes has occurred in the first or in the last layers of the GNN. Second, the fact that the walks more directly connect to the structure of the GNN confers important practical benefits for computing the explanations. In the following, we will contribute two algorithms for explanation, where the relevant walks can be easily extracted using simple backward passes in the GNN.

To simplify the presentation of these algorithms, we introduce the new variable $\bm{\Lambda}^{\star}\leftarrow(\bm{\Lambda},\dots,\bm{\Lambda})$ which distinguishes between edges occurring at different layers of the GNN. We then express the GNN output as a function of this expanded input, i.e. $f(\bm{\Lambda}^{\star})$. We also adopt a node-based notation, where walks are given by the sequence of nodes they traverse from the first layer to the top layer, e.g. $\mathcal{W}=(\dots,J,K,L,\dots)$. The letters $J,K,L$ denote nodes in consecutive layers, and ‘$\dots$’ acts as a placeholder for the leading and trailing nodes of the walk. We further denote by $\lambda^{\star}_{JK}$ the element of $\bm{\Lambda}^{\star}$ representing the connection between node $J$ and node $K$.

Our first method, GNN-GI is based on the mathematical insight that Eq. (6) can be rewritten in a way that decomposes into walks. Additionally, the $T$-order derivative reduces to simple first-order derivatives defined locally in the GNN, and that are easy to compute using backward passes.

For the considered function $f(\bm{\Lambda}^{\star})$ the higher-order terms in Eq. (6) can be equivalently computed as a sequence of differentations and multiplications by the terms of $\bm{\Lambda}^{\star}$ forming each walk $\mathcal{W}=(\dots,J,K,L,\dots)$:

and then applying the pooling operation $R_{\mathcal{B}}=\sum_{\mathcal{W}\in\mathcal{B}}R_{\mathcal{W}}$.

A proof is given in Appendix B of the Supplement. Practically, GNN-GI operates as follows: Denote by $K,L,M$ the last three nodes of the walk $\mathcal{W}$, the algorithm starts by attributing on $\lambda^{\star}_{LM}$:

where $\bm{H}_{T,M}$ is the top-layer representation for node $M$. We observe that $R_{LM}$ is a function of $\bm{H}_{T-1,L}$, which itself depends on $\lambda^{\star}_{KL}$. Hence, the algorithm continues by taking $R_{LM}$ and attributing it on $\lambda^{\star}_{KL}$:

To avoid writing all indices along the walk, we use the notation $R_{KL\dots}$ in place of $R_{KLM}$, and then proceed further to compute $R_{JKL\dots}$. We continue along the walk $\mathcal{W}$ until we reach the first layer where the final score $R_{\mathcal{W}}$ is obtained. The procedure can be repeated for all walks in the graph to arrive at a complete explanation.—We call this algorithm GNN-GI, because it can interpreted as a nested Gradient$\,\times\,$Input (GI) attribution, and consequently brings GI to GNNs. We will use GNN-GI as a baseline method in Section 4.

GNN-GI has however several limitations in terms of explanation quality: When the network is not positive homogeneous (e.g. because its neurons have non-zero biases), the conservation property $\sum_{\mathcal{B}}R_{\mathcal{B}}=f(\bm{\Lambda})$ is no longer satisfied. A significant portion of the prediction might consequently fail to be attributed to the input variables. Furthermore, in deep models, the gradient on which the GI method relies is affected by a shattering effect which makes it noisy and less reliable. More sophisticated techniques are therefore needed.

2 Better Explanations with GNN-LRP

To overcome the limitations of our simple GNN-GI baseline, we will leverage the robustness and broader applicability of an existing explanation technique, Layer-wise Relevance Propagation (LRP) , and adapt it for the purpose of explaining a GNN.

LRP is a well-adopted explanation technique that is specifically designed for deep neural networks (DNNs). LRP propagates the DNN output from the top layer to the input layer. At each layer, a propagation rule is applied. The propagation rule has hyperparameters that can be set to induce certain desirable properties of the explanation, such as robustness. Compared to GI, LRP deals better with the strong nonlinearities of the model (e.g. the shattering effect ). GI can in fact be seen as a special case of LRP where the hyperparameters for robustness are set to zero . Furthermore, when the neural network has negative biases, e.g. to build sparse representations, LRP also conserves the prediction better than GI .

Motivated by the advantageous properties of LRP, we propose GNN-LRP: an improvement of GNN-GI that substitutes in Eq. (7) the GI attribution steps by LRP attribution steps. The new nested attribution procedure is given by:

where the function LRP$(\cdot,\cdot)$ attributes the relevance given as a first argument to the connections given as a second argument. Note that LRP works at the neuron level instead of the node level. Hence, we use the bold notation in Eq. (8) to signify that the relevance arriving at a given node is a collection of relevances arriving at each neuron of the node, and that a connection between two nodes is a collection of connections between pairs of neurons from the two nodes. The nested LRP procedure is illustrated in Fig. 3.

While GNN-LRP does not correspond to a particular analytical form, the approach can still be theoretically justified using the same mathematical tool that was used to justify LRP: Deep Taylor Decomposition (DTD) . DTD views LRP as performing a multitude of simple Taylor expansions in each layer of the deep network—one per neuron. DTD relies on an inductive principle that we can formulate in the context of GNNs in three steps. Denote by $R_{kL\dots}$ the relevance arriving in neuron $k$, and let $h_{k}$ be the corresponding neuron activation.

Assume that we can write $R_{kL\dots}=h_{k}c_{kL\dots}$ where $c_{kL\dots}$ is a locally approximately constant term.

Define the map $(\bm{\lambda}^{\star}_{Jk})_{J}\mapsto h_{k}c_{kL\dots}$, where $c_{kL\dots}$ is treated as constant, and apply LRP to produce the relevance scores $R_{jkL\dots}$.

Apply the pooling $R_{jKL\dots}=\sum_{k\in K}R_{jkL\dots}$ and verify that the result can be written as $h_{j}c_{jKL\dots}$ with $c_{jKL\dots}$ locally approximately constant.

If this induction holds, this justifies the application of LRP through the whole GNN from the top-layer to the first layer. Appendix C of the Supplement gives a concrete application of these induction steps for the GCN model. Practical GNN-LRP propagation rules for three popular GNN architectures are provided in Table I.

Our GNN-LRP method is applicable to a broad range of existing GNN models, in particular, the original GNN model , GCN , GraphSAGE with mean aggregation , Neural FP , GIN , any spectral filtering method such as the Spectral Network or ChebNet . GNN-LRP is also applicable to other recent GNN architectures such as the SchNet used for predicting molecular properties, and where the graph is a representation of the distance between atoms. GNN-LRP is also applicable to convolutional neural networks for computer vision such as VGG-16 , which can been seen as a particular GNN receiving as input a pixel lattice. Because GNN-LRP is tightly embedded in the more general LRP/DTD framework, it can be extended to more advanced architectures such as joint CNN-GNN models for spatio-temporal graphs . Furthermore, GNN-LRP allows in principle to use different edges and nodes at different layers, which can be useful to handle graph pooling structures, such as those described in .

While equations in Table I fully specify the GNN-LRP procedure, the latter can be more conveniently and concisely implemented using a ‘forward-rewrite’ strategy originally proposed for standard LRP (cf. ). In the following, we adapt this strategy to GNN-LRP.

Our demonstration focuses on the GCN case (Eq. (9)), but the approach can be extended to other GNN models. We first observe that by rewriting relevance scores as a product of the corresponding activation and some factor, i.e. $R_{jKL\dots}=h_{j}c_{jKL\dots}$ and $R_{kL\dots}=h_{k}c_{kL\dots}$, Eq. (9) can be equivalently formulated as:

with $p_{k}=\sum_{J}\sum_{j\in J}\lambda_{JK}h_{j}w_{jk}^{\wedge}$. This formulation can be further transformed to let appear a structure similar (but not equivalent) to gradient propagation:

Specifically, compared to the standard gradient propagation equation given by $\delta_{j}=\sum_{K}\sum_{k\in K}(\partial h_{k}/\partial h_{j})\delta_{k}$, our LRP-equivalent equation differs by (i) computing the derivative of $p_{k}$ instead of $h_{k}$, (ii) multiplying by an extra factor $h_{k}/p_{k}$, and (iii) not summing over nodes $K$.

Having connected GNN-LRP to gradient propagation, we now rewrite the forward pass of the GNN in a way that its output remains the same, but where the output of the gradient computation—assumed to be computed by automatic differentiation—matches Eq. (13). Such functionality can be achieved by ‘detaching’ certain parts of the forward computation from the differentiation graph. Specifically, we redefine the combine step of Eq. (9) as:

where $\odot$ and $\oslash$ denote the element-wise multiplication and division respectively, where $\bm{M}_{K}$ is a mask array that is one for neurons associated to node $K$ and zero elsewhere, and where $[\cdot]_{\text{cst.}}$ indicates portions of the computation that have been detached.

Furthermore, once the forward pass is rewritten at each layer, with masks chosen in a way that it selects for some walk $\mathcal{W}$ of interest, we can compute the relevance score for $\mathcal{W}$ as

where the automatic differentiation mechanism is now fully repurposed to perform the sequence of LRP computations. The procedure must then be repeated for every walk in the graph in order to produce a full explanation.

Note that this procedure is flexible and can support many variations. For example, if we wish to ignore the node at which the walk passes at a certain layer of the GNN, the mask at that layer can be simply removed. In effect, removing this mask is equivalent to summing the relevance score of walks passing through all nodes at that layer.

Also, because computing a full explanation requires as many forward/backward steps as there are walks in the input graph, various strategies can be considered to speed up computations: For example, we can adopt a multi-resolution approach where relevant walks are first defined at a coarse level between super-nodes (masks $\bm{M}$ are then set to match these super-nodes), and the most relevant ‘super-walks’ are then expanded into walks between actual nodes. Alternately, the GNN-LRP computation can be broken down layer-wise, and walk computations can be stopped early if the relevance score $R_{JKL\dots}$ is below a certain threshold. Finally, GNN-LRP can also be made faster when the input graphs have a particular structure. In particular, for the experiments of Section 5.3, we will leverage the local connectivity of the VGG-16 network to compute many walks in parallel, which dramatically speeds up computations. Details of this parallel walk computation approach are presented in Appendix D of the Supplement.

Testing and Validating GNN-LRP

To test the proposed GNN-LRP method, we train various types of GNNs on several graph prediction tasks. We first consider a two-class synthetic problem where the first class consists of Barabási-Albert graphs of growth parameter $1$ (BA-1), and where the second class has a slightly higher growth model and new nodes attached preferably to low-degree nodes. Examples of graphs from the two classes are given in Fig. 4 (left). Details on this synthetic dataset are given in Appendix E in the Supplement.

We consider first a graph isomorphism network (GIN) that we train on this task. Our GIN has two interaction layers. In each interaction layer, the combine function consists of a two-layer network with $32$ neurons per node at each layer. The initial state $\bm{H}_{0}$ is an all-ones matrix of size $n\times 1$, i.e. nodes do not have intrinsic information. The GIN receives as input the connectivity matrix $\bm{\Lambda}=\widetilde{\bm{A}}/2$ where $\widetilde{\bm{A}}$ is the adjacency matrix augmented with self-connections. The GIN is trained on this task until convergence, where it reaches an accuracy above $95\%$. After training, we take some exemplary input graph from the class BA-1, predict it with our GIN, and apply GNN-LRP on the prediction. We use the LRP parameter $\gamma=2$ and $\gamma=1$ in the first and second interaction layers respectively. The resulting explanation is shown in Fig. 4 (right).

The explanation produced by GNN-LRP reveals that walks that traverse or stay in the high-degree node are the principal contributors to the GIN prediction. On the other hand leaf nodes or sequences of low-degree nodes are found to be either irrelevant or to be in slight contradiction with prediction.

In the following, we compare GNN-LRP to a collection of other GNN explanation methods:

Pope et al. : The method views the GNN as a function of the initial state $\bm{H}_{0}$, and performs an attribution of the GNN output on nodes as represented in $\bm{H}_{0}$. In principle, the proposed framework lets the user choose the technique to perform attribution on $\bm{H}_{0}$. In our benchmark, we use the techniques GI and LRP.

GNN-GI: This is the simple baseline we have contributed in Section 3.1. This baseline can also be seen as a special case of GNN-LRP with $\gamma=0$.

GNNExplainer : The method runs an optimization problem that finds a selection of edges that maximize the model output. The procedure can be viewed as finding a mask $\bm{M}=\sigma(\bm{R})$ where $\sigma$ denotes the logistic sigmoid function, that maximize the prediction $f(\bm{M}\odot\bm{\Lambda})$. The explanation is then given by $\bm{R}$.

Explanations produced by each method are shown in Fig. 5.

The method by Pope et al. highlights nodes that are relevant for the prediction. However, it is difficult to determine from the explanation whether the highlighted nodes are relevant by themselves or if they are relevant in relation to their neighbors. The GNN-GI baseline we have contributed, and our more advanced method GNN-LRP, provide a much higher level of granularity: They distinguish in particular between what has to be attributed to the node itself and what has to be attributed to collections of multiple connected nodes. The GNNExplainer produces explanations that are in agreement with GNN-LRP but sparser and less detailed.

Even when the user aims specifically for a simple explanation, GNN-LRP remains a method of choice: Relevance scores $(R_{\mathcal{W}})_{\mathcal{W}}$ can be reassigned from walks to more descriptive structures, such as leaves, trees, cycles, etc. Relevant walks can also be reassigned to more basic elements such as nodes or edges in order to produce a level of complexity similar to Pope et al. or GNNExplainer . In fact, pooling GNN-LRP and GNN-GI explanations based on the first node of the walk results in node-based explanations that are equivalent to those obtained with Pope et al. .

Orthogonal to the level of detail of the explanation, methods based on GI tend to be less selective than those based on LRP. We observe for GNN-GI that several regions of the graph receive an excessive amount of positive or negative relevance. The noise caused by GI becomes particularly strong and problematic on larger and deeper models such as the VGG-16 network (cf. Fig. 13 in Section 5.3).

Overall, GNN-LRP is the only method in our benchmark that produces explanations that have both the desired robustness and a high level of detail.

To verify that GNN-LRP produces explanations that are systematically superior to those produced by other explanation methods, we will perform a quantitative evaluation. A common evaluation technique that was introduced in the context of image classifiers is pixel-flipping . The procedure consists of ‘flipping’ pixels by increasing or decreasing order of relevance to verify that removing relevant/irrelevant pixels causes a strong/weak variation at the output of the model. If that is the case, it can be concluded that the explanation faithfully describes the prediction at the output of the model.

We adapt the pixel-flipping method to graph data by considering nodes of the graph instead of pixels of an image as a flipping unit. We refer to this adaptation as ‘node-flipping’. In our benchmark, we will leverage the higher-order information contained in some of the explanations to determine more precisely which nodes need to be flipped to incur the desired effect on the GNN output. Specifically, based on the explanation, we wish to estimate for any subgraph $\mathcal{G}$ the contribution $R_{\mathcal{G}}$ of that subgraph to the prediction, so that the effect on the GNN output of adding/removing nodes can be expressed as differences $R_{\mathcal{G}}-R_{\mathcal{G^{\prime}}}$.

For a node-based attribution (e.g. ), the relevance to be attributed to a particular subgraph $\mathcal{G}$ is simply given as the sum of contributions of each node:

For an edge-based attribution (e.g. GNNExplainer ), the relevance of the subgraph is more finely given as a sum over the edges $\mathcal{E}$ forming the subgraph:

For higher-order attribution methods whose unit of explanation are bags of edges (computable as $R_{\mathcal{B}}=\sum_{\mathcal{W}\in\mathcal{B}}R_{\mathcal{W}}$ for GNN-LRP and GNN-GI), the estimation of the subgraph relevance is further refined by computing

where the membership relation $\mathcal{B}\in\mathcal{G}$ requires that all edges in the bag $\mathcal{B}$ are also in the subgraph $\mathcal{G}$. We note that in every case, the estimator $R_{\mathcal{G}}$ is zero when considering the empty graph, and it corresponds instead to the GNN output when considering the full graph.

We consider two node-flipping tasks. First, an activation task, where we would like to add nodes to the graph so as to activate the GNN output maximally and as quickly as possible. In the general case, finding the optimal sequence of nodes to add is combinatorially complex. However we can use instead a greedy approach, where for a given subgraph $\mathcal{G}$, the best node to add next according to the explanation is given by:

Then, we consider a pruning task, where we start with the original graph $\mathcal{G}_{0}$ and want to remove nodes from the graph in a way that the GNN output is minimally affected. In that case, the best node to remove is

Note that with this greedy strategy, higher-order techniques such as GNN-GI and GNN-LRP may have their performance underestimated, as adding one node at a time prevents from uncovering new parts of the graph composed of mutually relevant nodes. To mitigate this effect we can substitute at regular intervals of the node-flipping procedure the greedy step by a coarser step where the node is added based on its marginal score $R_{\mathcal{V}}$.

Once the sequence of nodes to flip has been built, we produce a plot that keeps track of the GNN output throughout the flipping process. The procedure can be repeated for a large number of graphs, leading to an averaged version of the same plot. The latter can be further summarized with the ‘Area Under the Flipping Curve’ (AUFC), which we define as the mean of plotted values over the flipping sequence. The node-flipping procedure and the AUFC computation are depicted in Fig. 6.

We will now use the node-flipping procedure to evaluate the different explanation methods on a broad set of architectures and tasks. On the Synthetic Data, we consider in addition to the GIN model used in the qualitative experiments, a GCN and a spectral network. Our GCN, has $128$ neurons per node at each layer. For the spectral network, we use $32$ neurons per node at each layer and give as input the power expansion $\bm{\Lambda}=[\widetilde{\bm{A}}^{0},\frac{1}{2}\widetilde{\bm{A}}^{1},\frac{1}{4}\widetilde{\bm{A}}^{2}]$. Both networks perform similarly to the GIN in terms of classification accuracy.

In addition, we also consider networks trained on real data: A first one is designed and trained by ourselves on a Sentiment Analysis task where the graph represents a syntactic tree with nodes carrying information about each word. Another one is the SchNet model used for molecular prediction where nodes and edges represent atom types and distances respectively. Finally, we use a pre-trained VGG-16 network for image recognition that we interpret as a graph neural network operating on a lattice of size $14\times 14$ and starting at convolutional block 3. In this last network, each node represents the collection of activation at a specific spatial location. Details for each network are given in Appendix F in the Supplement. Results for each network, explanation method and task are summarized in Tables II and III.

On the Synthetic Data, we observe that GNN-LRP systematically outperforms other methods, both on the activation and pruning tasks. Nearest competitors are Pope et al. (in combination with LRP), GNN-GI, and the GNNExplainer . This corroborates our qualitative analysis at the beginning of Section 4.

On the Sentiment Analysis task, GNN-LRP and GNNExplainer perform best for the activation and pruning task, followed by GNN-GI and both node attribution methods by Pope et al. . In natural language, the sentiment associated to a sentence relies on word combinations, e.g. negation. This can explain why methods which attribute interactions of words such as GNN-LRP and GNNExplainer perform better.

For the experiments on the SchNet, our method performs again above competitors. Note that in this experiment, use of GI and LRP are equivalent, because the lack of ReLU-Dense-ReLU structures forces us to use the LRP- rule, instead of the more robust LRP-$\gamma$, and application of LRP- is equivalent to GI (cf. ). The difference to other competitors (Pope et al. and GNNExplainer ) is small on the prediction of the energy $E$ but larger for the dipole-moment $\mu$, possibly because of a more complex structure of the prediction task involving longer interactions.

Finally, on the VGG-16 image recognition model, GNN-LRP performs best on both tasks. Here, the superiority of LRP vs. GI can be explained both by a better handling of neuron biases and by a higher robustness to gradient shattering, a key difficulty to account for when explaining very deep models .

Overall, we find that GNN-LRP is systematically the best method in our benchmark. With the fine-grained yet robust explanations it provides, GNN-LRP is capable of precisely and contextually identifying elements of the graph that contribute the most or the least to the prediction.

New Insights with GNN-LRP

Having validated the proposed GNN-LRP method on a diverse set of GNNs including state-of-the-art models, and having shown the multiple advantages of our method compared to previous approaches, we will now inspect the explanations produced by GNN-LRP on some of these practically relevant GNN models to demonstrate how useful insights can be extracted about the GNN model and the task it predicts.

In natural language processing (NLP) text data can be processed either as a sequence, or with its corresponding grammatical structure represented by a parse tree . The latter serves as an additional structural input for the learning algorithm, to incorporate dependencies between words. NLP tasks are therefore particularly amenable to GNNs since these models can naturally incorporate the graph structure.

In the following experiments, we will demonstrate how GNN-LRP can be used to intuitively and systematically assess the quality of a GNN model, including its overall prediction strength and also its few weaknesses. For this, we will consider a GCN composed of two interaction layers, to classify sentiments in natural language text . We train our model on the Stanford Sentiment Treebank (SST) Note that this example serves as a mere demonstration for the versatility of our explanation approach and is by no means intended to reflect or compete with state-of-the-art NLP systems.. For details on the experimental setup we refer the reader to Appendix F.2 in the Supplement.

In Fig. 7 (top) we show an example of a GNN-LRP explanation for some exemplary input sentence containing a mixture of positive and negative sentiment. We observe that distinct combinations of words give rise to the emphasis of these sentiments. The model correctly detects word combinations such as “the best movies” to carry a positive sentiment, and “boring pictures” to contribute negatively.

GNN-LRP can also be used to assess the GNN prediction strategy relative to other (simpler) models, such as Bag-of-Words (BoW). The BoW model can be seen as a GNN model with zero interaction layers, hence our explanation technique applies to that model as well. Fig. 7 (bottom) shows the explanation of the BoW prediction for the same sentence as for the GNN. Interestingly, several words are now attributed a sentiment different from the one obtained with the GNN. For example, “like” becomes positive, which however appears in contradiction with the preceding words “didn’t”. Hence, GNN-LRP has highlighted from a single sentence that the GNN model is able to properly capture and disambiguate the sentiment of consecutive words, whereas the BoW model is not.

In the next experiment, we consider two additional sentences from the SST corpus, where GNN-LRP contributes to uncovering or better understanding flaws of a trained GNN model. Fig. 8 A shows a data sample that contains sarcasm and that is falsely classified by the GNN to be positive. Our explanation method highlights that relevant walks are too localized to capture the interaction between words that jointly explain sarcasm. Instead, local positive interactions such as “more entertained” dominate the prediction, which leads to the incorrect prediction. In Fig. 8 B, we see a case of entity bias where the GNN model is biased towards particular entities, namely “Hugh Grant” and “Sandra Bullock”. In this example, GNN-LRP finds that the GNN model uses with no objective reason “Hugh Grant” and “Sandra Bullock” as evidence for positive and negative sentiment, respectively. In NLP model biases are well studied areas and some approaches to tackle that problem have already been developed .

To identify words or combinations of words that systematically contribute to a positive or negative sentiment—and potentially discover further cases of entity bias,—we apply GNN-LRP on the whole dataset. This lets us find the combination of words (given by a walk $\mathcal{W}$) that are on average the most positive/negative (according to their score $R_{\mathcal{W}}$). Fig. 9 shows top-3 walks of both types (positive and negative) and containing one to three unique words.

We see that the walks which are most relevant for the task contain positive adjectives and adverbs, such as “solidly”, “brilliant”, “wonderfully” or “entertaining”. The walks with a very negative relevance score contain negative words such as “moot”, “gimmicky” or “vulgar”, but also subsequences like “charlie sorry”, “dead weight” or “no more.” which clearly transport a negative emotion. Here again, GNN-LRP detects an entity bias by the word “lewis”, which the GNN model considers to be positively contributing although this word is objectively neutral. Note that this time, this entity bias was discovered directly, without having to visualize a large number of explanations.

Overall, applying the proposed GNN-LRP explanation method to the GNN model for sentiment classification has highlighted that GNN predictions are based on detecting meaningful sentence sub-structures, rather than single words as in the BoW model. Furthermore, GNN-LRP was able to find the reasons for incorrect predictions, or to shed light on potential model biases. The latter could be identified manually by visual inspection of many explanations, or systematically by averaging the GNN-LRP results on a whole corpus.

2 Quantum Chemistry

In the field of machine learning for quantum chemistry , GNNs have been exhibiting state of the art performance for predicting molecular properties . Such networks incorporate a graph structure of molecules either by the covalent bonds or the proximity of atoms.

In this section we will test the ability of GNN-LRP to extract meaningful domain knowledge from these state-of-the-art GNNs. We will consider for this the SchNet, a GNN for the prediction of molecular properties , and we set the number of interaction blocks in this GNN to three. We train the model on the atomization energies and the dipole moments for 110,000 randomly selected molecules in the QM9 dataset . For more details on the model parameters and the network architecture, we refer to Appendix F.3 in the Supplement. On a test set of 13,885 molecules, the atomization energy and dipole moment are predicted well with a mean absolute error (MAE) of 0.015 eV and 0.039 Debye, respectively.

Our first objective is to get an insight into what structures in the molecule contribute positively or negatively to the molecule’s energy. While it is common to look at the atomization energy (describing the energy difference to dissociated atoms), we consider here for the purpose of explanation the centered negative atomization energy, and we define this quantity to be the actual ‘energy’. With this definition, molecules have high energy when they are hard to break and typically formed of strong bonds, and conversely, molecules have low energy when they are easy to break and unstable.

We consider for illustration the case of the paracetamol (acetaminophen) molecule, and feed this molecule to SchNet. Once the SchNet model has predicted its energy, we apply the GNN-LRP analysis in order to produce an explanation of the prediction. The resulting explanation is shown in Fig. 10 (left). We observe that the explanation is dominated by self-walks (i.e. staying in a single atom) or one-edge walks (traversing a single edge of the graph, in most cases, a bond). Bonds associated to the aromatic ring and bonds of higher order contribute strongly to the predicted energy, whereas regions involving single bonds contribute negatively. To verify whether this observation generalizes to other molecules, we perform the GNN-LRP analysis on a set of 1000 molecules randomly drawn from the QM9 dataset and show in Fig. 10 (right) the average bond contribution for each bond type. We observe an increasing energy contribution with ascending bond order. This coincides with chemical intuition that bonds of higher order are more stable and, thus, require more energy to break.—Note that the SchNet does not take bond types as an input, but as highlighted by GNN-LRP, it has clearly inferred these chemical features from the data.

We now turn to another quantum chemical property, the dipole moment, and its prediction by SchNet (cf. ). The quantity produced at the output of the model has the form $\|\bm{\mu}(\bm{\Lambda})\|$. The nonlinearity of the norm introduces higher-order terms in the GNN function and this prevents a direct application of GNN-LRP. Instead, we consider for explanation the dot product $\langle\bm{\mu}(\bm{\Lambda}),\bm{\mu}[\bm{\Lambda}^{\star}]/\|\bm{\mu}[\bm{\Lambda}^{\star}]\|\rangle$, where the left hand side functionally depends on the GNN input $\bm{\Lambda}$, and where the right hand side is the direction of the predicted dipole moment for the actual molecule denoted by $\bm{\Lambda}^{\star}$. With this modification, the top layer becomes linear, and GNN-LRP can proceed as for the energy prediction case.

Fig. 11 (top) shows the GNN-LRP explanation of the predicted dipole moment for the same molecule as in the previous experiment. Here, we observe that the contributions to the dipole moment found by GNN-LRP form a gradient from one side to the other side of the molecule. The orientation corresponds to the positive and negative pole of the molecule. To verify whether this insight generalizes to other molecules, we consider a set of 1000 molecules and we normalize each molecule to a span of 1 along its dipole direction. Subsequently, we project all walks onto their respective dipole to obtain a one-dimensional distribution of absolute relevance values for all molecules. Note that the atom density of molecules, in general, is not homogeneous, and thus, in some regions more walks may occur while other regions do not exhibit as many walks. Hence, for each molecule the distribution of absolute relevance is normalized w.r.t. its atom density. The result of this aggregated analysis is shown in Fig. 11 (bottom).

This quantitative result confirms the alignment of GNN-LRP contributions with the positive and negative poles of the molecule, as it was found qualitatively on the paracetamol molecule. This result is in accordance with chemical intuition regarding the dependence of the dipole on the span of the molecule.

Because the walk-based explanations produced by GNN-LRP are very detailed, some of the more intricate details of the explanation cannot always be visualized on a single molecule. Hence, we perform a further experiment where the GNN-LRP explanation is spread over multiple visuals, each of them showing relevant walks covering a specific number of edges. With this expanded visualization, we seek in particular to better distinguish between local atom-wise contribution and more global effects. Figure 12 shows this expanded analysis of the dipole moment prediction for the paracetamol molecule.

From this visualization, we gain further insights into the strategy used by the SchNet model for predicting. In our expanded explanation, one-edge walks clearly indicate the electrostatic poles of the molecule, while giving a hint on local dipoles. Self-walks (i.e. 0-edge walks) incorporate elements that are inherent to the atom types, in particular, their electronegativity. Two-edge walks provide rather complex and spatially less resolved contributions. Finally, three-edge walks, that are also the most global descriptors, again provide interesting spatial contributions, and appear to dampen the one-edge walks contributions based on the more complex structures they are able to capture.

Overall, GNN-LRP has provided insights into the structure-property relationship of molecules that reach beyond the original prediction task. The resulting relevant walks agree with chemical characteristics of the molecule, thus, indicating that the neural network has indeed learned chemically plausible regularities.

3 Revisiting Image Classification

A convolutional neural network (CNN) can be seen as a particular graph neural network (GNN) operating on lattices of pixels. CNN predictions have so far mainly been explained using heatmaps highlighting pixels that are the most relevant for a given prediction . Heatmaps are a useful representation summary of the decision structure, but they do not reveal the more complex strategies of a network that have been used to progressively build the prediction layer after layer. We will show by viewing CNNs as graph neural networks and extracting relevant walks in the resulting pixel lattice, that our GNN-LRP method is capable of shedding light into these strategies.

For this, we consider the well-established VGG-16 network. It consists of a collection of blocks interleaved by pooling layers, where each block is composed of a sequence of convolution and ReLU layers. We use the pretrained version of the VGG-16 network without batch-normalization, which can be retrieved using the TorchVision module of PyTorch.

Because the VGG-16 neural network is deep and the number of possible walks grows exponentially with neural network depth, we marginalize explanations to only consider the position of the walk at the input and at the output of a block. This is easily achieved by removing all masks except those at the input and output of the block (cf. Section 3.2.1). We then compute one explanation for block 3, 4, and 5. Also, to cope with the large spatial lattices in each block, we make use of the multi-mask strategy outlined in Appendix D of the Supplement. Specifically, because each block of the VGG-16 network has receptive fields of size $7$, we can process multiple walks at the same time by choosing the mask to be a grid with stride $7$. This allows us to collect all relevant walks at the given block in the order of $49$ backward passes.

We consider two exemplary imagesImages are from https://www.piqsels.com/en/public-domain-photo-fjjsr and https://www.piqsels.com/en/public-domain-photo-fiffy, rescaled and cropped to the relevant region to produce images of size $224\times 224$ which are the standard input size for VGG-16. that the VGG-16 network respectively predicts as ‘teapot’ and ‘dumbbell’. We set the LRP parameter to $\gamma=0.5$ in block $3$, halving the parameter value in each subsequent block, and choosing $\gamma=0$ in the top-level classifier. Fig. 13 (left) shows the result of the analysis for these two images at various blocks of the VGG-16 network.

For the first image, Block 3 detects local edges in the teapot, then, in Block 4, the walks converge to center points of specific parts of the teapot (e.g. the handle, the spout and the knob), and finally the walks converge in Block 5 to the center of the teapot, which can be interpreted as composing the different parts of the teapot. For this exemplary image, we further observe in Fig. 13 (right) the advantageous properties of GNN-LRP compared to more basic explanation methods. The GNN-GI baseline also produces a vector field, however, the latter is significantly more noisy than the one produced by GNN-LRP. The method by Pope et al. robustly highlights relevant nodes at the input of the given block, however, it does not reveal where these features are being transported for use in the subsequent block.

For the second image, we investigate a known ‘Clever Hans’ strategy where the network classifies images as ‘dumbbell’ by detecting both the dumbbell and the arm that holds it . Using GNN-LRP we observe that Blocks 3 and 4 detect the arm and the dumbbell separately, and then, Block 5 composes them into a single ‘dumbbell-arm’ concept, as shown by the walks for both objects converging to some center point near the wrist. Clearly these insights could not have been obtained from a standard pixel-wise heatmap explanation.

Overall, our GNN-LRP method can be used to comprehensively inspect the prediction of an image classifier beyond what would be possible with a standard pixel-wise heatmap explanation. This deeper explanation capability allows us to better understand the detailed structure of image classifications, and also to shed more light into anecdotal ‘Clever Hans’ effects observed in the context of state-of-the-art image classifiers.

Conclusion

Graph neural networks are a highly promising approach for predicting graphs, with a strong demand from the practical side. For these models to be broadly adopted, it is however important that their predictions are made explainable to the user.—Because the input of a GNN is tightly entangled with the model itself, the explanation problem is particularly difficult, and, methods for explaining GNNs have so far been limited.

In this paper we have proposed a novel theoretically principled approach to produce these explanations, based higher-order Taylor expansions. From this conceptual starting point, we have then contributed two practical algorithms: GNN-GI which we propose as a simple baseline, and GNN-LRP which is more robust and scales to highly non-linear models. GNN-LRP produces detailed explanations that subsume the complex nested interaction between the GNN model and the input graph. It also significantly outperforms other explanation methods in our quantitative benchmark.—In addition to the high quality of the explanations it produces, GNN-LRP is also broadly applicable (covering the GCN, the GIN, and spectral filtering approaches), and it can handle virtually any type of input graph, whether it is a parse tree, a spatial graph, a pixel lattice, etc.

This broad applicability is demonstrated in our extensive application showcase, including sentiment analysis, quantum chemistry and image classification. In each scenario, GNN-LRP could highlight the diverse strategies employed by the GNN models, and unmask some undesired ‘Clever Hans’ strategies. In our quantum-chemical application showcase, we could additionally extract interesting problem-relevant insights. Future work will apply the proposed methodology to analyze properties of materials for practically highly relevant tasks, e.g. in catalysis.

Acknowledgments

This work was funded by the German Ministry for Education and Research as BIFOLD – Berlin Institute for the Foundations of Learning and Data (ref. 01IS18025A and ref. 01IS18037A), and the German Research Foundation (DFG) as Math+: Berlin Mathematics Research Center (EXC 2046/1, project-ID: 390685689). This work was partly supported by the Institute of Information & Communications Technology Planning & Evaluation (IITP) grants funded by the Korea Government (No. 2019-0-00079, Artificial Intelligence Graduate School Program, Korea University). Furthermore we would like to thank Jacob Kauffmann, Lukas Ruff and Marina Höhne for the highly helpful and illuminating discussions on the topic and also Niklas W. A. Gebauer for helping with the molecule visualization. We would like to thank Jasmijn Bastings for very helpful comments on the manuscript.

References