Characterizing the Influence of Graph Elements
Authors: Zizhang Chen
Peizhao Li
Hongfu Liu
Pengyu Hong
Venue: ICLR 2023 poster (2023)
Keywords: Interpretable Machine Learning
Influence functions
Graph Neural Networks

Abstract: Influence function, a method from the robust statistics, measures the changes of model parameters or some functions about model parameters with respect to the removal or modification of training instances. It is an efficient and useful post-hoc method for studying the interpretability of machine learning models without the need of expensive model re-training. Recently, graph convolution networks (GCNs), which operate on graph data, have attracted a great deal of attention. However, there is no preceding research on the influence functions of GCNs to shed light on the effects of removing training nodes/edges from an input graph. Since the nodes/edges in a graph are interdependent in GCNs, it is challenging to derive influence functions for GCNs. To fill this gap, we started with the simple graph convolution (SGC) model that operates on an attributed graph, and formulated an influence function to approximate the changes of model parameters when a node or an edge is removed from an attributed graph. Moreover, we theoretically analyzed the error bound of the estimated influence of removing an edge. We experimentally validated the accuracy and effectiveness of our influence estimation function. In addition, we showed that the influence function of a SGC model could be used to estimate the impact of removing training nodes/edges on the test performance of the SGC without re-training the model. Finally, we demonstrated how to use influence functions to effectively guide the adversarial attacks on GCNs.

Published as a conference paper at ICLR 2023
CHARACTERIZING THE INFLUENCE OF GRAPH ELE- MENTS
Zizhang Chen, Peizhao Li, Hongfu Liu, Pengyu Hong Brandeis University (z i zhang2, pei zhaoli, i, hongful iu, howgpengg@brandeiss.oo edu
ABSTRACT
Influence function, method from robust statistics, measures the changes of model parameters or some functions about model parameters concerning the removal or modification of training instances. It is an efficient and useful post-hoc method for studying the interpretability of machine learning models without the need for ex- pensive model re-training. Recently, graph convolution networks (GCNs), which operate on graph data, have attracted a great deal of attention. However, there is no preceding research the influence functions of GCNs to shed light the effects of removing training nodes/edges from an input graph. Since the nodes/edges in a graph are interdependent in GCNs, it is challenging to derive influence functions for GCNs. To fill this gap, we started with the simple graph convolution (SGC) model that operates on an attributed graph and formulated an influence function approximate the changes of model parameters when a node or an edge is removed from an attributed graph. Moreover, we theoretically analyzed the error bound of the estimated influence of removing an edge. We experimentally validated the accuracy and effectiveness of our influence estimation function. In addition, we showed that the influence function of SGC model could be used to estimate the impact of removing training nodes/edges on the test performance of the SGC with- out re-training the model. Finally, we demonstrated how use influence functions to guide the adversarial attacks on GCNs effectively.
INTRODUCTION
Graph data is pervasive in real-world applications, such as, online recommendations (Shalaby al.
2017 Huang et al.] 2021; Li et al. 2021), drug discovery (Takigawa & Mamitsuka] 2013 Li et al.
2017) and knowledge management (Rizun) 2019 Wang 2018), to name few. The growing
need to analyze huge amounts of graph data has inspired work that combines Graph Neural Networks
with deep learning (Gori et al. 2005| Scarselli al. 2005 Li et al., 2016; Hamilton et al. 2017 Xu
jet al. 2019b] Jiang et al. 2019). Graph Convolutional Networks (GCNs) (Kipf & Welling 2017]
Zhang & Chen 2018 Fan et al. 2019). the most cited GNN architecture, adopts convolution and mnessage-passing mechanisms.
To better understand GCNs from data-centric perspective, we consider the following question:
Without model retraining, how can we estimate the changes of parameters in GCNs when the graph used learning is perturbed by edge- nedevaemovass?
This question proposes to estimate counterfactual effects on the parameters of well-trained model when there is a manipulation in the basic elements in graph, where the ground truth of such an effect should be obtained from model retraining. With a computational tool as the answer, we can efficiently manipulate edges nodes in graph to control the change of model parameters of trained GCNs. The solution would provide further extensions like graph data rectification, improving model generalization, and graph data poison attacks through pure data modeling way. Yet, current meth- ods for training GCNs offer limited interpretability of the interactions between the training graph and the GCN model. More specifically, graph elements on both the changes in model parameters and the generalizability of a trained model Ying et al. 2019 Huang et al. 2022
fall short of understanding the influence of the input
Yuan al. 2021 Xu et al. 2019a Zheng et al. 2021

---

