Collective Certified Robustness against Graph Injection Attacks
This work addresses the limited certifying performance of existing sample-wise methods for GNNs under attacks, making provable defense more practical for graph-based machine learning applications.
The paper tackles the problem of certifying robustness for Graph Neural Networks (GNNs) against graph injection attacks by introducing the first collective certificate that verifies multiple nodes simultaneously, achieving a certified ratio increase from 0.0% to 81.2% on the Citeseer dataset with minimal computational overhead.
We investigate certified robustness for GNNs under graph injection attacks. Existing research only provides sample-wise certificates by verifying each node independently, leading to very limited certifying performance. In this paper, we present the first collective certificate, which certifies a set of target nodes simultaneously. To achieve it, we formulate the problem as a binary integer quadratic constrained linear programming (BQCLP). We further develop a customized linearization technique that allows us to relax the BQCLP into linear programming (LP) that can be efficiently solved. Through comprehensive experiments, we demonstrate that our collective certification scheme significantly improves certification performance with minimal computational overhead. For instance, by solving the LP within 1 minute on the Citeseer dataset, we achieve a significant increase in the certified ratio from 0.0% to 81.2% when the injected node number is 5% of the graph size. Our step marks a crucial step towards making provable defense more practical.