Collective Certified Robustness against Graph Injection Attacks

arXiv:2403.01423v1 Announce Type: cross
Abstract: 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 …

abstract arxiv attacks collective cs.cr cs.lg gnns graph node nodes paper performance research robustness sample set type wise