mlsanityData to 14 Oct 2026

Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks

arXiv 2312.03979 ↗First posted 7 Dec 2023cs.LG cs.CRcited by 8

Not on the map. Why?

Abstract (arXiv)

Deep Graph Learning (DGL) has emerged as a crucial technique across various domains. However, recent studies have exposed vulnerabilities in DGL models, such as susceptibility to evasion and poisoning attacks. While empirical and provable robustness techniques have been developed to defend against graph modification attacks (GMAs), the problem of certified robustness against graph injection attacks (GIAs) remains largely unexplored. To bridge this gap, we introduce the node-aware bi-smoothing framework, which is the first certifiably robust approach for general node classification tasks against GIAs. Notably, the proposed node-aware bi-smoothing scheme is model-agnostic and is applicable for both evasion and poisoning attacks. Through rigorous theoretical analysis, we establish the certifiable conditions of our smoothing scheme. We also explore the practical implications of our node-aware bi-smoothing schemes in two contexts: as an empirical defense approach against real-world GIAs and in the context of recommendation systems. Furthermore, we extend two state-of-the-art certified robustness frameworks to address node injection attacks and compare our approach against them. Extensive evaluations demonstrate the effectiveness of our proposed certificates.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 46 of its 64 references that are in the map. First posted on arXiv 7 Dec 2023.

Builds on

46 of 64 references.

References · 46

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,340
  4. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 468
  5. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 397
  6. 2020Graph Structure Learning for Robust Graph Neural Networkscited by 371
  7. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  8. 2021A Comprehensive Survey on Graph Anomaly Detection with Deep Learningcited by 230
  9. 2020GNNGuard: Defending Graph Neural Networks against Adversarial Attackscited by 195
  10. 2020RAB: Provable Robustness Against Backdoor Attackscited by 118
  11. 2020Deep Partition Aggregation: Provable Defense against General Poisoning Attackscited by 115
  12. 2020MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radiuscited by 114
34 more
  1. 2020Certified Robustness to Label-Flipping Attacks via Randomized Smoothingcited by 108
  2. 2020SoK: Certified Robustness for Deep Neural Networkscited by 105
  3. 2020(De)Randomized Smoothing for Certifiable Defense against Patch Attackscited by 98
  4. 2020Intrinsic Certified Robustness of Bagging against Data Poisoning Attackscited by 94
  5. 2020On Certifying Robustness against Backdoor Attacks via Randomized Smoothingcited by 77
  6. 2021TDGIA:Effective Injection Attacks on Graph Neural Networkscited by 67
  7. 2019Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifierscited by 65
  8. 2022Understanding and Improving Graph Injection Attack by Promoting Unnoticeabilitycited by 62
  9. 2019Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablationcited by 60
  10. 2020Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbationcited by 57
  11. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  12. 2020GCN-Based User Representation Learning for Unifying Robust Recommendation and Fraudster Detectioncited by 54
  13. 2021SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustnesscited by 49
  14. 2021Single Node Injection Attack against Graph Neural Networkscited by 45
  15. 2021Data Poisoning Attacks to Deep Learning Based Recommender Systemscited by 43
  16. 2021Improved, Deterministic Smoothing for L_1 Certified Robustnesscited by 39
  17. 2023Are Defenses for Graph Neural Networks Robust?cited by 38
  18. 2021Scalable Certified Segmentation via Randomized Smoothingcited by 35
  19. 2020Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothingcited by 29
  20. 2023Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directionscited by 28
  21. 2019Adversarial Training Methods for Network Embeddingcited by 26
  22. 2022Double Sampling Randomized Smoothingcited by 22
  23. 2022Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learningcited by 19
  24. 2020Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbationscited by 16
  25. 2022On Collective Robustness of Bagging Against Data Poisoningcited by 16
  26. 2023Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networkscited by 16
  27. 2023Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debiascited by 16
  28. 2022Adversarial Camouflage for Node Injection Attack on Graphscited by 11
  29. 2022Localized Randomized Smoothing for Collective Robustness Certificationcited by 10
  30. 2023Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networkscited by 10
  31. 2023PORE: Provably Robust Recommender Systems against Data Poisoning Attackscited by 10
  32. 2023Hierarchical Randomized Smoothingcited by 9
  33. 2022(De-)Randomized Smoothing for Decision Stump Ensemblescited by 5
  34. 2023Single Node Injection Label Specificity Attack on Graph Neural Networks via Reinforcement Learningcited by 3

Built on by

Cited by year

Citing papers per year: 2024: 3; 2025: 5.

8 papers.

  1. 2024Exact Certification of (Graph) Neural Networks Against Label Poisoningcited by 6
  2. 2024Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attackscited by 5
  3. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4
  4. 2024Collective Certified Robustness against Graph Injection Attackscited by 3
  5. 2025Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbationscited by 2
  6. 2025AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothingcited by 2
  7. 2025Provably Robust Adaptation for Language-Empowered Foundation Modelscited by 0
  8. 2025Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testingcited by 0