A Differential Geometric View and Explainability of GNN on Evolving Graphs
Authors: Yazheng Liu
Xi Zhang
Sihong Xie
Venue: ICLR 2023 poster (2023)

Abstract: Graphs are ubiquitous in social networks and biochemistry, where Graph Neural Networks (GNN) are the state-of-the-art models for prediction. Graphs can be evolving and it is vital to formally model and understand how a trained GNN responds to graph evolution. We propose a smooth parameterization of the GNN predicted distributions using axiomatic attribution, where the distributions are on a low dimensional manifold within a high-dimensional embedding space. We exploit the differential geometric viewpoint to model distributional evolution as smooth curves on the manifold. We reparameterize families of curves on the manifold and design a convex optimization problem to find a unique curve that concisely approximates the distributional evolution for human interpretation. Extensive experiments on node classification, link prediction, and graph classification tasks with evolving graphs demonstrate the better sparsity, faithfulness, and intuitiveness of the proposed method over the state-of-the-art methods.

Published as a conference paper at ICLR 2023
A DIFFERENTIAL GEOMETRIC VIEW AND EXPLAIN- ABILITY OF GNN ON EVOLVING GRAPHS
Yazheng Liu', Xi Zhang', Sihong Xie
"Key Laboratory of Trustworthy Distributed Computing and Service (MoE), BUPT, Beijing, China "Department of Computer Science and Engineering, Lehigh University, Bethlehem, PA, USA [liuyz, zhangx edu. en, xiesihongl hamplllmmmmm.m..mmm com
ABSTRACT
Graphs are ubiquitous in social networks and biochemistry, where Graph Neural Networks (GNN) are the state-of-the-an models for prediction. Graphs be evolving and is vital to formally model and understand how a trained GNN re- sponds graph evolution. We propose a smooth parameterization of the GNN predicted distributions using axiomatic attribution, where the distributions are on low-dimensional manifold within high-dimensional embedding space. We exploit the differential geometric viewpoint to model distributional evolution as smooth curves on the manifold. We reparameterize families of curves on the manifold and design a convex optimization problem to find a unique curve that concisely approximates the distributional evolution for human interpretation. Ex- tensive experiments node classification, link prediction, and graph classifica- tion tasks with evolving graphs demonstrate the better sparsity, faithfulness, and intuitiveness of the proposed method over the state-of of-the-art methods.
INTRODUCTION
Graph neural networks (GNN) now the state-of-the-art method for graph representation in many applications, such as social network modeling Kipf & Welling (2017) and molecule property pre- diction Wu al. (2018), pose estimation
computer vision Yang al.] (202I), smart cities Ye let al. (2020), fraud detection Wang et al. (2019), and recommendation systems Ying et al. (2018). A GNN outputs a probability distribution Pr Pr(Y|c: 0) of Y, the class random variable of node (node classification), a link (link prediction), or graph (graph classification), using trained parameters 0. Graphs can be evolving, with edges/nodes added and removed. For example, social networks are undergoing constant updates Xu et all (2020a); graphs representing chemical compounds are constantly tweaked and tested during molecule design. In a sequence graph snapshots, without loss of generality, let Go + G1 be any two snapshots where the source graph Go evolves to the destination graph G1. Pr(Y Go; O) will evolve to Pr(Y|G1;; 0) accordingly, and we aim to model and explain the evolution of Pr O) with respect to Go G to help humans understand the evolution Ying et al. (2019); Schnake et al. (2020): Pope et al. ) Ren et al.) (202T): Liu et al.) (202I). For example. a GNN's prediction of whether chemical compound is promising for target disease during compound design can change as the compound is fine-tuned, and it is useful for the designers understand how the GNN's prediction evolves with respect to compound perturbations.
To model graph evolution, existing work Leskovec et al. 2007 2008) analyzed the macroscopic change in graph properties, such as graph diameter, density, and power law, but did not analyze how a parametric model responses to graph evolution. Recent work Kumar et al. (2019); Rossi et al. (2020); Kazemi et al. 2020); Xu et al. (2020bla) investigated learning model for each graph snapshot and thus the model is evolving, while we focus on modeling a fixed GNN model over evolving graphs. more fundamental drawback of the above work is the discrete viewpoint of graph evolution, individual edges and nodes are added or deleted. Such discrete modeling fails to describe the corresponding change in Pr 0), which is generated by a computation graph that can be perturbed with infinitesimal amount and can be understood as a sufficiently smooth function. The smoothness can help identify subtle infinitesimal changes contributing significantly to change in Pr(Y GG; O) and thus more faithfully explain the change.

---

