On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective

(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?

We 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.

Table 1: Prediction accuracy of GCNNs under edge perturbations produced by different methods.

We 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. We 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.

(2) comparison to [1,2]?

We 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:

(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.

(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.

We will add a more detailed comparison with these approaches in the revised manuscript’s related work section to highlight these distinctions.

(3) Comparing to stronger baselines?

We 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:

ENZYMES dataset using SGC model.

ENZYMES dataset using GIN model.

As 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.

(4) Tightness of the bound in Theorem 2?

We 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.

Thank you for your detailed response! I appreciate the extra effort which has gone into improving the paper. The authors have addressed my concerns and I maintain my preference for accepting the paper.

(1) poisoning attack?

We 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.

To clarify the distinction:

• Evasion attacks manipulate the test data while keeping the model parameters fixed.
• Poisoning attacks perturb the training data to influence the learned model parameters, which subsequently affects test-time performance.

Consequently, 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.

Given this distinction, our theoretical results on inference-time stability do not directly extend to poisoning scenarios.

Despite it being outside our theoretical framework, we conduct the following experiment to evaluate empirically how Prob-PGD performs under a poisoning attack.

• Set up: We 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.
• Results : | Method | Accuracy (%) | |--------------|--------------------| | Unperturbed | 69.21 ±1.21 | | Random | 66.58 ±1.21 | | Wst-PGD | 70.79 ±2.19 | | Prob-PGD | 69.47 ±2.93 |

These 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.

[1] Saurabh Verma, Zhi-Li Zhang, Stability and Generalization of Graph Convolutional Neural Networks, ACM KDD'19

(2) scalability to large graphs?

We 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). Scaling 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.

We 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:

(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.

(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.

While 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.

• Dataset: ogbn-arxiv (169,343 nodes, 1,166,243 edges, 128-dimensional features)
• Perturbation: 20 edge deletions
• Runtime: 9 minutes 53 seconds
• Memory usage: 1182.85 MB
• Average embedding perturbation: 2.43 (random baseline produces 1.23)

These 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.

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.

While 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.

The following practical scenarios could further help explain this need:

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.

In 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.

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:

(1) scalability to very large-scale graphs?

We 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). Scaling 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.

We 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:

(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.

(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.

While 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.

• Dataset: ogbn-arxiv (169,343 nodes, 1,166,243 edges, 128-dimensional features)
• Perturbation: 20 edge deletions
• Runtime: 9 minutes 53 seconds
• Memory usage: 1182.85 MB
• Average embedding perturbation: 2.43 (random baseline produces 1.23)

These 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.

(2) The framework requires accurate estimation of the signal autocorrelation matrix, which may be challenging in real-world scenarios with limited or noisy data.

We 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.

(3) Evaluation is limited to homophily graphs

We 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.

To 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.

H2GCN model details: Given a node feature matrix X and graph adjacency matrix A, H2GCN constructs node representations as $[X; AX, A^2X],$ which 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.

We 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):

(a) Chameleon dataset:

• Nodes: 2277 (train:1092, val:729, test:456)
• Edges: 36101
• Feature dimension: 2325
• Classes: 5
• Homophily score: 0.23 (low, heterophilic)

(b) Squirrel dataset:

• Nodes: 5201 (train:2496, val:1664, test:1041)
• Edges: 217073
• Feature dimension: 2089
• Classes: 5
• Homophily score: 0.22 (low, heterophilic) | Method | Accuracy (%) | Embedding Perturbation $\|\cdot\|_F$ | |--------------------|------------------------|--------------------------------------| | Unperturbed | 50.38 ± 0.39 | - | | Random | 47.91 ± 0.47 | 578.92 ± 3.86 | | Wst-PGD | 48.48 ± 0.73 | 1127.21 ± 0.00 | | Prob-PGD | 48.28 ± 0.73 | 3908.26 ± 0.00 |

In 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.

(4) adversarial defense against structural attacks?

We 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:

As 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.

One 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])

This 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.

We 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.

We 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.

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.

In 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.

In 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:

Despite 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.

We 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.