mlsanityData to 7 Oct 2026

Collective Certified Robustness against Graph Injection Attacks

arXiv 2403.01423 ↗First posted 3 Mar 2024cs.CR cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 27 of its 31 references that are in the map. First posted on arXiv 3 Mar 2024.

Builds on

27 of 31 references.

References · 27

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  5. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 633
  6. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
  7. 2020Graph Structure Learning for Robust Graph Neural Networkscited by 368
  8. 2017Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Rankingcited by 332
  9. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  10. 2020GNNGuard: Defending Graph Neural Networks against Adversarial Attackscited by 195
  11. 2022Understanding and Improving Graph Injection Attack by Promoting Unnoticeabilitycited by 62
  12. 2020Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbationcited by 57
15 more
  1. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  2. 2020GCN-Based User Representation Learning for Unifying Robust Recommendation and Fraudster Detectioncited by 53
  3. 2020Reliable Graph Neural Networks via Robust Aggregationcited by 43
  4. 2020Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothingcited by 29
  5. 2023Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directionscited by 28
  6. 2022Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learningcited by 19
  7. 2020Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbationscited by 16
  8. 2023Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networkscited by 16
  9. 2023Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debiascited by 16
  10. 2022Adversarial Camouflage for Node Injection Attack on Graphscited by 11
  11. 2022Localized Randomized Smoothing for Collective Robustness Certificationcited by 10
  12. 2023Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networkscited by 10
  13. 2023PORE: Provably Robust Recommender Systems against Data Poisoning Attackscited by 9
  14. 2023Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attackscited by 8
  15. 2020Tutorials on Advanced Optimization Methodscited by 2

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 2.

3 papers.

  1. 2024Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attackscited by 5
  2. 2025AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothingcited by 1
  3. 2025Provably Robust Adaptation for Language-Empowered Foundation Modelscited by 0