arXiv CSopen access

Relevant Walk Search for Explaining Graph Neural Networks

Relevant Walk Search for Explaining Graph Neural Networks

Ping Xiong 1 2 Thomas Schnake 1 2 Michael Gastegger 1 Grégoire Montavon 3 2 Klaus-Robert Müller 1 2 4 5 6 Shinichi Nakajima 1 2 7

arXiv:2605.23673v1 [cs.LG] 22 May 2026

Abstract

1. Introduction Graph Neural Networks (GNNs) are powerful machine learning tools to solve tasks on graph datasets, such as social networks (Yanardag & Vishwanathan, 2015) and molecules (Kazius et al., 2005; Schütt et al., 2018). Various GNN models have been proposed (Wu et al., 2021a), while the rationale of prediction—for example, which node features or which parts of the input graph are (jointly) contributing to the prediction—cannot be directly extracted from the model. The GNN therefore acts as a black box and its prediction is hard to comprehend without further investigation. To address this challenge, many explainability methods emerged in recent years (Schnake et al., 2022; Ying et al., 2019), which can be generally categorized into model-level and instance-level methods (Yuan et al., 2020b): modellevel methods generate representative graphs for different predictions, while instance-level methods focus on single predictions and find relevant features in the corresponding input graphs.

Graph Neural Networks (GNNs) have become important machine learning tools for graph analysis, and its explainability is crucial for safety, fairness, and robustness. Layer-wise relevance propagation for GNNs (GNN-LRP) evaluates the relevance of walks to reveal important information flows in the network, and provides higherorder explanations, which have been shown to be superior to the lower-order, i.e., node-/edgelevel, explanations. However, identifying relevant walks by GNN-LRP requires exponential computational complexity with respect to the network depth, which we will remedy in this paper. Specifically, we propose polynomial-time algorithms for finding top-K relevant walks, which drastically reduces the computation and thus increases the applicability of GNN-LRP to large-scale problems. Our proposed algorithms are based on the maxproduct algorithm—a common tool for finding the maximum likelihood configurations in probabilistic graphical models—and can find the most relevant walks exactly at the neuron level and approximately at the node level. Our experiments demonstrate the performance of our algorithms at scale and their utility across application domains, i.e., on epidemiology, molecular, and natural language benchmarks. We provide our codes under github.com/xiong-ping/rel walk gnnlrp.

This paper focuses on the instance-level explanation, for which most of the existing methods, e.g., GNNExplainer (Ying et al., 2019), PGExplainer (Luo et al., 2020) and methods in Pope et al. (2019), only consider lower-order features, i.e., nodes and edges, ignoring higher-order interactions. Recently, Schnake et al. (2022) proposed layer-wise relevance propagation for GNNs (GNN-LRP) as a decomposition of the model into contributions of input features that jointly give rise to the prediction. In particular, this leads us to a higher-order explanation method that measures the relevance of walks on the input graph. GNN-LRP can be used in two ways: (1) identifying relevant walks that reveal important information flows in the network, and (2) aggregating walk relevances within subgraphs or substructures in the input graph to attribute them. In either way, GNN-LRP captures interactions between features across the network layers, and has shown its superior performance to the lower-order methods.

1

Technische Universität Berlin (TU Berlin) 2 BIFOLD – Berlin Institute for the Foundations of Learning and Data 3 Freie Universität Berlin (FU Berlin) 4 Department of Artificial Intelligence, Korea University, Seoul 136-713, Korea 5 Max Planck Institut für Informatik, 66123 Saarbrücken, Germany 6 Google Research, Brain team, Berlin 7 RIKEN Center for AIP, Japan. Correspondence to: Shinichi Nakajima <[email protected]>.

Despite its ability to enable higher-order explanation, the GNN-LRP algorithm faces computational issues: both its relevant walk identification and the subgraph attribution require exponentially many walks to be evaluated. Therefore naive implementations can cope only with small-scale prob-

Proceedings of the 40 th International Conference on Machine Learning, Honolulu, Hawaii, USA. PMLR 202, 2023. Copyright 2023 by the author(s).

1

Relevant Walk Search for Explaining Graph Neural Networks

Figure 1. We aim to find the most important information flows for a GNN prediction in terms of walk relevance. Naively one can apply a brute force search, where the relevances of all possible walks are evaluated and the most relevant ones are chosen. Our proposed methods are based on the max-product algorithm to find the most relevant walks by local message passing, which reduces the computational complexity drastically from exponential to linear with respect to the network depth.

product search for neuron-level walks (EMP-neu), and an approximate max-product search by averaging (AMP-ave) for node-level walks.

lems in terms of the network depth and the graph size. The latter issue, namely exponential complexity for subgraph attribution, was solved by Xiong et al. (2022). They pointed out that the relevance of a walk has the same decomposability to the joint distribution of a Markov chain process, and applied the sum-product message passing algorithm for computing the subgraph relevance, which reduces the computational cost from exponential to polynomial. They also showed that the general LRP computation for feed-forward neural networks can be seen as marginalization of walk relevances by the sum-product message passing algorithm.

The computational complexities of EMP-neu and AMP-ave are polynomial, so that we obtain an explanation method that has the same higher-order feature resolution as GNN-LRP but without exponential computational costs. In addition we provide a variety of qualitative and quantitative experiments that demonstrate the usefulness of our approach. We show as well that the accuracy of AMP-ave is high in our experiments, so that the potential approximation error is negligible throughout the domains. This leads us to a new explanation method, with only an insignificant approximation error, that is fast computable and exhibits superior higher-order feature resolution.

In this paper, we tackle the other issue: exponential complexity for relevant walk identification. First of all, we would like to propose that the decomposability argument in Xiong et al. (2022) could also invoke the applicability of the max-product message passing algorithm. This idea could allow us the usage of a popular workhorse for finding the maximum likelihood configuration of probabilistic graphical models (Viterbi, 1967; Bishop, 2006). Our proposal indeed relies on the max-product decomposability of the objective, and thus allows deriving local message passing for relevance maximization (see Fig.1). However, two difficulties stand in our way by obstructing max-product decompositions: (1) negative values that relevance factors can take, and (2) sum operations involved in the node-level walk search.1 We resolve those difficulties by finding multiple absolute relevant walks with search space splitting (Nilsson, 1998) and approximation with neuron averaging, and propose two algorithms in this paper: an exact max-

2. Background and Related Works 2.1. Graph Neural Networks Graph Neural Networks (GNNs) (Scarselli et al., 2009; Wu et al., 2021b) take a graph as an input, and make the corresponding prediction by using the topological structure of the graph. In our setting we consider the message passing neural networks (MPNNs) (Gilmer et al., 2017), which learn node embeddings in multiple interaction blocks, and each block typically consists of aggregate and combine steps:

Aggregate: Z (l) = M(l) (H (l−1) , Λ),   Combine: H (l) = C (l) Z (l) .

1

The neuron- and node-level walks (defined in Xiong et al. (2022)) will be explained in Section 2.3, and illustrated in Fig.2.

2

(1) (2)

Relevant Walk Search for Explaining Graph Neural Networks (l)

Here H (l) ∈ RM ×N is the feature (activation) matrix of the l-th layer, which consists of the N (l) -dimensional feature embeddings for all M nodes. In the aggregate step, (l−1) the (forward) message Z (l) ∈ RM ×N is computed by (l) the aggregation function M that aggregates the features H (l−1) from the last layer using a modified (e.g., normalized with self-loops) adjacency matrix Λ ∈ RM ×M . In the combine step, the (typically non-linear) combine function C (l) transforms Z (l) into the new node features H (l) for this layer.

Tage (Xie et al., 2022) is a framework for efficiently explaning GNN with multiple downstream tasks, which trains a parametric explainer in a self-supervision manner. There are also higher-order methods that consider interactions between more than two nodes. SubgraphX (Yuan et al., 2021) searches the most relevant subgraph using MonteCarlo Tree Search (MCTS) with Shapley value (Lundberg & Lee, 2017), and applied approximation methods in computing Shapley values, which is otherwise too computationintensive. GNN-LRP (Schnake et al., 2022) is an LRP-based method, which scores bag-of-edges by decomposing and backpropagating the output to the input layer. GNN-LRP considers a walk as the basic unit for attribution, which is detailed below.

A common choice for the aggregation and the combine functions in Eqs.(1) and (2), respectively, is the linear aggregation and a one-layer perceptron, as in a simple GCN (Kipf & Welling, 2017): M(l) (H (l−1) , Λ) = ΛH (l−1) , (l)

(l)

(l−1)

(l)

C (Z

) = σ(Z

(l)

W

(l)

),

(3)

2.3. Relevance of Walks

(4)

A walk is defined as an ordered sequence of nodes connected from layer to layer (Schnake et al., 2022). Assume that the whole graph G consists of M nodes. Then, a walk can be denoted by m ∈ M with M = {1, . . . , M }L+1 , meaning that the walk starts from the m0 -th node at the input layer, goes through the ml -th node at the l-th layer, and reaches the mL -th node in the last layer. We also denote a partial walk by ml:l′ for 0 ≤ l ≤ l′ ≤ L.

×N where W (l) ∈ RN is a trainable weight matrix and σ(·) is a non-linear (entry-wise) activation. After the final node features are computed, a readout function will be applied to make the final model predictions, e.g., sum over all nodes followed by a softmax function to produce graph-level classification probabilities.

The GNN-LRP rule for the MPNNs, Eqs.(1) and (2), with the aggregation and combine functions, Eqs.(3) and (4), and the ReLU activation is given as

2.2. Explaining GNNs Many explanation methods for GNNs have emerged recently. These include general explanation methods, e.g., sensitive analysis (SA), guided backpropagation (GBP), class activation mapping (CAM) and excitation backpropagation (EB) (Baldassarre & Azizpour, 2019; Pope et al., 2019), adapted to the GNN structure, and novel methods specialized for GNNs, e.g., GNNExplainer (Ying et al., 2019) and PGExplainer (Luo et al., 2020). GNNExplainer finds soft masks (for node or edge features) such that the mutual information between the predictions of the original graph and the masked graph is maximized, and uses the masks as the relevance scores. PGExplainer learns approximate discrete masks by training a parametric predictor, and masks out unimportant edges according to the learned masks. PGM-Explainer (Vu & Thai, 2020) trains an explainable probabilistic graphical model as a surrogate of the GNN, and use its explanation as a substitution. GraphMask (Schlichtkrull et al., 2021) trains a one layered perceptron network to predict whether each edge in each layer can be removed without changing the model output significantly. XGNN (Yuan et al., 2020a) and GNNInterpreter (Wang & Shen, 2022) explain a GNN on the model-level, and generates representative graphs for possible model predictions by using reinforcement learning or probabilistic generative models. GNES (Gao et al., 2021) is a general framework that can make the explanation more reasonable and stable by training GNN and optimizing its explanation simultaneously with specific regularization.

r̆ (l,ml ) = T l,ml ,ml+1 r̆ (l+1,ml+1 ) ,

(5)

(l)

where r̆ (l,ml ) ∈ RN is the propagated relevance at the ′ (l) (l+1) node ml in the l-th layer, and T l,m,m ∈ RN ×N is the propagation matrix whose entries are given as ′

