Explanations of GNN on Evolving Graphs via Axiomatic  Layer edges
Authors: Yazheng Liu
Sihong Xie
Venue: ICLR 2025 Poster (2025)
Keywords: explainability; dynamic graphs; message flows; layeredges
Primary area: interpretability and explainable AI

Abstract: Graphs are ubiquitous in social networks, chemical molecules, and financial data, where Graph Neural Networks (GNNs) achieve superior predictive accuracy. Graphs can be
evolving, while understanding how GNN predictions respond to the evolution provides significant insight and trust. 
We explore the problem of explaining evolving GNN predictions due to continuously changing edge weights.
We introduce a layer edge-based explanation to balance
explanation fidelity and interpretability.
We propose a novel framework to address the challenges of axiomatic attribution and the entanglement of multiple computational graph paths due to continuous change of edge weights. We first design an axiomatic attribution of the evolution of the model prediction to message flows, then develop Shapley value to fairly map message flow contributions to layer edges.
We formulate a novel optimization problem to find the critical layer edges based on KL-divergence minimization. Extensive experiments on eight datasets for node classification, link prediction, and graph classification tasks with evolving graphs demonstrate the better fidelity and interpretability of the proposed method over the baseline methods. The code is available at https://github.com/yazhengliu/Axiomatic-Layer-Edges/tree/main.

