Certified Robustness of Graph Classification against Topology Attack with Randomized Smoothing

2020/09/12 by Zhidong Gao, Rui Hu, Gao, Zhidong +3 · 1 citation
Computer Science · #Advanced Graph Neural Networks #Adversarial Robustness in Machine Learning #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.2009.05872

openalex publication_date 2020/09/12 · openalex created_date 2020/09/21 · openalex updated_date 2026/07/28

Abstract

Graph classification has practical applications in diverse fields. Recent studies show that graph-based machine learning models are especially vulnerable to adversarial perturbations due to the non i.i.d nature of graph data. By adding or deleting a small number of edges in the graph, adversaries could greatly change the graph label predicted by a graph classification model. In this work, we propose to build a smoothed graph classification model with certified robustness guarantee. We have proven that the resulting graph classification model would output the same prediction for a graph under l₀ bounded adversarial perturbation. We also evaluate the effectiveness of our approach under graph convolutional network (GCN) based multi-class graph classification model.

Citations

• The Space of Transferable Adversarial Examples
• Inductive Representation Learning on Large Graphs
• Certified Adversarial Robustness via Randomized Smoothing
• Adversarial Examples on Graph Data: Deep Insights into Attack and Defense
• Detecting Functionality-Specific Vulnerabilities via Retrieving Individual Functionality-Equivalent APIs in Open-Source Repositories
• Certifiable Robustness to Graph Perturbations

Cited by

• Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifier

Related

• Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation
• Structure-Aware Robustness Certificates for Graph Classification
• Certifiable Robustness to Graph Perturbations
• GraphDefense: Towards Robust Graph Convolutional Networks
• Complex Network Effects on the Robustness of Graph Convolutional Networks