↑(l+1)

l,m,m Tn,n =P ′

(l) Λm,m′ Hm,n Wn,n′

↑(l+1) (l) m′′ ,n′′ Λm′′ ,m′ Hm′′ ,n′′ Wn′′ ,n′

.

(6)

Here W ↑ is a modified weight parameter depending on the choice of LRP rules (Bach et al., 2015; Montavon et al., 2019; Samek et al., 2021; Eberle et al., 2022), e.g., W ↑ := W +γ ·max(0, W ) for the LRP-γ rule with γ ≥ 0, where the max operator applies entry-wise. Note that we mostly use subscripts to specify the entry of a matrix or vector, while superscripts for distinguishing different matrices or vectors. For general MPNNs, (1) and (2), relevance propagation rules (5) can be similarly defined with appropriate propagation matrices {T l,ml ,ml+1 } (see an exemplary study in Schnake et al. (2022)). We stress that our theory and algorithms can be applied to any GNN (possibly beyond MPNNs) as long as the propagation rule in the form of Eq.(5) is defined. Considering the unfolded GNN as a feed-forward neural 3

Relevant Walk Search for Explaining Graph Neural Networks

neuron-level walk

node-level walk

suggest two novel algorithms, namely, for neuron-level and node-level search of the most relevant walks. 3.1. Exact Neuron-level Search Unlike the sum-product decomposition, the max-product decomposition holds only when each factor is non-negative. Therefore, we first maximize the absolute relevance: Q  l,ml ,ml+1 L−1 L R̆m,n = | |rnL,m |. (9) l=0 |Tnl ,nl+1 L Thanks to the decomposability of the objective, the maximization (9) can be performed by the following max-product message passing for l = L, . . . , 0:

Figure 2. Illustration of neuron-level and node-level walks. The node-level path of the top neuron-level walk may differ from the top node-level walk, because many weakly relevant neuron-level walks may sum up to a strongly relevant node-level walk.

l−1,m

m b l, n bl = argmaxml ,nl |Tnl−1 ,nl−1 l

,ml

l−1,m ,m bl bl l−1 µ bl−1,m = |Tnl−1 ,bnl−1 |µ bl,nblm , nl−1 l

network (FFNN), Xiong et al. (2022) defined the neuronlevel walk (see Fig. 2): Q  L−1 l,ml ,ml+1 L Rm,n = rnL,m , (7) l=0 Tnl ,nl+1 L

l |µ bl,m nl ,

(10) (11)

(l)

b l,ml ∈ RN is a (backpropagating) message at the where µ L L l-th layer, and initialized as µ bL,m = |rnL,m |. (m b l, n bl ) ∈ nL L (l) {1, . . . , M }×{1, . . . , N } are also messages, and actually functions of (ml−1 , nl−1 )—we abbreviated them as m bl = m b l (ml−1 , nl−1 ) and n bl = n bl (ml−1 , nl−1 ) in Eqs.(10) and (11) to avoid from cluttering. (m b l, n bl ) together specify the most relevant backward neuron-level step for any possible next step choice for the (l−1)-th layer. The derivation of the message passing, (10) and (11), and the detailed algorithm are given in Appendix B.

and pointed out that it has the same decomposability as the joint distribution of a Markov chain process. Here n ∈ N ≡ {1, . . . , N (0) }×· · ·×{1, . . . , N (L) } specifies the trajectory (L) of relevance through neurons, and r L,mL ∈ RN denotes the neuron-level relevance at the L-th layer. Based on this observation, it was shown that the propagation rule (5) for computing the (node-level) walk relevance by GNN-LRP, i.e., Q  L−1 l,ml ,ml+1 Rm = r L,mL l=0 T Q  P L−1 l,ml ,ml+1 L = n∈N T rnL,m , (8) n ,n l l+1 l=0 L

The max-product message passing above finds the neuronlevel walk that has the highest absolute relevance in 2 O(M 2 N L) time, where N = maxl N (l) . However, the solution can be not the maximizer but the minimizer of the original walk relevance (7) if it is negative. Furthermore, we expect that only focusing on the single most relevant walk is not always informative enough for GNN explanation. To remedy both issues, we propose a procedure to find the tope absolute relevant walks, following the strategy proposed K in Nilsson (1998).

(as well as the one for the standard LRP for general FFNN with any propagation matrices T ) can be interpreted as the sum-product message passing algorithm—a common tool to compute marginal probabilities of tree-structured probabilisitic graphical models (Pearl, 1982; Bishop, 2006)—for marginalizing over the neurons within the node-level walk m. Xiong et al. (2022) applied the same argument for the subgraph relevance, proposed in Schnake et al. (2022), and drastically accelerated the exponential computation of the original GNN-LRP to a polynomial one.

1

