Collective Certified Robustness against Graph Injection Attacks

Yuni Lai, Bailin Pan, Kaihuang Chen, Yancheng Yuan, Kai Zhou
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:25871-25891, 2024.

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 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 paper marks a crucial step towards making provable defense more practical. Our source code is available at https://github.com/Yuni-Lai/CollectiveLPCert.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-lai24a, title = {Collective Certified Robustness against Graph Injection Attacks}, author = {Lai, Yuni and Pan, Bailin and Chen, Kaihuang and Yuan, Yancheng and Zhou, Kai}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {25871--25891}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/lai24a/lai24a.pdf}, url = {https://proceedings.mlr.press/v235/lai24a.html}, 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 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 paper marks a crucial step towards making provable defense more practical. Our source code is available at https://github.com/Yuni-Lai/CollectiveLPCert.} }
Endnote
%0 Conference Paper %T Collective Certified Robustness against Graph Injection Attacks %A Yuni Lai %A Bailin Pan %A Kaihuang Chen %A Yancheng Yuan %A Kai Zhou %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-lai24a %I PMLR %P 25871--25891 %U https://proceedings.mlr.press/v235/lai24a.html %V 235 %X 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 paper marks a crucial step towards making provable defense more practical. Our source code is available at https://github.com/Yuni-Lai/CollectiveLPCert.
APA
Lai, Y., Pan, B., Chen, K., Yuan, Y. & Zhou, K.. (2024). Collective Certified Robustness against Graph Injection Attacks. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:25871-25891 Available from https://proceedings.mlr.press/v235/lai24a.html.

Related Material