Abstract: In recent years, graph neural network (GNN) has been widely applied in fields such as anomaly detection, recommendation systems, and biomedicine. Despite their excellent performance in specific tasks, many studies have shown that GNN is susceptible to adversarial perturbations. To mitigate the vulnerability of GNN to adversarial examples, some researchers have proposed robustness certification defense techniques against graph modification attacks, aiming to enhance the ability of GNN models to resist malicious perturbations in this scenario. However, the robustness analysis of node classification models in the context of graph injection attack (GIA) has not been widely explored. Facing this challenge, we extend the sparse-aware randomized smoothing mechanism and design a robustness certification method, RCGNN, based on randomized smoothing for the GIA scenario. To align the noise perturbation space with GIA attack behaviors, we pre-inject malicious nodes and restrict perturbations near these nodes, and improve the noise perturbation function to increase the certification ratio and expand the maximum certification radius. Comparative experiments on real datasets demonstrate that RCGNN can achieve robustness certification for node classification tasks in the GIA scenario, and it outperforms the sparse-aware randomized smoothing mechanism in terms of certification ratio and maximum certification radius.

Key words: graph neural network (GNN), node classification, randomized smoothing, graph injection attack (GIA), robustness certification