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

arXiv: https://arxiv.org/abs/2312.03979 · HTML: https://mlsanity.com/paper/2312.03979/

## 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 (most cited first, 30 of 46)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [A Comprehensive Survey on Graph Anomaly Detection with Deep Learning](https://mlsanity.com/paper/2106.07178/) (2021)
- [GNNGuard: Defending Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2006.08149/) (2020)
- [RAB: Provable Robustness Against Backdoor Attacks](https://mlsanity.com/paper/2003.08904/) (2020)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius](https://mlsanity.com/paper/2001.02378/) (2020)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [SoK: Certified Robustness for Deep Neural Networks](https://mlsanity.com/paper/2009.04131/) (2020)
- [(De)Randomized Smoothing for Certifiable Defense against Patch Attacks](https://mlsanity.com/paper/2002.10733/) (2020)
- [Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks](https://mlsanity.com/paper/2008.04495/) (2020)
- [On Certifying Robustness against Backdoor Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.11750/) (2020)
- [TDGIA:Effective Injection Attacks on Graph Neural Networks](https://mlsanity.com/paper/2106.06663/) (2021)
- [Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers](https://mlsanity.com/paper/1906.04948/) (2019)
- [Understanding and Improving Graph Injection Attack by Promoting Unnoticeability](https://mlsanity.com/paper/2202.08057/) (2022)
- [Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation](https://mlsanity.com/paper/1911.09272/) (2019)
- [Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation](https://mlsanity.com/paper/2008.10715/) (2020)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [GCN-Based User Representation Learning for Unifying Robust Recommendation and Fraudster Detection](https://mlsanity.com/paper/2005.10150/) (2020)
- [SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustness](https://mlsanity.com/paper/2111.09277/) (2021)
- [Single Node Injection Attack against Graph Neural Networks](https://mlsanity.com/paper/2108.13049/) (2021)
- [Data Poisoning Attacks to Deep Learning Based Recommender Systems](https://mlsanity.com/paper/2101.02644/) (2021)
- [Improved, Deterministic Smoothing for L_1 Certified Robustness](https://mlsanity.com/paper/2103.10834/) (2021)
- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [Scalable Certified Segmentation via Randomized Smoothing](https://mlsanity.com/paper/2107.00228/) (2021)

## Built on by (most cited first, 8 of 8)

- [Exact Certification of (Graph) Neural Networks Against Label Poisoning](https://mlsanity.com/paper/2412.00537/) (2024)
- [Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2407.10867/) (2024)
- [Exact Verification of Graph Neural Networks with Incremental Constraint Solving](https://mlsanity.com/paper/2508.09320/) (2025)
- [Collective Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2403.01423/) (2024)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothing](https://mlsanity.com/paper/2503.22998/) (2025)
- [Provably Robust Adaptation for Language-Empowered Foundation Models](https://mlsanity.com/paper/2510.08659/) (2025)
- [Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing](https://mlsanity.com/paper/2510.18591/) (2025)

## 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.