GOAt: Explaining Graph Neural Networks via Graph Output Attribution
Authors: Shengyao Lu
Keith G. Mills
Jiao He
Bang Liu
Di Niu
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Networks
Explainability
Interpretability
Local-level explanation
Instance-level explanation
Primary area: general machine learning (i.e., none of the above)

Abstract: Understanding the decision-making process of Graph Neural Networks (GNNs) is crucial to their interpretability. Most existing methods for explaining GNNs typically rely on training auxiliary models, resulting in the explanations remain black-boxed. This paper introduces Graph Output Attribution (GOAt), a novel method to attribute graph outputs to input graph features, creating GNN explanations that are faithful, discriminative, as well as stable across similar samples. By expanding the GNN as a sum of scalar products involving node features, edge features and activation patterns, we propose an efficient analytical method to compute contribution of each node or edge feature to each scalar product and aggregate the contributions from all scalar products in the expansion form to derive the importance of each node and edge. Through extensive experiments on synthetic and real-world data, we show that our method not only outperforms various state-of-the-art GNN explainers in terms of the commonly used fidelity metric, but also exhibits stronger discriminability, and stability by a remarkable margin.

Published as a conference paper at ICLR 2024
GOAr: EXPLAINING GRAPH NEURAL NETWORKS VIA GRAPH OUTPUT ATTRIBUTION
Shengyao Lu', Keith G. Mills', Jiao He², Bang Liu?, Di Niu
'Department of Electrical and Computer Engineering, University of Alberta Kirrn AI Algorithm & Solution, Huawei DIRO, Université de Montréal & Mila (shengyao, kgmills flm, dniujeua he jia4 @huawei. com, bang. 1 Liu eeuiuuuuomnn umwntreal.cc..
ABSTRACT
Understanding the decision-making process of Graph Neural Networks (GNNs) is crucial to their interpretability.. Most existing methods for explaining GNNs typically rely on training auxiliary models, resulting in the explanations remain black-boxed. This paper introduces Graph Output Attribution (GOAt), a novel method to attribute graph outputs input graph features, creating GNN explana- tions that are faithful, discrininative, as well as stable across similar samples. By expanding the GNN as a sum of scalar products involving node features, edge fea- tures and activation patterns, we propose an efficient analytical method to compute contribution of each node or edge feature to each scalar product and aggregate the contributions from all scalar products in the expansion form to derive the impor- tance of each node and edge. Through extensive experiments on synthetic and real-world data, show that our method not only outperforms various state-of- the-art GNN explainers in terms of the commonly used fidelity metric, but also exhibits stronger discriminability, and stability by remarkable margin. Code be found at: [https:/ com/ sluxsz/GOAt
INTRODUCTION
Graph Neural Networks (GNNs) have demonstrated notable success learning representations from graph-structured data in various fields (Kipf & Welling. 2017: Hamilton et all 2017 Xu et all 2019). However, their black-box nature has driven the need for explainability, especially in sectors where transparency and accountability
essential, such finance (Wang et all 2022h, health- care (Amann et al. 2020), and security (Pei et all, 2020). The ability to interpret GNNs can provide insights into the mechanisms underlying deep models and help establish trustworthy predictions.
Existing attempts to explain GNNs usually focus on local-level or global-level explainability. Local-
level explainers (Ying et al. 2019 Luo et al.. 2020:
Schlichtkrull al.) 2021 Vu & Thai, 2020
Huang et al., 2002; Lin et al_
2021: Shan et all 2021: Bajai et al. 2021) typically train a secondary
model identify the critical graph structures that best explain the behavior of a pretrained GNN for
specific input instances. Global-level explainers (Azzolin et all (2023: Huang et al] (2023) perform prototype learning or random walk on the explanation instances to extract the global concepts or counterfactual rules over multitude of graph samples. While global explanations can be robust, local explanations are more intuitive and fine-grained.
In this paper, we introduce a computationally efficient local-level GNN explanation technique called Graph Output Attribution (GOAI) to overcome the limitations of existing methods. Unlike meth- ods that rely on kack-propagation with gradients (Pope et all, 2219: Baldassarre & Azizpour, 2019 Schnake et all 1021: Feng et all, 2022) and those relyinig on typer-parameters or training complex black-box models (Luo et all 2020 Lin et al. (2021 Shan et all 2021] Bajaj et al., 2021). ap- proach enables attribution of GNN output to input features, leveraging the repetitive sum- num-product structure in the forward pass of a GNN.
Given that the matrix multiplication in each GNN layer adheres to lincarity properties and the acti- vation functions operate element- wise, GNN can be represented in expansion form as sum of

---

Published as a conference paper at ICLR 2024
scalar product terms, involving input graph features, model parameters, as well activation patterns that indicate the activation levels of the scalar products. Based on the notion that all scalar variables X, in scalar product term g X2 ......... Xx contribute equally to g. where e is constant, can attribute each product term to its corresponding factors and thus to input features, obtaining the importance of each node edge feature in the input graph to GNN outputs. We present case stud- ies that demonstrate the effectiveness of our analytical explanation method GOAr on typical GNN variants, including GCN, GraphSAGE, and GIN.
Besides the fidelity metric, which is commonly used to assess the faithfulness of GNN explana- tions, we introduce two new metries to evaluate the discriminabiility and stability of the explanation. which are under-investen indessiiveet by prior literature. Discriminability refers to the ability of explana- tions to distinguish between classes, which is assessed by the difference between the mean expla- nation embeddings of different classes, while stability refers to the ability to generate consistent explanations across similar data instances, which measured by the percentage of data samples covered by top-k explanations. Through comprehensive experiments based on on both synthetic and real-world datasets along with qualitative analysis, we show the outstanding performance of our proposed method, GOAr, in providing highly faithful, discriminative, and stable explanations for GNNs, as compared to a range of state-of- sate-of-the-ar the-art methods.
2 PROBLEM FORMULATION
Graph Neural Networks. Let G (V,E) be a graph, where V = {u1, U2...., UN) denotes the set of nodes and & V> V denotes the set of edges. The node feature matrix of the graph is represented by X E RNxdd and the adjacency matrix is represented by A E (0, 1)NxN such that A.j = if there exists edge between nodes e; and uy. The task of GNN is to learn a function f(G). which maps the input graph G to a target output, such as node labels, graph labels, or edge labels. Formally speaking, for given GNN, the hidden state h, of node Uú its layer I can be represented as:
h (1) COMBINE {n.-", AGGREGATE ((N9-") VV, Vus E AGG))
(1)
where Mr represents the set of neighbors of node U/ in the graph. COMEBINE" is a COM- BINE function such as concatenation (Hamilton et all (017), while AGGREGATE (.) are AG- GREGATE functions with aggregators such ADD. We focus on GNNs that adopt the non-linear activation function ReLU in COMBINE or AGGREGATE functions.
Local-level GNN Explainability. Our goal is to generate faithful explanation for each graph instance G = (V,E) 8) by identifying a subset of edges 5 C E, which are important to the predic- tions, given GNN f(-) pretrained on of graphs G. We highlight edges instead of nodes as suggested by (Faber et al. 1) that edges have more fine-graince information than nodes while giving human- undersanddaele explanations like subgraphs.
METHOD
The fundamental idea of our approach can be summarized as two key points: i) Equal Contribution of product terms; ii) Expanding the output representation to product terms. Before diving into the mathematical definitions, we briefly describe them by toy examples as following.
Equal Contribution. Given a product term = 10.41 where the variables A11 A12
Ag3 indicate that all three edges exist, resulting in 10. If any of the edges is missing, i.e., at least one of A, A12, A23 is 0. then = 0. This fact implies that the presence of all edges is equally essential for the resulting value of 0. Therefore, each of the three edges contributes 1/3 to the output, resulting in an attribution of 10/3.
Expand the output representation. The output matrix a GNN can be described as the outcome of a linear transformation involving the input matrices and the GNN parameters. Since the GNNs are pretrained, the parameters W, B are fixed, hence can be treated as constants. As a result, each element within the output matrix can be represented entries from the inputs. Consequently, we can determine the attribution of an edge, by summing its contribution across all the scalar products in which it participates. For example, if the expansion
the sum of scalar products that involve
2

