# Characterizing the Influence of Graph Elements

Zizhang Chen, Peizhao Li, Hongfu Liu and Pengyu Hong
Brandeis University
<EMAIL_ADDRESS>

###### Abstract

Influence function, a 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 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 in 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 an 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 guide the adversarial attacks on GCNs effectively.

##  1 Introduction

Graph data is pervasive in real-world applications, such as, online
recommendations (Shalaby et al., 2017; Huang et al., 2021; Li et al., 2021),
drug discovery (Takigawa and Mamitsuka, 2013; Li et al., 2017), and knowledge
management (Rizun, 2019; Wang et al., 2018), to name a 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 et al., 2005;
Li et al., 2016; Hamilton et al., 2017; Xu et al., 2019a; Jiang et al., 2019).
Graph Convolutional Networks (GCNs) (Kipf and Welling, 2017; Zhang and Chen,
2018; Fan et al., 2019), the most cited GNN architecture, adopts convolution
and message passing mechanisms.

To better understand GCNs from a 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 for learning is perturbed by edge- or node-removals?

This question proposes to estimate counterfactual effects on the parameters of
a well-trained model when there is a manipulation in the basic elements in a
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 or nodes in a graph to control the change of model parameters
of trained GCNs. The solution would provide extensions like increasing model
performance, improving model generalization, and graph data poison attacks
through pure data modeling. Yet, current methods for training GCNs offer
limited interpretability of the interactions between the training graph and
the GCN model. More specifically, we fall short of understanding the influence
of the input graph elements on both the changes in model parameters and the
generalizability of a trained model (Ying et al., 2019; Huang et al., 2022;
Yuan et al., 2021; Xu et al., 2019b; Zheng et al., 2021).

In the regime of robust statistics, an analyzing tool called influence
functions (Hampel, 1974; Koh and Liang, 2017) is proposed to study the
counterfactual effect between training data and model performance. For
independent and identically distributed (i.i.d.) data, influence functions
estimate the model’s change when there is an infinitesimal perturbation added
to the training distribution, e.g., a reweighing on some training instances.
However, unlike i.i.d. data, manipulation 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 to pass through this edge and consequentially change
node representations and affect the final model optimization. Therefore,
introducing influence functions to graph data and GCNs is non-trivial work and
requires extra considerations.

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 a surrogate
SGC.

##  2 Preliminaries

In the following sections, we use a lowercase $x$ for a scalar or an entity,
an uppercase $X$ for a constant or a set, a bolder lowercase $\mathbf{x}$ for
a vector, and a bolder uppercase $\mathbf{X}$ for a matrix.

#### Influence Functions

Influence functions (Hampel, 1974) estimate the change in model parameters
when the empirical weight distribution of i.i.d. training samples is perturbed
infinitesimally. Such estimations are computationally efficient compared to
learn-one-out retraining iterating every training sample. For $N$ training
instances $\mathbf{x}$ and label $y$, consider empirical risk minimization
(ERM)
$\hat{\theta}=\operatorname*{arg\,min}_{\theta\in\Theta}\frac{1}{N}\sum_{\mathbf{x},y}\ell(\mathbf{x},y)+\frac{\lambda}{2}\|\theta\|_{2}^{2}$
for some loss function $\ell(\cdot,\cdot)$ through a parameterized model
$\theta$ and with a regularization term. When down weighing a training sample
$(\mathbf{x}_{i},y_{i})$ by an infinitely small fraction $\epsilon$, the
substitutional ERM can be expressed as
$\hat{\theta}(\mathbf{x}_{i};-\epsilon)=\operatorname*{arg\,min}_{\theta\in\Theta}\frac{1}{N}\sum_{\mathbf{x},y}\ell(\mathbf{x},y)-\epsilon\ell(\mathbf{x}_{i},y_{i})+\frac{\lambda}{2}\|\theta\|_{2}^{2}$.
Influence functions estimate the actual change
$\mathcal{I}^{*}(\mathbf{x}_{i};-\epsilon)=\hat{\theta}(\mathbf{x}_{i};-\epsilon)-\hat{\theta}$
for a strictly convex and twice differentiable $\ell(\cdot,\cdot)$:

$\mathcal{I}(\mathbf{x}_{i};-\epsilon)=\lim_{\epsilon\to
0}\hat{\theta}(\mathbf{x}_{i};-\epsilon)-\hat{\theta}=-\mathbf{H}_{\hat{\theta}}^{-1}\nabla_{\hat{\theta}}\ell(\mathbf{x}_{i},y_{i}),$
(1)

where
$\mathbf{H}_{\hat{\theta}}\vcentcolon=\frac{1}{N}\sum_{i=1}^{N}\nabla_{\hat{\theta}}^{2}\ell(\mathbf{x}_{i},y_{i})+\lambda\mathbf{I}$
is the Hessian matrix with regularization at parameter $\hat{\theta}$. For
some differentiable model evaluation function $f:\Theta\rightarrow\mathbf{R}$
like calculating total model loss over a test set, the change from down
weighing $\epsilon\rightarrow(\mathbf{x}_{i},y_{i})$ to the evaluative results
can be approximated by
$\nabla_{\hat{\theta}}f({\hat{\theta}})\mathbf{H}_{\hat{\theta}}^{-1}\nabla_{\hat{\theta}}\ell(\mathbf{x}_{i},y_{i})$.
When $N$ the size of the training data is large, by setting
$\epsilon=\frac{1}{N}$, we can approximate the change of $\hat{\theta}$
incurred by removing an entire training sample
$\mathcal{I}(\mathbf{x}_{i};-\frac{1}{N})=\mathcal{I}(-\mathbf{x}_{i})$ via
linear extrapolations $\frac{1}{N}\rightarrow 0$. Obviously, in terms of the
estimated influence $\mathcal{I}$, removing a training sample has the opposite
value of adding the same training sample
$\mathcal{I}(-\mathbf{x}_{i})=-\mathcal{I}(+\mathbf{x}_{i})$. In our work, we
shall assume an additivity of influence functions in computations when several
samples are removed, e.g., when removing two samples:
$\mathcal{I}(-\mathbf{x}_{i},-\mathbf{x}_{j})=\mathcal{I}(-\mathbf{x}_{i})+\mathcal{I}(-\mathbf{x}_{j})$.

Though efficient, as a drawback, influence functions on non-convex models
suffer from estimation errors due to the variant local minima and usually a
computational approximation to $\mathbf{H}_{\hat{\theta}}^{-1}$ 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.

#### Simple Graph Convolution

By removing non-linear activations between layers from typical Graph
Convolutional Networks, Simple Graph Convolution (SGC) (Wu et al., 2019)
formulates a linear simplification of GCNs with competitive performance on
various tasks (He et al., 2020; Rakhimberdina and Murata, 2019). Let $G=(V,E)$
denote an undirected attributed graph, where $V=\\{v\\}$ contains vertices
with corresponding feature $\mathbf{X}\in\mathbf{R}^{|V|\times D}$ with $D$
the feature dimension, and $E=\\{e_{ij}\\}_{1\leq i<j\leq|V|}$ is the set of
edges. Let $\Gamma_{v}$ denote the set of neighborhood nodes around $v$, and
$d_{v}$ the node degrees of $v$. We use $\mathbf{A}$ denote the adjacency
matrix where $\mathbf{A}_{ij}=\mathbf{A}_{ji}=1$ if $e_{ij}\in E$, and 0
elsewhere. $\mathbf{D}=\text{diag}(d_{v})$ denotes the degree matrix. When the
context is clear, we simplify the notation
$\Gamma_{v_{i}}\rightarrow\Gamma_{i}$, and the same manner for other symbols.
For multi-layer GNNs, let $\mathbf{z}_{v}^{(k)}$ denote the hidden
representation of node $v$ in the $k$-th layer, and with
$\mathbf{z}_{v}^{(0)}=\mathbf{x}_{v}$ the initial node features. Simple Graph
Convolution processes node representations as:
$\mathbf{z}_{v}^{(k)}=\mathbf{W}^{(k)}\left(\sum_{u\in{\Gamma_{v}\cup\\{v\\}}}d_{u}^{-1/2}d_{v}^{-1/2}\mathbf{z}_{u}^{(k-1)}\right)+\mathbf{b}^{(k)}$,
where $\mathbf{W}^{(k)}$ and $\mathbf{b}^{(k)}$ are trainable parameters in
$k$-th layer. In transductive node classification, let
$V_{\text{train}}\subset V$ denote the set of $N$ training nodes associated
with labels $y$. ERM of SGC in this task is
$\hat{\theta}=\operatorname*{arg\,min}_{\theta\in\Theta}\frac{1}{N}\sum_{v\in
V_{\text{train}}}\ell(\mathbf{z}_{v}^{(k)},y_{v})+\frac{\lambda}{2}\|\theta\|_{2}^{2}$.
Due to the linearity of SGC, parameters $\mathbf{W}^{(k)}$ and
$\mathbf{b}^{(k)}$ in each layer can be unified, and predictions after $k$
layers can be simplified as
$\mathbf{y}=\operatorname*{arg\,max}(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}})^{k}\mathbf{X}\mathbf{W}+\mathbf{b}$
with $\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$ and $\tilde{\mathbf{D}}$ the
degree matrix of $\tilde{\mathbf{A}}$. Therefore, for node representations
$\mathbf{Z}^{(k)}=(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}})^{k}\mathbf{X}$
with $\mathbf{y}$ and cross-entropy loss, $\ell(\cdot,\cdot)$ is convex. The
parameters $\theta$ in $\ell$ consist of matrix
$\mathbf{W}\in\mathbf{R}^{D\times|\text{Class}|}$ and vector
$\mathbf{b}\in\mathbf{R}^{|\text{Class}|}$ with $|\text{Class}|$ the number of
class, and can be solved via logistic regression.

