Node-aware Bi-smoothing: Certified Robustness against Graph Injection
  Attacks
Yuni Lai Yulin Zhu Bailin Pan Kai Zhou
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.