---

Published as a conference paper at ICLR 2024
form of an element in the output matrix is M13 10A11 + A11 + 11112422114 A13. then the attribution of A11 to V1s is 10/3 + 8/3 = 6 since A11 does not participate in the term 113
The rest of this section begins by presenting our fundamental definition of equal contribution in a product term. Then, mathematically present GOAr method for explaining typical GNNs, fol- lowed by a case study on GCN (Kipf & Welling, (017)). Additional case studies of applying GOAr GraphSAGE (Hamilton et al. 2017) and GIN (Xu al. 2019) included in Appendix and The code implementing our algorithm is included in the Supplementary Material of our submission.
3.1 EQUAL CONTRIBUTION
Definition (Equal Contribution). Given a function g(X) where X {X1..... 3 represents M variables, we say that variables X; and X3 have equal contribution to function g at (I), with respect to the base manifold at (xr,, x²)) ) if and only if setting X; = Tz. = z' and setting X, = x X3 = 2j yield the same manifold, i..,
9x 9x (X (XX, (x,, 9x, -ni,, xx,(x,,,,))
for any values of X excluding X; and Xj.
Lemma (Equal Contribution in a product). Given a function g(X) defined as g(X)
b " Xt. where b is constant, and X [X1,..., XM3 represents M uncorrelated variables. Each variable Xş is either O or Ti, depending on the absence or presence of certain featuin Then,
all the variables in X contribute equalty g(X) at [21...., with respect to [O.....0.. 0).
Proofs of all Lemmas and Theorems can be found in the Appendix. Since all the binary variables have equal contribution, we define the contribution of each variable X to g(X) b blI Xx for all 1,..., M, as
b bI iE NI
Ix,
(2)
M
3.2 EXPLAINING GRAPII NEURAL NETWORKS ATTRIBUTION
A typical GNN KKip & Welling, 2017: Hamilton et all 2017: Xu et al. 2019) for node or graph classification tasks usually comprises 2-6 message-passiigg layers for learning node or graph repre- sentations, followed by several fully connected layers that serve as the classifier. With the hidden state !1 of node i; the (-th message-passing layer defined as Equation (.. generally have the hidden state H (!) of a data sample as:
H o (8 (()+ H ( (H²U-))).
(3)
where A is the adjacency matrix, e refers the self-loop added to the graph if fixed 1, other- wise it is learnable parameter, a-)) is the element wise activation function, Φ( and (T() can be Multilayer Perceptrons (MLP) or linear mappings, À E {0, }} determines whether a concatenation is required. If the COMBINE step of a GNN requires a concatenation, we have À = and ( = 1; the COMBINE step requires a weighted sum, we have e!)) set trainable and = 0. Alternativel,, Equation 3 can be expanded to:
H = AH
W (1) + 1(-
W (1)
+ +XH (1
w
(4)
where K, Q refer to the number of MLP layers in (.)(.) and (.),., and W and W are the trainable parameters in (0)) and (1)
Given certain data sample and pretrained GNN, for an element-wisg activation function we can define the activation pattern as the ratio between the output and input the activation function:
Definition (Activation Pattern), Denote H and H as the hidden representations before and after passing through the element-wise activation function at the 1-th layer, we define activation
3

---

Published as a conference paper at ICLR 2024
pattern p() for given data sample
TH #
P
0,
otherwise
where p( 1.j is the element-wise activation pattern for the j-th feature of i-th node at layer I.
Hence, the hidden state H at the 1-th layer for a given sample can be written as
H = p() @
AH
W
II W + AH 1) II 5
(5)
where @ represents element- multiplication. Thus, expand the expression of each output entry in a GNN f(A, X) into a sum scalar products, where each scalar product the multipli- cation of corresponding entries in A, X, W, and P in all layers. Then each scalar product can be written as
2 == C. (p()) (
p(t)
(Ple ... plecss-11) P
aLo.
(6)
(ALL)
A(1)
Xi.s
(W(t) B1o.31
w.ll) 810.811)
(Wree) W "10m"1 yaro.mar
010.0011
a10,0n)
where C is a constant, C2 refers to the k-th layer of the classifier, (avo- an1). (Bio, 811), (Noo 711) are (row, column) indices of the corresponding matrices at layer l.
classifier with M MLP
layers, only (M- 1) layers adopt activation functions. Therefore, we do not have p(()) in Equation (6. For scalar products without factors of A, all A's are considered as constants equal to 1 in Equation (6). Since the GNN model parameters are pretrained and fixed, we only consider A, X, and all the terms as the variables in each product term, where A is the dominant one as we explained in Section
Lemma 4 (Equal Contribution variables in the GNN expansion form's 's scalar product). For sealar product term z in the expansion form of a pretrained GNN f(). when the number of nodes N is large, all variables in have equal contributions to the scalar product
For the purpose of theoretical analysis, in the lemmas, take the assumption that there are large number of nodes in the graphs. We demonstrate later the experiments that "a large number of nodes" is not required in practical application of GOAt.
Hence, by Equation 2 we can calculate the contribution Iz(2) of a variable v (i.e., an entry in A, X and P matrices) to each scalar product (given by Equation (6) by:
(2)
(7)
V(=)
where function V--) represents the set of variables in its input, and [V(=)] denotes the number of unique variables in z, e.g., V(z²y) = fur y). and [V(x²y)] 2.
Similar to Section 3.1 entry (A, X) of the output matrix f(A, X) can be expressed by the sum of all the related scalar products as
f (A, Σ C. (p())
110..n ... p(L)
(plcy)
(()) Pmi
(1) Amp.an
Ammaz
(8)
XXas
(w:
910.811 ... w(L)) #Lo.see)
(w(eg) ... W
where summation is over all possible (am. a11). (8to, B11), (Yo. 71,, for message passing layer = 1...., L or classifier layer / = 1, 1,..., M, well as all i, indices for X. By summing up the contribution each variable u among the entries in the A, X and P's in all the scalar products in the expansion form of fm.n()) (-), we can obtain the contribution of to fm. (-) as:
[o(fm.a()))
(9)
[v(2)]
in f'm (-) that contain
4

---

Published as a conference paper at ICLR 2024
Theorem 5 (Contribution of variables in the expansion form of a pretrained GNN). Given Equations (7) and (9. for each variable v (i.e., an entry in A, X and P matrices), when the number of nodes N is large, can approximate Iylfm, (.) by:
O
((fma())) i Jon. that contain v Epin O(p,z)
Σ
(10)
where O(v, 2) denotes the number of occurrences of v among the variables of
Recall that [V(2) stand for the number of unique variables z. Hence the total number of occur- rences of all the variables Epin= O(p, z) is not necessarily equal to [V()).. For example, if all of
(Aaio.. (Aaio.a.:.... Auto.ar. in unique entries in A, then they can be considered as L indepen- dent variables in the function representing z. If two of these occurrences of variables refer to the same entry in A, then there are only (L - 1) unique variables related to A.
Although Theorem 3 gives the contribution each entry in A, X and P's, we need to further at- tribute P's to A and X and allocate the contribution of each activation pattern P(t) to node features X and edges A by considering all non-zero features in X, of node vo and the edges within m hops of node Va. as these inputs may contribute to the activation pattern a.6 However, determining the exact contribution of each feature that contributes a.b is not straightforward due to non-linear ac- tivation. We approximately attribute all relevant features equally to pl() That is, each input feature that has nonzero contribution to p(7) will share an equal contribution of I p(r) (fm.n()))/
where VV (P(22) denotes the number of distinct node and edge features X and contributing to Pa.b- which exactly all non-zero features X₂ of node ta and the adjacency matrix entries within r hops of node va- Finally, based on Equation (IO), we can obtain the contribution of an input feature in X, A of graph instance the (m, n)-th entry of the GNN output f(-) as:
Ppie (fm.(())
{.)m,,))) = Io(sm,o()))
Σ
(1I)
(V(P())
p(r) in fmin (-), with in p(r)
where v is an entry in the adjacency matrix A or the input feature matrix X, p(r) denotes an entry a.b in all the activation patterns. Thus, we have attributed f(-) to each input feature of a given data instance.
Our approach meets the completeness axiom, which is a critical requirement attribution meth- ods (Sundararaian et all 2017: Shrikumar et al. 2017: Binder et all 2016). This axiom guaran- tees that the attribution scores for input features add up to the difference in the GNN's output with and without those features. Passing this sanity check implies that approach provides more comprehensive account of feature importance than existing methods that only rank the top features (Bajai all 2021: Luo et al.. 2020 [Pope al.. 2019: Ying et all 2019 Vu & Thai. 2020
Shan et al. 2021).
3.3
CASE STUDY: EXPLAINING GRAPH CONVOLUTIONAL. NETWORK (GCN)
GCNs use simple sum in the combination step, and the adjacency matrix is normalized with the diagonal node degree matrix D. Hence, the hidden state of GCN's 1-th message-passinng layer is:
O ReLU (VH(+-) + +B²).
(12)
where -= DD DA represents the normalized adjacency matrix with self-loops added. Suppose a GCN has three convolution layers and a 2-layer MLP as the classifier, then its expansion form without the activation functions ReLU(-) will be:
f(V, X)p = (2) ()) XW (2) w ((o)) + you g(D w (2) (orr)) + Bd ( + g(er) Blo2),
+ Ble (io M (e)) wlo)
w +
(13)
5

---

Published as a conference paper at ICLR 2024
(a) BA 2Motifs
Mutagenicity
NC11
0.6
0.8
0.6
Fideliyy
0.4
Fidelity
0.4
0.4
0.2
0.2
0.2
0.0
0.0
75
80
85
90
95
80
85
90
95
80
85
90
95
Average sparsity (%)
Average sparsity (%)
Average sparsity (%)
GNNExpbiter
PGW Exploiner
GWWExphiner
G0M (Ours)
PdEsplamer
Subgraphx
McSxplaise
Figure/ 1: Fidelity performance averaged across 10 runs on the pretrained GCNs for the datasets at different levels of average sparsity.
where V(I) V is the normalized adjaceney matrix in the 1-th layer's calculation. In the ac- tual expansion form with the activation patterns, the corresoondigg P(m) are multiplied when- ever there is W(() or ((m)) in scalar product, excluding the last layer W((z) and B(()), For example, in the scalar products corresponding to V(3) ((8)) X 1ppp there are eight variables consisting of four P's, one X, and three V's. By Equation (T), an ad- jacency entry Vi, itself will contribute 1 of (() of X5: (0 ( v:? v()))
8 +(V (()) 1/
+
where p(-) denotes the results with the element-wise multiplication of the corresponding activation patterns applied at the appropriate layers. After we obtain the contribution of Vi.j itself on all the scalar products, we can follow Equation (II to allocate the contribution of activation patterns to
Vi.j-
With Equation 13 we find that when both V and X are set to zeros, f(-) remains non-zero and is:
f(0. 0) p((()))p))))(aa)) + ((B))))))))))))))))))))))))))))) + B(ez),
(14)
where ((2z) is the global bias, and the other terms have non-zero entries at the activated neurons. In other words, certain GNN neurons in the 3-rd and c1-th layers may already be activated prior to any input feature being passed to the network. When we do feed input features, some of these neurons may remain activated or be toggled off. With Equation II. we consider taking all 0's of the X entries, V entries and P entries as the base manifold. Now, given that some of the P entries in GCN are non-zero when
and V set to zeros, as present in Equation (4), we will need subtract the contribution of each features these P from the contribution values calculated by Equation (II) We let P' represent the activation patterns of f(0, 0), then the calibrated contribution Teali (f(-)) of Vi is given by: =V. (/V,,,
I pr0 (f(),0))
Σ
(15)
IVP
p(r) S(0,0), with Vag pf(r)
In graph classification tasks, pooling layer such as mean- mrean-pooling added after the convolution layers to obtain the graph representation. To determine the contribution of each input feature, we can simply apply the same pooling operation as used the pre-trained GCN. As we mentioned in 2ection we aim to obtain the explanations by the critical edges in this paper, since edges have more fine-grained information than nodes. Therefore, we treat the edges as variables, while considering the node features X as constants similar to parameters W or B. This setup naturally aggregates the contribution of node features onto edges. By leveraging edge attributions, we are able to effectively highlight motifs within the graph structure.
EXPERIMENTS
We evaluate the performance of explanations on three variants of GNNs, which are GCN (Kipf & Welling 2017). GraphSAGE (Hamilton et all, 2017) and GIN (Xu et all 2019). The experiments are conducted on six datasets including both the graph classification datasets and the node classification datasets. For graph classification task, we evaluate on synthetic dataset, BA-2motifs (Luo et al. (020). and two real-world datasets, Mutagenicity (Kazius et all 2005) and NCII (Pires et al., 2015). For node classification task, we evaluate three syn- thetic datasets (Luo et all, 2020), which are BA-shapes, BA-Community and Tree-grid. We con- duct series of experiments the fidelity, discriminability and stability metrics compare

---

Published as a conference paper at ICLR 2024
(a)BA-2Motiss
(b]Mutagenicity
[c]NCI1
10
100
Discriminabiity
10f
Discriminabiltty
109
Discriminabilly bilibbllllyyy
10-4
10
10-3
10-
10-1
10-0
70
75
80
85
90
70
75
80
85
90
70
75
80
85
90
Av Average sparsity (%)
Average sparsity (%)
Average sparsity (%)
GNVExpainer
PGN Expiaieer
Subgrapex
DEGREE
Original
PGExplainer
RG Explainer
RCExplainer
G0AL (Curs)
Figure 2: Discriminability performance averaged across 10 runs of the explanations produced by various GNN explainers at different levels of sparsity, "Original" refer to the performance of feeding the original data into the GNN without any modifications or explanations applied.
(aJGNNExplainer
(b/GGxxlainner
Ic/PGM-Exolalner
(dJRG-Explainer
(0 Original
(e]SubgraphX
(ARCExplainne
(gIDEGREE
(h)GOAL (Ours)
Figure 3: Visualization explanation embeddings on the BA-2Motifs dataset. Subfigure (i) refers to the visualization of the original embeddings by directly feeding the original data into the GNN without any modifications or explanations applied.
method with the state-of -ot-----tttt-tttt methods including GNNExplainer Ying et all 2019). PGEx- plainer (Luo et al.. (202)), PGM- -MMMx-iaiieer (Vu & Thail 2020). SubgraphX (Yuan et all 202 1). CF- GNNExplainer (Lucic all 2022). RCExplainer (Bajai et all 2021b. RG-Explainer (Saan et all 2021) and DEGREE (Feng et all (022). We reran these baselines since most of them are not trained on GraphSAGE and GIN. We implemented RCExplainer as the code is not publicly avail- able. As outlined in Section 2 we highlight edges as explanations as suggested by (Faber et all 2021). For baselines that identify nodes or subgraphs as explanations, we adopt the evaluation setup from (Bajaj et al. (021)). As space is limited, we will only present the key results here. Fidelity re- sults on GIN and Grap as well as the results of node classification tasks are Appendix G and Appendix M Discussions on the controversial metrics such as accuracy are also moved to the [ppendix[
Fidelity (Pope et all. 2019 Yuan et al., 2022: Wu et all
2022: Bajai et al. 2021) is the decrease
of predicted probability between original and new predictions after removing important edges, which used to evaluate the faithfulness of explanations. It is defined fidelity(S (S,, G)) fG Similar to (Yuan et all 2022: Xie et al. 2022 Wu et all 2022 Bajaj et al. 2021).
evaluate fidelity at different sparsity levels, where spar (i, = TeT indicating the per- centage of edges that remain G after the removal of edges in S. Higher sparsity means fewer edges are identified as critical, which may have a smaller impact on the prediction probability. Figure []] displays the fidelity results, with the baseline results sourced from (Bajaj et al., 2021). Our proposed approach, GOAr, consistently outperforms the baselines in terms of fidelity across all sparsity levels, validating superior performance in generating accurate and reliable faithful explanations. Among the other methods, RCExplainer exhibits the highest fidelity, as it specifically designed for fidelity optimization. Notably, unlike the other methods that require training and hyperparameter tuning, GOAr offers the advantage of being training-free frre approach, thereby avoiding any errors across different runs.
Discriminability. It is also known discrimination ability (Bau et all 2017: Iwana all 2019). refers to the ability of the explanations to distinguish between the classes. We define the dis- criminability between two classes e₁ and d2 as the I.2 norm of the difference between the mean values of explanation embeddings ng the two classes: discriminabblityyl...co
=
No Eiecy (1()) 1 No, Ejece (1(1))
where No₃ and Noz refer to the number of data samples
7

---

Published as a conference paper at ICLR 2024
(a]BA-2Motifs
[b]Mutagenicity
(c)NC11
100
80
(%%)
40
Coverage
60
40
20
20
3
7
5
105
205
305
405
505
5
105
205
305
405
505
Top motifs (k)
Top k motifs (K)
Top k motils (k)
PGM--aapeitte Explainer
Subggappix RCExpblnnr
PGExplonnrr
GOM (Duns)
Figure 4: Coverage of the top-k explanations across the datasets.
in class e₁ and C2. The embeddings ( used for explanations are taken prior to the last-layer clas- sifier, with node embeddings employed for node classification tasks and graph embeddings utilized for graph classification tasks. In this procedure, only the explanation subgraph S is fed into the GNN instead of G. We show the discriminability across various sparsity levels on GCN, as illus- trated in Figure When we evaluate the discriminability, we filtered out the wrongly predicted data samples. Therefore, only when GNN makes a correct prediction, the embedding would be included in the discriminability computation. Due to the significant performance gap between the baselines and GOAI, a logarithmic scale is employed. Our approach consistently outperforms the baselines in terms of discriminability across sparsity levels, demonstrating its superior ability to generate accurate and reliable class-specifis explanations. Notably, at sporsity 0.7, GOAr achieves higher discriminability than the original graphs on the BA-2Motifss and NCII datasets. This indicates that GOAr effectively reduces noise unrelated to the investigated class while producing informative class explanations. Furthermore, we present scatter plots to visualize the explanation embeddings gener- ated by various GNN explainers. Figure B showcases the explanation embeddings obtained from different GNN explaining methods on the BA-2Motifs dataset, with sparsily = 0.7. More scatter plots on Mutagenicity and NCI1 and can be found in the Appendix ??. The explanations generated by GNNExplainer fail to exhibit class discrimination, as all the data points are clustered together without any distinct separation. While some of the Class explanations produced by PGExplainer, PGM-Explainer, RG-Explainer, RCExplainer, and DEGREE are noticeably separate from the Class 0 explanations, the majority of the data points remain closely clustered together. As for SubgraphX, most of its Class explanations are isolated from the Class 0 explanations, but there is a discernible overlap between the Class and Class O data points. contrast, our method, GOAI, generates ex- planations that clearly and effectively distinguish between Class 0 and Class 1, with no overlapping points and a substantial separation distance. highlighting the strong discriminability of our approach.
Stability of extracting motif's. As will later show in Section ??, it is often observed that datasets contain specific class motifs. For instance, in the BA-2Motifss dataset, the Class motif cxhibits a "house" structure. To ensure the stability of GNN explainers in capturing the class motifs across di- verse data samples, we aim for the explanation motifs to exhibit relative consistency for data samples with similar properties, rather than exhibiting significant variations. To quantify this characteristic, we introduce the stability metric, which measures the coverage of the top-k explanations across the
dataset: stability Es.estuph Ns: where the explanations S are ranked by the number of data samples that each explanation can explain, i.c., NNs,, Stopk is the set of the top-k explanations based on the rank, and N is total number of data samples. An ideal explainer should generate explanations that cover a larger number of data samples using fewer motifs. This characteristic is also highly desirable in global-level explainers, such as (Azzolin all 2003: Huang et all. 2023).. We illustrate the stability of the unbiased class as the percentage converge of the top-k explanations produced on GCN with sporsity 0.7 in Figure Our approach surpasses the baselines by considerable mar- gin in terms of the stability of producing explanations. Specifically, GOAr is capable of providing explanations for all the Class data samples using only three explanations. This explains why there are only three Class scatters visible in Figure R
Qualitative analysis. We present the qualitative results of our approach in Table D where we compare it with state-of-the-art baselines such as PGExplainer, SubgraphX, and RCExplainer. The pretrained GNN achieves a 100% accuracy on the BA-2Motifs dataset. As long as it successfully identifies one class, the remaining data samples naturally belong to the other class, leading to perfect accuracy rate. Based on the explanations from GOAr, we have observed that the GNN effectively recognizes the "house" motif that is associated with Class 1. In contrast, other approaches face difficulties in consistently capturing this motif. The Class motifs in the Mutagenicity dataset generated by GOAr represent multiple connected carbon rings. This indicates that the presence
8

---

Published as a conference paper at ICLR 2024
Table 1: Qualitative results of the top motifs of each class produced by PGExplainer, SubgraphX, RCExplainer and GOAr. The percentages indicate the coverage of the explanations.
BA Motiis
Mutagenicity
NCII
ClassO
Class
ClassO
Class
ClassO
Class I
PGiEsplainer
4.8%
1.8%
1.2%
1.3%
0.1%
0.5%
8888888 0.4%
0-0
SubgraphX
12.8%
0.2%
0.2%
0.2%
0.1%
8888 6.4%
RCExplainer
6.2%
0.4%
0.5%
0.05%
0.1
GOAL
3.8%
3.4%
93.4%
4%
3.5%
2.2%
2.2%
1,2%
3,5%
1.2%
4,3%
4.0%
of more carbon rings in a molecule increases its likelihood of being mutagenic (Class O), while the presence of more "C-H" or "O-H" bonds in a molecule increases its likelihood of being non- mutagenic (Class 1). Similarly, in the NCI1 dataset, GOAr discovers that the GNN considers a higher number of carbon rings evidence of chemical compounds being active against non-small cell lung cancer. Other approaches, on the other hand, fail to provide clear and undersaadddrt explanations.
RELATED WORK
Local-level Graph Neural Network (GNN) explanation approaches have been developed to shed light on the decision-making process of GNN models at the individual data instance level. Most of them, such as GNNExplainer (Ying et all 2019). PGExplainer eLuo al. (020). PGM-Explainer (Vu & Thai, (202). GraphLime (Huang et al. 2022). RG-Explainer (Shan et al
202th, CF-GNNExplainer (Lucic et al. 2022), RCExplainer (Baiai et al 2021). CF2 (Tan et al 2022), RelEx (Zhang et a 2021h and Gem (Lin et all 2021). TAGE (Xie at 2022),
GStarX (Zhang all (2022) train secondary model to identifyy crucial nodes, edges, subgraphs that explain the behavior of pretrained GNNs for specific input samples. Zhao et al. (2023) intro-
duces alignment objectives to improve these methods, where the embeddings of the explanation subgraph and the raw graph are aligned via anchor- based objective, distributional objective based on Gaussian mixture models, tions produced by these methods is highly dependent on hyperparameter choices. Moreover, these explainers' black-box nature raises doubts about their ability provide comprehensive explanations for GNN models. Approaches like SA (Baldassarre & Azizpour 2019). Grad-CAM (Pope et all 2019). GNN-LRP (Schnake al., 2021h. and DEGREE (Feng et al.. 2022).
objective. However, the quality of the explana-
which rely on gradient 2017) a these meth-
back-propagation, encounter the saturation problem (Shrikumar et al.
ods may generate less faithful explanations. SubgraphX (Yuan al. based techniques with pruning using Shapley values. While it can generate some high-qualic sub- graph explanations, its computational cost is significantly high due to the reliance on the MCTS (Monte Carlo Tree Search). Additionally, as demonstrated in our experiments in Section 4 existing methods exhibit inconsistencies on similar data samples and poor discriminability. This reinforces the need for our proposed method GOAI, which outperforms state-of-the-art baselines. fidelity, discriminability and stability metrics.
2021) combines perturbation-
6 CONCLUSION
We propose GOAr, a local-level GNN explainer that overcomes the limitations of existing GNN explainers, in terms of insufficient discriminability. inconsistency on same-class data samples, and overfitting to noise. We analytically expand GNN outputs for each class into a sum of scalar prod- uets and attribute each scalar product to each input feature. Although GOAr shares similar limitations with some decomposition methods of requiring expert knowledge to design corresponding explain- ing processes for various GNNs, extensive experiments on both synthetic and real datasets, along with qualitative analysis, demonstrate its superior explanation ability. Our method contributes to enhancing the transparency of decision-making in various fields where GNNs widely applied.

---

Published as a conference paper at ICLR 2024
REFERENCES
Julia Amann, Alessandro Blasimme, Effy Vayena, Dietmar Frey, and Vince Madai. Explainability for artificial intelligence healthcare: multidisciplinary perspective. BMC Medical Informatics and Decision Making, 20(1):1-9, 2020.
Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Lio, and Andrea Passerini. Global explain- ability of GNNs via logic combination of learned concepts. In The Eleventh International Con- ference on Learning Representations, 2023. 2023.
Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang- Robust counterfactual explanations on graph neural networks. Advances in Neural Information 2021.
Processing Systems,
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional net- works. International Conference on Machine Learning (ICML) Workshops, 2019 Workshop on Learning and Reasoning with Graph-Structured Representations, 2019.
David Bau, Bolei Zhou, Aditya Khosla, Aude Oliva, and Antonio Torralba. Network dissection: Quantifying interpretability of deep visual representations. In Proceedings of the IEEE Confer- ence on Computer Vision and Pattern Recognition (CVPR), July 2017.
Alexander Binder, Grégoire Montavon, Sebastian Lapuschkin, Klaus-Robert Müller, and Wojeiech Samek. Layer-wise relevance propagation for neural networks with local renormalization layers. In Artificial Neural Networks and Machine Learning-ICANd 2016: 25th International Confer- ence on Artificial Neural Networks, Barcelona, Spuin, September 6-9, 2016, Proceedings, Part II 25. pp. 63-71. Springer, 2016.
Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer. 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, pp. 332-341, 2021.
Qizhang Feng, Ninghao Liu, Fan Yang. Ruixiang Tang, Mengnan Du, and Xia Hu. Degree: Decom- position based explanation for graph neural networks. In International Conference on Learning Representations, 2022.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Chang. Graphlime: Local inter- pretable model explanations for graph neural networks. IEEE Transactions Knowledge and Data Engineering, 2022.
Zexi Huang, Mert Kosan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Global counterfactual ex- plainer for graph neural networks. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 141-149, 2023.
Brian Kenji Iwana, Ryohei Kuroki, and Seiichi Uchida. Explaining convolutional neural net- works using softmax gradient layer-wise relevance propagation. In 2019 IEEE/CVF Inter- national Conference on Computer Vision Workshop (ICCVW), pp. 4176-4185, 2019. doi: 10.1109/CCVV.2211..00
Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312-33) -200,, 2005.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. In International Conference on Machine Learning, pp. 6666-6679, PMLR, 2021.
Ana Lucic, Maartje A Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. Cf- gunexplainer: Counterfactual explanations for graph neural networks. In International Confer- ence on Artificial Intelligence and Statisties, pp. 4499-4511. PMLR, 2022.
10

---

Published as a conference paper at ICLR 2024
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information pro- cessing systems, 33:19620-19611 2020.
Xinjun Pei, Long Yu, and Shengwei Tian. Amalnet: deep learning framework based on graph convolutional networks for malware detection. Computers & Security, 93:101792, 2020.
Douglas EV Pires, Tom L Blundell, and David Ascher. pkesm: predicting small- molecule phar- macokinetic and toxicity properties using graph-based signatures. Journal of medicinal chemistry, (8(9):406-40072 2015.
Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural networks. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 10772-10781, 2019.
Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for nlp with differentiable edge masking. In International Conference Learning Representations, 2021.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schüitt, Klaus-Robert Müller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE transactions on pattern analysis and machine intelligence, 44(11):7511-75% 2021.
Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning en- hanced explainer for graph neural networks. Advances in Neural Information Processing Systems, 34:22523 225333, 2021.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International conference machine learning. pp. 3145- 3153. PMLR, 2017.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International conference on machine learning, pp. 3319-3328, PMLR, 2017.
Juntao Tan, Shijie Geng, Zuohui Fu, Yinggiang Ge, Shuyuan Xu, Yungi Li, and Yongfeng Zhang. Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In Proceedings of the ACM Web Conference 2022, pp. 1018-1027, 2022.
Minh Vu and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. Advances in neural information processing systems, 33:12225-12235. 2020.
Daixin Wang, Zhiqiang Zhang, Jun Zhou, Peng Cui, Jingli Fang, Quanhui Jia, Yanming Fang, and Yuan Qi. Temporal-aware graph neural network for credit risk prediction. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 702-710. SIAM, 2021.
Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao. Graph Neural Networks: Foundations, Frontiers, and Applications. Springer Nature, 2022.
Yaochen Xie, Sumeet Katariya, Xianfeng Tang, Edward Huang, Nikhil Rao, Karthik Subbian, and Shuiwang Ji. Task-agnostic graph explanations. Advances in Neural Information Processing Systems, 15:12077-12099 2022.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neu- ral networks via subgraph explorations. International Conference on Machine Learning, pp. 12241-12252. PMLR, 2021.
11

---

Published as a conference paper at ICLR 2024
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Shichang Zhang, Yozen Liu, Neil Shah, and Yizhou Sun. Gstarx: Explaining graph neural networks with structure-aware cooperative games. Advances in Neural Information Processing Systems, 35: 19810-19823, 2022.
Yue Zhang, David Defazio, and Arti Ramesh. Relex: A model-agnostic relational model explainer. In Proceedings of the 2021 AAAT/ACM Conference AI, Ethics, and Society, pp. 1042-1049, 2021.
Tianxiang Zhao, Dongsheng Luo, Xiang Zhang. and Suhang Wang. Towards faithful and consis- tent explanations for graph neural networks. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 2023.
A PROOF OF LEMMA
Proof. We prove by contradiction. Suppose Lemma false, then either of the following shall hold:
There exists variables (X,, X3} X, which equally contribute g(X) (z),Tz) with respect to (0, 0);
ii) There are two variables X,, X, C X that cannot have X; and Xj 0 simultaneouslyy or X; and X, = I, simultaneously.
We consider contradiction to each of the above statements separately.
According Definition 1, if there exists two variables (X,,X) X, which are not equally contribute to g(X) at (z,, with respect to 0), we should have at least one assignment of X except for X; and X, such that
9x, 9x,=a,,y=0 X X,, Xj))
(X (X,
However, since
8x X,)) (X 9x,= (X (X,, X,)) 0,
we have reached a contradiction to the first statement.
ii) As all the variables uncorrelated, the value assigned to variable has impact how we choose values for the other variables. Therefore, is possible to have X; 2; and X; = simultaneously or have X; 0 and X; æj simultaneously for arbitrary variables X; and Xy. We have reached a contradiction to the second statement.
B PROOF OF LEMMA 4
Proof. To prove Lemma 4, we first prove the following Lemma.
Lemma 6. For scalar product
in the expansion form of pretrained GNN f()), when the number of nodes N is large, it is feasible to have both U4 = 3; and Vj = or both v; = O and
V2 = 2j for all possible pairs Vi, Vj of variables in z, where Ii, Ty indicate the presence variables Vi, Vj. respectively.
Proof. We first show that in the scenario of a large number of nodes N, an arbitrary variable Pa.e among the variables in can take any value within its domain while keeping all other variables in fixed to certain values.
We begin with defining notations. For a scalar product term in the expansion of pretrained (1)
GNN f(-), we let U Abzu,az... (1) Adjoon denotes the factors involving the adjacency matrix A,
P a1otn ... p(L) plei) (()))1))
p(1)
010.811 Pazomm ... Pazortar 131 denotes the factors involving the activation
12

---

Published as a conference paper at ICLR 2024
pattern P, and C W (1)
910.9n ... 82o.821 71 ... 7aco-7ars stands for "reduced constant"
w(l)
W (01)
Wrlexr)
denoting the product of the related parameters in f(-), such that each product term can be rewritten
as UP..,GC.
The entries in an activation pattern are determined by the hidden representation before being passed to the activation function. Similar to Equation (9), the e)-th entry of the hidden representation the 1-th layer before the activation function can expressed by the sum of all the related sealar products as
a.9.p A C Σ
(
A
Agaan
w Broce
II
plm) amo Dmm deml
A(m)
W [m(m BmoaBaan
X XpmoiPmss
When of the variables in Reje constrained, the mathematical range of (1) is R. Let c(he.e (1) 2) be the sum of scalar products involving the variables in z. If the range of (h -c(heee (((hee,,)) =)) is also IR when none of the variables in it is constrained, then Pa.e can take any value within its do- main while keeping the variables in fixed to some certain values. In other words, if there is at least scalar product in (ha c(hi,e holding the variables z fixed to certain values.
Qyy
(ty 2)), then P..e can take any value within its domain while
The sum of scalar products involving X is
ohh Oy XI.) X.,) = a,8
Σ
A 2,00
(( Sta.e m=1
p(m)
(m) am
W(())
X(n
The sum of scalar products involving an arbitrary variable Aa,b in U
a,3,p
[
T-1
ch Ao,b)
Σ
Asaa
wil
Piace
II
oeman Amu,am 3mai0m1
(m)
(m)
wffm) X Xpmo.pmi
where
m=1
at least of (1(1)
A0-1) 200-1000--1
100.0 } Aa,b- A
The sum of scalar products involving an arbitrary variable Pg.s i
a.B.p Σ
1-1
ch Pan)
Acco
1- Pio.e
II
(m))
Ammo and Ama.mma
(m)) (m)
X PmmoiPoss where
m=l
on (p(1-)
p(1)
010.911 is Pg.
Then the number of scalar products in (1)
,(bc,e,)))
(h (r) cee
- -chh
(y) =)1 2 | - 1e(h X1,)) - (c(1!l) Aas)) - (1 (1-1) (1-1)-(c(hh)) Pa.n)l
where I (2) lo(hee (ice,,ii, Xis)l, lo(her (!)
(!) Aad)), lo(her Pa represents the number of scalar products in hel ol Xx.), oh Au,)), cc.b))c(hh?)) Pg,x) respectively. Hence if we can prove h
(1)
Je(hee (y) Xig)l - 1 le(he,, Aa,s) (1 1) le(hal'
Uy
(yy Pg.n)l 2 1, then we will also have
!i - o(holez)) 2)1 2 proved. That is, we should prove
( hhe 0
lo(be,
( Xx.i)l le(hee' Ao,t)l (1-1) 1)- |
(y lo(hee, Pg.n)
|
Equivalently, we should prove
le(hee ay
X1.5)l
le(he,, An.i.) -1-1)-
lo(heee Pa.t) h
+
<
|ha.
Note that the first term
lo(ha Xi.i)l
lheel
Nd.
13

---

Published as a conference paper at ICLR 2024
Je(12 .x,53l 0.
Since d 2 1 is the feature dimension of X, we have lim
Now consider the second term
1- cchace
Ry Aa,b) =1- (1N + (9N N(-2) + +... N)
N
N2
N
ND+1j
1!
1!
1!
=1-
+
11(1
1)!
N
2!(1
2)!
N3
E.(1 1)! NQ-1)
1
1
1
1 1-1
1
11N N
2!N
N
N
IIN N N
Since N >> we have limN 1000 N
0. Also, because
1
1-1
N
N
UN
EN
then have limy L- [e(h AA..WIl
O.
1ath Pu.n)),
Now we consider the third term (1 -
(1 1) lolhee, Paihll (1 (1- N'd
uy
Io(K!! Cei (P.aa)
Since N >> 1 and d 2 1, we have lim -1).
0.
le(h xx.))
For the terms on the right hand side of the inequality, since 1 lim +00 0. Hence oo
we have
Je(h AA, L.
Since 0 1, we have prove that when N is large,
(1 1).
1e( Pa.h)l [N
<
Therefore, in scenarios with a large number of nodes N, an arbitrary [
variable Pa.e in P can take any value within its domain while keeping all other variables in fixed to certain values.
If the data is properly preprocessed, feature Xi, and the unique entries in A should be uncorrelated with each other. Also, from the above proof we can conclude that when N large, any arbitrary variables in can be freely set to "absence" or "present" without affecting other variables. That is, in scenarios with a large number nodes N, it is always feasible to hold
both X 0 and Aa,b Aabs well as both Xi.j vij and Au.b = 0;
both Ag, 0 and Au,b Aa,b, by as well as both Ag, Akn and Au,b 0:
both XJ 0 and Pa. Pe.er as well as both X,,; Iij and Pa.e 0;
both Aq,b and Pa.e Pe.e, as well as both Au,b Aq,b and Pe,e 0:
both Pa.e = 0 and Pg = Pg. as well as Pa.e = Pe.e and Pg. O.
without affecting other variables in 2, where Xt,,, Aa.b, Akn Po,er Pa, refers to the variables in 2. Hence we have proved Lemma 6
Next, prove by contradiction that for all possible variable pairs (n,, 23) among the unique variables in 2, we have (V), contribute equally to z at (I), with respect to (0, 0) where 0s Iz, Uy xy means the "presence" of the variables.
14

---

Published as a conference paper at ICLR 2024
Assume there exists two variables (ve, V3) in V(2) that are not equally contribute to (2;, 23) with respect to (0, 0). Then by Definition 1, we should have one assignment of other variables in 2, such that
=V== 1y) + (Ve)))
However, since
2n =0
م,,=0,,;==, (V) 0,
have reached contradiction. Hence have proved Lemma 4.
C PROOF OF THBOREM 5
Proof. If the total number of unique variables in scalar product equals to the total number of
occurences of all the unique variables, i.e., if [V(z) = Epin= O(p, z), we will have (=)
O(v.z)+ [ Eping O'p.a' This is because when [V(2)] = Epin= 0(p,2), all the occurrences of variables are unique variables, and we have (14 = 1. Consider I,(Sm.n (-)) as the sum of two
components, which are the contribution = (.)) of v to the scalar products where [V=)] =
pine (p, holds, and the contribution ( (-)) of to the scalar products where [V(z) p (p,z) does not hold. That is,
If(f,a = I2 IN + (
We able to have multiple occurrences of X P in scalar product, but only able to have multiple occurrences of A. Considering the scalar products are bounded by a value of e, we have
NL) + N
lu(fmmn())
C. C-N++1
L!NL-1
LiN (L))OIN
2!(L 21N
L(L 1)
2!
NL
L
L
N2
N2
Since N > L, we have
lim
[p(fm,(.)) O.
N=
Therefore, when N is large, (o( = (fV== (.)) Hence, by Equation (10), we have proved O(v.z)
that when N large, (m = Exin ii fm that contain v En ins O(p,z)
D CASE STUDY: EXPLAINING GRAPH ISOMORPHISM NETWORK (GIN)
GIN adopts weighted sum at the COMBINE step, hence the hidden state of GIN's I-th layer is:
H = ( (A
(16)
where Á = A + refers to the adjacency matrix with the self- (0) is trainable scalar param- eter. If (()(.) (-) is 2-layer MIP, expanding Φ(0,, we have
( = ReLU (ReLU (1 + 10 + BBy) was - BO3") (17)
15

---

Published as a conference paper at ICLR 2024
Suppose GIN f(A has three message- pasaiing layers and 2-layer MLP as the classifier, then its expansion form without the activation functions ReLU(-) will
x) xx W
w w aas w wai M wll)
+ +
+ -
was wl()) W w worr o ih w wla)
+ xe
+ 10
/ 1 w
1 x wh we iaa (lmm
/ 1 (1) x
:h iar (radkrei
w way w way (2) Bod /h
1
(18)
1
1 (o)
w wal
A0
wf w w(a))pl
10)
w ff af ((m)p
( (
a ai w oh (()
+ 1 gd wh !h w p(w))
+ (3) f w wh ah (p(
+ 1 8 ff ff (lz) + (3) Bdd fo wof (la)ppa))
+ ldlh w woed foth w ((a)) wlo)) + Blaz)
Then similar to the case study on GCN and GraphSAGE, the activation patterns are multiplied to each of the scalar products. Although Equation 18) may appear complex, we can observe a pattern that when Á is present in a product term, the corresponding e!)) not. This observation allows us to simplify the expression by using for loops to cover all the product terms. The code of explaining GIN on the graph classification task in the package of Supplementary Material.
E
CASE STUDY: EXPLAINING GRAPHSAGE (SAMPLE AND AGGREGATE)
GraphSAGE adopts concatenation at the COMBINE step, hence the hidden state of GraphSAGE's 1-th layer is
H ReLU (AH #0-0w00 + BO))
(19)
where (' and W00v represents the trainable parameters for concatenating the node information and its neighborhood information. Suppose a GraphSAGE network (A, has three message- passing layers and 2-layer MI.P the classifier, then its expansion form without the activation
16

---

Published as a conference paper at ICLR 2024
functions ReLU(-) will be
1 ww www.pppww.........
f(A, X)p
a X w(
wiiiii a (al +
www.ww Mxx (0 100 +
an X do foo + M MX
ww M bf ae tel + wwmmmn
(20)
/ (eo ee wy Maee li off fag +
+ (
n eet (ol +
+ A lol yeo
(n) Malllll
+ B (2) (()))))))
+ B ( w + Blo) + g(a)
Then all the other steps will be identical to the case study of GCN. The code of explaining Graph- SAGE on the graph classification task is in the package of Supplementary Material.
F HANDLING BATCH NORMALIZATION LAYER
In certain cases, Batch Normalization (BN) may be applied between the message-passing layers. In this section, we will elaborate on how BN layer handled to provide explantions with GOAr. The formula of BN is
W + B, V8+
I
(21)
where is the running mean, is the running variance, E is a prefixed small value, W, B are learnable parameters. During the evaluation mode of a pretrained GNN, μ. 8, e, and B are fixed. As result, we can treat the Batch Normalization (BN) layer as linear mapping y zW(BN) (BN) while obtaining GNN explanations with GOAr, where
W(BN)
W
((BN)
B.
(22)
VO+E
V8
G FIDELITY RESULTS OF EXPLAINING GRAPHSAGE AND GIN
(a) BA-2Motifs
Mutagenicity
(c) NCIL
0.5
0.7
0.6
0.4
0.5
0.5
Rideitty
0.3
Adelity
0.4
0.4
0.2
0.3
0.2
0.1
0.2
0.1
0.1
0.0
80
85
90
95
80
85
90
95
80
85
90
95
Average sparsity (%)
Average sparsity (%)
Average sparsity (%6
GNNEsplainer PGExpaaee
PGM Explainer Explainer
-I-
Suboraptx RcExplatrer
DEGREE -f-
(Ours)
Figure 5: Fidelity performance averaged across 10 runs on the pretrained GraphSAGE for the datasets at different levels of average sparsity.
17

---

Published as a conference paper at ICLR 2024
(a) BA-2Motifs
(b) Mutagenicity
(c) NC11
0.8
0.6
0.7
Fidelity
Fidelity
Fidelity
0.4
0.6
0.5
0.2
0.2
0.4
65
70
75
80
85
90
65
70
75
80
85
90
65
70
75
80
855
90
Average sparsity (%)
Average sparsity (%)
Average sparsity (%)
GNNFxplainer PGLxplainer
PGN-Exppliierr
SubgraphX
RG- MG-Lxplainer
RCEaplaine iner
GOAL (Ours)
Figure 6: Fidelity performance averaged across 10 runs on the pretrained GIN for the datasets at different levels of average sparsity.
H STATISTICS AND IMPLEMENTATION DETAILS
The GNNs are trained using the following data splits: 80% for the training set, 10% for the validation set, and 10% for the testing All experiments are conducted
Intel@ CM i7-10700 Processor and NVIDIA GeForce RTX 3090 Graphics Card. The GNN architectures consist of message-passing layers and 2-layer classifier. The hidden dimension is 32 for BA-2Motifs, BA- BA-Shapes. BA-Community, Tree-gria and 64 for Mutagenicity and NCI1. The code is available the Supplementary Material, provided alongside this Appendix file.
Table 2: Statistics of the datasets used and the classification accuracy of the trained GNNs.
BA-
BA- Community
Tree- Grid
BA- 2Motifs
Mutagenicity
NCI1
Shapes
Graphs
1,000
4,337
4,110
Nodes (avg)
700
1,400
1,231
25
30.32
29.87
Edges (avg)
4,110
8,920
3,410
25.48
30.77
32.30
Classes
8
2
2
GCN
0.97
0.91
0.97
1.00
0.82
0.81
Test ACC
GraphSAGE GIN
1.00
0.80
0.80
0.89
0.83
I EXPLANATIONS OF NODE CLASSIFICATION
We utilize seatter plots to visually depict the explanation embeddings produced by GNNExplainer, PGExplainer, and GOAt, and compare them with the node embeddings in the original graphs. In the generated figures, set the value of lopk be 6, 7, and 14 for the BA-Shapes, BBA-Communtty and Tree-Grid datasets, respectively. In the case of BA- BA-Shapes and BA-Comm BA-Community. we only plot the nodes within the house-shape motif, as the other nodes are located far away and may not be easily discernible in terms of explanation performance.
As presented in Figure 9 the majority of the explanations on the Tree-Grid dataset generated by GNNExplainer are closely clustered together. and GOAr has fewer overlapped data points than PG- Explainer. As illustrated in Figure Z and Figure g the explanations generated by GNNExplainer and PGExplainer fail to exhibit class discrimination on BA-Shapes and BA-Com BA-Communicty datasets, as the data points are clustered together without any distinct separation. In contrast, our method, GOAr, generates explanations that clearly and effectively distinguish between classes, with fewer overlapping points and substantial separation distances, highlighting the strong discriminability of approach the node classification task.
Discussion on the AUC/Accuracy metrics. Many existing GNN explanation approaches are eval- uated using metrics such as AUC or Accuracy. These metrics compare the explanations generated by the explainers with "ground- truth" explanations that are predetermined by humans. Ground-truth explanations refer the underlying evidence that leads the correct label, rather than the prediction
18

---

Published as a conference paper at ICLR 2024
(*)GNNExplainer
[b)PGExplainer
3
3
2
2
1
0
-1
-15.0-
1.00-12.--100
10.0
-7.5
-500
225
0.0
2.5
-15.0
12.5
100.0
-7.5
55.0
225
0.0
(cIGOAt
(d) Original
-2
Po
-4
-4
-6
-25
-20
-15
-10
-5
-10
-8
-6
Class
Class
Class 3
Figure 7: Visualization of explanation embeddings on the BA-Shapes dataset. Subfigure (d) refers to the visualization of the original embeddings by directly feeding the original data into the GNN without any modifications explanations applied.
(aGGNNExplalner
(b)PGExplainer
-10
15
20
20
-30
-5
-00
-30-
-50
-5.0
-2.5
0.0
2.5
5.0
7.5
-20
-15
-10
5
(c]GOAt
(d) Original
-20
440
-20
660
-30
-40
-30
-20
-10
-30
-20
-10
Class
Class
Cless 3
Class 5
Class
Class
Figure 8: Visualization of explanation embeddings on the BA-Community dataset. Subfigure (d) refers to the visualization of the original embeddings by directly feeding the original data into the GNN without any modifications or explanations applied.
label itself. However, highlighted by (Faber et al., 202 there often be mismatch between the ground truth and the GNN. To avoid any potential misunderstandings, we have chosen to directly present scatter plots of the explanations generated by different explainers.
19

---

Published as a conference paper at ICLR 2024
(a/GNNEXplainer
(b)PGExplainer
5.0
5.0
2.5
2.5
0.0
-25
-50
-7.5
4
5
20
25
15
25
(cIGOAt
(d) Original
4
2
2
0
0
-2
-2
-4
-6
10
Class 0
Class
Figure 9: Visualization of explanation embeddings on the Tree-Grid dataset. Subfigure (d) refers to the visualization of the original embeddings by directly feeding the original data into the GNN without any modifications or explanations applied.
J TIME ANALYSIS
Table 3 presents the average running time per data sample over the six datasets used in our experi- ments on GCNs. We compared with the outstanding baselines, which are the certurbation-basee method GNNExplainer (Ying et al. (201)), decomposition based method DEGREE (Feng et all 2022), and the search-based method SubgraphX (Yuan et all 2021). Our approach is much faster than SubgraphX and GNNExplainer, and runs slightly faster than DEGREE while providing more faithful, discriminative and stable explanations as demonstrated in Section which showcases the significance of our method.
Table 3: Average running time per data sample.
BA- Shapes
BA- Community
Tree- Grid
BA- 2Motifs
Mutagenicity
NCI1
GNNExplainer DEGREF
0.65-0005s
0.78110.05s
0.7211.06s
1.1610.10s
1.43:10.03s
1.4410.09ss
0.44-10.20s
1.02++0.35s
0.37=00066
0.58+10.11s
0.83+t0.45s
0.94:+0.34s
SubgraphX GOAr (ours)
81.8+t34.99
138.8:138.3
56.7::12.1s
95.4
419.8-1655.6
541.6:+357.06
0.36:10.00s
0.50:10.00s
0.05=10.00s
0.46:10.00s
0.60:10.22s
0.83-10.39g
K ILLUSTRATIVE EXAMPLE OF GOAT
Equal contribution in each product ferm
input
f(G)
output
10A
Contribation each
An 10/3 i 8/1
App 10:3 + 11/3
A
Aua 6/3 11/3 19/3
Expand the representation sum product terms
e.g. A0p
AAniA 11ApzAgiAs
6/3
product
product
product
Figure 10: Illustrative example of GOAt.
20


Reviews:
[{"review_id": "K8aB021TmD", "reviewer": "Reviewer_cqeJ", "summary": "This paper focuses on a problem of explaining graph neural networks. Specifically, the author proposed an explaining method that lies in the category of decomposed approaches. The proposed method aims to compute the contribution of each node/edge for the final predictions. Experiments are conducted to compare with some perturbation-based explanation methods.", "questions": "Please refer to the weaknesses.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper focuses on an important problem of explaining graph neural networks. \n2. The proposed method is reasonable and technically sound.\n3. The results compared with the representative perturbation-based explainers are promising.", "weaknesses": "1. There are already a group of decomposition methods for explaining graph neural networks [1, 2]. They share very similar idea with the proposed method. However, they are not discussed in the paper. It is necessary to clarify the contributions of this work compared with these related works. \n2. In the experimental section, the decomposition methods are not compared with the proposed framework. It is suggested to add decomposition-based explainers as basslines.\n3. It is claimed that the proposed method can be faithful and also stable across similar samples. I suggest to discuss and compare with a recent work [3] that also works in both directions of GNN explainer.\n\n[1] Pope, Phillip E., et al. \"Explainability methods for graph convolutional neural networks.\" Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2019.\n[2] Schnake, Thomas, et al. \"Higher-order explanations of graph neural networks via relevant walks.\" IEEE transactions on pattern analysis and machine intelligence 44.11 (2021): 7581-7596.\n[3] Zhao, Tianxiang, et al. \"Towards Faithful and Consistent Explanations for Graph Neural Networks.\" Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining. 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "e1jheP0Rgb", "reviewer": "Reviewer_PCGE", "summary": "The paper proposes a new GNN explanation method by expanding the GNN as a sum of scalar products. The proposed method efficiently computes the contribution of each node and feature. From extensive experiments, the paper shows significant improvements over baselines and also has better stability across samples.", "questions": "Please refer to the weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The GNN explanation problem is important for decision-making.\n2. The proposed method is sound and could explain both edges and features.\n3. The proposed method significantly outperforms baselines.", "weaknesses": "1. There is no computation complexity analysis for the proposed method.\n2. It is better to have a figure to illustrate the key idea of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LQI4eEhr19", "reviewer": "Reviewer_8TnY", "summary": "This paper introduces GOAt, a novel method for GNNs by representing the output with product terms. Specifically, the authors propose an efficient analytical method to compute the contribution of each node or edge feature to each scalar product and aggregate the contributions from all scalar products in the expansion form to derive the importance of each node and edge. GOTt is shown to be applicable to different GNN architectures, including GCN, GraphSAGE, and GIN. It outperforms various SOTA GNN explanation baselines in terms of fidelity, discriminability, and stability as demonstrated through experiments on both synthetic and real-world data. The authors also provide qualitative case studies to show that GOAt can identify the most important nodes and edges in the input graph that contribute to the output prediction and that it can also detect the presence of adversarial attacks and the robustness of the GNN model.", "questions": "1. For the discriminability metric, which the class labels were used? The ground truth labels or the GNN predicted labels? In these two cases, the discriminability has different meanings. My current understanding is using the ground truth labels, but this means when GNN makes an incorrect prediction, the embedding is also included in the discriminability computation.\n\n2. I am a bit confused about how the coverage for the stability measure is computed. Can the authors explain more? Also, although coverage for BA-2Motifs is high for GOAt, it is very low on Mutagenicity and NCI1 for all methods. Any discussions about this observation?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Novelty: Explaining GNNs via output attribution is a novel approach to my knowledge.\n\n2. Effectiveness: GOAt outperforms SOTA baselines in terms of fidelity, discriminability, and stability, and case studies show GOAt can generate qualitatively meaning explanations.\n\n3. GOAt is shown to work for different GNN architectures and for both graph classification and node classification.\n\n4. Code is provided for reproducibility.", "weaknesses": "1. Given the GOAt method is relatively complex, a time complexity analysis or empirical speed evaluation helps assess its significance.\n\n2. For the newly introduced metrics, i.e., discriminability and stability, a more detailed discussion of how they are computed can help improve clarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yBMdYCg4Ma", "reviewer": "Reviewer_nBUo", "summary": "In this paper, the authors introduce  a new method for interpreting GNNs. Specifically, this method provides transparent explanations by attributing graph outputs to input features. It employs an analytical approach that expands the GNN into a sum of scalar products, which allows for efficient calculation of feature contributions. Empirical results on three well-known datasets show the effectiveness of the proposed method.", "questions": "Please refer to Weaknesses 1-5.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.Unlike previous methods that either rely on back-propagation with gradients or train complex black-box models, this method uses an analytical method based on the sum-product structure of the GNN’s forward pass.\n2. The proposed method demonstrates promising performance on synthetic and real-world data. These experiments demonstrate that GOAt outperforms existing state-of-the-art methods in several key metrics, such as fidelity, discriminability, and stability.\n3. The paper seems to be well-organized in its presentation.", "weaknesses": "1. It isunclear what limitations of previous methods the author's method can overcome, and the reasons for overcoming these limitations. It would be good to clarify these two points.\n2. Please explain why it makes sense to define each edge as an Equal Contribution.\n3. The latest methods mentioned in the Related Work: GLGExplainer and GCFExplainer, do not appear in the experiments as baselines.\n4 .The experimental datasets could be more diverse, such as including the BBBP, MNIST, and other datasets, to make the model more convincing.\n5. The reference to 'Equation(??)' in the paragraph below Equation 5 is unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)