Published as a conference paper at ICLR 2023
In the regime of robust statistics, analyzing tool called influence functions (Hampel 1974 Koh
& Liang 2017) is proposed to study the counterfactual effect between training data and model per- formance. For independent and identically distributed (i.i.d)) data, influence functions offer an ap- proximate estimation of the model's change when there is an infinitesimal perturbation added to the training distribution, e-g., reweighing on some training instances. However, unlike i.i.d. data, ma- nipulation on a graph would incur a knock-on effect through GCNs. For example, an edge removal will break down all message passing that is supposed tially change node representations and affect the final model optimization. Therefore, introducing influence functions to graph data and GCNs is non-tri non-trivial work and requires extra considerations.
pass through this edge and consequen-
In this work, we aim to derive influence functions for GCNs. As the first attempt in this direction, we focused on Simple Graph Convolution (Wu et al. 2019). Our contributions are three-fold:
We derived influence functions for Simple Graph Convolution. Based on influence functions, we developed computational approaches to estimate the changes in model parameters caused by two basic perturbations: edge removal and node removal.
We derived the theoretical error bounds to characterize the gap between the estimated changes and the actual changes in model parameters in terms of both edge and node removal.
We show that our influence analysis on the graph can be utilized to (1) rectify the training graph to improve model testing performance, and (2) guide adversarial attacks to SGC or conduct grey-box attacks on GCNs via surrogate SGC.
Code is publicly available at hut.ass//gttaaaacom////////////2 graph influence
2
PRELIMINARIES
In the following sections, we use a lowercase r for scalar or an entity, an uppercase X for a constant or set, bolder lowercase x for a vector, and a bolder uppercase X for a matrix.
Influence Functions Influence functions (Hampel 1974) estimate the change in model param- eters when the empirical weight distribution of i.i.d. training samples is perturbed infinitesi- mally. Such estimations are computationally efficient compared to learn-one-out retraining it- erating every training sample. For N training instances x and label y. consider empirical risk minimization (ERM) Å arg min N Ex., ((x. v) + |10112 for some loss function E(:,-) through parameterized model 0 and with a regularization term. When down weighing train- ing sample (x,, y4) by an infinitely small fraction e, the substitutional ERM can be expressed as 0(x;; -) = arg mingee N Ex,r f(x, y) - el(x,, we) + Í 11011. Influence functions estimate the actual change I (xx: cc = 0(x; -c) - for a strictly convex and twice differentiable E(,,):
I(x; - t) = lim 0(x;; -)) - - V (gl((x,,, Wi), c00
(1)
where == EN Vel(x, v:) AI is the Hessian matrix with regularization at parameter 0. For some differentiable model evaluation function f + R like calculating total model loss over a test set, the change from down weighing by (0) VVl(xi, y.). When N the size of the training data is large, by setting e N. we can
(x,; 31) to the evaluative results can be approximated
approximate the change of ê incurred by removing an entire training sample I(x;; 1 I( xx,)
via linear extrapolations 1 + O. Obviously, in terms of the estimated influence I, removing training sample has the opposite value of adding the same training sample I(-x,) I (+x;). In our work, we shall assume an additivity of influence functions in computations when several samples are removed, e.g., when removing two samples: I(-x;, -X,) I(-x,) + I(-x,).
Though efficient, as a drawback, influence functions on non-convex models suffer from estimation emrors due to the variant local minima and usually computational approximation to H for a non- invertible Hessian matrix. To introduce influence functions from i.i.d. data to graphs and precisely characterize the influence of graph elements to model parameters' changes, we consider a convex model called Simple Graph Convolution from the GCNs family.
2

---

Published as a conference paper at ICLR 2023
Simple Graph Convolution By removing non-linear activations between layers from typical Graph Convolutional Networks, Simple Graph Convolution (SGC) (Wu et al. 2019) formulates various tasks (He et al., 2020)
linear simplification of GCNs with competitive performance Rakhimberdina & Murata 2019). Let G = (V, F.) denote an undirected attributed graph, where V = [0f contains vertices with corresponding feature X E R V with D the feature dimension, and E = {egghsssjsj is the set of edges. Let I, denote the set of neighborhood nodes around v, and d, the node degrees of u. We use A denote the adjacency matrix where Aij = Aji = if egg E, and O elsewhere. D diag(d.) denotes the degree matrix. When the context is clear, we simplify the notation Fe, + r, and the same manner for other symbols. For multi-layer GNNs, let z!! denote the hidden representation of node v in the k-th layer, and with z! X2 the initial node features. Simple Graph Convolution processes node representations as: 2 W(k) (uer,,u()) du 1,,122,1// Zi (/(= + b(&) where W(k) and ((k) are trainable parameters in k-tth layer. In transductive node classification, let Virain C V denote the set of N training nodes asso- ciated with labels y. ERM of SGC in this task is i arg mingge NV Evev.... ((z :y0) + 3 [10112- Due to the linearity of SGC, parameters (()) and b in each layer can be unified, and predictions after k layers can be simplified as y arg max D à AA y X + b with A A + I and D the degree matrix of A. Therefore, for node representations (k) (D 1 AD + )a with y and cross-entropy loss, .(:-)) is convex. The parameters A in consist of matrix W DD [Class] and vector b R [Class] with [Class] the number of class, and be solved via logistic regression.
Additional Notations In what follows, we shall build our influence analysis upon SGC. For no- tational simplification, we omit (k) in (kk) and use Z denote the last-layer node representations from SGC. We use (- = (--es)) - i to denote the actual model parameters' change where O(-ei)) is obtained through ERM when eij is removed from E. Likewise, I*(-u: denotes the change from 2t's 's removal from graph G. I(-ei,) and I(=2;) are the corresponding estimated influence for I (-eig) and I (-v;) based on influence functions, respectively.
3 MODELING THE INFLUENCE OF ELEMENTS IN GRAPHS
We mainly consider the use of influence functions of two fundamental operations over an attributed graph: removing an edge (in Section 3.1) and removing complete node (in Section 3.2)
3.1 INFLUENCE OF EDGE REMOVAL
With message passing through edges in graph convolution, removing an edge will incur representa- tional changes in Z. When Gij is removed, the changes come from two aspects: (1) The message passing for node features via the removed edge will be blocked, and all the representations of k-hop neighboring nodes of the removed edge will be affected. (2) Due to the normalization operation over A, the degree of all adjacent edges Ezk, Vk E Л, and esk: Vk E T will be changed, and these edges will have larger value in - 1 AD 4, We have the following expression to describe the representational changes A(-ei) of node representations Z in SGC incurred by removing Cij-
A(-ee) [(((-es) A((es))) (x) ((-
(D -b- AD "|x
(2)
A(-eg) is the modified adjacency matrix with A(- -i))) (1/je 0 and (- A elsewhere. A(-eg) = A(-e;)) + and D--e,)) the degree matrix of A(-es)). By having A (--et))
). we can access the change in every node. Let (x(() denotes the k-th row in A A(-et)). 64 0 implics no change in k-th node from removing eaj. and & + O indicates a change in Zy--
We proceed Our high-level idea is, from an influence functions perspective, representational changes nodes z + z + 8 is equivalent to removing training instances with feature z, and adding new training instances with feature + 5 and with the same labels. The problem thus turns back to an instance reweighing problem developed by influence functions. In this case, have the lemma below to prove the influence functions' linearity.
influence functions to characterize the counterfactual effect of removing Cij-
Lemma 3.1. Consider empirical risk minimization θ = arg mingee E, E(x, y.) and 0(x; + x, + 5) arg mingge Eizz ((x,, vi) + [(x, + 5, yU) with some wice-differentiable and strictly convex
3

---

Published as a conference paper at ICLR 2023
e, let (xx, -x + [(x; >x + +) - 8, the estimated inftuence satisfies linearity: I(x; + xj + 6) I(-x,) + Z(+(xx 66).
(3)
By having Lemma 3.1 we are ready to derive proposition from characterizing edge removal.
Proposition 3.2. Let dg(-eis) denote the k-th row of ((-esg). The influence of removing an edge Cij E E from graph G can be estimated by:
I(-ei)) = I(z + (=zto(-es))
Σ I(+(Z= + )x((ei))) + +I(-2s)
&
(4)
= H Σ (Vollz) + 6x (- yk.) V / jl(Zz Uk))
P.EV
Proof. The second equality comes from Lemma 3.1 and the third equality comes from Equation (1)
Zi: zj) = I( 2,) + z{₃)) completing the proof. Realize that removing two representations I( (-z;;
Proposition 3.2 offers approach to calculate the estimated influence of removing Cij- In practice, having the inverse hessian matrix, a removal only requires users to compute the updated gradients Vgl(zz & (-ei)), ys)) and its original gradients for all affected nodes in (k+1)-hop neighbors.
3.2 INFLUENCE NODE REMOVAL
We address the case of node removal. The impact from removing node from graph G' to param- eters' change are two-folds: (1) The loss term {(x, yi) will no longer involved ERM if v2 Vinin- (2) All edges link to this node {eish, J. vj E I; will be removed either. The first aspect can be deemed as a regular training instance removal similar to an i.i.d. case, and the second aspect be can an incremental extension from edge removal in Proposition 3.2
The representational changes from removing node vú can be expressed as:
(--u: = (D((-))) vx) - A - D(- (D - AD - 1
(5)
with A A- j/)kk A jk/kj, Vj. i A & T; and A(-#;) 0 elsewhere. Similarly, A ( = A( Uj + I and D (-2;) is the corresponding degree matrix Á Having state the estimated influence of removing v:-
A A--o), Lemma 3.1 and Proposition 3.2
Proposition 3.3. Let 6,(- denote the j-th row of A(-vs). The influence of removing node is
from graph G can be estimated by:
I(-o:) I(-Z:) + I(z + z (22+8---)) 8(-v:)) I(--;; + Σ + +5,(- + I(-z,)
= ee Vine
H H (2.. (2:
H
Σ
(Vgl(z) + 55(-u)), Vgl(z,
My Vena
where 1 is an indicator function.
Proof. Combining Lemma
3.1 and Equation
completes the proof.
THEORETICAL ERROR BOUNDS
In the above section, we show how to estimate the changes of model parameters due edge removal:
i + 0(-ezy) and node removals: á - 0(-u;). In this section, we study the error between the estimated influence given by influence functions I and the actual influence I obtained by model retraining. We give upper error bounds on edge removal I (-ets) - I[(es;)) ll2 (see Theorem 4.1
and node removal | (-u;) I(-u;)ll 1|) (see Corollary A.I
In what follows, we shall assume the second derivative of ((..)) is Lipschitz continuous at O with constant C based on the convergence theory of Newton's 's method. To simplify the notations,
z! Z; + 6; to denote the new representation of v; obtained after removing an edge or a node, where 6, is the row vector of A (--es) or A(-r:) depending on the context.
4

---

Published as a conference paper at ICLR 2023
Theorem 4.1. Let min 2 0 denote the smallest eigenvalue of all eigenvalues of Hessian matrices (Z, 36), Vo, E Virain of the original model 0. Let d 2 denote the smallest eigenvalue of all eigenvalues of Hessian matrices V V Eizi, Y1), Vo, E Virain of the retrained model ((-ex)) with eij removed from graph G. Use I. denote the set {u= z' $ 2. containing affected nodes from the edge removal, and Err(-e;j) = (- -I([ee)) Recall is the lg regularization strength, we have an upper bound the estimated error of model parameters' change:
((-=)s)
NºC
Err(-eig) S (NA+ (N- mLl) + min [I]33
Σ
V V&((z), Vo((2).)))
WELL
N
(V8 (Vl((z)))) Fgl(z),31))l
N (N min + min(o (miire miaa)
Proof sketch. We use the one-step Newton approximation (Pregibon 1981) as an intermediate step to derive the bound. The first term is the difference between the actual change (-(ee) and its Newton approximation, and the second term is the difference between the Newton approximation and the estimated influence I(-es)). Combining these two parts result the bound.
L
Remark 4.2. We have the following main observations from Theorem 4. (1) The estimation error of influence function is controlled by the & regularization strength within factor of (1/A). A stronger regularization will likely produce a better approximation.
(2) The error is controlled by the inherent property of model. A smoother model in terms of its hessian matrix will help lower the upper bound. (3) The upper bound is controlled by the norm of the changed gradient from z + z'. Intuitively, if removing eij incurs smaller changes in node representations, the approximation of the actual influence would be more accurate. Also, smaller Err( (-)) is expected if the model is less prone to changes in training samples. (4) There are no significant correlations between the bound and the number of training nodes N. As special case, if min d' 0, the bound is irrelevant to N. We attach empirical verification for our bound in Appendix
Similar to Theorem 4.1 we have Corollary A.1 derive an upper bound on [I'(--;; II-ee)
for removing a node &2 from graph presented in Appendix
5 EXPERIMENTS
We conducted three major experiments: (1) Validate the estimation accuracy of our influence func- tions on graph in Section 5.2 (2) Utilize the estimated edge influence carry out adversarial attacks and graph rectification for increasing model performance in Section 5.33 and (3) Utilize the estimated node influence carry out adversarial attacks on GCN (Kipf & Welling 2017) in Section [.4
5.1 SETUP
We choose six real-world graph datasets:Coru, PubMed, CiteSeer (en et al.; 2008), WiKi- CS (Mernyci Cangea 2020). Amazon Computers, and Amazon Photos (Shchur et al. 2018) in experiments. Statistics of these datasets are outlined in Appendix B Table 4 For the Cora, PubMed, and CiteSeer datasets, we used their public train/val/test splits. For the Wiki-CS datasets, took random single train/val/test split provided by Memyyii & Cangea (2020). For the Amazon datasets, we randomly selected 20 nodes from each class for training, 30 nodes from each class for validation and used the rest nodes in the test set. All the experiments are conducted under the transductive node classification settings. We only use the last three datasets for influence validation.
5.2 VALIDATING INFLUENCE FUNCTIONS ON GRAPHS
Validating Estimated Influence We compared the estimated influence of removing node/edge with its corresponding ground truth effect. The actual influence obtained by re-training the model after removing node/edge and calculating the change in the total cross-entropy loss. We also validated the estimated influence of removing node embeddings, for example, removing E(z, 9:) of node v; from the ERM objective while keeping the embeddings of other nodes intact. Figure
5

---

Published as a conference paper at ICLR 2023
Infi Infi
class 2
Inft.
class
Infi.
Inft.
class 5
Infi, ++
Infi. ++
plass
The Cora experiment the estimated influences of individual training nodes/edges on the validation loss. The largest connected component of the Cora dataset is visualized here. Left: The dataset. The node size indicates if node is in the training subset (large) or not (small), Middle: Influence of the training edges. Each edge colored accordingly to its estimated influence value (blue negative influence, removing is expected to decrease the loss the validation set; red positive influence, removing influence. The deeper color indicates higher influence.). Right: Influence of the training nodes. The same color scheme in the middle plot is used here.
Figure 1:
expected to increase the loss on the validation set, and grey - little
shows that the estimated influence correlates highly with the actual influence (Spearman correlation coefficients range from 0.847 0.981). More results are included in Figure in the appendix.
Visualization Figure visualizes the estimated influence of edge and node removals on the val- idation loss for the Coru dataset. This visualization hints at opportunities for improving the test performance of a model or attacking model by removing nodes/edges with noticeable influences (see experiments in Sections 5.3 and 5.4).
5.3 APPLICATIONS OF THE ESTIMATED EDGE INFLURNCE.
The estimated influence of edge removals on the validation set can be utilized to improve the test performance of SGC or carry out adversarial attacks on SGC/GCN.
Graph Rectification via Edge Removals We be-
Table 1:
Our performance via eliminating
gin by investigating the impact edges with nega- tive influences. Based on influence analysis, moving negative influence edges from the original will decrease validation loss. Thus the classifica- tion accuracy on the test set is expected to increase correspondingly. We sort the edges by their esti- mated influences in descending order, then cumula- tively remove edges starting from the one with the lowest negative influence. We train the SGC model, fine-tune on the public split validation lect the number of negative influence edges to be removed by validation accuracy. For a fair comparison, we fix the test set remaining unchanged regarding the removal of the edges. The results derived based Figure and displayed in Table I where we also report the performance of several classical and statc-of-thh-art GNN models the original whole set references, including GCN (Kipf & Welling 2017), GAT (Veličković et al. 2018). FGCN (Chen et al., 2018), GIN (Xu et al. 2019b). DGI /Velickovic et al. 2019) with
edges with negative influence values.
Methods
Cora
Pubmed
Citeseer
GCN
81.4 0.4
79.0
0.
70.1 + 0.5
GAT
83.3 0:7.
78.5 003
72.6 0:66
FGCN
79.8 0:3
77.4 03
68.8 0
GIN
1.16
77.0 122
66.1 0.9
DGI
82.5 0.7
78.4
71.6
SGC
$1.0400
78.9 000
71.9 4.11
Ours
81.8 + 0.0
79.7 0.
73.7 + 0.
and se-
nonlinear activation function and SGC (Wu al. 2019).
We demonstrate that our proposed method can marginally improve the accuracy of SGC from the data perspective and without any change the original model structure of SGC, which validates

---

Published as a conference paper at ICLR 2023
Cora
Pubmed
Citeseer
20
20
20
Pred. Embed. Inft.
p= 0.978
0=9.949
Pred. Embed. Infl.
p= 0.976
Pred. Feat, Infl.
10
10
10
-10
-10
-10
-20
-20
-20
-20
-10 0
10
-20
-10
10
20
-20
-10
0
10
Act. Feat. Infl.
Act. Embed. Infl.
Act. Feat. Infl.
0=0.881
0=0.942
p=0.847
Pred. Edge Inft.
Pred. Edge infl.
Pred. Edge Infl.
-3
-3
-6
-6
-3
0
3
6
-3
0
3
6
Act. Edge Infl.
Act. Edge Infl.
Act. Edge Infl.
10
0.981
10
0.974
10
p=0.968
Pred. Node Infl.
Pred. Node Infl.
Pred. Node Infl.
0
0
-5
-5
-5
-10
-10
0
10
-10
10
-10
0
10
Act. Node Infl.
Act. Node Infi.
Act. Node Infl.
Figure 2: Estimated influence vs. actual influence. Three datasets are used in this illustration Cora (left column), Pubmed (middle column) and Citeseer (right column). In all plots, the horizontal axes indicate the actual influence on the validation set, the vertical axes indicate the predicted influence, and p indicates Spearman's correlation coefficient between predictions and the actual influences. Top row: Influence of node embedding removal. Each point represents training node embedding Middle row: Influence of edge removals. Each point corresponds to a removed edge. Bottom row: Influence of node removal. Each point represents removed training node.
Table 2: Grey-box attacks GCN via edge removals. lower performance indicates a more suc- cessful attack. The best attacks are in bold font. The number following the dataset name is the pre- attack performance. '.' denotes an out-of mut-of-memory issue encountered on GPU with 24GB VRAM.
Dataset
Cora 80.1
Citeseer - 70.07%
Pubmed 79.80%
Elimination Rate
1%
3%
5%
1%
3%
5%
1%
3%
5%
DICE
79.9%
80.1% 1%
80.0%
71.1%
70.3%
69.8%
79.4%
79.7%
79.1%
GraphPoison
80.0%
80.1% %
79.6%
70.2%
70.1%
70.0%
79.4%
79.7%
79.1%
MetaAttack
79.6%
77.1%
73.3%
70.4%
69.3%
65.4%
Ours
77.3%
74.2%
72.8%
69.3%
67.4%
64.7%
69.3%
65.2%
64.1%
the impacts of edges with negative influences. In addition, the performance of the SGC model with eliminating the negative influence edges can outperform other GNN-based methods in most cases.
Attacking SGC via Edge Removals We investigated how to use edge removals to deteriorate SGC performance. Based on the influence analysis, removing an edge with a positive estimated the validation set.
influence can increase the model loss and decrease the model performance Thus, our attack is carried out the following way. We first calculated the estimated influence of all edges and cumulatively removed edges with the highest positive influence we remove a new edge, we retrain the model to obtain the current model performance. We remove 100 edges in total for each experiment.
time. Every time
7

---

Published as a conference paper at ICLR 2023
Cora: Edge sorted Inf).
Pubmed: Edge sorted Infl.
Citeseer: Edge sorted Infl.
2
2
inft
1
0
25
50
75
100
25
50
75
100
0
25
50
75
100
0.80
0.74
0.80
0.78
0.72
0.78
0.75
Acc.
0.70
0.76
0.73
0.74
0.70
0.68
100
50
100
50 Num. Edges removed
100
Num. Edges removed
Num. Edges removed
Figure 3: Study of edges with positive influence both validation (blue) and test (red) set. Columns correspond to Cora, Pubmed and Cileseer datasets. Top: scale of values of the edges with negative influence. Bottom:
accuracy drop by cumulatively removing edges with positive influence.
Table 3: Performance of node removing attack. Lower performance means better attacks. The number after the dataset name means the performance of GCN model without attack. Victim model's 's test accuracy averaged over 25 runs on the citation network.
Dataset
Cora 81.10%
Citeseer - 70.07%
Pubmed 79.80%
Removing Rate
5%
10%
15%
5%
10%
15%
5%
10%
15%
Random
80.4%
80.3%
80.2%
70.6%
69.0%
69.2%
78.9%
79.6%
77.3%
Degree
80.3%
78.7%
79.0%
69.4%
68.3%
68.4%
79.1%
79.6%
77.4%
Ours
74.7%
59.8%
57.9%
69.5%
65.5%
56.1%
79.0%
77.2%
75.2%
We present our results in Figure 3 Apparently, in general, the accuracy of SGC on node classifica- tion drops significantly. We notice the influence of edges approximately power-law distributed, where only small proportion of edges has a relatively significant influence. The performance worsens with increasingly cumulative edge removals on both validation and test sets. The empirical results verify expectations of edges with positive estimated influence.
Attacking GCN via Surrogate SGC We further explored the impact of removing positive influ-
ences edges under adversarial grey-box attack settings. Here, we followed Zügner & Günnemann (2019) to interpret SGC as a surrogate model for attacking the GCN (Kipf & Welling] (017) as victim model, where the assumption lays under that the increase of loss SGC implicitly drop the performance of GCN. We eliminated positive influence edges at different rates 1%, 66.3%,75 5% among all edges. The drop in accuracy was compared against DICE (Zügner et al.) 2018), Graph- Poison (Bojchevski & Günnemann] 2019), MetaAttack (Zügner et al.) 2018). For a fair comparison, we restrict the compared method can only perturb graph structures via edge removals.
Our results are presented in Table 2 Our attack strategy achieves the best performance in all the scenarios of edge eliminations, especially on Pubmed with 1% edge elimination rate. Our attack model outperforms others by over 10% in accuracy drop. Since we directly estimate the impact of edges on the model parameter change, our attack strategy is more effective in seeking the most vulnerable edges to the victim model. These indicate that our proposed influence on edges can guide the construction of grey-box adversarial attacks on graph structures.
5.4 INFLUENCE OF NODE REMOVAL
Attacking GCN via Node Removals In this section, study the impact of training nodes with a positive influence on transductive node classification tasks. Again, we assume that eliminating the positive influence nodes derived from SGC may implicitly harm the GCN model. We sort the nodes
8

---

Published as a conference paper at ICLR 2023
by estimated influence in descending order and cumulatively remove the nodes from the training set. We built two baseline methods, Random and Degree, to compare the accuracy drop in different node removal ratios: 5%. 10%, 15%. For the Random baseline, randomly remove the nodes from the training sets. For Degree baseline, we remove nodes by their degree in descending order.
According Table Table the model performance GCN drops by a large margin in all three citation network datasets as the selected positive influence node is removed, especially on the Cora dataset. The model outperforms the baseline over 20% on 15% removing ratio. These results indi- cate that our estimation of node influence can be used to guide the adversarial attack on GCN in the settings of node removal.
RELATED WORKS
Influence Functions Recently, more efforts have been dedicated to investigating influence fune- tions (Koh et al.) 2019: Giordano ct al. 2019 Ting & Brochu, 2018) in various applications, such as,computer vision (Koh & Liang, 2017). natural language processing (Han et al., 2020), tabular data (Wang et al.] 2020b). causal inference (Alaa & Van Der Schaar 2019). data poisoning at- tack (Fang et al. 2020 et al.) 2020a), and algorithmic fairness (Li & Liu 2022). this work, propose major extension of influence functions to graph-structured data and systemically study how we can estimate the influence of nodes and edges terms of different editing operations on graphs. We believe our work complements the big picture of influence functions in machine learning applications.
Understanding Graph Data Besides influence functions, there many other approaches to ploring the underlying patterns in graph data and its elements. Explanation models for graphs (Ying al.) 2019 Huang al. 2022 Yuan al. 2021 Bajaj al. 2021 Abrate & Bonchi 2021) provide an accessible relationship between the model's predictions and corresponding elements in graphs or subgraphs. They show how the graph's 's local structure or node features impact the decisions from GNNs. As major difference, these approaches tackle model inference with fixed parameters, while we focus on counterfactual effect and investigate the contributions from the presence of nodes and edges in training data to decisions of GNN models in the inference stage.
Adversarial Attacks on Graph The adversarial attack on an attributed graph usually conducted by adding perturbations on the graphic structure or node features (Züggner & Günnemann 2019] Zheng et al.] (02T). In addition, [Zhang al. (2020) introduces an adversarial attack setting by flipping small fraction of node labels in the training set that causes significant drop in model performance. A majority of the attacker models (Zügner et al. 2018 Xu et al., 2019a) on graph structure are constructed based on the gradient information achieved costly but effective attacking results. These attacker models rely mainly on greedy- methods to find the graph structure's 's optimal perturbations. We only focus the perturbations resulting from eliminating edges and directly estimate the change of loss in response to the removal effect guided by the proposed influence-based approach.
both edges and node features and
CONCLUSIONS
We have developed novel influence analysis to understand the effects of graph elements the parameter changes of GCNs without needing to retrain the GCNs. We chose Simple Graph Con- volution due to its convexity and its competitive performance non-linear GNNs on a variety of tasks. Our influence functions can be used to approximate the changes in model parameters caused by edge or node removals from an attributed graph. Moreover, we provided theoretical bounds on the estimation error of the edge and node influence on model parameters. We experimentally val- idated the accuracy and effectiveness of our influence functions by comparing its estimation with the actual influence obtained by model retraining. We showed in our experiments that our influence functions could be used to reliably identify edge and node with negative and positive influences on model performance. Finally, we demonstrated that our influence function could be applied to graph rectification and model attacks.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
We would like to thank the three anonymous reviewers for their constructive questions and invalu- able suggestions. This work partially supported by NSF DMR 1933525 and NSF OAC 1920147. Any opinions or conclusions in this paper are those of the authors and do not reflect the views of the funding agencies.
REFERENCES
Carlo Abrate and Francesco Bonchi. Counterfactual graphs for explainable classification of brain networks. In Proceedings of the 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2021.
Ahmed Alaa and Mihaela Van Der Schaar. Validating causal inference models via influence func- tions. In International Conference on Machine Learning, 2019.
Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. Robust counterfactual explanations graph neural networks. In Advances in Neural Information Processing Systems, 2021.
Alcksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. International Conference on Machine Learning, 2019.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. International Conference on Learning Representations, 2018.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, 2019.
Minghong Fang, Neil Zhenqiang Gong, and Jia Liu. Influence function based data poisoning attacks to top-n recommender systems. In Proceedings of The Web Conference, 2020.
Ryan Giordano, William Stephenson, Runjing Liu, Michael Jordan, and Tamara Broderick. swiss army infinitesimal jackknife. In International Conference on Artificial Intelligence and Statistics, 2019.
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In Proceed- ings of the IEEE International Joint Conference on Neural Networks, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances Neural Information Processing Systems, 2017.
Frank R Hampel. The influence curve and its role in robust estimation. Journal of the American Statistical Association, 1974.
Xiaochuang Han, Byron C Wallace, and Yulia Tsvetkov. Explaining black box predictions and unveiling data artifacts through influence functions. Annual Meeting of the Association for Com- putational Linguistics, 2020.
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development Information Retrieval, 2020.
Chao Huang, Jiahui Chen, Lianghao Xia, Yong Xu, Peng Dai, Yanqing Chen, Liefeng Bo, Jiashu Zhao, and Jimmy Xiangji Huang. Graph-enhanced multi-tase task learning of multi-level transition dynamics for session-bace recommendation. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
10

---

Published as a conference paper at ICLR 2023
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local inter- pretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022.
Xiaolong Jiang, Peizhao Li, Yanjing Li, and Xiantong Zhen. Graph neural based end-to-end data association framework for online multiple-object tracking. arXiv preprini arXiv: Nekiv:/907.05311 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. International Conference on Learning Representations, 2017.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Internatioboona Conference on Machine Learning, 2017.
Pang Wei Koh, Kai-Siang Ang, Hubert Teo, and Percy S Liang. On the accuracy of influence functions for measuring group effects. In Advances in Neural Information Processing Systems, 2019.
Junying Li, Deng Cai, and Xiaofei He. Learning represstatto for drug discovery. arXiv preprint arXiv:1709. 0.774, 2017.
Peizhao Li and Hongfu Liu. Achieving fairness at no utility cost via data reweighing with influence. In International Conference on Machine Learning, 2022.
Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. On dyadic fairness: Exploring and mitigating bias in graph connections. In International Conference on Learning Representa- tions, 2021.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. International Conference on Learning Representations, 2016.
Péter Mernyei and Cătälina Cangea. Wiki-es: A wikipedia-based benchmark for graph neural net- works. arXiv preprint axXiv:2007.02901, 2020.
Daryl Pregibon. Logistic regression diagnostics. The annals of statistics, 94):7055 1981.
Zarina Rakhimberdina and Tsuyoshi Murata. Linear graph convolutional model for diagnosing brain disorders. In International Conference on Complex Networks and Their Applications, 2019.
Mariia Rizun. Knowledge graph application in education: literature review. Acta Universitatis
Lodziensis. Folia Oeconomica, 2019.
F. Scarselli, S. L. Yong, M. Gori, M. Hagenbuchner, A. C. Tsoi, and M. Maggini. Graph neu- ral networks for ranking web pages. In Proceedings of the 2005 IEEE/WIC/ACM International Conference Web Intelligence, 2005.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.
Collective classification in network data. Al magazine, 2008
Walid Shalaby, BahaaEddin AlAila, Mohammed Korayem, Layla Pournajaf, Khalifeh AlJadda, Shannon Quinn, and Wlodek Zadrozny. Help me find job: A graph-based approach for job recommendation scale. In 2017 IEEE international conference on big data (big data), pp- 1544-1553. IEEE, 2017.
Oleksandr Shchur. Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurlPS 2018, 2018
Ichigaku Takigawa and Hiroshi Mamitsuka. Graph mining: procedure, application to drug discovery and recent advances. Drug Discovery Today, 2013.
Daniel Ting and Eric Brochu. Optimal subsampling with influence functions. In Advances Neural Information Processing Systems, 2018.

---

Published as a conference paper at ICLR 2023
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. Interaational Conference on Learning Representations, 2018.
Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. International Conference on Learning Representations, 2019.
Binghui Wang, Tianxiang Zhou, Minhua Lin, Pan Zhou, Ang Li, Meng Pang, Cai Fu, Hai Li, and Yiran Chen. Evasion attacks graph neural networks via influence function. arXiv preprint vrXiv:2009.00203, 2020a.
Ruijie Wang. Yuchen Yan, Jialu Wang. Yuting Jia, Ye Zhang, Weinan Zhang, and Xinbing Wang- Acekg: A large-scale knowledge graph for academic data mining. Proceedings of the 27th ACM International Conference on Information and Knowledge Management, 2018
Zifeng Wang, Hong Zhu, Zhenhua Dong, Xiuqiang He, and Shao-Lun Huang. Less is better: Un- weighted data subsampling via influence function. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020b.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In International Conference Machine Learning, 2019.
Kaidi Xu, Hongge Chen, Sijia Liu, Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. Interna- fional Joint Conferences Artificial Intelligence Organization, 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019b.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in Neural Information Process- ing Systems, 2019.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In International Conference on Machine Learning, 2021.
Mengmei Zhang, Linmei Hu, Chuan Shi, and Xiao Wang. Adversarial label-flipping attack and defense for graph neural networks. In IEEE International Conference on Data Mining, 2020.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, 2018.
Qinkai Zheng, Xu Zou, Yuxiao Dong, Yukuo Cen, Da Yin, Jiarong Xu, Yang Yang, and Jie Tang- Graph robustness benchmark: Benchmarking the adversarial robustness of graph machine learn- ing. Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference Learning Representations, 2019.
12

---

Published as a conference paper at ICLR 2023
A PROOFS
Lemma 3.1. Consider empirical risk minimization θ = arg mingee E, (xx, Vs) and 0(x; + + 5) arg mingee Eizj f(x;, Vs) + {(x, + 6, 5,))) with some twice- sicce-ifferentiable and strictly convex let I (x, - xj 5) {xx; Xj + - 0, the estimated influence satisfies linearity:
I(x; xj 6) -(-x;) [x, 6)).
Proof. Notice the actual model parameters in response of the perturbations A can be denoted as:
1 _ l ((5 8, N
8(x; xx + 8) arg min OEB N
e (xx. un) (x,,
In this case, the actual change in model parameters in response of the perturbations can be repre- sented as: I(x; + Xj + 5)=0(x; - x, + 6)-ô. For estimating A0, we start by considering the parameter change from up weighting infinite small on (xi) and down weight infinite small on {xi} where VI E L. By definition, the model parameter in response of perturbation 0_ can be represented as:
i def arg min 8EB
Σ e (xk. yk) el (x,, 95) + el (xy + 6, 0,)))
(8)
The change model parameter to the modification on group data's weight on loss be:
A6 6 -
(9)
Since 0g minimize the changed loss function under perturbation, take the derivative:
6. (xx, uk) - V (xx, Uj)
(10)
1=
+ (x, + 6, Us)
Apply the first order Taylor expansion of 6- on â on the right side of the equation, have:
N
Vol V 2k) Voo (x, + +6,4,) - - +
(11)
Vie (x,, wn) vn) ),93) V
-A0 + o(A0²)
Since i minimize the loss function without perturbation, Nv k==1 Vo e (xL, vk)= Dropping of o(Ao?) term, We have:
1 Σ
A0_ ~ Vill(xx (xk, yk) + + (x, 8. (, -
(12)
leV (x, 8, V pl (x,, vy)1
Take the derivative of 20, over e, by dropping (ee) terms we have:
dA8.
1
V 1 (Xx.
yx) [ / (x, + +,,1) -
de
N
(13)
H.
(x, + 5, (x(,,,,))
JEL
13

---

Published as a conference paper at ICLR 2023
For sufficient large N, by setting x. the changed approximate the actual change in model parameters using: I(x, + Xj + -)= + x, + 6) - -0. Plugging in to Eq. finish the proof:
we
I(x; + +
6) +x,+ - (VE + 0, --H (xx +. H Vi (x =I(+(x; + 6)) - I(-x))
V (5)
(14)
Proposition 3.3. Let 65(- denote the j-th row of ()- The influence of removing node U/
from graph G can be estimated by:
I(- I(- 2.) + I(z + + 8(-v;)) I(-;;) + Σ I(+ I(+(2) + +6((- I(-z))
=1 De Visis
H
H V (Z:
H Σ (Volla) + +,((-)),,)) Vol(2,, Ki)),
2/ E Voun
(6)
where 1. is an indicator function.
Proof. Similarly to the edge removal, we first calculate the node representation change incurred from the removal of the node v, of 2-layer SGC as follow:
A(- (--))=(DZ) D (D 2 AD
- ADAAA--y' A 1/p]x.
(15)
The above change will affect a set of nodes, including the node vs itself and the 2-hop neighbors of the node v; connected neighbors. A set of nodes S=(s|s E M UJEN, N2} capture the changed
node embeddings in the training set, i.e., 8_ f O. where A-., { in Eq. (15). The model parameter change of the removal the node v can be characterized by removing the representation of the node n; if the node U/ is training sample, and the node representation change from the set S. Thus, we have
I(-u,)
1 VvVin
I (12
Σ +E(S)m4
(I Uz) I (2.: vo))
(16)
= -1,,
H V LcE
(z:
H
Σ 8ES
(VLcE (2), - VLCE Vo)).
We finish the proof.
Theorem 4.1. Let a denote the smallest eigenvalue of all eigenvalues of Hessian matrices Eil v.), Vog E Vinan of the original model Ó. Let d'min 2 0 denote the smallest eigenvalue of all eigenvalues of Hessian matrices V2
E(zz, Yt), Yog E Virain of the retrained model Ô(-eis) with eij removed from graph G. Use L denote the set {u z' + 2) containing affected nodes from the edge removal, and Err( Err(- = (-ex)) - (I(-ess)ll) 2|2. Recall is the l2 regularization strength, we have upper bound the estimated error of model parameters' change:
0(-e)))
N3C
Err( Err(-ee)) S (NA+ (N- ml.))mmm + o'min |1//3
Σ (V (V6(211011) (gl(()))))
vy
N
+ NX (N Ll)a + min Omin: o' [
(Vgl(z), vn) Vel(z, v1)1l.
1ELL
Proof. In this proof, we utilize one-step Newton approximation as an intermediary estimate the error bound of the change in model parameters, ie.,
Err(-og) (-esg) I I' (~ee)) + [IN I( I(-et)].
(17)
14

---

Published as a conference paper at ICLR 2023
where I (-er))=A0,=00-- I I is the one-step Newton approximation with the model parameter dx AdN.. According to Boyd al. (2004) (Section 9.5.1), AθN can be calculated as follows:
AdN=
(Hg + AT)
8 (Zi, Ui) + Vgl(zi.
N
WEL
(18)
Vol(zz, 31 + 2110112).
In the following, will calculate the bound of of - (- and (-ee)) I(-ey) as two separate steps and combine them together. Here we define the before and after objective functions with the removal of edge Cij as follows:
X
Lo(0) = Σ E(z,, Ui) + 11012.
2
(19)
(0) = Σ E(z,, Ui) + Σ
E(zi, 91)
Σ
E(zi, 31) + 101
1EL
JELL
Step I: Bound of (-eet) - IN
Due to that SGC model is convex on I, we take the second derivative of (0) and have
1 N N
XI + Σ (Z + Σ (V((
V 0.
(20)
WEL
VELL
To simplify the above equation, we define J'min and d' maz are the smallest and largest eignenvalues of 4 (z(, m)) and Jmin and mmax are the smallest and largest eignenvalues of V L (zi, wr). Then we have
(.(A+
(N (N [L]) IL)) minn [L]
o'mn
(21)
N
Therefore, the SGC loss function corresponds to the removal of edge is strictly convex with the +| ). By this convexity property and the implications of strong 2004) (Section 9.1.2), we can bound I" (-ee)) I>"(-ei)) with the first derivative of SGC loss function as follows:
parameter x (N- (N-) +|
convexity Boyd et al.
I (-ei)) I (N
=1 - Ad = 11 + +0) - (AÂNE - + 0)1l2 = 110- - -deellz
N
2N
ONE E(z,, 3:) + Σ V
Orx f(z), v1)
(22)
NX+ (N-
min + 1L10 min
N
WEL
Σ
Von. ((zi, v1
All
A110xell2)
mEL
we take a close look at the second term in the above equation, we notice is equal the first derivative of La (f), i.e.,
Vola(O V Ow (Zzk Mke)
Von. Elz), v1)
Σ
O ((21)))) + x1(@Nelle). (23)
HEL
Therefore, we focus on bounding
(VV.L. in the following.
VoL. = (6 Ad
Voo Aθ veC.(0) + (o)a(0)12
(24)
=oVo AQNx) - VeC, v.C,(0)A.
15

---

Published as a conference paper at ICLR 2023
The above last equation holds due to the definition of AdNT in Eq. 18
For any continuous function and any inputs and there exists f(a (())
(f' bt) dt. Based on that, we can rewrite (0 as follows:
(Voea(0 Vea AdN)) VoL.(0) (1
=|1 /. (V A .)) (0C,(0)
(25)
We assume the loss function & on is twice differentiable and the second derivative of the loss func- tion is Lipschitz continuous 0, with parameter C. Here C is controlled by the third derivative (Curvature) the loss function L. Thus, we have
())(()) V2e(02)l22 s C. .101 - 02ll2.
(26)
Then we take Eq.
26 into Eq. and have
dett| V (lNe)ll2
NC ( ldill2 A VV (0) voCo (V.
NC
< <INCAÓNI
(27)
NC
N²
Σ V ge (z/, 91) V (z, w)
2
(NA+ - 4I) Omin + |1| m'mnn
IEL
The above last inequation holds according to the bound of VaLa -1 and Eq.
Combining Eq.
22
23 and 27p. finish the bound of I
(-eig) ( I IN (-eu)) follows:
I (-eas) No el
NºC
(28)
VV VFgl(z/.u - V (2) v1)
(NA + (N - [L])0min tm 11)3
We finish Step I.
Step II: Bound of N (INN((((E)) (-ets) - -I(--I(- I(-ei)).
By the definition of of and I( I(-e;s)), we have:
I (-ees) I( I((-e()
n
V2 (zi, 9n) 1)
-1
AI +
V2 (Zk 8k) + Σ (2) Σ
N
WELL
EE
(29)
HE
H
3e (Zz. yk)
Σ
(V (V (2), 31) v Ve (2(2)131))
LEEL
For simplification, matrix A, B and C for the following substitutions:
A = AI
1
(Zz, vk)
Σ
(21, 91
N
WEL
(30)
1
B
Σ
(z), vn and C=
Vge v1),
N 1z
N
191
where A, B and C are positive definite matrix and have the following properties:
+ (N
LI)omaz
X+ (N
1L))
N
N
(31)
|
[ Oaa
[Loomin
and
> y
N
N
N
N
16

---

Published as a conference paper at ICLR 2023
Therefore, have
V Vol (z/, - V (z). }. (32)
I ((((-e-)-((-ee ((A ((A+B) -
(A+ (A+C)
Σ
LEEL
where (A + B) (A+CC-1 NX+ [4])amin [ mine mmin)
The la norm of the error between our predicted influence and Newton approximation can be bounded as follows:
I (-ei)) - I(-ei))ll2
N
Σ 1E
(Veg
(2) v1)
Vég (1))222)
(33)
NA (N (N-lol) min(o min: mmin
We finish Step II.
Combining the conclusion in Step and II in Eq. influence and our predicted influence
28 and
33
we have the error between the actual
Err(-
(1 - (-ee-)) + ( -I(-e)))
N3C
Il Σ
v be (z/, 31) 31) - va (z), v2)
=NN (N - -L()omiin min + ILlo min)
(34)
WEL
N
Σ EE
Vgl (2) (1))l.2
NA (N Li)a min(o min mmin)
We finish the whole proof.
Corollary A.1. Let Omin denote the smallest eigenvalue of all eigenvalues of Hessian matrices Vie Mi), Vuz E Viaai of the original model Ó. Let d denote the smallest eigenvalue of all eigenvalues of Hessian matrices V2 (((-v)) 0(-o,)((z
(l(zz, ye), Vu, Vinain of the retrained model 0(- with removed from graph G. Use S denote the set {u z' + 2) containing affected nodes from the have the following upper bound on the
node removal, and Err(-v;) = [I''(-;)) -
estimated error of model parameters' change:
N
(N 1)m
Err(-o:) 5 ((N -(N-1)A+ 1)A+ (N mS)) + t'in
NA + (N - [ + min min o'in SS]
N
N
+ (NA+ (N- 1)0min)3 [1e 112 NX + Nomin
11e (1)
(35)
where m = 1 V Vgllz's Us) Vol(z,,v.)) V d v:ll2.
Proof. We provide a simple proof for the enror bound removing complete nodes. Notice that this error can be decomposed into two parts, 1, the error removing single node embedding z; and 2, the error of adding z and removing Za, where sES. where we have
Err(-o:) S Σ Err(za + 2 + Err(-2;)
SES
proofs the error bound of Err(-u;), in the proving process we decom- pose the problem in to deriving the error bound by adding z and removing zi where IeL, where L is the set of changed node embedding caused by removing a edge from the graph. Following the same proving setting of Eq. Theorem 4.1 Again, notice that S the set of changed node embedding caused by removing a node from the graph. We simply substitute L by S, we have the error bounds for E.es Err(z, > 22).
Notice that Eq. Theorem 4.1
4.
N
Σ Frr(zz + +2,) NA + (N- (5)) + o' S))3
SES
(N 1)m
N (N - m min Tminn o' d' )
17

---

Published as a conference paper at ICLR 2023
Where E Lv.es For Err(-z;), it can be derived following the same proving process as Eq. Theorem 4.1 but only remove one data points. In this case we have:
Vol(zs,Bel) y2)1
N
N NA + Nomin
Err(-2)) S (NA+ + (N min)
(16.
[|4, Ui) 1l2.
Combining the two error bounds we have:
N²C
(N 1)m
Brr(-o;) 2 ((N 1)X + (N
+
( + dmin 11)3
NA + (N [S] (8)) + min( m'nnn )
N
+ (NA+ (N 1) 11e (24, v.) 112 +
||E (z), 14) l2
NA Nomin
(36)
B DATASET STATISTICS
We present the data statistic on experiments below. We choose only small and medium-sized data. Because, each time we validate the influence of the elements in graph, we need to retrain the model.
Table 4: Dataset Statistics
Dataset
# Node
Edge
# Class
Feature
Train/Val/Test
Cora
2,708
5,429
7
1,433
140 / 500 1,000
Citeseer
3,327
4,732
6
3,703
120 / 500 1,000
Pubmed
19,717
44.338
500
60 / 500 1,000
WikiCS
11,701
216,123
10
300
250/ 1769 /5847
Amazon Computer
13,752
245,861
767
200 300 / Rest
Amazon Photo
7,650
119,081
8
745
160 / 240 / Rest
C VALIDATING INFLUENCE OF ELEMENTS: EXTRA DATASETS
For the Wiki- CS dataset, we randomly select one of the train/val/test split as described in Mernyei & Cangea (2020) to explore the effect of training nodes/edges influence. For the Amazon Computers and Amazon Photo dataset, we follow the implementation of [Shchur al. (2018). To set random splits, On each dataset, we use 20 * nodes as training set, rest nodes as testing set, where C is the number of classes.. Because for validating every edge's ' influence, we need to retrain the model and compare the change on loss, the computation cost is exceptionally high. We randomly choose 10000 edges of each datasets and validate their influence. We observe that even for medium-size datasets, our estimated influence of high correlation to the actual influence.
nodes as validating set and the
D EMPIRICAL VERIFICATION OF THEOREM 4.1
As the value of la regularization term decreases, the accuracy of our estimation of the influence of edges drops, and the Spearman correlation coefficient decrease correspondingly. This trend is consistent with the interpretations of the error bound on Theorem 4.1 that the estimation error of an influence function is inversely related with the la regularization term. We also notice that the edges that connects high-degree nodes have overall less influence. Their estimation points lies relatively close to the y=v line and thus could have relative small estimation
18

---

Published as a conference paper at ICLR 2023
WikiCS
AmazonComputee
AmazonPhoto
10
p= 0.033
0=0.873
0.868
Pred. Feat. Inft.
Pred. Feat. Infl.
Pred. Feat. Infl.
0
-10
-5
-5
-20
-10
-20
-10
0
10
20
-10
-5
0
5
10
-6
-3
3
6
Act. Feat.
Infl.
Act. Feat.
Infl.
Act. Feat. Infl.
00877
p=0.892
p= 0.978
Pred. Edge Infi.
Pred. Edge Infl.
Pred. Edge Infl.
0.5
0.5
-1.0
-1.0
-1.0
-0.5
0.0
0.5
1.0
-0.5
0.5
1.0
Act. Edge Infi.
Act. Edge Infl.
Edge
0=0.92
p=0.888
0=0.906
Pred. Node Infl.
Pred. Node Infl.
Pred. Node Infl.
3
0
-3
-6
-6
-6
-6
-3
0
-6
-3
0
3
-6
-3
3
6
Act. Node Infi.
Act. Node Infl.
Act. Node Infl.
Figure 4: Estimated influence vs. actual influence on medium-sized graphs. Three datasets are used in this illustration Wiki-CS (left column), Amazon Computers (middle column) and Amazon Photo (right column). all plots, the horizontal axes indicate the actual influence on the test set, the vertical axes indicate the predicted influence, and indicates Spearman's correlation coefficient between our predictions and the actual influences. Top row: Influence of node embeddings. Middle row: Influence of edge removals. Each point corresponds removed training edge. Bottom row: Influence of node removal. Each point represents a removed training node.
0.01
h 0.003
0.50
3.0
Aw=0.943
Au=60885
Aw=0.847
Pred. Edge Infi.
0.25
Pred. Edge Infi.
1.5
Pred. Edge Infi.
1.5
0.00
0.0
0.25
-1.5
-1.5
-0.50
-3.0
-3.0
-0.50
-0.25 0.00
0.25
0.50
-1.5
1.5
-3.0
-1.5
0.0
3.0
Act. Edge Infl.
Act. Edge Infl.
Act. Edge Infl.
Figure 5: Spearman correlation Citeseer dataset with different l2 regularization term on validating influence of edges. The orange points denote the summations of the degrees the two nodes that an edge connects is high. The blue points denote the edges, which are the summations of the degrees of the two nodes connecting the edge.
19

---

Published as a conference paper at ICLR 2023
E
GROUP EFFECT OF REMOVING MULTIPLE EDGES
We study the group effect of influence estimation on removing multiple edges. On dataset Cora, we randomly sample k edges from the attributed graph, where k's values were chosen increasingly as 2, 10, 50, 100, 200, 350. Every time, we remove k edges simultaneously and validate their estimated influence. We observe: though with high correlation, our influence plots tend move downward as more edges are removed at the same time. In this case, our method tends to be less accurate and underestimates the influence of simultaneously removed group of edges.
Influence estimation of removing number of edges(k)
k
==10
k=
15
15
15
p=0.87
p=
0.82
p=
0.84
Pred. Embed. Inft.
Embed. Inf.
Embed. Inf.
5
5
5
0
-5
-5
-5
-10
-10
-10
-15
-15
-15
Act. Edge. Infi.
Act. Edge. Infi.
Act. Edge. Infl.
== 100
= 200
k= 350
Pred. Embed. Infl.
10
p-0.85
Pred. Embed. Infl.
10
0-0.85
10
5
Embed.
5
0
-5
-5
-5
-10
-10
-10
-15
-15
-15
-10
10
-10
10
-10
10
Act. Edge. Infi.
Act. Edge. Inf.
Act. Edge. Inf..
Figure 6: Estimating group influence Cora. The horizontal axes indicate the actual influence the validation set, and the vertical axes indicate the predicted influence. On each set, we randomly sample & edges (A=2, 10, 50, 100, 200, 350) from the graph and repeat this process 5000 times. Each time, we remove edges simultaneously and validate our influence estimation.
F VALIDATING INFLUENCE FOR ARTIFICIALLY ADDED EDGES
In this section, validate influence estimation for artificially added edges dataset Cora, Pubmed, and Citeseer. On each dataset, we randomly select 10000 unconnected node pairs, add an artificial edge between them and validate its influence estimation. Figure[]shove that the estimated influence correlates highly with the actual influence. This demonstrates that our proposed method can successfully evaluate the influence of artificially added edges.
Influence of artifically added edges Pubmed
Cora
Citeseer
Pred. Embed. Inf).
0=0.94
Pred. Embed. Infl.
0=0.957
Pred. Embed. Infl.
2
p=0.942
Dr
-2
-2
-4
-2.5
0.0
2.5
-2.5
0.0
2.5
-2.5
0.0
2.5
Act. Edge.
Act. Edge. Infl.
Act. Edge. Infl.
Figure 7: Estimated influence vs. actual influence on artificially added edges. Three datasets are used this illustration Cora, Pubmed, and Citeseer. Due to the high time complexity of evaluating the influence every pair of nodes, we randomly sample 10000 node pairs and add artificial edge.
20

---

Published as a conference paper at ICLR 2023
G STUDY OF EDGES WITH NEGATIVE INFLUENCE
Here we demonstrate the performance via cumulatively removing edges with negative influence in Figure The detailed implementation has been discussed in Section 5.3 Due to that the inaccurate influence estimation with more edges removed, we consider a maximum of 50 edges to be removed for each dataset. We observe an overall increase in model performance as we cumulatively remove edges predicted as negative influence. This again demonstrates the usefulness of our influence estimatiin on edges.
Cora: Edge sorted Infi.
Pubmed: Edge sorted Infi.
Citeseer: Edge sorted Infl.
-2
Inn.
Inf.
Inf.
-8
-4
20
40
0
20
40
20
40
0.820
0.760
0.820
0.810
0.750
Acc
0.810
0.800
AcC
0.740
0.730
0.800
0.790
0.720
0,780
20 40
20
40
20
Num. Edges removed
Num. Edges removed
Num. Edges removed
Figure 8: Study of edges with negative influence, each column corresponds to Cora, Pubmed, and Citeseer dataset. Top: the scale of edges with negative influence. Bottom: accuracy by cumula- tively removing edges with negative influence. Blue and red lines present the accuracy changes of validation and test in response to negative influence edge removal, respectively.
H EXTEND INFLUENCE METHOD TO OTHER GNN MODELS
Theoretically, our current pipeline can be extended to other nonlinear GNNs under some viola- tion of assumption. (1) According to Propositions Proposition 3.2 and Proposition 3.3 we require
the existence of the inverse the Hessian matrix, which is based on the assumption that the loss function model parameters is strietly convex. Under the context of some GNN models with non- linear activation functions, we can use the pscudo-inverse non-convex loss functions of most GNN, our proposed error bound in Theorem Theorem does not hold unless a large regularization term is applied to make the hessian matrix positive definite. From the implementation purpose, (1) From the implementation perspective, the non-linear models usually have more parameters than the linear ones, which require more space to store the Hessian matrix. Accordingly, the calculation of the inverse of the Hessian matrix might be out of memory. It needs to reformulate the gradient calculation and apply optimization methods like Conjugate gra- dient for approximation. (2) Our current pipeline is constructed based on mathematical, hands-on derived gradients adopted from Koh et al. (2019). Existing packages like PyTorcl use automatic differentiation to get the gradients on model parameters. It could be inaccurate for second-order gradients calculation. Extending the current pipeline to other GNNs may require extensive first and second-order gradient formulations. We will explore more GNN influence in the future.
the hessian matrix instead. (2) For
I RUNNING TIME COMPARISON
We present the running time comparison between calculating the edge influence via the influence- based method and retrieving the actual edge influence via retraining. We conduct our experiment on dataset Cora, Pubmed, and Citeseer. We demonstrate our method is 15-25 faster than the retrained method. Notably, for tasks like improving model performance or carrying out adversarial attacks via
21

---

Published as a conference paper at ICLR 2023
edge removal, it could save considerable amount of time in finding the edge to be removed with the lowest/largest influence.
Table 5: Running time comparisons for edge removal by second. Self-loop edges are not recorded.
Dataset
Infl. (single edge)
Infl. edges)
Retrain (single edge)
Retrain (all edges)
Cora
0.004910.0000
24.86
0.0683
370.80
Pumbed
1.000810.0000
34.58
899.62 0.0203.10.004
Citeseer
0.009711..000
45.90
0.157810.000
746.47
22


Reviews:
[{"review_id": "yjNooQZPkW", "reviewer": "Reviewer_Lyjj", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes a methodology to leverage influence functions toward estimating how GNN model parameters change under graph perturbation schemes. This is an important problem to efficiently understand the effect of graph elements on model parameters, without the need to retrain the model. Specifically, the paper considers edge and node removals as perturbation strategies, deriving theoretical bounds to characterize the changes on model parameters. Besides, it is empirically shown how to utilize such graph influence functions to (i) improve the prediction performance, and (ii) as tools to guide adversarial attacks to the GNN.", "summary_of_the_review": "Overall, the paper introduces an exciting approach to further understanding the impact of graph components on the performance of the model. Nevertheless, I still have some concerns about the practical application of the framework (restricted or not to SGC) and its relationship to previous developments (e.g., DropEdge).", "strength_and_weaknesses": "*Strengths:*\n* Leveraging influence functions to analyze the performance of a GNN constitutes an interesting theoretical framework. \n\n* The paper provides a good experimental pipeline in which the influence scores of nodes and edges are utilized in different ways (e.g., to define attacks).\n\n*Weaknesses:*\n* The formulation of the methodology is done on the Simplified Graph Convolution (SGC) model. Although the paper states that their analysis could be extended to other GNN models, this does not seem to be straightforward. \n\n* Missing possible connections to related work and theory. One of the practical applications of influence functions considered in the paper, examines how edge removals could improve classification performance. To do so, edges with negative influence are removed from the graph before training the SGC model. \n\n  First, what is the fraction of edges that are being removed, and how is the performance affected if we increase/decrease the number of deleted edges? \n\n  Second, how is this methodology related to other approaches that remove edges towards building more robust models? For instance, it has been shown that a simple random edge removal could improve performance by reducing over-smoothing (the DropEdge model). Is this something contradictory to the theoretical results presented in the paper? This point needs further clarification to understand the impact of edge influence scores.\n", "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": "uQqIWaq4HV1", "reviewer": "Reviewer_pmjX", "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 extending influence functions-- a method from statistics that approximates the change of parameters or loss functions, with respect to removing or modifying training instances -- for using them in GNNs. As typical GNNs usually involve non-linear activation functions that make derivations of formulas difficult, a simplified version of them, called SGC, is used. SGC is essentially a GNN stripped of all non-linear functions. Hence, the learnable weight matrices collapse to a single matrix that transforms a smoothed version of the adjacency matrix, A^k. For each edge and node, the authors calculate the influence of them (positive or negative) in the loss function. Based on this they propose two applications, graph rectification and graph poisoning, where their method can be useful.", "summary_of_the_review": "I think this paper as it is falls within the threshold line. From one point the application of influence functions to GCNs is interesting with first promising results. On the other hand, though, little explanation is provided to the results (besides the accuracy of the method). Moreover, there is no mention at all on the running time and comparison with other methods that collect set of edges for counterfactual graph explanation.", "strength_and_weaknesses": "Strengths:\n* The use of SGC allows the use of influence function in the context of GCNs.\n* Despite its simplicity, it seems that results with respect to graph poisoning, can be transferred\nto other architectures with non-linearities, like GCN from Kipf et al.\n* Theoretical bounds on the error of approximation are also provided.\n\nWeaknesses:\n* The use of SGC essentially transforms the problem to that of deriving the influence function of a convex optimization problem.\nHence, what is important in this context is the graph structure itself and the smoothness parameter $k$. I didn't see them being involved in a clear and intuitive way in the paper. E.g. for which types of edges their influence function is higher/lower, or is it difficult to approximate? What is the effect of the smoothness parameter $k$ in the results?  It is difficult to see how Thm 4.1 provides any intuition to this direction.\n* There is no mention of the running time (both actual and in asymptotic notation) of calculating the influence functions for each edge/node in the graph. \n* There is a line of work, e.g. a paper from [NeurIPS 2021 ->\" Robust Counterfactual Explanations on Graph Neural Networks\"] or [KDD 21->\"Counterfactual graphs from Explainable Classification of Brain Networks\"], that identify a set of edges that removing them will change the prediction. Maybe the authors could compare with those in terms of indentifying influential edges (in the extreme positive/negative range).", "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": "mQ5FyXL_Qn", "reviewer": "Reviewer_Jtg1", "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 sets out to analyze the influence of attributed graph elements on the changes of parameters in a Graph Convolutional Network under Simple Graph Convolution, without having to go through retraining. The derived influence functions are capable to estimate changes caused by the removal of nodes or edges from the graph. A theoretical analysis provides bounds on the errors of such estimation.", "summary_of_the_review": "This paper sets out to analyze the influence of attributed graph elements on the changes of parameters in a Graph Convolutional Network under Simple Graph Convolution, without having to go through retraining. The derived influence functions are capable to estimate changes caused by the removal of nodes or edges from the graph. A theoretical analysis provides bounds on the errors of such estimation.\n\nIt is not clear why the conducted analysis should be limited to removal operations.\nOther operations, such as addition, or rewiring under some invariant, may also be studied to derive a complete framework.\nPotential missing elements or predicted elements of a network are also candidate for such analysis.\nIn particular, it is not clear why the proposed concept of graph recitification should only involve removals.", "strength_and_weaknesses": "Strength:\n- Novel theoretical results.\n- Experimental verification over the retraining case.\n\nWeakness:\n- Limited to removals operations.\n- Unclear and biased concept of rectification.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OFHjrO6omh", "reviewer": "Reviewer_9bmE", "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": "The authors propose a method to quantify and estimate how various components of graph neural network models will be affected by node/edge removals in the training set. In particular, the authors derive influence functions for the Simple Graph Convolution (SGC) architecture. The authors provide rigorous theoretical results, including error bounds on the estimated change vs. the actual effect of node/edge removals. A case study on adversarial attacks on graph neural networks showcase a very relevant application of the proposed method.", "summary_of_the_review": "Please see the two sections above. Based on those sections, I believe this paper should be accepted.", "strength_and_weaknesses": "Strengths:\n- Novelty. Interpretability of graph neural network models is an open area of research, and, to the best of my knowledge, influence functions have not been explored before for this task.\n- Rigorous theoretical bounds on estimation error, and reasonable empirical results that show that theoretical bounds are relevant in practice.\n- Practical significance. The authors illustrate that their proposed method can be used against / for adversarial attacks.\n- Paper is very well-organized, and the authors stay focused on the task at hand.\n\n\nWeaknesses:\n- Gap between theory and practice. The paper focuses on SGC, presumably because it is easier to derive theoretical results for this model. SGC is not as popular as other graph architectures, such as GCN and its many variants. It is also not clear how the proposed method would work in the presence of skip connections, different normalizations, such as LayerNorm, or the myriad of enhancements that are commonly used in modern graph neural network models. As such, there is a gap between the methods proposed in the paper and application. However, this is to be expected of a first exploration of influence functions for GNNs.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster