Despite significant advancements in Graph Neural Networks (GNNs), adaptive attacks pose ongoing challenges to their robustness. Certified robustness through randomized smoothing offers provable guarantees but suffers from a severe accuracy-robustness trade-off, limiting its practical applicability. To bridge this gap, we introduce AuditVotes, the first framework that achieves both high clean accuracy and strong certified robustness.
AuditVotes seamlessly integrates two novel components into the randomized smoothing pipeline: (1) graph rewiring augmentation, which denoises randomized graphs to recover data quality, and (2) conditional smoothing, which filters low-confidence votes to ensure prediction consistency. We establish a novel theoretical result proving that certified robustness is preserved under arbitrary filtering functions.
Designed for inductive learning, our framework generalizes to unseen nodes and broadly applies to other smoothing schemes, including de-randomized smoothing for graphs and Gaussian smoothing for images. Extensive experiments demonstrate that AuditVotes delivers substantial improvements: on the Cora-ML dataset under 20-edge attacks, it enhances clean accuracy by 437.1% and certified accuracy by 409.3%, while maintaining comparable runtime to vanilla smoothing. As a widely applicable and efficient plug-in, AuditVotes offers higher accuracy and stronger guarantees, enabling practical and certifiably robust GNNs in security-sensitive domains.
Blogger's Review: The innovation of AuditVotes lies in its combination of graph rewiring and conditional smoothing, which significantly enhances both the robustness and accuracy of GNNs. The theoretical foundation and experimental results indicate its potential in security-sensitive applications, warranting further exploration and practical implementation. The specific filtering mechanisms pave the way for new directions in robustness research.