#### Additional Notations

In what follows, we shall build our influence analysis upon SGC. For
notational simplification, we omit $(k)$ in $\mathbf{Z}^{(k)}$ and use
$\mathbf{Z}$ to denote the last-layer node representations from SGC. We use
$\mathcal{I}^{*}(-e_{ij})=\hat{\theta}(-e_{ij})-\hat{\theta}$ to denote the
actual model parameters’ change where $\hat{\theta}(-e_{ij})$ is obtained
through ERM when $e_{ij}$ is removed from $E$. Likewise,
$\mathcal{I}^{*}(-v_{i})$ denotes the change from $v_{i}$’s removal from graph
$G$. $\mathcal{I}(-e_{ij})$ and $\mathcal{I}(-v_{i})$ are the corresponding
estimated influence for $\mathcal{I}^{*}(-e_{ij})$ and
$\mathcal{I}^{*}(-v_{i})$ 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 a 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 representational changes in $\mathbf{Z}$. When $e_{ij}$ 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 $\mathbf{A}$, the degree of all adjacent edges
$e_{jk},\forall k\in\Gamma_{i}$ and $e_{ik},\forall k\in\Gamma_{j}$ will be
changed, and these edges will have a larger value in
$\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}}$.
We have the following expression to describe the representational changes
$\Delta(-e_{ij})$ of node representations $\mathbf{Z}$ in SGC incurred by
removing $e_{ij}$.

$\Delta(-e_{ij})=[(\tilde{\mathbf{D}}(-e_{ij})^{-\frac{1}{2}}\tilde{\mathbf{A}}(-e_{ij})\tilde{\mathbf{D}}(-e_{ij})^{-\frac{1}{2}})^{k}-(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}})^{k}]\mathbf{X}.$
(2)

$\mathbf{A}(-e_{ij})$ is the modified adjacency matrix with
$\mathbf{A}(-e_{ij})_{ij/ji}=0$ and $\mathbf{A}(-e_{ij})=\mathbf{A}$
elsewhere. $\tilde{\mathbf{A}}(-e_{ij})=\mathbf{A}(-e_{ij})+\mathbf{I}$ and
$\tilde{\mathbf{D}}(-e_{ij})$ the degree matrix of
$\tilde{\mathbf{A}}(-e_{ij})$. We can access the change in every node by
having $\Delta(-e_{ij})$. Let $\delta_{k}(-e_{ij})$ denotes the $k$-th row in
$\Delta(-e_{ij})$. $\delta_{k}=0$ implies no change in $k$-th node from
removing $e_{ij}$, and $\delta_{k}\neq 0$ indicates a change in
$\mathbf{z}_{k}$.

We proceed to use influence functions to characterize the counterfactual
effect of removing $e_{ij}$. Our high-level idea is, from an influence
functions perspective, representational changes in nodes
$\mathbf{z}\rightarrow\mathbf{z}+\delta$ is equivalent to removing training
instances with feature $\mathbf{z}$, and adding new training instances with
feature $\mathbf{z}+\delta$ and with the same labels. The problem thus turns
back to an instance reweighing problem developed by influence functions. In
this case, we have the lemma below to prove the influence functions’
linearity.

######  Lemma 3.1.

Consider empirical risk minimization
$\hat{\theta}=\operatorname*{arg\,min}_{\theta\in\Theta}\sum_{i}\ell(\mathbf{x}_{i},y_{i})$
and
$\hat{\theta}(\mathbf{x}_{j}\rightarrow\mathbf{x}_{j}+\delta)=\operatorname*{arg\,min}_{\theta\in\Theta}\sum_{i\neq
j}\ell(\mathbf{x}_{i},y_{i})+\ell(\mathbf{x}_{j}+\delta,y_{j})$ with some
twice-differentiable and strictly convex $\ell$, let
$\mathcal{I}^{*}(\mathbf{x}_{j}\rightarrow\mathbf{x}_{j}+\delta)=\hat{\theta}(\mathbf{x}_{j}\rightarrow\mathbf{x}_{j}+\delta)-\hat{\theta}$,
the estimated influence satisfies linearity:

$\displaystyle\mathcal{I}(\mathbf{x}_{j}\rightarrow\mathbf{x}_{j}+\delta)=\mathcal{I}(-\mathbf{x}_{j})+\mathcal{I}(+(\mathbf{x}_{j}+\delta)).$
(3)

By having Lemma 3.1, we are ready to derive a proposition from characterizing
edge removal.

######  Proposition 3.2.

Let $\mathbf{\delta}_{k}$($-e_{ij}$) denote the $k$-th row of
$\Delta(-e_{ij})$. The influence of removing an edge $e_{ij}\in E$ from graph
$G$ can be estimated by:

$\displaystyle\mathcal{I}(-e_{ij})$
$\displaystyle=\mathcal{I}(\mathbf{z}\rightarrow\mathbf{z}+\delta(-e_{ij}))=\sum_{k}\mathcal{I}(+(\mathbf{z}_{k}+\delta_{k}(-e_{ij})))+\mathcal{I}(-\mathbf{z}_{k})$
(4) $\displaystyle=-\mathbf{H}_{\hat{\theta}}^{-1}\sum_{v_{k}\in
V_{\text{train}}}(\nabla_{\hat{\theta}}\ell(\mathbf{z}_{k}+\delta_{k}(-e_{ij}),y_{k})-\nabla_{\hat{\theta}}\ell(\mathbf{z}_{k},y_{k})).$

###### Proof.

The second equality comes from Lemma 3.1, and the third equality comes from
Equation 1. Realize that removing two representations
$\mathcal{I}(-z_{i},-z_{j})=\mathcal{I}(-z_{i})+\mathcal{I}(-z_{j})$
completing the proof. ∎

Proposition 3.2 offer an approach to calculate the estimated influence of
removing $e_{ij}$. In practice, having the inverse hessian matrix, a removal
only requires users to compute the updated gradients
$\nabla_{\hat{\theta}}\ell(\mathbf{z}_{k}+\delta_{k}(-e_{ij}),y_{k})$ and its
original gradients for all affected nodes in ($k$+1)-hop neighbors.

###  3.2 Influence of Node Removal

We address the case of node removal. The impact from removing a node $v_{i}$
from graph $G$ to parameters’ change are two-folds: (1) The loss term
$\ell(\mathbf{x}_{i},y_{i})$ will no longer involved in ERM if $v_{i}\in
V_{\text{train}}$. (2) All edges link to this node $\\{e_{ij}\\},\forall
j\in\Gamma_{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 can be an incremental extension from edge removal in Proposition 3.2.

The representational changes from removing node $v_{i}$ can be expressed as:

$\Delta(-v_{i})=[(\tilde{\mathbf{D}}(-v_{i})^{-\frac{1}{2}}\tilde{\mathbf{A}}(-v_{i})\tilde{\mathbf{D}}(-v_{i})^{-\frac{1}{2}})^{k}-(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}})^{k}]\mathbf{X},$
(5)

with $\mathbf{A}(-v_{i})_{jk/kj}=\mathbf{A}_{jk/kj},\forall j,k:j\neq i\wedge
k\notin\Gamma_{i}$, and $\mathbf{A}(-v_{i})=0$ elsewhere. Similarly,
$\tilde{\mathbf{A}}(-v_{i})=\mathbf{A}(-v_{i})+\mathbf{I}$ and
$\tilde{\mathbf{D}}(-v_{i})$ is the corresponding degree matrix of
$\tilde{\mathbf{A}}(-v_{i})$. Having $\Delta(-v_{i})$, Lemma 3.1 and
Proposition 3.2, we state the estimated influence of removing $v_{i}$.

######  Proposition 3.3.

Let $\delta_{j}(-v_{i})$ denote the $j$-th row of $\Delta(-v_{i})$. The
influence of removing node $v_{i}$ from graph $G$ can be estimated by:

$\displaystyle\mathcal{I}(-v_{i})$
$\displaystyle=\mathcal{I}(-\mathbf{z}_{i})+\mathcal{I}(\mathbf{z}\rightarrow\mathbf{z}+\delta(-v_{i}))=\mathcal{I}(-\mathbf{z}_{i})+\sum_{j}\mathcal{I}(+(\mathbf{z}_{j}+\delta_{j}(-v_{i})))+\mathcal{I}(-\mathbf{z}_{j})$
(6) $\displaystyle=-\mathds{1}_{v_{i}\in
V_{\text{train}}}\cdot\mathbf{H}_{\hat{\theta}}^{-1}\nabla_{\hat{\theta}}\ell\left(\mathbf{z}_{i},y_{i}\right)-\mathbf{H}_{\hat{\theta}}^{-1}\sum_{v_{j}\in
V_{\text{train}}}(\nabla_{\hat{\theta}}\ell(\mathbf{z}_{j}+\delta_{j}(-v_{i}),y_{j})-\nabla_{\hat{\theta}}\ell(\mathbf{z}_{j},y_{j})),$

where $\mathds{1}$ is an indicator function.

###### Proof.

Combining Lemma 3.1 and Equation 1 completes the proof. ∎

