CiDer: A Black-box Approach to Classify Node with Certified Robustness Guarantees

Due to the outstanding performance of graph node classification in tasks such as detecting illegal nodes in transaction networks, adversarial attacks aiming to perturb classification results have proliferated. Although current defenses based on randomized smoothing have shown some effectiveness, these approaches still require modifications to the classification model to ensure accuracy. Here, we propose a novel approach - CiDer, that theoretically guarantees the robustness of graph node classification results in a black-box setting, which means no assumptions on the form of attack and the classification model. The key idea behind our approach is to leverage the denoise capability of diffusion models on features to perform adversarial purification on the data. We then prove this stochastic purification method can ensure certified robustness under certain attack budgets. Our extensive experiments corroborate our theory and demonstrate that node classifiers worked with CiDer achieve significantly superior performance compared to state-of-the-art, e.g., the accuracy improves by 7% on Cora and the optimal result improves by 30% on PubMed.