Source-linked AI summary
Certifiable Robustness to Graph Perturbations
Aleksandar Bojchevski, Stephan Günnemann
TL;DR
Graph neural networks and related graph models lack robust guarantees despite vulnerability to adversarial changes in graph structure and node attributes. The paper develops PageRank-based certificates for graph perturbations and studies certificate-driven robust training, finding improved certified robustness and clean accuracy while noting computational and threat-model boundaries.
Problem
Graph models have limited robustness certification despite vulnerability to adversarial perturbations of both graph structure and node attributes.
Method
The paper uses personalized PageRank to compute robustness and non-robustness certificates for a general model family, including GNNs and label/feature propagation.
Results
The certificates are flexible and efficiently computed, exact for some threat models, while robust training increases certifiably robust nodes and improves clean accuracy.
Takeaways & Limitations
The approach provides certifiable guarantees for graph-structure perturbations and supports robust training that can improve robustness without sacrificing predictive accuracy.
Takeaways & Limitations
Robust training is constrained by an inner worst-case-margin optimization that makes gradients difficult to obtain, and the threat model represents uncertainty through fragile edges.
Abstract
from arXiv · showhide
Despite the exploding interest in graph neural networks there has been little effort to verify and improve their robustness. This is even more alarming given recent findings showing that they are extremely vulnerable to adversarial attacks on both the graph structure and the node attributes. We propose the first method for verifying certifiable (non-)robustness to graph perturbations for a general class of models that includes graph neural networks and label/feature propagation. By exploiting connections to PageRank and Markov decision processes our certificates can be efficiently (and under many threat models exactly) computed. Furthermore, we investigate robust training procedures that increase the number of certifiably robust nodes while maintaining or improving the clean predictive accuracy.
1 Introduction
Graph models are widely used for semi-supervised node classification but remain vulnerable to adversarial perturbations, while certifiable robustness has received little attention. The paper introduces provable graph-structure robustness certificates, robust training, and efficient computation for a broad model family.
- Graph models are vulnerable to low-cost adversarial attacks because small feature or structural perturbations can change predictions across the graph.
- Graph neural networks are widely used for semi-supervised node classification in high-impact applications, including protein, scientific-paper, fraud, and breast-cancer classification.
- The paper proposes the first provable robustness method for graph-structure perturbations, covering models whose predictions are linear functions of personalized PageRank.
- The approach provides certificates and adversarial examples for assessing certifiable robustness or non-robustness under general admissible graph perturbations.
- Robust training based on the certificates improves both robustness and clean accuracy, while exact certificates are efficiently computable for some threat models.
2 Related work
Prior work largely used heuristic defenses against graph-model attacks, whereas certifiable methods provide guarantees for specified threat models. Before this work, graph neural network certification covered node attributes but not graph structure or propagation models.
- Certifiable robustness is presented as a more promising alternative because heuristic defenses can be defeated by new attacks.
- Heuristic graph-robustness methods include adversarial training, edge weighting, encoder refinement, contrastive learning, smoothing, and Bayesian models.
- Prior GNN certificates handled perturbations to node attributes, whereas this work addresses graph-structure perturbations.
- The paper extends certification beyond GNNs to semi-supervised methods such as label and feature propagation, while identifying joint attribute-and-structure perturbations as future work.
3 Background and preliminaries
The paper formulates semi-supervised node classification and analyzes PageRank-based propagation, using personalized PageRank to make graph-dependent predictions linear and theoretically tractable. A PageRank-based PPNP variant supplies the central model abstraction.
- Semi-supervised node classification predicts each node’s class from an attributed graph and labels available for only a subset of nodes.
- Topic-sensitive PageRank represents random-walk landing probabilities under edge-following and teleportation, with personalized PageRank obtained by teleporting to one node.
- PPNP independently transforms node features into logits and propagates them through a graph-dependent diffusion matrix.
- Replacing PPNP’s symmetric propagation matrix with a personalized PageRank matrix yields π-PPNP, whose propagated class logits are linear in each node’s personalized PageRank vector.
- For two classes, the prediction margin is linear in personalized PageRank, and a negative minimum margin for the true class indicates misclassification.
4 Robustness certificates
The paper certifies robustness by minimizing node-class margins over admissible fragile-edge perturbations, exploiting their linear dependence on personalized PageRank. Local budgets admit exact, efficient certificates, while global budgets require a relaxed lower bound that still certifies robustness when positive.
- Threat model and budgets: The threat model allows fragile edges to be included or excluded under global and per-node local perturbation budgets.Fixed edges remain reliable, while fragile-edge configurations define the admissible perturbed graphs.
- Core formulation: Because the margin is linear in personalized PageRank, certification reduces to optimizing a linear PageRank objective over admissible graph configurations.This converts an apparently exponential discrete search into the paper’s central optimization problem.
- Local-budget certificates: For local budgets, policy iteration greedily improves edge configurations and is guaranteed to converge to the optimal policy.The algorithm solves a linear system, selects improving fragile edges subject to local budgets, and iterates until convergence.
- Local-budget certificates: Local-budget certificates are exact and can recover worst-case margins for all nodes by solving once per class pair and evaluating the resulting perturbed graphs.The optimal perturbed edges do not depend on the teleport vector, enabling reuse across target nodes.
- Robustness certificates: A positive worst-case margin certifies robustness, while a negative exact margin certifies non-robustness by exhibiting an adversarial graph.The exact local-budget certificate distinguishes guaranteed robustness from guaranteed vulnerability.
- Global-budget certificates: Global budgets make the optimization hard, so the method builds an auxiliary-graph MDP, adds budget constraints to its LP, and applies a relaxation yielding a lower bound.A positive lower bound certifies robustness, but a negative relaxed bound does not necessarily provide an adversarial example.
5 Robust training for graph neural networks
The paper turns worst-case margins into trainable robust losses, using exact certification results to improve graph-model robustness while preserving clean accuracy.
- Worst-case-margin robust losses are optimized with respect to model parameters to encourage more robust weights.The losses include robust cross-entropy and a robust hinge penalty.
- Danskin’s theorem permits direct gradient computation at the optimal perturbation because the worst-case margin is linear in logits and PageRank.The resulting gradient equals the optimal signed PageRank scores used during certification.
- The hinge penalty becomes zero when training nodes are certifiably robust with margin at least M, reducing the objective to standard cross-entropy with robustness guarantees.
- Increasing local attack strength decreases the ratio of certified nodes, motivating training at the attack strength relevant to deployment.
6 Experimental results
Experiments show that certification is efficient and sensitive to the threat model, model configuration, and graph structure; robust training increases certified nodes while maintaining or improving accuracy.
- Robustness certificates: Local budget only: Removing edges yields significantly more certifiably robust nodes than allowing both edge removal and addition, and π-PPNP is more robust than label propagation.Because the certificate is exact, remaining nodes are certifiably non-robust.
- Analyzing influence on robustness: Decreasing the damping factor α significantly increases robustness with at most a 0.5% accuracy loss.Higher α produces greater influence from the effective neighborhood.
- Analyzing influence on robustness: Higher neighborhood purity corresponds to a higher worst-case margin and certifiable robustness.
- Robustness certificates: Local and global budget: A global budget restricts the attacker beyond local constraints and increases the number of robust nodes.
- Efficiency: Algorithm 1 finds the optimal solution in a few iterations for fragile sets as large as 10^4, with runtime on the order of a few seconds.Each iteration uses efficient sparse matrix operations.
- Robust training: Around 13% more nodes become certifiably robust at the trained local attack strength s = 10, while Citeseer F1 improves from 0.70 with LCE to 0.73 with LCEM.LRCE achieves higher certifiable robustness, whereas LCEM achieves the higher F1 score.
7 Conclusion
The paper establishes graph-structure robustness certificates for GNNs and propagation models, supports flexible local and global threat budgets, and introduces robust training that improves certified robustness and predictive accuracy.
- The certificates cover graph-structure perturbations for GNNs and label/feature propagation, support local and global budgets, and can be efficiently computed.The paper identifies joint feature-and-structure robustification as future work.
8 Appendix
The appendix extends the certification framework to label and feature propagation, develops optimization-based certificate solvers, and reports scalability, accuracy, and complexity results.
- Certificates for Label Propagation and Feature Propagation: Label propagation fits the framework by propagating one-hot vectors of labeled nodes instead of neural-network logits, requiring only a different H matrix.The learned classification matrix F assigns each node-class pair an unnormalized class probability, with predictions obtained by argmax.
- Certificates for Label Propagation and Feature Propagation: Feature propagation first diffuses node features through the graph and then trains logistic regression on the diffused features.The diffusion step is Xdiff = ΠX.
- Further experiments: Robust training increases certifiably robust nodes while preserving the same F1 score as training with a smaller local attack strength.The comparison uses local attack strength s=10 versus s=6.
- Further experiments: Certifiable accuracy stays relatively close to clean accuracy under restrictive budgets and decreases gracefully as the perturbation budget grows.Certifiable accuracy is the ratio of correctly predicted, certifiably robust nodes and lower-bounds worst-case classification accuracy.
- Further experiments: Certificates scale to graphs exceeding 10K nodes in a few seconds for local budgets, while global-budget runtime scales linearly with the number of edges.The local-budget timing uses the VI algorithm, and the global-budget timing uses the RLT relaxation.
- Proofs: The local-budget policy-iteration method scales to large graphs, while the global-budget problem is W[1]-hard and has no FPTAS.The global-budget hardness follows from a reduction from Link Building, whereas policy iteration handles local constraints in polynomial time.