##  4 Theoretical Error Bounds

In the above section, we show how to estimate the changes of model parameters
due to edge removal: $\hat{\theta}\rightarrow\hat{\theta}(-e_{ij})$ and node
removals: $\hat{\theta}\rightarrow\hat{\theta}(-v_{i})$. In this section, we
study the error between the estimated influence given by influence functions
$\mathcal{I}$ and the actual influence $\mathcal{I}^{*}$ obtained by model
retraining. We give upper error bounds on edge removal
$\|\mathcal{I}^{*}(-e_{ij})-\mathcal{I}(-e_{ij})\|_{2}$ (see Theorem 4.1) and
node removal $\|\mathcal{I}^{*}(-v_{i})-\mathcal{I}(-v_{i})\|_{2}$ (see
Corollary A.1).

In what follows, we shall assume the second derivative of $\ell(\cdot,\cdot)$
is Lipschitz continuous at $\theta$ with constant $C$ based on the convergence
theory of Newton’s method. To simplify the notations, we use
$\mathbf{z}_{i}^{\prime}=\mathbf{z}_{i}+\delta_{i}$ to denote the new
representation of $v_{i}$ obtained after removing an edge or a node, where
$\delta_{i}$ is the row vector of $\Delta(-e_{ij})$ or $\Delta(-v_{i})$
depending on the context.

######  Theorem 4.1.

Let $\sigma_{\text{min}}\geq 0$ denote the smallest eigenvalue of all
eigenvalues of Hessian matrices
$\nabla_{\hat{\theta}}^{2}\ell(\mathbf{z}_{i},y_{i}),\forall v_{i}\in
V_{\text{train}}$ of the original model $\hat{\theta}$. Let
$\sigma_{\text{min}}^{\prime}\geq 0$ denote the smallest eigenvalue of all
eigenvalues of Hessian matrices
$\nabla_{{\hat{\theta}}(-e_{ij})}^{2}\ell(\mathbf{z}_{i},y_{i}),\forall
v_{i}\in V_{\text{train}}$ of the retrained model $\hat{\theta}(-e_{ij})$ with
$e_{ij}$ removed from graph $G$. Use $L$ denote the set
$\\{v:\mathbf{z}^{\prime}\neq\mathbf{z}\\}$ containing affected nodes from the
edge removal, and
$\text{Err}(-e_{ij})=\|\mathcal{I}^{*}(-e_{ij})-\mathcal{I}(-e_{ij})\|_{2}$.
Recall $\lambda$ is the $\ell_{2}$ regularization strength; we have an upper
bound on the estimated error of model parameters’ change:

$\displaystyle\text{Err}(-e_{ij})\leq$
$\displaystyle\frac{N^{3}C}{(N\lambda+(N-|L|)\sigma_{\text{min}}+\sigma_{\text{min}}^{\prime}|L|)^{3}}\cdot\|\sum_{v_{l}\in
L}(\nabla_{\hat{\theta}}\ell(\mathbf{z}^{\prime}_{l},y_{l})-\nabla_{\hat{\theta}}\ell(\mathbf{z}_{l},y_{l}))\|^{2}_{2}$
(7)
$\displaystyle+\frac{N}{N\lambda+(N-|L|)\sigma_{\text{min}}+\min(\sigma_{\text{min}},\sigma_{\text{min}}^{\prime})|L|}\cdot\|\sum_{v_{l}\in
L}(\nabla_{\hat{\theta}}\ell(\mathbf{z}^{\prime}_{l},y_{l})-\nabla_{\hat{\theta}}\ell(\mathbf{z}_{l},y_{l}))\|_{2}.$

###### 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 $\mathcal{I}^{*}(-e_{ij})$ and its Newton approximation, and the second
term is the difference between the Newton approximation and the estimated
influence $\mathcal{I}(-e_{ij})$. Combining these two parts result in the
bound. ∎

######  Remark 4.2.

We have the following main observations from Theorem 4.1. (1) The estimation
error of influence function is controlled by the $\ell_{2}$ regularization
strength within a factor of $\mathcal{O}(1/\lambda)$. A stronger
regularization will likely produce a better approximation. (2) The error is
controlled by the inherent property of a 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
$\mathbf{z}\rightarrow\mathbf{z}^{\prime}$. Intuitively, if removing $e_{ij}$
incurs smaller changes in node representations, the approximation of the
actual influence would be more accurate. Also, a smaller $\text{Err}(-v_{i})$
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 a special case, if
$\sigma_{\text{min}}=\sigma_{\text{min}}^{\prime}=0$, the bound is irrelevant
to $N$. We attach empirical verification for our bound in Figure 5.

Similar to Theorem 4.1, we have Corollary A.1 to derive an upper bound on
$\|\mathcal{I}^{*}(-v_{i})-\mathcal{I}(-v_{i})\|_{2}$ for removing a node
$v_{i}$ from graph.

##  5 Experiments

We conducted three major experiments: (1) Validate the estimation accuracy of
our influence functions on graph in Section 5.2; (2) Utilize the estimated
edge influence to increase model performance and carry out adversarial attacks
in Section 5.4; and (3) Utilize the estimated node influence to carry out
adversarial attacks on GCN (Kipf and Welling, 2017) in Section 5.5.

###  5.1 Setup

We choose six real-world graph datasets:Cora, PubMed, CiteSeer (Sen et al.,
2008), WiKi-CS (Mernyei and Cangea, 2020), Amazon Computers, and Amazon Photos
(Shchur et al., 2018) in our experiments. Statistics of these datasets are
outlined in Section 5.1 Table 1. For the Cora, PubMed, and CiteSeer datasets,
we used their public train/val/test splits. For the Wiki-CS datasets, we took
a random single train/val/test split provided by Mernyei and 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.

Table 1: 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 | 3 | 500 | 60 / 500 / 1,000
WikiCS | 11,701 | 216,123 | 10 | 300 | 250/ 1769 /5847
Amazon Computer | 13,752 | 245,861 | 10 | 767 | 200 / 300 / Rest
Amazon Photo | 7,650 | 119,081 | 8 | 745 | 160 / 240 / Rest
Figure 1: 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 a node is in the training subset (large) or not (small). Middle:
Influence of the training edges. Each edge is colored accordingly to its
estimated influence value (blue \- negative influence, removing it is expected
to decrease the loss on the validation set; red – positive influence, removing
it is expected to increase the loss on the validation set; and grey – little
influence. The deeper color indicates higher influence.). Right: Influence of
the training nodes. The same color scheme in the middle plot is used here.

###  5.2 Validating Influence Functions on Graphs

#### Validating Estimated Influence

We compared the estimated influence of removing a node/edge with its
corresponding ground truth effect. The actual influence is obtained by re-
training the model after removing a 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 $\ell(\mathbf{z}_{i},y_{i})$
of node $v_{i}$ from the ERM objective while keeping the embeddings of other
nodes intact. Figure 2 shows that the estimated influence correlates highly
with the actual influence (Spearman correlation coefficients range from 0.847
to 0.981). More results are included Figure 3.

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 predicted
influence on the validation set, the vertical axes indicate the actual
influence, and $\rho$ indicates Spearman’s correlation coefficient between our
predictions and the actual influences. Top row: Influence of node embedding
removal. Each point represents a 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 a removed training node.

#### Validating Estimated Influence: medium-sized datasets

Figure 3: 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). In all plots, the
horizontal axes indicate the predicted influence on the test set, the vertical
axes indicate the actual influence, and $\rho$ 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 to a removed training edge. Bottom row: Influence of
node removal. Each point represents a removed training node.

For the Wiki-CS dataset, we randomly select one of the train/val/test split as
described in Mernyei and 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 et al. (2018). To set random splits, On
each dataset, we use $20*C$ nodes as the training set, $30*C$ nodes as
validating set, and the rest nodes as the 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 dataset and
validate their influence. We observe that our estimated influence is highly
correlated to the actual influence even for medium-size datasets.

Figure 4: Study of edges with a positive influence on both validation and test
set. Columns correspond to Cora, Pubmed and Citeseer datasets. Top: the scale
of values of the edges with negative influence. Bottom: accuracy drop by
cumulatively removing edges with positive influence.

#### Visualization

Figure 1 visualizes the estimated influence of edge and node removals on the
validation loss for the Cora dataset. This visualization hints at
opportunities for improving the test performance of a model or attacking a
model by removing nodes/edges with noticeable influences (see experiments in
Sections 5.4 and 5.5).

###  5.3 Empirical Verification of Theorem 4.1

Figure 5: Spearman correlation on Citeseer dataset with different $l_{2}$
regularization term on validating influence of edges. The orange points denote
the summations of the degrees of 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.

We choose CiteSeer to verify the error bounds for the edge influence
empirically. We estimated the edge influence and compared it to the actual
influence in different values of $l_{2}$ terms. In addition, we calculate the
degree of each edge in the attributed graph and compare the estimation error
between the top $10\%$ largest degrees of edges(colored as orange) and rest
edges(colored as blue). We have the following observations. As the value of
$l_{2}$ 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 to the $l_{2}$ regularization term. This verifies our
observations that the error bound is controlled by the $l_{2}$ term. We also
notice that the edges that connect high-degree nodes have less influence
overall. Their estimation points lie relatively close to the $y$$=$$x$ line
and thus could have a relatively small estimation error. This could be
partially explained by our interpretations on Remark 4.2. On removing edges
with high degrees, the corresponding change in node embeddings should be
relatively small. Thus, its gradients change should also be small. Therefore,
it enjoys a relatively small estimation error.

