acceptodds
Under review as a conference paper at ICLR 2027

Adversarial Stability of Deep GCNs under Adam: Worst-Case Bounds and Residual-Path Diagnostics

Abstract

The adversarial generalization of deep graph convolutional networks (GCNs) trained with Adam remains theoretically undercharacterized. For sampled Adam updates, we trace graph propagation through both moment histories and derive explicit architecture-dependent stability bounds for scalar-readout vanilla and residual GCNs. For vanilla GCNs, we give an explicit worst-case construction with an exponential-in-depth lower bound on loss smoothness. Isolating the spectral contribution in Adam’s stability bound yields a depth scale that is doubly logarithmic in sample size. We call the rapid depth-driven growth of the bound stability-bound collapse. A residual-path decomposition identifies how the architecture enters the stability bound. Under controlled expansion, the temporal accumulation factor grows linearly with the number of updates, while the remaining factors retain their architecture and depth dependence. An auxiliary local result gives sufficient conditions for positive directional curvature, and an expected-graph calculation describes homophily-dependent spectral depth scales for a seven-community stochastic block model. Experiments on five benchmarks examine the associated depth and perturbation trends. Averaged over ten runs, residual GCNs show smaller increases in adversarial cross-entropy gaps with depth than vanilla GCNs on Cora and CiteSeer. Source code is available at https://anonymous.4open.science/r/AdvStab-GCN.

Primary area:
learning theory
Keywords:
Graph convolutional networks, adversarial generalization, spectral amplification factor, local curvature

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_sCBjOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies algorithmic stability and expected adversarial generalization for deep graph convolutional networks trained with Adam. It explicitly tracks both moment histories and derives architecture-dependent bounds for vanilla and residual GCNs. Additional analyses address worst-case depth-dependent smoothness, residual-path Jacobians, local directional curvature, and spectral depth diagnostics. Experiments examine generalization gaps and optimization statistics across network depths and report smaller CE-gap increases for residual GCNs on Cora and CiteSeer.

Critical strengths
  1. Explicitly tracking both Adam moment histories is potentially valuable. The analysis addresses a relevant extension of GCN stability theory and exposes how architecture-dependent gradient factors enter the optimizer’s stability recursion. This provides a useful framework for studying the interaction between graph propagation and adaptive optimization.

  2. The empirical reporting is informative and appropriately qualified. The main comparisons report results over ten runs and present accuracy and optimization diagnostics alongside generalization gaps. The authors explicitly acknowledge the theoretical–experimental differences and distinguish growth of an upper bound from actual performance deterioration.

Critical weaknesses
  1. The applicability of the guarantees and their connection to the empirical observations remain limited. Appendix C discusses differentiability through Danskin's theorem, but uniform parameter smoothness of the maximized adversarial loss remains an assumption. Smoothness of the fixed-perturbation losses does not generally establish this property. A concrete, nontrivial graph-attack setting with a controlled smoothness constant would make the scope of the guarantees clearer.

    The main theorems concern sampled Adam updates on a maximized adversarial loss, whereas the depth experiments use full-batch training with perturbations generated once before training. The theoretical absolute expected generalization gap also differs from the empirical average of absolute train–test gaps. The authors explicitly acknowledge these distinctions and provide complementary diagnostics, including sensitivity to nearby initializations. These diagnostics do not directly measure sample-replacement stability or establish a quantitative connection to the reported CE-gap trends. This limits the explanatory evidence, rather than contradicting the conditional theorems.

  2. The connection between the residual-path analysis and the observed residual advantage remains limited. Proposition 5 establishes a smaller path-averaged squared-norm proxy in the expansive regime, while Remark 27 explicitly distinguishes this proxy from the full-network Jacobian and loss smoothness. The analysis does not establish when this proxy advantage translates into a smaller complete stability bound or quantitatively explains the observed CE-gap trends. This limits the explanatory contribution, rather than demonstrating an error in the conditional results.

Questions for authors
  1. Appendix C discusses differentiability through Danskin’s theorem. Can the authors establish a uniform parameter-smoothness constant for a nontrivial graph-attack setting, with explicit dependence on depth and the attack budget?

  2. Under what verifiable conditions does the path-average advantage in Proposition 5 translate into a smaller complete stability bound for ResGCN, and do the reported measurements support those conditions?