c ,n b 1 with the highest After finding the neuron-level walk m absolute relevance, we split the rest of the search space 1 b 1 ) into L + 1 disjoint subsets {Ai }, where (M × N) \ (c m ,n A0 = {(m, n) : (m0 , n0 ) ̸= (m b 10 , n b10 )},

3. Message Passing for Relevant Walk Search

Ai = {(m, n) : (m0:i−1 , n0:i−1 ) = (m b 10:i−1 , n b10:i−1 ),

This paper aims to provide a family of efficient algorithms for finding most relevant walks; see Section 4 for applications. We reiterate from Section 1 that the same decomposability of the walk relevance as a Markov chain process (see Xiong et al. (2022)) allows us now to propose the application of the max-product algorithm for maximization (Viterbi, 1967; Bishop, 2006), instead of the sum-product algorithm for marginalization. Specifically, we can now

Namely, the subset Ai consists of all walks that have the same partial walk as the first solution until the (i − 1)-th layer, and differ at the i-th layer. No restriction is imposed for the subsequent layers, l = i + 1, . . . , L. Then we apply the max-product message passing to each subset, taking the corresponding constraint into account. Among the (L + 1) solutions from the subsets, the walk that gives the highest

(mi , ni ) ̸= (m b 1i , n b1i )} for i = 1, . . . , L. (12)

4

Relevant Walk Search for Explaining Graph Neural Networks 2

c ,n b 2 . The absolute relevance is the second best solution m third best solution can be similarly obtained by further split2 b 2 ), where Abi is the set from which the ting Abi \ (c m ,n second solution was found, into disjoint subsets, and we can e walks are collected iterate this procedure until the top-K (see Appendix B for detailed procedure). The number of e + 1 in the worst case. disjoint subsets increases up to KL e e.g., Note that this procedure can be terminated at any K, when we are satisfied with the collection, and therefore it is e beforehand. not necessary to fix K

the node-level relevance Q  P L−1 l,ml ,ml+1 L max Rm = maxm∈M n∈N Tnl ,nl+1 rnL,m l=0 L m∈M P P l−1,m ,ml 0 ,m1 = maxm∈M n0 ,n1 Tn0,m · · · nl Tnl−1 ,nl−1 l 0 ,n1 P P l,ml ,ml+1 L−1,m ,m L · · · nL TnL−1 ,nLL−1 L rnL,m . (13) nl+1 Tnl ,nl+1 L In the last equation, the summation operators are distributed according to the sum-product decomposition, while the maximization operator cannot be distributed. This is because the maximization for ml involves multiple terms that depend on ′ the propagation matrices {T l ,ml′ ,ml′ +1 } for l′ < l through the dependence on the neurons.

We call the algorithm described above—top-K relevant neuron-level walk search by max-product message passing, (10) and (11), and the search space splitting (12)— exact max-product search for neuron-level walks (EMPneu), for which the following theorem holds (for proof see Appendix B):

Now assume that the propagation matrices {T l−1,ml−1 ,ml } at the (l − 1)-th layer has similar columns, and can be l−1,ml−1 ,ml approximated as T l−1,ml−1 ,ml ≈ T , where l−1,ml−1 ,ml N (l−1) ×N (l) T ∈ R consists of the same columns equal to the average column of T l−1,ml−1 ,ml , PN (l) l−1,m ,ml l−1,ml−1 ,ml i.e., T nl−1 ,nl = N1(l) n′ =1 Tnl−1 ,nl−1 , ∀nl = ′

e walks with the highTheorem 3.1. Assume that the top-K est absolute relevance contain K walks with positive relevance. Then, EMP-neu finds the top-K neuron-level walks that maximize Eq.(7) with the computational com2 e 2 M N ) and the memory cost plexity O(LM 2 N + KL 2 O(LM 2 N ).

l

l

1, . . . , N (l) . With this approximation, we see that the max operator can be distributed as X l−1,ml−1 ,ml 0 ,m1 max Rm ≈ max Tn0,m · · · T nl−1 ,nl 0 ,n1 m∈M

max

ml+1 ,...,mL

This theorem guarantees that EMP-neu can perform exact search in polynomial-time. Notably, the complexity for e ≥ 2 can be much smaller than a naive application of the K whole message passing to each subset, which would cost e 2 M 2 N 2 ) (note that the graph size M and the feature O(KL dimension N are typically much larger than the network depth L in large-scale problems). This is because most of the messages required to find the k-th solution candidate in each subset have been already computed after the top(k − 1) solutions were found, and can be reused. How large e is required for a target K is affected by how many and K large negative entries the propagation matrices contain. We empirically found (see Appendix D.1) that the proportion e absolute walks are more of positive walks among the top-K than half for LRP-γ with γ ≥ 0.2, and therefore typically e < 2K. K

m0 ,...,ml

X nl ,nl+1

n0 ,n1

l ,ml+1 Tnl,m ··· l ,nl+1

X

L−1 ,mL L,mL TnL−1,m rnL . L−1 ,nL

nL

Inspired by this observation, we propose an approximate max-product search by averaging (AMP-ave), which iterates the following message passing for l = L, . . . , 0: P l−1,m ,ml l,ml m b l = argmaxml nl−1 ,nl Tnl−1 ,nl−1 µ bnl , (14) l P l−1,m , m b l−1 l bl l−1 µ bl−1,m = nl Tnl−1 ,nl µ bl,nlm . (15) nl−1 To find the top-K walks, we can apply the same search space splitting procedure (12) as in the neuron-level walk search. Algorithm details of AMP-ave are given in Appendix C. Below we give a few notes on AMP-ave: • Approximation error occurs in the maximization step (14), where the marginalization over nl−1 is already performed, ignoring the dependence of the propagal−2,m ,ml−1 tion matrix Tnl−2 ,nl−2 at the (l − 2)-th layer l−1 on nl−1 . This is justified when (T l−2,ml−2 ,ml−1 − l−2,ml−2 ,ml−1 T ) is not so large that it changes the choice m b l of node—which we refer to the columnsimilarity assumption in the subsequent sections. We will investigate the approximation accuracy and its dependence on the LRP parameters in Section 4.

3.2. Approximate Node-level Search Let us move our focus on the node-level walk relevance (8), which has shown to be useful for GNN explanation (Schnake et al., 2022; Xiong et al., 2022). Unfortunately, the max-product algorithm is not directly applicable to the nodelevel relevance because the marginalization over the neurons prevents max-product decompositions. As a remedy, we propose an approximation method.

• The relevance message (15) treats the dependence on nl−1 correctly, and therefore, the approximation error

Let us have a close look into the maximization problem of 5

Relevant Walk Search for Explaining Graph Neural Networks

does not acumulate as long as the approximate maximization step (14) gives the correct choice.

demonstrate the scalability of our framework, using the Infection dataset, for which exhaustive evaluation of all walks is infeasible. This dataset was originally generated by simulating a dissemination process based on the susceptibleinfected (SI) model—a common process in epidemiology studies (Bai et al., 2017; Oettershagen et al., 2020; Isella et al., 2011). We first generate a random directed graph with size M that expresses interactions between humans, by using the code provided by Faber et al. (2021). Then we randomly choose 2% of the population (nodes) to be the initial infected people or carriers. We simulate L-time steps of the infection process: each carrier infects its neighbors with probability λ, and never cures itself. We record the infection chains from one of the initial carriers to each carrier at time L, which are used as the ground truth for quantitative evaluation. We assume that the investigator, who has no information on the data generating process, trains a GNN to predict whether each person will be infected after L steps. We generated 100 samples (scenarios) with M = 1000, L = 4, λ = 0.6, and trained a L-layered GCN with 80 samples and tested on the other 20 samples. The model reached 82.51% accuracy, which is close to the prediction accuracy 83.1% by the oracle.2

• We do not apply the absolute value operation to the propagation matrices {T l,ml ,ml+1 } in the message passing. This is because marginalizing over the absolute values tends to significantly differ from the marginalizing over the original values, and the objective in Eq.(14) tends to be non-negative after the neuron marginalization (see Appendix D.2 for empirical investigation). When negative values are involved e walks in the maximization step, a few of the top-K found by AMP-ave can have negative relevance. In e such cases, we increment K(≥ K) until K walks with positive relevance are found, similarly to EMP-neu. • AMP-ave has the same computational complexity as 2 e 2 M N ). EMP-neu, i.e., O(LM 2 N + KL • A naive implementation that directly works with the 2 propagation matrices requires O(LM 2 N ) memory cost, which can be too huge for large scale problems. Although this is inevitable for the neuron-level walk search, AMP-ave can work on the activation matrices {H (l) } and the modified weight matrices {W ↑(l) } (see Sections 2.1 and 2.3 for the definitions), which reduces the memory costs to O(L max(M, N )2 ) and makes the node-level walk search feasible for larger scale problems (see Appendix C.1). For one layer in the GIN used in our experiment on Infection dataset, the memory cost reduced from 10002 × 322 ≈ 109 to only 10002 + 1000 ∗ 32 + 322 ≈ 106 Tensor.floats.

4.2. Approximation Accuracy of AMP-ave We first validated the accuracy of AMP-ave. By using BA2motif, MUTAG, Mutagenicity, and Graph-SST2 datasets with the corresponding trained GNN models, we performed an exhaustive search to identify the ground-truth top-K ∗ walks. Then, we performed approximate top-K walk search by AMP-ave for different K, and evaluated its performance in terms of precision TP/K and recall TP/K ∗ , where TP = |{Approx. top-K walks} ∩ {True top-K ∗ walks}|, on randomly chosen samples among the correctly classified test samples from each dataset.3 Figure 3 shows the precision-recall curves on BA-2motif and Mutagenicity for different K ∗ and different γ of LRP-γ rules. Here, γ = [3, · · · , 0] indicates the recommended setting by Schnake et al. (2022), i.e., γ is set from 3 to 0, linearly l decreasing as γ = 3(1 − L−1 ) for the l-th layer. We observe that the approximation accuracy by AMP-ave is generally good for LRP-γ with γ ≥ 0.2. Similar results were obtained on MUTAG and Graph-SST2 (see Appendix E). Note that the accuracy of AMP-ave is low for LRP-0, which however is rarely used for GNN explanation because of its

4. Experiments Here, we will empirically study our proposed approach. After introducing the datasets used in our experiments, we first evaluate the approximation accuracy of AMP-ave, i.e., how accurately AMP-ave can find the true top-K walks, by comparing with the ground-truth most relevant walks found by exhaustive search. Then, we show qualitative results demonstrating the utility of our approach, followed by quantitative evaluations supporting the exquisite performance of our walk search approach. Lastly, we report its computation cost, showing dramatic improvement over previous GNNLRP implementation from Schnake et al. (2022). Empirical evaluation of EMP-neu in terms of accuracy (or correctness) and computation time can be found in Appendix D.3.

2 As the oracle, we estimate the infection probability of each person, as well as the possible infection chains with their probabilities, by using the complete information of the data generation process including the parameter setting (see Appendix G for detailed computation). They are used as the ground truth or as the best possible predictor/detector in qualitative and quantitative evaluations. 3 Due to the exponential complexity of exhaustive search, we chose 10 samples from each dataset and excluded the Infection dataset.

4.1. Datasets We use common benchmark datasets including BA-2motif, MUTAG, Mutagenicity, and Graph-SST2 (see Appendix F for details on data and employed GNNs). We 6

Relevant Walk Search for Explaining Graph Neural Networks

Infection dataset, for which a naive implementation for GNN-LRP cannot be applied. We also demonstrate on smaller-scale Mutagenicity and Graph-SST2 datasets that the top-K walks, efficiently found by AMP-ave, already capture the most important information that GNN-LRP can get by evaluating all walks. Infection: Figure 5 compares explanations by our AMPave to Node-IG and Edge-IG (Sundararajan et al., 2017) on the Infection dataset with M = 1000, L = 4. Note that Edge-IG showed state-of-the-art performance on a similar infection chain detection task (Faber et al., 2021), outperforming the other existing methods including Grad-CAM (Baldassarre & Azizpour, 2019), GNNExplainer (Ying et al., 2019) and PGMExplainer (Vu & Thai, 2020). In the figure, each method explains why the GNN predicts that Node 1, depicted as a star at the top, will be infected after L time steps. The initial carriers that can infect the target node are depicted as squares at the bottom, and the nodes on the possible infection chains, identified by the oracle, are depicted with thick circles. In this example, there are only 3 possible infection chains, which were identified by AMP-ave as the top-3 relevant walks. On the contrary, Node-IG and EdgeIG do not identify those nodes as the most relevant nodes or the nodes connected to the most relevant edges. We also observe another advantage of AMP-ave that users can easily identify the whole infection chains, unlike the node-/edgelevel explanations that only provide partial information. Chemistry: Figure 6 shows example explanations for the mutagenicity prediction by a GNN on 1,4Naphthalenediamine (top) and Naphthalene (bottom) from Mutagenicity dataset. The former is known as mutagenic, while the latter as non-mutagenic. The figure compares our AMP-ave with K = 10, to Node-IG, Edge-IG, as well as to GNN-LRP that depicts all M L+1 walks. The red and blue colors indicate evidence for mutagenicity and nonmutagenicity, respectively. We observe that the top-10 walks found by AMP-ave already capture the functional group— —the NH2 combined with an aromatic carbon ring—that are known to cause mutagenicity. AMP-ave also found the non-fused carbon rings, which indicates non-mutagenicity. GNN-LRP also provides negative evidence to the (non)mutagenicity of the molecules, which is also useful: in the upper molecule the right carbons are indicators for nonmutagenicity, and in the bottom molecule the middle C-C points to a fused carbon ring could in principle be an indicator for mutagenicity in some molecules. However, we emphasize that our AMP-ave, which captures the most important positive evidence with only polynomial complexity, is a useful alternative to the full GNN-LRP, which requires exponential complexity. Other examples are shown in Appendix I. Language: We furthermore compared AMP-ave with the baseline methods on Graph-SST2 dataset, and observed similar trends as shown for infection and chemistry above (see

Figure 3. Precision-recall curves of AMP-ave in top-K ∗ node-level walk search on BA-2motif (top) and Mutagenicity (bottom).

Figure 4. The histograms of the cosine similarity (16) between the column vectors and their average of the propagation matrices for γ = [3, . . . , 0]. Each panel corresponds to each dataset.

poor performance in general (Schnake et al., 2022). In the subsequent experiments, we focus on the recommended setting γ = [3, · · · , 0]. Column-similarity Assumption: Here, we investigate to what extent the assumption required for high accuracy of AMP-ave holds. Specifically, we measure the cosine simi(l) l,m ,m larity between the column vectors {tnl l l+1 }N nl =1 of the l,m ,m

propagation matrix T l,ml ,ml+1 with their average t l l+1 l,ml ,ml+1 (the corresponding column vectors of T ) for each edge (ml , ml+1 ) in each layer l:  l,m ,m ⊤ l,m ,m tnl l l+1 tnl l l+1 l,m ,ml+1

tn l l

l,m ,ml+1

tn l l

for

nl = 1, . . . , N (l) .

(16)

Figure 4 shows the histograms of the cosine similarity over all nl , ml , ml+1 , l and all positive class data samples classified correctly. The zero column vectors are excluded. The average cosine similarity is above 0.8 for all four datasets, which explains the good accuracy of AMP-ave. Further analysis is necessary to guarantee the approximation accuracy, and fully understand its relation to the column similarity. 4.3. Visualization with Top-K Walks Now we demonstrate that AMP-ave provides better explanations than the lower-order methods on the large-scale 7

Relevant Walk Search for Explaining Graph Neural Networks

(a) AMP-ave (top-3 walks).

(b) Node-IG (top 10 nodes).

(c) Edge-IG (top 10 edges).

Figure 5. Visual explanation by AMP-ave (ours), Edge-IG, and Node-IG on Infection dataset. The deeper the red color is, the higher the relevance is. The star node at the top is the target node for which the prediction is explained, while the square nodes at the bottom are initial carriers. For clarity, we only plot the nodes within 4-hops from the target node, and the nodes involved in the 3 possible infection chains are depicted as thick circles. The top-1 walk by AMP-ave, shown as solid arrows, is exactly the ground truth infection chain, with the top-2 and top-3 walks being two other possible infection chains. AMP-ave

GNN-LRP

Node-IG

Edge-IG

Figure 7. Recall of infection chain detection on Infection dataset. Figure 6. Explanation for 1,4-Naphthalenediamine (top; mutagenic), and Naphthalene (bottom; non-mutagenic) from Mutagenicity. The red and blue colors indicate evidence of mutagenicity and non-mutagenicity, respectively. Top-10 walks by our AMP-ave can already capture the most relevant functional groups for molecules’ (non-)mutagenicity with polynomial complexity.

Appendix I). Figure 8. Recall of motif’s edge detection on BA-2motif dataset. Positive samples and negative samples are plotted separately.

4.4. Quantitative Evaluation We conducted a quantitative evaluation on Infection data by using the ground truth infection chain, which well-trained GNNs are expected to use as an important information flow. We used AMP-ave as an infection chain detector, and evaluated its performance with different K. As shown in Figure 7, top-5 walks already include the ground-truth walk with 94.22% recall, and the performance is close to the oracle detector (see Appendix G). Since no existing polynomialtime method provides walk-level explanation, we compare our method with two heuristic methods, Edge-IG sum and Edge-IG prod, based on Edge-IG (Sundararajan et al., 2017), where top K walks are constructed from the most relevant edges (see Appendix H for details). Figure 7 shows that the two heuristics are clearly outperformed by our AMP-ave. We also used the BA-2motif dataset, which provides the ground truth subgraphs as motifs, and evaluated how accurately explanation methods can detect the motifs. Specifically, we labeled all edges included in the motif as positive samples, and compared edge detection performance of

AMP-ave to popular edge-level explanability baseline methods with comparable computational complexity,4 including Edge-IG, GNNExplainer, edge-level GNN-LRP (relevance propagated to edges in the input layer) and simple Gradientbased heatmap for edges. Here the edge scoring by AMPave is simply the highest relevance of the walk that contains the corresponding edge. Figure 8 shows the recall. We see that AMP-ave reaches 100% recall faster than all baselines, indicating that it can detect the motif more precisely. 4.5. Computational Efficiency Table 1 shows computation time (on an M1Pro CPU) of explanation methods on the BA-2motif and Infection datasets. AMP-ave is orders of magnitude faster than GNN-LRP, 4

We excluded in our evaluation recently proposed methods, e.g., GraphMask (Schlichtkrull et al., 2021) and Tage (Xie et al., 2022), that are by several orders of magnitude slower than ours.

8

Relevant Walk Search for Explaining Graph Neural Networks Table 1. Computation time (in seconds). B and I denote BA-2motif (small graph) and Infection (large graph) datasets, respectively.

AMP- AVE K = 1 AMP- AVE K = 25 AMP- AVE K = 1000 E DGE -IG ( EDGE - LEVEL ) GNNE XPLAINER ( EDGE - LEVEL ) GNN-LRP ( EXHAUSTIVE )

(a) Network depth dependence

T IME (B)

T IME (I)

0.003 0.123 2.574 0.124 0.371 15.879

0.137 1.217 86.006 0.514 60.621 > 1011

pose a family of novel relevant walk search algorithms based on max-product message passing. Specifically, our proposed EMP-neu performs exact search for the top-K most relevant walks at neuron-level, and AMP-ave performs approximate search at node-level, both in polynomial-time instead of previous exponential time approaches (see Schnake et al. (2022)). Our novel methods provide robust and fast explanation with their performance validated competitively in our experiments on several synthetic and real-world datasets. In future studies we will aim to apply our novel efficient higher-order explanation methods broadly to the sciences and engineering, e.g., epidemic studies (Oettershagen et al., 2020; Isella et al., 2011) and software vulnerability detection (Yamaguchi et al., 2014), ultimately hoping to contribute to furthering the transparency, security, robustness, and fairness of machine learning methods. Finally, we would like to stress that our novel max-product approach can be applied to any feed-forward neural network: EMP-neu is for finding neuron-level walks, while AMP-ave is for finding block-level walks, where marginalization over the neurons in blocks is involved. An immediate application would be to obtain neuron-/block-level decompositions similar to Achtibat et al. (2022) for discovering concept-based decompositions of even finer granularity.

(b) Graph size dependence

Figure 9. Computation time dependence on the network depth L (left) and on the graph size M (right). Note the different vertical scales in the top and bottom parts, and that y-axis in (a) is in log-scale. For the depth larger than L > 4, the computation time of exhaustive search is estimated from partial computation, since the whole computation is infeasible. (a) Top-1 walk search with GIN-L for L = 2, . . . , 7 on BA-2motif. (b) Top-1 walk search with GIN-3 for M s among all samples in Mutagenicity dataset.

Limitations Our node-level walk search method—AMP-ave—is an approximation method, of which the accuracy has not been theoretically guaranteed but only supported by empirical evaluation. Further investigation on the relation between the accuracy of AMP-ave and properties of propagation matrices is necessary to understand for what propagation rules AMP-ave is reliable. A compromising approach is also possible and worth pursuing: one can cluster the neurons based on the propagation vectors so that the column-similarity assumption better holds at the expense of the computational cost proportional to N L , where N is the number of clusters. Another limitation is that our approach can be applied only to the models for which the relevance propagation can be defined as in Eq.(5). This might exclude some of the general GNNs beyond MPNNs. Efforts should be made for developing appropriate propagation rules for different architectures, in order to explain general large scale GNNs with our efficient algorithms.

where all walks are evaluated, and can be applied even to the large Infection dataset. The computation time of Edge-IG and GNNExplaner is measured in the task of relevant edge detection. Figure 9 plots the computation time of AMP-ave and exhaustive search as functions of the network depth L (left) and the graph size M (right). The huge computational gain by our approach becomes evident.

5. Conclusion Many practical applications such as chemistry, infection biology, NLP etc., embody complex correlations that are higher-order in nature. While deep learning models can exploit such structure for improving prediction, it has so far been a challenge to practically extract such higher-order information from a learned model. The notion of walk relevance, based on layer-wise relevance propagation for graph neural networks (GNN-LRP) (Schnake et al., 2022), was introduced for higher-order attribution; notably it has also provided a new perspective of LRP computation as a byproduct—the decomposability of relevance. Previous work used this property and developed efficient marginalization algorithms, called subgraph GNNLRP, for subgraph attribution by using the sum-product message passing (Xiong et al., 2022), while in this paper we pro-

Acknowledgments This work was supported by the German Ministry for Education and Research (BMBF) as BIFOLD - Berlin Institute for the Foundations of Learning and Data under grants 01IS18025A and 01IS18037A.

9

Relevant Walk Search for Explaining Graph Neural Networks

References

Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, pp. 1263–1272. JMLR.org, 2017.

Achtibat, R., Dreyer, M., Eisenbraun, I., Bosse, S., Wiegand, T., Samek, W., and Lapuschkin, S. From ”where” to ”what”: Towards human-understandable explanations through concept relevance propagation. CoRR, abs/2206.03208, 2022.

Isella, L., Stehlé, J., Barrat, A., Cattuto, C., Pinton, J.F., and Van den Broeck, W. What’s in a crowd? analysis of face-to-face behavioral networks. Journal of Theoretical Biology, 271(1):166–180, 2011. ISSN 0022-5193. doi: https://doi.org/10.1016/j.jtbi.2010.11. 033. URL https://www.sciencedirect.com/ science/article/pii/S0022519310006284.

Bach, S., Binder, A., Montavon, G., Klauschen, F., Müller, K.-R., and Samek, W. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10(7):e0130140, 2015. Bai, Y., Yang, B., Lin, L., Herrera, J. L., Du, Z., and Holme, P. Optimizing sentinel surveillance in temporal network epidemiology. Scientific reports, 7(1):1–10, 2017.

Kazius, J., McGuire, R., and Bursi, R. Derivation and validation of toxicophores for mutagenicity prediction. Journal of Medicinal Chemistry, 48(1):312–320, 2005. doi: 10.1021/jm040835a. PMID: 15634026.

Baldassarre, F. and Azizpour, H. Explainability techniques for graph convolutional networks. CoRR, abs/1905.13686, 2019. URL http://arxiv.org/ abs/1905.13686.

Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.

Bishop, C. M. Pattern Recognition and Machine Learning (Information Science and Statistics), pp. 402–411. Springer-Verlag, Berlin, Heidelberg, 2006. ISBN 0387310738.

Lundberg, S. M. and Lee, S.-I. A unified approach to interpreting model predictions. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30, pp. 4768–4777. Curran Associates, Inc., 2017.

Debnath, A. K., Lopez de Compadre, R. L., Debnath, G., Shusterman, A. J., and Hansch, C. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34 (2):786–797, 1991. doi: 10.1021/jm00106a046.

Luo, D., Cheng, W., Xu, D., Yu, W., Zong, B., Chen, H., and Zhang, X. Parameterized explainer for graph neural network. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.

Eberle, O., Büttner, J., Kräutli, F., Müller, K., Valleriani, M., and Montavon, G. Building and interpreting deep similarity models. IEEE Trans. Pattern Anal. Mach. Intell., 44(3):1149–1161, 2022. doi: 10.1109/TPAMI.2020. 3020738. Faber, L., K. Moghaddam, A., and Wattenhofer, R. When comparing to ground truth is wrong: On evaluating gnn explanation methods. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD ’21, pp. 332–341, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383325. doi: 10.1145/ 3447548.3467283. URL https://doi.org/10. 1145/3447548.3467283. Gao, Y., Sun, T., Bhatt, R., Yu, D., Hong, S., and Zhao, L. GNES: learning to explain graph neural networks. In Bailey, J., Miettinen, P., Koh, Y. S., Tao, D., and Wu, X. (eds.), IEEE International Conference on Data Mining, ICDM 2021, Auckland, New Zealand, December 7-10, 2021, pp. 131–140. IEEE, 2021. 10

Montavon, G., Binder, A., Lapuschkin, S., Samek, W., and Müller, K. Layer-wise relevance propagation: An overview. In Explainable AI, volume 11700 of Lecture Notes in Computer Science, pp. 193–209. Springer, 2019. Nilsson, D. An efficient algorithm for finding the m most probable configurationsin probabilistic expert systems. Statistics and computing, 8(2):159–173, 1998. Oettershagen, L., Kriege, N. M., Morris, C., and Mutzel, P. Temporal graph kernels for classifying dissemination processes. In Demeniconi, C. and Chawla, N. V. (eds.), Proceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020, Cincinnati, Ohio, USA, May 7-9, 2020, pp. 496–504. SIAM, 2020. doi: 10.1137/ 1.9781611976236.56. URL https://doi.org/10. 1137/1.9781611976236.56.

Relevant Walk Search for Explaining Graph Neural Networks

Pearl, J. Reverend Bayes on inference engines: A distributed hierarchical approach. In Waltz, D. L. (ed.), Proceedings of the National Conference on Artificial Intelligence, Pittsburgh, PA, USA, August 18-20, 1982, pp. 133–136. AAAI Press, 1982.

and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. Wang, X. and Shen, H. Gnninterpreter: A probabilistic generative model-level explanation for graph neural networks. CoRR, abs/2209.07924, 2022. doi: 10. 48550/arXiv.2209.07924. URL https://doi.org/ 10.48550/arXiv.2209.07924.

Pope, P. E., Kolouri, S., Rostami, M., Martin, C. E., and Hoffmann, H. Explainability methods for graph convolutional neural networks. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pp. 10772–10781. Computer Vision Foundation / IEEE, 2019.

Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Yu, P. S. A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn. Syst., 32(1):4–24, 2021a. doi: 10.1109/TNNLS.2020.2978386. URL https:// doi.org/10.1109/TNNLS.2020.2978386.

Samek, W., Montavon, G., Lapuschkin, S., Anders, C. J., and Müller, K.-R. Explaining deep neural networks and beyond: A review of methods and applications. Proc. IEEE, 109(3):247–278, 2021.

Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Yu, P. S. A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn. Syst., 32(1):4–24, 2021b.

Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Trans. Neural Networks, 20(1):61–80, 2009.

Xie, Y., Katariya, S., Tang, X., Huang, E. W., Rao, N., Subbian, K., and Ji, S. Task-agnostic graph explanations. In NeurIPS, 2022.

Schlichtkrull, M. S., Cao, N. D., and Titov, I. Interpreting graph neural networks for NLP with differentiable edge masking. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https: //openreview.net/forum?id=WznmQa42ZAx.

Xiong, P., Schnake, T., Montavon, G., Müller, K., and Nakajima, S. Efficient computation of higher-order subgraph attribution via message passing. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., and Sabato, S. (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 24478–24495. PMLR, 2022. URL https://proceedings.mlr.press/ v162/xiong22a.html.

Schnake, T., Eberle, O., Lederer, J., Nakajima, S., Schütt, K. T., Müller, K., and Montavon, G. Higher-order explanations of graph neural networks via relevant walks. IEEE Trans. Pattern Anal. Mach. Intell., 44(11):7581– 7596, 2022. Schütt, K. T., Sauceda, H. E., Kindermans, P.-J., Tkatchenko, A., and Müller, K.-R. Schnet–a deep learning architecture for molecules and materials. The Journal of Chemical Physics, 148(24):241722, 2018.

Yamaguchi, F., Golde, N., Arp, D., and Rieck, K. Modeling and discovering vulnerabilities with code property graphs. In 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, May 18-21, 2014, pp. 590–604. IEEE Computer Society, 2014. doi: 10.1109/SP.2014. 44. URL https://doi.org/10.1109/SP.2014. 44.

Sundararajan, M., Taly, A., and Yan, Q. Axiomatic attribution for deep networks. In Precup, D. and Teh, Y. W. (eds.), Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 3319–3328. PMLR, 2017. URL http://proceedings.mlr.press/ v70/sundararajan17a.html.

Yanardag, P. and Vishwanathan, S. V. N. Deep graph kernels. In Cao, L., Zhang, C., Joachims, T., Webb, G. I., Margineantu, D. D., and Williams, G. (eds.), Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, pp. 1365–1374. ACM, 2015. doi: 10.1145/2783258.2783417.

Viterbi, A. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory, 13(2):260–269, 1967. doi: 10.1109/TIT.1967.1054010.

Ying, Z., Bourgeois, D., You, J., Zitnik, M., and Leskovec, J. Gnnexplainer: Generating explanations for graph neural networks. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d’Alché-Buc, F., Fox, E. B., and Garnett, R.

Vu, M. N. and Thai, M. T. PGM-Explainer: Probabilistic graphical model explanations for graph neural networks. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., 11

Relevant Walk Search for Explaining Graph Neural Networks

(eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 9240–9251, 2019. Yuan, H., Tang, J., Hu, X., and Ji, S. XGNN: towards modellevel explanations of graph neural networks. In Gupta, R., Liu, Y., Tang, J., and Prakash, B. A. (eds.), KDD ’20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pp. 430–438. ACM, 2020a. Yuan, H., Yu, H., Gui, S., and Ji, S. Explainability in graph neural networks: A taxonomic survey. CoRR, abs/2012.15445, 2020b. URL https://arxiv.org/ abs/2012.15445. Yuan, H., Yu, H., Wang, J., Li, K., and Ji, S. On explainability of graph neural networks via subgraph explorations. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 12241– 12252. PMLR, 2021.

12

Relevant Walk Search for Explaining Graph Neural Networks

A. Notation Table Table 2 summarizes the notation used in this paper.

h, h, H, Hm,m′ ml:l′ G and S m and n m, ml n, nl R, r r̆ T b m c, n b R,

Table 2. Notation. scalar, vector, matrix, matrix entry partial vector with indices (l, . . . , l′ ) graph and subgraph sequence of nodes and neurons integers for node identifications integers for neuron identifications relevance propagated relevance, message, or belief propagation matrix optimum relevance, optimum walk, etc.

B. Details of Exact Max-product Message Passing Algorithm for Neuron-level Search (EMP-neu) B.1. EMP-neu-Basic: Derivation of Message Passing Equations (10) and (11) Applying the max-product decompositions to the objective (9) gives b ≡ max R̆m,n = max |T 0,m0 ,m1 ||T 1,m1 ,m2 | · · · |T L−1,mL−1 ,mL ||rL,mL | R n0 ,n1 n1 ,n2 nL−1 ,nL nL m,n

m,n

0 ,m1 1 ,m2 L−1 ,mL L | |rnL,m |, = max max |Tn0,m | max |Tn1,m | · · · max |TnL−1,m 0 ,n1 1 ,n2 L−1 ,nL L m0 ,n0 m1 ,n1 m2 ,n2 mL ,nL | {z } L,m

=b µnL L

| |

{z

L−1,m

=b µnL−1 L−1

{z

1,m

=b µ n1 1

|

{z

0,m

=b µ n0 0

} } }

l where {b µl,m nl } are the messages that can be computed by Eqs.(10) and (11) sequentially for l = L, . . . , 0. Thus, we get 0,m0 b = maxm ,n µ R . Backtracing the mappings (ml−1 , nl−1 ) → (ml , nl ), computed by Eq.(10), for l = 1, . . . , L gives 0 0 bn0 the walk maximizing the absolute relevance. The algorithm, which we call EMP-neu-Basic, for finding the highest absolute relevant neuron-level walk is summarized in Algorithm 1.

Algorithm 1 Find the highest absolute relevant neuron-level walk (EMP-neu-Basic) Input: # of nodes: M , # of neurons at l-th layer: N (l) , LRP transition matrices {T l,ml ,ml+1 }, initial messages {b µL,mL } L,mL L,mL such that µ bnL = |rnL |. for l = L to 1 do for ml−1 = 1 to M do for nl−1 = 1 to N (l−1) do Find ml , nl by solving: l−1,m ,ml l,ml argmaxml ,nl |Tnl−1 ,nl−1 |b µ nl l Store the result in a maximum step mapping (ml−1 , nl−1 ) → (ml , nl ). Compute the relevance along the corresponding maximum walk step for ml−1 , nl−1 : l−1,m l−1,m ,ml l,ml µ bnl−1 l−1 = |Tnl−1 ,nl−1 |b µ nl l end for end for end for 0 Select (m∗0 , n∗0 ) by argmaxm0 ,n0 µ b0,m n0 . Read from the maximum step mappings the full walk (m∗ , n∗ ) = (m∗0 , n∗0 ) → (m∗1 , n∗1 ) → · · · → (m∗L , n∗L ). return (m∗ , n∗ ). 13

Relevant Walk Search for Explaining Graph Neural Networks

e most relevant neuron-level walks Algorithm 2 Search space splitting for finding the top-K 1 1 Input: top-1 most relevant walk (m , n ), maximum step mappings (ml−1 , nl−1 ) → (ml , nl ). Initialize SearchSpace = {} Initialize T opKW alks = {(m1 , n1 )} for l = 0 to L do subset = {(m, n) : (mj , nj ) = (m1j , n1j ) ∀j < l, (ml , nl ) ̸= (m1l , n1l )}. Set the beginning of (m∗ , n∗ ) such that (m∗j , n∗j ) = (m1j , n1j ) ∀j < l. Read from the maximum step mappings the following steps (m∗l , n∗l ) → · · · → (m∗L , n∗L ). Add (subset : (m∗ , n∗ )) to SearchSpace. end for e do for k = 2 to K M axRelevance = −∞ for {subset : (m∗ , n∗ )} in SearchSpace do ∗ ∗ if R(m ,n ) > M axRelevance then ∗ ∗ M axRelevance = R(m ,n ) . k k ∗ ∗ (m , n ) = (m , n ) M axSubset = subset end if end for Add (mk , nk ) to T opKW alks. Split M axSubset according to (18), read out each subspace’ most relevant walk, and add them to SearchSpace. Remove M axSubset from SearchSpace. end for return T opKW alks.

B.2. Complexity of Finding the Most Relevant Walk by EMP-neu-Basic From Algorithm 1 we can find that the computational complexity of finding the highest absolute relevant neuron-level walk 2 2 is O(LM 2 N + M N + L) = O(LM 2 N ). The memory cost including the storage for the transition matrices and the 2 maximum step mappings is O(LM 2 N ). e Walks B.3. Search Space Splitting for Finding Top-K 1

b 1 ) the best solution found by EMP-neu-Basic. Then, the second solution can be found by splitting Let us denote by (c m ,n 1 b 1 ) into L + 1 disjoint subsets {Ai }, where the rest of the search space (M × N) \ (c m ,n A0 = {(m, n) : (m0 , n0 ) ̸= (m b 10 , n b10 )}, Ai = {(m, n) : (m0:i−1 , n0:i−1 ) = (m b 10:i−1 , n b10:i−1 ), (mi , ni ) ̸= (m b 1i , n b1i )}

for

i = 1, . . . , L.

(17)

Note that the subset Ai consists of all walks that have the same partial walk as the first solution until the (i − 1)-th layer, and differ at the i-th layer. No restriction is imposed for the subsequent layers, l = i + 1, . . . , L. Then we apply EMP-neu-Basic to each subset, taking the corresponding constraint into account. Among the (L + 1) solutions from the subsets, the walk 2 b 2 ). that gives the highest absolute relevance is the second best solution (c m ,n Assume that the second solution was found from Abi , which means that (m b 10:i−1 , n b10:i−1 ) = (m b 20:i−1 , n b20:i−1 ). 2 b 2 ) into (L − bi + 1) disjoint subsets {Abi,j }, where To obtain the third best solution, we split Abi \ (c m ,n

Abi,0 = {(m, n) ∈ Abi : (mbi , nbi ) ∈ / {(m b b1i , n bb1i ), (m b b2i , n bb2i )}}, Abi,j = {(m, n) ∈ Abi : (mbi:bi+j−1 , nbi:bi+j−1 ) = (mb2i:bi+j−1 , nb2i:bi+j−1 ), (mbi+j , nbi+j ) ̸= (m b b2i+j , n bb2i+j )} for

j = 1, . . . , L − bi, 14

(18)

Relevant Walk Search for Explaining Graph Neural Networks

Algorithm 3 Find the most relevant node-level walk approximately by averaging (AMP-ave-Basic) L L | = |rnL,m Input: # of nodes: M , LRP transition matrices {T l,ml ,ml+1 }, initial messages {b µL,mL } such that µ bL,m nL L for l = L to 1 do for ml−1 = 1 to M do Find ml by solving: P P l−1,m ,ml l,ml argmaxml nl−1 nl Tnl−1 ,nl−1 µ bnl l Store the result in a maximum step mapping ml−1 → ml . Compute the relevance along the corresponding maximum walk step for ml−1 : P l−1,m l−1,m ,ml l,ml µ bnl−1 l−1 = nl Tnl−1 ,nl−1 µ bnl l end for end for P 0 Select m∗0 by argmaxm0 n0 µ b0,m n0 . Read from the maximum step mappings the full walk m∗ = m∗0 → m∗1 → · · · → m∗L . return m∗ .

and apply EMP-neu-Basic to each subset. Now, we have (2L − bi + 1) disjoint subsets that covers the remaining search space, i.e., 1

2

i b 1 ) ∪ (c b 2 )}, (∪i̸=bi Ai ) ∪ (∪L− m ,n m ,n j=0 Ab i,j ) = (M × N) \ {(c b

with the maximizer from each subset. The third best solution is the best one among those maximizer. Similarly, the k-th solution can be found by splitting the subset from which the (k − 1)-th solution was found into disjoint e solutions are found. subsets, and applying EMP-neu-Basic to each new subset. We continue this process until top-K Algorithm 2 summarizes this procedure. B.4. Upper Bound of Number of Subsets e + 1) subsets in the worst case. Formally, the search space splitting procedure, described in Appendix B.3, generates (KL (l) e None of those subsets is empty if K ≤ M N , where N = min N , while some can be empty otherwise. Therefore, the e + 1. number of subsets is upper-bounded by KL e Neuron-level Walk Search B.5. Proof of Theorem 3.1: Complexity of Top-K e neuron-level walks with the highest Appendix B.1 and Appendix B.3 already explained how EMP-neu finds the top-K absolute relevances, and the top-K walks with the highest positive relevances can be found from those solutions by assumption. Below we consider the computational complexity. 2

According to Appendix B.2, finding the walk with the highest absolute relevance by EMP-neu-Basic requires O(LM 2 N ) e e + 1) subsets time. For finding the second to the K-th solution, the search space splitting generates no more than (KL (see Appendix B.4), for each of which EMP-neu-Basic needs to be applied. However, in finding the k-th solution, maximization in each subset is operated effectively only at one layer with the messages m b l (ml−1 , nl−1 ) and n bl (ml−1 , nl−1 ) already computed when the top-(k − 1) solutions were searched. Therefore, by reusing those messages, the computation complexity to find the maximizer from each subset for the k(≥ 2)-th solution search is only O(LM N ). Therefore, the 2 e total computational cost of EMP-neu is O(LM 2 N + KL(LM N )). The memory cost is dominated by the storage for the 2 transition matrices (see Appendix B.2) and thus O(LM 2 N ).

C. Details of Approximate Max-product Message Passing Algorithm with Averaging for Node-level Walks (AMP-ave) Algorithm 3 describes the detailed steps of AMP-ave-Basic that approximately finds the most relevant node-level walk, e node level search. while Algorithm 4 describes the steps of search space splitting for the top-K Similarly to EMP-neu-Basic, AMP-neu-Basic (Algorithm 3) requires O(LM 2 N 2 ) time, and the search space splitting (Algorithm 4) requires O(KL2 M N ), and thus the total computational complexity is O(LM 2 N 2 + KL2 M N ). 15

Relevant Walk Search for Explaining Graph Neural Networks

e most relevant node-level walks Algorithm 4 Search space splitting for approximately finding the top-K 1 Input: top-1 most relevant node-level walk m , maximum step mappings ml−1 → ml . Initialize SearchSpace = {} Initialize T opKW alks = {m1 } for l = 0 to L do subset = {m : mj = m1j ∀j < l, ml ̸= m1l )}. Set the beginning of m∗ such that m∗j = m1j ∀j < l. Read from the maximum step mappings the following steps m∗l → · · · → m∗L . Add (subset : m∗ ) to SearchSpace. end for e do for k = 2 to K M axRelevance = −∞ for {subset : m∗ } in SearchSpace do ∗ if Rm > M axRelevance then ∗ M axRelevance = Rm . k ∗ m =m . M axSubset = subset. end if end for Add mk to T opKW alks. Split M axSubset similar to (18), read out each subspace’ most relevant walk, and add them to SearchSpace. Remove M axSubset from SearchSpace. end for return T opKW alks.

A naive implementation requires the same memory cost O(LM 2 N 2 ) as EMP-neu to store the transition matrices. However, there is a way to reduce the memory cost to O(M 2 + LN (M + N )) = O(L max(M, N )2 ), as explained below. C.1. Low-Memory Computation for Top-K Node-level Walk Algorithm Substituting the explicit expression (6) of the propagation matrices for GCN into the objective in the message passing (14) gives P

nl−1

(l−1) ↑(l−1) Λm P P ,m Hm ,nl−1 Wnl−1 ,nl l−1,ml−1 ,ml l,ml l µ bnl = nl−1 nl P l−1 l l−1 (l−1) bl,m ↑(l−1) µ nl nl Tnl−1 ,nl H W ′′ ′′ Λ ′′

P

m ,n

= Λml−1 ,ml (l)

(l−1)

m ,ml

m′′ ,n′′

n′′ ,nl

↑(l−1) H (l−1) ml−1 W nl (l−1) ↑(l−1) nl P ′′ Λ ′′ m ,ml H m′′ W nl m

P

(19) l µ bl,m nl ,

(l)

×N where Λ ∈ RM ×M , H (l) ∈ RM ×N , W ↑(l) ∈ RN are the adjacency matrix, the activation matrix, and the modified weight matrix, respectively (see Sections 2.1 and 2.3). The expression (19) implies that the maximization (14), as well as the relevance message passing (15), can be performed by using Λ, {H (l) , W ↑(l) }, which requires O(M 2 + LM N + 2 2 LN ) memory, without storing the transition matrices {T (l),ml ,ml+1 }, which requires O(M 2 N ) memory. The memory 2 cost of this implementation is thus O(L max(M, N ) ).

D. Empirical Investigation of Algorithm Behavior e Absolute Relevant Walks D.1. Proportion of Positive Relevant Walks in Top-K e absolute relevant neuron-level We randomly chose 10 correctly classified graph samples from MUTAG and found the top-K e absolute walks by EMP-neu. Figure 10 plots the proportion K of the number K of positive relevant walks in the top-K e K relevant walks. We observe that higher γ leads to a larger proportion of positive walks, and that more than half walks are positive for γ ≥ 0.2. 16

Relevant Walk Search for Explaining Graph Neural Networks

K e Figure 10. The proportion K e of positive relevant neuron-level walks in the top-K absolute relevant walks.

Dataset

γ

BA-2motif

0 0.2 [3, . . . , 0] +∞ 0 0.2 [3, . . . , 0] +∞ 0 0.2 [3, . . . , 0] +∞

MUTAG

Graph-SST2

+

−

0

3.70% 6.38% 5.34% 6.70% 11.82% 12.39% 12.86% 14.28% 39.17% 41.45% 42.06% 40.48%

4.12% 2.78% 2.66% 2.67% 2.48% 2.23% 1.95% 1.12% 3.30% 2.41% 1.76% 3.30%

92.10% 90.84% 92.01% 90.63% 85.70% 85.38% 85.19% 84.60% 57.53% 56.14% 56.18% 56.22%

Table 3. Frequency of the sign of the objective in AMP-ave message passing (14).

D.2. Sign of Maximization Objective in Eq.(14) Table 3 shows how often the objective of the maximization objective in the AMP-ave message passing (14) is positive, negative, or zero on randomly chosen 10 correctly classified samples from BA-2motif, MUTAG, and Graph-SST2 with different γ. We see that the objective tends to be positive or zero for γ ≥ 0.2, although it can be negative with significant frequency, compared to the positive frequency, in BA-2motif. D.3. Empirical results from EMP-neu Here we verify the correctness of the top neuron-level walks found by EMP-neu. For one graph each from the positive (Table 4) and the negative (Table 5) classes in BA-2motif, we list the top 100 most absolute relevant walks (before omitting the negative-relevant walks) found by EMP-neu. The first and the second columns, respectively, show the estimated ranking by EMP-neu and the true ranking found by the exhaustive search. We observe that the true ranking is in non-decreasing order, proving the correctness of EMP-neu. Notably, our method took only 3.4 seconds to find the top 100 most absolute relevant walks, while the exhaustive search took over 3 hours, because the number of possible neuron-level walks is O((M N )L ).

E. Additional Precision Evaluation on MUTAG and Graph-SST2 Figure 11 shows the precision-recall curves of AMP-ave on MUTAG and Graph-SST2.

F. Datasets and GNN Models for Experiments The datasets (summarized in Table 6) and models are mainly downloaded and trained according to the instructions provided in Xiong et al. (2022). 17

Relevant Walk Search for Explaining Graph Neural Networks

Est. #

True #

Most absolute relevant walks

Relevance

Est. #

True #

Most absolute relevant walks

Relevance

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

1 1 1 1 1 1 7 7 7 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

((21, 0), (22, 9), (23, 11), (24, 0)) ((22, 0), (22, 9), (23, 11), (24, 0)) ((23, 0), (22, 9), (23, 11), (24, 0)) ((24, 0), (23, 9), (23, 11), (24, 0)) ((22, 0), (23, 9), (23, 11), (24, 0)) ((23, 0), (23, 9), (23, 11), (24, 0)) ((20, 0), (24, 9), (23, 11), (24, 0)) ((23, 0), (24, 9), (23, 11), (24, 0)) ((24, 0), (24, 9), (23, 11), (24, 0)) ((21, 0), (21, 9), (22, 11), (21, 0)) ((21, 0), (22, 9), (22, 11), (21, 0)) ((21, 0), (22, 9), (23, 11), (22, 0)) ((21, 0), (22, 9), (23, 11), (23, 0)) ((22, 0), (21, 9), (22, 11), (21, 0)) ((22, 0), (22, 9), (22, 11), (21, 0)) ((22, 0), (22, 9), (23, 11), (22, 0)) ((22, 0), (22, 9), (23, 11), (23, 0)) ((23, 0), (22, 9), (22, 11), (21, 0)) ((23, 0), (22, 9), (23, 11), (22, 0)) ((23, 0), (22, 9), (23, 11), (23, 0)) ((24, 0), (23, 9), (22, 11), (21, 0)) ((24, 0), (23, 9), (23, 11), (22, 0)) ((24, 0), (23, 9), (23, 11), (23, 0)) ((22, 0), (23, 9), (22, 11), (21, 0)) ((22, 0), (23, 9), (23, 11), (22, 0)) ((22, 0), (23, 9), (23, 11), (23, 0)) ((23, 0), (23, 9), (22, 11), (21, 0)) ((23, 0), (23, 9), (23, 11), (22, 0)) ((23, 0), (23, 9), (23, 11), (23, 0)) ((20, 0), (21, 9), (22, 11), (21, 0)) ((20, 0), (24, 9), (23, 11), (22, 0)) ((20, 0), (24, 9), (23, 11), (23, 0)) ((23, 0), (24, 9), (23, 11), (22, 0)) ((23, 0), (24, 9), (23, 11), (23, 0)) ((24, 0), (24, 9), (23, 11), (22, 0)) ((24, 0), (24, 9), (23, 11), (23, 0)) ((21, 0), (21, 9), (22, 11), (22, 0)) ((21, 0), (21, 9), (22, 11), (23, 0)) ((21, 0), (22, 9), (22, 11), (22, 0)) ((21, 0), (22, 9), (22, 11), (23, 0)) ((22, 0), (21, 9), (22, 11), (22, 0)) ((22, 0), (21, 9), (22, 11), (23, 0)) ((22, 0), (22, 9), (22, 11), (22, 0)) ((22, 0), (22, 9), (22, 11), (23, 0)) ((23, 0), (22, 9), (22, 11), (22, 0)) ((23, 0), (22, 9), (22, 11), (23, 0)) ((24, 0), (23, 9), (22, 11), (22, 0)) ((24, 0), (23, 9), (22, 11), (23, 0)) ((22, 0), (23, 9), (22, 11), (22, 0)) ((22, 0), (23, 9), (22, 11), (23, 0))

0.12953492 0.12953492 0.12953492 0.12953492 0.12953492 0.12953492 0.12953490 0.12953490 0.12953490 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489 0.12953489

51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

10 10 10 10 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 73 73 73 73 77 77 77 77 77 77 77 77 85 85 85 85 89 89 89 89 93 93 93 93 97 97 97 97

((23, 0), (23, 9), (22, 11), (22, 0)) ((23, 0), (23, 9), (22, 11), (23, 0)) ((20, 0), (21, 9), (22, 11), (22, 0)) ((20, 0), (21, 9), (22, 11), (23, 0)) ((0, 0), (13, 9), (15, 11), (13, 0)) ((13, 0), (13, 9), (15, 11), (13, 0)) ((15, 0), (13, 9), (15, 11), (13, 0)) ((19, 0), (15, 9), (15, 11), (13, 0)) ((0, 0), (13, 9), (15, 11), (15, 0)) ((0, 0), (13, 9), (15, 11), (19, 0)) ((13, 0), (15, 9), (15, 11), (13, 0)) ((13, 0), (13, 9), (15, 11), (15, 0)) ((13, 0), (13, 9), (15, 11), (19, 0)) ((15, 0), (15, 9), (15, 11), (13, 0)) ((15, 0), (13, 9), (15, 11), (15, 0)) ((15, 0), (13, 9), (15, 11), (19, 0)) ((19, 0), (15, 9), (15, 11), (15, 0)) ((19, 0), (15, 9), (15, 11), (19, 0)) ((13, 0), (15, 9), (15, 11), (15, 0)) ((13, 0), (15, 9), (15, 11), (19, 0)) ((15, 0), (15, 9), (15, 11), (15, 0)) ((15, 0), (15, 9), (15, 11), (19, 0)) ((21, 0), (20, 9), (24, 11), (24, 0)) ((24, 0), (20, 9), (24, 11), (24, 0)) ((20, 0), (20, 9), (24, 11), (24, 0)) ((0, 0), (20, 9), (24, 11), (24, 0)) ((21, 0), (20, 9), (21, 11), (21, 0)) ((21, 0), (20, 9), (24, 11), (23, 0)) ((24, 0), (20, 9), (21, 11), (21, 0)) ((24, 0), (20, 9), (24, 11), (23, 0)) ((20, 0), (20, 9), (21, 11), (21, 0)) ((20, 0), (20, 9), (24, 11), (23, 0)) ((0, 0), (20, 9), (21, 11), (21, 0)) ((0, 0), (20, 9), (24, 11), (23, 0)) ((21, 0), (20, 9), (21, 11), (22, 0)) ((24, 0), (20, 9), (21, 11), (22, 0)) ((20, 0), (20, 9), (21, 11), (22, 0)) ((0, 0), (20, 9), (21, 11), (22, 0)) ((21, 0), (20, 9), (24, 11), (20, 0)) ((24, 0), (20, 9), (24, 11), (20, 0)) ((20, 0), (20, 9), (24, 11), (20, 0)) ((0, 0), (20, 9), (24, 11), (20, 0)) ((21, 0), (20, 9), (21, 11), (20, 0)) ((24, 0), (20, 9), (21, 11), (20, 0)) ((20, 0), (20, 9), (21, 11), (20, 0)) ((0, 0), (20, 9), (21, 11), (20, 0)) ((1, 0), (2, 9), (10, 11), (2, 0)) ((2, 0), (2, 9), (10, 11), (2, 0)) ((10, 0), (2, 9), (10, 11), (2, 0)) ((1, 0), (2, 9), (10, 11), (10, 0))

0.12953489 0.12953489 0.12953489 0.12953489 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.10064131 0.07078890 0.07078890 0.07078890 0.07078890 0.07078888 0.07078888 0.07078888 0.07078888 0.07078888 0.07078888 0.07078888 0.07078888 0.07078888 0.07078888 0.07078888 0.07078888 0.07078885 0.07078885 0.07078885 0.07078885 0.07078885 0.07078885 0.07078885 0.07078885 0.06455576 0.06455576 0.06455576 0.06455576

Table 4. The top 100 most absolute relevant node-level walks (found by EMP-neu). The columns show the estimated ranking by EMP-neu, the true ranking found by the exhaustive search, the neuron-level walk, and its relevance. The walk is expressed as L + 1 = 4 steps of node-neuron pairs (m, n), denoting the n-th neuron of the m-th node. The graph is from the positive class of BA-2motif dataset. Note that the walks with the same relevance share the same ranking.

18

Relevant Walk Search for Explaining Graph Neural Networks

Est. #

True #

Most absolute relevant walks

Relevance

Est. #

True #

Most absolute relevant walks

Relevance

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

1 1 1 1 5 5 5 5 5 5 5 5 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 28 28 28 31 31 31 31 31 31 37 37 37 37 37 37 37 37 37 37 37 37 49 49

((20, 0), (21, 9), (22, 11), (23, 1)) ((21, 0), (21, 9), (22, 11), (23, 1)) ((22, 0), (21, 9), (22, 11), (23, 1)) ((24, 0), (21, 9), (22, 11), (23, 1)) ((20, 0), (21, 9), (22, 11), (21, 1)) ((20, 0), (21, 9), (22, 11), (22, 1)) ((21, 0), (21, 9), (22, 11), (21, 1)) ((21, 0), (21, 9), (22, 11), (22, 1)) ((22, 0), (21, 9), (22, 11), (21, 1)) ((22, 0), (21, 9), (22, 11), (22, 1)) ((24, 0), (21, 9), (22, 11), (21, 1)) ((24, 0), (21, 9), (22, 11), (22, 1)) ((2, 0), (9, 9), (16, 11), (16, 1)) ((4, 0), (8, 9), (12, 11), (8, 1)) ((8, 0), (8, 9), (12, 11), (8, 1)) ((9, 0), (9, 9), (16, 11), (16, 1)) ((12, 0), (8, 9), (12, 11), (8, 1)) ((14, 0), (14, 9), (19, 11), (14, 1)) ((16, 0), (9, 9), (16, 11), (16, 1)) ((19, 0), (14, 9), (19, 11), (14, 1)) ((4, 0), (14, 9), (19, 11), (14, 1)) ((4, 0), (8, 9), (12, 11), (12, 1)) ((8, 0), (8, 9), (12, 11), (12, 1)) ((12, 0), (8, 9), (12, 11), (12, 1)) ((14, 0), (14, 9), (19, 11), (19, 1)) ((19, 0), (14, 9), (19, 11), (19, 1)) ((4, 0), (14, 9), (19, 11), (19, 1)) ((2, 0), (9, 9), (16, 11), (9, 1)) ((9, 0), (9, 9), (16, 11), (9, 1)) ((16, 0), (9, 9), (16, 11), (9, 1)) ((23, 0), (22, 9), (22, 11), (23, 1)) ((20, 0), (23, 9), (22, 11), (23, 1)) ((21, 0), (22, 9), (22, 11), (23, 1)) ((22, 0), (22, 9), (22, 11), (23, 1)) ((22, 0), (23, 9), (22, 11), (23, 1)) ((23, 0), (23, 9), (22, 11), (23, 1)) ((23, 0), (22, 9), (22, 11), (21, 1)) ((23, 0), (22, 9), (22, 11), (22, 1)) ((20, 0), (23, 9), (22, 11), (21, 1)) ((20, 0), (23, 9), (22, 11), (22, 1)) ((21, 0), (22, 9), (22, 11), (21, 1)) ((21, 0), (22, 9), (22, 11), (22, 1)) ((22, 0), (22, 9), (22, 11), (21, 1)) ((22, 0), (22, 9), (22, 11), (22, 1)) ((22, 0), (23, 9), (22, 11), (21, 1)) ((22, 0), (23, 9), (22, 11), (22, 1)) ((23, 0), (23, 9), (22, 11), (21, 1)) ((23, 0), (23, 9), (22, 11), (22, 1)) ((5, 0), (7, 9), (7, 11), (7, 1)) ((7, 0), (7, 9), (7, 11), (7, 1))

-0.062610321 -0.062610321 -0.062610321 -0.062610321 -0.062610313 -0.062610313 -0.062610313 -0.062610313 -0.062610313 -0.062610313 -0.062610313 -0.062610313 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097323 -0.057097316 -0.057097316 -0.057097316 -0.045452297 -0.045452297 -0.045452297 -0.045452297 -0.045452297 -0.045452297 -0.045452293 -0.045452293 -0.045452293 -0.045452293 -0.045452293 -0.045452293 -0.045452293 -0.045452293 -0.045452293 -0.045452293 -0.045452293 -0.045452293 -0.039949972 -0.039949972

51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

49 49 53 53 53 53 53 53 53 53 53 53 53 53 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85

((13, 0), (7, 9), (7, 11), (7, 1)) ((15, 0), (7, 9), (7, 11), (7, 1)) ((5, 0), (7, 9), (7, 11), (5, 1)) ((5, 0), (7, 9), (7, 11), (13, 1)) ((5, 0), (7, 9), (7, 11), (15, 1)) ((7, 0), (7, 9), (7, 11), (5, 1)) ((7, 0), (7, 9), (7, 11), (13, 1)) ((7, 0), (7, 9), (7, 11), (15, 1)) ((13, 0), (7, 9), (7, 11), (5, 1)) ((13, 0), (7, 9), (7, 11), (13, 1)) ((13, 0), (7, 9), (7, 11), (15, 1)) ((15, 0), (7, 9), (7, 11), (5, 1)) ((15, 0), (7, 9), (7, 11), (13, 1)) ((15, 0), (7, 9), (7, 11), (15, 1)) ((0, 0), (1, 9), (2, 5), (2, 1)) ((1, 0), (1, 9), (2, 5), (2, 1)) ((3, 0), (1, 9), (2, 5), (2, 1)) ((18, 0), (1, 9), (2, 5), (2, 1)) ((20, 0), (20, 9), (21, 5), (20, 1)) ((21, 0), (20, 9), (21, 5), (20, 1)) ((24, 0), (20, 9), (21, 5), (20, 1)) ((2, 0), (1, 9), (2, 5), (2, 1)) ((23, 0), (20, 9), (21, 5), (20, 1)) ((0, 0), (20, 9), (21, 5), (20, 1)) ((0, 0), (1, 9), (2, 5), (9, 1)) ((1, 0), (1, 9), (2, 5), (9, 1)) ((3, 0), (1, 9), (2, 5), (9, 1)) ((18, 0), (1, 9), (2, 5), (9, 1)) ((20, 0), (20, 9), (21, 5), (24, 1)) ((21, 0), (20, 9), (21, 5), (24, 1)) ((24, 0), (20, 9), (21, 5), (24, 1)) ((2, 0), (1, 9), (2, 5), (9, 1)) ((23, 0), (20, 9), (21, 5), (24, 1)) ((0, 0), (20, 9), (21, 5), (24, 1)) ((0, 0), (1, 9), (2, 5), (1, 1)) ((0, 0), (1, 9), (2, 5), (5, 1)) ((1, 0), (1, 9), (2, 5), (1, 1)) ((1, 0), (1, 9), (2, 5), (5, 1)) ((3, 0), (1, 9), (2, 5), (1, 1)) ((3, 0), (1, 9), (2, 5), (5, 1)) ((18, 0), (1, 9), (2, 5), (1, 1)) ((18, 0), (1, 9), (2, 5), (5, 1)) ((20, 0), (20, 9), (21, 5), (21, 1)) ((20, 0), (20, 9), (21, 5), (22, 1)) ((21, 0), (20, 9), (21, 5), (21, 1)) ((21, 0), (20, 9), (21, 5), (22, 1)) ((24, 0), (20, 9), (21, 5), (21, 1)) ((24, 0), (20, 9), (21, 5), (22, 1)) ((2, 0), (1, 9), (2, 5), (1, 1)) ((2, 0), (1, 9), (2, 5), (5, 1))

-0.039949972 -0.039949972 -0.039949801 -0.039949801 -0.039949801 -0.039949801 -0.039949801 -0.039949801 -0.039949801 -0.039949801 -0.039949801 -0.039949801 -0.039949801 -0.039949801 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394594 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591 0.037394591

Table 5. The top 100 most absolute relevant node-level walks (found by EMP-neu). The columns show the estimated ranking by EMP-neu, the true ranking found by the exhaustive search, the neuron-level walk, and its relevance. The walk is expressed as L + 1 = 4 steps of node-neuron pairs (m, n), denoting the n-th neuron of the m-th node. The graph is from the negative class of BA-2motif dataset. Note that the walks with the same relevance share the same ranking.

19

Relevant Walk Search for Explaining Graph Neural Networks Table 6. Statistics of the datasets. BA-2 MOTIF MUTAG M UTAGENICITY # OF E DGES ( AVG ) # OF N ODES ( AVG ) # OF G RAPHS

25.48 25.00 1000

19.79 17.93 188

17.79 16.90 4337

G RAPH -SST2

I NFECTION

19.40 10.20 70042

3991.30 1000 100

F.1. BA-2motif BA-2motif (Luo et al., 2020) is a synthetic dataset of graphs that are built by attaching one of two different motifs (either a house or a circle shape) to a random graph, which is generated by the Barabási-Albert (BA) model. The prediction task is to classify the graphs according to the motif type. We trained a GIN model with 3 layers, with a 2-layer multi-layer perceptron as the combine function in every GIN block. The activation function we use throughout the model is ReLU. The nodes’ initial embedding is single value 1 (N (0) = 1), and the first 2 GIN blocks transforms the features into 20-dimensional and the last block transforms the feature into 2 dimensions. In the last layer we do a sum pooling across all node features to get a vector that represents the whole graph, and transform it to class probabilities by a softmax function. We trained the model with the SGD optimizer with a decreasing learning rate γ = 0.00001/(1.0 + (epoch/epochs) for 5000 epochs. The dataset consists of 1000 samples (500 for each class). We train the model with a set of 400 positive and 400 negative samples, and use the rest as test set. The test accuracy is 100%. F.2. MUTAG MUTAG (Debnath et al., 1991) is a molecule dataset. The molecules are represented as graphs of atoms being nodes and chemical bonds being edges. The initial node features are one-hot vectors of atom types. The samples are labelled as mutagenic and non-mutagenic. For this dataset we apply a 3-layered GIN model, with 2-layer MLP as the combine function in each GIN block. The input node feature dimension is 7, and the output dimension of first 2 GIN blocks is 128, and the final block transforms the feature into 2 dimensions. The readout function is sum over all nodes followed by a softmax function. The train set consists of 108 samples with half positive and half negative, and we use the rest samples as the test set. We trained the model with SGD optimizer for 1500 epochs, and the learning rate γ = 0.0005/(1.0 + (epoch/epochs). The test accuracy is 85.00%. F.3. Mutagenicity Mutagenicity (Kazius et al., 2005) is another bigger dataset for mutagenic and non-mutagenic molecules, and contains larger variety of types of mutagenic groups. The model’s input feature size is 13, and the rest settings are the same as used in MUTAG model. The train set has 3096

Figure 11. Precision-recall curves of AMP-ave for the top-K ∗ node-level walks on MUTAG (top) and Graph-SST2 (bottom).

20

Relevant Walk Search for Explaining Graph Neural Networks

samples with half positive and half negative, and the rest are used as test set. We trained the model with Adam optimizer for 25 epochs, and the initial learning rate γ = 0.00005. The test accuracy is 83.16%. F.4. Graph-SST2 Graph-SST2 (Yuan et al., 2020b) is a dataset of texts in the parse tree form, which is also represented as graphs. The node features are 768-dimensional word embedding vectors, which are pretrained and provided by the authors. The model is built with a node feature embedding part and a following 3-layer GCN. The input feature dimension is 768, and in the middle layer of GCN the output dimension is 20. We downloaded the dataset from Yuan et al. (2020b) and used their dataset split. We trained the model with Adam optimizer for 50 epochs, and the initial learning rate γ = 0.0001. The test accuracy is 89.40%.

G. Oracle Predictors for Infection Dataset We call oracle who has the complete information about data generation process, and therefore provides predictions with best possible accuracy. Since the analytic expressions of the predictive probabilities for the SI model are intractable, we estimate the probabilities by Monte Carlo sampling. Assume that we fixed the parameters of the SI model, and drew a graph and initial carriers, for which we will compute the oracle predictors. We simulate the infection process Q = 1000 times and record the results. We use a counter x(m) to record how many times the node m was infected after L time steps. We also use a counter y(c(m) ) to record how many times a particular infection chain c(m) ∈ C (m) occurred. Here C (m) denotes the set of possible infection chains from one of the initial carriers to the target node m. With those records, we can estimate the following probabilities: x(m) , Q y(c(m) ) P(Infection chain c(m) will occur) ≈ . Q P(Node m will be infected) ≈

(20) (21)

The estimators above converge to the true probabilities as Q → ∞. The oracle infection predictor based on Eq.(20) gives an accuracy upper-bound for any machine learning predictor, while the oracle infection chain predictor based on Eq.(21) gives an upper-bound of the possible infection chain detection accuracy. We can also obtain the set of possible infection chains by collecting chains such that Eq.(21) is positive.

H. Heuristics to Find the Most Relevant Walks based on Edge-IG We rely on a natural assumption—the edges of which the most relevant walks consist should be relevant—and build the following heuristics. We first sort the edges in descending order of the relevance scores given by Edge-IG. Then, we take e edges (m, m′ )k , k = 1, · · · , K e with their relevance scores R(m,m′ ) , find all possible walks they can form, and the top-K assign each walk a relevance score. Note that a walk can have any length no larger than L + 1. For a walk [m1 , · · · , ma ], we assign a relevance score in two way:

sum: R[m1 ,··· ,ma ] =

a−1 X

R(mi ,mi+1 ) ,

i=1

prod: R[m1 ,··· ,ma ] =

a−1 Y

R(mi ,mi+1 ) ,

i=1

e = 25 in the main text. Note that these heuristics which respectively correspond to Edge-IG sum and Edge-IG prod with K are compatible with all edge-level explanability methods, including GNNExplainer and PGExplainer, which however are incomparably slow. 21

Relevant Walk Search for Explaining Graph Neural Networks

I. More Samples for Qualitative Visualization I.1. Explaining model predictions on Mutagenicity In Figure 12, we give 4 further examples of molecule explanations, with two of them mutagenic and two non-mutagenic. In the first mutagenic molecule, our method successfully finds the mutagenic NO2 group within the top-10 walks, while Node-IG and Edge-IG only highlight partially the NO2 and wrongly give the carbon or C-N bond a negative relevance. GNN-LRP with all walks gives information of some non-mutagenic structures, but they are not as important as the mutagenic group that our method finds much faster. In the second mutagenic molecule, our method identifies the OH substituent of the aromatic ring, while Edge-IG wrongly identifies the C-O bond as non-mutagenic. Node-IG is successful in identifying the real mutagenic structure, but wrongly identifies the nitrogen atom as mutagenic. In the first non-mutagenic molecule, our method finds the C-N bonds, which are chemically stable and therefore indicate non-mutagenicity. Node-IG highlights all atoms, which is not wrong, but gives no specific information. In the second non-mutagenic molecule, our method identifies the C subsituents of the aromatic rings, which lead to a chemically stable structure. However, Edge-IG highlights all edges and it’s not clear if aromatic bond or the aromatic C structure is the evidence of non-mutagenicity.

AMP-ave top-10

GNN-LRP all

Node-IG

Edge-IG

+

+

—

—

Figure 12. Heatmaps of different explanation methods of 4 molecules from the Mutagenicity dataset (+: mutagenic, -: non-mutagenic).

22

Relevant Walk Search for Explaining Graph Neural Networks

I.2. Explaining model predictions on Graph-SST2 In Figure 13, we provide four further examples for parse tree explainations. Two of them with positive and two with negative sentiment. In the first positive sentiment sample, our method finds the most relevant part “the value and respect”, which is in this sentence most evident for the positive sentiment of the movie-review. When reading the sentence it is noticable that the last words “epic cinema” also give rise to a positive prediction, yet overall less than “the value and respect“. In the heatmap we see that our method decides for the most relevant subsentence and, with only 10 most relevant walks, leaves the less relevant parts out of scope. Yet, we want to highlight that this is not a limitation of our method. Since, when we increase the number of top-K walks, we would obtain other less relevant features in the parse-trees as well and finally converge with K → ∞ to the heatmap of GNN-LRP. We see that the baseline methods also provide a clear idea of what is relevant in the input graph, yet they are not able to distinguish comparably clear what is most relevant. In the second positive sentiment sample, we can say by reading the sentence that all words except “and” are relevant. From the heatmaps we see that our method identifies all of them with focus on “arrive” and “stay late”. Notably, one of the top-10 walks goes through the four relevant words, showing our higher-order method’s superiority in capturing the node interactions. On the opposite side, Node-IG wrongly identifies “stay” and Edge-IG wrongly identifies “arrive”-“stay” as evidence for negative sentiment. In the first negative sentiment sample, our method finds the most relevant part “altogether too slight”, which is what we expect to be evident for a negative sentiment. Node-IG highlights “slight“ and “called“ to be most evident, which is partly useful, but does not give sufficient intuition for this sentence. Edge-IG also highlights the edges between the words ”altogether”, ”slight”, ”too” and ”called”, which seems reasonable for the prediction task. Yet, the connection between ”called” and ”kind” also seems quite relevant, which is more confusing here than enlightening. For the GNN-LRP result we can see that visualization all words can make it harder to tell which part of the sentence is more or less relevant, by just looking at the heatmaps. In the second negative sentiment sample, our method identifies the words “because” and “acts goofy”, which are strong evidence for negative sentiment. If we plot all walks, the most highlighted part becomes “goofy” and “time”, which is less intuitive for human. Node-IG and Edge-IG focus on the wrong parts, leaving the word “goofy” with only small relevance scores.

23

Relevant Walk Search for Explaining Graph Neural Networks

AMP-ave top-10

GNN-LRP all

Node-IG

Edge-IG

+

the value and respect for the term epic cinema

+

arrive early and stay late

—

altogether too slight to be called any kind of masterpiece

— because he acts so goofy all the time

Figure 13. Explanations of parse trees from Graph-SST2 (+: positive sentiment, -: negative sentiment).

24