###  5.4 Applications of the Estimated Edge Influence

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.

#### Improving performance via Edge Removals

We begin by investigating the impact of edges with negative influences. Based
on our influence analysis, removing negative influence edges from the original
will decrease validation loss. Thus the classification accuracy on the test
set is expected to increase correspondingly. We sort the edges by their
estimated influences in descending order, then cumulatively remove edges
starting from the one with the lowest negative influence. We train the SGC
model, fine-tune it on the public split validation set and select 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 is displayed in Table 2, where we also report the
performance several classical and state-of-the-art GNN models on the original
whole set as references, including GCN (Kipf and Welling, 2017), GAT
(Veličković et al., 2018), FGCN (Chen et al., 2018), GIN (Xu et al., 2019a),
DGI (Velickovic et al., 2019) with a non linear activation function and SGC
(Wu et al., 2019).

Table 2: Our performance via eliminating edges with negative influence values.

Methods | Cora | Pubmed | Citeseer
---|---|---|---
GCN | 81.4 $\pm$ 0.4 | 79.0 $\pm$ 0.4 | 70.1 $\pm$ 0.5
GAT |  83.3 $\pm$ 0.7 | 78.5 $\pm$ 0.3 | 72.6 $\pm$ 0.6
FGCN | 79.8 $\pm$ 0.3 | 77.4 $\pm$ 0.3 | 68.8 $\pm$ 0.6
GIN | 77.6 $\pm$ 1.1 | 77.0 $\pm$ 1.2 | 66.1 $\pm$ 0.9
DGI | 82.5 $\pm$ 0.7 | 78.4 $\pm$ 0.7 | 71.6 $\pm$ 0.7
SGC | 81.0 $\pm$ 0.0 | 78.9 $\pm$ 0.0 | 71.9 $\pm$ 0.1
Ours | 82.0 $\pm$ 0.0 | 79.7 $\pm$ 0.0 | 74.5 $\pm$ 0.0

We demonstrate that our proposed method can marginally improve the accuracy of
SGC from the data perspective and without any change to the original model
structure of SGC, which validates 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

Table 3: Grey-box attacks to GCN via edge removals. A lower performance
indicates a more successful attack. The best attacks are in bold font. The
number following the dataset name is the pre-attack performance. ‘-’ denotes
an out-of-memory issue encountered on GPU with 24GB VRAM.

Dataset |  Cora \- 81.10% |  Citeseer \- 70.07% |  Pubmed \- 79.80%
---|---|---|---
Elimination Rate | 1% | 3% | 5% | 1% | 3% | 5% | 1% | 3% | 5%
DICE | 79.9% | 80.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%

We investigated how to use edge removals to deteriorate SGC performance. Based
on the influence analysis, removing an edge with a positive estimated
influence can increase the model loss and decrease the model performance on
the validation set. Thus, our attack is carried out in the following way. We
first calculated the estimated influence of all edges and cumulatively removed
edges with the highest positive influence one at a time. Every time we remove
a new edge, we retrain the model to obtain the current model performance. We
remove 100 edges in total for each experiment.

We present our results in Figure 4. Apparently, in general, the accuracy of
SGC on node classification drops significantly. We notice the influence of
edges is approximately power-law distributed, where only a 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 our expectations of edges with a positive estimated
influence.

#### Attacking GCN via Surrogate SGC

