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

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.