Published as a conference paper at ICLR 2025
EXPLANATIONS OF GNN ON EVOLVING GRAPHS VIA AXIOMATIC LAYER EDGES
Yazheng Liu, Sihong Xie
The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China yl yliu533econne hkust-gr www..eedd....ooo .du.cn, cn, si wwwonnxieehkustt--00
www.edz..ccegegeooo edu.
ABSTRACT
Graphs are ubiquitous in social networks, chemical molecules, and financial data, where Graph Neural Networks (GNNs) achieve superior predictive accu- racy. Graphs can be evolving, while understanding how GNN predictions re- spond to the evolution provides significant insight and trust. We explore the problem of explaining evolving GNN predictions due to continuously changing edge weights. We introduce layer edge-based explanation to balance expla- nation fidelity and interpretability. We propose a novel framework to address the challenges of axiomatic attribution and the entanglement of multiple com- putational graph paths due to continuous change of edge weights. We first de- sign an axiomatic attribution of the evolution of the model prediction to mes- sage flows, then develop Shapley value to fairly map message flow contributions layer edges. We formulate novel optimization problem to find the criti- cal layer edges based on KL-divergence minimization. Extensive experiments on eight datasets for node classification, link prediction, and graph classifica- tion tasks with evolving graphs demonstrate the better fidelity and interpretabil- ity of the proposed method over the baseline methods. The code is available https///giiub..oomyyaaaengg////p Laaeenaatte-aa----eeeeeeeee Edyyeer-ddgss/tre//min
INTRODUCTION
Graph neural networks (GNNs) achieve superior performance in many graph learning tasks, such as social network modeling (Kipf & Welling 2017), molecule property prediction (Wu et al. 2018), knowledge graph embedding WWag et al. 2019a), fraud detection (Wang et al.) 2019b). and rec- ommendation systems (Ying et al.) 2018). Due to the complex message calculation, aggregation, and nonlinear update mechanisms of GNN, they are usually deep. highly nonlinear, and complex. desirable make GNN predictions transparent to humans (Ying al. 2019, Schnake et al.) 2020). For example, a user may want to know why recommendation is made by GNNs to ensure no breach of sensitive information (e.g., age and gender) (Li al.) (02T); a GNN-based rumor or spam detector should explain why an user account is suspicious (Lai & Tan 2019
In the real world. graphs are usually evolving, with in- put edge weight continuously changing (including ad- dition and deletion of edges/nodes), leading to changes in GNNs model predictions, see Figure [ For exam- ple, in rumor detection task, as new tweets or prod- uct reviews are posted over time, the edge weights are also continuous changing due to some factors such rumor dissemination speed and user interaction fre- quency. Consequently, the suspiciousness of an ac- count changes accordingly. Let Go - Gi be any two snapshots where the source graph Go evolves to the destination graph G1 with the edges weights changed continuously. Accordingly, Pr(Y Go; 0) will evolve to Pr(Y|Gr:: 0). and we aim to attribute the change in
Eecons sdge reight
Go
Evelving
D4
42
Prederke peinually
dasa liaiion
(G) (010240066 (Gi) = (0650240.1)
Lis
Piy (G) - (0307)
Pry, (G) [B6644]
Cala Scaioon
(G) (0600222) Why dinees powel chect probabilly CNils chrenge?
Pr (3302005))
Figure 1: Top: The weights of the input edges the evolution graph change continuously. Bottom: Altered weights leads the changes in GNNs predictions for node classification, link prediction, and graph classification tasks.
SShonn Xie the the corresponding author

---

Published as a conference paper at ICLR 2025
Pr(Y|G; 0) elements changed (such as input edges) in Go - G1. With this tool, decksion-makers can understand this evolution. For example, what specific rumor spread pattern changes lead to pre- diction shift.
Explanations of GNN models on evolving graphs must account for both Interpretability (Ras et al.] 2018) and Fidelity (Yuan) et al., 2020b). Interpretabillity ensures the selected key elements are easy for users understand, while Fidelity ensures these el- ements faithfully reflect shifts in model predictions. As GNNs capture complex relationships through multiple message pass- ing and aggregation steps, the explanation should also reflect these complex interaction berween nodes and edges, especially when the edge weights are changing. However, such complex evolving interactions involve comparing many node features and edges on the initial and destination graphs, making the explana- tions complicated for users to understand. Thus, there is often a trade-off between these two factors (see Figure (a)). Various GNN explanation methods have been proposed. including GN- NExplainer (Ying al. 2019), PGExxlaiinr (Luo et al.| (020). and Flow (Gui et al. 2023) to select important input edges, layer edges, or message flows, respectively. We consider three types of explanations: message flow, input edges and layer edges. For the message flow explanations, if the GNN model with ''' layers, the message flows with T + 1 nodes contain the precise com- putational process of GNN predictions, leading to the highest fi- delity (Gui et al. 2023). However, understanding message flows requires users to be familiar with the multi-layers information ag- gregation and transformation, which can lead to cognitive overload users unfamiliar with GNNs, even for the GNNs model designer. especially when node degrees are high, resulting in the worst Interpretability. For the input edges explanations, the input edges directly related to the specific graph elements, often corresponding to real-word concepts, which users find easier understand, offering the highest Interpretability. However, input edges con- tain fewer computational process of GNNs predictions, they offer the worst Fidelity. For the layer edge explanations, the layer edges capture aggregated message information used in the GNN's cal- culations compared to the input edges, leading to the higher Fidelity than input edges. Although the layer edges transmit information that has been processed through multiple layers, it is easy to understand compared with the message flow explanation, resulting in the higher Interpretability than the message flows. Figure b)) illustrates the Fidelity and Interpretability of different explanation forms.
Explanation trade off
User
Medel
Explanation
Interprelabllit
Fidelity
Explanation form
The better
Fideliyy
Measuge fowa
Repplenation
Loyer exdges
Compudatoon
sie lonu adges
Interpeaafilly
[h)
Figure 2: (a) Explanations should have high Fidelity and Interpretubility accurately repre- senting the model while remaining user-friendly. However, there often a trade off. (b) The Fidelity and Interpretability of different explanation forms.
(Anderson et al., (020) for those
For dynamic graphs, explaining the change from Pr(Y 0) to Pr(Y]G 0) has several chal- lenges: 1) To explain the changes in predicted probability, it is necessary to understand shifts in logits (the final GNN layer output before activation) between the G, and C1. These logits changes can be derived mathematically and mapped to probability shifts. However, existing methods focus on static graphs. Although the static graphs can be considered as an evolution from an empty graph (e.g. G1 evolving from the Gempuy). these methods only explain the changes in logits between Gempey and G1- They ignore the differences between Gempty and Go. leading to inaccurate contributions that fail to explain the evolution of prediction probability, as shown in Figure a). 2) To balance Interpretability and Fidelity, we provide the layer edges as explanation, requiring a mapping func- tion convert the message flows contributions into layer edges. Existing methods overlook the fact that layer edges in message flows may contribute differently. The contribution of a layer edge is influenced not only by its associated weight but also by the hidden vector of the node connected to Fairly attributing the contributions of message flows to the layer
it. See the example in Figure edges is also the key challenge. 3) To ensure the explanations should be understandable to humans, it is important to select small number of layer edges. The layer edges selected by the top- K in the existing methods may not faithfully represent the model's ' behavior, as demonstrated in the case shown in Figure C(c. Selecting the small number of layer edges that provide faithful explanation of the model is also the challenge.
2

---

Published as a conference paper at ICLR 2025
Static graph
XLO Bupunc
Calculate contribution
Map contribution
Select
Gerpyy
Missagg Tow
P.
Scar
Average Lundton
Score
11A
Tep-1
Explen
O C 3
0
Average Lundin
H4
140
Dynamic
Fol
Fat
08 K
x/ (Carpt
odge Score, Target expiah
Q4
Lagar edge
Spom
(2.0.%) X-Ix [c]
A
Computational grephs
The dlaaed
Message floes
mexaage contetation mubic
2
Snopley
1
0.5
-0.5
-1
-1.
( - [ (32.) Py(G)) (66024011
0.1
0.1
0.5
05
-2
-8.0
-1g
(G) (G)))) (G)))
(C - (BLASAB6))
-5,-804 x/,0) 8yG0) (200 2]
surmarion--o- properiy
C.-AAr
Blcessy of thepity
500
-03
-33
Figure 3: Top: The steps for selecting important layer edges as explanations on static graphs in the existing methods. Middle: The challenges of using the existing methods to explain the evolution of prediction probabil- ity. (a) The existing methods can only explain the changes in logits between Gempey and G1, but cannot explain the changes in logits between G1 and Ga- (b) Layer edges may contribute differently not equally. (c) The top- K selection cannot faithfully explain the prediction. Bottom: The proposed method explain the cvolution of prediction probability. (d) calculate the contribution message flows, ensuring the summation-to- property. (e) We use Shapley value to attribute the contribution of message flows to layer edges, preserving the summation-to-de to-eelttt----etaaaaaaa property. (l) Leveraging the summation-to-dell property, we derive KL divergence and formulate optimization problem to faithfully select important layer edges explanations.
To address these challenges: 1) We formula the changes in hidden vectors on Go and G1 and apply the multipliers and chain rule of DeepLIFT to assign the changes in logits to message flows, en- suring that their contributions follow the summation-to-delta property. 2) We frame the mapping of message flows to layer edges as an allocation problem. Then, we apply the Shapley value to fairly attribute contributions, ensuring that layer edges' contributions also satisfy the summation-to-della property due to the Shaplye value's efficiency. 3) Based on cummattion-to-ellee property, we derive the Kullback-Leibler divergence, and define objective function to map changes in logits to shifts in predicted probability. By solving this optimization problem, we select a small number of layer edges that faithfully explain the evolution of predicted probability. Extensive experiments datasets for node classification, link prediction and graph classification tasks with evolving graphs show the effectiveness of our method in explaining the evolution of the predicted probability. Our methods empirically outperforms five popular, state-of-the-at baselines across the three graph tasks.
eight
2
PRELIMINARIES
2.1 GRAPH NEURAL NETWORKS
For node classification, consider a trained GNN with T' layers that predicts the class distribution of each node J E V in a graph G = (V, E). Let eIJ denote a directed edge from node to node J. Let A represent the adjacency matrix of graph G. The element ar of A represents the weight of the edge e1J. and a₁ = 0 indicates that enj does not exist. Let Let (J) denote the neighbors of node J. At layer t (t = 1,..., T), for node J, the GNN computes hidden vector hýj using messages received from its neighbors:
z = fUPDNEE (ha .1,- : ((J))))), h = NonLinear(z))..
(1)
(2)
where fk aggregates the messages from all neighbors, using clement-wise operations, such as sum, average, maximum. The function firDAIE maps the aggregated messages fiag to z'y, with parameters 0¹ For layer & E (l,...,7 T - 1}. ReLU is used as the nonlinear activation function. At input layer, h is the node feature vector x,, At layer T, the logits are given by 2 & (G). The logits GG) is mapped to the class distribution Pr(Y,|G; 0) using the softmax sigmoid function.
3

---

Published as a conference paper at ICLR 2025
For link prediction, we concatenate 2 and z input to linear layer to compute the logits:
ZrJ = < 23] OTP)
(3)
Since link prediction is a binary classification problem, z is mapped to the probability of edge J) existence using the sigmoid function.
For graph classification, the average pooling of zy( across all nodes in graph G produces single vector representation (G) for classification.
2.2 THE MESSAGE FLOW VIEW OF GNN
Given the adjacency matrix A' at layer t, the layer edge aj. in this matrix rep- resents the message carrier with which the message passes from node I to node J. The set of layer edges, is defined as A f.... "vv.. "C.y.... .'vv ... and (A] [ x T. For example, assuming the nodes in Go in Figure [ have no self-connections, and T 2, A A= =att,.77, a') JJ ahz, o (1; oZ. I "k LLx Li
Layer Edges:
Message Flow: In T-layer GNN model, let F (1, M,...... U.V...., J) denote the mes- sage flow starting from node in the input layer, and sequentially passing messages through node M,..., U, ..,..... L. until reaching node in the final layer T. The corresponding layer edges can be represented as (a/M.--. ... .iv...... ................................ aff)) Let F(t) denote the node at the layer in this message -iv......v...............
flow F. where = O...., T, = 0 denotes the input layer. For example, for the message flow F (I, J), the corresponding layer edges are (atz, (2,). F(O] I, F[]] F1 J.
Table I: Symbols and their meanings
2.3 EVOLVING GRAPHS
Symhols
Definitions and Descriptions
{0, 1} indicate the time steps The weight of input edge graph G, The weight layer edge in graph
Let (0, 1} denote the time steps of two graph snapshots, where G. (V", _ rep- resents the graph. The adjaceney matrix of G, is denoted as AT, with element ary rep- resenting the weight of input edge. Addi- tionally, And refers to the adjacency matrix at layer t, with element auv representing the weight of layer edge. Let h² and zj T.P denote the hidden vector and relevant vec- tor of node J at layer t in graphs G,. As the graph evolves from Gu to G1, we define the change in layer edge weight as Sary = avi - avy. Similarly, Let Ah', = h h and Az', = 1.f 0,4 graph Go and G. Let Áz, A Az denote the difference in logits of node J between Go and G₁.
"dy "0v A
layer
set of a'ttered message flows
The set altered layer edges
The hidden vector of node J at layer in G+
The relevant vector node J at layer in G+ The difference in weight of layer edge between Gg and G1 The difference in relevant vector z between Go and G; The difference in hidden vector h between Go and G.
Anby
T.
Az
Abj
C
Contribution of the message flows to Az Contribution the layer edges Az
z denote the difference in the hidden vectors and relevant vectors at layer between
We assume that the edge weights change continuously, including edge additions and removals. Let AE be the set of altered edges: AE = {evv dby # U.V. E V). Let AA repre- sent the set of altered layer edges: AA {aby ary # abv,t E [I....,T). U,V E V}. If the weight of layer edge within message flow changes between Go and G1, the message flow also altered. Let AF denote the set of altered message flows: AF = {F (F[0)....
o.t
I, I,...,,y T}. As Gy + G1, the predic- tion evolves from Pr(Y))o) to Pr(Y))T). The set AF causes this evolution, as the information propagated by these massage flows differs between the source and destination graphs. Thus, AF provides explanation of the evolution with 100 % Fidelity, without any loss of information. How- ever, due to lack of Interpretability, it is difficult for humans to understand. The complexity of AF increase significantly due to changes in edge weights connected to high degree nodes. Small perturbations in graph can cause AA to become large, further impacting the complexity of AF. As result, AF can be not serve good explanation.
0,t F(T]), =[--1]51 * F1p111
Ltt
4

---

Published as a conference paper at ICLR 2025
3 METHOD
We propose a method to study the explainability of the evolution from Pr(Y|Goo 0) to Pr(Y|G1;0)
To address the challenge in Figure 3 we first derive the A t .,... T. We then apply the mul- tipliers and chain rule from DeepL.FT to calculate the contributions of altered message flows, and obtain the contribution matrix C. This contribution matrix satisfy the summation-to-derl property,
i.c. Áz, = D!AF C.. However, due to the non- non-linearity of softmax function and KL divergence, Az not linearly represent the evolution from Pr(Y Go: 0) to Pr(Y|G;;; ;
0). To resolve this, We map the áz, to the evolution from Pr(Y|Ga Go; 0) to Pr(Y G1; 0) through mathematical derivation, utilizing the cummatioon-o-delia property, as illustrated in Figure dj. Next, to fairly attribute the contribution of message flows to layer edges, we employ the Shapley values and compute the con- tribution of layer edges, denoted 4. Due the efficiency of Shapley values, & also holds the summation- tto-lll property, i.c. Áz, = Ei=1 select the important layer edges, derive the KL divergence and design the optimization problem, leveraging the summation- to--llt property, as shown in Figure ff).
|AAI L1, as shown in Figure ((c). Finally, to faithfully
3.1 CALCULATE THE CONTRIBUTION OF MESSAGE FLOWS
To demonstrate the calculation of contribution values, we focus on the node classification task. Details for calculating contribution values in link prediction and graph classification tasks can be found in Appendix A.2.2 and A.2.3 respectively. We use DeepLIFT (Shrikumar et al. 2017) to
114 calculate the contribution values of message flows and ensure the Az,- = =E Cs,, which existing work did not do with continuously changing edge weights.
3.1.1 DEEPLIFT
We introduce the multipliers and chain rules from DeepLIFT (Shrikumar et al. 2017) which are used to calculate the contributions of message flows. While DeepLIFT is designed contributions at the neuron level in multi-layer preceptron models, we extend it to a vectorized representation for computational efficiency. Let E {0, 1} denote the time step. Let hT E RR and h h E R represent the hidden layer vector layer t and t+ at time step T, respectively. The vector h is computed as h = fh where f(h = h for a linear function, with O Ruxm as the weight matrix, otherwise, is the nonlinear activation function. The is defined as Ah ++1 h1.41 0,0+1 and Ah' -h h DeepLIFT
evaluate
defines multiplier as follows:
0 Raxm
linear layer
Mah
Aht Ahh' E R Ixn nonlinear activation
(4)
denotes element-wise division. The following relationship holds: Ah' x mak = Ah++1
where X represents matrix multiplication if f is linear, and wise multiplication if f is nonlinear. DeepLIFT defines the chain rules
AhT T " - = AhT 2
(5)
Ah MARPAA MAA.-AAATA
According to chain rule and multipliers, we can calculate the contribution message flows.
3.1.2 DEEPLIFT FOR GNN
DeepLIFT has been applied GNNs with the addition and removal of edges (Liu al. 2024 How- ever, existing methods assume discrete graph evolution, leading to incorrect contribution calcula- tions for message flows continuously evolving GNNs. This because, difference-from frefeeeeee,,,,-eeeeennee,,,, used in the calculation process of DeepLIFT, becomes more complex and inconsistent in continu- ously evolving GNNs. To address this challenge, for a given message flow J E AF, we derive Ah" t = 0, ... ,T based on the propagation rules of GNNs. Then, we use multipliers and the chain rule defined by DcepLIFT to caleulate the contribution value of message flow.
In GNNs, zi = EVEN(y) hi ' where z depends to two factors: the information from the neighboring node h and the edge weight a Consequently, Azl, is influenced by changes
5

---

Published as a conference paper at ICLR 2025
in both Ahy' and Adiy. Specifically, Aby propagates node V. altering V's information. Additionally, Adyy affect the extent of information aggregation from node U to node V. The formula for Azy given by:
E VEN(V)
(a (avvhe
01)
E VEN(V)
(aiv )dbr) )b 1/ aivhi hi
Σ UEN(V)
(h2 hi h2- + Aatyhy 11-11 OVv
04t
0
Σ
1.t- hi 0¹. 0² + sair auv Guy
0,t
DEN(V)
Eq. (6) explains the cause of Azy by decomposing the change into two parts, The first term 0.t
duv duv Ahi '0' represents the propagation of Ah from node U to node V when the the layer edge weight auy remains unchanged. Since by b h Ahy the second term can be rewritten as Aayy (hg 1hot-1 + ")', showing that the change in edge weight transfers both h hot-1 and Abj 1 to node V, contributing to Azy.
According Eq. (6) and by applying the chain rule and the multipliers defined in Eq. the contribution of message flow can be computed through layer by layer decomposition. For a given flow F in AF, F[t] denotes the node at layer in F. The formula for calculating the contribution of this message flow is as follows (detailed derivations and examples are provided in Appendix A.2.1)
C,
Σ 1=0
1.1 FF00)
Da 1+1 11+ (
0,8+2
0.T 1][T-1],((]]
F[(+1]
h 1.1
h
Ah
(+1
Ah T-1 -T- 0
h 1.0
fm
Fit
g
F(O)
Az
Az F[
FU
F[++1]
where ratios denote the element-wise division, and C E RA xc denotes the the contribution matrix of message flows. Let denote s-th flow F in AF to Az,, Due the multipliers and chain rules, the contribution matrix satisfies the summation-to-delta property, i.e. a=1 C. = AzJ.
DIAFI
Leveraging this property, we can map the Az, to the evolution from Pr(Y 0) to Pr(Y|G;;;)
3.2 APPLY THE SHAPLEY VALUE TO MAP MESSAGE FLOW CONTRIBUTIONS TO LAYER EDGES
Message flows are difficult for humans to understand and challenging to evaluate. In GNN compu- tational graphs, layer edges in message flows carry weights, and during evaluation, single layer edge can appear in multiple message flows with different weights. However, GNN propagation rules require each layer edges to share a single weight, making it impossible to merge these flows while adhering to GNN propagation rules (see Figure 6 for an example). A mapping function is needed to convert the contributions of message flows to layer edges. Existing methods use average or sum functions mapping functions, overlooking the fact that layer edges may contribute differently. To fairly attribute the contributions message flows, we use the Shapley value.
For message flow F = (F(0) ..... F(T E AF, the corresponding layer edges in the G, can be represented {a
T [[]]]]][1)
{0, 1). The changed layer edges in given [ [F * a 1.t [|F E (1....,T) We consider
F[T {)
T.
) where 0,t
message flow is AA, mapping the contribution values C. computed using Eq. (7). to the changed layer edges in AAr
as an allocation problem. We use the Shapley value Φ; = =scNy( ([91=()))11(111) (i)))
(NI-1)
v(S) to fairly distribute C, among these layer edges. We define the following:
The player i: One changed layer edge "111111 in AAF.
The player sets N: N AAF denotes all changed layer edges in the message flow. |N] the total number of players.
The coalition S: S C N. Only the weights of the layer edges in S will be altered. This change will yield different layer edges for the given message flow. Consequently, the contribution of the same

---

Published as a conference paper at ICLR 2025
message with different layer edges will differ. For given S, the corresponding layer edges
{">1oop11))"" - "tt -3r--11111 where d5(-111711 a [](--1]=(1" if a 15p-11111 S,
else 151111111 1 [S] represents the size of S.
0.2
(S): Given S and the corresponding layer edges, v(S) is computed according to Eq. classification) or Eq. (13) (link prediction) Eq. (14) (graph classification).
7 (node
Given a message flow FF in AF, we use the Shap- ley value to calculate the contribution (1at-11711 (F)
Message Flow K 0
of layer edge "F[t-1]Fld to the message flow C..
The layer
v(S)
Due to efficiency of Shapley value. it follows that Eazy, E P1pp-11a (F) = (NN)= C.. An example of this calculation is illustrated in Figure
-05
Obeah
10:05
-03 -05
(42))
For node classification, let the + E glAA|x denote the contribution matrix of layer edges, the row vector d denote the contribution of I-th layer edge dF(t11=F11 in AA. $
Satan (2,04
0gl 10.12, R4. - [-0125, 0.60
ExEsF Pas Poz (F). Because
Ay de. x00)
Eajy- 11- EN Dazz Mat (F) C. and E!A C. Az,, AA 4 = Áz For link prediction and graph clas- sification tasks, see Appendix A.3
Figure 4: For message flow G1 Figure | the example of using Shapley value map contribution from message flows to layer edges.
3.3 SELECT THE IMPORTANT LAYER EDGES
To illustrate the selection of important layer edges, we focus on node classification task, while link prediction and graph classification tasks detailed in the Appendix [A.4] KL-divergence is used to
measure the approximation quality of a static predicted distribution PG) (Liu et al. 2024):
KL(Pro(Gi)(Pt((Ga)))
Σ (G)) - (Go)] log Z(G1)
Z(G1)
Σ Pra logl Z(Go) Z(Go)
(8)
where Z(G+)= = Ei=1 exp(2x (G+)) for = 0,1. Let x E {0, (0,1)1AA) denote the selection vector, where the element zı in indicates whether the I-th layer edge is selected. Suppose select a subset of n important changed layer edges AAsub E AA to explain evolution from Pr(Y)Goo Pr(YIG;; 0). Let Gn denote the graph that the weights of the layer edges in A are changed to those in G1, while the weights of the layer edges in AA \ AArub re- main unchanged.
the (L(Pr(G1))| (P((G)) is small, it means that the AAsub can faithfully explain the evolution in prediction probability. Let & denote the contribution matrix of layer edges, and 4 represent the contribution of I-th layer edge to Áz,- $1.6 indicates the contribution of 1-th layer edge to Azt. Thus, (G(),)) EA T; + (G and according to Eq. (8) (L(Pr(G.)IPrr(GA,
Di-1 Pra (rx( Z(G,,) Ei=ı exp(2x (G.)), then can define the following objective function:
(G.)) log Z(Gi) + log Z(G.), where
[AAI
AA
x"
arg min xe
(r.)
Σ Im1
+ log
Σ R
exp
(G))
Σ 1mm
xy PL
1)
=x
By solving Eq. we obtain the most important changed layer edges. The Algorithm I shows the overall process of selecting important layer edges for node classification task. The Algorithm 2 for the link prediction task and Algorithm 3 for the graph classification task are in the Appendix.

---

Published as a conference paper at ICLR 2025
Algorithm Selecting important layer edges to explain evolution of Pr(Y]G)) to Pr(Y]G;) on the
node classification task
1: Input: the source graph Go and the destination graph G1, Pre-trained GNN parameters 0
2: Obtain the layer edges flow set AA
3: Initialize layer edges contribution matrix (RÁAA as an all-zero matrix
4: Obtain the altered massage flows set AF
5: Given the target node J, AF = (F
AF and F[T] = J}
6: for for to AF do
7: Select the s-th message flow in AF and calculate contribution C, according to the Eq.
8: Obtain the changed layer edges set AAr on this flow
9: for []][(] in AA, do
10: Calculate Oazz (3(0)1111)))
11 (F) using Shapley value.
11: Let the index of a 1 in AAi d1 41 + Pa's 115(0 (F)
end for end for Solve Eq. (9) to obtain the important changed layer edges Output: The important changed layer edges set
13:
15:
3.4 COMPLEXITY ANALYSIS
Obtain the changed message flows AF: Given the changed edges AE, we use the depth-first search method to obtain AF and the complexity is (1AE)?).
Calculate contributions: According to the Eq. 7 we calculate the contribution of each message flow through the vectorized method. The complexity O(IAF( (++1 dl df++1), where de
and 1 denote the dimension of the 0 Rdd x ,t fl....... ,.).
Apply the Shapley value: For each message flow F E AF with more than one changed layer edge, the Shapley value is used to fairly attribute contributions. Some calculations in the calculating contributions can be used repeatedly. The worst-case complexity is O[AFF((2 1)d +++))
where (2 - 1) represents the number of non-empty subsets of layers.
Select the inportant layer edges: The time complexity is ((4AA)))
EXPERIMENT
Datasets and tasks. We evaluate method node classification, link prediction and graph classification tasks using real and simulated dynamic graph datasets. Details of these datasets are provided in Appendix A.7.1 We assess the running time of our method large datasets (See Appendix A.7.7 and Figure 9.. On BA-Shapes dataset, we validate the accuracy the explanation methods. The visualization results and accuracy are shown in Appendix A.7.8 Figures 10 and [II
Experimental setup. For each dataset, we optimize the GNN parameter on the training of static graphs, using labeled nodes, edges, or graphs based the specific tasks. For each graph snapshot, excluding the first one, target nodes/edges/graphss with a significantly large are collected and the change in Pr(Y is explained. We run Al- gorithm [ or Algorithm B to identify the important layer edges for node classification, link pre- diction and graph classitication tasks. The optimization problems in Eq. (9. Eq. (15) and Eq. (16) are solved using the cvxpy library (Diamond & Boyd). Our proposed method is called "AxiomLayeredge"
DxL (Pr(Y (Eo)|PP((Y
Additionally, we employ the GNNExplainer (Ying et al.) 2201)), PG- Explainer (Luo et al., 2020), GNNLRP (Schnake et al.) (020) DecoLIFT (Shrikumar et al.) 2017). and the FlowX (Gui et al.] 2003) as our baselines. We also design some variant meth- ods: AxiomLayeredge- Topk, AxiomLayeredee SShaley. AxiomEdge, AxiomEdge-Top and Ax- Shomleey Appendix [A.722 gives details of the baseline methods. Appendix A.7.3 gives
details of the experimental setup.
8

---

Published as a conference paper at ICLR 2025
Quantitative evaluation metrics. Supposing the selected important layer edges set and edges set are denoted as AA' and AE", respectively. For evaluating the layer edges, we start from the computational graph of Go. only adjusting the weights of the layer edges in AA" to those G1, while the weights of the layer edges in A \ AA" remain unchanged, then we obtain the computational graph Gn- Similarly, for edges evaluation, we alter the weights of the edges in AE* those in G1, with other edges weights in & \ AE unchanged, then we also obtain the G... After obtaining Gas we can compute the (r)Y) The case of obtaining Gn, can be seen in Figure 7
(KL) divergence See Figure 7 for an example. The idea of this metric similar to the Fidelity- Yuan et al. (2020b). Intuitively, if adjusting only the weights of selected layer edges (rather than all changed edges) brings (r)(Gn) closer to Pr)(Gr), indicates that these edges effectively explain the evolution from Pr(Y|Gp) to Pr(Y)G1), resulting in smaller evaluation metric. A sim- ilar metric can be defined for the link prediction task and the graph classification task, where the KL-divergence is calculated using predicted distributions over the target edge or graph. To ensure comparability between layer edges based and edges based explanations, we apply the same level of sparsity. We define five levels of explanation sparsity (Yuan et al., 2020b), with all methods com- pared under the same sparsity level. For the edges, the sparsity is 1 AE AE.
The evaluation metric for the node classification is Kullback-Leible (L(Pr)(Gn)) (G)))]]r)GrG)
For the layer edges, it AA The higher sparsity indicates the explanations are more sparse and tend to only capture the most important input information. The Table 4 and Table 5 Appendix AA.7.4 provide details on the sparsity for real and simulated dynamic graph datasets across the three graph tasks.
- A4"
Performance evaluation and comparison. We evaluate the performance of the methods across three tasks: node classification, link prediction and graph classification in real and simulated dy- namic graph datasets. For each dataset, we report the average KL over target nodes/edges/graphs. Results for dynamic graph datasets are illustrated in Figure [5] while those for simulated dynamic graphs are presented in Figure in Appendix A.7.6 Table fand Table5]display explanation sparsity levels across different datasets. In Table [ the sparsity for all real dynamic graph datasets is no less than 0.9. Figure 5 demonstrates that our method AxiomLayeredge has the smallest KL across all levels of explanation sparsity levels, datasets, and tasks, with exception of certain sparsity levels of Pheme dataset. This illustrates that our method maintains high fidelity in explanations even under high sparsity. On eight settings (Weibo, YelpChi, YelpNYC, BC-Alpha, BC-OTC, UCI, MUTAG, ClinTox), our method AxiomLayeredge along with its variants AxiomEdge, AxiomEdge' Shapley, AxiomLayeredge SaareedeeeSSSSpleee (hapley outperform the GNNLRP, DeepLIFT, GNNExplainer, PGExplainer and FlowX methods. This demonstrates that our proposed methods more effectively explain the evolu- tion of Pr(Y|Gu; 0) to Pr 0), while methods designed for static graph struggle to identify salient edges that explain changes in the predicted probability distribution. Moreover, our method Axioml Layreege has superior performance compared to the Axioml sayrrddyy Shapley Shaplee method across all levels of explanation sparsity, datasets, and tasks, with a significant gap observed on the Pheme and Weibo datasets. Therefore, the Shapley value provides a fair attribution.
RELATED WORK AND FURTHER DISCUSSION
GNNs Explainability. The limitation of GNNs is the lack of explainability. Recently, various meth- ods have been proposed to explain GNN predictions, primarily focusing on static graphs. In the survey (Yuan et al., 2020b), existing GNN explanation approaches are categorized instance-level methods, such as CAM and GradCAM (Baldassarre & Azizpour 2019 Pope al. 2019). which identify important nodes by the gradient,but are not applicable for the node classification. Perturbation- based methods, such as GNNexplainer (Ying al. 2019). PGExplainer (Luo et al. 2020), Graph- Mask (Schlichtkrull et al., 2020). learn masks to identify important edges by maximizing the mutual information to explain the predicted class distribution of model. However, these methods cannot ax- iomatically isolate contributions of message flows that causally impact the prediction changes on the computation graphs. Decomposition- based methods, such as GNN-LRP (Schnake et al. 22200, ex- tend the original LRP (Bach et al. 2015) algorithm to GNNs and study the importance of the graph walks. While GNN-LRP explains the single class probability, it cannot explain multi-class distri- butions change over evolving graphs. Surrogate-based methods, like GraphLime (Huang et al.) 2020). use a surrogate model with kernel-based feature selection to provide node feature explana- tions. In model-level category, XGNN (Yuan et al. 2020a) generates graph patterns that maximize
and model-level methods. The instance-level category includes Gradient/features-ben

---

Published as a conference paper at ICLR 2025
Pheme
Welbo
YelpChi
YegNYC
0.7
1.0
0.5
0.8
0.4
0.5
0.0
0.2
0.3
04
0.2
02
0.2
0.1
0.1
0.0
2
2
Expleration spereily leveds
Explanation opersily levelo
Explenation sparsiy levels
Expleration spereily levels
BC-Alpha
BC-OTC
0.025
GNNExplamer
0.30
0.35
0.14
0.020
PGExphiner
GNN-LRR
52
0.20
0.25
0.10
0.015
Rowk
AudonEdge/Shaptery
DeepLIFT
0.10
0.15
0.06
0.010
AxlomEdge
AdiomEdge
0.05
0.02
0.005
AyyommLy Topk
Lyyrodge
Explariation sparsily levels
Explanation nalion spershy lools
2
Explanation sporsity levals
2
AubomLayyredgeeShaatey
MCB-BINARY
0.20
0.200
0.178
0.10
0.11
0.15
0.150
0.00
0.125
0.08
0.10
0.04
2 0.100
0.07
0.075
0.08
0.02
0.050
0.00
0.00
0.000
0.025
0.04
2
Explanation sparsity lovels
Explanation sparsty levels
Explanation sparsity levels
Explanation sparsity lovels
Figure 5: Performance of KL in real dynamic graphs. Each figure corresponds to different dataset. The first, second and third rows represent node classification, link prediction and graph classification tasks, respectively.
a certain model prediction via reinforcement learning. In conclusion, most prior work evaluate the fidelity of the explanations on static graphs. They cannot explain the evolution of Pr(Y|Guu 0) to O).
Limitations and Concerns. While acknowledge the effectiveness of our methods, we also recognize their limitations. We focus on the explanations on static GNNs in evolving graphs. Our method cannot be extended to dynamic graph models, such TGN (Rossi al. 2020), which incorporate time-series components like RNNs or LSTMs. We do not design rules for decomposing contributions in RNNs LSTMs. For static GNNs, our method can be applied to the GIN (Xu al., 2018) model. For GAT model, our explanations are limited to identifying a small subset of changed attention weights on edges. We are unable to measure the contribution of added or removed edges to the changed attention weights and select the changed edges as the explanations. Because we do not define the rules to attribute the difference of softmax function to the changed input.
CONCLUSIONS
We studied the problem of explaining change in GNN predictions with the weights of input edges continuously changed. We addressed the issues of prior works, such as lack of axiomatic attribution of message flows, unfair distribution and lack of optimality. The proposed algorithm can axiomat- ically decompose the changes to message flow in the computation graphs of GNN and employ the Shapley value for fair attribution to layer edges. It further optimally select a small subset of layer edges to explain the evolution of prediction probabilities. Experimental results demonstrate that our method achieves superior performance even when sparsity exceeds 0.9. This indicates that our approach successfully balances Interpretability and Fidelity.
10

---

Published as a conference paper at ICLR 2025
7 ACKNOWLEDGEMENT
Sihong Xie was supported by the Department of Science and Technology of Guangdong Province 2023CXI0X079)) National Key R&D Program of China (Grant No.2003YYFF7220001 the Guangzhou-HKUSTCCE HKUST(GZ) Joint Funding Program (Grant No.2023A03300008) and Education Bu- reau Guangzhou Municipality.
REFERENCES
Andrew Anderson, Jonathan Dodge, Amrita Sadarangani, Zoe Juozapaitis, Evan Newman, Jed Irvine, Souti Chattopadhyay, Matthew Olson, Alan Fern, and Margaret Burnett. Mental models of mere mortals with explanations of reinforcement learning. ACM Transactions on Interactive Intelligent Systems (TiiS), 10(2):1-37, 2020.
Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Blaus-Robert Müller, and Wojciech Samek. On pixel-wise explanations for non-linear classifier decisions by layer- layer-wise relevance propagation. PloS one, 10(7):e0130100, 2015.
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional net- works. In ICML Workshop. 2019.
Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, and Cor- win Hansch. crtucture-activing relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. 1991.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research.
Kaitlyn M Gayvert, Neel S Madhukar, and Olivier Elemento. A data-driven approach to predicting successes and failures of clinical trials. Cell chemical biology, 23(10); 2016.
Shurui Gui, Hao Yuan, Jie Wang, Qicheng Lao, Kang Li, and Shuiwang Ji. Flowx: Towards ex- plainable graph neural networks via message flows. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, Dawei Yin, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. arXiv preprint arXiv:2001.06216. 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Vivian Lai and Chenhao Tan. On Human Predictions with Explanations and Predictions of Machine Learning Models: A Case Study on Deception Detection. In Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019.
Yunqi Li, Yingqiang Ge, and Yongfeng Zhang. Tutorial on fairness machine learning in recom- mender systems. In Proceedings of the 44th international ACM SIGIR conference on research and development information retrieval, pp. 2654 2657,2021, 2021.
Yazheng Liu, Xi Zhang, and Sihong Xie. A differential geometric view and explainability of gnn on evolving graphs. arXiv preprint arXiv:2403. 0024400.5555, 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-1963 1, 2020.
Jing Ma, Wei Gao, and Kam-Fai Wong. Rumor detection on twitter with tree-structured recursive neural networks. ACL, 2018.
Phillip E Pope. Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural networks. In CVPR, 2019.

---

Published as a conference paper at ICLR 2025
Gabriëlle Ras, Marcel van Gerven, and Pim Haselager. Explanation methods in deep learning: Users, values, concerns and challenges. Explainable and interpretable models in computer vision and machine learning, pp. 19-36, 2018.
Shebuti Rayana and Leman Akoglu. Collective opinion spam detection: Bridging review networks and metadata. In KDD, 2015.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.1063 10637, 2020.
Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for nip with differentiable edge masking. arXiv preprint arXiv:2010.00577, 2020.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima Kristof T. Sch utt, Klaus-Robert M Muuller, and Gr' egoire Montavon. Higher-order explanations of graph neural networks via rele- vant walks. 2020.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1 1.05868, 2018.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International conference machine learning, pp. 3145- 3153. PMIR, 2017.
Hongwei Wang, Fuzheng Zhang, Mengdi Zhang, Jure Leskovec, Miao Zhao, Wenjie Li, and Zhongyuan Wang. Knowledge-aware graph neural networks with label smoothness regulariza- tion for recommender systems. In KDD, 2019a
Jianyu Wang, Rui Wen, Chunming Wu, Yu Huang, and Jian Xion. FdGars: Fraudster Detection via Graph Convolutional Networks in Online App Review System. In WWW, 2019b.
Zhenqin Wu, Bharath Ramsundarand Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay S. Pande. Moleculenet: benchmark for molecular machine learning. 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.000 00826, 2018.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William Hamilton, and Jure Leskovec. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In KDD, 2018.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. GNNExplainer: Generating Explanations for Graph Neural Networks. In NeurlPS, 2019.
Jiaxuan You, Bowen Liu, Zhitao Ying. Vijay Pande, and Jure Leskovec. Graph convolutional pol- icy network for goal-directed molecular graph generation. Advances Neural Information Processing Systems, volume 31, 2018.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. 2020a.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. arXiv preprint arXiv:2012. 15445 2020b.
Arkaitz Zubiaga, Maria Liakata, and Rob Procter. Exploiting context for rumour detection in social media. In ICSI, pp. 109-123, 2017.
12

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 EVALUATION MESSAGE FLOWS ON DYNAMIC GRAPHS
In Figure 6 we illustrate the computation of Fidelity for both dynamic and static graphs from the perspective of computational graphs. The static graph Go is considered an evolution of Gempty In the case of dynamic graphs. G₁ evolves from the Gg. After identifying the important message flows, we adjust their weights to align with those in the destination graph, keeping the weights of the remaining flows unchanged. This process generates a new computational graph G,- In dynamic graphs, adjusting the weights of selected important message flows may lead to differing weights for the same-layer edges across various flows. However, GNN propagation rules require that edges within each layer share single weight. Thus, merging these flows while complying with GNN propagation constraints is infeasible.
Source
Import message flows
G
destination
Gempty
Go
New
A 0.3 computational
0.3
Fidelity
0.2
Static graphs
graph
+
A 0.4
0
0.4
0.2
0.3
0.4
K
Go
G
New computational graph
0.2
0.3
0.3
0.1
Fidelity
1033
Dynamic graphs
+
0.2
K
How to combine?
0.2
0.3
0.4
0.02
0.42
0.3
0.42
02
Figure 6: Calculation of Fidelity for dynamic and static graphs. Challenges may arise during the computation for dynamic graphs.
A.2 CALCULATE THE CONTRIBUTION OF MESSAGE FLOWS
A.2.1 THE EXAMPLES ON THE NODE PREDICTION TASKS
Supposing the GNN models have two layers, considering the massage flow = (V,IJJ) the altered message flows set AF, We have derived in detail the calculation process of the con- tribution value of message flow:
C.
01J
0.T Aht- 10 + Aajnht 1r the contribution of Ah, hy to Az,
O. =ajj (Az) A 12 -17 OT
the contribution of Azr Ahr
+Daf, [z] m -
1TT-1
the contribution of 2, hy
(10)
=0j] AhT -22 2m snE 2227 1-T-im, 11 'Ah7 20T
0.TT
the contribution of Ahy to Az,
+ ajj hy
0,T -2
hy
m 1
7- _ax7
- -Ah? 0T
the contribution of hy to Az,
+ +AaT, (hy
1TT m 22)
2 m 1. nn
T T
the contribution of hy to Az,
According to the multiplier designed
by the DeepL.FFT m MAh T-2 Az T-1
Aut A m Az
Ah Az
1.7 0T
T-
1.T 17-1 ayi
13

---

Published as a conference paper at ICLR 2025
therefore,
Ah - A r-1 8" 1T-1 I. 2z
/ --1
C. Sayy
0.7 aIj hy
h1/-1/10 -0" 12"--1
avi hat
r- g
(11)
Where the divide means the element-wise division, T == 2.
Similarly, Supposing the GNN models have three layers, considering the massage flow I.J) & the altered message flows set AF, We have derived in detail the calculation pro- cess of the contribution value of message flow:
C,
aij -aj Ah, + A, 0T
0.7
the contribution of Ahr, h, to Az,
= a]j (Z ( - An)-
-)TT
the contribution of Az, to Ahy
+ Aaa [2]
11--1 - 1.1.1111111111
the contribution z, to h
a1j Ah
0.T 2
ahT-mmAn
Ahhy T
im A27 Ah?
the contribution of Ahy to Az,
+ 013 hy
0.T 1.T-2
1m
1- A Ah?- 0T
the contribution of hy to Az.J
AafJ (hy
1
m bv 1.7-22) r-1 m 1. h)
h: 0
the contribution of hy Az,
aj (aVV
-.T
T - 30" 2 + D T' 2 1
m An? A
Az, An?
Ah?
the contribution of Ahy to Az,
+ ais
(hT-33m 0TT m (hy- " 7- m 1 T-2 11
Ax. Aax/-1Ah) 7- 0
(12)
the contribution of by to Azj
+ ArTy (bT- "m
3 T 1 m 1T 21 1.7-
m 1
m 1.
0
the contribution of by to Az,
T-2
Ah 1
0.T-2 0, 0.T DaUV avI DIj hi
8
V
0
0
AZ
T-2
Az T 1
T T-2
Ah T 1
+ dUV
-TT-2
To 01 hi
T-1
0.T
1.7
0
T--
0
ZV
T
Az
T-2
h T-1
+ HVV "vi
1T--2 1,T-1
Aat
h
IT -3 0
V
0
0
Z
A.2.2 ON THE LINK PREDICTION TASK
According to Eq. (3. for the target edge ei,, the z glxd and z e glxd are concatenated and passed through linear layer with the parameters 0LP. According to Eq. 7.. we can obtain the contribution of message flow Azi or Azy then the contribution of message flow to the Azi, = (G)(Gr) ZI)(Go) is:
Σ C,
1.1 12
a
Aa F|1
0412 [[++)) (
0.T "f(T-1),F[1
(13)
Ah f+1
Ah T-1
h
1.0
r[++ g++
J[T-1]
g g'
F[0]
1.1
1.t
Az
++1
Az T-1
z 2
[[11]
Where 0rp- 0z. 00: d], V7+1 I, 0/r
Orrld if V J
14

---

Published as a conference paper at ICLR 2025
A.2.3 ON THE GRAPH CLASSIFICATION TASK
Because the average pooling is used for the graph classification tasks, Az z(G1) z(Go)
EJE(MUR)) / UV"I, thus the contribution is:
T-1
C =
A-1 Ao
0,0+2 Fi
0,7
[[++1) ...
FFTT-11.F11
(14)
1.
Ah ++1
T-1 Ah
1.0
r 0
1 0") /aD0
Fl
Az
Fi()
[[++]]
FTT-1
Where, Vn and Vi denote the the nodes set of graph Go and GI, respectively.
A.3 MAPPING CONTRIBUTIONS FOR THE GRAPH CLASSIFICATION TASK
(F) of layer edge 1 to Azi,, Note that the changed layer edge can affect many nodes, not the single node. Thus, in the graph classification task, the contribution matrix of (-th layer edge d311111111 AA s' E BIL"Lv" xe the row vector Ø Pa ; (F) denotes the contribu-
In the section 3.2 we show how calculate the Shapley value, i.e. contribution Oajy -
tion of the 1-th layer edge to Azi, where the i-th node in the V UV is Fr. Let & = E Φ!
the & also follows the summation-to- property I 4 Az z(G1) z(Go)
A.4 SELECTING THE IMPORTANT LAYER EDGES
A.4.1 ON THE LINK PREDICTION TASK
For the link prediction, the (G) [Gr) ,Pr .r. Pre(G)), Let & denotes the contribution matrix of layer edges, where d represents the contribution of 1-th layer edge to AzrJ, and dr, indicates the contribution of 1-th layer edge to Az, we can define following objective function for the link prediction:
1z,.... Zel. Pr))(G)
IAA
x
arg min
Pre(GG)
Σ
XE(0.1]1AA1
1=1
|
AAA
log
exp
ze (Go)
Σ
(15)
A.4.2 ON THE GRAPH CLASSIFICATION TASK
For the graph classification, the Tb' denotes contribution matrix of the I-th layer edge in the AA. The logits of the graph classification ZG [zi,-.. Bg ... ,Z]], the Pr(G) [Pr, (G), ... .r.... (G))) because the Σ >I>"v"1 EISAi s! Az Az(Gr) Az(Go),
the objective function for the graph classification task is:
Mrr Σ
x arg min xe (0.1) I
Pry(Gi)
Ty T
9=1
1=1
|x
|
+ log
exp
Zg (Go)+ +
Σ
2 T '.g'
(16)
g'
A.5 SELECTING THE IMPORTANT LAYER EDGES FOR LINK PREDICTION
Selecting the important layer edges for link prediction task can be seen in Algorithm
2
15

---

Published as a conference paper at ICLR 2025
Algorithm 2 Selecting important layer edges to explain evolution of Pr(Y]G)) Pr(Y]G;) on the
link prediction task
1: Input: the source graph Go and the destination graph G1, Pre-trained GNN parameters 0
2: Obtain the layer edges flow set AA
3: Initialize layer edges contribution matrix T &R AA all-zero matrix
4: Obtain the altered massage flows set AF
5: Given the target edge IJ, AF {F E AF and (F[T) I or F[T] J)}
6: for for to AF do
7: Select the s-th message flow in |A and calculate C, according the Eq.
8: Obtain the changed layer edges set A on this flow
9: for d=1[11])11 AA, do
10: According to the section calculate 11 (F)
11: Let the index a' a' 1 A is 1, 21 = 2i Dasz 1all (F)
12: end for
13: end for
14: Solve Eq. (15 to obtain the important changed layer edges
15:
Output: The important changed layer edges set
A.5.1 SELECTING THE IMPORTANT LAYER EDGES FOR GRAPH CLASSIFICATION
Selecting the important layer edges for graph classification task can be seen in Algorithm
Algorithm 3 Selecting important layer edges to explain evolution of Pr(Y[Go) to Pr(Y|G,) on the
graph classification tasks
1: Input: the source graph Go and the destination graph G1, Pre-trained GNN parameters 0
2: Obtain the layer edges flow set AA
3: Initialize layer edges contribution matrix Φ RIV"V |xe all-zero matrix
4: for for to |F do
5: Select the s-th message flow in AA and calculate C, according the Eq. (14)
6: obtain the changed layer edges set AAF on this flow
7: for [ AAF do
8: According to the section
3.2
calculate Pa 177
9: Let the index a'
d' in AA is I. Let the index of F[T] in the 1 1 is
10: $ & (a3 (F)
11: end for
12:
end for
13:
Solving the Eq. (66) to obtain the important changed layer edges
Output: The important changed layer edges set
A.6 OBTAIN THE IMPORTANT INPUT EDGES
A.6.1 ON THE NODE CLASSIHCATION TASK
Let & denotes the contribution matrix of edges, where O represents the contribution of I-th edge Az,, and L indicates the contribution of (-th edge to Ažk. we can define the following objective function for the node classification:
arg min xe (j.e
(ra((r)
Σ
P1.k
1=1
+ log
(Go) +
Σ
x d
(17)
#=1
1=1
16

---

Published as a conference paper at ICLR 2025
A.6.2 ON THE LINK PREDICTION TASK
For the link prediction, the ZiJ(G) [Gr, Pr...., Pro(G),, Let & denotes the contribution matrix of edges, where D represents the contribution of 1-th edge to ÁziJ, and 41 indicates the contribution of I-th edge to Aze, we can define the following objective function for the link prediction:
1z Ze... ,Zo], PriJ(G)
|AEI
x" =
arg min
-
(re(G
Σ
x L.E
x
1=1
||||===
|EE
log
exp
Ze (Go)
Σ
(18)
1=1
A.6.3 ON THE GRAPH CLASSTRICATION TASK
For the graph classification, the o' denotes contribution matrix of the l-th layer edge in the AA. The logits of the graph classification ZG [.,.... "gg.... ... Zo], , [Gr Pr. Pro(G)], because the E|'"v'' Σ Φ Az Az(G1) Az(Go), the objective function for the graph classification task is:
the Pr(G) =
1D |AE1
x
arg min
Σ 8=1
- (G))
Σ
Σ
xz x
xe (0.1) |
1=1
1=1
[
log
exp
Zg)(Go)
+
Σ
Σ
x 2
(19)
A.6.4 SELECTING THE IMPORTANT INPUT EDGES
Selecting the important input edges for node classification and link prediction can be seen in the Algorithm The selection of important input edges for graph classification can be seen in the Algorithm
A.7 EXPERIMENTS
A.7.1 DATASETS
We study node classification task on the YelpChi, YelpNYC (Rayana & Akoglu 2015), Pheme (Zbiigaa al. 2017) and Weibo (Ma al. 2018) datasets. We explore the link prediction tasks on the BC-OTC, BC-Alpha, and UCI datasets. We study the graph classification tasks on MUTAG (Debnath al. 1991), ClinTox, IMDB-BIN BIDB-BINARY and REDDIT-BINAN datasets. The details of data are in Table 2
In the simulated dynamic graphs, we modify edge weights without adding or removing edges. Specifically, given changed ratio we randomly adjust the the weights of | x edges to create evolving graphs. For the real dynamic graph datasets used in the node classification and link prediction tasks, timestamps allow to track graph evolution, which includes modifications edge weights, as well as the addition deletion edges. In graph classification, we apply slight per- turbations to the graphs (You et al. 2018, by randomly adding removing edges altering edge weights.
YelpChi, YelpNYC (Rayana & Akoglu 2015): each node represents a review, product, or user. If a user posts a review to a product, there are edges between the user and the review, and between the review and the product. The data sets are used for node classification.
Pheme (Zubiaga et al. 2017) and Weibo (Ma et al. 2018): they are collected from Twitter and Weibo. A social event is represented as trace of information propagation. Each event has label, rumor or non-rumor. Consider the propagation tree of each event as a graph. The data sets are used for node classification.
17

---

Published as a conference paper at ICLR 2025
Algorithm 4 Selecting important input edges to explain evolution of Pr(Y|Go) to Pr(Y]G1) on the node classification and link prediction tasks
Input: the source graph Go and the destination graph G1, Pre-trained GNN parameters 0
2: Obtain the changed edges set A = fauv agyv abv, t E (1....,T) T.UUU U,
yo UV!)
3: Initialize layer edges contribution matrix Φb E [R k an all-zero matrix
4: Obtain the altered massage flows set AF {F F = F(1 F((....F(T)... F[t- +
0.0
1.4
[F]tt1]]F(t. ,.
5: The node classification task then
6: Given the target node J, AF = {F: F AF and F[T] = J
7: else if The link prediction task then
8: Given the target edge TJ, AF = (F F AF and (F(T) = or F(T) = J))
9: end if
10: for F in AF do
According to the Eq. message flow contribution
(node classification) or Eq. (link prediction), calculate the
obtain the changed edges set A&F (aF(L-1]F14) : o Fi * a on this flow
13: for [ in AEF do According to the Section 3.2 calculate Φazz milh (F).
Let the (F[t-1]=[[( the I-th edge in AE, 11 = 41 Wa (F)
16: end for
17:
end for
18: Solving the Eq. 17 (node classification) Eq.
18 (link prediction) to obtain the important
changed input edges
Output: The important changed input edges set
Algorithm Selecting the important input edges explain evolution of Pr(Y to Pr(Y]G() on the graph classification tasks
1: Input: the source graph Go and the destination graph G1, Pre-trained GNN parameters 0 O.f 1.t 2: Obtain the layer edges flow set AA = {abv .iv * avv, / E (1....,T), U.V E D U
3: Obtain the altered massage flows AF IF: (F[0), ..... Fll... F(T]), 0.t F1--IF +
"F[11]=F11"" t 1.
1.1
4: for for 1 to |A do
5: Initialize layer edges contribution matrix o' E RIV ix as an all-zero matrix
6: end for
7: for F in |F do
8: According to the Eq. 14
calculate the message flow contribution C
9: obtain the changed edges set AEF (amt-11774) a d3p-111F1 * 1 on this flow
for ( in AE do According to the section
11:
3.2 calculate - (F)
12:
Let the a=111111 is the 1-th layer edge in AE, F[T is the i-th node in the D U v1 = 9037-117799 (F)
Φ
13:
end for end for
15: Solving the Eq. 19) to obtain the important changed input edges
Output: The important changed input edges set
18

---

Published as a conference paper at ICLR 2025
BC-OTdHam and BC-Alpha who trusts-whor network of bitcoin users trading the platform. The data sets are used for link prediction.
UC is an online community of students from the University of California, Irvine, where in the links of this social network indicate sent messages between users. The data sets are used for link prediction.
MUTAG (Debnath et al. 1991 A molecule is represented as graph of atoms where an edge represents two bounding atoms.
ClinTox (Gayvert et comppaesssares drugs approved through FDA and drugs eliminated due to the toxicity during clinical trials.
IMDB-BINARY is movie collaboration datasets. Each graph corresponds to an ego-network for each actor/actress, where nodes correspond actors/actresses and an edge drawn betwen two actors/actresses if they appear in the same movie. movie.Each graph is derived from pre-specified genre movies, and the task is to classify genre graph is derived from.
REDDIT-BINARY is balanced datasets where each graph corresponds to an online discussion thread and nodes correspond to users. An edge was drawn between two nodes if at least one of them responded to another's comment. The task is to classify each graph to a community or subreddit it belongs to.
Table 2: The details of datasets
Datasets
Nodes/Avg. Nodes)
Edges(Avg. Edges)
task
Accuracy(AUC)
VelpChi
105,659
375,239
node classification
0.8477
YdpNYC
520,200
1,956,408
node classification
0.8743
weibo
4,657
node classitication
0.9549
pheme
5,748
node clussification
0.7621
BC-OTC
5,881
35.588
link prediction
0.9388
BC-Alpha
prediction
UCT
1,899
59,835
link prediction
0.9061
MUTAG
17.93
19.79
graph classilication
0.75
ClinTox
26.1
55.5
graph classification
0.9874
IMDE-BINARY
19.8
193.1
graph classification
0.8
REDDIT-RINARY
graph classification
Table The changed ration on different datasets
YelCChi
YepNYC
Weibo
Pheme
BC-OTC
BC-Alphu
UCI
MUTAG
ClinTox
IMDE-
REDDIT- BINARY
0.5
0.6
0.4
A.7.2 BASSLINES
GNNExplainer is designed to explain GNN predictions for node and graph classification on static graphs. We train the explainer on graphs Go and G1 to obtain the edges contribution t0 and 11 The final edges contribution is given by + = क T if the predicted class on Go and G1 are different. Otherwise, & $. The top-K edges are selected based on as the explanations.
PGExplainer learns approximated discrete masks for edges to explain the predictions, with im- portant edges selected in the same manner GNNExplainer.
GNN-LRP utilizes the back-propagation attribution method LRP GNN (Schnake et al. 2020 attributing the class probability Pr(Y = ks/11 to input neurons regardless of (TY)) thereby obtaining contribution scores for message flows. It uses summation function map these tributions to edges, with edge selection consistent with GNNExplainer.
html
htm
19

---

Published as a conference paper at ICLR 2025
DeepLIFT (Shrikumar et al. 2017 klGu) and Pr(Y = R1G1), where k o k', to the message flows. Then it uses a summation func- tion to obtain contributions of edges. The edge selection process is consistent with GNNExplainer.
attributes the log-odd between two probabilities Pr(Y
FlowX applies the Shapley value to derive initial contributions of message flows, subsequently training these scores by defining loss functions. summation function employed to map con- tributions to edges, with edge selection aligned with GNNExplainer.
a variant of Axioml Layerede that selects the top layer edges based on the highest contributions 11, where 1 is all-1
Layeradge-
vector.
AdiomEdge maps the contribution of message flows to the input edges also using the Shapley value. See Algorithm
4 and Algorithm in the Appendix A.6 for details.
TxoomEdge-Topk is variant of AdiomEdge that selects the top edges with the highest contribu- tions 1 where dg is the contribution matrix of the altered edges, 1 is an all-1 x 1 vector.
A Shapley is a variant of AxiomEdge that utilizes the average function instead of the Shapley value when mapping contributions of message flows to edges.
AxiomLayeredge Shaaley is a variant of AxiomLayeredge that utilizes the average function instead the Shapley value when mapping the contribution of message flow to layer edges.
A.7.3 EXPERIMENTAL SETUP
We trained the two layers GNN. utilizing element-wise The logit for node is denoted by GG) For node classification, 2J(G) is mapped to the class distribution through the softmax function. For the link prediction, we concatenate (r and ZG( as the input to a linear layer to obtain the logits, which are then mapped to the probability of the existence of the edge (I, J). For the graph classification task, the average pooling of 2, (G) across all nodes in G' can produce single vector representation z(G) for classification. It can be mapped to the class probability distribution through the softmax function. During training, we the learning rate to 0.01, the dropout rate to 0.2 and the hidden size to 16. The model is trained and then fixed during the prediction and explanation stages.
the aggregation function SAGG-
A.7.4 THE PREDEFINED SPARSITY
On the real dynamic graphs, the sparsity of explanations across various datasets and tasks is illus- trated in Table The sparsity of simulated dynamic graphs is illustrated in Table The sparsity small, but our method can also achieve the better performance than the baselines.
Table 4: The sparsity of explanations on real dynamic graph datasets
Datasets
Sparsity level
Sparsity level
Sparsity level
Sparsily level
Sparsity level 5
YelpChi
0.996
0.992
0.988
0.994
0.98
YelNNYC
0.996
0.994
weibo
0.996
0.993
0.99
0.986
0.982
pheme
0.98
0.94
0.92
0.9
BC-OTC
0.996
0.995
0.994
0.993
0.992
BC-Alpha
0.993
0.991
UCI
0.998
0.997
0.996
0.994
0.992
MUTAG
0.988
0.976
0.964
0.952
0.94
ClinTox
0.991
0.982
0.973
0.964
0.954
IMDE-BINARY
0.996
0.991
0.988
0.984
0.98
REDDIT-BINARY
0.998
0.997
0.996
0.995
0.994
A.7.5 EVALUATION METRIC
In Figure 7 we illustrate the calculation process of evaluation metric.
A.7.6 PERFORMANCE EVALUATION AND COMPARISON
We compare the performance of the methods across three tasks: node classification, link predic- tion and graph classification in simulate dynamic graph scene, illustrated in Figure 8. For
20

---

Published as a conference paper at ICLR 2025
Table 5: The sparsity explanations on different simulated graph datasets
Datasets
Sparsity level
Sparsity level
Sparsity level 3
Sparsity level
Sparsity level 5
YelpChi
0.999
0.998
0.997
0.996
0.995
YelpNYC
0.9994
0.9988
0.9981
0.9975
0.9966
weibo
0,9972
0.9945
0.992
0.989
0,986
pheme
0.982
0.963
0.945
0.927
0.908
BC-OIC
0.967
0.95
0.935
0.918
0.9
BC-AIpha
0.79
UCT
0.999
0.998
0.997
0.996
0.995
MUTAG
0.988
0,976
0.964
0.952
0.94
Toi
0,99
0.98
0.97
0.96
0.95
0.988
REDDIT-BINARY
0.998
0.996
0.994
0.992
0.99
Go
The selected layer edges
G₂
G1
0.2
0-
0.2
0.3
0.1
KL
+
0.2
0.3
0.4
t=1
0L0Z
0.2
0.3
0.4 0
0.3
0
0.42
0.42
Figure The calculation process of evaluation metric.
each dataset, we report the average KL over target nodes/edges//raaph. From Figure g we can see that our method AxiomLayeredge has the smallest KL across all levels of explanation sparsity and datasets and tasks, with exception of Weibo, Pheme and certain sparsity levels of YeCpNYC dataset. In datasets with dense graph structures (YelpChi, YelpNYC, BC-Alpha, BC-OTC, UCI, IMDB- BINARY REDDIT-BINAYR), the AxiomLayeredge- that our designed message flow contribution value Algorithm can effectively explain the dynamic graphs. In seven experimental settings (Weibo, YelpChi, YelpNYC, BC-Alpha, UCI, MUTAG, ClinTox),, our method Axioml Layerede along with variants AxiomEdge, AxiomEdge' (Shalley, AxiomLayeredge Shapley outperform the GNNLRP, DeepLIFT, GNNExplainer, PGExplainer and FlowX methods. This demonstrates that our proposed methods more effectively explain the evolu- tion of Pr(Y|Gu 0) to Pr 0), while methods designed for static graph struggle to identify salient edges that explain changes in the predicted probability distribution.
method ranks third. This indicates
Shaipleyy
A.7.7 RUNNING TIME
We plot the rumning time for searching AF, calculating message flow contributions, using the Shapley value attribute contributions to layer edges, and selecting important layer edges on the Pubmed, Coauthor-Computer and Coauthor-Physics datasets. The details of these datasets are shown in the Table 6 As shown in Figure the larger AA lead higher cost in the selecting step compared to the other steps. The time for calculating contributions and applying the Shapley value remains relatively small, even for larger graphs. On large graphs, the searching and selecting steps dominate the running time, but the overall time remains manageable, In practice, incremental mes- sage flow searches tailored specific graph topologies and more efficient optimization algorithms can further speed up the process.
In citation network, PubMed (Kipf & Welling 2017). each paper has bag-of- words features, and the goal is to predict the research area of each paper.
and Coauthor-Physice demic Graph from the KDD Cup 2016. We represent authors as nodes, that are connected by an edge if they co-authored paper (Shchur et al. 2018). Node features represent paper keywords for each author's 's papers.
Coauthor-Comen
co-authorship graphs based the Microsoft Aca-
21

---

Published as a conference paper at ICLR 2025
Pheme
Welbo
YebOC
YeloVYC
1.6
2.5
12
0.150
0.125
1.5
0.100
1.0
02
0.5
0.05
0.025
0.00
0.000
2
Expleration spereily leveds
Explanatio opersily levelo
Explanstio sparsity levels
Explenation spersily sity levwe
0.30
BC-Alpha
BC-OTC
UCI
GNNExplamer
0.5
PGExphiner
0.25
0.35
GNN-LRP
0.20
0.25
Rowk
DeepLIFT
3 0.15
5
AutomEdge/Shapttry
0.10
0.2
0.15
AxiomEdge
0.05
0.1
0.05
AdiumEdge
AyyoenLy Topk
0.00
0.0
Layoodddd
Explariation sparsily levels
Explanatio sparally pariily levala
5
Explondion sparsily levala
2
3
AubomaayerodgeSShastey
CoinTox
REDDIT-BINARY
0.12
0.10
0.35
0.50
0.14
0.30
0.08
0.25
0.10
6.08
0.20
0.44
0.15
0.22
0.10
0.04
2
Explanation sparsity lovels
Explanation sparsty levels
Explanztio sparsity lovals
Explanation sparsity lovels
Figure 8: Performance in KL Go Ct. Each column corresponds to different dataset. The first, second and third rows represent node classification, link prediction and graph classification tasks, respectively.
Table 6: Three large graph datasets
Datasets
Classes
Nodes
Edges
Edge/Node
Features
PubMed
19.717
44,324
2.24
Soantho--Coppute
13
18,333
327,576
17.87
6,805
Coauthor- Coautbor-Physles
2
34,493
991,848
28.76
8,415
A.7.8 VISUALIZATION AND ACCURACY ON THE BA-SHAPES DATESET
On the BA-Shapes dataset, we randomly generated 1,000 graphs with a House motif and 1,000 with Circle motif. For each motif dataset, randomly deleted one edge to disrupt the motif and perturbed edges outside the motif area, generating another 1,000 graph datasets. We trained a GNN model to classify the presence of the motif. We applied explanation methods to select one edge. If the selected edge disrupts the motif, the explanation is correct, while if the edge lies outside the motif area, the explanation is wrong. The accuracy results for GNN and the explanation methods are presented in Table and Table 7 respectively. Visualization of the explanations for the House and Circle motifs are shown in Figure 10 and Figure II
Table 7: The accuracy explanation methods
Datasets
our
GNNExplainer
PGEsplainer
DeepL.IFT
GNN-LRP
FlowX
Circle-moti
0.9657 0.9936
0.9067 0,3618
0.4765 0.6025
0.8848
0.1152
0.4156
House-motir
0.9897
0.1755
0.0238
22

---

Published as a conference paper at ICLR 2025
Pubmed
Pubmed
Averoge runniing time (in second)
Search message flow ate Contributions
Calculate Contributions
Apply Shapley value
0.6
Shapley value Select layer edges
nunning
0.4
(in
950
3873
2768
37V5
4617
5532
5487
7303
5532
number changed layer edges
number changed layer edges
Coauthor-Computer
Coauthor-Computer
Search message flow
Calculate Contributions
Average runningg time (in second))
0.8
Calculate ate Contributtions
Apply Shapley value
Apply Shapley value
Average running
40
Select layer edges
20
0.2
860
2282
1179
3835
1280
0025
8ELS
4502
5280
0022
changed layer edges
number changed edges
Coauthor- Soauthor-Physics
Coauthor Physsis
Average runninng time
Search message flow
Average running time
15
Calculate Contributions
Contributions
Apply Shapley
(in secords
Apply Shapley value
Select layer edges
1.00
7439
12940
15905
18140
23318
120
13990
number changed edges
The number changed edges
Figure 9: Running time decomposition: Each row represents a dataset. The first column shows the total
running time for all four steps, while the second column displays the running time for calculating contributions applying the Shapley value.
Table 8: The accuracy of GNN model
Datasets
GCN
Circle-matif 0.755
House-motif 0.847
A.7.9 PERFORMANCE EVALUATION ON DISCONTINUOUS CHINNGES OF EDGES
We evaluate the effectiveness of method node classification, link prediction, and graph clas- sification tasks under discontinuous edge changes. As shown in Figure 12 our method outperforms others across all five datasets, further validating its effectiveness.
23

---

Published as a conference paper at ICLR 2025
Oid
Our
ENNExplalner
DeepLIFT
New graph
PGExplaner
Figure 10: The visualization of Housc-motif dataset. The blue edges represent changes in edge weights. In the new graph, the edge (12, 13) is removed destroy the motif, and the weights of edges (0, 1). (2,3), (0, 4), (13, 3), and (0, S) are perturbed. The edge (12, 13) serves as the ground truth for explanation, clarifying why the old graph contains a house while the new graph does not. The red edge represents the selected edge by different methods. Our method correctly identifies (12, 13) as the explanation, while other methods select the wrong edge.
DapLPtt
graph
PUbader
C'eUu
Figure 11:
The visualization of Circle-motif dataset. The blue edges represent changes in edge weights. In the new graph. the edge (10, 11) removed destroy the motif, and the weights of edges (0, 1). (0. 4), (0, 2). (0, 5) are perturbed.
edge (10. 11) serves the ground truth for the explanation, clarifying why old graph contains a circle while the new graph does not. The red edge represents the selected edge by different methods. Our method correctly identifies (10, 11) as the explanation, while other methods select the wrong edge.
24

---

Published as a conference paper at ICLR 2025
Pheme
Weibo
BC-Alpha
0.14
1.4
0.12
0.6
1.2
0.10
1.0
0.4
0.8
0.08
0.6
0.08
0.2
0.4
0.04
0.2
0.02
Explanation sparsity levels
Explanation sparsity levels
Explanation sparsity levels
BC-OTC
IMDB-BINARY
GNNExplainer
0.18
PGExplainer
0.16
0.10
GNN-LRP
0.14
DeepLIFT
0.12
0.08
FlowX
0.10
AxiomEdgelShapley
0.06
0.08
AxiomEdge
0.06
0.04
AxlomEdge-Topk
0.04
AviomLayoredge-Toph
AxiomLayeredge
3
2
5
AxiomLayeredggeeSnallyy
Explanation sparsity levels
Explanation sparsity levels
Figure 12: Performance KL Go - Gi when only adding or deleting edges. Each column corresponds
to a different dataset.
25


Reviews:
[{"review_id": "ngGZy0CWB3", "reviewer": "Reviewer_d3Hv", "summary": "The paper presents Axiom Layer Edge, a novel explanation framework designed for dynamic graph learning models, particularly focusing on Graph Neural Networks (GNNs). The framework aims to identify the most influential \"layer edges\" — connections within the GNN layers that have a significant impact on the model’s predictions. This approach is based on the use of Shapley values to fairly attribute contribution scores to individual layer edges and provides a principled and interpretable explanation for prediction shifts that occur as the graph changes over time. The results on several datasets and graph task show that method outperforms other existing baseline methods.", "questions": "- It would be helpful if the authors can justify the use of Shapley value instead of other game-theoretic methods  (e.g., core, Banzhaf etc)?\n- How can we approximate the calculations of shapley and KL divergence in large/dynamic graphs?\n\n- Can we have a discussion on the usefulness of the explanations from the point of view domain experts? Also, are the explanations stable to graph operations like attention, pooling, etc.?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The work focuses on problem of explainability in evolving/dynamic graphs which is an important task\n- Extending concepts of shapley value to many dynamic graphs is also key contribution of the work\n- The work aims to focus on the trade-offs between quality of interpretablity and fidelity", "weaknesses": "- Applying shapley value and KL divergence to large or highly dynamic graphs can be challenge especially due to combinatorial nature of computation\n- No theoretical analysis on computation complexity is provided for evolving graphs\n- There are several limitations with Shapley such as the lack of robustness, stability etc [1]. It is unclear what are the limitations of Shapley in this setting. \n\n[1] Kumar, I. Elizabeth, Suresh Venkatasubramanian, Carlos Scheidegger, and Sorelle Friedler. \"Problems with Shapley-value-based explanations as feature importance measures.\" In International conference on machine learning, pp. 5491-5500. PMLR, 2020.", "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": "HUtfRhlWde", "reviewer": "Reviewer_7mCd", "summary": "This paper works on the problem of explaining challenges in GNNs' predictions when the weights of the input edges are continuously changing. Prior work has weaknesses in axiomatic attribution of message flows, unfair distribution, and optimality. The proposed algorithm from the authors addresses the challenges by decomposing the changes in the message flow and introducing the Shapley value for fair attribution. Extensive experiments have been conducted to show the effectiveness of the proposed method. The paper is well-written and organized.", "questions": "1. There are typos in line 221. Please carefully check them.\n2. As the goal of this paper is to understand how GNN predictions respond to the evolution of graphs. However, in this paper, the GNNs are all static GNNs. What is the effectiveness of the proposed method in explaining the dynamic GNN methods? For example, TGN or TGAT?\n3. What is the relationship between the Shapley value through temporal dimension? Does the proposed method capture the influence of evolving nature in dynamic graphs?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The intuition behind this paper is interesting and novel. The design of the framework is feasible and detailed explained. There are also sufficient experiments to demonstrate the effectiveness of the proposed methods.", "weaknesses": "The goal of this paper is to address the challenges of explanation on GNN in evolving graphs. Thus, it should include more dynamic graph baselines instead of simply using static GNNs. Besides, the authors should introduce more on the relationship between the proposed evaluator through the temporal dimension.", "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": "SSmRwYvFHa", "reviewer": "Reviewer_aPrr", "summary": "This paper introduces a method for the explainability of evolving graphs, where edge weights of a graph changes over time. The authors explore this problem across three tasks of node classification, link prediction, and graph classification and show that their approach demonstrates superior performance compared to other baselines. Furthermore, in their problem setting Pr(Y |G0; θ) will evolve to Pr(Y |G1; θ), and they aim to explain the evolution of Pr(Y |G; θ) with respect to G0 → G1. They formulate the changes in hidden vectors on G0 and G1 and apply chain rule of DeepLIFT to assign the changes in logits to message flows. Finally, they show that their approach outperforms other baselines on KL divergence metric.", "questions": "- What pre-trained GNN has been used in this work?\n- Could you provide visualizations of your results for datasets such as MUTAG?\n- What is the rational behind choosing KL divergence as the evaluation metric?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem of explainability for Graph Neural Networks (GNNs) in the context of evolving graphs is both interesting and novel. \n\n- The proposed model demonstrates superior performance compared to other baseline methods.", "weaknesses": "- The metric used for evaluation is not clearly justified. There are standard metrics, such as fidelity, that could provide a better understanding of the method's performance.\n- For an explainability method, it is crucial to include at least one visualization of a dataset. This would allow readers to visually assess the method's effectiveness.\n- It would be beneficial to experimentally demonstrate that this method works with different Graph Neural Networks (GNNs). Additionally, including a table that shows the performance of the pre-trained GNNs across various datasets would be helpful.", "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": "09N1AWBozF", "reviewer": "Reviewer_KvnM", "summary": "This paper provides explanations for predictions on evolving graphs. In the case of continuously changing edge weights, the authors propose an explanation method based on Axiomatic Layer Edges, mapping the contribution of message flows to layer edges using Shapley values, and selecting key layer edges by minimizing the KL divergence optimization problem. Experimental results show that this method outperforms existing baseline methods across multiple datasets and tasks.", "questions": "See Weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper presents an explanation method based on layer edges, which can more accurately capture the variations in message passing, thereby improving the fidelity of the explanations. The method is innovative.\n2. The authors explain prediction changes by selecting a small number of key layer edges at multiple scales through a KL divergence-based optimization problem.\n3. The paper conducts experiments on multiple datasets and tasks, including node classification, link prediction, and graph classification tasks.", "weaknesses": "1. The authors should conduct a complexity analysis, as the computation of Shapley values generally has a high complexity. Additionally, since the authors select a small number of key layer edges in their method, will this impact the complexity of the model?\n2. In this paper, the authors use a series of carefully designed methods to balance the fidelity and interpretability of explanations. However, I still have a question: is there an optimal balance point (for example, the optimal point reached in Figure 2(b))?\n3. The paper assumes that changes in edge weights are continuous; however, could the authors also explore sudden or discontinuous changes (such as the addition or deletion of nodes or edges)? Changes in graph structure can be quite complex and unpredictable, which may affect the robustness of the 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": {}}]

Author rebuttal:

Decision: Accept (Poster)