Reviewer_BzT9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the adversarial stability and generalization of deep GCNs trained with Adam. The authors recognize that existing stability analyses mainly consider SGD and do not fully account for how graph propagation interacts with Adam’s accumulated gradient statistics. They compare training runs that differ in one labeled example and track how the resulting differences propagate through model parameters and Adam’s first- and second-moment estimates. This analysis yields architecture-dependent generalization bounds for vanilla and residual GCNs under structural and feature perturbations. The paper also constructs a worst-case example in which loss smoothness grows exponentially with depth and examines how this contributes to rapid growth of the stability bound. For residual GCNs, the authors decompose the network Jacobian into paths of different lengths to characterize their contributions to sensitivity. They also conduct additional analyses of local directional curvature and homophily-dependent spectral factors. Experiments on five benchmarks and synthetic graphs compare architectures, optimizers, depths, and perturbation budgets, reporting smaller depth-related increases in train–test loss gaps for residual GCNs in several settings, alongside measurements of predictive accuracy and optimization dynamics.

Critical strengths
  • The paper studies a relevant and fundamental problem: how network depth and Adam’s gradient history jointly affect GCN training stability.

  • The experiments cover multiple datasets, GCN architectures, optimizers, and random seeds.

Critical weaknesses
  • The experiments do not directly test the training procedure analyzed by the theory. The main bounds concern sampled Adam updates on a maximized adversarial loss, while the main experiments use full-batch training on attacks constructed once before training. This makes it difficult to determine which theoretical conclusions the experiments support.

  • The theoretical results do not clearly establish when residual GCNs should be more stable than vanilla GCNs. Both architectures share the same form of stability bound, and the shorter-path analysis does not establish a tighter bound for the full residual network. Rapid growth of an upper bound also does not establish that actual training stability deteriorates.

  • The applicability beyond GCN-style architectures is not established. The analysis relies on a fixed graph propagation operator, and the experiments compare closely related GCN variants. Although this is consistent with the paper’s stated scope, it leaves unclear which findings reflect Adam’s behavior more generally.

Questions for authors
  • Which experimental results directly support the main stability bounds? Please explain how the analysis connects to full-batch training on fixed attacked inputs. It would help to see more direct evidence from a controlled experiment that follows the theoretical setup, including measuring the effect of replacing a single training example.

  • Under what conditions does the residual GCN obtain a tighter stability bound than the vanilla GCN? Please clarify how shorter residual paths improve the bound for the full network, and whether the predicted bound growth corresponds to a measurable increase in training sensitivity.

  • Which findings extend beyond GCN-style propagation? Please distinguish results that apply generally to Adam-trained models from those that require a fixed graph propagation operator. An additional comparison using GraphSAGE or GAT would help assess whether the observed depth and residual-connection trends extend beyond this model family.

Reviewer_41MfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The main contribution of the paper is a theoretical analysis of training stability of graph convolutional networks under the Adam optimiser. Theoretical results (adversarial generalisation bounds) are derived for both vanilla and residual models, which are then validated with empirical experiments.

Critical strengths
  • The paper tackles an open and important theoretical issue in the training of graph machine learning models;
  • Unlike many studies in the literature, the analyses cover both structural and feature perturbation;
  • The geometric analysis in 4.3 represents an interesting direction as well.
Critical weaknesses
  • One main weakness is the organisation and presentation of the paper requires significant improvement: for example, Sec 3.1 (“Perturbation Constants and Spectral Amplification”) presents a large number of concepts and definitions without proper motivation, which is difficult to understand and follow; attack objectives and budgets are key information in the problem setting and in my view should not be completely left to Appendix; the main text frequently refers to different sections in Appendix which makes reading rather difficult. In general, the paper is mathematically dense but lacks a clear roadmap, which makes it rather difficult to follow the progression of ideas.
  • Related to the above, the theoretical results come without appropriate interpretations: for example, no explanation was provided on the generalisation bound in Theorems 2 and 3 and it is unclear what is the trade-off (if any) among the large number of factors involved.
  • Experimental results are presented with minimum discussion, which makes it difficult for the reader to appreciate their value in validating the theoretical analyses.
  • It is unclear what the implications of the theoretical analyses are: can they inform the training process, or defence against adversarial perturbation in practice? These should be properly discussed to justify the value of the theoretical results.
Questions for authors
  • Given that the paper discussed adversarial attacks and classifies them as inference-time perturbation, can the authors discuss theoretical analysis of stability against perturbation at inference-time (after model training) as well just for completeness? See [1-3] below for a few recent examples.
  • Introduction present three questions while the experimental section presents four; can these be better aligned?
  • The paper focuses on worst-case bounds, which can be overly conservative (see [3] below for a recent study on a probabilistic alternative, despite the different setting there). Can the authors elaborate on this?
  • The paper seems to focus on node classification as the task. Can the analysis be generalised to other graph ML tasks such as graph classification?

References

[1] Gama et al., “Stability properties of graph neural networks,” IEEE TSP, 2020.

[2] Levie et al., “Transferability of spectral graph convolutional neural networks,” JMLR, 2021.

[3] Zhang et al., “On the stability of graph convolutional neural networks: A probabilistic perspective,” NeurIPS, 2025.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.