We further explored the impact of removing positive influences edges under
adversarial grey-box attack settings. Here, we followed Zügner and Günnemann
(2019) to interpret SGC as a surrogate model for attacking the GCN (Kipf and
Welling, 2017) as a victim model, where the assumption lays under that the
increase of loss on SGC can implicitly drop the performance of GCN. We
eliminated positive influence edges at different rates $1\%,3\%,5\%$ among all
edges. The drop in accuracy was compared against DICE (Zügner et al., 2018),
GraphPoison (Bojchevski and 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 3. 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.5 Influence of Node Removal

#### Attacking GCN via Node Removals

Table 4: Performance of node removing attack. Lower performance means better
attacks. The number after the dataset name means the performance of the GCN
model without an attack. The victim model’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%

In this section, we 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 by our 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\%$. We randomly remove the nodes from the
training sets for the Random baseline. We remove nodes by their degree in
descending order for the Degree baseline.

The model performance on 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 the $15\%$ removing ratio. These results indicate that our estimation of
node influence can be used to guide the adversarial attack on GCN in the
settings of node removal.

##  6 Related Works

#### Influence Functions

Recently, more efforts have been dedicated to investigating influence
functions (Koh et al., 2019; Giordano et al., 2019; Ting and Brochu, 2018) in
various applications, such as,computer vision (Koh and Liang, 2017), natural
language processing (Han et al., 2020), tabular data (Wang et al., 2020a),
causal inference (Alaa and Van Der Schaar, 2019), data poisoning attack (Fang
et al., 2020; Wang et al., 2020b), and algorithmic fairness (Li and Liu,
2022). In this work, we propose a major extension of influence functions to
graph-structured data and systemically study how we can estimate the influence
of nodes and edges in 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 are many other approaches to exploring the
underlying patterns in graph data and its elements. Explanation models for
graphs (Ying et al., 2019; Huang et al., 2022; Yuan et al., 2021) provide an
accessible relationship between the model’s predictions and corresponding
elements in graphs. They show how the graph’s local structure or node features
impact the decisions from GNNs. As a major difference, these approaches tackle
model inference with fixed parameters, while we focus on a 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 is usually conducted by adding
perturbations on the graphic structure or node features Zügner and Günnemann
(2019); Zheng et al. (2021). In addition, Zhang et al. (2020) introduces an
adversarial attack setting by flipping a small fraction of node labels in the
training set, causing a significant drop in model performance. A majority of
the attacker models Zügner et al. (2018); Xu et al. (2019b) on graph structure
are constructed based on the gradient information on both edges and node
features and achieve costly but effective attacking results. These attacker
models rely mainly on greedy-based methods to find the graph structure’s
optimal perturbations. We only focus on 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.

##  7 Conclusions

We have developed a novel influence analysis to understand the effects of
graph elements on the parameter changes of GCNs without needing to retrain the
GCNs. We chose Simple Graph Convolution due to its convexity and its
competitive performance to 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 validated 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 improve model
performance and carry out adversarial attacks.

## References

  * Shalaby et al. [2017] Walid Shalaby, BahaaEddin AlAila, Mohammed Korayem, Layla Pournajaf, Khalifeh AlJadda, Shannon Quinn, and Wlodek Zadrozny.  Help me find a job: A graph-based approach for job recommendation at scale.  In _2017 IEEE international conference on big data (big data)_ , pages 1544–1553. IEEE, 2017.
  * Huang et al. [2021] Chao Huang, Jiahui Chen, Lianghao Xia, Yong Xu, Peng Dai, Yanqing Chen, Liefeng Bo, Jiashu Zhao, and Jimmy Xiangji Huang.  Graph-enhanced multi-task learning of multi-level transition dynamics for session-based recommendation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2021.
  * Li et al. [2021] 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 Representations_ , 2021.  URL https://openreview.net/forum?id=xgGS6PmzNq6.
  * Takigawa and Mamitsuka [2013] Ichigaku Takigawa and Hiroshi Mamitsuka.  Graph mining: procedure, application to drug discovery and recent advances.  _Drug Discovery Today_ , 2013.
  * Li et al. [2017] Junying Li, Deng Cai, and Xiaofei He.  Learning graph-level representation for drug discovery.  _arXiv preprint arXiv:1709.03741_ , 2017.
  * Rizun [2019] Mariia Rizun.  Knowledge graph application in education: a literature review.  _Acta Universitatis Lodziensis. Folia Oeconomica_ , 2019.
  * Wang et al. [2018] 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.  In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_ , 2018.
  * Gori et al. [2005] M. Gori, G. Monfardini, and F. Scarselli.  A new model for learning in graph domains.  In _Proceedings of the IEEE International Joint Conference on Neural Networks_ , 2005.
  * Scarselli et al. [2005] F. Scarselli, S. L. Yong, M. Gori, M. Hagenbuchner, A. C. Tsoi, and M. Maggini.  Graph neural networks for ranking web pages.  In _Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence_ , 2005.
  * Li et al. [2016] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel.  Gated graph sequence neural networks.  _International Conference on Learning Representations_ , 2016.
  * Hamilton et al. [2017] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Xu et al. [2019a] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  _International Conference on Learning Representations_ , 2019a.
  * Jiang et al. [2019] Xiaolong Jiang, Peizhao Li, Yanjing Li, and Xiantong Zhen.  Graph neural based end-to-end data association framework for online multiple-object tracking.  _arXiv preprint arXiv:1907.05315_ , 2019.
  * Kipf and Welling [2017] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _International Conference on Learning Representations_ , 2017.
  * Zhang and Chen [2018] Muhan Zhang and Yixin Chen.  Link prediction based on graph neural networks.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Fan et al. [2019] 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.
  * Ying et al. [2019] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec.  Gnnexplainer: Generating explanations for graph neural networks.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Huang et al. [2022] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang.  Graphlime: Local interpretable model explanations for graph neural networks.  _IEEE Transactions on Knowledge and Data Engineering_ , 2022.
  * Yuan et al. [2021] 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.
  * Xu et al. [2019b] Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin.  Topology attack and defense for graph neural networks: An optimization perspective.  _International Joint Conferences on Artificial Intelligence Organization_ , 2019b.
  * Zheng et al. [2021] 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 learning.  _Neural Information Processing Systems Datasets and Benchmarks Track_ , 2021.
  * Hampel [1974] Frank R Hampel.  The influence curve and its role in robust estimation.  _Journal of the American Statistical Association_ , 1974.
  * Koh and Liang [2017] Pang Wei Koh and Percy Liang.  Understanding black-box predictions via influence functions.  In _International Conference on Machine Learning_ , 2017.
  * Wu et al. [2019] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying graph convolutional networks.  In _International Conference on Machine Learning_ , 2019.
  * He et al. [2020] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang.  Lightgcn: Simplifying and powering graph convolution network for recommendation.  In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2020.
  * Rakhimberdina and Murata [2019] Zarina Rakhimberdina and Tsuyoshi Murata.  Linear graph convolutional model for diagnosing brain disorders.  In _International Conference on Complex Networks and Their Applications_ , 2019.
  * Pregibon [1981] Daryl Pregibon.  Logistic regression diagnostics.  _The annals of statistics_ , 9(4):705–724, 1981\.
  * Sen et al. [2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  _AI magazine_ , 2008.
  * Mernyei and Cangea [2020] Péter Mernyei and Cătălina Cangea.  Wiki-cs: A wikipedia-based benchmark for graph neural networks.  _arXiv preprint arXiv:2007.02901_ , 2020.
  * Shchur et al. [2018] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann.  Pitfalls of graph neural network evaluation.  _Relational Representation Learning Workshop, NeurIPS 2018_ , 2018\.
  * Veličković et al. [2018] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph Attention Networks.  _International Conference on Learning Representations_ , 2018.
  * Chen et al. [2018] Jie Chen, Tengfei Ma, and Cao Xiao.  Fastgcn: fast learning with graph convolutional networks via importance sampling.  _International Conference on Learning Representations_ , 2018.
  * Velickovic et al. [2019] Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm.  Deep graph infomax.  _International Conference on Learning Representations_ , 2019.
  * Zügner and Günnemann [2019] Daniel Zügner and Stephan Günnemann.  Adversarial attacks on graph neural networks via meta learning.  In _International Conference on Learning Representations_ , 2019.
  * Zügner et al. [2018] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann.  Adversarial attacks on neural networks for graph data.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2018.
  * Bojchevski and Günnemann [2019] Aleksandar Bojchevski and Stephan Günnemann.  Adversarial attacks on node embeddings via graph poisoning.  In _International Conference on Machine Learning_ , 2019.
  * Koh et al. [2019] Pang Wei W 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.
  * Giordano et al. [2019] Ryan Giordano, William Stephenson, Runjing Liu, Michael Jordan, and Tamara Broderick.  A swiss army infinitesimal jackknife.  In _International Conference on Artificial Intelligence and Statistics_ , 2019.
  * Ting and Brochu [2018] Daniel Ting and Eric Brochu.  Optimal subsampling with influence functions.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Han et al. [2020] 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 Computational Linguistics_ , 2020.
  * Wang et al. [2020a] Zifeng Wang, Hong Zhu, Zhenhua Dong, Xiuqiang He, and Shao-Lun Huang.  Less is better: Unweighted data subsampling via influence function.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2020a.
  * Alaa and Van Der Schaar [2019] Ahmed Alaa and Mihaela Van Der Schaar.  Validating causal inference models via influence functions.  In _International Conference on Machine Learning_ , 2019.
  * Fang et al. [2020] 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.
  * Wang et al. [2020b] Binghui Wang, Tianxiang Zhou, Minhua Lin, Pan Zhou, Ang Li, Meng Pang, Cai Fu, Hai Li, and Yiran Chen.  Evasion attacks to graph neural networks via influence function.  _arXiv preprint arXiv:2009.00203_ , 2020b.
  * Li and Liu [2022] Peizhao Li and Hongfu Liu.  Achieving fairness at no utility cost via data reweighing with influence.  In _International Conference on Machine Learning_ , 2022.
  * Zhang et al. [2020] 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.
  * Boyd et al. [2004] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.

##  Appendix A Proofs

See 3.1

###### Proof.

Notice the actual model parameters in response to the perturbations $\Delta$
can be denoted as:

$\hat{\theta}(\mathbf{x}_{j}\rightarrow\mathbf{x}_{j}+\delta){\stackrel{{\scriptstyle\operatorname{def}}}{{=}}}\underset{\theta\in\Theta}{\arg\min}\frac{1}{N}\sum_{k=1}^{N}\ell\left(\mathbf{x}_{k},y_{k}\right)-\frac{1}{N}\ell\left(\mathbf{x}_{j},y_{j}\right)+\frac{1}{N}\ell\left(\mathbf{x}_{j}+\delta,y_{j}\right)$

In this case, the actual change in model parameters in response of the
perturbations can be represented as:
$\mathcal{I}(\mathbf{x}_{j}\rightarrow\mathbf{x}_{j}+\delta)$$=$$\hat{\theta}(\mathbf{x}_{j}\rightarrow\mathbf{x}_{j}+\delta)$$-$$\hat{\theta}$.
For estimating $\Delta\theta$, we start by considering the parameter change
from up weighting infinite small $\varepsilon$ on
$\\{\mathbf{x}^{\prime}_{l}\\}$ and down weight infinite small $\varepsilon$
on $\\{\mathbf{x}_{l}\\}$ where $\forall l\in L$. By definition, the model
parameter in response of perturbation $\hat{\theta}_{\varepsilon}$ can be
represented as:

$\hat{\theta}_{\varepsilon}{\stackrel{{\scriptstyle\operatorname{def}}}{{=}}}\underset{\theta\in\Theta}{\arg\min}\frac{1}{N}\sum_{k=1}^{N}\ell\left(\mathbf{x}_{k},y_{k}\right)-\varepsilon\ell\left(\mathbf{x}_{j},y_{j}\right)+\varepsilon\ell\left(\mathbf{x}_{j}+\delta,y_{j}\right)$
(8)

The change of model parameter due to the modification of the group of data’s
weight on loss be:

$\Delta\theta_{\varepsilon}=\hat{\theta}_{\varepsilon}-\hat{\theta}$ (9)

Since $\hat{\theta}_{\varepsilon}$ minimize the changed loss function under
perturbation, take the derivative:

$\displaystyle 0=$
$\displaystyle\frac{1}{N}\sum_{k=1}^{N}\nabla_{\hat{\theta}_{\varepsilon}}\ell\left(\mathbf{x}_{k},y_{k}\right)-\varepsilon\nabla_{\hat{\theta}_{\varepsilon}}\ell\left(\mathbf{x}_{j},y_{j}\right)$
(10)
$\displaystyle+\varepsilon\nabla_{\hat{\theta}_{\varepsilon}}\ell\left(\mathbf{x}_{j}+\delta,y_{j}\right)$

Apply the first order Taylor expansion of $\hat{\theta}_{\varepsilon}$ on
$\hat{\theta}$ on the right side of the equation, we have:

$\displaystyle 0=$
$\displaystyle{\left[\frac{1}{N}\sum_{k=1}^{N}\nabla_{\theta}\ell\left(\mathbf{x}_{k},y_{k}\right)+\varepsilon\nabla_{\theta}\ell\left(\mathbf{x}_{j}+\delta,y_{j}\right)-\varepsilon\nabla_{\theta}\ell\left(\mathbf{x}_{j},y_{j}\right)\right]}+$
(11)
$\displaystyle{\left[\frac{1}{N}\sum_{k=1}^{N}\nabla_{\theta}^{2}\ell\left(\mathbf{x}_{k},y_{k}\right)+\varepsilon\nabla_{\theta}^{2}\ell\left(\mathbf{x}_{j}+\delta,y_{j}\right)-\varepsilon\nabla_{\theta}^{2}\ell\left(\mathbf{x}_{j},y_{j}\right)\right]\cdot\Delta\theta_{\varepsilon}}+o(\Delta\theta_{\varepsilon}^{2})$

Since $\hat{\theta}$ minimize the loss function without perturbation,
$\frac{1}{N}\sum_{k=1}^{N}\nabla_{\hat{\theta}_{\varepsilon}}\ell\left(\mathbf{x}_{k},y_{k}\right)$$=$$0$.
Dropping $o(\Delta\theta_{\varepsilon}^{2})$ term, We have:

$\displaystyle\Delta\theta_{\varepsilon}\approx$
$\displaystyle-\left[\frac{1}{N}\sum_{k=1}^{N}\nabla_{\theta}^{2}\ell\left(\mathbf{x}_{k},y_{k}\right)+\varepsilon\nabla_{\theta}^{2}\ell\left(\mathbf{x}_{j}+\delta,y_{j}\right)-\varepsilon\nabla_{\theta}^{2}\ell\left(\mathbf{x}_{j},y_{j}\right)\right]^{-1}\cdot$
(12)
$\displaystyle\left[\varepsilon\nabla_{\theta}\ell\left(\mathbf{x}_{j}+\delta,y_{j}\right)-\varepsilon\nabla_{\theta}\ell\left(\mathbf{x}_{j},y_{j}\right)\right]$

Take the derivative of $\Delta\theta_{\varepsilon}$ over $\varepsilon$, by
dropping $O(\varepsilon)$ terms we have:

$\displaystyle\frac{\partial\Delta\theta_{\varepsilon}}{\partial\varepsilon}=$
$\displaystyle-\frac{1}{N}\sum_{k=1}^{N}\nabla_{\hat{\theta}}^{2}\ell\left(\mathbf{x}_{k},y_{k}\right)^{-1}\left[\nabla_{\hat{\theta}}\ell\left(\mathbf{x}_{j}+\delta,y_{j}\right)-\nabla_{\hat{\theta}}\ell\left(\mathbf{x}_{j},y_{j}\right)\right]$
(13) $\displaystyle=-H_{\hat{\theta}}^{-1}\sum_{l\in
L}(\nabla\ell\left(\mathbf{x}_{j}+\delta,y_{l}\right)-\nabla\ell\left(\mathbf{x}_{j},y_{j}\right))$

For sufficient large $N$, by setting $\varepsilon$ to $\frac{1}{N}$, the
changed we can approximate the actual change in model parameters using:
$\mathcal{I}(\mathbf{x}_{j}\rightarrow\mathbf{x}_{j}+\delta)$$=$$\hat{\theta}(\mathbf{x}_{j}\rightarrow\mathbf{x}_{j}+\delta)$$-$$\hat{\theta}$$\approx$$\hat{\theta}_{\varepsilon}$$-$$\hat{\theta}$.
Plugging into Eq. (13), we finish the proof:

$\displaystyle\mathcal{I}(\mathbf{x}_{j}\rightarrow\mathbf{x}_{j}+\delta)$
$\displaystyle\approx-
H_{\hat{\theta}}^{-1}(\nabla\ell\left(\mathbf{x}_{j}+\delta,y_{l}\right)-\nabla\ell\left(\mathbf{x}_{j},y_{j}\right))$
(14)
$\displaystyle=-H_{\hat{\theta}}^{-1}\nabla\ell\left(\mathbf{x}_{j}+\delta,y_{l}\right)+H_{\hat{\theta}}^{-1}\nabla\ell\left(\mathbf{x}_{j},y_{l}\right)$
$\displaystyle=\mathcal{I}(+(\mathbf{x}_{j}+\delta))+\mathcal{I}(-\mathbf{x}_{j}).$

∎

See 3.3

###### Proof.

Similarly to the edge removal, we first calculate the node representation
change incurred from the removal of the node $v_{i}$ of a 2-layer SGC as
follow:

$\displaystyle\Delta(-v_{i})$
$\displaystyle=\left[(\mathbf{D}_{-v_{i}}^{-\frac{1}{2}}\mathbf{A}_{-v_{i}}\mathbf{D}_{-v_{i}}^{-\frac{1}{2}})^{2}-(\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}})^{2}\right]\mathbf{X}.$
(15)