Published as a conference paper at ICLR 2023
(ps. 1]
Manifold GNN predlicted distributions
Pr:
T2(()
(r(())
Differentible evolution curves
(pI.1)
(Cy(Gr,G))
(p2.1)
(pr. k-+
Go
Discrete evolution
G1
1) (K +
(pa, 1)
Go at time time = 0 is updated to G1 at time = 1 after the edge (J, K) is added, and the predicted class distribution (Pr(Y]Goo) of node J changes accordingly. The contributions of each path p a computation graph to Pr(Y j|G) for class j give the coordinates of Pr(Y[G) Euclidean space, with axes indexed by (). Pr(Y (G) varies smoothly on a low dimensional manifold, where multiple curves 78) can explain the evolution from Pr(Y]Co) to Pr(Y[Gi) at very fine-grained. We select a (s)) that use sparse set of axes for explaining the prediction evolution. Edge deletion, mixture of addition and deletion, link prediction, and graph classification handled similarly.
Figure 1:
high-dimensional
Regarding explaining GNN predictions, there is promising progress made with static graphs, in- cluding local or global explanation methods Yuan et al. (2020b). Local methods explain individual GNN predictions by selecting salient subgraphs Ying et al. (2019). nodes, edges Schhake et al.) (2020). Global methods Yuan et al.] (2020a); | Vu Thai (2020) optimize simpler surrogate mod- els to approximate the target GNN and generate explaining models or graph instances. Existing counterfactual or perturbation-bant vidual edges or nodes by optimizing perturbation to the input graph to maximally alter the target prediction, thus giving a sense of explaining graph evolution. However, the perturbed graph found by these algorithms can differ from Go. and thus does explain the change from Pr(Y Go; 0) to Pr(Y]G1; f). Both prior methods DeepLIFT [Shrikumar et al. (2017) and GNN-LRP Schnake et al. (2020) can find propagation paths that contribute prediction changes. However, they have fixed Go for any G₁ and thus fail to model smooth evolution between arbitrary Go and G1. They also handle multiple classes independently [Schnake et al., (2020) or uses the log-odd of two predicted classes Y = and Y j' to measure the changes in Pr(Y (G; Shrikumar et al. (017)). rather than the overall divergence between two distributions.
methods Lucic et al. (202T) attribute a static prediction to indi-
To facilitate smooth evolution from Pr(Y|Go; 0) to Gr;)) (we ignore the fixed 0 in the se- quel), in Section 3.1 we set up coordinate system for Pr(Y using the contributions of paths on the computation graphs to Pr(Y (G) relative to global reference graph. We rewrite the distribution Pr(Y|G) for node classification, link prediction, and graph classification using these coordinates, so that Pr(Y|G) for any graph G is embedded in this Euclidean space spanned by the paths. For classification, the distributions Pr(Y have only c - 1 sufficient statistics and form an intrinsic liwdeeenniooall manifold embedded in the constructed extrinsic embedding Euclidean space. In Section 3.2) we study the curvature of the manifold local to a particular Pr(Y We derive the Fisher information matrix I of Pr(Y /G) with respect the path coordinates. As the KL-divergence between Pr(Y and Pr(Y]G;, that are sufficiently close can be approximated by quadratic function with the Fisher information matrix, Pr(Y|G) does not necessarily evolve linearly in the extrinsic coordinates but adapts to the curved intrinsic geometry of the manifold around Pr(Y|G)) Previous explanation methods (hhrikumar al. (2017); [Schnake et al. (2020) taking a linear view point will not sufficiently model such curved geometry. Our results justify KI KL-ddiergennce as a faith- fulness metric of explanations adopted in the literature. The manifold allows a set of curves 7s)) with the continuous time variable [o, 1] to model differentiable evolution between two distri- butions. With a novel reparameterizzation, we devise a convex optimization problem to optimally select curve depending
small number of extrinsic coordinates to approximate the evolution of Pr(Y GG) into Pr(Y [G,) following the local manifold curvature. Empirically, in Section 4 we show that the proposed model and algorithm help select sparse and salient graph elements
2

---

Published as a conference paper at ICLR 2023
cisely and faithfully explain the GNN responses to evolving graphs on 8 graph datasets with node classification, link prediction, and graph classification, with edge additions and/or deletions.
PRELIMINARIES
Graph neural networks. For node classification, assume that we have trained GNN Tf layers that predicts the class distribution of each node J E V on a graph G = (V,E). Let (J) be the neighbors of node J. On layer i, l t- I,...,
1,.,,..,,
and for node J, GNN computes hidden vector j
using messages sent from its neighbors:
2 (0)
= J AG0 (h) (h)- .nk 1-"") K KEN())))
(1)
NonLinear(z))) (9)
(2)
where fA0o aggregates the messages from all neighbors and can be the element- sum, average, or maximum of the incoming messages. ( SUPDATE maps fAGG z using z ( o or
a multi-layered perceptron with parameters O For layer t E {I...., T 1}. ReLU is used as the NonLinear mapping, and refer to the linear terms in the argument of NonLinear "logits". At the input layer, (") the node feature vector xJ. At layer T. the logits are 2!?") - (G), whose j-th element (G) denotes the logit of the class j ,... ZJ( is mapped to the class distribution Pr(Y)]G; 0) through the softmax (c > 2) or sigmoid (c = 2) function, and arg max; 2j arg max, Pr(Y = j|G; 0) is the predicted class for J. For link prediction, concatenate 217 and 2!,") as the input to linear layer to obtain the logits:
2 (T)
Zrs
Since link prediction a binary classification problem, Zr can mapped to the probability that (I, J) exists using the sigmoid function. For graph classificution, the average pooling of x. of all nodes from can be used to obtain a single vector representation z(G) of G for classification.
Since the GNN parameters O are fixed,
we ignore O in Pr(Y|G; 0) and use Pr(Y]G) to denote the predicted class
Table 1: Symbols and their meanings
distribution of Y. which is a general ran-
Symbols
Detniiions and Descriptions
dom variable of the class of a node, an edge, or a whole graph, depending on the tasks. Similarly, we use (!!) and to denote logits on layer & and the last layer of GNN, respectively. For uniform treatment, we consider the GNN as learning node representations z.. while the concatenation, pooling, sigmoid, and softmax at the last layer
U.V....,
Nodes the graph
Neurons of the corresponding modes
The number of classes
Go G1
Graph Go evolves
*z(G)
Logit vector [x] (G),
(.) of node J A G1] (G1) - (Go
Azj(Go, G1)
Pr(Y]G)
Distribution [Pr, (G), (G)..... Pre(G)) class Y
W(G)
Paths on the computation graph of GNN
(G)
The subset of (G) that computes (G)
AW G.)
Altered paths in W (C.)) as Go + G₁
Cp.i
Contribution of the p. altered path to Az
that generate Pr(Y[G) from the node representations are task-specific and separated from the GNN.
Evolving graphs. In sequence of graph snapshots, let Go (Vo, En) denote an arbitrary source graph with edges E, and nodes Vo. and G1 = (Vi, an arbitrary destination graph, so that the edge set evolves from Eo to ε, and the node set evolves from Vo to V1. We denote the evolution by Go + G₁. Both sets can undergo addition, deletion, or both, and all such operations happen deterministically so that the evolution is discrete. Let AE be the set of altered edges: AE {e le:ee E E Ae e & Eo ore E Eo Ae e & & As Go - G1, there is an evolution from Pr(Y Go) to PrtY)
Definition (Differentiable evolution): Given fixed GNN model, for Go + G1. find a family of com- putational models (Pr(Y s E [0, 1]. Pr(Y [G()) = Pr(Y|),,, Pr(Y Pr(Y()(()) = Pr)) and G(s)) is differentiable with respect to the time variable s.
Differential geometry. An n dimensional manifold M is a set of points, each of which can be associated with local n dimensional Euclidean tangent space. The manifold can be embedded in
A computational model that outputs Pr(y G(s)) does not necessarily correspond to concrete input graph G(s). We use the notation Pr))) and G(s) for notation convenience only.
3

---

Published as a conference paper at ICLR 2023
global Euclidean space R", that each point can be assigned with global coordinates. A smooth curve on M is a smooth function y [0, 1] + M. A two dimensional manifold embedded in R with two curves is shown in Figure I
3 DIFFERENTIAL GEOMETRIC VIEW OF GNN ON EVOLVING GRAPHS
3.1 EMBED A MANIFOLD OF GNN PREDICTED DISTRIBUTIONS
While manifold general is coordinate- free. we aim to embed manifold in an extrinsic Euclidean space for a novel parameterization of Pr(Y|G). The GNN parameter 0 is fixed and cannot be used. Pr(Y[G) given by the softmax or sigmoid of the sufficient statisties z(G), which are used as coordinates in information geometry |Amari (0016). However, the logits sit at the ending layer of the GNN and will not fully capture how graph evolution influences Pr(Y|G) through the changes in the computation of the logits. GNNExplainer Ying et al. (2019) adopts soft llement-wise mask over node features or edges and thus parameterize Pr(Y using the mask. However, the mask works the input graph (edges node features), without revealing changes in the internal GNN computation process.
We propose a novel extrinsic coordinate based the contributions of paths Pr(Y[G) the computation graph of the GNN. (G( is generated by the computation graph of the given GNN, which is a spanning tree rooted J of depth I', Figure shows two computation graphs for Go and G1. On computation graph, each node consists of neurons for the corresponding node in G, and we use the same labels (I, K, L, etc.) to identify nodes in the input and computational graphs. The leaves of the tree contain neurons from the input layer (t = 0) and the root node contains neurons of the output layer (1 = T). The trees completely represent the computations in Eqs. (1(2). where each message is passed through path from a leaf to the root. Let path be (....
J),
where U and V represent any two adjacent nodes and J is the root where z. generated. For a GNN with T layers, the paths sequences ' + 1 nodes. Let WG( be the paths ending at J.
Consider a reference graph G containing all nodes in the graphs during the evolution. The symmetric set difference (G, G)) (G AG, contains all m paths rooted at J with at least one altered edge when G - G. For example, in Figure D J G) {(J, K, J), JJ (K, J). (L, K, AW) ,G) causes the change z, and Pr(Y|G) through the computation graph. Let the difference in z, computed on G and G be A G) [Azi..... Aze] RRS. We adopt DeepLIFT to GNN (see [hrikumar et al. 2017 and Appendix A.4p to compute the contribution Cp.,(G) of each path p E AW G)
(. GG)
Szy (C) for any class I,...,C, so that [2] (G),... Ze.)) (G) is reparameterized as
m
m
(Zr(G"), de (G*) +
Cp.
Cp,c(G) = =z((")) +TC
(4)
Here, CG) is the contribution matrix with (G) as elements and GG)(G) the j-th column. 1 is an all-1 m x 1 vector. By fixing G and 2. (G" ). we use (G.)(G) as the extrinsic coordinates of (r) In this coordinates system, the difference vector between two logits for node J is:
zz Az, G1) (G)))) 1 -C,)))))GGG))))
1 A Gt). (5)
If set G* = Go. we have (Go G1) (G)) Even with fixed G*, different graphs G and nodes J can lead to different sets of (G" G). We obtain a unified coordinate system by taking the union UG,JeaAW,(G* G). We set the rows of CG(G) zeros for those paths that are not in AW, G). In implementing our algorithm, we only rely on the observed graphs to exhaust the relevant paths without computing UG, G). We now embed Pr(Y G)) in the coordinate system.
Node classification: the class distribution of node J is
Pr(Y softmax(z,((")) = (oftmax(2x_("")+11
(6)
Link prediction: for link JJ) between nodes I and J, the logits z (G) and (G) are con- catenated as input to a linear layer θLP ("LP" means "link prediction"). The class distribution of the link is
Pr(V]G) = sigmoid( (z,(G))) (C(((C): +1 1 [C)(G))OP))
4

---

Published as a conference paper at ICLR 2023
Graph classification: with linear layer dsc ("GC" for "graph classification") and average pool- ing, the distribution of the graph class is
(8) The arguments of the above softmax and sigmoid are linear in C)(G) for all J E V of G. and we recover exponential families reparameterized by C))G). For a specific prediction task, we let the contribution matrices (G) in the corresponding equation of Eqs. O vary smoothly, and the resulting set [Pr(Y[G)} constitutes a manifold MM J). The dimension of the manifold is the same as the number of sufficient statisties of Pr(Y]G),, though the embedding Euclidean space has me (2me and [/, resp.) coordinates for node classification (link prediction and graph classifica- tion, resp.), where m is the number of paths in AW, (Go, G1) and the number of classes.
Pr(Y|G) softmax(mean(zzj) "1"(")))+"c())))))"""""")))""))) V)0Gc).
3.2 A CURVED METRIC ON THE MANIFOLD
We will define a curved metric on the manifold MMG, JJ) of node classification probability distri- bution (link prediction and graph classification can be done similarly). A well-defined metric is vital to tasks such as metric learning on manifolds, which we will use to explain evolving GNN predictions in Section 3.3 We could have approximated the distance between two distributions Pr(Y Go) and Pr(Y G1) by ||CC)(Go, G1)ll with some matrix norm (c.g., the Frobenius norm), as shown in Figure I As another example, DeepLIFT Shrikumar al. (2017) uses the linear term 1 (G.) C.3r (G)) for two predicted classes j and j' on Go and G1. respectively. These op- tions imply the Euclidean distance metric defined in the flat space spanned by elements in (G). However, the evolution of Pr(Y|G) on M(G. J) depends on C)(Go) and C)(Gi) nonlinearly 8 and the difference between Pr(Y Go) and Pr(Y|G1) should reflect the curvatures over the manifold M(G. J) of class distributions.
through the sigmoid or softmax function as in Eqs. (
We adopt information geometry Amari 2016) to defined a curved metric on the manifold M J). Take node classification
example, the KL-divergence DxL (Pr (eNYY//G)llll ((Gr)))llPPY))) (Go) between
any two class distributions on the manifold M J) defined as Ex log Pr(Y|G)))m(y Pr( As
Pr(Y|G,)
the parameter (G)) approaches C)(G)). Pr(Y[Go) becomes close to Pr(Y(G,) (as measured by the following Riemannian metric on M(G.), rather than the Euclidean metric of the extrinsic space), and the KL-divergence can be approximated locally at Pr(Y|G)) as
vec(AC)(G), (G) (ece
Go));
where ve)(Cr(G1) is the column vector with all elements from CG(),,, and similar for rec(AC)(Gr Go)) with the matrix ACJ(G), Go). [(vec(C)(G1)) ))) is the Fisher informa- tion matrix of the distribution Pr(Y]G;) with respect to parameters in (er(C)(G,)), evaluated with (x) =
as (Vre(CCs (G))) Z)
V (G,( log Pr(Y]G.)) being the gradient vector of the log-likelihood with respect to (G and (ex(m)) the Jacobian of (G, w.r.t (e))C)(Gi)). See Martenss (2020) and Appendix A.2 for the derivations). I is symmetric positive definite (SPD) and Eq. (9) dennes a non -on-Eucideann metric on the manifold make M a Riemannian manifold.
V Vec(C )) (
3.3 CONNECTING TWO DISTRIBUTIONS VIA A SIMPLE CURVE
We formulate the problem of explaining the GNN prediction evolution as optimizing a curve on the manifold M. Take node classification as an example ?
Let 8 E [0, 1] be the time variable.
As s + 1. Pr())G(ss) moves smoothly over M along curve (s) E I(Go, G1) (n(s)
(Pr(Y]G(s)) : s E Gr() = Pr(Y Pr(Y (L))) = G1)} C M). Two possible curves (s) and 72(()) are shown in Figure [ With the parameterization in Eqs. (5)
(6). we can specifically define the following curves by smoothly varying the path contributions to
Pr(Y)G((s) through (Z))G(s)) (s can be reversed to move in the opposite direction along (s)).
linear in the directional matrix ACr(Go, G1), with ACr(Go. G(s)) = ACr Gi)s; linear in the elements of (C) Gj): (C, G(s)) = AC G₁) @ X(s). where @ is wlem product and the matrix element X (s) is function mapping s E [0, (0, 1]:
II the Appendix section
A.3 we discuss the cases of link prediction and graph classification.
5

---

Published as a conference paper at ICLR 2023
linear in the rows of AC, G1): let x = p-th path as a whole, and
and xp(s) E [0, 1] weight the
(C, AC Gi) o [xix x @ {()]s,
(10)
where @ is the Kronecker product creating the path weighting matrix lix @ x(s) E [0, 1jme.
According to the derivation in Appendix A.1 we rewrite Dra(P((V(G))IIP(((()) as
Ex-PiYrC, | (C, - Cy)(G))] log Z(Gi) + log Σ [explz((C)++1 j=1
(II)
where the expectation has class sampled from Pr(Y[G1) and log 2(G is the cumulant function
of Gr) In Eq. [I). by letting Go vary along any 7()) as parameterized above and replacing
(G,) with C.yy (G)())
C. (Go) + (G, G(s)), we obtain DKL (Pr(Y)(r)) (r(()
Taking + 1. the curve Pr(Y G(()) enters neighborhood of Pr(Y on the manifold M to approximate Pr(Y (G,) and DRL ( G())) + 0 so that the curve 7(s) parameter- ized by x()) smoothly mimics the movement from Pr(Y|Go) to Pr(Y[Gr), at least locally in the neighborhood of Pr(Y Since ((s) E (Go, G1) MM selecting a curve 7 is differ- ent from selecting some edges from G1 to approximate the distribution Pr(Y G1) as in Ying et al. (2119). Rather, the curves should move according to the geometry of the manifold M(G
We can use Eq. 11 to explain how the computation of Pr(Y]Go) evolves to that of Pr(Y]G,) following (ss). There are me coordinates in (G(()))), and can be large when J is a high- degree node, while explanation should be concise. We will identify curve (s)) using small number of coordinates for conciseness. The parameterization Eq. (10) assigns a weight (s(s) to each path p at time s, allowing thresholding the elements in x(s) to select subset E, of n & m paths. The contributions from these few selected path is now ACr(Go.G(a
which should well-approximate AC, G(1)) 8 + 1. For example, in Figure [ we can take E2 = {(K, J, J), (L, JJ} C AW, G1) with n = 2. The selected paths span a low- dimensional space to embed the neighborhood of Pr(Y[G;) on the manifold MMJ, G). Adding paths in E, to the computation graph of Go leads to a new computation graph on the manifold.
We optimize En to minimize the KL-divergence in Eq. III) with Eq. I0). Let ((; E [0, 1].
p= 1....,m m be the weight of selecting path p into En. We solve the following problem:
min Ey-p(r-sicn) CC.((G)) x()){(0.11" [x(s)lim
log Σ f=1
( (12)
where C,,(x(s) = Co)(G) + AC, G(s)) is vector of path contributions to the logit of class AC (Go, G(s)) is parameterized by Eq. (10 and is function of x(s). The constants log Z (G,) is ignored from Eq. (1) as G₁ is fixed. The linear constraint ensures the total probabilities of the selected edges is n. The optimization problem is convex and has unique optimal solution. We select the paths with the highest x(s) values to constitute a curve (s)) that explains the change from Pr(Y]Go) to Pr(Y (s) approaches GI( Concerning the Riemannian metric in Eq. D.. the above optimization does not change the Riemannian metric [(vee(C)(Gi)) at Pr(Y|Gi) since the objective function is based on the KL-divergence of distributions generated by the non- linear softmax mapping, while (x(s)) vary in the extrinsic coordinate system with x(s).
4 EXPERIMENTS
Datasets and tasks. We study node classification task on evolving graphs on the YelpChi. Yelp- NYC, YelpZip Rayana & Akoglu (2015), Pheme /Zubiaga et al. (2017) and Weibo Ma et al. (2018) datasets, and study the link prediction task on the BC-OTC, BC-Alpha, and UCI datasets. These datasets have time stamps and the graph evolutions can be identified. The molecular data (MUTAG Debnath et al. (1991) is used for the graph classification. In searching molecules, slight perturba- tions applied to molecule graphs You et al. (2018). We simulate the perturbations by randomly add or remove edges to create evolving graphs. Appendix I.5. gives more details.
Experimental setup. For each dataset, optimize GNN parameter 0 on the training set of static graphs, using labeled nodes, edges, or graphs, depending on the tasks. For each graph snapshot ex- cept the first one, target nodes/edges/graphs with a significantly large Dxi (PP(((())))))PPP(((Tc))

---

Published as a conference paper at ICLR 2023
collected and the change in Pr(Y|G) is explained. We run Algorithm I calculate the contribu- tion matrix C)( for each node J E V*. We use the evxpy library Diamond & Boyd to solve the constrained convex optimization problem in Eq. (12 (14 and Eq.(13). This method is called "AxiomPath-Conss
We also adopt the following baselines.
Gradient. Grad computes the gradients of the logit of the predicted class j with the maximal Pr(Y j]G)) on Go and G1 respectively. Each computation path is assigned the sum of gradients of the edges on the paths as its importance. The contribution of a path to the change in Pr(Y]G) is the difference between the two path importance scores computed Go and G1. If path only exists on one graph, the importance of the path is taken as the contribution. All paths with top importance selected into En.
GNNExplainer (GNNExp) Ying et al. (2019) is designed to explain GNN predictions for node and graph classification on static graphs. It weight edges on G1 to maximally preserve Pr(Y)G,) regardless of Pr(Y|Gn)) Paths are weighted and selected for Grad, with edge weights calculated using GNNExplainer.
GNN-LRP adopts the back paok-propagation attribution method LRP to GNN Schnake et al. attributes the class probability Pr(Y = j|G1) ) input neurons regardless of Pr(Y Go). It assigns an importance score to paths and top paths are put in Ex.
2020).
DeepLIFT [hrikumar et al. (017) can attribute the log-odd between two probabilities Pr(Y = j|Ga) and Pr(Y = J'),,, where j * j'. For a target node edge or graph, if the predicted class changes, the difference between a path's 's contributions to the new and original predicted classes is used to rank and select paths. If the predicted class remains the same but the distribution changes, a path's contributions to the same predicted class is used. Only paths from AW, (Gu. G1) or in AG, G1) U (Go, G1) or in UJev G1) are ranked and selected.
It selects the top paths p from (W,(Go, G1) or AW, (Go, G1) U ( G1) or UJev G1) with the highest con- tributions (G, G1)1, where 1 is an all-1 c x vector. This baseline works in the Euclidean space spanned by the paths as coordinates and rely on linear differences in C(G) rather than the nonlinear movement from Pr(Y)]o) to Pr(Y
AxiomPath-Topk is a variant of AxiomPath-Conver
AxiomPath- optimizes the AxiomPath Pato--Co--ooee objectives without the last log terms, lead- ing to a linear programming.
Quantitative evaluation metrics. Let Pr(Y|-G(s)) be computed on the computation graph of G1 with those from E,, disabled. That should bring G1 close to Gu along 7ss) so that KL* = Pry,Prr(GoPP (-s)()(()) should be small if E,, does contain the paths vital to the evolution. Sim- ilarly, we expect (r)))())) to move close to Pr.(Gr) after the paths E, are enabled on the com- putation graph of Go. and KL = KL((Pr((i, indeed contains the more salient altered paths that turn Go into Gj, the less information the remain- ing paths can propagate, the more similar should G, be to G and -G, be to Go. and thus the smaller the KL-divergence. Prior work Suermmoni] (1992); Yuan et al. (2020a); |Ying et al. (2019) use KL-divergence to measure the approximation quality of static predicted distribution Pr G)),,
should be smaller. Intuitively. if E,,
while the above metrics evaluate how distribution on the curve (ss) approach the target G1)
A similar 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. The target nodes (links graphs) are grouped based on the number altered paths in AW, G1) for the results to be comparable, since alternating different number of paths can lead to significantly dif- ferent performance. For each group, we let |EE range in a pre-defined 5-level of explanation simplicity and all methods are compared under the same level of simplicity. Appendix A.5.2 and Appendix A.5.3 gives more details of the experimental setup.
4.1 PERFORMANCE EVALUATION AND COMPARISON
We compare the performance of the methods three tasks (node classification, link prediction and graph classification) under different graph evolutions (adding and/or deleting edges). For the node classification, in Figure 2 demonstrate the effectiveness of the salient path selection of Croomaahh-Covees For each dataset, we report the average KL over target nodes/edges on three datasets (results with the KI. metric, and results the remaining datasets are given Figure 6
7

---

Published as a conference paper at ICLR 2023
Welbo (add edges)
Pheme (add edges)
YelpChi (add edges)
0.30
Gld Aasafhn Pann
0.25
0.06
und
0.15
0.10
0.20
0.06
Nootrn--oone Aoserhen Liver
0.15
2
3
4
3 Explanation complexity levels
2
Explanation complesdly
Explanstiio complexity
Weibo (remove odges)
Pheme (romove edges)
YopChi (remove edges)
Comera
0.10
0.02
Araofich Fun
ovde
0.1
0.05
0.01
0.0
Explanation complextty lovels
Exp lanation complexity levels
Explanation complexity levels
Weibo (add and remove edges)
Phome (add and remove edges)
YelpChi (add and remove edges)
0.20
0.2
0.2
0.15
grouuer
0.1
0.10
0.05
0.0
2
2
3
4
5
1
2
Explanation compicafty lovels
Explanation complexity levels
Explanation complexity levels
Performance KL+ as Co - G1 on the node classification tasks. Each column a dataset and Figure 2:
each row is one type of evolution.
and 8 in the Appendix). From the figures, we can see that AxiomPath-Convex has the smallest KL over all levels of explanation complexities and over all datasets. On six settings (Weibo-adding edges only and mixture of adding and removing edges, and all cases YelpChi), the gap between AxiomPath-Come Convahh---Chceeccc and the runner-up is significant. On the remaining settings, ExiomPath-Come slightly outperforms or is comparable to the runner-ups. underperform AxiomPath-Convex, indicating that modeling the geometry of the manifold of proba- bility distributions has obvious advantage over working in the linear parameters of the distributions. On two link prediction tasks and one graph classification task, in Figure 3] we show that AxiomPath- Convex significantly uniformly outperform the runner-ups (results on the remaining link prediction task and regarding the KL. metrics are give in the Figure 6 8 and | in the Appendix). DeepLIFT and GNNExplainer always, and Grad sometimes, fails to find the salient paths to explain the change, as they are designed for static graphs. In Appendix [A.7] we provide cases where AxiomPath-Conver identifies edges and subgraphs that help make sense of the evolving predictions. In Appendix [A.6] analyze how long each component of the ChomPath-Conver algorithms take several datasets. we analysis the limit of our method.
Piiompath-Tops and AxiomPath-
In Appendix A.8
RELATED WORK
Differential geometry of probability distributions are explored in the field called "information geom- AAmrii (2016), which has been applied to optimization Chen et al. (2020): Osawa et al. (2019); Kunstner et al. (2019): Scroussi & Zeitouni (2022); Soen & Sun (2021) machine learning Lebanon 2200)) Karakida et al. (2020); Nock et al. (2017): Bernstein et al. (2020), and computer vision Shao
et al. (2018). However, taking the geometric viewpoint of GNN evolution and its explanation is novel and has not been observed within the information geometry literature and explainable/intepprtbbbe
machine learning.
Prior work explain GNN predictions on static graphs. There are methods explaining the predicted class distribution of graphs or nodes using mutual information Ying et al. (2019). Other works
8

---

Published as a conference paper at ICLR 2023
UCI (odk edges)
BC-Alpha (add edges)
(add edges)
0.15
0.175
0.15
0.10
SZ 0.10
0.125
Vesa 1
Accen con
0.05
0.05
0.100
2 Explanaatoon complexity levels
Explanalion compleddly
Explanation complexity
UCI (romove edges)
BC-Aiphha (remove edges)
(romove edges)
0,100
0.10
0.075
0.05
Yack
0.050
0.025
Explanatio complexity leve's
Explanation complexity levels
Explanation complexity levels
UCI (add and remove edges)
BC-Alpha (add and remove edges)
(add and edges)
0.100
0.08
0.075
0.16
0.08
ouz
0.050
0.10
0.04
0.025
DeauITT FT
Asuehal
Asuemaa and
2
3
4
6
2
Explaration comp loxily levels
Explanation complexity levals
Explanation complexity levels
Figure 3: Average K KL+ on the link prediction and graph classification tasks, Each row a dataset and each column is one evolution setting.
explained the logit or probability of a single class Schnake et al. 2020). CAM, GradCAM, GradIn- put, SmoothGrad, IntegratedGrad, Excitation Backpropagation, and attention models are evaluated in Sanchez-Lengeling et al. (2020); Pope et al. (2019) with the focus on explaining the static pre- diction of single class. CAM and Grad-CAM are not applicable since they cannot explain node classification models Yuan et al. (2020)). DeepLIFT [Shrikumar et al.] (2017) and counterfactual explanations Lucic et (2021) do not explain multi-class distributions change over arbitrary graph evolution, as they assume Gp is fixed at the empty graph. To compose an explanation, simple surrogate models Vu & Thai (2020) edges [Schnake et al. (211)); Lucic et al. (2021) subgraphs Yuan et al. (021 2020a) or graph samples Yuan et al. (2020a) and nodes Pope al. (2019) have been used construct explanations. These works can- not axiomatically isolate contributions of paths that causally lead to the prediction changes on the computation graphs. Most of the prior work evaluates the faithfulness of the explanations of a static prediction. To explain distributional evolution, faithfulness should be evaluated based on approxi- mation of the curve of evolution on the manifold so that the geometry will be respected. None prior work has taken differential geometric viewpoint of distributional evolution of GNN. Optimally se- lecting salient elements to compose a simple and faithful explanation is less focused. With the novel reparameterization of curves the manifold, we formulate convex programming to select curve that can concisely explain the distributional evolution while respecting the manifold geometry.
al. (2020): Ying al.] (2019); Shrikumar
6 CONCLUSIONS
We studied the problem of explaining change in GNN predictions over evolving graphs. We ad- dressed the issues of prior works that treat the evolution linearly. The proposed model view evo- lution of GNN output with respect to graph evolution as smooth curve on a manifold of all class distributions. This viewpoint help formulate a convex optimization problem to select a small subset of paths to explain the distributional evolution on the manifold. Experiments showed the superior- ity of the proposed method over the state-of-thed In the future, we will explore more geometric properties of the construct manifold to enable deeper understanding of GNN evolving graphs

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
Sihong was supported in part by the National Science Foundation under NSF Grants IIS-1909879, CNS-1931042, NIS-2008155, and IIS-2145922. Yazheng Liu and Xi Zhang supported by the Natural Science Foundation of China (N966176)226 and the 1 111 Project (B 18008). Any opinions, findings, conclusions, recommendations expressed in this document those of the author(s) and should not be interpreted as the views of any U.S. Government.
REFERENCES
Shun-ichi Amari. Information Geometry and Its Applications. Springer Publishing Company, In- corporated, 1st edition, 2016. ISBN 4431559779.
Jeremy Bernstein, Arash Vahdat, Yisong Yue, and Ming- Yu Liu. On the distance between neural networks and the stability of learning. In Advances in Neural Information Processing Systems, volume 33, pp. 21370-2138/ 2020.
Huiming Chen, Ho-Chun Wu, Shing-Chov Chan, and Wong-Hing Lam. A Stochastic Quasi-Newton Method for Large-Scale Nonconvex Optimization With Applications. IEEE Transactions on Neural Networks and Learning Systems, 31(11)4477-4770, 2020. doi: 10.1109/TNNLS.2019 2957843.
Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, and Cor- win Hansch. Structure-activvity 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.
Ryo Karakida, Shotaro Akaho, and Shun-ichi Amari. tics of Fisher information in deep neural networks:
Universal statis- mean field approach Journal of Statisticul Mechanicx: Theory and Experiment, 2
sup*/sup. 124005, dec2020.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation Learning for Dynamic Graphs: Survey. Mach. Learn. Res., 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in tem- poral interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, KDD, pp. 1269-1278. Association for Computing Ma- chinery, 2019.
Frederik Kunstner, Philipp Hennig, and Lukas Balles. Limitations of the empirical Fisher approx- imation for natural gradient descent. In Advances in Neural Information Processing Systems, 2019.
Guy Lebanon. Learning riemannian metrics. In Proceedings of the Nineteenth Conference Uncertainty in Artificial Intelligence, UAI, 2002.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data, 1(1), 2007. ISSN 1556-4681.
Jure Leskovee, Lars Backstrom, Ravi Kumar. and Andrew Tomkins. Microscopic evolution of social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pp. 462-470. Association for Computing Machinery, 2008.
Meng Liu, Youzhi Luo, Limei Wang, Yaochen Xie, Hao Yuan, Shurui Gui, Haiyang Yu, Zhao Xu, Jingtun Zhang, Yi Liu, et al. DIG: turnkey library for diving into graph deep learning research. arXiv preprint arXiv: 103. /2008, 2021.
10

---

Published as a conference paper at ICLR 2023
A. Lucic, Maartje ter Hoeve, Gabriele Tolomei, M. Rijke, and F. Silvestri. Cf-gnnexplainer: Coun- terfactual explanations for graph neural networks. ArXiv, abs/2102.03322, 2021.
Jing Ma, Wei Gao, and Kam-Fai Wong. Rumor detection on twitter with tree-structured recursive neural networks. ACL, 2018.
James Martens. New insights and perspectives on the natural gradient method. Journal of Ma- chine Learning Research, 21(146):1-76, 2020. URL
17-678 html
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML
2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www.
graphlearning...
Richard Nock, Zac Cranko, Aditya K Menon, Lizhen Qu, and Robert C Williamson. f-GANs in an Information Geometric Nutshell. In Advances in Neural Information Processing Systems, volume 30, 2017.
Kazuki Osawa, Yohei Tsuji, Yuichiro Ueno, Akira Naruse, Rio Yokota, and Satoshi Matsuoka. Large-Scale Distributed Second-Order Optimization Using Kronecker-Factored Approximate Curvature for Deep Convolutional Neural Networks. Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), jun 2019.
Phillip E Pope. Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability Methods for Graph Convolutional Neural Networks. In CVPR, 2019.
Shebuti Rayana and Leman Akoglu. Collective opinion spam detection: Bridging review networks and metadata. In KDD, 2015.
Jie Ren, Mingjie Li, Zexu Liu, and Quanshi Zhang. Interpreting and Disentangling Feature Compo- nents of Various Complexity from DNNs. In ICML, 2021.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard. Federico Monti, and Michael Bronstein. Temporal Graph Networks for Deep Learning on Dynamic Graphs. Technical report, 2020.
Benjamin Sanchez-Lengeling Jennifer Wei, Brian Lee, Emily Reif, Peter Wang, Wesley Qian, Kevin McCloskey, Lucy Colwell, and Alexander Wiltschko. Evaluating Attribution for Graph Neural Networks. In NeurIPS, 2020.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima Kristof T. Sch Sut, Klaus-Robert M 'lluller, and Gr' egoire Montavon. Higher-order explanations of graph neural networks via rele- vant walks. 2020.
Inbar Seroussi and Ofer Zeitouni. Lower Bounds on the Generalization Error of Nonlinear Learn- ing Models. IEEE Transactions on Information Theory, pp. 1, 2022. doi: 10.1122/ 3189760.
Hang Shao, Abhishek Kumar, and P. Thomas Fletcher. The riemannian geometry of deep generative models. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2018.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning Important Features Through Propagating Activation Differences. In ICML, 2017.
Alexander Soen and Ke Sun. On the Variance of the Fisher Information for Deep Learning. In Advances in Neural Information Processing Systems, volume 34, 2021.
Henri Jacques Suermondt. Explanation in Bayesian Belief Networks. PhD thesis, 1992.
Minh Vu and Thai. PGM-Explaine:: Probabilistic Graphical Model Explanations for Graph
Neural Networks. In NewrIPS, 2020.
11

---

Published as a conference paper at ICLR 2023
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, 2019.
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.
Chengjin Xu, M. Nayyeri, Fouad Alkhoury, Hamed Shariat Yazdi, and Jens Lehmann. Temporal knowledge graph completion based on time series gaussian embedding. In SEMWEB, 2020a.
Da Xu, Chuanwei Ruan, Evren Korpcoglu, Sushant Kumar, and Kannan Achan. Inductive represen- tation learning temporal graphs. In ICLR, 2020b.
Yiding Yang, Zhou Ren, Haoxiang Li, Chunluan Zhou, Xinchao Wang, and Gang Hua. Learning dynamics via graph neural networks for human pose estimation and tracking. CVPR, 2021.
Jiexia Ye, Juanjuan Zhao, Kejiang Ye, and Cheng-Zhong Xu. How to build graph-based deep learning architecture in traffic domain: survey, ArXiv, abs/2005. 1691, 2020.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L 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, abs/2012.15445, 2020b.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In ICML, 2021.
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 2023
A APPENDIX
You may include other additional sections here.
A.1 MISC. PROOFS
Here we give the detailed derivations of Eq.
( Σ Pr(Y = j[G; log(Pr(Y = - (BGG))/P(YY-(aaa
= =]G)]]
(13)
Pr(Y= ((G)), - -2, -og (og
Pr(Y j|G AC,(GG, Gi) + log Z(Go) - log
2j(G") +1"
AC,
AC,, GI)
exp
j=l
-Cy(Gi)
Pr(Y = ([C.)) Gi) log Z(Gi) + log Σ exp
A.2 SECOND-ORDDREE APPROXIMATION OF THE KL DIVERGENCE WITH THE FISHER INFORMATION MATRIX
To help understand Eq. (9) that defines the Riemannian metric, we need second-order approx- imation of the KL-divergence. We reproduce the derivations from the note "Information Geom- etry and Natural Gradients" posted on https:: /www nwt.an liffffff... www.//om/eeaeeeee ptoopppeagggy/// mathhmatiion ics- for intelligent systems| by Nathan Rathiff (Disclaimer: we make contribution to these derivations and the author of the note owns all credits). In the following, the term 0 should be understood the vector vee(C) and 5 should be understood as the difference vector vec( (ec Go)) in Eq. 9 x is understood as the random variable Y, the class variable, in our case.
KL (p (z; (1p
/ p (a;0)) dx
/ (x: [0gg(o;00) ( (Ve0(150))
1 5 (Vzlogp logp (z; ()) 8) dr 8
(x;
((x;0) du ( (=x;0) log
do) 8
(xx; 0)
1 ST (fDlat))))bgp(zee) 6
2
By assuming that the differentiation and integration in the second term be exchanged, have
/ Vp (v) dr = v d
- de v1=0
V2 logg (2: (xx;0) (2; V Vogg(
13

---

Published as a conference paper at ICLR 2023
KL (p (x;; 8) 1p (x; 0 + +))
(f p (2; 0) logn (x:
2 ST
8
(ʃ (a; (z; 0) dx
TT
2 50
(
V log (Vlog
(x; 0) v Flogp (x; 0)
de
G(O))
The matrix (0) known as the Fisher Information matrix.
A.3
OPTIMIZE CURVE ON THE LINK PREDICTION TASK AND GRAPH CLASSIFICATION TASK
Similar to node classification,, according to the Eq. 12). for the link prediction, we solve the follow-
ing problem:
min x1
Bncrcc)(CC(G))-C(((()))()) (8)))= xx)
I=0
x (s (e)))''m
[x())
(4 1
(14)
where C.( = CCC (x((())x((()))
{(s) (C,(()) +
AC. G(s))): ( AC G(s)))))
For the graph classification, we solve the following problem:
min (G. Cipy (x(s))oGc + log Σ exp ex' x())e[u,)1" [
+ (x)(((s)))0Gc (15)
[
Σvev C.(()
where [V] denotes the number nodes in the graph, (G1
(xi
[
Eeev x(s) [C,,(:))+A,,,GG,0ttt)))
A.4 ATTRIBUTING THE CHANGE TO PATHS
We describe the computation of Cp.j in the previous section.
A.4.1 DEEPLIFT FOR MLP
2017) serves foundation. Let the activation of neuron at layer 1 be ((+1) E TR, which computed by (0+1) = s( ..... ()))
LIT Shrikumar et al.
Given the reference ac- ...., 10 (0) layer L at time O we can calculate the scalar reference activation (t 1) (0) (() layer 1. The I,....n. the 0 in parentheses indicate the reference (or the current) activations. The contribution of Ah to (c-11) (preservation of (1+11))
livation vector (()) (1 (1) (O)....,
is n. With (or without)
()(++1) ((+1) (1+1( and An(") n, (0),
(M(+1) is Aan5 (M such that Σ CAMl)
The DcepLIFT method defines multiplier and the chain rule so that given the multipliers for each neuron each immediate successor neuron, Iee can compute the multipliers for any neuron
14

---

Published as a conference paper at ICLR 2023
to given target neuron efficiently via backpropagation. DeepLIFT defines the multiplier as: m An Ah(++1)
= Canço AM/t AM
(16)
0!0)
linear layer
=
AA(+I) AM! nonlinear activation
If the neurons are connected by a linear layer, C CA ABCT = Anl0 x 80" where 8/9) is the
element of the parameter matrix (00) that multiplies the activation n to contribute ((++1),, For wliment-wise nonlinear activation functions, we adopt the Rescale rule to obtain the multiplier such that C A A = (1+11)
DeepLIFT defines the chain rule for the multipliers as:
M ( AATT)
Σ
Σ
An AND ... AAAT" 1 DARTT)
(17)
A.4.2 DEEPLIFT FOR GNN
We linearly attribute the change to paths by the linear rule and Rescale rule, even with nonlinear activation functions.
When Gu + G1, there may be multiple added or removed edges, or both. These seemingly compli- cated and different situations can be reduced to the case with single added edge. First, any altered path can only have multiple added edges or removed edges but not both. If there were removed edge that is closer to the root than an added edge, the added edge would have appeared in a different path and the removed edge must be from an existing path leading to the root. If there were an added edge closer to the root than a removed edge, the nodes after the removed edge have contribution in Go and the situation is the same as with added edges. Second, path with removed edges only path with added edges only when G1 - Go- Lastly, shown
when Go -> G1 be treated below, only the altered edge closest to the root is relevant even with multiple added edges. Let U and V be any adjacent nodes path, where V is closer to the root J.
Difference-from from-referencee of neuron activation and logits. When handling the path with multiple added edges, we let the reference activations be computed by the GNN on the graph Go. Gref Go. the graph at the current moment is G1. Gour = G1. For a path p in AWJ(Gr G let p(t denote the node or the neurons of the node at layer t. For example, if p (I, .L..... ..... U, ..y....),, p[]] represents J or the neurons of J, and p(0] represents / or the neurons of T. Given a path let i= max(rlr 1,..., T, p(r] V and p(r 1] U and if VU, newly added]. When 2 F, the reference activation of p[4] is (1) (Go). While when / < T, the reference activation of p((] is zero, because the message of pft] cannot be passed along the path (pft)..... J) to J in Go. and the edge (U, V) must be added to Go to connect pit] to J in the path. We thus calculate the difference- from-reference of neurons at each layer for the specific path as follows:
h (t)
2 (G1)
( (Go)
t i
AA (t) p[4]
=
(18)
h ple (G1)
otherwise.
Cutbut toyer
3M 00988
Hidden loyer
7 0o0l
Figure 4: Circles in rectangles neurons, and a has specific color if contributes the prediction change a class. Left: DeepLIFT finds contribution of input neuron the change an output neuron of an MLP for link prediction, where the input layer is the output of a GNN. Right: A two-layer GNN. The four colored quadrants in A2, at the top layer, which can be the input layer to the MLP, can be attributed to the changes in the input neurons at the input layer (c.g., the two blue quadrants at the top is attributed to the blue neurons in node K at the input layer through paths (K, K, and (K, J, J)..
15

---

Published as a conference paper at ICLR 2023
For example, in Figure 4 the added edge is (J, For the path p (J) in G == 2 and Ang = h (G1), because in Go. the neuron j at layer 0 cannot pass message to the neuron at the output layer along the path (J, K, J) in Go. The change the logits A can be handled similarly.
pf(]
Multiplier of neuron to its immediate successor. We choose element-wise function to ensure that the attribution by DeepLIFT can preserve the total change in the logits such that Azj Th Cp.- Then, z04) EveN(ry (Enev Nig ( where a denotes the
the SAGG
element of the parameter matrix ((t) that links neuron to neuron According to the Eq. (16).
Ah (4)
m A A2
B(0) u,et
m A
ANS
(19)
Z
Then we can obtain the multiplier of the neuron to its immediate successor neuron according to Eq. (17)
Alee
mi AM! AA
Az (t)
x ((0) 0,8"
(20)
Note that the output of GNN model is thus AAA ||
((T) -[
We can obtain the
multiplier of each neuron to its immediate successor in the path according to Eq. 20 by letting
7
After obtaining the ( An (1 P(o] P(i]
(T p.T Az," according to Eq.
17 we can obtain
m AA (0) plo Ae,
Azy
Σ P[T-1]
AA (0)
...
(7-1) Aay"
(21)
10
210)
P(O
Calculate the contribution of each path. For the path in AW, (Go, G1), we obtain the contri- bution of the path by summing up the input neurons' contributions:
Cp.j
Σ
m
AN
PIO)
x
Ah
P(O)*
(22)
p|O]
where y(0] indexes the neurons of the input (a leaf node the computation graph of the GNN) and AA (0) (0)
P[O] "!0]"
Algorithm Compute Cp.j for target node J.
1: Input: two graph snapshots Go and G1. Pre-trained GNN parameters OANN for node classifi-
cation,
2: Obtain the altered path set AW,(Go, Gi).
3: Initialize C E R
an all-zero matrix
4: for E (W, G1) do
5: if p contains removed edges then
6: Reverse Go + G1 to G1 + Go.
7:
Compute Cp.j according Eq. 22 and let -Cp.j be the contribution of p as Go G1.
8: else
9:
Compute Cpj according to Eq.
22 as the contribution of p as Go G
10: end if
11:
end for
12: Output: the contribution matrix C.
Algorithm describes how to attribute the change in a root node J's logit Azj to each path p e
AW, (Go, G.).
16

---

Published as a conference paper at ICLR 2023
The computational complexity of Cp.j. Supposing that have the TT' layer GNN, the dimension
of hidden vector hy of layer t is dt(t = 1, ........77 T) and the dimension of the input feature vector
T
is d. The time complexity of determining the contribution of cach path is O de x d). In the ==1
I
calculation, according to the Eq 20 we can obtain the multiplier m AA! AA!") Then according to the Eq 2T and the Eq. 22 we use the chain rule to obtain the final multiplier and then obtain the contribution. Because the multiplier m "Aff 1) " is sparse, obtaining the final multiplier matrix also relatively fast. For the dense edge structure, the number of paths large. But for these paths with the same nodes after layer t (for example, the path (K, K, J) and the path (J, K, the multipliers after the layer are(for example m "n An the same. The proportion of paths that can share multiplier matrices is large. Because of this, the calculation will speed up.
Theorem 1, The GNN-LRP is a special case if the reference activation is set to the empty graph.
Proof. Considering the path p (T, ,..,. U,V. the graph C1, we let Go is the empty graph. (t) N.
Then, Ah P[[] 2/0 (G1) A (8) (t)
p[[]] Sy[{] (G1), An An!
Ah(1)
0 While, for the GNN-
A
LRP, when 0, R2 = Ej. we note LRP(t)
that represents the
u,v
AM
UEN(V)
allocation rule of neuron v to its predecessor neuron u. The contribution of this path is
R Σ
Σ
LRP(1)
LRP(T)
p/2-11,5 R
p|T
(0)
(1)
(T-1) (())
Σ
Σ
pfT'-1 p(T
2j
(I)
2j
P
p[1
h
(1)
0
Σ
Σ
Plu s,p[1]
((T)
(1)
D[T- 1)5
p|1
P 1]
P[1]]
1
(0)
AA! Aaj
Cp.
A.5 EXPERIMENTS
A.5.1 DATASETS
YelpChi, YelpNYC, and YelpZip Rayana & Akoglu (2015): each node represents a review, prod- uct, or user. a user posts a review to 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. (201)) and Weibo Ma et al. (018): 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.
BC-OTCTandd BC-Alpha" is a who trusts- whom network of bitcoin users trading on the platform.
The data sets are used for link prediction.
UCF 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 Morris et al. (020): A molecule is represented as a graph of atoms where an edge represents bounding atoms.
html
http: htte://epp..aatnnrna.oll///////s
hlmm
17

---

Published as a conference paper at ICLR 2023
A.5.2 EXPERIMENTAL SETUP
We trained the two layers GNN, We choose clement-wise sum as the fAGG function. The logit for node J is denoted by GG). For node classification, G)) is mapped to the class distribution through the softmax (number of classes c 2) or sigmoid (number of classes c= 2) function. For the link prediction, we concatenate 2r(G) and =. =)) as the input to a linear layer to obtain the logits. Then it be mapped to the probability that the edge (I, J) exists using the sigmoid function. For the graph classification task, the average pooling of (G) of all nodes from G can be used to obtain single vector representation =G) of G for classification.
can be mapped to the class probability distribution through the sigmoid softmax function. We set the learning rate to 0,01, the dropout to 0.2 and the hidden size to 16 when we train the GNN model. The model is trained and then fixed during the prediction and explanation stages.
The node or edge or graph is selected as the target node or edge or graph, (I,(Pr(Gi))])) (G))))r))))))))))) > threshold, where threshold=0.001.
For the MUTAG dataset, we randomly add or delete five edges to obtain the G1- For other datasets, the linitial and the fend obtain pair of graph snapshots. We get the graph containing all edges from fimitio! to fend. Then two consecutive graph snapshots can be considered as Go and G For Weibo and Pheme datasets, according the time-stamps of the edges, for each event, we can divide the edges into three equal parts. On the YelpZip(both) and UCI, we convert time to weeks since 2004. On the BC-OTC and BC-Alpha datasets, we convert time to months since 2010. On other Yelp datasets, we convert time to months since 2004. See the table 2 for details.
Table 2: The details for datasets
Datasets
Nodes
Edges
Settings
Lnnstial
lend
add (remove) both
[84, 90,96,102,10N,
YelpChi
105,659
375,239
[78,80,82,84]
884,86,88,90]
add (remove) both add (remove) both add (remove) both add (remove) both add (remove) both add (remove)
(78,80,82,84.86
YelpNYC
520,200
1,956,408
[78,79880.8]]
884,85,86,87]
178,79.80.81.82
YelpZip
873,919
3,308,311
13,8,340,,5223444
[354,556,358,
[48.50.52.54.56]
BC-OTC
5,881
35,588
28,,26
[48,30,52,54]
[48,51,54,57,60
BC-Alpha
3,777
24,173
(24,26,28,30]
[48,50,52,54]
[18.19,20,11.2]
UCI
1,899
59,835
118,17,18119]
[19200,1122]
11/3,2/3.1]
Weibo
4.657
both add (remove)
[0.1/3]
[2/3.1]
11/3,2/3,1]
Pheme
5,748
both
[0,173]
[273,1]
MUTAG
17.93
19.79
add (remove, both)
To show that as n increases, (r.) is gradually approaching (r.), we let gradually increase. We choose n according to the number of the altered paths.. See the table for details.
A.5.3
QUANTITATIVE EVALUATION METRICS
We illustrate the calculation process of our method in Figure
A.5.4 EXPERIMENTAL RESULT
See the Figure 6 for the result the KL the YelpNYC, YelpZip and BC-OTC datasets. See the Figure 7 Figure 8 and Figure 9 for the result on the KL on the all datasets. The method AxiomPath-Convex is significantly better than the runner-up method.
18

---

Published as a conference paper at ICLR 2023
Table
The the number of selected paths according to the number of altered paths.
The the number of selected paths
Task
settings
the number of altered paths
(1000, +:00
[15, 17, (10,11,12.13.14]
(500, 1000
Node classification
add, remove both
(100, 500]
16.7,8.9.10]
(10, 100
[1,2,3.4.5]
(1000, +
100,00
(500, 1000
[10,20,30,40500
Link prediction
add, remove and both
(100,500)
[10,12.14,16188]
100
[1,2.3,4,5]
(1000, +
[10,11,22.13144]
(500. 1000
(6.7.8,9,10]
Graph classification
add, remove and both
(000
[3,4,5.6.7]
(10, 100
[1,2.3,4,5]
A.6 SCALABILITY
Running time overhead of convex optimization. We plot the base running time for searching paths in AW (Go, G1) (or (W, U AW, G1)) and attribution the running time of the convex optimization. In Figure 10 we see that in the two top cases, the larger A AW, G1) (or ( G.) (Gu, G1)) lead to higher cost in the optimization step compared to path search and attribution. In the lower two cases, the graphs are less regular and the search and attribution can spend the majority computation time. The overall absolution running time is acceptable. In practice, one can design incremental path search for different graph topology, and more specific convex optimization algorithm to speed up the algorithm.
We plot the running of the baseline methods the Figure 11 Figure 12 and Figure 13 The order of running time by the baseline methods is: AxiomPath-Conver AxiomPath-Linear > DeepLIFT, AxiomPath-Toppe > Gradient, GNNLRP. About for the GNNExplainer methods, they cost more time when the the graph is small and they cost less time than DeepLIFT when
than AxiomPath-Come the graph is large. Although the running time of Gradient and GNNLRP is less, the Gradient method cannot obtain the contribution value of the path, only obtain the contribution value of the edge in the input layer. GNNLRP, like DeepI.IFT, was originally designed to find the path contributions to the probability distribution in the static graph, and cannot handle changing graphs considering the running time of calculating path contribution values, we can use GNNLPR to obtain the paths contribution value in the Go and C₁ and subtracted them as the of the final contribution value. still use theory choose the critical path to explain the change of
After obtaining Cp.jt probability distribution. GNNLPR can be faster replacement for DeepLIFT.
A.7
CASE STUDY
is necessary to show that AxiomPath -antvexx--oxxxxx selects salient paths to provide insight regarding the relationship between the altered paths and the changed predictions.
On Cora, we add and/or remove edges randomly, and for the target nodes that the predicted class changed, we calculate the percentages of nodes on the paths selected by AxiomPath-Convex that have the same ground truth labels as the predicted classes on Go (class 0) and G1 (class 1). respec- tively. We expect that there more nodes of class 1 on the added paths, and more nodes of class 0 on the removed paths. We conducted 10 random experiments and calculate the means and standard expected. It further con-
deviations of the ratios. Figure 14 shows that the percentages behave firms that the fidelity metric aligns well with the dynamics of the class distribution that contributed the prediction c
In Figure 15] on the MUTAG dataset, we demonstrate how the probability of the graph changes as some edges are added/removed. We add remove edges, adding or destroying new rings in the molecule. The AxiomPath Convex can identify the salient paths that justify the probability changes.
SeriomPath-Conveer has performance Cora similar to those in Figure
19

---

Published as a conference paper at ICLR 2023
Evolved graph
Path contributions each class Cpj
Go
K
G1
0.5
K
K
0
-1.5
2
0.5
0
-1
0.5
0.5
-0.1
0
GG) [3,3,4]
G) [3,2,5]
0.5
0.1
0
Pr)(G) = [0.21,0.11.00588]
Pr) [0.12,0.04.0.84]
Linear attribution Ar to path contributions
Áz= [0.0
-1.0
1.0]
Convex unique path selection
F The important
added path removed path added path PPr((G))
puths
K
Explain why Pro(Co)
Quantitative evaluation metrics
(ri(Gi)
Remove the added path
Pr)(G))
Pry(Go) Add the added puth
Pr)(G,
>J >> K >
K
Add the removed path J-V-~>
Remove the removed path JIV1~>
KL, = -
KL_ KLPPAG))))PPAAGG
Figure 5: Top left: Go (c.g., a citation network) at time t = is updated to G3 at time t after the edge (J, K) is added and the edge () is removed, and the logits z.(GGo) and predicted class distribution Pr)(Go) of node J changes accordingly. Prior counterfactual methods attribute the change to the edges (J, K) and J). Center left: the GNN computational graph that propagates information from leaves to the root J. Top right: Any paths from computational graph containing a dashed edge contrihute to the prediction change, and we axiomatically attribute the logits changes to these paths with contribution Cp.s (for the p- th path to the component Az₂). Center right: Not all paths significant contributors and we formulate convex program to uniquely identify a few paths maximally approximate the changes. Bottom: We show the calculation process KL* and KL. after obtaining E,, Other situations, including edge deletion, mixture of addition and delction, and link prediction can be reduced to this simple case.
A.8 FURTHER EXPERIMENTAL RESULTS
We analyzed how the method performs on the spectrum of varying (L((Pr,(G)) (I for the YelpChi, YelpZip, UCI, BC-OTC and MUTAG datasets when edges are added and removed (See Figure 16). For some nodes with the lower higher. Through the further analysis, we find that it may because the (r)(G1) or Pr) has all probability mass concentrated at one class. (See Figure 17). For the some target nodesiedges/graphe with the classification probability in G, or Go close I, the KL KL is high. That means the selected paths may not explain the change of probability distribution well. When the classification probability close in the Go(G1), 1), more difficult to select a few paths to make the probability distribution close G (G)), the KL KL is high.
the KL* or KL is
20

---

Published as a conference paper at ICLR 2023
YeloNYC (add edges)
YelpZio (add edges)
BC-OTC (add edges)
0.25
0.10
0.10
0.20
0.05
0.05
0.16
AAcettis Fup
0.00
Explanation complexily levels
Expla Explanation complexity levels
Explanstion complexity leve is
YelpNYC (remove edges)
YelpZ (remove edges)
BC-OTC (remove edges)
0.2
0.6
0.08
Acperash soeerathuae Lime?
0.4
0.06
0.2
0.04
0.02
0.0
2
2
Explanation complexity lovals
Explanation complexty levels
Explanation complexity levels
YelpNYC (add and remove edges)
YelzZip (add and remove edges)
BC-OTC (add and remove edges)
0.15
0.100
0.10
0.075
0.05
0.050
0.00
Ascegh M0
2
Explanation complexity lovels
Exp Explanation complexity levels
Explanation complexity levels
Figure 6: Performance on the node classification task and link prediction task. Each column is a dataset and each row is one setting. Each figure shows the KI. Go - G1 for pair of snapshots.
Weibo (add edges)
Phemme (add edgess
YelpChi (add edges)
0.20
Noueman Carna
0.16
0.02
0:10
Came
2
Explanation complexiyy levels
Explanation complesily leve
Explanatin complexty levels
Welbo (remove edges)
Phome (remove edges)
YelpChi (remove edges)
0.20
0.00
Ienerhe
0.125
0.08
Accerhen Liber
0.100
0.15
usa
0.01
0.075
0.10
0.000
Recetrmm Liner
Exp Expianationoom complexity lovels
Explanatio complexity lovels
Exp anationi complexity lovels
Weibo remove edges)
Phome (add remove edges)
YelCCi (add and remove edges)
0.15
0.40
22 0.10
028
Ood deviio
0.4
Fareten Tick
0.06
0.30
Expretaiio campuealyy
Exparaionn campaippllylyyy
Explenation complecty by mooiss
Figure 7: Performance on the node classification tasks. Each column is a dataset and cach row is one setting. Each figure shows the KL- as Go -> G1 for pair of snapshots.
21

---

Published as a conference paper at ICLR 2023
YelpNYC (add edges)
Ye pZip (add edges)
(add edges)
02
0.08
0.4
9.06
Nosethal Loeas
02
0.04
Exp appanatinnn complexity onlly levels
Exp anatioo comp onlyy lovels
Explanation complexity leve's
YdIpNYC (nemove edges)
YalpZip (remove adges)
tramove adges)
0.10
0.00
150
0.125
0.005
0.080
usd anrio
0.06
Accerhes
Page
0,076
100
0.02
Expanation comp exity
Explanatio complexit lovels
Explanatio complexity levels
YelpNYC (add and remove edges)
YelaZip (add and remove edges)
(add and remove edges)
0.6
0.15
0.16
04
0:10
0.88
02
0.10
Expraration complesily lrmels
Expretaionn complesily levels
Expleretio complest unlty loads
Figure 8: Performance the node classification task and graph classification task. Each column is dataset and each row one selting, Each figure shows the KL Go G1 for a pair of snapshots.
UCI (add edgas)
BC-Alpha (add adges)
BC-OTC (add adges)
0.100
100
0.06
0,075
0.06
and
0.000
0.050
0.04
0.005
0.025
0.02
Exponation exly
Explanation complexit lovels
Exclonation complexity
UCI (remove edges)
BC-Alpha (remove edges)
BC-OTC (remove edges)
0.190
0.15
0.125
0.3
0.100
2 0.90
Assetain Fash
crossio
0.55
0.050
0.1
Explanation compleily louls
Explamation complescly lecals
Explenation complecty levels
UCI (adi and remove edgos)
BC-Alpha (add and remove odges)
BC-OTC (add and remove edgas)
008
0.08
5.66
0.05
0.100
004
One
0.076
502
0.050
Asces on Eup
0.825
Aeurias lat
3
Explanation complesity ovele
Explanation complesne lovels
Explanation complesity ty levels
Figure 9: Performance on the link prediction tasks. Average KL on the link prediction and graph classifi- cation tasks. Each row is a dataset. Each column is one setting. Each figure shows the results of a pair of graph snapshots.
22

---

Published as a conference paper at ICLR 2023
BC-OTC
UCI
And spc HURRI E1Te
Optmmotten
Opennictt
ane
Aver 10000
170
Max number of patta procsseed
Vax number of potta prosessed
Max rumber of patts procosed
Max rumber of patts processed
Figure 10: Decomposition of running time of AxiomPuth-Convex.
YapCh
SCOTC
UCI
1.2
6.175
Aucnag ronnng
E2.100
6.10
8.529
6.00
8.000
88 0
Mac numberr
Maa number sate proseeed
procemeed
Mac
Figure 11: The running time of GNN-LRP.
WotD
Aonggnon Ere
6
2
8 0 55
Figure 12: The running time of Gradient.
VelCCH
Yepdt
Noungnaante line
2.5
21.3
1.0
pale procummed
TU parte
Figure 13: The running time of GNNExplainer.
Actadgss
adges
Add and remove edgex
Alle Tiken
144
07
80
Case study on the Cora dataset. Adding edges only, removing edges only and both adding and removing edges. As AxiomPath-Come nodes on the selected paths from any previously predicted class on Go (class 0) and in any newly predicted class on G1 (class l).
Figure 14:
selects different number salient paths, we show the percentages of
23

---

Published as a conference paper at ICLR 2023
MUTAD (0
VUTAS Putthtn - 0L Fastlss... 6.62
Figure 15: Case study on the MUTAG datasct. The circles denotes the nodes and the different types of nodes have different colors. Left: The black edges deonte the edges in the graph Go and G1. the red/blue edges denote the added/removed edges. Right: The red edges the paths selected by AsiomPath-Conver that lead to prediction changes, When adding or removing edges, the information gathered by neighbor nodes changed, thus affecting the classification probability. When masking or adding these red paths, KL. and KL. approach zero.
YeipCii (add and remoow adgeos
YelpChi (weid and remove sdlpes]
Yelpoip (adi and semous edgee]
Yeps? (wiid and renoee sllees
0.4
C4
0,2
0.
6.0
30
0.
022
0A
6.6
0a
1.
02
04
0.6
0.
1.
2.
944
0.
0.3
0.3
04
0.5
0.
AU P1
KUPY0 (P//9
HUPyOu Pr
BC-OTC and rumose edgea)
SC-OTC jail semore odges)
jadd and remove adgeo)
and nemove adges)
0.13
2
KUP/C PP
MUTAG jeci and
MUTAG (sdi and miroww
02
Figure 16: The KL and KL performance the (L(PP,()
24

---

Published as a conference paper at ICLR 2023
perpChi (add and remove odpes)
YeloChi (odd and remove edges)
Yoboo (add remove edpea)
Yop22 (add and remove edgest
044
0.4
03
0.2
00
5.0
40
00
37
0.7
0.5 Pr(R))
33
0.7
0.0
PryS.)
PhyS.)
(155.)
SC-OTC (wde recrove edgred
SC-GTC (wid seminn wlgne))
(edd and remrve edgre)
UICI (jebh and nemoow wilge))
0.5
6-1
0.
0.
MUTAG
MUTAG edges)
Figure 17: The KL and KL performance the Pr)(Gi) PrJ(
25


Reviews:
[{"review_id": "uOjdfsP-yZM", "reviewer": "Reviewer_yCBP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper introduces a new method of explaining how GNNs respond to evolutions of graph structure through adding or removing edges. It models the outputs of the GNN as a probability distribution depending on the input graph which varies over time. In contrast to previous work, time is taken as a continuous parameter. The most relevant edge additions and deletions are calculated and used in a convex optimization problem to determine a time-dependent smooth parameterization of the GNN.", "summary_of_the_review": "The paper provides an interesting geometric perspective on time-dependent graph changes. But some of the choices of methods used seem arbitrary and could use more justification, specifically to how this particular choice of curve contributes to explainability or performance of the GNN.", "strength_and_weaknesses": "Strengths:\n-\n\n- The evolution of paths is formulated nicely as a convex optimization problem with a theoretical motivation by KL divergence minimization.\n\nWeaknesses:\n-\n\n- The focus is on interpolating between two graphs G0 and G1, but it's not clear why we care about intermediate stages when the data itself comes in discrete intervals, and the modifications to the graph are themselves discrete. The experiments do not seem to shed further light on this.\n\n- The interpolation doesn't seem to use global time information, only the probability distributions P(Y|G0) and P(Y|G1) at consecutive time intervals.\n\n- The convex optimization selects over a small number of paths in the computation graph which contribute the most to the change in the output vector. Determining the contribution of each path seems to be expensive to determine, especially for a GNN with many layers or a relatively dense edge structure. If this is not the case, it would be good to have some mention of the computational complexity of determining the highest-contributing paths.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jtfedj9j21D", "reviewer": "Reviewer_uccj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work studies the explainability on evolving graphs through the lens of “differential geometry”. While prior literature primarily focuses on static graphs, there are some works in the thread of evolving graphs against which the authors highlight certain differences in the introduction and related work. More concretely, the contributions of the work include - (i) embedding a manifold in an extrinsic euclidean space, (ii) designing extrinsic coordinates based on the contribution of paths to the predicted distributions on the computation graph of the GNN, (iii) defining a metric on the manifold and (iv) lastly, learning the curve that connects the two distributions and provide the desired explainability. The design of the coordinates is primarily based on prior work defining the set of $m$ length paths rooted at the node at hand $J$ with at least one altered edge from the initial graph to the final graph. The rationale is that these altered paths primarily lead to the altered predictions in the graph at the desired snapshot. The manifold is defined using the set $Pr(Y|G)$. The intrinsic dimension of the manifold is given by the sufficient statistics of $Pr(Y|G)$, which is parametrized by the contribution matrix (as described in eq 6, 7 and 8). Furthermore, they emphasize the idea that the evolution of $Pr(Y|G)$ is nonlinear on the manifold, which is based on the approximation of KL divergence provided in eq 9. This nonlinearity is attributed to the definitions - eq 6, 7 and 8. Lastly, they describe the curves using the specific types of parameterizations against the argument $\\Delta{C}_{J}(G_0, G_1)$ in eq 10. The final objective described in eq 12 involves the constrained optimization of KL divergence term based on the curve formulation. Experiments have been performed on multiple benchmark datasets along with comparisons against the baseline explainability techniques. \n", "summary_of_the_review": "Based on the questions and comments raised in the aforementioned sections, I lean towards acceptance of the work. I am willing to reconsider my score if the authors can try to address some of the questions.\n", "strength_and_weaknesses": "1. The proposed method is intuitively clear and well supported by treferenes to the literature.\n2. The results provided in the figures - 2, 3, 6, 7 and 8 clearly demonstrate that the proposed method outperforms the baselines (almost always).\n3. Comparing the runtime against other baseline method/s (potentially the runner-up) will be helpful in identifying the runtime performance tradeoff.\n4. As the work considers evolving graphs, discussing more than 2 snapshots in the evolution will be highly interesting. Have the authors performed some analyses on that? It will be interesting to study and helpful in demonstrating the effectiveness of the work.\n5. Some analyses on the threshold described in section A.4.2 in order to select the target node/edge/graph will be useful. Studying how the method performs on the spectrum of varying $KL(P_J(G_1)||P_J(G_0))$ for the node/edge/graph $J$ can help explore the limit of the work. \n6. Providing more details regarding the GNN hyperparameters and the training procedure can help assess the reproducibility of the work.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Mi1GHI26scw", "reviewer": "Reviewer_JnV5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method that gives a geometric viewpoint on the evolution of graphs and enhances their explanatory and interpretability. To capture changes in the graph of a discrete, we view the graph of each state as a subgraph of a larger graph, consider the space of probability distributions with respect to the links of that larger graph, and view them as curves on that space. The authors give specific procedures for interpreting the above perspectives based on differential geometry formulations. Experiments have also been conducted to verify the effectiveness of the method for the three tasks in the graph.", "summary_of_the_review": "The evolution of a graph is difficult to understand as a graph as it is, and being able to understand it as a curve on a manifold is of great value. This method is clearly described in the framework of differential and information geometry. On the other hand, there are some unclear areas, such as necessary conditions that are implicit. Clarifying these would make for a better paper.\n\n**Conclusion following discussion with the authors**\n\n It is now clear that the authors' claimed problem set is not affected by the concerns I had. On the other hand, I have the impression that the results obtained are more rudimentary than those discussed in similar directions, for example, in image representation learning. I think this is a good result for the future, so I have a positive impression, but I won't change the score.", "strength_and_weaknesses": "Strength\n\n- Interpretation of the evolution of graphs is more difficult than, for example, changes in images, so it is worthwhile to realize them.\n- It is organized according to a clearly systematized differential geometry scheme. Interpretations based on differential geometry are also used in the generative model, a method that is not new but is acceptable to those in this domain.\n\nWeakness\n\n- One concern is whether the graph can be handled continuously on the GNN manifold, since it will be discrete. That is, when perturbed on a GNN manifold, is there a graph corresponding to that point? Basically, all graphs may be considered as weighted graphs and considered continuous, which may be fine on a general level. However, I think the reference to this point is weak. The text may be structured in a misleading manner.\n- This method constructs a large graph containing all data nodes. However, it is limited to the case where data including all nodes are present at training time, and it is likely that it will not work well when nodes that are not present at training time are input. This is considered a more cautionary situation than the usual Out of Distribution. It is not a big problem for cases where all the nodes are known or for the purpose of analyzing a model that has already been trained, so please clarify in what situations it can be used appropriately.\n- I am not sure if what is shown in the experiment demonstrates the claim. I believe the authors' claim is that the proposed method makes graph evolution easier to understand. For example, it is expected to track the length of the corresponding paths and the evolution of the graph in multiple evolutions between the same starting and ending data, etc. Please clarify why the experiment demonstrates the claim of this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JQDKl6Xavq", "reviewer": "Reviewer_gpiW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a probabilistic metric for explaining the change of GNN predictions in an evolving graph from the differential geometric perspective. The author first reformulates the distribution of GNN predictions in the context of path contributions. Then, the author establishes the distance metric based on the approximated KL divergence between the distributions of each class for evolving graphs. And therefore, it constructs the Reiman Manifold for measuring distribution shifts on predictions regarding the change in graphs. Last, the authors formulate the problem of explaining GNN predictions into the problem of minimizing the KL divergence between distribution shifts. In experiments, a subset of paths, which contribute the most to the evolving process, is disabled, and the KL divergence is calculated and appears to be small, which validates the explanation quality of the proposed methods.", "summary_of_the_review": "The paper is in general well written with coherence logic. The contributions are incremental. The experimental results appear to be good and support the conclusions. More explanations are needed to clarify a few ideas.", "strength_and_weaknesses": "Strength:\n1. The main contribution is marginal: the proposed manifold-based distance metric for measuring the smoothing evolutions of a graph. \n2. The experimental parts demonstrate that, for node classification tasks, the proposed method can find the most significant paths that explain the predictions of evolving graphs, thus, produce a good explanation. \n\nWeakness:\n1. Section 3.2 and 3.3 is kind of confusing. Need explanations about how Eq (10) and (11) are derived and calculated. How is the KL divergence second-ordered approximated by the Fisher information matrix? \n2. The proposed methods select a subset of paths that contributes most to the expansibility, yet the number of selected paths is vague. Please explain the criteria for selecting the paths from Table 3. \n3. A minor issue is the evolution of the graph is only constrained to adding or removing a subset of edges while the node features remain unchanged.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster