Adaptive Branch Specialization in Spectral-Spatial Graph Neural Networks for Certified Robustness
This work addresses certified robustness for graph neural networks, which is a critical issue for applications in security-sensitive domains, though it appears incremental as it builds on existing spectral-spatial architectures.
The paper tackles the problem of certified robustness in graph neural networks by specializing spectral and spatial branches to resist different types of attacks, achieving state-of-the-art node classification accuracy and tighter certified robustness on real-world benchmarks.
Recent Graph Neural Networks (GNNs) combine spectral-spatial architectures for enhanced representation learning. However, limited attention has been paid to certified robustness, particularly regarding training strategies and underlying rationale. In this paper, we explicitly specialize each branch: the spectral network is trained to withstand l0 edge flips and capture homophilic structures, while the spatial part is designed to resist linf feature perturbations and heterophilic patterns. A context-aware gating network adaptively fuses the two representations, dynamically routing each node's prediction to the more reliable branch. This specialized adversarial training scheme uses branch-specific inner maximization (structure vs feature attacks) and a unified alignment objective. We provide theoretical guarantees: (i) expressivity of the gating mechanism beyond 1-WL, (ii) spectral-spatial frequency bias, and (iii) certified robustness with trade-off. Empirically, SpecSphere attains state-of-the-art node classification accuracy and offers tighter certified robustness on real-world benchmarks.