The above change will affect a set of nodes, including the node $v_{i}$ itself
and the 2-hop neighbors of the node $v_{i}$ connected neighbors. A set of
nodes
$S$$=$$\\{s|s\in\mathcal{N}_{i}\cup_{j\in\mathcal{N}_{i}}\mathcal{N}_{j}\\}$
capture the changed node embeddings in the training set, i.e., $\delta_{s}\neq
0$, where $\Delta_{-v_{i}}=\\{\delta_{i}\\}_{i=1}^{N}$ in Eq. (15). The model
parameter change of the removal of the node $v_{i}$ can be characterized by
removing the representation of the node $v_{i}$ if the node $v_{i}$ is a
training sample, and the node representation change from the set $S$. Thus, we
have

$\displaystyle\mathcal{I}(-v_{i})$ $\displaystyle=-\mathbbm{1}_{v_{i}\in
V_{\text{train}}}\cdot\mathcal{I}\left(\mathbf{z}_{i},y_{i}\right)+\sum_{s\in\\{S\backslash
v_{i}\\}}(\mathcal{I}\left(\mathbf{z}^{\prime}_{s},y_{s}\right)-\mathcal{I}\left(\mathbf{z}_{s},y_{s}\right))$
(16) $\displaystyle=-\mathbbm{1}_{v_{i}\in
V_{\text{train}}}\cdot\mathbf{H}_{\hat{\theta}}^{-1}\nabla\mathcal{L}_{\textup{CE}}\left(\mathbf{z}_{i},y_{i}\right)-\mathbf{H}_{\hat{\theta}}^{-1}\sum_{s\in
S\backslash
v_{i}}(\nabla\mathcal{L}_{\textup{CE}}\left(\mathbf{z}^{\prime}_{s},y_{s}\right)-\nabla\mathcal{L}_{\textup{CE}}\left(\mathbf{z}_{s},y_{s}\right)).$

We finish the proof. ∎

See 4.1

###### Proof.

In this proof, we utilize a one-step Newton approximation as an intermediary
to estimate the error bound of the change in model parameters, i.e.,

$Err(-e_{ij})=\left[\mathcal{I}^{*}(-e_{ij})-\mathcal{I}^{Nt}(-e_{ij})\right]+\left[\mathcal{I}^{Nt}(-e_{ij})-\mathcal{I}(-e_{ij})\right],$
(17)

where
$\mathcal{I}^{*}(-e_{ij})$$=$$\Delta\hat{\theta}_{\varepsilon}$$=$$\hat{\theta}_{\varepsilon}$$-$$\hat{\theta}$,
$\mathcal{I}^{Nt}(-e_{ij})$ is the one-step Newton approximation with the
model parameter $\hat{\theta}_{Nt}$$=$$\hat{\theta}+\Delta\hat{\theta}_{Nt}$.
According to Boyd et al. [2004] (Section 9.5.1), $\Delta\hat{\theta}_{Nt}$ can
be calculated as follows:

$\displaystyle\Delta\hat{\theta}_{Nt}=$
$\displaystyle-\left(\mathbf{H}_{\hat{\theta}}+\lambda\mathbf{I}\right)^{-1}\cdot\frac{1}{N}(\sum_{i=1}^{N}\nabla_{\hat{\theta}}\ell(\mathbf{z}_{i},y_{i})+\sum_{v_{l}\in
L}\nabla_{\hat{\theta}}\ell(\mathbf{z}^{\prime}_{l},y_{l})$ (18)
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ -\sum_{v_{l}\in
L}\nabla_{\hat{\theta}}\ell(\mathbf{z}_{l},y_{l})+\lambda\|\hat{\theta}\|_{2}).$

In the following, we will calculate the bound of
$\mathcal{I}^{*}(-e_{ij})-\mathcal{I}^{Nt}(-e_{ij})$ and
$\mathcal{I}^{Nt}(-e_{ij})-\mathcal{I}(-e_{ij})$ as two separate steps and
combine them together. Here we define the before and after objective functions
with the removal of edge $e_{ij}$ as follows:

$\displaystyle\mathcal{L}_{b}(\theta)$
$\displaystyle=\sum_{i=1}^{n}\ell(\mathbf{z}_{i},y_{i})+\frac{\lambda}{2}\|\theta\|^{2}_{2},$
(19) $\displaystyle\mathcal{L}_{a}(\theta)$
$\displaystyle=\sum_{i=1}^{n}\ell(\mathbf{z}_{i},y_{i})+\sum_{v_{l}\in
L}\ell(\mathbf{z}^{\prime}_{l},y_{l})-\sum_{v_{l}\in
L}\ell(\mathbf{z}_{l},y_{l})+\frac{\lambda}{2}\|\theta\|^{2}_{2}.$

Step I: Bound of $\mathcal{I}^{*}(-e_{ij})-\mathcal{I}^{Nt}(-e_{ij})$.

Due to that SGC model is convex on $\theta$, we take the second derivative of
$\mathcal{L}_{a}(\theta)$ and have

$\lambda\mathbf{I}+\frac{1}{N}{\left[\sum_{i=1}^{N}\nabla^{2}\mathcal{L}\left(\mathbf{z}_{i},y_{i}\right)+\sum_{v_{l}\in
L}\nabla^{2}\mathcal{L}\left(\mathbf{z}^{\prime}_{l},y_{l}\right)-\sum_{v_{l}\in
L}\nabla^{2}\mathcal{L}\left(\mathbf{z}_{l},y_{l}\right)\right]}\succ 0.\\\ $
(20)

To simplify the above equation, we define $\sigma^{\prime}_{min}$ and
$\sigma^{\prime}_{max}$ are the smallest and largest eigenvalues of
$\nabla^{2}\ell\left(\mathbf{z}^{\prime}_{l},y_{l}\right)$ and $\sigma_{min}$
and $\sigma_{max}$ are the smallest and largest eigenvalues of
$\nabla^{2}\mathcal{L}\left(\mathbf{z}_{l},y_{l}\right)$. Then we have

$\mathbf{I}\cdot\left(\lambda+\frac{(N-|L|)\cdot\sigma_{min}+|L|\cdot\sigma^{\prime}_{min}}{N}\right)\succ
0.$ (21)

Therefore, the SGC loss function corresponds to the removal of edge is
strictly convex with the parameter
$\left(\lambda+\frac{(N-|L|)\cdot\sigma_{min}+|L|\cdot\sigma^{\prime}_{min}}{N}\right)$.
By this convexity property and the implications of strong convexity [Boyd et
al., 2004] (Section 9.1.2), we can bound
$\mathcal{I}^{*}(-e_{ij})-\mathcal{I}^{Nt}(-e_{ij})$ with the first derivative
of SGC loss function as follows:

