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