On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective
Authors: Ning Zhang
Henry Kenlay
Li Zhang
Mihai Cucuringu
Xiaowen Dong
Venue: NeurIPS 2025 poster ()
Keywords: stability
graph convolutional neural networks
graph signal processing
Primary area: general_machine_learning

Abstract: Graph convolutional neural networks (GCNNs) have emerged as powerful tools for analyzing graph-structured data, achieving remarkable success across diverse applications. However, the theoretical understanding of the stability of these models, i.e., their sensitivity to small changes in the graph structure, remains in rather limited settings, hampering the development and deployment of robust and trustworthy models in practice. To fill this gap, we study how small perturbations in the graph topology affect GCNN outputs and propose a novel formulation for analyzing model stability. Unlike prior studies that focus only on worst-case perturbations, our distribution-aware formulation characterizes output perturbations across a broad range of input data. This way, our framework enables, for the first time, a probabilistic perspective on the interplay between the statistical properties of the node data and perturbations in the graph topology. We conduct extensive experiments to validate our theoretical findings and demonstrate their benefits over existing baselines, in terms of both representation stability and adversarial attacks on downstream tasks. Our results demonstrate the practical significance of the proposed formulation and highlight the importance of incorporating data distribution into stability analysis.

On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective
Ning Zhang University of Oxford ning. waiggggtann@sttss.ee ox. ac uk
Henry Kenlay Independent Researcher'
Li Zhang
University College London uces1070uc1. ac
henrykenlay aam0mm.mmpmmmmmmmmmmmm
Mihai Cucuringu
Xiaowen Dong University of Oxford xdong@robots. ox ac.uk .k
UCLA, University of Oxford
Smath ucla.eclaee.ooo edu
Abstract
Graph convolutional neural networks (GCNNs) have emerged as powerful tools for analyzing graph-structured data, achieving remarkable success across diverse applications. However, the theoretical understanding of the stability of these models, i.c., their sensitivity to small changes in the graph structure, remains in rather limited settings, hampering the development and deployment of robust and trustworthy models in practice. To fill this gap, we study how perturbations in the graph topology affect GCNN outputs and propose a novel formulation for analyzing model stability. Unlike prior studies that focus only worst-case perturbations, our distribution-awen -wwrre formulation characterizes output perturbations across a broad range of input data. This way, our framework enables, for the first time, a probabilistic perspective on the interplay between the statistical properties of the node data and perturbations in the graph topology. We conduct extensive experiments to validate our theoretical findings and demonstrate their benefits over existing baselines. in terms of both representation stability and adversarial attacks on downstream tasks. Our results demonstrate the practical significance the proposed formulation and highlight the importance of incorporating data distribution into stability analysis.
Introduction
The past decade has witnessed an explosion of interest in analyzing data that resides on the vertices of graph, known as graph signals node features. Graph signals extend the concept of traditional data defined over regular Euclidean domains to the irregular structure of graphs. To facilitate machine learning over graph signals, classical convolution neural networks have been adapted to operate on graph domains, giving rise to class of graph-based machine learning models graph convolutional neural networks (GCNNs) [9, 27, 52, 28, 13]. At the heart of GCNNs lies the use of graph filters, which aggregate information from neighboring vertices in a way that respects the underlying graph structure [22, 12]. This mechanism enables GCNNs to produce structure-awar embeddings that effectively integrate information from both the input signals and the graph structure.
As GCNNs become prevalent in real-world applications, understanding their robustness under graph perturbations has become increasingly important. In particular, to ensure the deployment of trustworthy models, essential assess their inference-tine stability, how sensitive pre- trained GCNN's predictions are to small input perturbation. This is especially critical because real-worid networks could differ from the clear and idealized samples seen during training. For instance, in social
Work done while the University of Oxford.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

networks, adversarial agents such as bot accounts can strategically modify the network structure, by adding or removing connections, to mislead pre-trained GCNN-based fake news detector [48]. This consideration motivates our investigation into how structural perturbations affect the predictions of pre-trained GCNNs.
In this paper, we focus specifically on analyzing the embedding stability - the sensitivity of GCNN output embeddings to perturbations in the graph structure. Analyzing stability at the embedding level provides task-agnostic perspective that avoids assumptions about specific downstream ob- jectives (e.g.. classification or regression). making our analysis broadly applicable across different model architectures and application domains. A line of recent studies on the embedding stabil- ity of graph filters and GCNNs has primarily adopted worst-case formulation, analyzing the maximum possible change in embeddings under edge perturbations [29, 30, 23, 25, 35]. How- ever, a significant limitation of this worst-case view is its incompleteness: it overlooks output embeddings that are produced by graph inputs other than extreme cases; therefore, it could be overly pessimistic, as seen in Figure This motivates us to explore alternative formulations that capture a wide spectrum of embedding perturbations beyond the worst-case scenarios, rendering the analysis amenable to more realistic data. We summarize our main contributions as follows:
A probabilistic formulation (Section 3). We propose a probabilistic framework for analyzing the embedding sta- bility of graph filters and GCNNs under edge perturbation. Unlike prior work that focuses on the worst-case scenarios, we introduce the notion of expected embedding perturha- tion, enabling a more representative assessment of stability across a broad range of input graph signals. Under this framework, we derive exact characterization of the sta- bility of graph filters and an upper bound for multilayer GCNNs. Both results are distribution-awarre revealing how embedding deviations are jointly determined by the second moment matrix of graph signals and graph topol- ogy perturbations. To the best of our knowledge, this is the first work to establish framework for understanding the interplay between data distribution and structural perturbations in the context of embedding stability.
2.0-
density
1.5
average-Case metric
worst-case se metric
1.0
0.5
0.0
0.6
0.8
1.0
1.2
1.6
1.8
2.0
2.2
magnitute of embedding perturbation
Figure 1: Embedding perturbations of a graph filter on Zachary's s karate club net- work with 100 randomly sampled unit- length graph signals.
A structural interpretation (Section 4). We further interpret our theoretical results to better understand how the interaction between graph perturbation and signal correlation influences model stability. Such interpretation offers insight into why perturbations to certain parts of the graph structure are more impactful than others, empirically observed in recent studies [59, 46). Through case study on the contextual stochastic block model (cSBM), we show that our framework offers a rigorous explanation for heuristic perturbation strategies, clarifying, through the lens of embedding perturbation, why and when they are effective.
Application in adversarial attacks (Section 5). Based on our theoretical results, we propose Prob-PGD, an efficient projected gradient descent method for identifying highly impactful edge perturbations. Through extensive experiments, we demonstrate that Prob-PGD consistently produces on average larger embedding perturbations compared to existing baselines. Despite the focus on embedding stability, we further demonstrate that our method leads to greater performance degradation in down- stream tasks, including node and graph classification using GCNNs.
Related work. Analyzing the inference-ting time stability of GCNNs has gained growing interest in recent years due to its popularity in variety of real-world applications. Existing theoretical studies investigate different types of perturbations: Gao et al. [18], Testa et al. [43, 44). Wang et al. [49], Ceci and Barbarossa [7] study the embedding perturbation induced by stochastically adding or deleting a small number of edges. In Liao et al. [32], the authors analyzed the change in embeddings of GCNNs under a perturbation applied to the learnable model parameters. Ruiz et al. [39] adopted a relative perturbation model where the perturbation on the graph is formulated as multiplicative factor applied to the graph shift operator. Keriven et al. [26] studies the stability of GCNNs to small deformations of the random graph model. Our work is most closely related to series of studies on the embedding
"Code is available http:::/ggtthubb.cm///////////e Git http://anngntttttttattii.y..eeet
2

---

