Source-linked AI summary
Certifiable Robustness and Robust Training for Graph Convolutional Networks
Daniel Zügner, Stephan Günnemann
TL;DR
GNN predictions can change drastically under small adversarial perturbations, creating a need for reliable robustness guarantees. The paper develops certification and semi-supervised robust training for GCNs with binary node attributes under L0-bounded perturbations, and reports substantially improved robustness with only minor accuracy effects.
Problem
GNNs are vulnerable to small adversarial changes, while effective methods to prevent or verify prediction changes under specified perturbation models were unavailable.
Method
The paper certifies robustness and non-robustness for GCNs under binary node-attribute perturbations and trains robust models using labeled and unlabeled nodes jointly.
Results
Traditional training yields few certifiably robust nodes, whereas robust training can increase robustness by a factor of four while retaining high accuracy.
Takeaways & Limitations
The method improves the reliability of GNN outputs by providing guarantees and producing models that are much more robust to the considered attacks.
Takeaways & Limitations
The study focuses on perturbations of node attributes and leaves graph-structure perturbations for future work.
Abstract
from arXiv · showhide
Recent works show that Graph Neural Networks (GNNs) are highly non-robust with respect to adversarial attacks on both the graph structure and the node attributes, making their outcomes unreliable. We propose the first method for certifiable (non-)robustness of graph convolutional networks with respect to perturbations of the node attributes. We consider the case of binary node attributes (e.g. bag-of-words) and perturbations that are L_0-bounded. If a node has been certified with our method, it is guaranteed to be robust under any possible perturbation given the attack model. Likewise, we can certify non-robustness. Finally, we propose a robust semi-supervised training procedure that treats the labeled and unlabeled nodes jointly. As shown in our experimental evaluation, our method significantly improves the robustness of the GNN with only minimal effect on the predictive accuracy.
1 INTRODUCTION
GNNs improve node classification but are vulnerable to small adversarial changes that can make predictions unreliable. The paper introduces certifiable robustness analysis and semi-supervised robust training for graph convolutional networks.
- GNNs have improved node classification, but slight feature or structure perturbations can cause completely wrong predictions.
- Existing mechanisms did not effectively prevent prediction changes or verify robustness under specified perturbation models.The graph setting is difficult because perturbing other nodes can affect a target node's prediction.
- The paper proposes the first method for provable robustness of GNNs under perturbations of node attributes.
- Robustness certificates guarantee that no perturbation in the considered space changes a certified node's prediction, while non-robustness certificates provide adversarial examples.
- Robust training uses the semi-supervised learning setting by incorporating unlabeled nodes while aiming to improve robustness and preserve node-classification accuracy.
- Experiments find that traditional training certifies few robust nodes, whereas robust training increases robustness by up to a factor of four.
- The method is intended to improve the reliability of GNNs for production systems and scientific applications.
2 RELATED WORK
Prior graph-robustness work focused on generating adversarial examples, while certifiable robustness methods were developed mainly for classical neural networks. This paper extends certification and robust training to GNNs with relational dependencies and discrete perturbations.
- Earlier attacks on GNNs considered adversarial examples affecting node attributes or graph structure, whereas this work certifies and improves GNN robustness.
- Heuristic defenses for classical neural networks can be broken by new attacks, motivating guarantees that no perturbation in a specified space changes a prediction.
- Convex-relaxation methods bound worst-case margins and can support efficient certification and robust training through duality.
3 PRELIMINARIES
The paper studies semi-supervised node classification on one large graph with binary node features. A GCN maps nodes to classes using message passing, nonlinear transformations, and trainable parameters learned from labeled nodes.
- The task is to classify nodes in a single large graph with binary features using labels from a subset of nodes.
- The classifier maps each node to one class and uses graph convolutional networks for node classification.
- The output layer uses softmax, while intermediate layers use ReLU activations.
- Message-passing matrices determine how activations propagate through the graph.
- A GCN adds self-loops and normalizes adjacency through the degree matrix before propagation.
- Trainable weights and biases are typically learned by minimizing cross-entropy on labeled training nodes.
4 CERTIFYING ROBUSTNESS FOR GRAPH CONVOLUTIONAL NETWORKS
The method certifies whether a target node’s GCN prediction survives bounded binary node-attribute perturbations by reducing the graph computation and optimizing conservative worst-case margins. Convex relaxations, integral solutions, and dual optimization make these certificates tractable, while also enabling exact non-robustness certificates.
- Target-node reduction: The target node’s output depends only on its L−1-hop neighborhood, allowing the GNN matrices to be sliced to the entries needed for certification.This reduces the network size and the number of perturbations considered.
- Worst-case margins: The certificate problem minimizes the target node’s worst-case margin between the predicted class y∗ and each competing class under admissible attribute perturbations.A positive minimum margin means no admissible perturbation can change the prediction.
- Perturbation model: Perturbations are modeled for binary node attributes with global L0 budget Q and optional local budget q across the target’s L−1-hop neighborhood.This accounts for the fact that neighboring nodes can affect the target prediction.
- Convex relaxation: Convex relaxations address the discrete domain and nonlinear GNN while preserving a lower bound on the original worst-case margin.If the relaxed lower bound is positive for every competing class, the target node is certified robust.
- Exact tractability: The relaxed problem has an integral optimum, so replacing binary constraints with continuous variables still handles discrete perturbations exactly and tractably.Theorem 4.2 establishes equality between the relaxed formulations, and Corollary 4.5 identifies an integral linear program.
- Dual and primal certificates: Dual-feasible values provide robustness certificates, while an exact primal feasible perturbation provides a non-robustness certificate when its margin is negative.Some nodes receive neither certificate when the available bounds do not determine the outcome.
5 ROBUST TRAINING OF GNNS
The paper develops robust training objectives for GNNs that combine worst-case robustness bounds with exact-model classification, while using unlabeled nodes to encourage calibrated robustness. The resulting procedures improve certified robustness without discarding standard predictive training.
- Robust objectives: Robust training uses bounds on worst-case loss to make GNN predictions less sensitive to admissible perturbations.The robust cross entropy loss is based on an upper bound on the worst-case loss.
- Robust objectives: The robust hinge loss prevents robustness training from rewarding excessive worst-case margins that can produce false certainty.It is introduced because robust cross entropy can push logits toward very large negative values and overconfident predictions.
- Robust objectives: The final objective combines robust hinge loss with standard cross entropy on the exact GNN, using the relaxed model only to enforce robustness.When all nodes are robust, the robust term becomes zero and training reduces to standard cross entropy with a robustness guarantee.
- Semi-supervised robust training: For unlabeled nodes, a smaller margin M2 encourages robustness without forcing highly confident predictions that may be wrong.Unlabeled nodes are used for robustness purposes rather than as self-training labels.
- Semi-supervised robust training: In practice, training first optimizes the labeled-node objective, then optimizes the joint objective over all nodes until convergence.The second stage incorporates unlabeled nodes into robustness training while retaining exact-GNN classification of labeled nodes.
- Optimization: The robust-training approach is computationally practical, although updating activation bounds remains its least efficient component.The dual program and activation bounds are differentiable, enabling gradient descent with standard deep-learning libraries.
6 EXPERIMENTAL EVALUATION
The experiments show that certificates are informative for standard GNNs, while robust semi-supervised training substantially increases certified robustness with little accuracy loss.
- Certificates: At most 30% of nodes remain uncertified for any given Q across datasets, indicating tight certificates despite standard training.The uncertified region is described as small across all evaluated datasets.
- Certificates: At Q = 12, fewer than 55% of Cora-ML nodes and fewer than 20% of Citeseer nodes are certifiably robust under standard training.At the same budget, two thirds of Citeseer nodes and one quarter of Cora-ML nodes are certifiably non-robust.
- Certificates: Neighborhood purity is associated with robustness, while nodes with medium degree appear most robust because many neighbors enlarge the attack surface.On Cora-ML, almost all nodes certifiably robust above Q ≥50 have at least 80% neighborhood purity.
- Robust training: Robust training can quadruple the number of certifiably robust Citeseer nodes at Q = 12.The robustly trained model also increases certification coverage beyond its training budget, and previously certifiably non-robust nodes can become robust.
- Accuracy and training dynamics: Robustness increases with almost no classification-accuracy loss, and test accuracy on Citeseer changes from 68% to 66% when training Q rises from 12 to 48.The paper attributes the small test-accuracy change to retaining the normal cross-entropy loss alongside the robust hinge loss.
- Robust training: RH-U achieves significantly higher robustness at Q = 12 than the other robust training procedures.The comparison uses the percentage of nodes certifiably robust at the perturbation budget used for training.
- Accuracy and training dynamics: RH-U increases the worst-case margin toward the specified labeled and unlabeled targets, whereas standard training decreases it and leaves unlabeled nodes non-robust.Unlabeled nodes constitute 90% of all nodes in the described setup.
7 CONCLUSION
The paper presents the first robustness certification method for GNNs under discrete L0-bounded node-attribute perturbations and a semi-supervised robust training procedure. Experiments show tighter certificates and substantially improved robustness with only a minor effect on classification accuracy.
- Contributions: The method certifies robustness and non-robustness for GNNs under L0-bounded perturbations of discrete node attributes.Robustness certificates guarantee that no perturbation in the considered space changes a node’s prediction, while non-robustness certificates provide adversarial examples.
- Findings: Dual-based computation yields tight certificates for many nodes, while traditional training produces models that can be easily fooled.The paper identifies robust semi-supervised training as the alternative that makes the resulting GNNs much more robust.
- Findings: The proposed robust training improves GNN robustness with only a minor effect on classification accuracy.The training procedure uses the semi-supervised setting and considers both labeled and unlabeled nodes.
8 APPENDIX
The appendix supplies implementation details and derives the dual optimization used to compute robustness certificates under local and global perturbation budgets.
- Implementation details: Robust training uses mini-batch stochastic gradient descent with Adam, sampling 20 nodes per iteration and computing their two-hop neighborhoods.The implementation also uses dropout 0.5, L2 regularization strength 1e^-5, and learning rate 0.001.
- Dual formulation: The certificate problem is reformulated as a linear program before deriving a simplified dual formulation.The derivation eliminates several dual variables using ReLU complementarity and introduces auxiliary variables to represent positive-part terms.
- Perturbation constraints: The perturbation construction enforces the binary-feature bounds 0 ≤ X~ ≤ 1 when selecting attribute changes.The derivation sets the improvement contribution to zero when an attribute is already at its upper bound.
- Dual formulation: The resulting optimization uses variables such as Ω, ρ, and η_n after eliminating the remaining dual variables.The appendix establishes optimality through feasibility, complementary slackness, and the KKT conditions.
- Dual formulation: The dual selects the perturbation entries with the largest objective improvements while respecting local q and global Q budgets.The construction sets α_nd = 1 for the selected set S_Q corresponding to the admissible largest improvements.