GRACED: A Plug-and-Play Solution for Certifiable Graph Classification

Abstract

With the widespread application of machine learning-based graph classification models in fields such as biology and economics, there has been a growing number of attacks aimed at perturbing classification results. Although current defense methods, such as randomized smoothing, have achieved some success, their practical applicability remains limited due to the need to modify classification models to ensure accuracy.In this paper, we propose a novel defense method—GRACED, which provides theoretical guarantees for the accuracy and robustness of graph classification without requiring knowledge of the attacker’s capabilities or the classification model. The key idea behind our method is to leverage the denoising ability of feature diffusion models for adversarial data purification. We then demonstrate that this randomized purification approach can ensure certified robustness under specific attack budgets. Extensive experiments confirm our theoretical findings and show that graph classifiers using GRACED significantly outperform state-of-the-art classifiers. For instance, the accuracy on MUTAG improved by 11%, and the best results on IMDB showed a 14% increase.