Influence Functions for Edge Edits in Non-Convex Graph Neural Networks
Authors: Jaeseung Heo
Kyeongheung Yun
Seokwon Yoon
MoonJeong Park
Jungseul Ok
Dongwoo Kim
Venue: NeurIPS 2025 poster ()
Keywords: influence function
transductive node classification
Primary area: deep_learning

Abstract: Understanding how individual edges influence the behavior of graph neural networks (GNNs) is essential for improving their interpretability and robustness. Graph influence functions have emerged as promising tools to efficiently estimate the effects of edge deletions without retraining. However, existing influence prediction methods rely on strict convexity assumptions, exclusively consider the influence of edge deletions while disregarding edge insertions, and fail to capture changes in message propagation caused by these modifications. In this work, we propose a proximal Bregman response function specifically tailored for GNNs, relaxing the convexity requirement and enabling accurate influence prediction for standard neural network architectures. Furthermore, our method explicitly accounts for message propagation effects and extends influence prediction to both edge deletions and insertions in a principled way. Experiments with real-world datasets demonstrate accurate influence predictions for different characteristics of GNNs. We further demonstrate that the influence function is versatile in applications such as graph rewiring and adversarial attacks.

Influence Functions for Edge Edits in Non-Convex Graph Neural Networks
Jaeseung Heo', Kyeongheung Yun?, Seokwon Yoon",
MoonJeong Park Jungseul Ok1.2, Dongwoo Kim
GGaduuate School of Artificial Intelligence 2Department of Computer Science & Engineering
POSTECH, South Korea
( jarpoong.pjuuugnae... jungseul wdwggsookkimmgppssecchccooo ong.ggagggggggoooooooototooootto
ac.
Abstract
Understanding how individual edges influence the behavior of graph neural net- works (GNNs) is essential for improving their interpretability and robustness. Graph influence functions have emerged as promising tools to efficiently estimate the effects of edge deletions without retraining. However, existing influence pre- diction methods rely on striet convexity assumptions, exclusively consider the influence of edge deletions while disregarding edge insertions, and fail to capture changes message propagation caused by these modifications. In this work, we propose proximal Bregman response function specifically tailored for GNNs, relaxing the convexity requirement and enabling accurate influence prediction for standard neural network architectures. Furthermore, for message propagation effects and extends influence prediction to both edge dele- tions and insertions in principled way. Experiments with real-worlh datasets demonstrate accurate influence predictions for different characteristics of GNNs. We further demonstrate that the influence function is versatile in applications such as graph rewiring and adversarial attacks.
method explicitly accounts
1 Introduction
Graph neural networks (GNNs) have demonstrated that leveraging structural relationships, often encoded connectivity between data points, enhance the predictive performance of neural net- works across many tasks. Although the literature clearly identifies the importance of the relationship. the individual contribution of each connectivity, i.e., edge, remains poorly understood.
Several recent studies have explored edge importance from a particular perspective. For example, Nguyen et al. [26] propose an edge rewiring method to mitigate the problem of over-smoothing [23], a phenomenon where the learned node representation becomes indistinguishable as the depth of the GNN increases. Alon and Yahav [2] suggest edge rewiring methods to overcome the over-squashing, which occurs when information propagation encounters bottlenecks between distant nodes.
Despite progress in addressing individual challenges, unified framework for quantifying edge influence across these perspectives would provide more comprehensive understanding of their role in graph neural networks. For instance, it would allow us to assess how modifying a single edge affects model behavior from both over-smoothing and -uur-squg perspectives. On the other hand, influence functions have been introduced to quantify the impact on evaluation metrics, such as validation loss, when training data point removed [21]. To do so, the function estimates the changes in model parameters when the target data point is excluded from the training.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Over-squashing
Over-smoothing
Beneficial Edges
Harmful Edges
Figure I: An illustration of beneficial and harmful edges identified by an influence function proposed in this work with respect to two evaluation metrics. A harmful edge is one that either blocks informa- tion propagation between nodes (over-squashing (2]) or makes node representations indistinguishable (over-smoothing [23]). The barbell graph consists of two clusters, each with distinct node labels. The influence function can be used to analyze the properties of edges. For example, the edges connecting two different clusters mitigate over-squashing while amplifying ver-smoothing.
Applying influence functions [21] to GNNs introduces a unique challenge, primarily because modify- ing an edge can alter the propagation paths and consequently change the underlying computational graph structure. Previous attempts to adapt influence functions for GNNs have focused parameter changes, failing to address the influence of the changes in the computational graph [7, 35]. Moreover, their influence functions rely the strict convexity assumption of the loss function with respect to the model parameters, which limits their applicability widely used non-convex GNNs.
In this work, we propose an influence function tailored specifically for GNNs, enabling precise predictions regarding the effects of edge modifications from multiple perspectives. To do so, we overcome the unique challenges of GNNs by deriving the changes in the evaluation function from fundamental principles of calculus. deletion and insertion, the latter of which has not been explored in previous studies. To extend the influence function to non-convex GNNs, we establish the proximal Bregman response function [3] for node classification. The influence function derived from this response function relies on weaker assumptions that generally hold for non-convex GNNs. Figure shows an example of influence analysis for a barbell graph from two different perspectives. Through the analysis, one identify that the edges connecting two different clusters have opposite influences on over-squashing and over-smoothing, providing unifying view on edge importance.
result, our function can measure the influence of both edge
datasets demonstrate that our influence function accurately predicts edge influence in non-convex GNNs. We further show that the influence function is a versatile tool for analyzing various properties of GNNs. We present three practical applications, including 1) an analysis of edge rewiring methods suggested to improve the predictive performance of GNNs, 2) identifying adversarial edge edits that could alter node predictions, and 3) an analysis of edges connecting the nodes with the same label or different labels in terms of the node classification performance.
Experiments on
2 Preliminary
2.1 Influence function for convex models
Let L(x, y, 8) be loss function, where æ is the input, y the label, and f the model parameters. The optimal parameters 6" minimize the empirical loss over the training set Dirain
0" arg min
Σ (2.
C(a, y, 0).
(I)
Influence functions quantify how removing a specific training data point (x', yy) impacts model parameters. Computing the exact impact would require retraining the model by excluding the data

---

point from the training set, which is computationally expensive. Instead, one can model response function that measures the changes parameters when the data point is upweighted by an amount of 6 E IR by solving the following optimization problem:
0 ,y = arg min
Σ
2 el(a', v. 0),
N
(x.y))
where N [Prainl For example, ,',9', ,3/,==1// corresponds the optimal parameter obtained from Dirain \ [x',3'/
The changes in parameter further influence evaluation function f. such as validation loss. Koh and Liang [21] demonstrate that when the loss function strictly convex with respect to 0, the derivative of (0>r,r)e) with respect to evaluated at 0 is:
df (0 (0 vr
d8
-of((*)
x',
Vof((") Ha. Vol'''C('
de
de
le=0
==0
where Hg. = & ((zD)) ViL(z, y, (*) ) the Hessian matrix evaluated at 0* Finally, one can approximate the influence of data point (x', v') on the evaluation function f through the linearization around the optimal parameter 0" without retraining:
1 N
(0w,) (0))
Vof(O") H Ho.'VoL(z'.v'
When the objective is non-convex, the Hessian can be added with a damping term À E R, i.c., Hg- + AI, leading to positive definite matrix. We provide a complete derivation in Appendix A.
2.2 Influence function for neural networks
Although the influence function in Equation (4) reliably measures the influence of an input for a linear model with convex objective, the computation is unreliable in practice with deep neural networks, c.f. [4]. Bae et al. [3] identify the three main sources of unreliability related to the standard practices of neural network training and fine-tuning: 1) non-convex models, the response function is affected more by parameter initialization than by the influence of the data, as gradient methods approximate the solution. The addition of the damping term works as an & regularizer of Equation (1) leading to different response function. 3) The influence function is measured on fully converged parameter f*, which is not true practice due many reasons, such early stopping and over- over-fitting mitigation.
Bae al. [3] propose a response function, named the proximal Bregman response function (PBRF), to address the three practices:
+ A 110 - 0ol1 + eC(x', 80,0), (5)
0 O'. v/.e = arg min
Σ (B.i)
De (0,
N
where ga is model parameterized by 0. 02 is reference parameter from which the fine-tuning starts, and D is the Bregman divergence defined as:
De (h, h v) = - VnL
(M. M²
(6)
For detailed explanations of each term in Equation (5), please refer to Bae et al. [3].
The objective be further linearized around the model output simulate the local approximations
made in Equation (4), leading to the following influence function':
"qquation (7) is originally proposed by Teso et al. [31] an approximation of Equation (4). Bae et al. [3] provide corresponding response function the approximation.

---

f { f (0.)
1 vof(O.) (Jho, Hn, Jno, + AI) VoL(z'. (7)
where h and ht denote the model outputs parameterized by 0 and Os. respectively. Jao, is the Jacobian of the model outputs with respect to the parameters, and Hn, is the Hessian of with respect the outputs. When the loss function is convex with respect to the model outputs, the matrix Tee HA, Jno, is positive semi-definite. This convexity condition is satisfied by commonly used loss functions, such cross-entropy and mean squared error. Consequently, for À > 0, the matrix hoo HA, Jo, + AI becomes positive definite, ensuring its invertibility. We provide the complete derivation in Appendix A.
3 Quantifying the influence of edge edits on GNNs
Problem setup and notation We propose an influence function tailored for non-convex GNNs, designed to quantify how edge deletions and insertions perturb model predictions and evaluation functions. We consider node classification on an undirected graph G = E,,,,X) where V is the set of nodes, & S V x V forms the set of edges, and X E TR| represents the matrix of node feature X, Id for all node v E V. We also represent the graph structure using a binary symmetric adjacency matrix goal of the node classification is to predict the ground truth label ye y of node E V. The notation ig.0 refers to the representation of node v obtained by a GNN parameterized by 0 on graph G. A standard supervised training involves minimization of the average prediction loss C( yo) over the entire training set Virain S V with respect to the model parameter 0.
{0, 1) |VM,, where Aur indicates an edge between nodes u and v. The
We focus analyzing the effect of inserting deleting a single undirected edge fu, v). The derivation naturally generalizes to multiple edge edits, which are provided in Appendix C. We first define the reweighted adjacency matrix A such that only the (u, v) and (v, u) entries
updated as A = A... + (2I v} E| 1). while all other entries remain unchanged. Setting c - 1/N corresponds deleting the edge if it exists, inserting it otherwise. We denote the edge-reweighted graph as G = {V,E, A*), where we omit the target edge {u, 2) from the adjacency matrix when clear from context for notational simplicity. We collectively refer to edge deletions and insertions as edge edits.
Decomposition of influence function Let f00 g) be evaluation function, to which we want to measure the influence of edge edit. Note that unlike standard parameterization of the evaluation function, i.e., f()), the evaluation function needs to be parameterized by both the model parameter and the graph structure G. because an edge edit not only changes the model parameter but also changes the message propagation paths in GNNs. Due to the dependency of the evaluation function on the graph structure, the derivative the evaluation function with respect to the change in the weighting of target edge is decomposed as follows via the chain rule:
df (02.99) de
a0e
(f(0g9) DA
Vaf(06.9 9)
(8)
de
0A
de
c=
10=00 c=0
parameter shift
message propagation
where 8 represents the response function of an edge edit; a formal definition is provided in the following paragraph.
Remark. The influence functions proposed for GNNs Chen el al. [7], Wu al. [35] only consider the effect of parameter shift while missing the changes in the message propagation path.
Parameter shift To quantify the change in model parameters for non-convex GNNs, we propose
graph-adapted version the PBRE The original PBRF, introduced Equation (5), only quantifies the changes in parameters when the weight of single data point is modified, inapplicable to our scenario where the weight of an edge changes. To address this challenge, we introduce an edge-edit PBRF that explicitly accounts for changes in node representations caused by edge edit.

---

We define the edge-edit PBRF as follows?:
8: == arg min
Σ Muni
De (h h hg...)
A 110 0all² VEVaa
E
(c
- -L -c(1 &.0 ((T=*
8
2
The first two terms regularize 0 to stay close to the reference parameter 0,, both terms of the output space and the parameter space. The final term, with 0, encourages 0 to increase the loss the original graph while decreasing the loss on the edge-edited graph. Thus, edge-edit PBRF can be interpreted as identifying parameters near 0₂ that fail to predict correctly but succeed on the edge-edited graph, thereby responding to the edge edit. The scalar controls the magnitude of this response to the edge edit. Note that 0g Os. since the Bregman divergence De(h, h', y) is minimized when = h!.
the original graph
Based the edge-edit PBRF objective, the changes in the evaluation function caused by the parameter shift are then given by:
08" de
VoL (oL( (ho.0)) - VoL [ng (g= (10)
Vef(0 9)
G E
c=0
where G To HA, Jne, + AI denotes the generalized Gauss-Newton Hessian with a damping term, and it and h2 denote the node representations obtained using parameters and 0,, respectively. detailed derivation is provided Appendix B.
Message propagation To quantify the changes in the evaluation function caused by the modification the message propagation path, we can further expand the message propagation term Equation (8). Since 0 0 0 = 0 for all {i,j} + {u, v). the message propagation term simplifies as follows:
0 8A 8A
0f(0, OA
+ 0f(0,99)0AS
aA
DA
de
1000,cc0 OA
Ōe
1=00 c=0
0=0,,c=0
@f 9) 0f(0s.
v) E E
(11)
AA 0A
Unified influence function under edge edits By substituting Equation (11) and Equation (10) into Equation (8) and linearizing around we obtain first-order approximation of the influence function that captures both parameter shift and message propagation effects. The resulting influence of an edge edit given by:
I 10= (0-4.0- (((0,))) 1 9o
Σ VoL VoL [1 & $g,)),)))))))))
(211[u,, E (ff(0..9) (100-110 AA
0f(0..
(12)
AAm
Directly computing G-1 is computationally infeasible for large models. To address this, approxi- mate the inverse Hessian-vector product G (00,, 9) using the LiSSA algorithm [1], stochastic iterative method. A detailed description provided in Appendix D.
4 Validation of influence function
measure the correctness of the proposed influence function on three different evaluation metries: swershiu and over-smoothing measures, and validation loss. Our goal is to precisely predict
For notational simplicity, we omit the label of node v in expressions involving the loss function or the Bregman divergence, as it is clear from context.
5

---

how much over over-svuaaaee squashing and wer-ssmothing measures, and validation loss change when an existing edge is deleted from the graph or when potential edge is added between two nodes.
4.1 Evaluation functions
We explain the three evaluation functions considered in detail.
Over-squashing Over-squashing [2] is the phenomenon in which information from distant nodes is overly compressed during message passing, preventing it from effectively influencing node repre- sentations. Topping et al. [32] propose a gradient-
metric Th,/ ph,/0X, /ax, to quantify the influence of the initial node feature X,, the node representation hy- One way measure over-squashing in a graph is by averaging the gradients between all pairs of distant nodes. However, computing these gradients for every such pair is computationally expensive. Moreover, estimating the influence function requires taking the derivative of this measurement, which is even more costly due to the complexity of the measurement itself. To address this issue, we propose an alternative over-squashing one but without derivation. Let (v) be the set of nodes that can be reached from node v in exactly L hops. To measure the influence of node to node in an L-layer GNN, we first define modified graph ('vv) = EV,EX X'}, where
measure similar to the gradient-
O, X
if E (v)),, otherwise,
X
(13)
for all u in V. With the modified graph, we propose new over-squashing measure as:
foo(0, 9) = Σ hg. (g
(14)
The measure computes the average difference in node representations with and without L-hop neighborhood node features. It is similar to the gradient-based metric in that both quantify how node's ' representation changes when input features other nodes are modified, although one does so through gradient computation and the other through direct input masking.
Over-smoothing We use the Dirichlet energy that quantifies the over-smoothing phenomenon in GNNs [23]. Dirichlet energy is defined the average squared & distance between the embeddings of adjacent nodes [6]. and serves as a proxy for the representational diversity across the graph. A lower Dirichlet energy indicates more severe over-smoothing, as node representations become increasingly indistinguishable due to excessive message passing. Conversely, higher Dirichlet energy suggests that node embeddings remain more discriminative.
Validation loss function.
We use a standard mean cross-entropy loss on the validation set as an evaluation
4.2 Actual vs. predicted influence
Datasets and experimental setup We conduct experiments on five datasets: the citation graphs Cora, Citeseer, and Pubmed [29, 36), where the task to predict each paper's research area based on citation relationships; and the Wikipedia graphs Chameleon and Squirrel [28], where the task is to estimate page traffic based on hyperlink relationships. For the citation graphs, we follow the data splits provided by Yang et al. [36], and for the Wikipedia graphs, use the splits from Pei et al. [27].
We evaluate the prediction performance of our method on three representative graph neural networks: GCN [20], GAT [33], and ChebNet [13]. We compare our approach with GIF, an existing graph influence function [7, 35]. To measure the actual influence, we first train the model on the original graph. We then retrain the GNN on the edge-edited graph by optimizing the minimization objective defined by each response function. Specifically, for our influence function, we fine-tuned the model by minimizing the objective in Equation (9), using the original model parameters as 0, and setting L/N. For GIF, retrain the model by minimizing the loss on the edge-edited graph, using

---

8.0 x10=
Validation Loss
Over-squashing
Dirichlet Energy
1.5
Actual Infiuence
2.0
Actual Infueecce
1.0
0.5
0.0
0.0
-2.0
-2.0
Comelation: 0.49
Correlaionn
Comreaaionn
-1.0 -0.5
Estimated influence x10
Estimated Inft unfuce x10
Estimattdd Influence
(a) GIF [7. 35]
x10-1
Validation Loss
x10-1
Over-squashing
Dirichlet Energy
Actual Influnce
2.0
Insertion
Actual Influencs
1.0
Actual Actual Infusnnce
2.0
3.0
3.0
0.0
-1.0-
0.5
200
2.0
-3.0
Comrelation 0.88
-2.0-
------63 Correlation:
3.0
Conrelation:
-1
-200-is-io
2
-1
Estimated Influence
Estimated Influence
Estimated Influence
(b) Ours
Figure 2: Predicted influence versus actual influence four-layer GCN. The x-axis represents the predicted influence, the y-axis represents the actual influence, and the dotted line represents the perfect alignment.
the same parameter initialization as the original model. The actual influence is computed as the difference between the evaluation values of the original model and the retrained model.
Results Figure 2 presents scatter plots for the Cora dataset, where each point shows the actual and predicted influence of a single edge edit. The x-axis represents the predicted influence computed by each method, and the y-axis represents the actual influence. The first row illustrates results from GIF [7, 35], while the second row shows results from our proposed method for edge deletions and insertions, respectively. Additional results for other GNNs and datasets provided in Appendix E.
GIF [7, 35] fails reliably estimate actual influences on non-convex GNNs, achieving correlations of only 0.09 and 0.14 for over sauashiuasnng and Dirichlet energy, respectively. In contrast, our proposed method significantly improves prediction, achieving correlations up to 0.95, closely aligning with the ideal predictions shown by the grey dotted line. Moreover, our method exhibits strong predictive capability for both edge deletions and insertions.
We further evaluate how editing the graph to improve each measurement affects prediction on the test nodes.
Table 1: Test accuracy edge-edited graphs. The best result highlighted in bold.
To perform the edge edits, we first compute the influ- ence function with respect to each measurement and then edit the edges that are predicted to improve the corresponding measurement, For validation loss, we edit the edges with the l smallest influence values, as negative influence indicates that removing the edge is expected to reduce the measurement. For the other measurements, we edit the edges with the & largest influence values. The value of A is selected maxi- mize validation accuracy. We compare the edge edits produced by our influence function to two baselines: random edge deletion (Random) and edge edits using GIF [7, 35] in place of our influence function.
Cora
CiteScer
PubMed
GCN
81.020.3
69.3
75.6
Random
81.1
69.2s0.4
75.7
GIF
80.9 80.9205
69.2+0s
75.6209
Ours (DE)
80.8+0.
69.5
75.4
Ours (foq)
81.1#04
69,320.
75,4
Ours (VL)
82.1
69.620.7
76.4=13
Table shows the test accuracy when the model is trained and evaluated on edge-edited graphs. Dirichlet energy (DE), over-squashing (Jog), and validation loss (VL) are used as shorthand in the table. Our edits based on validation loss achieve the best performance across three datasets. This result suggests that editing edges to reduce validation loss can helpful for improving test accuracy. In contrast, editing edges to improve Dirichlet energy or the over-squashing measurement does not
7

---

x10-
Validation Loss
2.
Over--quashing
Dirichlet Energy
Effect
2.0
Deletion
Insertion
Propagation Effert
1.5
1.0
Propagation Efact
0.0
0.0
1.-
-0.
-2.0
-3.0
Correlation: 0.07
-2.0
Correlatio::
Correlation:
-2.0-15-1.0-0
-1-5-100-5
Parameter Shift Effect x10
Parameter Shift Effect
Parameter Shift Effect
Figure 3: The relationship between parameter shift effect and message propagation effect defined in Equation (8). The x-axis denotes the parameter shift effect, and the y-axis denotes the message propagation effect.
=10-
10 Edges
x10=2
20 Edges
x10-t
100 Edges
influence
Actual infiuence
1.0
Actual Influence
0.5
2.0
0.0
0.0
-0.5
2.0
2.0
4..0
-2.0
Comelation:
-1.5
-08
0.0
68
16
-2
Estimated influence
x10
Estimated Infueece x10-
Estimated Intluence x10-2
Figure 4: Predicted influence versus actual influence four-layer GCN under varying numbers of inserted edges.
consistently improve test accuracy. This indicates that optimizing these intermediate metrics does not necessarily translate to better predictive performance. Finally, editing edges to reduce validation loss using GIF fails improve test accuracy, which attribute its inaccurate influence estimation on non-convex GNNs.
Analysis on the influence of message propagation We analyze the importance of explicitly incorporating the influence of message propagation when predicting the influence of edge edits. If the influence of the message propagation negligible or highly correlated with the influence of the parameter shift, predicting the influence of the message propagation may not be necessary. To validate the importance of the message propagation influence, we measure its correlation with the influence of parameter shift.
Figure shows scatter plots comparing these two influences the Cora dataset. We observe low correlation between the message propagation and parameter shift influence across all metrics, while their magnitudes remain comparable. These results underscore the necessity of explicitly measuring the influence of message propagation in estimating the influence of edge edits.
Influence estimation for multiple edge edits We evaluate the accuracy of the proposed influence function in predicting the actual influence under multiple edge edits. Figure 4 presents scatter plots of predicted versus actual influence when inserting different numbers of edges. The experiments are conducted on the Cora dataset, with validation loss used as the evaluation metric. Specifically, we report results for simultaneous insertions of 10, 20, and 100 edges.
Our influence function maintains a high correlation with the actual influence, achieving 0.84 even under 100 simultaneous edge edits. Nonetheless, Figure 4 shows that the accuracy of influence estimation diminishes as the number of simultaneous edits increases. We attribute this degradation to first-order approximation errors induced by substantial parameter shifts, a phenomenon that has also been consistently observed in prior studies on group influence estimation [22, 5, 30).
5 Applications
Influence function as a tool for adversarial attack Once we identify the most influential edges in the entire input graph, significantly affect the model's output by editing them. This process

---

Table 2: Test accuracy under adversarial edge edits. The attack ratio denotes the percentage of edges added or removed with respect to the total number of edges in the original graph. The values in parentheses next each dataset name indicate the test accuracy the original graph before any edits.
Cora (81.0)
CiteSeer (69.3)
PubMed (75.6)
Attack ratio
1%
3%
5%
1%
3%
5%
1%
3%
5%
DICE
80.820.4
80,3205
80.0ta.5
69.0zaa
68.5
18.5
15.1
74.5
73.5
PRBCD
80.620.
79.420.
78.7
68.5aa0.
67.4ao.
66.42n.
74.621.3
72.921.
70.921.
GIF
80.8e04
80.8mas
80.6ta4
69 69.8
69 89..7
69.3
75.4
75.3#10
75.2
Ours (DE)
81.0203
80.7
80. 81:3
69.1
69.27
68.8tns
75.621.0
75.2410
75.0211
Ours (Foo
80.920.4
80.9
80.61377
68.9106
69. 69.01105
68.620.
75.410.
74.921.
74.4
Ours (VL)
80.2s0.7
19.1
78.42a8
68.22as
66.72a.
65.1
73.2
71.221.
69.921.1
represents a form of global adversarial attack for the graph, aiming to reduce the performance of the entire graph.
Table 2 presents the adversarial attack performance of our methods, comparing it to previous influence- methods and other adversarial attack methods, DICE [34] and PRBCD [14], in the white-box scenario. As a result, the GIF shows poor performance, while our method with validation loss metric outperforms the others. An interesting observation is that, among the three metrics we tested, the validation loss-based attack is more effective than the tailored attack methods.
Explanation of the characteristics of benefi- cial edges We demonstrate the influence of edges connecting the node with the same la- bel (homophilic edge) and different labels (her- erophilic edge) GCN. Figure 5 presents dumbbell plot showing the mean influence of homophilic and heterophilic edges across six datasets, which include three homophilic graphs (Cora, CiteSeer, and PubMed), where edges tend to connect nodes with the same labels, and three heterophilic graphs (Chameleon, Ac- tor, and Squirrel), where edges tend to connect nodes with different labels.
Insertion Influence
Deletion Influence
Cora
Gtteseer
PubMedd
Chamaleon
Actor
Homealili edge
Squimal
-40004
-0.000
B1200
00622
-16 -16-1-13 -100m7
12:1 10-1
Figure 5: Mean influence of homophilic and het- erophilic edges on validation loss for edge insertion (left) and edge deletion (right). Each dumbbell con- nects the average influence of homophilic (light green) and heterophilic (dark green) edges across six datasets. A negative value indicates that the edge edit decreases the validation loss, thus im- proving the performance.
For both types of graphs, adding homophilic edges is more beneficial than adding het- erophilic ones. The opposite effect observed for edge deletion. These findings suggest that increasing a graph's homophily beneficial, which aligns with the homophilic nature of the tested GNNs.
Analysis of the effect of edge rewiring Our approach provides multiple analytical perspectives on existing rewiring strategies through various evaluation metrics. Specifically, we analyze BORF [26] and FoSR [19]. BORF alleviates over-squashing by inserting edges between nodes with negative curvature and mitigates over-smoothing by removing edges with positive curvature, while FoSR alleviates over-squashing by inserting edges that enlarge the spectral gap.
Figure presents the estimated influence of edges selected by BORF and FoSR from three measure- ment perspectives. Edge insertions chosen by both methods generally increase the over-squashing measurement, while edge deletions in BORF tend to increase the over-smoothing measurement, confirming that each method effectively targets its intended GNN challenge. Nevertheless, we also ob- serve unintended side effects: edge insertions often exacerbate over-smoothing, and neither insertions nor deletions consistently reduce validation loss. Mitigating these side effects could substantially enhance the overall effectiveness and reliability of edge rewiring methods.

---

Validation Loss (4)
Over-squashing (1)
Dirichlet Energy (1)
577
Delecion (+67 -33)
Deletion (+52 -48)
Deletoo (+65 -15)
Frequency
Frequeccy
Frequeccy
-0.0000
0.0000
40092
-8.060
6.2000
13 0000
L5000
Value
Value
Value
(a) BORF [26]
Validitiion
Over-squashing (t)
Dirichlet Energy (1)
Insection (+ 1+100-100
Insertion (-143 -571
Invection (+66 -150
Frequency
Frequency
Friqueccy
402000 40.0330
33000
83450
38000
00338
0.0100
80000
-15003
0.0000
23000 2,0000
Value
Value
Value
(b) FoSR [19]
Figure 6: Histograms of the estimated influence of edge insertions (blue) and deletions (red) selected by BORF [26] and FoSR [19], evaluated on a four-layer GCN trained on the Texas dataset. Influences are measured across validation loss, over-squashing, and over-smoothing. Arrows (4 () indicate the desired direction of each measurement (decrease/increase)
Related work
Originally introduced by Cook and Weisberg [12]. the influence function quantifies how removing a single training point would affect model parameters after retraining. Koh and Liang [21] adapted this concept to modern machine learning, providing efficient approximations of the influence on model predictions without the need for retraining. Influence functions have since been widely employed for model interpretability [17, 16], data valuation [8, 18), adversarial analysis [11, 10]. and unlearning [39, 37].
significant limitation of influence functions the assumption of strict convexity the loss function [4], which does not hold for many deep learning models. To overcome this, Teso et al. [31] approximate the Hessian using the Fisher information matrix, while Bac et al. [3] introduce proximal Bregman response function objective that relaxes this convexity requirement. Recent studies have further extended influence functions to diffusion models [25] and large language models [15, 9, 38). In graph settings, Chen et al. [7] and Wu et al. [35] apply influence functions to transductive node classification, and Song et al. [30] analyze group-level influence.
7 Conclusion
We introduce enhanced graph influence function that estimates the impact of edge perturbations model predictions in Graph Neural Nerworks. Unlike existing graph influence functions, our approach explicitly incorporates message propagation effects and relaxes the convexity assumption, enabling to be applied to commonly used non-convex GNNs. Additionally, we extend the framework to handle both edge deletions and insertions, broadening its applicability real- world graph rewiring tasks. Experimental results on various real-world datasets demonstrate that our method provides significantly more accurate estimates of influence than previous methods and enables effective improvements in key target measurements such as validation loss, squashin,, and over-smoothing. Despite these advances, our method has limitations. Although achieves high accuracy under multiple edge edits, performance gradually declines as the number of simultaneous edits grows, and scalability to deep GNNs remains challenging. Future work could address these issues to enhance the applicability of the method to complex graph learning tasks.
10

---

Acknowledgements
This work was supported by the National Research Foundation Korea (NRF) grant funded by the Korea (SSI) RBS-2024-00337955; RS-2023-00217286) and Institute of Information communications Technology Planning Evaluation (IITP) grant funded by the Korea govern- ment(MSIT) (RS-2024-00457882, National AI Research Lab Project; RS-2019-11191066 Artificial
Intelligence Graduate School Program(POSTEECH).
References
[1] Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization for machine learning linear time. Mach. Learn. Res., 18(():4148-4133 2017. 3.
[2] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006. 05200,
2020. 2020. 4.1
[3] Juhan Bae, Nathan Ng, Alston Lo, Marzyeh Ghassemi, and Roger B Grosse. If influecce functions are the answer, then what the question? Advances in Neural Information Processing Systems, 35:17953-17966 2022. 1, 2.2, 2.2, 1, 6, A, A.2
[4] Samyadeep Basu, Philip Pope, and Soheil Feizi. Influence functions deep learning are fragile. arXiv preprint arXiv:2006. 14651, 2020, 2.2, 6
[5] Samyadeep Basu, Xuchen You, and Soheil Feizi. second-order group influence functions for black-box predictions. In International Conference on Machine Learning, pages 715-724. PMLR, 2020. 4.2
[6] Chen Cai and Yusu Wang. A note over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020. 4.1
[7] Zizhang Chen, Peizhao Li, Hongfu Liu, and Pengyu Hong. Characterizing the influence of graph elements. arXiv preprint arXiv:2210.0744. 2022. 1, 4.2, 2a, 4.2, 4.2,
[8] Anshuman Chhabra, Peizhao Li, Prasant Mohapatra, and Hongfu Liu. what data benefits my classifier?" enhancing model performance and interpretability through influence- data selection. In The Twelfth International Conference on Learning Representations, 2024. 6
[9] Sang Keun Choe, Hwijeen Ahn, Juhan Bae, Kewen Zhao, Minsoo Kang, Youngseog Chung, Adithya Pratapa, Willie Neiswanger, Emma Strubell, Teruko Mitamura, et al. What is your data worth to gpt? lim-scale data valuation with influence functions. arXiv preprins vrXiv:2405.13954 2024. 6
[10] Gilad Cohen and Raja Giryes. Membership inference attack using self influence functions. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 4892-4901, 2024.
[11] Gilad Cohen, Guillermo Sapiro, and Raja Giryes. Detecting adversarial samples using influence functions and nearest neighbors. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 14453-14462, 2020.
[12] R. Dennis Cook and Sanford Weisberg. Residuals and influence in regression. New York, United States Chapman and Hall, 1982.
[13] Michaël Defferrard, Xavier Bresson, and Pieree Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016. 4.2, E
[14] Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 7637-7649. Curran Associates, Inc., 2021. 5, F

---

[15] Roger Grosse, Juhan Bae, Cem Anil, Nelson Elhage, Alex Tamkin, Amirhossein Tajdini, Benoit Steiner, Dustin Li, Esin Durmus, Ethan Perez, al. Studying large language model generalization with influence functions. arXiv preprint arXiv:2308. 03296, 2023. 6
[16] Han Guo, Nazneen Fatema Rajani, Peter Hase, Mohit Bansal, and Caiming Xiong. Fastif: Scalable influence functions for efficient model interpretation and debugging. arXiv preprint arXiv:2012.15781, 2020. 6
[17] Xiaochuang Han. Byron C Wallace, and Yulia Tsvetkov. Explaining black box predictions and unveiling data artifacts through influence functions. arXiv preprint SBtv:20005006676 2020.
[18) Yuzheng Hu, Pingbang Hu, Han Zhao, and Jiaqi Ma. Most influential subset selection: Chal- lenges, promises, and beyond. Advances in Neural Information Processing Systems, 37: 119778-119810, 2024. 6
[19] Kedar Karhadkar, Pradeep Kr. Banerjee. and Guido Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In The Eleventh International Conference on Learning Representations, 2023. 5, 6b, 6, F
[20] Thomas N Kipf and Max Welling. supervipe classification with graph convolutional 2016. 4.2
networks. arXiv preprint
[21] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pages 1885-1894, PMLR, 2017. 1, 2.1, 6, A
[22] Pang Wei W Koh, Kai-Siang Ang, Hubert Teo, and Percy S Liang. On the accuracy of influence functions for measuring group effects. Advances in neural information processing systems, 32, 2019. 4.2
[23] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018. 1, 1.1.
[24] Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang. Deeprobust: A pytorch library for adversarial attacks and defenses. arXiv preprint arXiv:2005.06/ 066499 2020.
[25] Bruno Mlodozeniec, Runa Eschenhagen, Juhan Bae, Alexander Immer, David Krueger, and Richard Tumnr. Influence functions for scalable data attribution in diffusion models, arXiv preprint arXiv:2410.133:
2024. 6
[26] Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning, pages 15956-25979, PMLR, 2023. 1. 5, 6a,
F
[27] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287 2020. 4.2
[28) Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2)scnab014, 2021. 4.2
[29] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3) 93, 2008. 4.2
[30] Jacyun Song, Sung Yub Kim, and Eunho Yang. Rge: A repulsive graph rectification for node classification via influence. In International Conference on Machine Learning, pages 32331-
32348. PMLR, 2023. 4.2, 6
[31] Stefano Teso, Andrea Bontempelli, Fausto Giunchiglia, and Andrea Passerini. Interactive label cleaning with example-basseeeeeee basedd explanations. Advances in Neural Information Processing Systems, 12:79766-22977, 2021. 1, 6
[32] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint 11554 2021. 2021. 4.1
12

---

[33] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903. 2017. 4.2,
[34] Marcin Waniek, Tomasz Michalak, Michael J Wooldridge, and Talal Rahwan. Hiding individuals and communities in social network. Nature Human Behaviour, 2(2):139-147,
2018. F.
[35] Jiancan Wu, Yi Yang, Yuchun Qian, Yongduo Sui, Xiang Wang, and Xiangnan He. Gif: A general graph unlearning strategy via influence function. In Proceedings of the ACM Web Conference 2023, pages 651-661, 2023. 1, 3, 4.2, 2a, 4.2, 4.2, 6
[36] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016. 4.2
[37] Yuanshun Yao, Xiaojun Xu, and Yang Liu. Large language model unlearning. Advances in Neural Information Processing Systems, 11111155225555555555 2024.
[38] Han Zhang. Zhuo Zhang, Yi Zhang, Yuanzhao Zhai, Hanyang Peng. Yu Lei, Yue Yu, Hui Wang. Bin Liang, Lin Gui, et al. Correcting large language model behavior via influence function. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 14477-14485, 2025. 6
[39] Yang Zhang, Zhiyu Hu, Yimeng Bai, Jiancan Wu, Qifan Wang, and Fuli Feng. Recommendation unlearning via influence function. ACM Transactions on Recommender Systems, 3(2):1-23, 2024.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We represented contributions in Section 3, experimental evidence in Section and applications in Section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discussed about our method limitations in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
We provided the detailed derivation of theoretical approaches in Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We write the training of GCN and information of major experiment setup in Appendix F.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification: We used public datasets such as Cora, and the code is provided in the supple- mentary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
httia//guuideee/eeeuuiiiit soiobiiiiin for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https: CoodeSubmiis
httpps.ccppublic//eec gomdeeSSSS ssi wwisnnolicyyiooeoooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We mentioned data split in Section 4 and syper-parametent Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We include statistical information, such as standard deviation and correlation coefficients, for the major experimental results in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our experiments are not affected with different compute resources and do not requires extensive time. We write down GPU types we used in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://ewr....cpppppceeeeeeeea/e
Answer: [Yes]
Justification:
We have fully adhered to the ethical guidelines.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is intended make an academic contribution rather than a social impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not pose risks of misuse or dual use.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the original papers for the datasets, models, and code in Section 4.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide the documentation of our code in the supplementary material.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the datasettcooeemmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve any crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve any crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: Our methods and applications in paper don't utilize any LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: httprrpps.cc//oofeeeneee//////// /LLM) for what should or should not be described.
20

---

A Derivation of the influence function
In this section, we derive the influence function for linear models [21]. as shown in Equation (3), and for neural networks [3], as shown in Equation (7). In particular, we reformulate the derivation by Bae al. [3] fit our setting.
A.1 Influence function for linear models
We begin by considering the re-weighted objective introduced in Equation (2):
I(0,e)= N
Σ (2.9)
y, + e
(15)
Assuming that the loss function L is twice continuously differentiable and that [(0, c) is strictly
convex in the optimal parameter 8t w. minimizing the objective satisfies the first-order optimality condition:
VoJ v)) 0.
(16)
To justify that the response function 8% y''y' is differentiable with respect to e, apply the Implicit Function Theorem to the optimality condition. The following conditions must be satisfied for the theorem to apply:
The function VeJ e) is continuously diffcrentiable in both 0 and This holds because J [0,e e) constructed as a linear combination of smooth loss functions, and its dependence is linear.
The optimality condition VoJ = O holds by definition, since 0% w' minimizes the objective J(0,e). e).
The Hessian (0, e), taken with respect to 0, is non-singular in neighborhood of O, J(0,e) e) is assumed to be strictly convex in 0.
Under these conditions, the Implicit Function Theorem ensures that 0% .y continuously differen- tiable with respect to e, and we differentiate Equation (16) using the chain rule:
dd 20 + VoLla' o
de (VoJ = V2J (0, (02.
vf we) 0.
(17)
de
Solving for the derivative yields:
d0 v'v
(00 e)) e)) VoL(z' oo (r).).))
(18)
de
Evaluating at e = 0. we obtain the influence function:
d0
- ' " 0*),
(19)
de
c=0
where : 0% v = the minimizer of original objective without perturbation.
21

---

A.2 Influence function for neural networks
Bae al. [3] demonstrated that the influence function using the generalized Gauss-Newton Hessian corresponds to that of the linearized form of the proximal Bregman response function objective":
in. v'' arg min
Σ
1 112 + 110 0-1l² + VVo((c ..)) 0, (20)
(2.3)
where h = go (2), and Lqund and liin. are the quadratic and linear approximations of the loss and model output, respectively:
1 2 -h2) [[ (h2 h%²). Cquad (1%)) = C(h2)h))))))))) + ng ( )
h/mm00 h Jago, (0- 0s),
(21)
an is the Jacobian of the model output with respect to the parameters.
where Jaga =
00 1==8.
We now expand the Bregman divergence term. First, using Liquna (h
((h
D Deuu (h 1 h = Laquaa (h (h Lyuaal (1 - Vig hg Lauaal (1 [n=
lin,
=((h)) Vng )T (n2 h + 212
2 (h2 n
L(h (h
h.%)
he
-(h vng T The h
(22)
Next, using lim
h J Ago, (0 0.):
1in.0 ( nn ((h ) T ng (0 0,) (0 0s) T JTge.
C(h Jngo, -0))
Vng ((1 0:) R (0 0.)
= (0 0,) Jheo nge, Vig C(h Jngo, (0 - 0,).
(23)
Since ii oe is the optimal solution, the gradient of the objective with respect is zero this point:
Ago, kg C(hh)))))) Junoo
( (fin,.r - -o,) + a' 0.) + VoL(x', 0.)..
E
(24)
Solving for Oi a ,e
we obtain:
oin.a' we O2 (Joo. H Jno. AI) VoL(x' 0,),
(25)
where J he.. HA, Jo = 1/ ((.))) Jhgo, Vig C(h Jngo, is the generalized Gauss-Newton
Hessian.
'For notational simplicity, we omit the label in expressions involving the loss function or the Bregman divergence, is clear from context.
22

---

B Gradient derivation for edge-edit PBRE
Similar to the derivation of the influence function for the PBRF objective in Appendix A.2, demonstrate that the influence function in Equation (10) corresponds to that of the lincarized form of the edge-edit PBRF objective:
iin
arg min
Σ
Din (ng
n.g.0.) ).....) 110 0gll
N
8
VEVaan
Σ e (VaC(1183) - voL(ng
T 0, * *.))) -
(26)
oE Visin
where Lqund and 0.9.0.tin denote the quadratic and linear approximations of the loss and the model output, respectively:
Squal (hg = C(hg.0,) + V ng. L(hg.0) ) Tnn.0 -gg00))
+
2 (n hg.0, 0, T Ag Che 9. ( - -,.
1g.0,lin
h + ng.00 0s),
(27)
a 20
where J Ag-90, =
is the Jacobian of the model output with respect to the parameters.
0=0,
We first expand the Bregman divergence term:
D cue (hg.0.it ng.0,) (quad(hi (1g.0.ling - Equna ( V ng Cqua (hg ( ng.00)
= C( + V Lg [hg hg
2 (ng.0 ng TV hg. C(h 11 1g.0,)
L(1 V hg L(h (1. h S.O.).
(28)
Using hg.8..in Jin ng.0. = "0,00 (0 0.). we substitute into the expression:
",
D Lmu (hg (,g. 1g Vng. L( T Jng 0.) (0 0.) TJ) 1O
V Ag og ( 0z)
Agg (T J (0 0z)
こ (0 0.) 1. V L ( Nn (0 02).
(29)
Since Oin. is the optimal parameter minimizing the objective, the derivative of the objective with respect to at f = ii, is zero:
0
1
Σ
T2000 20gg Jnng (Bin.e 02)) A(0iin.e 0.)
N
vC Vin
(VoL(nge)) -VoLin & k.01))
Σ
(30)
DE
Rearranging the terms, we obtain:
Cin 0g - GGG -1 Σ VoL(1 - -Voli +
(31)
VEVin
where G == EvEv.n J Jg V
Chg..0 )J og
is the generalized Gauss-Newton matrix.
0g 9. hg.
Taking the derivative with respect to e, we obtain:
20i
Oin 0g = G Σ
VoL(ng.))) - voL(hy - voL(ng-+ t.00).
lim -0
(32)
de
V
which confirms that the linearized edge-edit PBRF objective yields the same influence function as derived in Equation (10).
23

---

C Influence function for multiple edge edits
Problem setup for multiple edge edits In this section, we extend our influence function handle multiple edge edits. Let S denote the set of edges to be edited. We generalize the definition of A in Section the multi-edge case by defining
A Auo + (2 v) ES] 1)
The rege-reweighted graph is then given by G (V,E,A); where edges in S are reweighted. Setting e = 1/N implies that all edges S are deleted they exist, and inserted otherwise.
Parameter shift
Following Section 3, the edge-edit PBRF is defined
(2(1900) - -L -(1 $t,0 )
02 = arg min
Σ
De (n ,1000)) + 110 0,11+
E
N
DE Muni
V Vi
(33)
Following the same derivation steps as in Appendix B, the contribution of the parameter shift to the evaluation function is given by
00e
Σ (VoL(188)) VoL ( (1g=+()))))
Vos 9) de r=0
Vof(O,,
(34)
DEVun
where G Jo, ko, H,, Jno, AI. The only distinction from the single-edge lies in the redefinition of G 1/N which now denotes the graph with multiple edge edits.
Message propagation Unlike the single-edge case in Section 3, the perturbed adjacency matrix A influenced simultaneously by all edges in the set S. Consequently, the message propagation effect longer be attributed to single edge but must be decomposed into contributions from all edited edges. By applying the chain rule, the overall effect is expressed as summation over gradients with respect each reweighted edge:
0f(0.g))
0A
0f(O,g")
0f(0.g)) DA
Σ
+
0A
dc
OAc
Òc
OA
de
A 1m fl
cm0
(u.tes
1 10m c
10m0,.c00
@f 9)
0f(0,,
Σ
(2Ilfu, u/ -)
+
(35)
DAy
AAvu
(u.les
Unified influence function under multiple edge edits By substituting the parameter shift and message propagation terms into Equation (8) and linearizing around e = 0, the resulting influence under multiple edge edits can be approximated
50 -((0. ~
N Vo
Σ Vinu
(ng VoL (ng (1g+*
E (0)(000.)))))) +
01(0,)9)
Σ (unees
(36)
dAn
dA
24

---

D Description of LiSSA
To approximate the inverse of the generalized Gauss-Newton Hessian-vector product G G employ the LiSSA algorithm [1]. LiSSA estimates G G by iteratively accumulating powers of the residual matrix [I G) applied to the vector u. When the spectral radius of (I GG less than the inverse can be expressed using the Neumann series:
G G 11
(37)
Letting ((K) = =E u the iteration is defined recursively as:
y())) v, (k+1)
G))(()
(38)
In practice, we perform the update in Equation (38) until convergence. The iteration terminated early the update difference [|r((+11) [8)] falls below a predefined threshold, when the number of iterations reaches 10,000.
Since the spectral radius of G) not necessarily less than rescale the matrix ensure convergence. Specifically, we define a scaled matrix G, = G where >> Amax (Gax so that the spectral radius of (I G3) less than The inverse then computed via
G v G e,
and LiSSA is applied to approximate - v.
To avoid explicitly storing the generalized Gauss -ewttn matrix G, the matrix-vector product G) in Equation (38) is computed approximately using a Jacobian-based heuristic. Specifically, compute the Jacobian-vector product Joo ((a), apply the Hessian obtain HA, œ. and finally compute the transposed seobian-vecttr product G)(*) The.
E Experimental result on other datasets and GNNs
In this section, we present scatter plots for additional non-convex GNNs and datasets. Figure 7 shows the results for additional datasets, while Figure and Figure show the results for ChebNet [13] and GAT [33], respectively. Under these settings, our influence function accurately predicts the actual influence, consistently showing correlation above 0.8.
Chameleon
310
Squimal
CitSSoor
Publied
3.0
6.0
Attua Full
-25
60
-4.
Condation:
Comdasion: 1.00
Consacio:
Comsas
-55 -3 D0 EX
1/
-20 -3
03
(a) Deletion
Chameleon
Squirrl
Citeseer
Publid
Actuall Ie unnee
2.0
Actual Iee uance
Acusi
Comeatiin:
Eximuted Infuerce X10-
Estamated Infuance
Estimated Infuunce
Extimtted infunne
(b) Insertion
Figure 7: The scatter plot of predicted influence and actual influence on four-layer GCN, The x-axis represents the predicted influence and y-axis represents the actual influence, and the red-dotted line represents the perfect alignment.
25

---

Validation Loss
Over-squashing
Dirichlet Energy
8.0
Actual Influence
Actual Influence
Actual Influence
2.0
0.1
0.0
0.0
-2.0
2.0-
-0.1
-..0
Comrelaion: 0.94
Correlatio::
0.94
-0.3
Correlation: 0.93
-0
-6
-4 -2
-4
-0.3
-0.2 -0.1 0.0 0.1 0.2
Estimated Influencex10
Estimated Influencex10
Estimated Influence
(a) Deletion
x10->
Validation Loss
x10-
Over-squashing
Dirichlet Energy
Actual Influence
1.0
Actual Influence
Actual Influence
0.5
0.0
0.0
0.0
-0.5
-0.1
-1.5
-1.0
0.91
2.0
0.99
0.99
-1.0
-0.5
0.0 0.5
1.0
-2.0 ~1. -1.0 -0.5
0.0 0.5
1.0
-02
-0.1
0.0
0.1
0.2
Estimated Influencex10
Estimated Influencex10
Estimated Influence
(b) Insertion
Figure 8: The scatter plot of predicted influence and actual influence on two-layer ChebNet. The x-axis represents the predicted influence and y-axis represents the actual influence, and the red-dotted line represents the perfect alignment.
x10
Validation Loss
Over-squashing
6.6 x10 4 Dirichlet Energy
0.8
0.5
Actual Influence
3.0
Actual Influence
0.0
0.0
-0.2
-0.5
4.0
-0.8
Comelation: 0.86
Comelation:
0.95
-6.0
Correlation: 0.8
Estimated influence x10
Estimated influence
x10-3
Estimated Influence x10-
(a) Deletion
x10-1
Validation Loss
x10-1
Over-squashing
x10-1
Dirichlet Energy
2.0
2.0
1.0
Actual Influence
Actual Influence
4.0
0.5
2.0
0.0
0.0
-1.0
-10-
2.0
15
-20
Correlation 0.94
Comelation: 0.96
4.0
Comelation: 0.80
-2
Estimated x10-
Estimated Influence x10
Influence x10->
(b) Insertion
Figure 9: The scatter plot of predicted influence and actual influence on two-layer GAT. The x-axis represents the predicted influence and y-axis represents the actual influence, and the red-dotted line represents the perfect alignment.
F Experimental configuration
All experiments are conducted using NVIDIA GeForce RTX 3090, NVIDIA RTX A5000, and NVIDIA RTX A6000 GPUs. The experiments presented in the main text employ 4-layer GCN model as a representative non-convex GNN. To produce the results in Table and Table 2, we tune the model and training hyperparameters of a vanilla GCN over the following search space: learning rates (0.1, 0.03, 0.01), hidden dimensions (32, 64), and weight decays {10-3 - 10-1,
10-1,10-5 10-5, 10-6 10-7).
Training is performed for 2000 epochs using the SGD optimizer. For influence function computation,
26

---

we run the LiSSA algorithm for 10,000 iterations. The damping parameter À is selected from {0.1, 0.01, 0.001, 0.0001}. We randomly sample 10,000 candidate edges for both deletion and insertion, and estimate their influence. For Table 1, the number of edges to edit is determined based on validation accuracy. The experiments are repeated for 10 independent runs using different random seeds provided by the BernNet implementation.
BORF [26] and FoSR [19], used in the analysis of edge rewiring methods, are applied with the default settings from the original paper. The number of rewired edges reported in Figure 6 is aggregated over 10 runs, with a total of 200 edges inserted. Unlike FoSR, which performs only edge insertions, BORF also considers edge deletions. To improve visualization, we reduce the number of edge deletions, as the influence scores for insertions exhibit long- tailed distribution, making it difficult to display them on the same scale as deletions. Accordingly, edge deletions are performed with 120, 100, and 100 edges, respectively.
For the adversarial attack experiments in Table 2, DICE [34] and PRBCD [14] are implemented by modifying the PyTorch-based DeepRobust library [24), while maintaining its default settings. For our method, we consider both edge insertions and deletions, and select the operations with the highest influence scores for validation loss, and the lowest influence scores for over-squashing and Dirichlet energy.
27


Reviews:
[{"review_id": "lgSUpIuEov", "reviewer": "Reviewer_CafE", "summary": "This paper builds one new kind of influence function for graph neural networks (GNNs). Old influence work needs the loss to be strictly convex and can only tell what happens if we delete one edge. The authors drop the convex need and let the formula work for deep, non-convex GNNs. They also treat both deleting and adding an edge as the same small change on edge weight.\n\nTheir “edge-edit proximal Bregman response” splits the total effect of one edge into two parts: (1) how model parameters move, (2) how message passing route changes. They use LiSSA to solve the inverse Hessian so the cost is low.\n\nOn five citation graphs and three GNN models, the predicted influence has about 0.9 Pearson link with the real effect, much better than past methods. They show three uses: cleaning or re-wiring graphs to improve accuracy, finding worst edges to attack the model fast, and explaining which edges help or hurt.", "questions": "1. Scale proof – Please run on one large OGB graph (e.g., ogbn-products). Report wall-time, peak GPU RAM, and Pearson r. \n\n2. Stronger baselines – Add recent influence / attack tools (e.g., NID-Edge, I-F) and PGD multi-edge attack. \n\n3. Multi-edge effect – Real edits often change dozens of edges. Can your first-order formula compose influences linearly? Please test on random k-edge batches (k = 5, 10, 20).\n\n4. Reproducibility tips – Provide heuristic for choosing LiSSA depth and damping λ based on dataset size and model depth.", "limitations": "1. Scale risk. Need one large OGB graph case with wall-time and GPU RAM; without this, “scalable” claim is weak.\n\n2. Baseline gap. Please compare with newer influence / attack tools such as NID-Edge, I-F, and multi-edge PGD.\n\n3. Multi-edge reality. Real users edit many edges at once. Show whether first-order scores add up linearly for k = 5-20 edges.\n\n4. Reproducibility. Give a thumb-rule for LiSSA depth and damping λ that changes with |V|, |E|, and model depth. This will help others copy the method.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. Authors drop the strict-convexity need and design one unified influence rule that works for deep, non-convex GNN and treats edge delete + add in the same frame. This fresh idea fills a clear blank in influence study.\n\n2. On five citation graphs and three GNN types, predicted-vs-real influence hits ≈ 0.9 Pearson, and three demos (graph repair, attack, explain) show real help; LiSSA keeps cost low.\n\nWeakness\n\n1. Quality & Scope – Paper studies only first-order, single-edge change. Real tasks often edit many edges; LiSSA inverse still heavy on huge graphs (e.g., OGB). Thus “scalable” claim not fully proved.\n\n2. Limited baselines and ablation – The study mainly compares with GIF and simple gradient scores. It lacks newer influence/attack tools such as NID or I-F. Also, no ablation on LiSSA depth, Hessian-free vs. exact inverse, or removing the propagation term, so we cannot see which design really drives the gains.", "was_revised": true, "final_justification": "The authors show a large-graph case (ogbn-products) with subgraph mini-batch, report clear wall-time, peak GPU, and Pearson=0.94. Ablations are helpful: LiSSA depth plateaus around 500 iterations; removing propagation term hurts a lot. Multi-edge extension is explained and tested.", "rebuttal": "We sincerely thank the reviewer for their thorough review and valuable feedback on our submission. We particularly appreciate the reviewer highlighting the novelty of our unified influence function and its strong empirical validation. Below, we carefully address the concerns regarding scalability, baseline comparisons, and ablations. We hope our responses effectively address these points and warmly welcome any further feedback from the reviewer.\n\n**[W1, Q1, L1] LiSSA inverse still heavy on huge graphs (e.g., OGB). Thus “scalable” claim not fully proved. Please run on one large OGB graph (e.g., ogbn-products). Report wall-time, peak GPU RAM, and Pearson r.**\n\nWe would like to clarify that we do not claim scalability in our manuscript. In fact, we state in our conclusion that future research could focus to enhance the method’s applicability to larger and more complex graph learning tasks. Nevertheless, we are grateful for the reviewer's insightful comment regarding scalability, and following this suggestion, we have conducted additional experiments on the large-scale ogbn-products dataset (with 2,449,029 nodes) to empirically verify the applicability of our method to large graphs.\n\nDue to memory constraints inherent in GNNs when handling such large-scale graphs, we employed mini-batch training by dividing the original graph into ten subgraphs, following the approach used in [1]. Below, we report detailed experimental results:\n\n- **[GPU used]** NVIDIA RTX A6000 (48 GB memory)\n- **[Wall-time]**\n  - LiSSA preprocessing: 258.3 seconds\n  - Influence function calculation per edge (excluding LiSSA preprocessing): 26.4 seconds\n  - Note: LiSSA preprocessing is required only once, after which calculating the influence function for multiple edges significantly reduces overhead (total average 26.7 seconds per edge when computing 1000 edges).\n- **[Peak GPU memory consumption]** 31,700 MB\n- **[Pearson correlation]** 0.94\n\nThese results suggest that our proposed method can be extended to large-scale graphs.\n\n**[W2, Q2, L2] The study mainly compares with GIF and simple gradient scores. It lacks newer influence/attack tools such as NID, I-F and PGD multi-edge attack.**\n\nRegarding the concern about comparison with newer influence/attack methods, we have now included PGD [2] in our adversarial-attack comparisons using the same perturbation budgets (1%, 3%, 5%) as those used in the main paper. The updated results are shown below:\n\n||Cora(81.0)|||CiteSeer(69.3)|||PubMed(75.6)|||\n|-|-|-|-|-|-|-|-|-|-|\n|Attack|1%|3%|5%|1%|3%|5%|1%|3%|5%|\n|PGD|80.9±0.4|80.8±0.4|80.5±0.9|69.2±0.4|69.0±0.5|69.0±0.5|75.5±1.0|75.2±0.9|75.1±1.0|\n|PRBCD|80.6±0.5|79.4±0.5|78.7±0.9|68.5±0.5|67.4±0.8|66.4±0.5|74.6±1.5|72.9±1.8|70.9±1.7|\n|Ours(VL)|**80.2±0.7**|**79.1±0.7**|**78.4±0.8**|**68.2±0.5**|**66.7±0.6**|**65.1±0.9**|**73.2±1.4**|**71.2±1.5**|**69.9±1.1**|\n\nOur influence-function-based method consistently outperforms PGD across all datasets and perturbation budgets. We emphasize that adversarial attacks represent only one possible application of our influence functions, and even with our simple strategy of selecting the top-$k$ edges by influence function magnitude, our method consistently outperforms the compared baselines. This finding aligns with the results from PRBCD [3], a gradient-based attack method similar to PGD.\n\nWe were unable to identify the methods \"NID\" and \"I-F\" mentioned by the reviewer. We would appreciate it if the reviewer could provide references for these methods.\n\n**[W2] No ablation on LiSSA depth, Hessian-free vs. exact inverse, or removing the propagation term, so we cannot see which design really drives the gains.**\n\nRegarding the ablations requested, we conducted experiments on LiSSA depth and the propagation term. Due to computational constraints, performing an ablation with the exact inverse of the Hessian (which has dimensions $p\\times p,$ with $p$ being the number of parameters) was infeasible. Thus, we could not include a comparison with the exact inverse.\n\n- **[Ablation on LiSSA Depth]**\n\nWe measured the Pearson correlation between the estimated influence and the actual influence (obtained via retraining) across varying numbers of LiSSA iterations. The results are summarized in the following table:\n\n|LiSSA iterations|Cora|CiteSeer|PubMed|\n|-|-|-|-|\n|10|-0.16|-0.04|0.76|\n|100|0.16|0.04|0.93|\n|500|0.91|0.94|0.94|\n|1000|0.91|0.94|0.94|\n|10000|0.91|0.94|0.94|\n|Time per iteration|11.8ms|18.0ms|19.5ms|\n\nThese results indicate that the correlation plateaus at around 500 iterations, suggesting that approximately 500 iterations are sufficient to obtain accurate influence estimates. Additionally, each LiSSA iteration is computationally inexpensive (around 10s total for 500 iterations), making this overhead negligible.\n\n- **[Ablation on Propagation Term]**\n\nWe measured the Pearson correlation between the estimated influence and the actual influence after removing the propagation term. Results are shown below:\n\n||Cora|CiteSeer|PubMed|\n|-|-|-|-|\n|w/o propagation|0.00|0.45|0.69|\n|Ours|0.91|0.94|0.94|\n\nRemoving the propagation term causes a significant drop in correlation, clearly demonstrating that this term is essential for accurately estimating the influence function.\n\n**[W1, Q3, L3] Real edits often change dozens of edges. Can your first-order formula compose influences linearly? Please test on random k-edge batches (k = 5, 10, 20).**\n\nUnlike influence functions for non-relational data, graph-based influence functions typically are non-additive, meaning that summing single-edge influences does not directly yield the influence of multiple edge edits [4]. Nevertheless, our formulation naturally extends to multi-edge edits with minimal modifications to Equation (12):\n- **[Retraining term modification]** We redefine $h_v^{\\mathcal{G}^{-1/N}}$ as the node representation after all selected edges are edited.\n- **[Message passing term modification]** We modify Equation (12) by summing over all perturbed edges, i.e., we introduce $\\sum_{(u,v)}$ in the second term to account for multiple edge edits.\n\nTo empirically validate this approach, we measured the Pearson correlation between the actual influence and our estimated influence across different sizes of randomly inserted edges (inserting $k$ edges simultaneously) on the Cora dataset:\n|k|1|5|10|20|50|100|1000|\n|-|-|-|-|-|-|-|-|\n|Correlation|0.91|0.88|0.91|0.93|0.88|0.86|0.79|\n\nThese results demonstrate that our influence estimates remain highly accurate for a wide range of $k$. Only at a very large scale $k = 1,000$ does the correlation drop slightly, which we attribute to first-order approximation errors caused by significant parameter changes from editing a large number of edges simultaneously.\n\n**[Q4, L4] Reproducibility tips – Provide heuristic for choosing LiSSA depth and damping λ based on dataset size and model depth.**\n\n- **[LiSSA depth]** We use a convergence-based heuristic, where at each iteration, we compute the $l_2$-norm of the difference between the current and previous inverse-Hessian estimates. The iteration stops when this difference falls below $10^{-7}$. We set the maximum depth to $10,000$.\n- **[Damping $\\lambda$]** A fixed damping value of $\\lambda=0.01$ consistently provided strong performance across nearly all evaluated datasets.\n\n\n[1] Li, Guohao, et al. \"Deepergcn: All you need to train deeper gcns.\" arXiv preprint arXiv 2020.  \n[2] Xu, Kaidi, et al. \"Topology attack and defense for graph neural networks: An optimization perspective.\" IJCAI 2019.  \n[3] Geisler, Simon, et al. \"Robustness of graph neural networks at scale.\" NeurIPS 2021.  \n[4] Song, Jaeyun, SungYub Kim, and Eunho Yang. \"Rge: A repulsive graph rectification for node classification via influence.\" ICML 2023."}, {"review_id": "xIT9n16ToD", "reviewer": "Reviewer_ofas", "summary": "This work proposes a method for estimating the influence functions of edge edits in graphs. Specifically, the authors introduce a graph-tailored proximal Bregman response function that supports both edge insertion and deletion while accounting for their effects on parameter shifts and message propagation. Experiments on three graph datasets demonstrate that the proposed method effectively estimates influence functions. By selectively adding or removing edges based on these estimates, the method can either enhance predictive performance or degrade it in adversarial scenarios.", "questions": "Do the changes in the evaluation function caused by modifications in the message propagation path still persist if only the training graph is edited, but the test graph remains unchanged?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Estimating the influence function of edge edits is a valuable and underexplored problem with promising practical applications.\n\n2. The paper proposes a practical and effective solution for estimating influence functions tailored to graph data. This is supported by experimental evaluations, which show a small error between the estimated influence scores and ground truth.\n\n3. The proposed method is backed by solid theoretical analysis.\n\nWeaknesses:\n\n1. The method is evaluated on three datasets—Cora, Citeseer, and PubMed—which are all homophilous graphs, where most edges connect nodes of the same class. Since the paper also investigates the influence of inserting or deleting homophilous versus heterophilous edges, it would be more convincing and comprehensive to include evaluations on heterophilous graphs or graphs with lower homophily.\n\n2. In Table 1, the results are based on models trained and evaluated on edge-edited graphs. It is unclear whether the comparisons remain fair if the test graphs are edited in different ways across methods. Clarifying this setup would improve the rigor of the evaluation. Also, is it appropriate to edit the test graph?\n\n3. The improvements reported in Table 1 do not appear to be statistically significant compared to the baselines. All methods show relatively similar performance, making it difficult to draw strong conclusions about how over-squashing or over-smoothing affects model performance. This may be due to the chosen datasets being relatively insensitive to edge edits. Again, incorporating a more diverse set of datasets could help better assess the method’s impact.", "was_revised": true, "final_justification": "My concerns have been addressed, and I maintained my positive evaluation.", "rebuttal": "We sincerely thank the reviewer for their thorough review and valuable feedback on our submission. We especially appreciate the reviewer recognizing the theoretical rigor, and practical effectiveness of our method for estimating influence functions in graph data. Below, we provide detailed responses addressing the weaknesses and questions raised. We hope our responses effectively clarify these points and look forward to any additional comments from the reviewer.\n\n**[W1] The method is evaluated on three datasets—Cora, Citeseer, and PubMed—which are all homophilous graphs, where most edges connect nodes of the same class. Since the paper also investigates the influence of inserting or deleting homophilous versus heterophilous edges, it would be more convincing and comprehensive to include evaluations on heterophilous graphs or graphs with lower homophily.**\n\nWe report the correlation coefficients and scatter plots for two heterophilic datasets in Figure 6 of Appendix D. The correlations range from 0.88 to 0.99, confirming that our influence function remains accurate even under lower homophily. Due to the inability to embed images directly in the rebuttal, we respectfully direct the reviewer to Appendix D for detailed plots.\n\nAdditionally, we evaluated test accuracy after editing edges selected to reduce validation loss on these heterophilic graphs. The summarized results in the table below suggest that our edge-editing method for reducing validation loss also effectively improves test accuracy on heterophilic graphs:\n\n||Chameleon|Actor|\n|-|-|-|\n|GCN|52.2±3.9|32.4±2.1|\n|+Ours(VL)|53.3±4.2|34.9±1.4|\n\n**[W3] The improvements reported in Table 1 do not appear to be statistically significant compared to the baselines. All methods show relatively similar performance, making it difficult to draw strong conclusions about how over-squashing or over-smoothing affects model performance. This may be due to the chosen datasets being relatively insensitive to edge edits. Again, incorporating a more diverse set of datasets could help better assess the method’s impact.**\n\nWe acknowledge the reviewer’s point regarding the modest improvements observed in Table 1, and agree these results alone provide limited evidence for our claims about over-smoothing and over-squashing.\n\nTo further substantiate our claim, we direct the reviewer’s attention to Table 2 in our paper, which presents adversarial edge edits selected using our influence function. The variant designed to maximize validation loss consistently results in a significant accuracy drop: 2.6% on Cora, 4.2% on CiteSeer, and 5.7% on PubMed. In contrast, the variants targeting the over-smoothing and over-squashing metrics induce substantially smaller or negligible performance degradation. This clear difference supports our original claim that adversely affecting these structural properties does not necessarily translate into impaired predictive performance.\n\nMoreover, we provide additional evaluation results on two more diverse datasets (Chameleon and Actor) in response to the reviewer's earlier point ([W1]). These datasets further confirm the effectiveness and general applicability of our method.\n\n\n**[W2, Q1] In Table 1, the results are based on models trained and evaluated on edge-edited graphs. It is unclear whether the comparisons remain fair if the test graphs are edited in different ways across methods. Clarifying this setup would improve the rigor of the evaluation. Also, is it appropriate to edit the test graph? Do the changes in the evaluation function caused by modifications in the message propagation path still persist if only the training graph is edited, but the test graph remains unchanged?**\n\nWe believe the comparisons in Table 1 remain fair due to the transductive node classification setup used in our paper. In transductive node classification, there is only one graph, and thus the training and test graphs are not separate. Instead, nodes within the graph are divided into training, validation, and test sets. During training, only training-node features are provided, along with all edges, including those connected to validation or test nodes. This setting is widely adopted in node classification [1,2,3]. Our method edits the edges provided at the training stage, which we believe ensures fairness. This follows the same protocol as previous edge-rewiring methods [4,5]. Consequently, perturbations in the message-propagation path affect both training and test nodes.\n\n\n[1] Kipf, Thomas N., and Max Welling. \"Semi-supervised classification with graph convolutional networks.\" ICLR 2017.  \n[2] Veličković, Petar, et al. \"Graph attention networks.\" ICLR 2018.  \n[3] Chien, Eli, et al. \"Adaptive universal generalized pagerank graph neural network.\" ICLR 2021.  \n[4] Nguyen, Khang, et al. \"Revisiting over-smoothing and over-squashing using ollivier-ricci curvature.\" ICML 2023.  \n[5] Karhadkar, Kedar, Pradeep Kr Banerjee, and Guido Montúfar. \"FoSR: First-order spectral rewiring for addressing oversquashing in GNNs.\" ICLR 2023."}, {"review_id": "NtyQP3nesx", "reviewer": "Reviewer_XMsy", "summary": "This paper, in general, presents their own method of predicting the edge influence in GNNs. What's so interesting about their work, in my opinion, is that they greatly relaxed the assumption we put on the GNNs to be analyzed, from convex to non-convex.\n\nTheir method can evaluate the influence of edges towards many different \"objectives\", such as measuring towards the over-squashing, over-smoothing, or the standard validation loss (such as cross-entropy). They are able to detect some \"beneficial\" edges that contributes to the phenomenon, and some \"harmful\" edges that avoid or break such phenomenon.\n\nThe capability of their method is also shown in downstream experiments such as adversarial attacks.", "questions": "1. I have some questions on the exact scalability and efficiency of your method. If, for example, I am planning to apply such method on a very large graph, say, social network graphs that typically include at least tens of thousands of nodes, do you think it will be problematic?\n\n2. The downstream tasks you proposed are interesting, but I really want to see if there are more applications. Say, do you think your method can be useful in some graph-based causal analysis studies, given that you relaxed the assumptions to non-convex graphs?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Their work has very clearly explained theoretical proof, and provided justification in all decisions they made. Preciseness is their greatest strength. The work is carefully-done in general, with obvious novelty, and the message is clearly delivered.\nAnd also, they provided their code and the code is well-documented. I think that helps explain a lot of the implementation details that are probably not sufficiently discussed in the main text.\n\nThe weaknesses are relatively subtle, but still there.\nAlthough the technical part is carefully written, and roughly justified, we did not see much mathematical proof on some of the decisions, such as that the alternative over-squashing measurement can really replace the a gradient-based metric.\n\nAlso, some of the wordings really worth re-considering, such as that \"beneficial\" and \"harmful\" are really counter-intuitive. You will understand their meaning after carefully reading their paper though.\n\nAll in all, I think this paper is above the acceptance line, but the writing (and proofing) can be improved somehow.", "was_revised": true, "final_justification": "The authors addressed all my concerns with care, and beyond. The quality of their work is slightly higher than I expected, so I am willing to increase my score a little bit.", "rebuttal": "We sincerely thank the reviewer for their thorough and positive review, as well as their encouraging comments on the clarity, novelty, and careful implementation of our work. We particularly appreciate the recognition of our detailed theoretical explanations and well-documented code. Below, we address the concerns and valuable suggestions raised, and we look forward to any further feedback from the reviewer.\n\n**[W1] We did not see much mathematical proof on some of the decisions, such as that the alternative over-squashing measurement can really replace the a gradient-based metric.**\n\nWe acknowledge the reviewer's concern regarding the lack of a mathematical proof for our alternative over-squashing measurement. While we agree that a rigorous mathematical justification demonstrating the replaceability of the two metrics would be ideal, conducting such a formal analysis is not straightforward. As an alternative, we provide empirical evidence demonstrating that our proposed metric is highly correlated with the gradient-based measure and significantly more computationally efficient. For every node in each dataset, we computed both metrics, reporting the Pearson correlation coefficients and runtimes below:\n\n||Cora|CiteSeer|PubMed|\n|-|-|-|-|\n|Grad runtime|27.6s|26.0s|614.8s|\n|Ours runtime|3.6s|3.9s|27.6s|\n|Correlation|0.74|0.87|0.67|\n\nOur alternative measure achieves strong correlations (0.67 to 0.87) with the gradient-based metric while offering substantial runtime improvements (6 to 20 times faster). We emphasize that these two metrics measure the same underlying concept, quantifying how much a node’s representation changes when the features of the most distant node in its receptive field are perturbed.\n\n**[W2] Some of the wordings really worth re-considering, such as that \"beneficial\" and \"harmful\" are really counter-intuitive.**\n\nWe agree with the reviewer that the terms \"beneficial\" edge and \"harmful\" edge can be counter-intuitive. To address this issue, we will revise our terminology to explicitly reflect both the operation performed (removal/insertion) and its impact on the evaluation metric, adopting terms such as \"beneficial edge removal\" or \"metric-increasing edge removal.\" We believe this revised terminology will resolve two key sources of confusion: (1) it explicitly clarifies that the terms refer specifically to the effect observed after an edge operation, and (2) it avoids the confusion caused by the opposite direction of impact between the edge's original role and the operation being performed. These changes should intuitively clarify the relationship between edge edits and their effects on the evaluation metric.\n\n\n**[Q1] I have some questions on the exact scalability and efficiency of your method. If, for example, I am planning to apply such method on a very large graph, say, social network graphs that typically include at least tens of thousands of nodes, do you think it will be problematic?**\n\nWe do not anticipate significant issues applying our method to large graphs containing tens of thousands of nodes. In fact, our experiments include evaluations on the PubMed dataset [1], which contains 19,717 nodes. We provide the GPU memory consumption and running time on this dataset:\n\n- **[Used GPU]** NVIDIA A6000 (48GB)\n- **[GPU memory consumption]** 1,386MB\n- **[Running time]** 41.04 seconds for calculating the influence of 1,000 edge edits (LiSSA calculation: 15.28 seconds, Remaining calculation: 25.76 seconds).\n\nThese results confirm that our method is practical and efficient for graphs at this scale, demonstrating clear applicability to large-scale scenarios.\n\nFurthermore, our method can also scale to very large graphs by employing mini-batch training, which divides the original graph into ten subgraphs following the approach used in [2]. We provide the GPU memory consumption, running time, and Pearson correlation on ogbn-products (2,449,029 nodes) [3]:\n\n- **[Used GPU]** NVIDIA A6000 (48GB)\n- **[GPU memory consumption]** 31,700 MB\n- **[Running time]**\n  - LiSSA preprocessing: 258.3 seconds\n  - Influence function calculation per edge (excluding LiSSA preprocessing): 26.4 seconds\n  - Note: LiSSA preprocessing is required only once, after which calculating the influence function for multiple edges significantly reduces overhead (total average 26.7 seconds per edge when computing 1000 edges).\n- **[Pearson correlation]** 0.94\n\n\n**[Q2] The downstream tasks you proposed are interesting, but I really want to see if there are more applications. Say, do you think your method can be useful in some graph-based causal analysis studies, given that you relaxed the assumptions to non-convex graphs?**\n\nYes, our influence function can be applied to various tasks involving non-convex graph neural networks, including graph-based causal analysis. Specifically, by setting the evaluation function as the loss associated with a single node, our method can identify which edges most strongly influence the model's prediction for that node [4]. Therefore, it is well-suited for causal analyses aimed at understanding the impact of specific edges on node-level predictions. However, as we are not experts in causality, a more rigorous and formal analysis would be required to validate this application thoroughly. We believe this represents an exciting direction for future research.\n\nMoreover, by selecting a fairness metric as the evaluation function, our framework can help identify edges whose removal would enhance fairness in model predictions [5]. Additionally, since our approach quantifies the extent of model parameter changes due to edge edits, it is applicable to model unlearning scenarios that require the removal of specific relationships [6]. We believe these applications highlight exciting opportunities for further research leveraging our method.\n\n[1] Sen, Prithviraj, et al. \"Collective classification in network data.\" AI magazine 29.3 2008.  \n[2] Li, Guohao, et al. \"Deepergcn: All you need to train deeper gcns.\" arXiv preprint arXiv 2020.  \n[3] Hu, Weihua, et al. \"Open graph benchmark: Datasets for machine learning on graphs.\" NeurIPS 2020.  \n[4] Koh, Pang Wei, and Percy Liang. \"Understanding black-box predictions via influence functions.\" ICML 2017.  \n[5] Chhabra, Anshuman, et al. \"\" What Data Benefits My Classifier?\" Enhancing Model Performance and Interpretability through Influence-Based Data Selection.\" ICLR 2024.  \n[6] Zhang, Yang, et al. \"Recommendation unlearning via influence function.\" ACM Transactions on Recommender Systems 2024."}, {"review_id": "wgL1JZt5yI", "reviewer": "Reviewer_q9wj", "summary": "The paper proposes a novel influence-function framework based on an approximate Proximal Bregman response function for edge edits in non-convex graph neural networks (GNNs), covering both edge deletions and insertions. It decomposes the effect of an edge edit into parameter-shift and message-propagation components. Extensive experiments on multiple datasets and GNN architectures show that predicted effects correlate highly with actual effects on validation loss, over-squashing, and Dirichlet energy, significantly outperforming previous GIF methods. Finally, the paper demonstrates practical applications of this influence function in analyzing graph rewiring strategies, constructing adversarial attacks, and studying the impact of homophilic versus heterophilic edges", "questions": "1. This paper only selects one baseline to compare, which is not convincing enough. Since there are other related baselines, such as [1].\n2. Why does the legend in the Figures refer to Dirichlet Energy instead of the term \"over-smoothing\" used in the main text? Could the authors clarify the reasoning behind this terminology choice and whether these two are being used interchangeably or have distinct implications in the analysis?\n3. Does assigning values of |ϵ| other than 1/N carry any practical or theoretical significance in this study? Can the authors elaborate on whether other values of |ϵ| were considered, and if so, what their implications would be for influence estimation accuracy or interpretability?\n4. In Section 4.1, is the definition of an \"L-layer neighborhood\" based on shortest path distance? The term \"L-layer\" is introduced in Section 4.1 when defining neighborhood influence. For clarity, could the authors confirm whether this refers to the set of nodes within shortest-path distance L from the target node, or if another graph-theoretic interpretation is used?\n\n[1] Gong L, Cheng Q. Exploiting edge features for graph neural networks[C]//Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2019: 9211-9219.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. This paper introduces an influence-function framework based on the PBRF, which relaxes convexity assumptions and, for the first time, systematically supports both edge deletions and insertions in non-convex GNNs.\n2. Decomposes the impact of an edge edit into parameter shift and message propagation components, and empirically demonstrates their low correlation.\n3. This paper conducts extensive experiments across multiple benchmark datasets and diverse GNN architectures, further validates practical value via downstream graph editing for improved accuracy, analysis of rewiring strategies, adversarial attack construction, and homophilic/heterophilic edge impact studies.\n\nWeaknesses\n1. The experiment is not convincing enough. This paper only selects one baseline to compare, however, there are other related baselines, such as [1].\n2. The paper proposes using the LiSSA algorithm to approximate the inverse Hessian–vector product, but does not specify any details regarding the number of iterations, step-size selection, or convergence guarantees. Furthermore, there is no quantitative assessment of how the LiSSA approximation error propagates into the final influence estimation. \n3. The current framework addresses only single-edge edits. In practical scenarios, multiple edges may be modified simultaneously, leading to potentially significant nonlinear coupling effects. \n4. The influence function derivation relies solely on a first-order Taylor approximation and does not account for higher-order or cross-term effects. The manuscript should either provide a theoretical justification for truncating at first order, demonstrating that higher-order contributions are indeed negligible, or include an empirical analysis quantifying the error introduced by ignoring these terms.\n5. The last term in Equation (9), which measures the difference in node-level loss between the original and edge-edited graphs, is presented in a form that is difficult to interpret. \n\n[1] Gong L, Cheng Q. Exploiting edge features for graph neural networks[C]//Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2019: 9211-9219.", "was_revised": true, "final_justification": "The specified details of experiments and generalization ability in practical scenarios are discussed in the authors' response.", "rebuttal": "We sincerely thank the reviewer for their thorough and constructive feedback. We particularly appreciate the reviewer recognizing the contributions of our influence-function framework, including relaxing convexity assumptions, handling both edge deletions and insertions, and conducting extensive empirical validations across various scenarios. We have carefully read all the comments and have addressed each concern and question in detail below. If there are any further questions or suggestions, we would be happy to respond.\n\n**[W1, Q1] The experiment is not convincing enough. This paper only selects one baseline to compare, however, there are other related baselines, such as [1].**\n\nWe sincerely appreciate the suggestion regarding additional baselines. We have carefully reviewed the paper suggested by the reviewer. Our understanding is that the objective of [1] is to propose a GNN architecture designed to effectively exploit multi-dimensional edge features. We think this objective differs from that of our paper, which introduces an influence function tailored specifically for node classification tasks. If there is a connection or relevance between [1] and our work that we have overlooked, we would sincerely appreciate it if the reviewer could let us know.\n\nTo the best of our knowledge, the only existing baseline directly addressing influence functions on graphs is GIF [2, 3], which we have extensively compared against in our paper.\n\n**[W2] The paper proposes using the LiSSA algorithm, but does not specify any details regarding the number of iterations, step-size selection, or convergence guarantees. Furthermore, there is no assessment of how the LiSSA approximation error propagates into the final influence estimation.**\n\n- **[Hyperparameter details for LiSSA]** We respectfully refer the reviewer to Appendix F (lines 509–510), where we describe the hyperparameters used for the LiSSA algorithm. Specifically, we run LiSSA for $10,000$ iterations, and select the damping parameter $\\lambda$ from the set $\\\\{0.1, 0.01, 0.001, 0.0001\\\\}$. \n- **[LiSSA convergence details]** Details on how we ensure the convergence of the LiSSA algorithm are provided in Appendix C. In brief, convergence holds when the spectral radius of $\\mathbf{I}-\\mathbf{G}$ is less than 1. To enforce this, we scale the matrix as $\\mathbf{G}_s=\\frac{1}{s}\\mathbf{G}$ and increment $s$ when divergence is observed. We respectfully refer the reviewer to Appendix C for a full description.\n- **[Quantitative analysis on LiSSA approximation errors]** To quantitatively assess how the LiSSA approximation error propagates into the final influence estimation, we measured the Pearson correlation between the estimated influence (via LiSSA) and the actual influence (via retraining) across varying LiSSA iteration counts. The results are summarized below:\n\n|LiSSA_iter|Cora|CiteSeer|PubMed|\n|-|-|-|-|\n|10|-0.16|-0.04|0.76|\n|100|0.16|0.04|0.93|\n|500|0.91|0.94|0.94|\n|1000|0.91|0.94|0.94|\n|10000|0.91|0.94|0.94|\n|Time per iteration|11.8ms|18.0ms|19.5ms|\n\nThese results demonstrate that low iteration counts (10 or 100) produce poor influence estimates due to high approximation errors. However, with 500 iterations or more, LiSSA provides accurate and stable influence estimations.\n\n**[W3] The current framework addresses only single-edge edits. In practical scenarios, multiple edges may be modified simultaneously, leading to potentially significant nonlinear coupling effects.**\n\nWe agree with the reviewer that addressing multiple-edge edits is practically important and worth clarifying. Our framework can be extended to the multiple-edge setting with only a minor change to Equation (12). \n- **[Retraining term modification]** We redefine $h_v^{\\mathcal{G}^{-1/N}}$ as the representation of node $v$ in the graph where all selected edges have been edited.  \n- **[Message passing term modification]** In the second term of Equation (12), we introduce a summation over the perturbed edge set, i.e., we prepend $\\sum_{(u,v)}$ to account for every edited edge.\n\nWe evaluate the Pearson correlation between the actual influence (obtained by retraining) and our estimated influence when simultaneously inserting $k$ edges on the Cora dataset:\n|k|1|5|10|20|50|100|1000|\n|-|-|-|-|-|-|-|-|\n|Correlation|0.91|0.88|0.91|0.93|0.88|0.86|0.79|\n\nThe results demonstrate that our influence estimation remains accurate across a broad range of simultaneous edge edits. A minor decrease in correlation is observed only at very high levels of edge editing ($k = 1,000$), which we attribute to first-order approximation errors arising from significant parameter changes when editing a large number of edges.\n\n**[W4] The influence function derivation relies solely on a first-order Taylor approximation and does not account for higher-order or cross-term effects. The manuscript should either provide a theoretical justification for truncating at first order, or include an empirical analysis quantifying the error introduced by ignoring these terms.**\n\nWe adopt the first-order Taylor approximation primarily due to the significant computational complexity associated with higher-order approximations. To illustrate the inherent difficulty, we consider the case of the vanilla influence function [4] as a simpler example (since our specific influence function is even more complex).\n\nFor clarity, we include the second-order derivative $\\frac{d^2\\hat{\\theta}_{z,\\epsilon}}{d\\epsilon^2}$ at $\\epsilon=0$ below:\n\n$$\n-H_{\\hat{\\theta}}^{-1}\\left(\\nabla_{\\theta}^{3}R(\\hat{\\theta})\\left[-H_{\\hat{\\theta}}^{-1}\\nabla_{\\theta}\\mathcal{L}(z,\\hat{\\theta}), -H_{\\hat{\\theta}}^{-1}\\nabla_{\\theta}\\mathcal{L}(z,\\hat{\\theta})\\right]-2\\nabla_{\\theta}^2\\mathcal{L}(z,\\hat{\\theta})H_{\\hat{\\theta}}^{-1}\\mathcal{L}(z,\\hat{\\theta})\\right)\n$$\n\nComputing this second-order derivative involves (1) evaluating the third-order derivative of the total training loss $R(\\theta)=\\sum_{v\\in V_{\\text{train}}}\\mathcal{L}(v,\\theta)$and (2) computing the second-order derivative of the loss for the specific data point $z$ whose influence is being assessed. These terms are challenging to compute, as evaluating higher-order derivatives with respect to the parameters typically requires substantial computational time and memory resources. Despite the truncation at the first-order approximation, our empirical evaluations indicate that this approximation yields high correlation (up to 0.95) with the actual influence, confirming its practical adequacy.\n\n**[W5] The last term in Equation (9), which measures the difference in node-level loss between the original and edge-edited graphs, is presented in a form that is difficult to interpret.**\n\nTo enhance the interpretability of Equation (9), we will explicitly clarify the meaning of the term $h_v^{\\mathcal{G}^{-1/N,\\theta}}=\\text{GNN}(\\{\\mathcal{V},\\mathcal{E}/\\{e\\},\\mathbf{X}\\},\\theta)$ which denotes the node embedding after removing the edge $e$, directly following Equation (9). We believe this clarification will enhance readers' understanding.\n\n**[Q2] Why does the legend in the Figures refer to Dirichlet Energy instead of the term \"over-smoothing\" used in the main text? Could the authors clarify the reasoning behind this terminology choice?**\n\nDirichlet Energy is a widely adopted metric from prior research for quantifying over-smoothing [5,6]. It directly measures the average difference between representations of adjacent nodes, intuitively capturing the degree of over-smoothing (lower Dirichlet Energy indicates stronger over-smoothing). We respectfully direct the reviewer to Section 4.1 for additional information.\n\n**[Q3] Does assigning values of |ϵ| other than 1/N carry any practical or theoretical significance in this study? Can the authors elaborate on whether other values of |ϵ| were considered, and if so, what their implications would be for influence estimation accuracy or interpretability?**\n\nThe parameter $|\\epsilon|$ controls the magnitude of an edge edit: when $|\\epsilon| = 1/N$ (with $N$ denoting the total number of nodes), it represents fully deleting or adding an edge, whereas $|\\epsilon| < 1/N$ corresponds to partially reducing or increasing an edge’s influence. Since our primary goal is to measure the influence of fully inserting or removing an edge, we consistently set $|\\epsilon| = 1/N$ throughout our study. This choice is standard in influence function research, where the focus is generally on measuring the impact of completely removing or adding an individual data point (or edge, in our context) [2,4]. Exploring smaller values of $|\\epsilon|$ could potentially provide insights into partial modifications of edges, but this falls beyond the main scope of our current analysis.\n\n**[Q4] In Section 4.1, is the definition of an \"L-layer neighborhood\" based on shortest path distance? For clarity, could the authors confirm whether this refers to the set of nodes within shortest-path distance L from the target node, or if another graph-theoretic interpretation is used?**\n\nWe carefully revisited our manuscript based on the reviewer's comment, but we were unable to locate the term \"$L$-layer neighborhood.\" Perhaps the reviewer was referring to the \"$L$-hop neighborhood,\" which is the term we used in Section 4.1. If this is the case, we would like to clarify that an \"$L$-hop neighborhood\" refers to the set of nodes whose shortest-path distance to the target node is at most $L$.\n\n[1] Gong, Liyu, et al. \"Exploiting edge features for graph neural networks.\" CVPR 19.  \n[2] Chen, Zizhang, et al. \"Characterizing the influence of graph elements.\" ICLR 23.  \n[3] Wu, Jiancan, et al. \"Gif: A general graph unlearning strategy via influence function.\" ACM 23.  \n[4] Koh, Pang Wei, et al. \"Understanding black-box predictions via influence functions.\" ICML 17.  \n[5] Cai, Chen, et al. \"A note on over-smoothing for graph neural networks.\" arXiv 20.  \n[6] Rusch, T, et al. \"A survey on oversmoothing in graph neural networks.\" arXiv 23."}]

Author rebuttal:

Meta-review: The paper studies edge influence functions in GNNs without relying on the convexity assumption of the loss function. It introduces a proximal Bregman response function tailored to graphs, which can accommodate both edge additions and deletions. The reviewers identified several merits, including the novel problem formulation targeting non-convex GNNs, the sound theoretical analysis, and the supporting empirical evaluation. The concerns raised during the review process have been reasonably addressed in the rebuttal. Overall, the paper makes a well-motivated contribution to the literature with interesting practical applications to graph rewiring and adversarial attacks.
Decision: Accept (poster)