$\displaystyle\mathcal{I}^{*}(-e_{ij})-\mathcal{I}^{Nt}(-e_{ij})$ (22)
$\displaystyle=$
$\displaystyle\|\Delta\hat{\theta}_{\varepsilon}-\Delta\hat{\theta}_{Nt}\|_{2}=\|(\Delta\hat{\theta}_{\varepsilon}+\hat{\theta})-(\Delta\hat{\theta}_{Nt}+\hat{\theta})\|_{2}=\|\hat{\theta}_{\varepsilon}-\hat{\theta}_{Nt}\|_{2}$
$\displaystyle\leq$
$\displaystyle\frac{2N}{N\lambda+(N-|L|)\sigma_{min}+|L|\sigma^{\prime}_{min}}\cdot\Big{\Arrowvert}\frac{1}{N}(\sum_{i=1}^{N}\nabla_{\hat{\theta}_{Nt}}\ell(\mathbf{z}_{i},y_{i})+\sum_{v_{l}\in
L}\nabla_{\hat{\theta}_{Nt}}\ell(\mathbf{z}^{\prime}_{l},y_{l})$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -\sum_{v_{l}\in
L}\nabla_{\hat{\theta}_{Nt}}\ell(\mathbf{z}_{l},y_{l})+\lambda\|\hat{\theta}_{Nt}\|_{2})\Big{\Arrowvert}_{2}.$

If we take a close look at the second term in the above equation, we notice it
is equal the first derivative of $\mathcal{L}_{a}(\theta)$, i.e.,

$\nabla_{\theta}\ell_{a}(\hat{\theta}_{Nt})=\frac{1}{N}(\sum_{k=1}^{N}\nabla_{\hat{\theta}_{Nt}}\ell(\mathbf{z}_{k},y_{k})+\sum_{v_{l}\in
L}\nabla_{\hat{\theta}_{Nt}}\ell(\mathbf{z}^{\prime}_{l},y_{l})-\sum_{v_{l}\in
L}\nabla_{\hat{\theta}_{Nt}}\ell(\mathbf{z}_{l},y_{l})+\lambda\|\hat{\theta}_{Nt}\|_{2}).$
(23)

Therefore, we focus on bounding
$\|\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta}_{Nt})\|_{2}$ in the following.

$\displaystyle\|\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta}_{Nt})\|_{2}=\|\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta}+\Delta\hat{\theta}_{Nt})\|_{2}$
(24) $\displaystyle=$
$\displaystyle\|\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta}+\Delta\hat{\theta}_{Nt})-\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta})+\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta})\|_{2}$
$\displaystyle=$
$\displaystyle\|\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta}+\Delta\hat{\theta}_{Nt})-\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta})-\nabla^{2}_{\theta}\mathcal{L}_{a}(\hat{\theta})\Delta\hat{\theta}_{Nt}\|_{2}$

The above last equation holds due to the definition of
$\Delta\hat{\theta}_{Nt}$ in Eq. (18).

For any continuous function $f$ and any inputs a and b, there exists
$f(a+b)-f(a)-bf^{\prime}(a)$$=$$\int_{0}^{1}b\cdot(f^{\prime}(a+bt)-f^{\prime}(a))dt$.
Based on that, we can rewrite
$\|\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta}_{Nt})\|_{2}$ as follows:

$\displaystyle\|\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta}_{Nt})\|_{2}=$
$\displaystyle\|\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta}+\Delta\hat{\theta}_{Nt})-\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta})-\nabla^{2}_{\theta}\mathcal{L}_{a}(\hat{\theta})\Delta\hat{\theta}_{Nt}\|_{2}$
(25) $\displaystyle=$
$\displaystyle\Big{\Arrowvert}\int_{0}^{1}\Delta\hat{\theta}_{Nt}(\nabla^{2}_{\theta}\mathcal{L}_{a}(\hat{\theta}+\Delta\hat{\theta}_{Nt}\cdot
t)-\nabla^{2}_{\theta}\mathcal{L}_{a}(\hat{\theta}))dt\Big{\Arrowvert}_{2}.$

We assume the loss function $\ell$ on is twice differentiable and the second
derivative of the loss function is Lipschitz continuous at $\theta$, with
parameter $C$. Here C is controlled by the third derivative (Curvature) of the
loss function $\ell$. Thus, we have

$\|\nabla^{2}_{\theta}\ell({\theta_{1}})-\nabla^{2}_{\theta}\ell({\theta_{2}})\|_{2}\leq
C\cdot\|\theta_{1}-\theta_{2}\|_{2}.$ (26)

Then we take Eq. (26) into Eq. (25) and have

$\displaystyle delt$
$\displaystyle\|\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta}_{Nt})\|_{2}$ (27)
$\displaystyle\leq$
$\displaystyle\|NC\Delta\hat{\theta}_{Nt}\int_{0}^{1}tdt\|_{2}=\frac{NC}{2}\|\Delta\hat{\theta}_{Nt}\|_{2}^{2}=\frac{NC}{2}\|\nabla^{2}_{\theta}\mathcal{L}_{a}(\hat{\theta})^{-1}\cdot\nabla_{\theta}\mathcal{L}_{a}(\hat{\theta})\|^{2}_{2}$
$\displaystyle\leq$
$\displaystyle\frac{NC}{2}\cdot\frac{N^{2}}{(N\lambda+(N-|L|)\cdot\sigma_{min}+|L|\cdot\sigma^{\prime}_{min})^{2}}\cdot\|\sum_{l\in
L}(\nabla_{\hat{\theta}}\ell\left(\mathbf{z}^{\prime}_{l},y_{l}\right)-\nabla_{\hat{\theta}}\ell\left(\mathbf{z}_{l},y_{l}\right))\|^{2}_{2}.$

The above last inequation holds according to the bound of
$\nabla^{2}_{\theta}\mathcal{L}_{a}(\hat{\theta})^{-1}$ and Eq. (19).

Combining Eq. (22), (23) and (27), we finish the bound of
$\mathcal{I}^{*}(-e_{ij})-\mathcal{I}^{Nt}(-e_{ij})$ as follows:

$\displaystyle\|\mathcal{I}^{*}(-e_{i,j})-\mathcal{I}^{Nt}(-e_{i,j})\|_{2}$
(28) $\displaystyle\leq$
$\displaystyle\frac{N^{3}C}{(N\lambda+(N-|L|)\sigma_{min}+\sigma^{\prime}_{min}|L|)^{3}}\cdot\|\sum_{v_{l}\in
L}(\nabla_{\hat{\theta}}\ell\left(\mathbf{z}^{\prime}_{l},y_{l}\right)-\nabla_{\hat{\theta}}\ell\left(\mathbf{z}_{l},y_{l}\right))\|^{2}_{2}.$

We finish Step I.

Step II: Bound of $\mathcal{I}^{Nt}(-e_{ij})-\mathcal{I}(-e_{ij})$.

By the definition of $\mathcal{I}^{Nt}(-e_{ij})$ and $\mathcal{I}(-e_{ij}))$,
we have:

$\displaystyle\mathcal{I}^{Nt}(-e_{ij})-\mathcal{I}(-e_{ij})$ (29)
$\displaystyle=$
$\displaystyle\Biggl{\\{}\left(\lambda\mathbf{I}+\frac{1}{N}{\left[\sum_{k=1}^{n}\nabla_{\hat{\theta}}^{2}\ell\left(\mathbf{z}_{k},y_{k}\right)+\sum_{v_{l}\in
L}\nabla_{\hat{\theta}}^{2}\ell\left(\mathbf{z}^{\prime}_{l},y_{l}\right)-\sum_{v_{l}\in
L}\nabla_{\hat{\theta}}^{2}\ell\left(\mathbf{z}_{l},y_{l}\right)\right]}\right)^{-1}$
$\displaystyle-\left(\lambda\mathbf{I}+\frac{1}{N}{\sum_{k=1}^{n}\nabla_{\hat{\theta}}^{2}\ell\left(\mathbf{z}_{k},y_{k}\right)}\right)^{-1}\Biggl{\\}}\cdot\Biggl{\\{}\sum_{v_{l}\in
L}(\nabla_{\hat{\theta}}\ell\left(\mathbf{z}^{\prime}_{l},y_{l}\right)-\nabla\ell\left(\mathbf{z}_{l},y_{l}\right))\Biggl{\\}}.$

For simplification, we use matrix $\mathbf{A}$, $\mathbf{B}$ and $\mathbf{C}$
for the following substitutions:

$\displaystyle\mathbf{A}=\lambda\mathbf{I}+\frac{1}{N}{\left[\sum_{k=1}^{n}\nabla_{\hat{\theta}}^{2}\ell\left(\mathbf{z}_{k},y_{k}\right)-\sum_{v_{l}\in
L}\nabla_{\hat{\theta}}^{2}\ell\left(\mathbf{z}_{l},y_{l}\right)\right]},$
(30) $\displaystyle\mathbf{B}=\frac{1}{N}\sum_{v_{l}\in
L}\nabla_{\hat{\theta}}^{2}\ell\left(\mathbf{z}^{\prime}_{l},y_{l}\right),\ \
\textup{and}\ \ \mathbf{C}=\frac{1}{N}\sum_{v_{l}\in
L}\nabla_{\hat{\theta}}^{2}\ell\left(\mathbf{z}_{l},y_{l}\right),$

where $\mathbf{A}$, $\mathbf{B}$ and $\mathbf{C}$ are positive definite matrix
and have the following properties:

