Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation

Abstract

Graph neural networks (GNNs) have recently gained much attention for node and graph classification tasks on graph-structured data. However, multiple recent works showed that an attacker can easily make GNNs predict incorrectly via perturbing the graph structure, i.e., adding or deleting edges in the graph. We aim to defend against such attacks via developing certifiably robust GNNs. Specifically, we prove the certified robustness guarantee of any GNN for both node and graph classifications against structural perturbation. Moreover, we show that our certified robustness guarantee is tight. Our results are based on a recently proposed technique called randomized smoothing, which we extend to graph data. We also empirically evaluate our method for both node and graph classifications on multiple GNNs and multiple benchmark datasets. For instance, on the Cora dataset, Graph Convolutional Network with our randomized smoothing can achieve a certified accuracy of 0.49 when the attacker can arbitrarily add/delete at most 15 edges in the graph.

arXiv commentAccepted by ACM SIGKDD'21

References in corpus (29)

• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Adversarial Attacks on Neural Networks for Graph Data
• Representation Learning on Graphs with Jumping Knowledge Networks
• Certified Adversarial Robustness via Randomized Smoothing
• Certified Defenses against Adversarial Examples
• Adversarial Attacks on Graph Neural Networks via Meta Learning
• Efficient Neural Network Robustness Certification with General Activation Functions
• Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
• SybilBelief: A Semi-supervised Learning Approach for Structure-based Sybil Detection
• Transferring Robustness for Graph Neural Network Against Poisoning Attacks
• Semidefinite relaxations for certifying robustness to adversarial examples
• Certified Adversarial Robustness with Additive Noise
• A Dual Approach to Scalable Verification of Deep Networks
• Adversarial Attacks on Node Embeddings via Graph Poisoning
• Adversarial Attack on Graph Structured Data
• A Unified View of Piecewise Linear Neural Network Verification
• Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics
• Adversarial Examples on Graph Data: Deep Insights into Attack and Defense
• Provably Minimally-Distorted Adversarial Examples
• Training verified learners with learned verifiers
• You are Who You Know and How You Behave: Attribute Inference Attacks via Users' Social Friends and Behaviors
• MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius
• Certifiable Robustness to Graph Perturbations
• Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers
• Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing
• Attacking Graph-based Classification via Manipulating the Graph Structure
• Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More