Structure-Aware Robustness Certificates for Graph Classification
Certifying the robustness of a graph-based machine learning model poses a critical challenge for safety. Current robustness certificates for graph classifiers guarantee output invariance with respect to the total number of node pair flips (edge addition or edge deletion), which amounts to an $l_{0}$ ball centred on the adjacency matrix. Although theoretically attractive, this type of isotropic structural noise can be too restrictive in practical scenarios where some node pairs are more critical than others in determining the classifier's output. The certificate, in this case, gives a pessimistic depiction of the robustness of the graph model. To tackle this issue, we develop a randomised smoothing method based on adding an anisotropic noise distribution to the input graph structure. We show that our process generates structural-aware certificates for our classifiers, whereby the magnitude of robustness certificates can vary across different pre-defined structures of the graph. We demonstrate the benefits of these certificates in both synthetic and real-world experiments.
Code (1)
Tasks
ClassificationGraph ClassificationSimilar Papers 제목 키워드 기반
Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks
Randomized smoothing is one of the most promising frameworks for certifying the adversarial robustness of machine learning models, including Graph Neural Networks (GNNs). Yet, existing randomized smoothing certificates f…
Adversarial RobustnessCollective Robustness Certificates: Exploiting Interdependence in Graph Neural Networks
In tasks like node classification, image segmentation, and named-entity recognition we have a classifier that simultaneously outputs multiple predictions (a vector of labels) based on a single input, i.e. a single graph,…
Adversarial RobustnessImage Segmentationnamed-entity-recognitionNamed Entity Recognition+3Collective Robustness Certificates
In tasks like node classification, image segmentation, and named-entity recognition we have a classifier that simultaneously outputs multiple predictions (a vector of labels) based on a single input, i.e. a single graph,…
Adversarial RobustnessImage Segmentationnamed-entity-recognitionNamed Entity Recognition+3Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks
Deep Graph Learning (DGL) has emerged as a crucial technique across various domains. However, recent studies have exposed vulnerabilities in DGL models, such as susceptibility to evasion and poisoning attacks. While empi…
Graph LearningNode ClassificationRecommendation SystemsRobustness Certificates Against Adversarial Examples for ReLU Networks
While neural networks have achieved high performance in different learning tasks, their accuracy drops significantly in the presence of small adversarial perturbations to inputs. Defenses based on regularization and adve…
General ClassificationMulti-Label ClassificationMUlTI-LABEL-ClASSIFICATION