Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks
This addresses a critical security vulnerability in graph learning models for applications like recommendation systems, though it is incremental as it extends existing robustness frameworks to a new attack type.
The paper tackles the problem of certified robustness against graph injection attacks in deep graph learning by introducing a node-aware bi-smoothing framework, which is the first certifiably robust approach for general node classification tasks and demonstrates effectiveness through extensive evaluations.
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.