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.

通过节点感知的双平滑框架，我们引入了第一种可证明对抗图注入攻击的通用节点分类任务的鲁棒方法，并通过严密的理论分析建立了我们平滑方案的可证明条件。此外，我们将两个最先进的可证明鲁棒性框架扩展到节点注入攻击，并与它们进行了比较。广泛的评估证明了我们提出的证书的有效性。