$\displaystyle\lambda+\frac{(N-|L|)\sigma_{max}}{N}\succ$
$\displaystyle\mathbf{A}\succ\lambda+\frac{(N-|L|)\sigma_{min}}{N},$ (31)
$\displaystyle\frac{|L|\sigma^{\prime}_{max}}{N}\succ$
$\displaystyle\mathbf{B}\succ\frac{|L|\sigma^{\prime}_{min}}{N},\ \
\textup{and}\ \
\frac{|L|\sigma_{max}}{N}\succ\mathbf{C}\succ\frac{|L|\sigma_{min}}{N}.$

Therefore, we have

$\mathcal{I}^{Nt}(-e_{ij})-\mathcal{I}(-e_{ij})=((\mathbf{A}+\mathbf{B})^{-1}-(\mathbf{A}+\mathbf{C})^{-1})\cdot\Biggl{\\{}\sum_{v_{l}\in
L}(\nabla_{\hat{\theta}}\ell\left(\mathbf{z}^{\prime}_{l},y_{l}\right)-\nabla_{\hat{\theta}}\ell\left(\mathbf{z}_{l},y_{l}\right))\Biggl{\\}},$
(32)

where
$(\mathbf{A}+\mathbf{B})^{-1}-(\mathbf{A}+\mathbf{C})^{-1}\prec\frac{N}{N\lambda+(N-|L|)\sigma_{min}+|L|min(\sigma^{\prime}_{min},\sigma_{min})}\mathbf{I}$.

The $l_{2}$ norm of the error between our predicted influence and Newton
approximation can be bounded as follows:

$\displaystyle\|\mathcal{I}^{Nt}(-e_{ij})-\mathcal{I}(-e_{ij})\|_{2}$ (33)
$\displaystyle\leq$
$\displaystyle\frac{N}{N\lambda+(N-|L|)\sigma_{min}+\min(\sigma^{\prime}_{min},\sigma_{min})|L|}\cdot\|\sum_{v_{l}\in
L}(\nabla\ell_{\hat{\theta}}\left(\mathbf{z}^{\prime}_{l},y_{l}\right)-\nabla\ell_{\hat{\theta}}\left(\mathbf{z}_{l},y_{l}\right))\|_{2}.$

We finish Step II.

Combining the conclusion in Step I and II in Eq. (28) and (33), we have the
error between the actual influence and our predicted influence as:

$\displaystyle Err(-e_{ij})$ (34) $\displaystyle\leq$
$\displaystyle\|\mathcal{I}^{*}(-e_{ij})-\mathcal{I}^{Nt}(-e_{ij})\|_{2}+\|\mathcal{I}^{Nt}(-e_{ij})-\mathcal{I}(-e_{ij})\|_{2}$
$\displaystyle=$
$\displaystyle\frac{N^{3}C}{(N\lambda+(N-|L|)\sigma_{min}+|L|\sigma^{\prime}_{min})^{3}}\cdot\|\sum_{v_{l}\in
L}(\nabla_{\hat{\theta}}\ell\left(\mathbf{z}^{\prime}_{l},y_{l}\right)-\nabla_{\hat{\theta}}\ell\left(\mathbf{z}_{l},y_{l}\right))\|^{2}_{2}$
$\displaystyle+\frac{N}{N\lambda+(N-|L|)\sigma_{min}+\min(\sigma^{\prime}_{min},\sigma_{min})}\cdot\|\sum_{v_{l}\in
L}(\nabla_{\hat{\theta}}\ell\left(\mathbf{z}^{\prime}_{l},y_{l}\right)-\nabla_{\hat{\theta}}\ell\left(\mathbf{z}_{l},y_{l}\right))\|_{2}.$

We finish the whole proof. ∎

######  Corollary A.1.

Let $\sigma_{\text{min}}\geq 0$ denote the smallest eigenvalue of all
eigenvalues of Hessian matrices
$\nabla_{\hat{\theta}}^{2}\ell(\mathbf{z}_{i},y_{i}),\forall v_{i}\in
V_{\text{train}}$ of the original model $\hat{\theta}$. Let
$\sigma_{\text{min}}^{\prime}\geq 0$ denote the smallest eigenvalue of all
eigenvalues of Hessian matrices
$\nabla_{{\hat{\theta}}(-v_{i})}^{2}\ell(\mathbf{z}_{i},y_{i}),\forall
v_{i}\in V_{\text{train}}$ of the retrained model $\hat{\theta}(-v_{i})$ with
$v_{i}$ removed from graph $G$. Use $S$ denote the set
$\\{v:\mathbf{z}^{\prime}\neq\mathbf{z}\\}$ containing affected nodes from the
node removal, and
$\text{Err}(-v_{i})=\|\mathcal{I}^{*}(-v_{i})-\mathcal{I}(-v_{i})\|_{2}$. We
have the following upper bound on the estimated error of model parameters’
change:

$\displaystyle\text{Err}(-v_{i})\leq$
$\displaystyle\frac{N^{3}m^{2}C}{((N-1)\lambda+(N-|S|)\sigma_{\text{min}}+\sigma_{\text{min}}^{\prime}|S|)^{3}}+\frac{(N-1)m}{N\lambda+(N-|S|)\sigma_{\text{min}}+\min(\sigma_{\text{min}},\sigma_{\text{min}}^{\prime})|S|}$
(35)
$\displaystyle+\frac{N^{3}C}{(N\lambda+(N-1)\sigma_{\text{min}})^{3}}\cdot\|\ell\left(\mathbf{z}^{\prime}_{i},y_{i}\right)\|_{2}^{2}+\frac{N}{N\lambda+N\sigma_{min}}\cdot\|\ell\left(\mathbf{z}^{\prime}_{i},y_{i}\right)\|_{2}$

where $m=\|\sum_{v_{s}\in
S}[\nabla_{\hat{\theta}}\ell(\mathbf{z}^{\prime}_{s},y_{s})-\nabla_{\hat{\theta}}\ell(\mathbf{z}_{s},y_{s})]-\nabla_{\hat{\theta}}\ell(\mathbf{z}_{i},y_{i})\|_{2}$.

###### Proof.

We provide a simple proof for the error bound of removing a complete nodes.
Notice that this error can be decomposed into two parts, 1, the error or
removing a single node embedding $\mathbf{z}_{i}$ and 2, the error of adding
$\mathbf{z}^{\prime}_{s}$ and removing $\mathbf{z}_{s}$, where $s$$\in$$S$.
where we have

$\displaystyle Err(-v_{i})\leq\sum_{s\in S}Err(z_{s}\rightarrow
z^{\prime}_{s})+Err(-z_{i})$

Notice that Eq. Theorem 4.1 proofs the error bound of $Err(-v_{i})$. In the
proving process, we decompose the problem into deriving the error bound by
adding $\mathbf{z}^{\prime}_{l}$ and removing $\mathbf{z}_{l}$ where
$l$$\in$$L$, where $L$ is the set of changed node embedding caused by removing
an edge from the graph. Following the same proving setting of Eq. Theorem 4.1,
Again, notice that $S$ is 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 $\sum_{s\in S}Err(z_{s}\rightarrow z^{\prime}_{s})$.

$\displaystyle\sum_{s\in S}Err(z_{s}\rightarrow
z^{\prime}_{s})\leq\frac{N^{3}m^{2}C}{N\lambda+(N-|S|)\sigma_{\text{min}}+\sigma_{\text{min}}^{\prime}|S|)^{3}}$
$\displaystyle+\frac{(N-1)m}{N\lambda+(N-|S|)\sigma_{\text{min}}+\min(\sigma_{\text{min}},\sigma_{\text{min}}^{\prime})|S|}\
,$

Where $m=\|\sum_{v_{s}\in
S}[\nabla_{\hat{\theta}}\ell(\mathbf{z}^{\prime}_{s},y_{s})-\nabla_{\hat{\theta}}\ell(\mathbf{z}_{s},y_{s})]\|_{2}$.
For $Err(-z_{i})$, it can be derived following the same proving process as Eq.
Theorem 4.1, but we only remove one data points. In this case, we have:

$\displaystyle Err(-z_{i})$
$\displaystyle\leq\frac{N^{3}C}{(N\lambda+(N-1)\sigma_{\text{min}})^{3}}\cdot\|\ell\left(\mathbf{z}^{\prime}_{i},y_{i}\right)\|_{2}^{2}+\frac{N}{N\lambda+N\sigma_{min}}\cdot\|\ell\left(\mathbf{z}^{\prime}_{i},y_{i}\right)\|_{2}.$

Combining the two error bounds we have:

$\displaystyle Err(-v_{i})\leq$
$\displaystyle\frac{N^{3}m^{2}C}{((N-1)\lambda+(N-|S|)\sigma_{\text{min}}+\sigma_{\text{min}}^{\prime}|S|)^{3}}+\frac{(N-1)m}{N\lambda+(N-|S|)\sigma_{\text{min}}+\min(\sigma_{\text{min}},\sigma_{\text{min}}^{\prime})|S|}$
(36)
$\displaystyle+\frac{N^{3}C}{(N\lambda+(N-1)\sigma_{\text{min}})^{3}}\cdot\|\ell\left(\mathbf{z}^{\prime}_{i},y_{i}\right)\|_{2}^{2}+\frac{N}{N\lambda+N\sigma_{min}}\cdot\|\ell\left(\mathbf{z}^{\prime}_{i},y_{i}\right)\|_{2}$

∎