stability under deterministic edge perturbation on the graph [29, 30, 23, 25, 16, 35, 37, (77,88 38]. The main difference between our work and existing embedding stability studies is that prior analyses are limited to the worst-case embedding perturbations, while our work first explores more representative notion using expected embedding perturbations. Such formulation not only captures embedding behaviour from a broader range of inputs, but also enables the integration of input distribution into the stability analysis.
Finally, we note that stability analysis in graph machine learning offers another perspective on robustness, known as training stability, which examines how perturbations to the training dataset influence the learning dynamics [45, 59, 4, 8). While conceptually related, training stability concerns different aspect of robustness and is less directly connected to our focus on the post-training behavior of models under input perturbations.
Preliminaries and problem formulation
2.1 Notation and definitions
Graphs and Graph Signals. Let EV,,, A) be a graph, where V is the set of vertices, E is the set of edges, and A E R=*" is the (possibly weighted) adjucency matrix. We denote Gp = (V, Ep, Ap) perturbed version of G, where only the edge set is modified, while the vertex set remains unchanged. A graph signal refers to a function mapping from the vertex set V to a real value, which can be equivalently defined as a vector x E R"" When multiple graph signals are considered, we represent them by matrix X E Rexd, where each column X.; corresponds to an individual signal.
Graph Filters. The structural information of graph is encoded via a graph shift operator S, self-adjoint matrix satisfying S, = O for all (i, & E. Common choices for S include the graph adjacency matrix A and the graph Laplacian L [5]. A graph filter is defined as function of the graph shift operator, denoted as g(S). Typical examples of graph filters include polynomial filters, g(S) = > - S* and autoregressive moving average filter [21]. Given input graph signals X, the filter output (i.e., output embedding) is expressed as gSS).
This paper investigates the impact of edge perturbations on the outputs of graph filters. Specifically, we measure the change in the output embedding using the squared Frobenius norm (gg( (S,) x f.p where S, denotes the graph shift operator of the perturbed graph 9p- Throughout our analysis, we fix the filter function g()) and consider changes in the filter output only as a consequence of the edge perturbation on the graph. For notational simplicity, when the specific forms of S and filter function are not essential to the context, we use the shorthand E, = g()) - gSp)) to denote the filter difference, Accordingly, the embedding perturbation of input X is denoted as | P... Concrete examples illustrating these concepts are provided in Appendix A.2.
Graph Convolutional Neural Networks. GCNNs are machine learning models that extend convo- lutional neural networks to graph-structured data by leveraging graph filters [17]. They consist of cascaded layers of graph filters gSS followed by non-linear activation function a(.). Given graph
and an input feature matrix X ((), the embeddings at each layer computed recursively
(4) =0 (0)) (1(5)x(-)(())
(1)
where o (-) denotes the activation function at layer I, and (!!) E xdd is the learned parameter in the 1-th layer. Throughout our analysis, we assume the model parameters {O(1) are fixed after training and do not change at test time. Therefore, any change in the final embedding is autributed solely to perturbations in the underlying graph G. The embedding perturbation for an I.-layer GCNN
is measured by ( x ( IP:, where (I.) and x are computed via the recursion in (1) using graph filters (S) and ((,)). respectively. We summarize common GCNN architectures and their associated graph filter functions in Table 4 in Appendix A.2.
2.2 Problem formulation
In this paper, we study the stability of graph filters and GCNNs from a probabilistic perspective. Specificallyy, we consider random input X E RRaxd, where each column X,, corresponds to graph signal drawn independently and identically from an unknown distribution D over R". We make no assumptions about the form of D beyond its second-order statistics, which are captured by the XX (also referred to covariance matrix when E[X.,.] 0).
second- matrix K
3

---

Since the columns x are i..d. samples from D, this second second-moment moment matrix is the same for all i. To
evaluate output stability, we introduce the notion of expected embedding perturbation.
Definition 1. Let gSS) be graph filter. Its embedding stability with respect to signal distribution D is measured by the expected embedding perturbation given by
Ex~plll((S)) - x(S,)xX1i = Ex =X
(2)
For an L-layer GCNN defined as in (1) with graph filter g(S), its embedding stability with respect to signal distribution 'D is quantified by
Ex~D [X x
(3)
Under this probabilistic framework, our goal is to characterize the expected embedding perturbations of graph filters (2) and GCNNs (3), and understand how they depend on the signal distribution D as well as the underlying graph. As our discussion involves both random and deterministic graph signals, we adopt the convention that boldface letters represent deterministic vectors or matrices (e.g.. x, X), while uppercase letters without boldface denote random vectors or matrices (e.g., X). We provide a summary of notations Appendix A. for ease of reference.
Our grobabilisticfooruuatton formulation is general as it does not impose any assumptions on the generative distribution of graph signals. Particularly, by specializing the signal distribution to let the random graph signal X assign all probability mass to the worst-cuse scenarios, our analysis encompasses the existing worst-case analysis, such as Kenlay et al. [25], as special case.
Remark 1.
To maintain focus, we do not explicitly address the permutation equivariance of graph filters and GCNNs, which is considered in other stability studies such as Gama al. [ [16]. However, our framework can readily incorporate such equivariance by only replacing the filter perturbation E, g(S) - g(p)) with its commutation-modulla counterpart Eg = g(() g(P PS)) where Po = arg milpen, [P'SPP - SSp
Remark 2.
3 Analyzing Embedding Stability of Graph Filters and GCNNS
Under our probabilistic formulation, this section studies the stability of graph filters and GCNNs by characterizing their expected embedding change under edge perturbations. We begin in Section 3. with the analysis of graph filters, which are simpler linear models that serve as foundational com- ponents of GCNNs. Building on this, Section 3.2 extends the analysis to the more complex case of multilayer GCNNs.
3.1 Stability Analysis of Graph Filters and Single-Layer GCNNS
Theorem (Stability of Graph Filters), Let X E RR be a random graph signal from a distribution D with second moment matrix K. Then for any graph filter perturbation Eg g(S) - g(Sp), the expected change in output embedding is
E Ex [| XEEXXI
x (K, Eg)
Corollary 1. For any 0, we have P[ (1 c) (, s 1
Itc"
In Theorem 1, we provide exact characterization of the expected embedding perturbation in (4). Furthermore, Corollary establishes a concentration bound that quantifies the probability of deviation from the expected value, thereby reinforcing the utility of our notion of stability. The proof of Theorem is provided in Appendix B. Detailed comparisons between the expected-cat and worst-case embedding perturbation metries are presented in Appendix C.4.
Equation 4 shows that the expected embedding perturbation of graph filter is equivalent to the filter perturbation E, measured in K-induced norm, i.e., (K, E E,) expression re-we weights the perturbation according the second-moment matrix, highlighting the interplay between graph filter perturbation and the correlation structure of the input graph signals. This perspective becomes particularly interesting when the second-order statisties of graph signals are correlated with the graph topology. which is a commonly adopted assumption in the field of graph signal processing [57, 34] and machine learning [2]. more detailed discussion of how this correlation influences stability is deferred to Section 4.
TT(E,KE)) This hightiss)

---

Recall that for single-layen layer GCNN, the embedding of multiple signals X E Raxd is given by x = o (((S)xx01) xp = (s(S))xe!))
where (-) a pointwise activation function and O a learned weight matrix. Due to the non- linearity of the activation function, we can no longer derive an exact expression for the expected embedding perturbation. Instead, Corollary 2 provides a distributionnddeeendent upper bound. The proof is deferred to Appendix B.3.
Corollary 2 (Stability of Single- Layer GCNNs), Let X E RR be a random matrix whose columns are i.i.d. graph signals from distribution D over R", with Cg Lipiscchit continuous. Then the expected embedding perturbation of a single-layer GCNN satisfies
matrix K, and (-) be
Ex~ell - x - dc² 10 EK Eg).
We next establish a connection between the embedding perturbation of single-layer GCNN and that of its associated graph filter. The following result holds under mild monotonicity condition on the activation function.
Corollary 3. Let (-) be monotonically non-decreasing activation function. Then the expected embedding perturbation of a single-layer GCNN is monotonically non-decreasing in the expected embedding perturbation of its associated graph filter.
Corollary 3 implies that for a single-layer GCNN with monotonically non-decreasing activation
functions, any optimization task involving the embedding perturbations can be reduced an equiva- lent problem over the associated graph filter. This observation is particularly valuable for studying adversarial edge perturbations, which are commonly formulated as optimization tasks. Since most commonly used activation functions, such as ReLU and Sigmoid, are monotonically non-decreasing, this corollary simplifies the analysis of adversarial attacks by allowing us to focus only on the embedding perturbation of graph filters. For the later case, which is linear, Theorem I provides an exact expression for the expected perturbation. As result, this connection enables near-exact stability analysis for broad class of single-layer GCNNs, including models such as SGC [52]. SIGN [14], and gfNN [36].
3.2 Stability Analysis of Multilayer GCNNs
We now extend our analysis multilayer GCNNs, which generalize the single-layer case by stacking multiple layers of graph filtering g(S), nonlinear activation o-), and learned model parameters [0 Unlike the single-layer setting, multilayer architectures introduce recursive dependencies and compound nonlinearities, making exact characterization of the embedding perturbation analyti- cally intractable. Nevertheless, by leveraging the results for graph filters and carefully bounding the propagation of perturbations across layers, we derive in Theorem 2 an upper bound on the expected embedding change for L-layer GCNNs.
Throughout analysis of multilayer GCNNs, we make the following standard assumptions:
|| < C and [[r(S,)] S C
(A1)
a' (-)) is C. Lipschiz continuous for all 51Sh.
(A2)
a' (0) 0 for all hidden layer < L 1-
(A3)
Assumption (A1) requires that the spectral norm (largest singular value) of g(S) and g(,)))
bounded by a constant C. This condition is trivially satisfied for finite graphs and can also be ensured for infinite graphs through appropriate normalization of the filter, such as dividing by the maximum degree. Assumption (A2) imposes Lipschitz continuity on the activation functions, property satisfied by most commonly used functions such as ReLU (C, 1), Tanh (C, = 1), and Sigmoid (C, = 1/4). Assumption (A3) requires that hidden-layy layer activation functions output zero when their input is zero, which is satisfied by many standard hidden-layer activation functions, including ReLU, Leaky ReLU, and Tanh.
Theorem 2 (Stability of L-layer GCNN), Let X E Raxd be a random matrix whose columns are i.i.d. graph signals from distribution D over R", with second-moment moment matrix K. Consider
5

---

an L-layer GCNN built on graph filter g(S) and let the corresponding filter perturbation be -(()) (((S))g(Sp)) Suppose the model satisfies assumptions (A1) (A2) and (A3). Then the expected embedding perturbation of the I-layer GCNN satisfies
Ex-D 1x(0 x sdc
sac
II 12
(L-1) model
(r(
K, Eg
(5)
signais
K-modulated pert.
model
Our result in (5) shows that the expected embedding perturbation of an L-layer GCNN is governed by several key components. The first is model complexity, captured by the factor C2LC2L-2211 I1 ||05)] and (T. 1), which reflects the cumulative effects of activation non- linearity, filter norms, and learned weights. The bound also depends on the filter perturbation norm ||E,|l and trace of the recond-moment matrix Tr(K), which reflect the magniuddes of the filter change and input intensity, respectively. The second-momen moment matrix modulated filter perturbation term (K, E Eg), is derived from bounding the recursive propagation of perturbations across layers. This term highlights how the embedding change is shaped jointly by the graph filter perturbation and the second-order statisties of the graph signal. For further intuition and complete derivation, we refer the reader to the proof in Appendix B.4.
In prior work, Kenlay et al. [24] showed that for unit-length input signals, the worst-case embedding perturbation of an I--laeer GCN [27] satisfies sup ||x(2) xx P& < dI. I = | 1|2. Compared to this worst-case bound, our result presents a tighter characterization of the embedding stability. More importantly, our result is distribution-awann capturing the joint influence of second- order statistics and graph topology perturbations on the embedding deviation.
4 A Structural Interpretation
Our theoretical results demonstrate that the expected embedding perturbations of both graph filters and GCNNs crucially related the second-moment matrix modulated filter perturbation term (K, E Eg), which is jointly determined by the signal correlation and the structure of the filter perturbation. In this section, we take one step further toward a structural interpretation, understanding which parts of the graph, when perturbed, have the greatest impact on embeddings. In particular, we aim to understand how the interplay between graph structure and signal correlation influences model stability. This perspective offers valuable insight into understanding why certain perturbations are more impactful than others, as empirically observed in several recent studies [31. 46, 50].
The filter perturbation E, gS) - g(pp) depends on the specific choice of graph filters, therefore, unified analysis is not feasible, and exhaustive enumeration of all possible filters is impractical. We therefore focus on two representative graph filters: a low-pass filter using graph adjacency matrix g(S) - A E (0, 1 jaxe and high-pass filter using the graph Laplacian matrix gS) L D- A. We denote P {(u, o} C V {u, o) is perturbed] the set of perturbed vertex pairs. We define Oun indicate the type of perturbation between vertex and v: Tun 1 corresponds adding an non-existing edge between u and v, while due = - corresponds to deleting an existing edge.
Proposition Consider an edge perturbation set P. If the graph filter is the adjacency matrix, i.e.. g(S) = A. then the expected embedding perturbation satisfies
Ex~D E x = (K, E Eg)
Σ
(Knn + K +2
Σ
Tue Baw (6)
{u,DEE
(u,0),Lu,d'EEP
the graph filter is the graph Laplacian, i.e., -SS)=I
Ex~D| E (K, Eg) = 2 R(u,, +)+ + Σ
aurFaer (R(u, + R(u, R(v,
{u.0)E (u.')
where R(u, v) is defined as R(u, w) A F( -..x2
Proposition shows that the expected embedding perturbation decomposes into two parts: self-terms, which capture the individual contribution of each perturbed edge (the first summation in (6) and (7)),

---

and coupling terms, which capture interactions between intersecting edge pairs, i.c., edge pairs that share a common vertex (the second summation in each expression). While each self-term is non- negative, the coupling terms depend on both the signs of the perturbations and the signal correlation between the endpoints. This suggests that impactful perturbations tend to involve intersecting edge pairs whose perturbation types are aligned with the signal correlation. The following remarks provide structural interpretations of impactful perturbations for A and L.
Remark 3. For the adjacency-bast filter g(S) = A. impactful edge perturbations tend to have intersecting edge perturbations rather than distributed and disjoint edge pertubattons.. Those intersecting edge perturbations tend to have their perturbation rypes aligned with the second-order statistics of the non-intersecting vertices, ensuring that a aue uv! Kov' > O.
Remark 4. By definition, the function R(-): VV>V - R is a distance function in a metric space, :
and it follows the triangle inequality R(,,u) + R(u, v') R(v, 2 O. Therefore. for g(S) L, impactful edge perturbations tend to have intersecting edge perturbations consistent in type, either both additions or both deletions, i.e. Tw
(a): 13.03
02
(b): 42.77
(c): 41.70
50
10c
|Ax ApXIF
(e): 23.84
01
(c): 85.17
100
150
I|LX
LPXIF
(a) Random
(b) As Remark 3
(c) As Remark 4
(d) Sample distribution
Figure 2: Edge perturbations on a graph and signals from the contextual stochastic block model.
To elaborate on these insights, we use the contextual stochastic block model (cSBM) as a demonstra- tion. In cSBM [10], vertices within the same community have positively correlated signals. while signals between communities are negatively correlated. We adopt graph signal distribution defined in (37), with Kuv > O if and v belong to the same community, K < O otherwise. Figure 2 illustrates edge perturbations patterns constructed according to Remark 3 and Remark 4. We generate 100 graph signals sampled from (37) and plot the distribution of their embedding perturbations in Figure 2d. The results show that, for the same number of edge perturbations, the perturbation patterns following Remark 3 and Remark 4 produce the largest overall embedding perturbations for A and L separately, validating the structural intuitions described both remarks.
Several prior studies [31, 46, 59] have shown that certain structural patterns of adversarial edge perturbations are more impactful than others. The key distinction is that: previous approaches design perturbations primarily with respect to the graph topology, such as vertex degree, while our study advocates for jointly considering both the graph topology and the signal distribution. In earlier work, Waniek et al. [50] proposed the heuristic ad adversarial perturbation method DICE, which disconnects nodes within the same community and connect nodes across communities. Our theoretical analysis, along with the cSBM case study, provides rigorous justification for this heuristic by explaining from a perspective of embedding perturbation why and when this strategy is efficient. We note that our framework is broadly applicable, as it neither relies on specific graph filter nor requires ground-truth labels from downstream tasks, thereby providing insights into the structure of impactful perturbations across diverse graph learning settings.
5 Empirical Study on Adversarial Edge Perturbation
Adversarial graph attacks are carefully designed, small changes applied to the graphs that can lead to unreliable model outputs. Understanding such adversarial vulnerabilities is crucial for assessing the robustness of graph learning models. In this section, we demonstrate the practical impact of our theoretical findings in adversarial graph attacks. Specifically, we develop a distribution-avir algorithm, Prob-PGD, to identify adversarial edge perturbations that significantly affect graph signal embeddings. Following our setting of inference-time stability of pre-trained models, we focus on evasion attacks on graphs (as opposed to poisoning attacks), where an adversary can modify only
attack
7

---

edges of the graph. without changing the learned model parameters of graph filters and GCNNs. We consider an adversarial edge attack on undirected simple graphs and further assume that adversaries have a limited budget, allowing them to add or delete up to edges.
Methodology. We consider task-agonistic edge attack where our goal of adversarial edge per- turbation is to maximize the expected embedding perturbations from graph filters or L-layer GC- NNs
D arg max E|| { or P arg max ElI X 121
P =m
pP
From Theorem and Theorem 2. we characterize both embedding perturbations and establish their crucial dependence the corresponding filter perturbation term (K, EK Eg). Based on these, we propose an adversarial edge perturbation design as
P arg max (K, E Eg)-
(8)
Here, the optimization objective involves the filter perturbation Eg and second-moment matrix K. The filter perturbation E, can be computed directly from its definition, E, = g(S) - ((,,), for any given filter and perturbation P (examples are provided in Appendix A.2) The second-moment matrix can be obtained using the empirical aecond-moment, i.e., Kamp = 1/N 2i== x,x.". with alternative approaches discussed in Appendix C.3. The main obstacle to solving this optimization problem is the computational cost, as the complexity of brute-force searching is O (n² To circumvent this, consider relaxing discrete constraints in the problem and applying projected gradient descent method developed by Xu et al. [54] for efficient adversarial attack in Prob-PGD. We present the algorithmic details in Appendix C.I. We also refer the reader Appendix C.8. where we discuss how the proposed method can be adapted to large-scale datasets and present experimental results.
Baselines. In our experiments, we compare our method Prob-PGD with two existing baselines: randomize baseline, Random, which uniformly selects m pair of vertices and alters their connectivity; another algorithm Wst-PGD from Kenlay et al. [25] is based on the same projected gradient descent approach but optimizes for the worst-case embedding metric (38). Other attack algorithms, such as those proposed in [54, 50], are not directly comparable, as they rely specific loss functions, whereas our setting is task-agnostic.
5.1 Adversarial embedding attack
Graph datasets. We conduct experiments on a variety of graphs with different structural prop- erties from both synthetic and real-world datasets. Specifically, we consider the following graph datasets: (1) Stochastic block model (SBM), which generates graphs with community structure [19]; (2) Barabasi-Albert model (BA), which generates random scale-free graphs through a preferential attachment mechanism [1]: (3) Strogatt model (WS) producing graphs with small-world properties [51]; (4) a random geometric (disc) graph model Random Sensor Network; (5) Zachary's ' karate club network, a social network representing a university karate club [56]; (6) ENZYMES, consisting of protein tertiary structures obtained from the BRENDA enzyme database [41]. We refer to Appendix C.2 for detailed descriptions.
Graph signals. Among the above datasets, only the ENZYMES dataset contains real-works mea- surement signals associated with their vertices, while the remaining five datasets only contain graph structures without signals on their vertices. For these graph-only datasets, we generate 100 synthetic signals from an arbitrary distribution, such as random Gaussian signals, signals from cSBM, or the smoothness distribution (see Appendix C.2 for a detailed description). The second-moment moment matrix K is obtained from computing the sample graph signals, i.e, using K amp 1/100 100 x,x?"
Results of graph filters embedding. We evaluate adversarial edge perturbations on two representative filters: the graph adjacency (low-pass) and the graph Laplacian (high-pass), which capture distinct signal propagation behaviors in graph-based data processing. We apply different adversarial edge perturbation methods with a fixed budget of m = 20 edges (less than 2% of the maximum possible edges in most graphs). The results, shown in Figure 3, are presented as violin plots, illustrating the distribution of embedding perturbations across multiple graph signals-100 100 randomly sampled signals for synthetic datasets and 18 real-world measurement signals for ENZYMES. This provides a more detailed view of how edge perturbations affect different signal realizations. Across all datasets and filter types, our distribution-awar method Prob-PGD consistently induces the largest overall embedding perturbations, highlighting the effectiveness and robustness of our methodology.
8

---

SBM
BA
W5
KC
Sensor
ENZYMES
01S A
Randam
Wen
Prot: Poot-PD
Randam
Wun
Prot-PGD
Randam
Wen
Prot-PG
Randemt
Prot-PG
Sandem
Pott-GD
Randemt
WUF-PGD
moot mrot-G0
ENZYMES
11
Randam Mst.
Prob-GG
Random
Wot:PG3
Prob-GGD
Random
Wit:PG3
Prob-FGD
Random
WSt-PGD
Prob-FGD
Random
Wst.PGD
Prob.
Random
Wat. Ws0-70
Prob-900
Figure 3: Violin plot of graph signal embedding perturbations for g A (1st row) and g(S) = L
(2nd row). The y-axis shows sample- wise embedding perturbations i.e, (lg(S)x; g(Sp)x, for
signals {x j= associated with each graph.
Results of multilayer GCN embedding. We conduct experiments multilayer GCN architec- tures [27] using the normalized adjacency matrix g(S) = D-1 A The tests are performed on contextual stochastic block models (cSBM) with 100 vertices, where each algorithm perturbs 20 edges. Since the learnable parameters {O 12 also influence the final embeddings, we perform 200 repeated experiments with model weights independently resampled from a standard Gaussian distribution ensure statistical reliability. Figure presents the Frobenius norm of the embedding perturbations at each layer, visualized as box plots over the 200 trials. Across all layers and activation functions, our distribution-awant strating the effectiveness of our probabilistic formulation in deeper architectures. We also observe that the performance gap between attack methods narrows in deeper layers, possibly due to the loosening of our theoretical bound with depth and inherent phenomena in deep GCNs, such as oversmoothing. Additional results with different model architectures are provided in Appendix C.5.
method Prob-PGD consistently outperforms the baselines, demon-
Layer
Layer
Layer
Layer
Layer
Layer
Layer
am Ro
Amodes Pree roe
Resdon
woy Ago
Aio
Atddim wirnop
Aool
Amodm socoog
400
Recamn
Prov roo
Aodeon stospp Poe-
Resdom
invo
(a) GCN with ReLU
(b) GCN with sigmoid
Figure 4: Embedding perturbation of 5-layer GCNs with different activation function.
5.2 Adversarial attack on downstream tasks
We further evaluate how embedding-level adversarial perturbations affect the downstream perfor- mance of pre-trained GCNN models. Our experiments include three popular architectures: GCN [27], SGC [52], and CIN' [53]. More details about model architecture are provided in Table 4 in Ap- pendix A.2, and training details are given in Appendix C.2.
Graph classification. We evaluate classification performance on two benchmark datasets: MUTAG (188 molccular graphs divided into two classes) and ENZYMES (600 protein graphs labeled by six enzyme classes). Both datasets provide numerical node features (e.g., atom types and physical measurements), from which we compute the second-moment matrix Kaam 1/d D> xxx² For each dataset, we use 80% of the graphs to pre-train 10 GCNNs and keep their parameters fixed during evaluation. To assess their prediction robustness, we perturb 5% edges in test set graphs using different attack algorithms and measure classification accuracy before and after perturbation.
Node classification. We the Cora citation network (2708 vertices belonging seven categories) with sparse bag-of-words node features. We pre-train 10 GCNNs on the unperturbed graphs with 140 labeled nodes and keep the model parameters fixed during evaluation. To assess the robustness
*e modify the standard GIN architecture by replacing the MLP in each layer with single-laye perceptron, resulting in a simplified convolutional variant of GIN, Experiments (Appendix C.6) show that standard GINs with deeper MLPs exhibit similar response to edge perturbations their convolutional counterparts.

---

0.75
Embedding pertb
3.0
0.70
accuracy
2.5
Accuracy
0.65
Majority class
Random
2.0
Wst-PGD
Prob-PGD PGD
1.5
0.45
0400
0.03
0.04
0.07
0.01
0.02
0.03
0.04
0.05
0.06
9.07
0.08
Edge Perturbation (percent)
Edge Parturbation (percent)
Figure 5: Classification performance of a pre-trained two-layer GCN on the MUTAG dataset under varying levels of edge perturbation.
of these pre-trained models, we apply different algorithms to perturb 1000 edges the graph and evaluate classification accuracy on test set nodes before and after perturbation. Additional experiments on heterophilic datasets are provided in Appendix C.7.
Table 1: Prediction accuracy of GCNNs under edge perturbations produced by different methods.
Prediction Accuracy(%e
Embedding Pert. || ||
Dataset
Method
GCN
GIN
SGC
GCN
GIN
SGC
Unpert.
70.00
82.8914.60
68.95
Random
73.16:1.05
7..53
1..8
1.24
28.62=2.34
3.57
MUTAG
Wst-PGD 49.21
76.32
68.16+1.42
1.95
37.47 #9.47
to.1
Prob-PGD
44.89
76.58+
41.58 +3.87
2.09
96.26+11.39
t.21
Unpert.
56.33 10
56.75
54.75 13
Random
49.58+3.93
45.83++2.64
45.50
15.3+0.7
81.3+11.3
36.4=1.2
ENZYMES
Wst-PGD
52.58+3.56
39.75
48.75
11.5
264.9
27.2=0.9
Prob-PGD
44.25+2.09
36.75
40.75
17.9
297.9
43.6=1.6
Unpert.
80.06:0.51
74.92
80.33
Random
78.30+0.82
71.75+1.85
78.12+0.64
93+4
974
136
Cora
Wst-PGD 78.47 4-0.44
73.76+-2.07
78.30
97
16901
151+6
Prob-PGD
+-.33
56.67 +-4.57
77.49 6.029
106
435655:3300
160
Results. We report classification accuracy and embedding perturbation magnitude (measured by the Frobenius norm) in Table 1, averaged over 10 pre-trained models. Across datasets and architec- tures, Prob-PGD consistently induces the largest embedding perturbations, which result in greater performance degradation eight out of nine cases. Figure further illustrates the performance of pre-trained two-layer GCN on the MUTAG dataset under varying levels of edge perturbation. The left plot shows that Prob-PGD consistently induces the largest embedding perturbations across all pertur- perturbations transfer to downstream
bation levels. The right plot demonstrates that embedding-les performance degradation. Notably, when the edge perturbation exceeds 3%, Prob-Poo PGD reduces model accuracy to level comparable trivial classifier that always predicts the majority class. Over- all, our proposed algorithm Prob-PGD, although agnostic, still causes significant performance degradation in pre-trat pre-trained GCNNs across different tasks. These results underscore the vulnerability of GCNNs to even small edge perturbations and reinforce the importance of comprehensive stability analysis in such settings.
6 Conclusion
In this paper, we propose probabilistic framework for analyzing the embedding stability of GCNNs under edge perturbations. Unlike prior worst-case analyses, our formulation naturally enables distribution- understanding of how graph structure and signal correlation jointly influence model sensitivity. This insight allows us to provide structural interpretation of the importance of perturbation, and motivates the design Prob-PGD, new adversarial attack method shown to be effective through extensive experiments. While focused on inference-time stability, our study naturally supports broader robustness studies graph machine learning, including adversarial training [33] by crafting adversarial examples. We leave such studies for future work.
10

---

Acknowledgment
NZ acknowledges support from the Engineering and Physical Sciences Research Council (EPSRC) and IBM. XD acknowledges support from the Oxford-Man Institute of Quantitative Finance and EPSRC No. EP/T023333/1.
References
[1] A.-L. Barabási and R. Albert. Emergence scaling in random networks. science, 286(5439): 509-512, 1999.
[2] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanzhez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 0rXiv::806.0126.1 2018.
[3] A. Blum, J. Hoperoft, and R. Kannan, Foundations of data science. Cambridge University Press, 2020.
[4] A. Bojchevski and S. Günnemann. Adversarial attacks on node embeddings via graph poisoning. In International Conference on Machine Learning, pages 695-704. PMLR, 2019.
[5] Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 1312,620,, 2013.
[6] T. Cai and W. Liu. Adaptive thresholding for sparse covariance matrix estimation. Journal of the American Statistical Association, 106(494):672-6844 2011.
[7] E. Ceci and S. Barbarossa. Graph signal processing in the presence of topology uncertainties. IEEE Transactions on signal processing, 68: 1858-531,, 2020.
[8] H. Chang, Y. Rong. T. Xu, Y. Bian, S. Zhou, X. Wang, Huang, and W. Zhu. Not all low-pass filters are robust in graph convolutional networks. Advances in Neural Information Processing Systems, 34:25058-25000 250711, 2021.
[9] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[10] Y. Deshpande, S. Sen, A. Montanari, and E. Mossel. Contextual stochastic block models. Advances Neural Information Processing Systems, 31, 2018
[11] X. Dong, D. Thanou, P. Frossard, and P. Vandergheynst. Learning laplacian matrix in smooth graph signal representations. IEEE Transactions on Signal Processing, 64(23))6160-6113, 2016.
[12] X. Dong, D. Thanou, L. Toni, M. Bronstein, and P. Frossard. Graph signal processing for machine learning: A review and new perspectives. IEEE Signal processing magazine, 37(6): 117-127, 2020.
[13] V. P. Dwivedi, K. A. T. Luu, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023.
[14] Frasca, E. Rossi, D. Bynard, B. Chamberlain, M. Bronstein, and F. Monti. Sign: Scalable inception graph neural networks. arXiv preprini arXiv:2004.11 11198, 2020.
[15] Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432-441, 2008.
[16] F. Gama, J. Bruna, and A. Ribeiro. Stability properties of graph neural networks. IEEE Transactions on Signal Processing, 26:5680-5695,,222
[17] F. Gama, E. Isufi, G. Leus, and A. Ribeiro. Graphs, convolutions, and neural networks: From graph filters to graph neural networks. JEEE Signal Processing Magazine, 37(6): 1188,, 2020.
[18] 7. Gao, E. Isufi, and A. Ribeiro. Stability of graph convolutional neural networks to stochastic perturbations. Signal Processing, 108:10 2021.

---

[19] P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109- 1983.
[20] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances neural information processing systems, 33:221 1822218-220 22132,,, 2020.
[21] E. Isufi, A. Loukas, Simonetto, and G. Leus. Autoregressive moving average graph filtering. IEEE Transactions on Signal Processing, 65(2):274 288, 2016.
[22] E. Isufi, F. Gama, D. I. Shuman, and S. Segarra. Graph filters for signal processing and machine learning on graphs. IEEE Transactions on Signal Processing, 2024.
[23] H. Kenlay, D. Thanou, and X. Dong. On the stability of polynomial spectral graph filters. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5350-5330 5354. IEEE, 2020.
[24] H. Kenlay, D. Thano, and X. Dong. On the stability of graph convolutional neural networks under edge rewiring. In ICASSP 2021-2021 IEFE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8513-8517. IEEF, 2021.
[25] H. Kenlay, D. Thanou, and X. Dong. Interpretable stability bounds for spectral graph filters. In International conference on machine learning, pages 5388-5397 PMLR, 2021.
[26] N. Keriven, A. Bietti, and S. Vaiter. Convergence and stability of graph convolutional networks on large random graphs. Advances in Neural Information Processing Systems, 33:21512-21523, 2020.
[27] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks arXiv preprint arXiv: 600.029907 2016.
[28] R. Levie, F. Monti, X. Bresson, and M. M. Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1): 97-109, 2018.
[29] R. Levie, F. Isufi, and G. Kutyniok. On the transferability of spectral graph filters. 2019 13th International conference on Sampling Theory and Applications (SampTAA), pages 1-5. IEEE, 2019.
[30] R. Levie, W. Huang, L. Bucci, M. Bronstein, and G. Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Reseurch, 22(272):1-59, 2021.
[31] K. Li, Y. Liu, X. Ao, and Q. He. Revisiting graph adversarial attack and defense from data distribution perspective. In The Eleventh International Conference on Learning Representations, 2022.
[32] R. Liao, R. Urtasun, and R. Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. arXiv preprint arXiv:2012.0766 2020.
[33] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 010..70066.888 2017.
[34] M. Navarro, Y. Wang, A. G. Marques, C. Uhler, and S. Segarra. Joint inference of multiple graphs from matrix polynomials. Journal of machine learning research, 23(76):1-35, 2022.
[35] H.-S. Nguyen, Y. He, and H.-T. Wai. On the stability of low pass graph filter with a large number of edge rewires. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5568-5572. IEEE, 2022.
[36] H. Nt and T. Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv:1905.000 095550 2019.
[37] A. Maroda-Mayorga and A. Ribeiro. Algebraic neural networks: Stability to deformations, IEEE Trunsactions on Signal Processing, 69:3351-3366. 2021.
[38] A. Parada-Mayorga Z. Wang, F. Gama, and A. Ribeiro. Stability of aggregation graph neural networks. IEFE Transactions on Signal and Information Processing over Networks, 9:850-864, 2023.
12

---

[39] L. Ruiz, F. Gama, and A. Ribeiro. Graph neural networks: Architectures, stability, and transferability. Proceedings of the IEEE. 109(5):660 682, 2021.
[40] A. Sandryhaila and M. Moura. Discrete signal processing on graphs: Frequency analysis. IEEE Transactions on signal processing, 62(12):3042-33 3054, 2014.
[41] I. Schomburg. A. Chang, C. Ebeling, M. Gremse, C. Heldt, G. Huhn, and D. Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic acids research, 2004.
22(supl_1):D4311-D44
[42] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83-98, 2013.
[43] L. Testa, C. Battiloro, S. Sardellitti, and S. Barbarossa. Stability of graph convolutional neural networks through the lens of small perturbation analysis. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 6865- 6869. IEFF, 2024.
[44] L. Testa, S. Sardellitti, and S. Barbarossa. Robust filter design for graph signals. arXiv preprint arXiv:2403. 16983, 2024.
[45] S. Verma and Z.-L. Zhang. Stability and generalization of graph convolutional neural networks In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1539-1548, 2019.
[46] X. Wan, H. Kenlay, R. Ru, A. Blaas, M. A. Osborne, and X. Dong. Adversarial attacks on graph classifiers via bayesian optimisation. Advances in Neural Information Processing Systems, 34: 6983-6996, 2021.
[47] B.-Y. Wang and M.-P. Gong. Some eigenvalue inequalities for positive semidefinite matrix power products. Linear Algebra and Its Applications, 184:249-2600 260, 1993.
[48] H. Wang, Y. Dou, C. Chen, L. Sun, P. S. Yu, and K. Shu. Attacking fake news detectors via manipulating news social engagement. In Proceedings of the ACM Web Conference 2023, pages 3978-3986, 2023.
[49] X. Wang, E. Ollila, and S. A. Vorobyov. Graph convolutional neural networks sensitivity under probabilistic error model. IEEE Transactions on Signal and Information Processing over Networks, 2024.
[50] M. Wanick, T. P. Michalak, M. J. Wooldridge, and T. Rahwan. Hiding individuals and commu- nities in social network. Nature Human Behaviour, 2(2):139-147, 2018 2018.
[51] D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world" networks. nature, 393 (4684):440-442, 1998.
[52] Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6871. PMLR, 2019.
[53] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, How powerful are graph neural networks? arXiv preprint 1iv.10800000266 2018
[54] K. Xu, H. Chen, S. Liu, P.-Y. Chen, T.W.. Weng, M. Hong, and X. Lin. Topology attack and de- fense for graph neural networks: An optimization perspective. arXiv preprint arXiv: arXiv: 1906.042144 14, 2019.
[55] M. Yuan. High dimensional inverse covariance matrix estimation via linear programming. The Journal of Machine Leurning Research, 11: 11:2261-2286, 2010.
[56] W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of anthropological research, 33(4):452-473, 1977.
[57] C. Zhang, D. Florêncio, and A. Chou. Graph signal processing-a probabilistic framework. Microsoft Res., Redmond, WA, USA, Tech. Rep,
2015.
13

---

[58] J. Zhu, Y. Yan, L. Zhao, M. Heimann. L. Akoglu, and D. Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs, Advances in neural information processing systems, 33:7793-7804, 2020.
[59] D. Zügner, O. Borchert, Akbarnejad, and Günneeaan. Adversarial attacks on graph neural networks: Perturbations and their patterns. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1-31, 2020.
14

---

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:[Yen Yes]
Justification: Yes, the main claims in the abstract and introduction accurately represent the paper's s contributions and align well with its overall scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, the paper includes a discussion the limitations of the work, acknowl- edging areas where the approach may be constrained or where further research is needed.
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 on 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 a 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 low or images are taken in low lighting. Or speech-to-tex. 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: Yes, for each theoretical result, the paper provides a complete set of assump- tions along with thorough and correct proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' 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 in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged 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 or 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 the paper to the extent that 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: Yes, the paper fully discloses necessary information to reproduce the main ex- perimental results, ensuring the main claims and conclusions can be independently verified.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a specific model and empirical evaluation, it may be necessary to either make it 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 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, other means that appropriate to the research performed.
also be provided via detailed
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 to reproduce that algorithm.
(b) the contribution is primarily new 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 way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe 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., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Yes, the paper provides open access to the data and code, along with sufficient instructions in the supplemental material to faithfully reproduce the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.. cc/
Saaides/CodeSubmisse
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/nips. /ttps.cc/ppbbiiii/ wttpcc//ppppguc...eeeeee gui huto:////middees/eeeeubbbiiiiii
CooeeSummie is onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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: Yes, the paper specifies all relevant training and test details, including data splits, hyperparameters, selection methods, and optimizer types, ensuring the results are fully understandable.
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 a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, the paper reports error bars or provides appropriate statistical significance measures, ensuring reliable interpretation of the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It 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 figures symmetric error bars that would yield results that are out range (e.g. negative error 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 in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Yes, the paper provides sufficient information on the computational resources used for each experiment, including the type of hardware, memory, and execution time.
Justification:
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 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 or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https /ttp///eerup./e//ee//ee cc
Answer: [Yes]
Justification: Yes, the research presented in the paper fully conforms to the NeurIPS Code Ethics all respects.
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 to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: Yes, the paper discusses both potential positive and negative societal impacts, noting that the work motivated by a computational task with broad applicability across many fields, while also acknowledging possible risks limitations.
18

---

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 considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a 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 conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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: Not applicable the paper does not involve the release of high-risk data models that would necessitate specific safeguards against misuse.
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 to 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. Licenses 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: Yes, all external assets used in the paper properly credited, with licenses and terms of use clearly stated and appropriately followed.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
19

---

The name of the license (e.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.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pa se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Not applicable the paper does not introduce new assets that require addi- tional documentation.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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:Nor applicable - the paper does not involve crowdsourcing experiments or 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
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?
Question:
Answer: [NA]
Justification: Not applicable - the paper does not involve study participants or require IRB equivalent ethical review.
Guidelines:
20

---

The answer NA means that the paper does not involve crowdsoureing 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 expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Not applicable the paper does not use large language models (LLMs) as an important, original, or non-standard component of its core methodology.
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 LLM policy (https: / http///uurscc//ooniieee/eeeeeeee htarrrpppsccc/ooneeenneeeee///// for what should or should not be described.
21

---

A
Summary on notations and concept definitions
A.1 Summary of notations
Table 2: Summary on notations
Notation
Definition
X
deterministic graph signal, x E R"
X
Random graph signal (node feature)
G
Graph
Gp
Perturbed graph
A
Graph adjacency matrix
A
Adjacency matrix of the perturbed graph Gp
S
Graph shift operator, S.. = 0 if Auv =
S,
Graph shift operator on a perturbed graph, (Sp)uv 0 if (Ap)uo A graph filter defined on the shift operator S
g(S)
Eg
Graph filter perturbation, g(S,) g(S) Eg
E,x
Embedding perturbation for input x, and E g(Sp)x 9(S)x Distribution of graph signals
D
K
aecond-moment matrix of graph signal from distribution
D
Degree matrix, a diagonal matrix with entries D; - Σ; Aij Graph Laplacian where
D Degree matrix of the perturbed graph Gp Graph Laplacian of perturbed graph 9p. where Lp = Dp Ap
Dp
P
L
J
All-one matrix Identity matrix
I
Graph adjacency matrix with self-loop, À A
D
Degree matrix with self-loop, D = Σ; Aij Collection of perturbed vertex pairs, P (fu, o} V: fu, v) } is perturbed) Cardinality of the set P
PI
X
quadratic norm of vector x, where | = xxx
M
Spectral norm of matrix M, where M the largest singular value
Frobenius norm of matrix M, where |M
F
Eig M2-
(A,
B
Frobenius inner product, (A, B)
Ai Bij
Hadamard product of two matrices, (A Matrix A is positive semidefinite
B) A,
A 2 0
(.)
Non-lincar activation function
(1)
Learnable parameters in the (-th layer of a GCNN
A.2 Concept definitions
Edge perturbation. We take simple graph G, shown in Figure 6a, illustrative example. The graph signal on G is given by (0.1, 0.5, 0.9, 0.3, 0.7, 0.6)² We perturb the graph & by deleting the edge between 4 and and connecting 3 and 5, and the resulting perturbed graph is shown in Figure 6b. The edge perturbations can be represented as p {{3, 5), {4, 6}} with a46 - and 035
Filter perturbation. Edge perturbations in graph induce corresponding changes in the graph filters. For example, when using the graph Laplacian as the filter, i.e., (() L, the perturbation P results filter change given by
0
0
0
0
0
0
0
0
0
0
-1
0
0
Eg = L Lp
0
1
-1
0
0
1
0
-1
0
-1
Then the magnitude of embedding perturbation for graph signal is ||
|
0.26.
22

---

Table 3: Common graph filters from [42, 40] and their perturbations
Graph Filter g(S)
Filter Perturbation Eg
polynomial of adjacency matrix: Σ C/A
1 Ap)
polynomial of Laplacian: Σ j== ojL
2n (L Lp)
low-pass filter: (I + aL)
(L+ (I+ aLLp) 1
heat diffusion filter: e L
e 1L -
0.9
0.6
0.1 0.6
0.1
(a) graph G and associated signal x
(b) perturbed graph Up with
Figure 6: Attributed graph and graph perturbation.
For a general graph filter gS),, the corresponding filter perturbation induced by P can be computed by first constructing gSS and g g(Sp) from the original graph and the perturbed graph Gp separately, and then taking their difference Ey = g(S) g(p)). We summarize Table 3 some common filters and their perturbation.
B Proofs
B.1 Proof of Theorem 1
Theorem (Stability of Graph Filters). Let X E RD be a random graph signal a distribution D with second moment matrix K. Then for any graph filter perturbation E.g g(S) 9(Sp), the expected change in oulpul embeddingg is
EX || (K E.)
(
Proof. We start with deriving the expression (4) for the expected embedding perturbation. Consider random graph signal X in R" its i-th entry is random variable, which denote X,. Given deterministic graph filter perturbation Eg. the perturbation on the output embedding is E, X, which also random vector, and its squared Frobenius norm (Fuclidean norm) can be written
E X'E
Σ XxX,(E,
Then the expectation of this squared Euclidean norm of the embedding perturbation can be written as
Ex~D E, X 1
Σ
E( = (K, E,,
where the last equality simply follows from the definition of the second-moment matrix K E[XXT].
'We modify the standard GIN architecture by replacing the MLP in each layer with single- layer perceptron. resulting simplified convolutional variant of GIN.
23

---

Table 4: GCNNs and their associated graph filters.
GCNN Model
g(S)
Eg
from (A1)
GCN [27]
D AD 1/2
D-1/AAD 1/2
Dp 1/22 ", 1/2
1
GIN [53]*
(1 [
A A
max degree
SGC(k) [52]
D-1/"A 2/2)
(D-VAA 1/2) (D,
( D, 1/2) 1/)
Next, we show the concentration of the embedding perturbation. Using Markov's inequality, we have that, for the non-negative random variable | 12 and any > 0
1
PxND E, 2 (1 E,
S 1 1+6 c
B.2 Proof of Corollary 4
The following Lemma contains useful inequalities that will use in the proofs.
Lemma (Basic matrix inequalities). For any A, B Rexn we have
BI] & ABI 1 < ( (A)
(9)
For any A, B Z O, have
(A, B) < [r(B)
(10)
For any E Raxm Rmxdd x we have
| < A BI
(11)
where |||| is the larges singular value of A.
Proof. The incqualities from (9) are adapted from Theorem 1 in [47].
To prove the inequality (10), we denote the eigendecomposition A = UAU" and B = VΣV",
where A diag(A,) and Σ diag(o,). Then we have
A, B) TH(UAU" -EAAU"
Σ VVVVV'V
|||
U U'VEV'
(U |A TT(B)
Here the inequality follows because A; 2 and o; 2 for all To prove the inequality (11), note that
| - Tr A A = (BT AFA)
Therefore, (10) directly implies (11).
B.3 Proof of Corollary 2
Corollary 2 (Stability of Single-Layer GCNNs). Let X E RRaxd be random matrix whose columns are i.i.d. graph signals from a distribution D over R", with moomett matrix K, and a(.) be Co-Lipschitz continuous. Then the expected embedding perturbation of single-layer GCNN satisfies
Ex-pllIx()
x111 dd 10 11 K, E., En).
24

---

Proof. Under edge perturbations, the induced output embedding perturbation of a single-layered GCNN is more complicated than outputs of graph filters due to the existence of the non-linear activation function and the learned weight matrix (1))
To handle the non-linearity, we consider upper bound the change in output in the following way:
x - ((())x(() (o(S,)xe())
- C. (S)) - ((S))
(12)
= C. =C
In (12), the inequality denotes entrywise less than, and denotes entrywise absolute value on the matrix. The inequality (12) follows from the Lipschitz continuity of activation function o(.).
Furthermore, handle ( we apply a matrix inequality (11) from Lemma have that
|
(13)
where ||(0]] denotes the larges singular value of O Combining (12) and (13), have the magnitude of the embedding perturbation
F x
< C
E.g X (2) 1
C e (1) ( E X
(14)
dC? (1) (K, E Eg),
(15)
where (14) follows from (13) and (15) follows Theorem 1.
B.4 Proof of Theorem
Theorem 2 (Stability of I--layer GCNN). Let X E Raxd be random matrix whose columns are i.i.d. graph signals from a distribution 'D over R", with second-moment matrix K. Consider I--layer GCNN built on graph filter g(S) and let the corresponding filter perturbation be
E, = gS) g(Sp). Suppose the model satisfies assumptions (A1) (A2) and (A3). Then the expected embedding perturbation of the L-layer GCNN satisfies
Ex~D |
[
xx-00 C2L - II 12
(L 1- tr( K Ey
(5)
model
signnis
K K-moddiated pert.
model
Proof. To establish our result, we first observe that if the following
|x(0) x C. CaL- II O 10 ([ 110---1))B 1) |E,
(16)
holds with probability 1. Then, by Theorem 1, we easily show
E(| x C II e 10 (2(( IT(( + (K, E.)).
(17)
Thus, it remains to show that condition (16) holds, which we prove by induction.
Base case (l 1): In previous proof of Corollary 2, equation (12) and (13) imply it holds with probability that
| x ? (1) | |2
Induction step For 1 < < L,, assume that for the I-th layer embedding, it has
|x(0- - c 21
@ |2 E, |
(18)
j=l
25

---

Then, for the (1 + 1)-th layer, its embedding perturbation can be first simplified as follows
||x - -x
= | ((())x''=+))) -
(x, ((),)
- (( - 11 I 1 -
(19)
(20)
Here (19) follows form the Lipschitz continuity of o ()),)))). and (20) follows Frobenius--peccrall
inequality (11) from Lemma 1. The term llg(S) xx 1 contains two sources of
perturbation: perturbation in the graph filter (SS) and propagated signal perturbation from pervious
layer x We decompose them as follows
(lg(S)x(0 - x( = Il((S) - -
< (l+(S)x(1 ((,))x 18 (o(,, -(S
x 1| +10(s,)))1 - 1
(21)
C2 -
(22)
Here (21) follows from the Frobenius-spectral inequality (11) in Lemma 1, and (22) holds by the assumption (I9())) < C. Here in (22), the first term captures the change of embedding with input x²) caused by the filter perturbation, and the second term accounts for the embedding change from the 1-th layer, which is given by the inductive hypothesis in (18). Therefore, we only need to further bound the term E 11. x
By definition of the GCNN, (1() is recursively computed following
( = واو (1(S)x6-)((0)) for = I,....,
Becasue of Assumption (A2) and (A3), we further have that o (X())x(--)))) is entrywise upper bounded by |Col - Therefore, we have
E 12 < C, E,g(S)) (,((() S ||E,
(23)
The second inequality in (23) is obtained by using the Frobenius-spectral incquality from Lemma 1. Therefore, we can also recursively bound the squared Frobenius norm of Ex and obtain
x S C. 22 II | ()
(24)
Combining the above results and the inductive hypothesis (18), we have
[x 1I
< C² (141)) ( (1
(25)
x
(26)
S 1
-2
θ 0 12
1 13 + -2xx00-
(27)
S 2 2
6 P1 + |
(28)
Here, equation (25) follows from (20); inequality (26) is derived from (22); inequality (27) follows from (24); and the final step, equation (28), follows from the inductive hypothesis (18).
B.5 Proof of Proposition
Proposition 1. Consider an edge perturbation set P. If the graph filter is the adjacency matrix, iee. g(S) = A, then the expected embedding perturbation satisfies
F Ex Eg X [
(K, E.)
Σ (u.UEP
(Ken + K +2
Σ
TuoTuu Kew-
(6)
26

---

If the graph filter is the graph Laplacian, i.e. g(S) = L
Ex~el] Ex x = (K, E Eg)
R(u, v) + Σ FunFaur (R(u R(u, R(v,d')) Σ
{u. (ur))_und)E
where R(u, v) is defined as v), & El - X.)9%
Proof. (Case 1.) Proof for adjacency filter g(S)= A. We denote lav the edge indicator matrix, where the entries of luv is all other than entry (u, v) and (u, v)) have value 1. Then, for edge perturbation P, decompose the filter perturbation
Es
Ap
A = Σ
Tunlues
(a.u)P
where Our = +1 indicating adding deleting edge between and Then, we have
) (I
(Ap - (A, A)=
Σ fu.otEP
Guolur
Σ
Gurhuv
(uIOtEP
Σ
P. +
Σ
Owa (Buvlar + lwo) +
E
GaaDv'u (Duvlu'a + letalue)
{u.
(u.o))
Σ {u.u)EP
lue Loe
Σ
Tnd (Door luro)
E
Tuod (Doo' + Du'v).
(u,u),tu.''EP
(29)
Therefore, we can further decompose the expected embedding perturbation from Theorem as (A, A),
Elll E
X
(E
E
K) ((Ap
Σ
(Ier + toon K) + Σ
Tun uwr (Dow loros K)
Σ
Tun (low + luvos K)
(u.UEP
(uo)-tu,e')EP
(uro).tu,o'EP
(30)
Σ (MN)EP
Kun + Knv +2
Σ Tun Kev' + E Owo Kow.
(31)
(u,o),(u,0')EP
(u.'))
Here (30) follows from (29). From (31), have that for each pair of perturbed edges {u, w) P. its contribution to the overall embedding perturbation comes from two parts: the unitary term K K,, E[X² + X3]; and the coupling term, which further add 20 war n X Xxx for each of other perturbed edges (u, v') E P that intersects with {u, v..
(Case 2.) Proof for Laplacian filter (S) L To start, we introduce the oriented edge indicator vector buv E {1, 1,, 03", which only has +1 on entries that correspond to two vertices and connected by edge and zero elsewhere. For directed graph,
buo (i) = {
if the edge points to i if the edge leaves i
O.w.
This definition can be extended to undirected graphs with arbitrary directions assigned each edge. With the definition of edge indicator vector, we can then decompose the Laplacian matrix as
L
Σ
bZ
This expression allows us to decompose the filter perturbation to perturbation induced by each edge
E,y
Lp L
Σ
ourburr
(32)
(u.eEP
27

---

Here P denote the collection of vertex pairs that are perturbed. For fu, E P, we denote Jae = 1 an edge is added to connect u and v and oue -1 if the edge between and is deleted. Then, we can further derive
(Lp
L) (L, -
-L)
Σ fu.tEP
auo Duo
Σ fu.u)P
Jun buo
Σ bur buo +
E JwvTur bur bu
b uv
Σ
owu bub b''ube
tu.u)EP
(u.o),(u,0')E
=2
Σ
(lan + lon
lue lva) +
Σ Onoauw (20 + Oew + Doev Ouo - Durn - Uwu 0wv)
{u,e)EP
(u,))(
+
Σ
Ounov'n (2ban + low buv luv' lora
Upa lav)
(33)
(f'
Combining the above perturbation decomposition and Theorem 1, we have the following decomposi- tion on the expected embedding perturbation
E||| E
E K) ((Lp -L)² - K)
2
Σ (K... + K Kuv Kou) +2 Σ Tuo (Kuu. + Kuw' Kun' Kmn) (34)
(u.))EP
(u,)),(ur'))P
= Σ
R3
Σ
Oun R(u, + R(u, -(U,))
(35)
(u.
Here, (34) follows from (33), (35), we define R(u,v) & El(X, - -X)7%
C Experimental details
C.1 Algorithm: Prob-PGD
As we discussed, attacking graph filters and GCNNs by optimizing the second matrix modulated filter perturbation term (K, E E,) is computationally expensive due to the combinatorial nature of the problem. To circumvent this, we consider relaxing discrete constraints in the problem and applying a projected gradient descent method for efficient adversarial attack. This strategy is adapted from a prior work [54].
We denote p the perturbation indicator matrix in (0, 1]nxx, where the entry (1 = (1 = if {u, 1) P and (1p)...
otherwise. For notational clarity, denote the objective function, the expected filter embedding perturbation, as f(Ip) = (K, E E,y) This function f(1p) is determined by the prespecified filter function s(S), the signal second-moment matrix K and a given graph perturbation P. With budget of perturbing at most edges, the optimal adversarial edge attack be formulated as finding a maximizer of the following problem
max f(Lp)
(PI)
s.t. 1p {0, 10,1
(Lp.J) J) 2m
The hardness of solving (PI) mostly comes from the integer constraint, therefore, we consider relaxing this constraint to the following
max J(M)
(P2)
s.t.
Vu, v, M E [0, 1] (M,J) < 2m
The relaxed problem (P2) has convex feasible region and continuous objective function. Moreover, according to [54] (Proposition 1) for a general matrix M, projecting it to the feasible region of (P2) is simply
II(M) = ( (Po.1 Mooj]M- [J] P/.11.10 []
if > and (J, M) 2m
(36)
if (J, M) < 2m.
28

---

where the function P(o.1j()) (1)())s is applied elementwise to the input matrix, and it has
I i E [0.1] ())1(()) = 0 i < 0
1 1
From the projection function (36), we notice that the sparsity of matrix M from each of projected- gradient descent iterations monotonously non-increasing. Therefore, we set the stopping criteria to be when || is close to n² 2m. Then, we interpret the resulting matrix as probabilistic indicator and select the m edge perturbations corresponding to its largest entries to construct the final adversarial perturbation. We summarize this projected gradient descent edge attack in Algorithm 1. Note that gradient-bast based methods are generally favored for convex objective functions, which does not necessarily apply for all graph filters. However, in the case of adversarial attacks involving small set of edge perturbations, employing gradient- baased method to find local optimum can still produce effective adversarial edge perturbations.
Algorithm 1: Prob-PCD
Input :graph G, second-moment matrix K, edge perturbation budget m, maximum number of iterations N, learning rate a, tolerance 7
Output: : perturbed graph Sp
Initialize M 0;
2 for torl=1 1 N do
Update ( via gradient ascent:
( f(M(t-) + a (M
Project M back the feasible
(*) < (I()())) (see Eq. (36));
6
if || (4) loo S n² - 2m + 2r then
7
break
end
10
end
Obtain the set of edge perturbations P by selecting the m pairs (u, corresponding the largest entries in (2)); Apply the perturbations in P to the graph to obtain the perturbed graph Gp:
C.2 Experiment setup
Graph datasets. To quantify the effectiveness of adversarial edge perturbation using the two algorithms built on our probabilistic framework, we conduct experiments on a variety of graphs with different structural properties from both synthetic and real-world datasets. Specifically, we consider the following graph datasets:
(1) Stochastic block Models. The stochastic block models (SBM) random graph models that can generate graphs with community structure due to their community-dependee assignment [19]. In our test experiments, generate graph with 40 vertices using SBM with two equally sized communities. The intracommunity edge probability is set to 0.4, reflecting dense connectivity within communities, while the intercommunity edge probability is set 0.05, indicating sparse connections between communities.
edge probability
(2) Barabasi-Albert model. The Barabasi-Albert (BA) models generate random scale-free graphs through a preferential attachment mechanism, where vertices with higher degree are more likely to be connected by new vertices added to the graph. In experiments, we sample graph of 50 vertices, following the preferential attachment scheme, where each new vertex connects to existing vertices.
(3) -trogatz model. The Watts-Strogatz (WS) model is random graph model that produces small-world properties, i.e., high clustering coefficient and low average path length. This model built on underlying ring lattice graph of degree h; which exhibits high clustering coefficient. Starting from the ring lattice, each edge is randomly rewired with probability 3 leading to a decrease
29

---

in the average path length. Here, the model parameter 3 controls the interpolation between a regular ring lattice (3 = 0) and an Erdos-Renyi random graph (3 1). In our experiments, we sample graph of size 50 from the WS model using k = 4 and B 0.2.
(4) Random Sensor Network. The random sensor network is random geometric graph model. Here, the vertices are randomly distributed on an underlying space, and the edge probability depends on the geographic distance. We sample a graph with 50 vertices drawn uniformly random from a 2D coordinate system, with the communication radius to be 0.4.
(5) Zachary's is karate club network. Zachary's karate club is social network of a university karate club [56]. This network captures the interaction the 34 members of a karate club, and a popular example of graph with community structure.
(6) ENZYMES. The ENZYMES dataset consists of protein tertiary structures obtained from the BRENDA enzyme database [41]. In this dataset, secondary structure elements (SSEs) of proteins are represented as vertices, and their interactions are captured as edges. Along with the graph structure, this dataset also includes physical and chemical measurements the SSEs, further providing 18- dimensional numerical graph signals (node features). This dataset contains 600 graphs the protein tertiary structures. For our test experiment, we randomly select one protein graph from the dataset, which contains 37 vertices, along with the associated (8-dimensional graph signals.
(7) MUTAG. MUTAG is another widely used dataset for graph classification tasks. It consists of 188 graphs, representing mutagenic aromatic and heteroaromatic nitro compounds. Each vertex in the graphs is associated with 7 node features, representing one-hot encoded atom types.
(8) Cora. The Cora dataset contains 2708 scientific publications (vertices) categorized into 7 classes. These documents are connected by 5429 citation links (edges), forming a citation network. Each document is described by 1433-dimensional sparse bag-of-words feature vector, where each dimension corresponds to a unique word from the corpus vocabulary.
Graph signal generation. Graph signals are data attributed to the vertices of a graph, which could be independent of or correlated with the graph structure. Below, we present several popular generative models for graph signals that depend on the underlying graph semantics.
(1) Contextual-SBM The Contextual stochastic block models (cSBM) are probabilistic models of community conmunity-structuuee structured graphs with high-dimensional covariate data that share the same latent cluster structure. Let v E {1, -1} be the vector encoding the community memberships. Then a graph signal, condition on and a latent value are generated as follows:
X
Vinu uiu + Zi,
(37)
where Zi has independent standard normal entries. has
Therefore, the second-moment matrix K
P u = +1
K₁ = E[X,
Intuitively, vertices from the same community have slightly positively correlated covariates, while vertices from different clusters have negatively correlated graph signals.
(2) Smooth graph signal: Smooth graph signals refer to cases where signal values of adjacent vertices do not vary much, property observed in many real-world datasets, such as geographic datasets. Dong al. [11] demonstrates that such graph signals can be modeled samples from multivariant Gaussian distribution ~ N(,, + + o²1) where L denotes the Moore-Penrose pseudoinverse of L, and a, E R represent the noise level. For smooth graph signals, the second-moment matrix has
K,j = (L* +
ifi=j if ii j
+
Training GCNN models. For graph classification tasks using the ENZYMES and MUTAG datasets, partition the dataset into training and test sets using an 80%, 20% split. We pre-train graph
30

---

convolutional neural networks (GCNNs), including two-layer GCNs [27]. two-layer SGCs [52], and two-layer GIN, where GIN refers a specialized variant of the original model in which the MLPs are replaced with single-layer perceptrons. All models use a hidden dimension of (32,64), followed by ReL.U activation, and employ max-pon max-pooling as the final readout layer. Training on ENZZYMES, and MUTAG both use the standard cross-entropp loss. Models are optimized using the Adam optimizer with learning rates between 0.005 and 0.01, weight decay 10- -3 and 50 to 100 training epochs. In the adversarial attack experiments, the number of edge perturbations is limited to at most 5% of the total possible edge modifications, i.e., 5%m2², where ri is the number of nodes in the graph.
For node classification, we pre-train two-layer GCNs [27], two-layer SGCs [52], and two-layer SUM-GCNs on the original, unperturbed graph, using 140 labeled nodes for training and 1,000 nodes for testing, following the standard setup in [27]. Each GCNN has a hidden dimension of 64 and uses ReLU as the activation function. The models are trained using a standard cross-entropy loss over the labeled training nodes. Training was conducted using the Adam optimizer with learning rate of 0.01 and weight decay 10-4 for 50 epochs. In the adversarial attack experiments, each algorithm perturbs 1000 edges. We repeat the experiments five times and report the average classification accuracy.
All experiments were conducted on an NVIDIA V100 GPU with 16GB of memory. Pretraining of the GCNNs on the input graphs was completed within a few minutes. Adversarial attacks on the ENZYMES and MUTAG datasets finished within few minutes, while attacks on the Cora dataset required slightly more time due to the larger graph size, where Prob-PGD and Wst-PGD both take nearly 10 minutes to complete, with the maximum number of PGD iterations set to 250.
C,3 Computing the second-moment matrix K
Our stability analysis so far is based on the knowledge of the second-moment matrix K. In practical scenarios, computing the second-momed matrix is typically straightforward and can be done in several ways. The most straightforward approach is to use the sample rscond-moment K = Σ, x,x,' Beyond simple empirical estimators, more sophisticated methods based on statistical inference are also available, such as adaptive thresholding estimators [6]. graphical lasso [15], and linear programming- based techniques [55]. Moreover, domain knowledge can further facilitate the construction of the second- -omentt matrix. In graph signal processing, meaningful graph structures often align with the distribution of graph signals. For example, certain sensor networks, geographic proximity tends to produce similar signal patterns, which can be modeled using smoothness assumptions [11].
C.4 Comparison with the average-case metric for graph filters
With the derived expected embedding stability given from Theorem 1, we now compare our proposed metric on the embedding perturbation with the existing metric based on the worst-case perturbation adopted in [29, 30, 23, 25, 16, 35).
sup 11g(S)x ,(,,)x1 |x||==1
(38)
Recall that in the worst-case metric. the graph signal is normalized to unit length. For a fair comparison, we present in Corollary 4 the expected embedding perturbation when graph signals are sampled from the unit sphere in IR".
Corollary 4. Consider a graph signal X sampled from the unit sphere in Rd Then the second- moment matrix K is positive semi-definin with Tr(K)- = 1. Furthermore, the expected embedding perturbation satisfies
F Ex~D | x12 = (K, E - |2,112
(39)
Proof. Note that for any vector x RR, we have
<<==''XXX'">===
X 2
Therefore, K is positive semidefinite matrix with eigenvalues nı 2 0 for all i 1,..., When X restricted to be sampled only from the unit length sphere, we have that with probability 1,
Σ x -1
31

---

472
Embedding perturbation
332
Ware-case embedding perturbation: E,
Expected embesting peturtation ix- Ex,())
202
Sample maximum: max |e
Sample average
202
rank(E
Figure 7: Comparison between the worst-case analysis and average-case analysis. We create an arbitrary filter perturbation E, |pnxa with 100 by sampling i..d. entries from (00, 1). We further compute different rank approximations on Eg and test the embedding perturbation induced by each approximation separately. For each scenario, from unit sphere. The red line represents the expected embedding perturbation as defined in (42), with the sample average depicted by the red star-line. Similarly, the blue line represents the worst-case embedding perturbation as defined in (41), with the sample worst-case shown by the blue star-line.
randomly sample N 10000 graph signals
With this, we further have the trace of K
Tr(K) = Σ E(X?] =
X?
=1.
(40)
For given filter perturbation Eg. ET also a positive semidefinite matrix. Therefore. using (10)
from Lemma 1, we have
E ( E.g K) S I (TY(() | 112
From Corollary 4, it is trivially true that the worst-case embedding perturbation is always an upper bound on the expected embedding perturbation. To further assess how large the gap is between the average-case and worst-case metric, we consider the following three cases, arranged from smallest to largest gap:
Case 1. We consider a deterministic input graph signal that achieves the worst possible embedding perturbation. We X1 denote the worst-case signal, which is the eigenvector associated with the largest eigenvalue of Eg. Therefore, the second-moment simply follows as = x, xix Further using the expression of expected embedding perturbation (4), we derive that the average case perturbation is exactly | |2, which matches with the worst-case metric.
Case 2. We consider the case where we have no prior information about the graph signal X and simply assume that is sampled uniformly at random from the unit sphere Sn-1 Then we have that the second-moment moment matrix K [3].
If we assess the embedding stability from the worst-case view in (38), then we have
sup [[g(S)x ((,,)x113 ||,
(41)
| 2=1
If we assess the embedding stability from the average case view, from our analysis in Theorem 1, we have
Ex= = E, P..
(42)
Note that for an arbitrary matrix M of rank it always holds that |M < Therefore, direct comparison between the two bounds (41) and (42) indicates significant gap between the average-case analysis and worst-case analysis, especially when the change in the graph filter E,
32

---

exhibits low-rank structure or has large eigengaps. We validate this intuition through numerical simulations on synthetic data, and report the comparison results in Figure From the experiments, we observe that as the rank of the filter perturbation Eg decreases, the expected embedding perturbation decreases significantly, while the worst-case embedding perturbation remains unchanged. This highlights that for low-rank filter perturbations, the worst-case bound fails to adequately capture the embedding perturbation across a broad range of graph signals.
Case 3. If the distribution of X is such that the column vectors of K are drawn from the null with probability 1, and the gap between worst-case and
space of Eg. then we have E| X [|]] average-can case metric is maximized.
The comparison between our probabilistic stability metric and the worst-case metric identifies scenarios where they align and where they differ the most. Other than these special cases, the discrepancy between the average-case metric and worst-case metric is mainly influenced by the rank and eigengap of Ey- Notably, certain graph filters tend to exhibit low rank in Ey, such as graph filters that are linear in the graph shift operator S. For those filters, when only a few edges are perturbed, the resulting Eg remains sparse, implying its low-rankness. In applications involving these filters, incorporating the average-case stability metric is practically meaningful, as the worst-case metric is proved to be overly conservative and fails to accurately capture the overall embedding perturbations.
C.5 Embedding perturbation of multilayer GCNNS
Layer
Layer
Layer 4
Layer
Ranovi Veo Prot-K00
Kmsson Hecron 1Do
Kandom W00 mab-oop
Kancom Ricoggo
Akddom W0-
mabion
Figure 8: Left side figures are edge perturbations visualization of different algorithms. Box plots report embedding perturbations at different depths of GCN with sigmoid in each layer.
Layer
Layer 2
Layer
Layer
Layer 5
Randio ioc- Poo
Resson Pog 1g0
Randen WILPD madt-op
Nansom dec.
Rodden
Figure 9: Left side figures are edge perturbations visualization of different algorithms. Box plots
report embedding perturbations at different depths of GIN with ReLU in each layer.
Layer
Layer 2
Layer 3
Layer
Layer 5
Ruedion verv Posh-P0
Ansom weeeo roo
Austion wed Rodivon
Rusdon Wereoo Rgo
Figure 10: Left side figures are edge perturbations visualization of different algorithms. Box plots report embedding perturbations at different depths of GIN with sigmoid in each layer.
C.6 Experiments on message passing neural networks
This study mainly focuses on analyzing the stability of Graph Convolutional Neural Networks (GCNNs), which represent one of the two main paradigms in graph neural networks. The other major
33

---

paradigm consists of message passing neural networks (MPNNs). While both frameworks aggregate node information based on the underlying graph, MPNNS do not necessarily rely on graph filter convolutions. One notable example of MPNN is the Graph Isomorphism Network (GIN) [53]. In GIN, vertex embeddings are computed recursively. For given vertex v, embedding at layer I is obtained by aggregating information from its neighbors as well as from itself at the previous layer, according to the following:
x = MLP(1 ((++ xx
(1-1) +
Σ (EN(e)
(1-1)
where (v) denotes the set of neighbors of vertex u and (0) is either learnable parameters or a fixed scalar. When the multi-layer perceptron (MLP) reduced to a single-layer perceptron, the model simplifies to GCNN with graph filter of the form A + I Empirical studies the stability of GIN with a single-layer perceptron are presented Section 5. Here, we extend this investigation to GIN architectures with a two-layer perceptron (GIN-2) and three-layer perceptron( both implemented within a two-layer GIN framework. Using the same experimental settings as in Section 5, we pre-train 10 GINs on unperturbed graphs. Table 5 reports the prediction accuracy and embedding perturbation under various edge perturbation algorithms. Across different datasets and models, Prob-PGD induces the largest embedding perturbations, and further results in greater performance degradation for ENZYMES and Cora classification. Overall, GIN models with deeper MLPs exhibit similar response edge perturbations as their single-layer counterparts. This observation suggests that our filter-based analysis might be extended to study the stability of MPNNs by investigating graph filters that capture their underlying message passing mechanism.
Table Prediction accuracy GINs under edge perturbations produced by different methods.
Prediction Accuracy %)
Embedding Pert. || |||
Dataset
Method
GIN-2
GIN-3
GIN-2
GIN-3
Unpert.
82.89
82. 12.111m
Random
70.53
70.53
28.62
28 28.43
MUTAG
Wst-PGD
76.32
76.321994
37.47
17.37
Prob-PGD
76.58
77. 11781
96.26211.99
93.47:10322
Unpert.
58.9 +8.92
50.08
Random
48. 23.75
41.83
92.44:112.6
28.35
ENZYMES
Wst-PGD
39.33
41.001:314
295 625.62233500
74.06112.8
Prob-PGD
37.00
35.58
345.54149.35
83.59
Unpert.
73.76111.9
70.72.1..30
Random
69.73
66.95
1129=344
1498
Cora
Wst-PGD
72.55
69. 19.19922.. 1:.20
16329_7638
11105
Prob-PGD
57.95
54.09
40343=22301
25784
C.7 Additional experiments on heterophilic datasets
We further conduct empirical study on the following two benchmark heterophilic datasets.
Chameleon. The Chameleon dataset contains 2277 nodes representing Wikipedia articles, where edges denote hyperlinks between them. Each node is assigned the average monthly traffic of the corresponding page. With a homophily score of 0.23, reflecting strong heterophilic properties. Following the standard split, we use 1092 nodes for training, 729 for validation, and 456 for testing.
of five classes according to
The Squirrel dataset contains 5201 nodes, each representing Wikipedia article, with edges indicating hyperlinks between pages. Nodes are categorized into five classes based on the average monthly traffic. The dataset has homophily We follow the standard data split, using 2496 nodes for training, 1664 for validation, and 1041 for testing.
Squirrel.
of 0.22, reflecting strong heterophilic properties.
With low homophily scores, these two datasets are challenging for traditional GNNs. Therefore, we adopt the H2GCN model [58], graph convolutional network specifically designed for heterophilic
34

---

Table 6: Results on heterophilic datasets with H2GCN.
Dataset
Method
Prediction Accuracy (%)
Embedding Pert.
||
Unperturbed
55.92 1.47
Random
54.23 + 1.16
136.65 + 4.27
Chameleon
Wst-PGD
64.87 + 1.51
3099. 12 = 0.00
Prob-PGD
52.96 1.38
6392.17 = 0.00
Unperturbed
50.38 0.39
Squirrel
Random
47.91 0.47
578.92 +: 3.86
Wst-PGD
48.48 0.73
1127.2 22 + 0.00
Prob-PGD
48.28 + 0.73
3908 26 = 0.00
Table 7: Scalability experiments on large-scale graphs.
Dataset
Nodes
Edges
Embedding Pert.
|| ||e
Memory (MB)
Time (s)
Random
Wst
Prob (Ours)
ogbn-arxiv
169,343
1,166,243
4.10
14.96
25.29
390.6
537.7
ogbn-mag
1,939,743
21,111,007
2.59
8.53
15.75
7362.4
1603.0
ogbn-products
2,449,029
61,859,140
17.65
24.39
193.84
5833.3
2798.5
pokec 1,632,803
30,622,564
292.32
303.30
334.20
18040.3
1172.1
graphs. Given a node feature matrix X and graph adjacency matrix A, H2GCN constructs node embedding as
H [X;
where the three components correspond the original node features X, the aggregated 1-hop features AX, and the aggregated 2-hop features X respectively. The concatenated embedding H are then passed through multi-layer perceptron (MIP) for node classification. For each dataset, pre-train 10 H2GCNs and report in Table 6 the mean and standard deviation of both prediction accuracy and embedding perturbation under different attack methods by perturbing 1000 edges.
Across both heterophilic graphs, the Prob-PGD attack consistently induces the largest embedding perturbation compared to baselines. On the Squirrel dataset, despite producing the most substantial embedding disruption, Prob-Pot PPD does not lead to the largest degradation in prediction accuracy. This outcome not unexpected: Prob-PGD is task-agnostic attack that seeks maximal perturbation in node embeddings rather than direct misclassification. Consequently, the relationship between embedding perturbation and classification accuracy not always linear.
C.8 Scalability study on large-scale graphs
Our proposed algorithm Prob-PGD has demonstrated efficiency through intensive experiments medium-sized graphs. The underlying framework, however, is general and can be adapted to large- scale graphs with millions of nodes. In particular, based optimization and can naturally incorporate alternative search strategies such as greedy heuristics. These approaches iteratively perturb the edge that induces the largest local embedding change and can operate on local subgraphs or within restricted edge subsets. By narrowing the perturbation space, such localized search substantially reduces computational overhead while maintaining competitive attack strength, providing a practical balance between efficiency and optimality.
attack formulation (8) is not restricted to PGD-
To provide concrete example, adopt scalable greedy edge-deletion approximation of the original optimization in (8). Specifically, we restrict the perturbation search to existing edges, randomly sample subset of candidate edges at each iteration, and greedily delete the one that maximizes the attack objective in (8). This stochastic greedy strategy leverages graph sparsity for efficient computation. We denote approximation by Prob and apply the same approximation to the worst-case baseline, denoted as Wst. We conduct experiments using the adjacency graph filter on four large-scale OGB benchmarks [20]: ogbn-arxiv, ogbn-mag. mag, ogbn-products, and pokec, where ogbn-mag is heterogeneous and pokec exhibits label heterophily. For each dataset we perform adversarial edge-deletion attacks that remove 200 existing edges. We report average embedding perturbation, peak memory usage, and running time in Table 7.
35


Reviews:
[{"review_id": "mKDhcU8UXK", "reviewer": "Reviewer_SjSK", "summary": "This paper investigates the stability of Graph Convolutional Neural Networks (GCNNs) from a probabilistic perspective. Specifically, it studies the sensitivity of GCNN embeddings to small perturbations in graph topology. Unlike prior research focusing primarily on worst-case perturbations, this paper proposes a novel distribution-aware formulation, analyzing expected embedding perturbations across various input data. The authors derive exact characterizations and upper bounds for embedding perturbations in both graph filters and multilayer GCNNs. They further interpret these theoretical findings through structural insights, clarify conditions under which certain perturbations are more impactful, and propose a novel adversarial attack method (Prob-PGD) validated through extensive experiments.", "questions": "(1) How well does the proposed framework scale to very large graphs such as ogbn, Reddit, or Aminer-CS? Have the authors conducted any runtime or memory usage comparisons on such datasets?\n\n(2) How might the framework perform on heterophilous or mixed-type graphs? Would the authors consider including a discussion or additional evaluations on this point?\n\n(3) Considering that adversarial defense against structural attacks is a well-studied area, could the authors expand the empirical comparison to include more recent or stronger baselines [1, 2, 3, 4]?", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n(1) The proposed probabilistic framework extends beyond traditional worst-case analyses, providing deeper insights into embedding stability considering realistic data distributions.\n\n(2) Rigorous derivations of stability measures for graph filters and multilayer GCNNs enhance the theoretical understanding of these models.\n\n(3) The paper is well-structured, clear, and self-contained, with theoretical results clearly presented and complemented by insightful empirical analysis.\n\nWeaknesses:\n\n(1) The computational efficiency and scalability to very large-scale graphs are not extensively addressed, potentially limiting applicability in large-scale graphs, such as ogbn, Reddit, and Aminer-CS.\n\n(2) The framework requires accurate estimation of the signal autocorrelation matrix, which may be challenging in real-world scenarios with limited or noisy data.\n\n(3) The evaluation is limited to homophily graphs. The author should add a discussion on that.\n\n(4) The major concern is with the empirical study in this paper. Adversarial defense against structural adversarial attacks is a widely studied topic [1,2,3,4]. However, only a limited number of works are discussed and compared in the experiments. \n\n[1] Reliable representations make a stronger defender: Unsupervised structure refinement for robust gnn\n\n[2] Self-guided robust graph structure refinement\n\n[3] Adversarial robustness in graph neural networks: A Hamiltonian approach\n\n[4] Elastic graph neural networks", "was_revised": true, "final_justification": "The authors have made a commendable effort in addressing several concerns, particularly those related to autocorrelation estimation and evaluation on heterophilic graphs. However, the scalability claims of the proposed method remain insufficiently supported. The results on small-scale datasets such as Cora, which contain only thousands of nodes, do not adequately demonstrate the method's practical applicability to real-world graph settings that involve significantly larger and more complex structures. Moreover, the additional experiment on ogbn-arxiv evaluates only a simplified greedy variant of the method and compares it solely against a random baseline, which limits the strength of the empirical evidence. As a result, I intend to maintain my original score.", "rebuttal": "We thank the reviewer for their acknowledgement of the strengths of our work, and for raising insightful comments to help us further improve the paper. Below we provide detailed response to each comment: \n\n> (1) scalability to very large-scale graphs?\n\nWe thank the reviewer for the question regarding scalability. Our algorithm Prob-PGD is efficient on moderate-sized graphs (in practice, ~0.8 seconds per iteration on Cora on an A100GPU).\nScaling to graphs with millions or billions of nodes could be challenging. The primary bottleneck lies in the $O(n^2)$ time and memory complexity of computing gradients over the full adjacency matrix. However, it is important to note that this complexity is not unique to our approach but is a **general limitation of edge attack algorithms that operate over the full edge space**. Since the search space includes all possible edge and non-edge positions, the number of potential perturbations grows quadratically with the number of nodes.\n\nWe agree that studying large-scale datasets would be valuable and will consider this in a future extension of our study.  Here, we outline several possible directions to improve scalability:\n\n(a) **mini-batch gradient**: Rather than computing the gradient over the entire graph, we can approximate it using a mini-batch of b nodes per iteration. This reduces both the time and memory complexity per iteration to O(b^2), making it feasible for large graphs. \n\n(b) **greedy & local search**: Our methodology (see line 310) is not restricted to PGD and allows alternative algorithms, such as greedy heuristics that recursively perturb one edge with the highest embedding impact. These methods can be applied to local subgraphs or a subset of edges to narrow the search space and reduce computational overhead.\n\n\nWhile these approximations trade off some optimality, they offer promising routes for handling large-scale networks.  To demonstrate feasibility, we conducted an experiment using a greedy edge deletion strategy, where the search space is restricted to existing edges, thereby leveraging graph sparsity for efficient computation.\n\n\n- Dataset: ogbn-arxiv (169,343 nodes, 1,166,243 edges, 128-dimensional features)\n- Perturbation: 20 edge deletions\n- Runtime: 9 minutes 53 seconds\n- Memory usage: 1182.85 MB\n- Average embedding perturbation: 2.43 (random baseline produces 1.23)\n\nThese results show that scalable approximations of our method can nearly double the magnitude of embedding perturbations compared to random baselines, enabling efficient edge attacks on large graphs. Due to time and computational resource constraints, we were unable to include additional large-scale datasets. We will include a more detailed discussion on scalability in our revised version.\n\n> (2) The framework requires accurate estimation of the signal autocorrelation matrix, which may be challenging in real-world scenarios with limited or noisy data.\n\nWe thank the reviewer for raising the concern about estimating the signal autocorrelation matrix. When graph signals are fully accessible, straightforward computation on the empirical autocorrelation is sufficient and reliable. In some challenging settings, such as when some node features are unobservable or corrupted by noise, more advanced statistical estimation techniques can be employed to obtain robust and accurate estimates.  For example, the graphical lasso estimator can be used to denoise the autocorrelation matrix, leveraging the assumption that the correlation structure among signals exhibits a certain level of sparsity. **We have already included a discussion of these alternative estimation strategies in Appendix C5** and, due to space limit here, kindly refer the reviewer there for a detailed discussion about alternative estimation methods.\n\n> (3) Evaluation is limited to homophily graphs\n\nWe acknowledge that some other methodologies, such as DICE, are explicitly based on the homophily assumption.  In Section 4, we compare, under a homophilic setting (as captured by the cSBM), that our method exhibits similar behavior to DICE, even without access to ground-truth labels. However, we would like to emphasize that **our framework does not rely on the homophily assumption**. That setting is merely used as an easy-to-compare illustrative example. All of our theoretical results hold generally and are directly applicable to heterophilic or mixed-type graphs. The methodology, including the optimization formulation and the Prob-PGD algorithm, **remains valid regardless of the underlying homophily or heterophily structure**. \n\nTo further clarify this point and address the concern, we include additional experiments on two benchmark heterophilic datasets: Chameleon and Squirrel. These datasets are known to exhibit low homophily scores and present challenges for traditional GNNs, and we adopt H2GCN, a GCNN model specifically designed for heterophilic graphs.\n\nH2GCN model details:\nGiven a node feature matrix X and graph adjacency matrix A, H2GCN constructs node representations as $[X; AX, A^2X],$\nwhich is obtained by concatenating node feature X, aggregated feature with 1-hop AX, and aggregated with 2-hop neighbor $A^2X$. Such node embeddings are then passed through a multi-layer perceptron (MLP) to perform classification.\n\n\nWe pre-train 10 models and report the mean+std of the prediction accuracy and embedding perturbation under different attack methods (1k edge perturbations for both datasets):\n\n(a) Chameleon dataset:\n- Nodes: 2277 (train:1092, val:729, test:456)\n- Edges: 36101\n- Feature dimension: 2325\n- Classes: 5\n- Homophily score: 0.23 (low, heterophilic)\n\n| Method      | Accuracy (%)           | Embedding Perturbation $\\|\\cdot\\|_F$ |\n|-------------|------------------------|--------------------------------------|\n| Unperturbed (Test) | 55.92 ± 1.47     | -                                    |\n| Random      | 54.23 ± 1.16           | 136.65 ± 4.27                        |\n| Wst-PGD     | 54.87 ± 1.51           | 3099.12 ± 0                          |\n| Prob-PGD    | **52.96 ± 1.38**       | **6392.17 ± 0**                      |\n\n(b) Squirrel dataset:\n- Nodes: 5201 (train:2496, val:1664, test:1041)\n- Edges: 217073\n- Feature dimension: 2089\n- Classes: 5\n- Homophily score: 0.22 (low, heterophilic)\n| Method             | Accuracy (%)           | Embedding Perturbation $\\|\\cdot\\|_F$ |\n|--------------------|------------------------|--------------------------------------|\n| Unperturbed        | 50.38 ± 0.39           | -                                    |\n| Random             | 47.91 ± 0.47           | 578.92 ± 3.86                        |\n| Wst-PGD            | 48.48 ± 0.73           | 1127.21 ± 0.00                       |\n| Prob-PGD           | **48.28 ± 0.73**       | **3908.26 ± 0.00**                   |\n\nIn both heterophilic graphs, we observe that Prob-PGD consistently induces the largest embedding perturbation compared against the baselines. On the squirrel dataset, despite producing the largest embedding change, Prob-PGD does not result in the largest drop in prediction accuracy. We comment that this is not unexpected given that Prob-PGD is a **task-agnostic attack** that does not optimize for misclassification directly. Instead, it targets maximal disruption in node embeddings. As such, the relationship between embedding perturbation and accuracy degradation is not always linear or straightforward. For a more detailed discussion on this phenomenon, we refer the reviewer to our response to Reviewer f7yR.\n\n>(4)  adversarial defense against structural attacks?\n\nWe thank the reviewer for the suggestion. In response, we evaluate and compare different attack methods on ElasticGNN [4], a robust GNN model that incorporates a locally adaptive smoothness regularization to enhance resistance against adversarial perturbations. We report results averaged over 10 independent runs:\n\n| Method       | Accuracy (%)       |\n|--------------|--------------------|\n| Test         | 81.57 ± 0.26       |\n| Random       | **80.20 ± 0.77**       |\n| Wst-PGD      | 80.79 ± 0.27       |\n| Prob-PGD     | 81.63 ± 0.46       |\n\n\nAs shown in the results, the random baseline leads to the lowest post-attack accuracy, while our proposed method, Prob-PGD, results in the smallest performance drop. This indicates that Prob-PGD is currently less effective at degrading ElasticGNN's performance compared to other attack strategies.\n\nOne possible explanation is that ElasticGNN is inherently robust to the class of perturbations introduced by Prob-PGD, which on homophilous graphs tends to behave like DICE and blur the community structure by connecting nodes from different classes. ElasticGNN, however, is particularly designed to tolerate such adversarial perturbations (see Section 4.3 in [4])\n\nThis alignment between the behavior of ElasticGNN and Prob-PGD perturbations suggests that our attack stability framework may also **provide insight into why certain defense strategies are effective**. We plan to include more empirical studies to further explore and explain these connections.\n\nWe emphasize that our current theoretical framework is primarily designed to analyze the stability of standard GNNs, rather than robustified architectures like ElasticGNN. While evaluating such models is valuable, extending our analysis to cover robust architectures would require separate, model-specific analysis. We consider this a compelling direction for future work.\n\nWe would like to thank the reviewer again for their comments. We remain at their disposal during the discussion period and, in case the responses above addressed most concerns from the original review, would appreciate if the reviewer could kindly consider increasing the score/confidence in light of this."}, {"review_id": "TbnibNyTsV", "reviewer": "Reviewer_BGAr", "summary": "This paper investigates the stability of Graph Convolutional Neural Networks (GCNNs) to small perturbations in the graph structure. The theoretical analysis in this paper is performed from a probabilistic perspective, which accounts for the underlying distribution of graph signals and perturbations. The paper includes comprehensive empirical evaluations, including testing robustness against adversarial attacks, which emphasize the importance of considering data distributions in stability analysis.", "questions": "I suggest that the authors also review the recent literature on coVariance neural networks (VNNs), which study data-driven perturbations to covariance graphs in GCNNs and are perhaps more closely related to their work.\n\n[a] Sihag, Saurabh, et al. \"coVariance neural networks.\" Advances in neural information processing systems 35 (2022): 17003-17016.\n\n[b] Cavallo, Andrea, Mohammad Sabbaqi, and Elvin Isufi. \"Spatiotemporal covariance neural networks.\" In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 18-34. Cham: Springer Nature Switzerland, 2024.\n\n[c] Cavallo, A., Navarro, M., Segarra, S., & Isufi, E. (2025, April). Fair covariance neural networks. In ICASSP 2025-2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (pp. 1-5). IEEE.", "limitations": "I did not find an explicit discussion on limitations of this work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper provides a probabilistic scenario to stability of GCNNs, which is likely to provide more realistic insights relative to the worst case stability analyses in the literature. \n2. Theoretical results on stability are rigorous and cover multi-layer GCNNs.\n3. The theory presented in this paper further motivates a distribution-aware attack algorithm Prob-PGD, which produces greater performance degradation relative to other baselines. \n\n**Weaknesses**\n\nNo notable weaknesses.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for bringing this relevant line of work to our attention. CoVariance Neural Networks (VNNs) use the covariance matrix of graph signals (i.e., the covariance graph) as the underlying graph structure for GCNNs.\n\nIn the stability analysis of VNN [a,b,c], the authors consider perturbation on the covariance graph  $C-\\hat{C}$, which arises due to estimation errors from a finite number of graph signal samples. These perturbations are data-dependent, as they depend on the underlying distribution of graph signals. The corresponding output stability is assessed using a worst-case metric, measured via the spectral (operator) norm $\\|H(C)-H(\\hat{C})\\|$ between the perturbed and original covariance graph filters. \n\nIn contrast, our work considers more general GCNNs, and the graph perturbations are also generic. The data-dependence in our stability analysis arises from the notion of stability itself, where we show that our introduced metric, the expected embedding perturbation, depends on the graph signal distribution. We summarize the key differences as follows:\n\n\n| Category         | Stability [a, b, c]               | Ours                            |\n|------------------|-----------------------------------|----------------------------------|\n| Perturbation     | Estimation error                  | Generic edge perturbation       |\n| Stability Metric | Worst-case                        | Average-case                     |\n| Architecture     | Covariance-based GCNNs            | General GCNNs                    |\n\n\n\nDespite these differences, both approaches adopt a distribution-aware perspective and highlight connections between network stability and the second-order statistics of graph signals. This opens the door to interesting directions for combined research. For example, our probabilistic framework could complement the VNN line of research by offering an average-case sensitivity analysis of VNNs, in which both the perturbation model and the notion of stability are tied to the underlying distribution of graph signals. Understanding stability from this perspective could be mathematically interesting and potentially lead to more representative and interpretable measures of robustness for VNNs.\n\nWe will include a more detailed discussion and comparison to VNN-related works [a, b, c] in the revised manuscript and highlight the conceptual and methodological connections."}, {"review_id": "GrsqWMFYDO", "reviewer": "Reviewer_6sQf", "summary": "This paper studies how the perturbation on the graph would affect the output embeddings from a probabilistic view.  It studies the relation of the expected embedding perturbation with the input feature distribution and the changes in the graph structure.  The authors also designed a fast algorithm using projected gradient descent to find the adversarial examples with larger embedding pertubations compared to the baseline, as shown by the empirical results.", "questions": "Some minor suggestions:\n\n- The legend of Figure 1 can be put outside of the contents.\n\n- In line 164, it should be $S_p$. \n\n- Corollary 3 seems to be incomplete.\n\n- The main contribution part in section 1 can be more concise.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. Comprehensive probabilistic bounds are derived to show the factors contributing to the embedding perturbation.\n2. The experiment results show a significantly larger perturbation compared to the baseline.\n\nWeakness:\n\nThe motivation is not strongly established.  I wonder what is the real-world application of the research.  In another word, why is this topic important?", "was_revised": true, "final_justification": "I keep my original score and my concerns are addressed.", "rebuttal": "We thank the reviewer for the helpful suggestions, and we will address them correspondingly in our revised manuscript.  We would like to explain a bit why this topic is important.  \n\nWhile GCNNs have achieved remarkable success across various domains, their deployment in practice faces a critical challenge: the graph structure at inference time may differ from what the model was trained on, due to either noise, dynamics, or adversarial manipulations. Retraining models to adapt to each variation is often impractical due to time, cost, and data constraints. This makes it essential to understand and quantify how robust pre-trained GCNNs are to such perturbations.\n\nThe following practical scenarios could further help explain this need:\n\n**Defensive robustness** in social media platforms: Pre-trained graph-based misinformation detectors may be targeted by adversarial agents (e.g., bots) who add or delete edges (friendships, follows) to evade detection. Understanding embedding stability helps assess whether such detectors are reliable under manipulative behaviors.\n \nIn **dynamic environments** such as communication networks, traffic systems, or recommender systems, graph structures evolve over time. Our framework enables practitioners to assess whether a model trained on an earlier graph snapshot can still be used effectively as the graph changes, which provides a critical tool for model updating planning."}, {"review_id": "5ZgLCm4zHc", "reviewer": "Reviewer_MeYi", "summary": "The paper departs from the prevailing worst-case view of GNN robustness and introduces a distribution-aware framework that measures expected embedding perturbations when edges are added or deleted at test time. Closed-form expressions are obtained for graph filters, and depth-dependent upper bounds are derived for multilayer GNNs. The theory yields structural insights that explain which edge sets hurt most and motivates a new projected-gradient attack, Prob-PGD, that maximises expected embedding change. Experiments on six benchmark graphs and three downstream tasks demonstrate that Prob-PGD produces larger embedding shifts and bigger accuracy drops than strong baselines, confirming the practical value of the analysis.", "questions": "NA", "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**\n\n1. First probabilistic stability framework for GNNs, giving a realistic alternative to worst-case analysis.\n\n2. Clear structural insight: links autocorrelation and edge-intersection patterns to vulnerability, rationalising prior heuristic attacks.\n\n3. Prob-PGD, derived directly from theory, consistently outperforms random and worst-case PGD in both embedding and task metrics.\n\n**Weaknesses**\n\n1. Focuses only on evasion (test-time) attacks; poisoning scenarios are not studied.\n\n2. Experiments use small graphs; scalability to million-node graphs is untested.", "was_revised": true, "final_justification": "I think my score is reasonable.", "rebuttal": ">(1) poisoning attack?\n\nWe appreciate the reviewer’s comment. Our focus on evasion attacks is deliberate, as our theoretical framework is built on understanding the inference-time stability, which is directly related to test-time behavior. While poisoning attacks are indeed important, they operate through fundamentally different mechanisms.\n\nTo clarify the distinction:\n - Evasion attacks manipulate the test data while keeping the model parameters fixed.\n - Poisoning attacks perturb the training data to influence the learned model parameters, which subsequently affects test-time performance.\n\nConsequently, the relevant notions of stability also differ. **Evasion attacks are closely connected to inference-time (test-time) stability**, which is the focus of our study. (For a more detailed explanation of the importance of this topic, we refer the reviewer to our response to Reviewer 6sQf.) In contrast, **poisoning attacks are more closely related to algorithmic stability**, i.e., how sensitive a machine learning algorithm is to small changes in the training data [1]. While there may be conceptual connections between these two stability notions, they pertain to distinct aspects of the learning process.\n\nGiven this distinction, our theoretical results on inference-time stability do not directly extend to poisoning scenarios. \n\nDespite it being outside our theoretical framework, we conduct the following experiment to evaluate empirically how Prob-PGD performs under a poisoning attack.\n\n- Set up:\nWe use a GCN for graph classification on the MUTAG dataset. In the poisoning attack, we randomly choose 20% of the graphs from the training set and perturb 5% of their edges using different attack algorithms. We train GCN models (with fixed hyperparameters) on these poisoned datasets separately and report the test accuracy averaged over 10 runs.\n- Results :\n| Method       | Accuracy (%) |\n|--------------|--------------------|\n| Unperturbed  | 69.21       ±1.21   |\n| Random       | 66.58        ±1.21   |\n| Wst-PGD      | 70.79         ±2.19   |\n| Prob-PGD     | 69.47         ±2.93   |\n\nThese results suggest that the GCN model maintains a certain level of robustness to poisoning attacks, where test accuracy is not significantly degraded across methods. However, we emphasize that **these empirical observations fall outside the scope of our theoretical framework, and interpreting them rigorously would require new theoretical developments**. We thank the reviewer for encouraging this important line of inquiry, and we view it as a promising direction for future research.\n\n[1] Saurabh Verma, Zhi-Li Zhang, Stability and Generalization of Graph Convolutional Neural Networks, ACM KDD'19\n\n\n>(2) scalability to large graphs?\n\nWe thank the reviewer for the question regarding scalability. Our algorithm Prob-PGD is efficient on moderate-sized graphs(in practice, ~0.8 seconds per iteration on Cora on an A100GPU).\nScaling to graphs with millions or billions of nodes could be challenging. The primary bottleneck lies in the $O(n^2)$ **time and memory complexity of computing gradients over the full adjacency matrix**. However, it is important to note that this complexity is not unique to our approach but is a **general limitation of edge attack algorithms that operate over the full edge space**. Since the search space includes all possible edge and non-edge positions, the number of potential perturbations grows quadratically with the number of nodes.\n\nWe agree that studying large-scale datasets would be valuable and will consider this in a future extension of our study.  Here, we outline several possible directions to improve scalability:\n\n(a)**mini-batch gradient**: Rather than computing the gradient over the entire graph, we can approximate it using a mini-batch of b nodes per iteration. This reduces both the time and memory complexity per iteration to O(b^2), making it feasible for large graphs. \n\n(b)**greedy&local search**: Our methodology (see line 310) is not restricted to PGD and allows alternative algorithms, such as greedy heuristics that recursively perturb one edge with the highest embedding impact. These methods can be applied to local subgraphs or a subset of edges to narrow the search space and reduce computational overhead.\n\n\nWhile these approximations trade off some optimality, they offer promising routes for handling large-scale networks.  To demonstrate feasibility, we conducted an experiment using a greedy edge deletion strategy, where the search space is restricted to existing edges, thereby leveraging graph sparsity for efficient computation.\n\n\n- Dataset: ogbn-arxiv (169,343 nodes, 1,166,243 edges, 128-dimensional features)\n- Perturbation: 20 edge deletions\n- Runtime: 9 minutes 53 seconds\n- Memory usage: 1182.85 MB\n- Average embedding perturbation: 2.43 (random baseline produces 1.23)\n\nThese results show that scalable approximations of our method can nearly double the magnitude of embedding perturbations compared to random baselines, enabling efficient edge attacks on large graphs. Due to time and computational resource constraints, we were unable to include additional large-scale datasets. We will include a more detailed discussion on scalability in our revised version."}, {"review_id": "G1njkNfitE", "reviewer": "Reviewer_f7yR", "summary": "The paper introduces a probabilistic framework for analyzing the embedding stability of Graph Convolutional Neural Networks (GCNNs). Unlike prior work, which focuses on worst-case perturbations, this paper shifts the focus to expected embedding perturbations. The authors use this formalism to assess the interplay between perturbations, node features and graph topology. They then use this insight to propose a gradient-based perturbation attack to maximally effect the GCNN output, and validate on a range of benchmarks.", "questions": "my questions are written within the weaknesses section. I mainly want to understand why some results aren't great and whether stronger baselines or comparisons make sense. I am also interested in getting a better intuition for the size of the bound in Theorem 2.", "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": "**Strengths**\n\n- The limitations of prior works in terms of focusing on worst-case perturbations is clearly outlined and addressed with their probabilistic approach. This limitation is problematic to the community so an attempt to address this is impactful. The study on the contextual stochastic block model (cSBM) offers both theoretical and empirical justification for the heuristic perturbation strategies observed in prior work.\n\n- The theoretical contributions of the paper are very compelling. The theoretical contributions alone are a substantial contribution. For example the exact characterization of the stability of graph filters and the analysis and connections between perturbations, node features and graph topology.\n\n**Weaknesses**\n\n- Some of the results are inconclusive about the benefits of the approach. For example, Prob-PGD causes a larger degradation on MUTAG than random with a GCN but not with a GIN. Is there any reason for this? Given that results like this highlight the strong dependance on the model architecture, the generalization of the approach may not be strong and thus be less impactful. It might be worth at least showing that your perturbation perturbs the embedding more than a random perturbation for MUTAG with GIN. A similar analysis has also been performed in [1] and would at least show that the reason for this result is some complexity in the label space/training rather than the attacks ability to maximize embedding distance after perturbation. \n\n- As we increase the number of layers, the bound in Theorem 2 gets worse with these recursive constants due to dependencies and compounding nonlinearities. It may be useful to have some toy experiments with real-datasets (eg. MUTAG) to get a sense of the size of these constants. How bad is this bound with increasing layers? \n\n- Papers like [1] and [2] have discussed pseudometrics between graphs. [1] provides an upper-bound on the embedding distance with respect to edge deletions. I understand your method can provide a probabilistic description of the stability unlike these approaches. But I don't necessarily see why an attack based on your measure would be better. Additionally, you could also use standard structural measures to do the attacks (eg. Edge Betweenness Centrality.) Perhaps comparing to stronger baselines may be useful for assessing the benefits of the approach.\n\n[1] Chuang et al. Tree Mover’s Distance: Bridging Graph Metrics and Stability of Graph Neural Networks. NeurIPS 2022. \n\n[2] Rauchwerger et al. Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs. ICLR 2025.", "was_revised": true, "final_justification": "my accept remains after reading the rebuttal", "rebuttal": "> (1) Some of the results are inconclusive about the benefits of the approach. For example, Prob-PGD causes a larger degradation on MUTAG than random with a GCN but not with a GIN. Is there any reason for this?\n\nWe thank the reviewer for the thoughtful observation. To address this concern, we now report in Table 1 **both classification accuracy and embedding perturbation magnitude ** (measured by the Frobenius norm), averaged over 10 independently trained models. This enables a clearer comparison of the attack strength across different architectures.\n\n| Dataset  | Method   | GCN Acc. (%)       | GIN Acc. (%)       | SGC Acc. (%)       | GCN ebd. ($\\|\\cdot\\|_F$) |  GIN  ebd ($\\|\\cdot\\|_F$)|  SGC ebd  ($\\|\\cdot\\|_F$)|\n|----------|----------|--------------------|---------------------|---------------------|------------------|-------------------|-------------------|\n| **MUTAG** | Unpert.  | 70.00 ± 2.68        | 82.89 ± 4.60         | 68.95 ± 1.58         | -                | -                 | -                 |\n|          | Random   | 73.16 ± 1.05        | **70.53 ± 4.82**         | 72.89 ± 1.21         | 2.24 ± 0.15      | 28.62 ± 2.34       | 3.57 ± 0.17        |\n|          | Wst-PGD  | 69.21 ± 2.37        | 76.32 ± 8.15         | 68.16 ± 1.42         | 1.95 ± 0.13      | 37.47 ± 9.47       | 3.11 ± 0.16        |\n|          | Prob-PGD | **42.89 ± 4.86**    | 76.58 ± 8.02         | **41.58 ± 3.87**     | **3.09 ± 0.16**  | **96.26 ± 11.39**  | **5.21 ± 0.25**    |\n| **ENZYMES** | Unpert.  | 56.33 ± 3.10        | 56.75 ± 2.99         | 54.75 ± 3.48         | -                | -                 | -                 |\n|          | Random   | 49.58 ± 3.93        | 45.83 ± 2.64         | 45.50 ± 2.94         | 15.3 ± 0.7       | 81.3 ± 11.3        | 36.4 ± 1.2         |\n|          | Wst-PGD  | 52.58 ± 3.56        | 39.75 ± 3.29         | 48.75 ± 4.27         | 11.5 ± 0.5       | 264.9 ± 34.7       | 27.2 ± 0.9         |\n|          | Prob-PGD | **44.25 ± 2.09**    | **36.75 ± 4.62**     | **40.75 ± 3.83**     | **17.9 ± 0.9**   | **297.9 ± 57.1**   | **43.6 ± 1.6**     |\n| **Cora**   | Unpert.  | 80.06 ± 0.51        | 74.92 ± 1.86         | 80.33 ± 0.29         | -                | -                 | -                 |\n|          | Random   | 78.30 ± 0.82        | 71.75 ± 1.85         | 78.12 ± 0.64         | 93 ± 4           | 974 ± 496          | 136 ± 4            |\n|          | Wst-PGD  | 78.47 ± 0.44        | 73.76 ± 2.07         | 78.30 ± 0.33         | 97 ± 7           | 16901 ± 12495      | 151 ± 5            |\n|          | Prob-PGD | **77.88 ± 0.33**    | **56.67 ± 4.57**     | **77.49 ± 0.29**     | **106 ± 5**      | **43565 ± 33035**  | **160 ± 6**        |\n\n**Table 1: Prediction accuracy of GCNNs under edge perturbations produced by different methods.**\n\n\nWe observe that across all architectures and datasets, including MUTAG with GIN, our proposed Prob-PGD **consistently produces the largest embedding perturbations**, which aligns with our theoretical motivation. This confirms that Prob-PGD **effectively maximizes structural sensitivity at the representation level, independent of the model used**.\nWe note that the final **accuracy drop also depends on the task-specific decision boundary**. In particular, for GIN on MUTAG, despite Prob-PGD producing the most substantial embedding shift, the prediction degradation is less significant. This suggests that the perturbed representations remain on the same side of the classifier's (MLP’s) decision boundary, which is not unexpected for a task-agnostic embedding attack. We emphasize that a large embedding perturbation is a necessary (but not sufficient) condition for adversarial vulnerability across diverse downstream tasks, and thus offers **a general-purpose tool for assessing the model robustness**. We will include this clarification in the revision.\n\n> (2) comparison to [1,2]?\n\nWe acknowledge that alternative metrics such as those in [1,2] offer valuable insights and have their own advantages. Beyond the interpretability enabled by our probabilistic formulation, our proposed metric provides several key benefits:\n\n(a) Generality: Our metric is applicable to GCNNs with a broad range of graph filter structures, such as low-pass, high-pass, and heat diffusion filters, that could involve higher-order structures. In comparison to [1], where the analysis is tightly tailored to  GIN-style message passing, our approach provides insights into spectral GNN settings.\n\n(b) tightness for single-layer models: Most prior metrics provide only upper bounds characterization on the model stability, often due to mathematical intractability or by definition. Optimizing these upper bounds does not guarantee a strong attack. In contrast, for many single-layer GCNNs, our study yields a tight, closed-form characterization of expected embedding perturbation, which is more direct for designing effective attack strategies. \n\nWe will add a more detailed comparison with these approaches in the revised manuscript’s related work section to highlight these distinctions.\n\n> (3) Comparing to stronger baselines?\n\nWe thank the reviewer for the constructive suggestion. In response, we have included preliminary experiments incorporating centrality-based attacks as an additional baseline.  Specifically, we compare the classification accuracy and embedding norm perturbation under various attacks on the ENZYMES dataset using SGC and GIN models:\n\n**ENZYMES dataset using SGC model.**\n\n| Method      | Accuracy (%)       | Embedding pert. ($\\|\\cdot\\|_F$) |\n|-------------|--------------------|-------------------------------|\n| Test        | 53.75 ± 3.44       | -                             |\n| Random      | 47.58 ± 3.38       | 38.14 ± 1.29                  |\n| Centrality  | **34.17 ± 2.58**       | **85.63 ± 2.70**                  |\n| Wst-PGD     | 48.42 ± 2.90       | 28.13 ± 0.98                  |\n| Prob-PGD    | 43.08 ± 3.59    | 45.72 ± 1.45                 |\n\n\n---\n\n**ENZYMES dataset using GIN model.**\n\n| Method             | Accuracy (%)           | Embedding pert. $\\|\\cdot\\|_F$ |\n|--------------------|------------------------|--------------------------------------|\n| Unperturbed  | 56.58 ± 4.19           | -                                    |\n| Random             | 45.75 ± 3.90           | 118.12 ± 7.37                        |\n| Centrality    | 41.58 ± 2.43           | 83.00 ± 4.55                         |\n| Wst-PGD            | 38.67 ± 4.64           | 380.03 ± 20.75                       |\n| Prob-PGD           | **37.17 ± 3.86**       | **492.80 ± 42.41**                   |\n\nAs shown in the above results, both centrality-based attacks and Prob-PGD produce competing results, leading to significantly larger embedding shift and accuracy drop than other baselines. We also note an important distinction: centrality-based attacks are distribution-independent, and thus their effectiveness can vary with changes in the underlying feature distribution. We will include more empirical studies with stronger baselines in the revision, together with a more detailed analysis to better interpret the experimental results.\n\n> (4) Tightness of the bound in Theorem 2?\n\nWe thank the reviewer for this constructive suggestion. While we did not include such an empirical analysis in the current response due to time constraints, we agree that it is an important direction to understand the behavior of the bound with increasing depth. We plan to include empirical results (e.g., similar to Figure 5 from [1]) in the revision or during the author-response discussion phase to illustrate how the bound scales with depth and to provide insight into its tightness."}]

Author rebuttal:

Meta-review: This work introduces a distribution-aware framework for analyzing the stability of graph convolutional neural networks to small graph topology perturbations with a probabilistic flavor. All the referees were mostly positive about this submission, and the rebuttal helped to improve some specific points of the paper. I recommend to the authors to carefuly implement every point raised by the referees in the camera ready version. I recommend acceptance to NeurIPS 2025.
Decision: Accept (poster)