Research map / Graph learning / GNN architectures
Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PGNNCert, a deterministic certified defense against arbitrary edge, node, and node-feature poisoning of GNN training graphs, using hash-based subgraph division and majority voting over sub-classifiers for both node and graph classification.
Problem
Certifying GNNs against training-time graph poisoning attacks that arbitrarily perturb edges, nodes, and node features, with deterministic (not probabilistic) guarantees for both node and graph classification.
Approach
Extends voting-based (ensemble/subgraph-division) certification to training-time poisoning: training graphs are hashed into S disjoint subgraph sets (edge-centric or node-centric directed division), one GCN-style classifier is trained per set, and a majority vote is certified deterministically via the count of sub-classifiers whose weights change under perturbation.
Key results
- PGNNCert-E and PGNNCert-N tolerate certified perturbation sizes up to 25 (node) and 30 (graph) on the evaluated datasets.
- Under node injection attacks, PGNNCert-N outperforms RS, Bagging and Bi-RS; PGNNCert-E beats RS, Bagging and Bi-RS-Include but is worse than Bi-RS-Exclude.
- On Cora-ML with S=60, PGNNCert-N keeps 0.661 accuracy against Metattack perturbing 40 edges and nodes, versus 0.675 clean accuracy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PGNNCert-E instead of Bagging | Graph classification · PROTEINS under edge perturbations | certified graph accuracy: 0.205 -> 0.518; 0.000 -> 0.260 | Helped |
| Use PGNNCert-E instead of Bagging | Graph classification · DD under edge perturbations | certified graph accuracy: 0.311 -> 0.578; 0.000 -> 0.330; 0.00 -> 0.063 | Helped |
| Use PGNNCert-N instead of Bagging | Graph classification · PROTEINS under edge perturbations | certified graph accuracy: 0.756 -> 0.778; 0.205 -> 0.474; 0.000 -> 0.102 | Mixed |
| Use PGNNCert-N instead of Bagging | Graph classification · DD under edge perturbations | certified graph accuracy: 0.785 -> 0.771; 0.311 -> 0.344; 0.000 -> 0.006 | Mixed |
| Use node-centric graph division rather than edge-centric division | PGNNCert · CIFAR10 | certified graph accuracy: 0.596 -> 0.636; 0.556 -> 0.593; 0.482 -> 0.498; 0.107 -> 0.113 | Helped |
| Train PGNNCert classifiers on divided subgraphs rather than training GCN normally | GCN node classifier · Cora-ML | accuracy: 0.73 -> 0.68 | Hurt |
| Train PGNNCert classifiers on divided subgraphs rather than training GCN normally | GCN node classifier · Citeseer | accuracy: 0.66 -> 0.67 | Helped |
| Increase the number of subgraphs S (ablation) | PGNNCert · Node and graph classification datasets | certified perturbation size | Helped |
| Increase the number of subgraphs S (ablation) | PGNNCert · Node and graph classification datasets | normal accuracy | Hurt |
| Change the hash function (ablation) | PGNNCert · Node and graph classification datasets | certified accuracy | No clear effect |
| Use PGNNCert-N rather than PGNNCert-E | PGNNCert · Node injection attacks on node classification datasets | certified node accuracy | Helped |
Surprising findings
- In PGNNCert-N, each guaranteed perturbed node can inject unboundedly many edges, so the total bounded edge count can be infinite.
- Hash function choice (MD5 and others) has almost no effect on certified accuracy or certified perturbation size.
Limitations
- Training and certification cost scales S times that of a standard GNN, which may be significant for large GNNs.
- PGNNCert-E is weaker against node-level and node-feature manipulations because edges of manipulated nodes dominate the bound.
- Certified accuracy drops with larger perturbation sizes; clean accuracy trades off against S.
Experimental setup
Datasets: Cora-ML Citeseer PubMed Amazon-C AIDS MUTAG PROTEINS DD CIFAR10 (superpixel graphs)
Benchmarks: Cora-ML Citeseer PubMed Amazon-C AIDS MUTAG PROTEINS DD CIFAR10
Metrics: certified node accuracy certified graph accuracy
Baselines: Randomized smoothing (RS) Bagging Bi-RS Metattack
Builds on: Jia et al. voting certification (Bagging) Bi-RS randomized smoothing Metattack
Closest papers by meaning
- Robustness Inspired Graph Backdoor Defense (ICLR 2025 · similarity 0.89)
- Grimm: A Plug-and-Play Perturbation Rectifier for Graph Neural Networks Defending Against Poisoning Attacks (AAAI 2025 · similarity 0.89)
- A Simple and Yet Fairly Effective Defense for Graph Neural Networks (AAAI 2024 · similarity 0.89)
- Adversarial Robust Generalization of Graph Neural Networks (ICML 2025 · similarity 0.89)
- Exact Certification of (Graph) Neural Networks Against Label Poisoning (ICLR 2025 · similarity 0.89)
- Provably Robust Explainable Graph Neural Networks against Graph Perturbation Attacks (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.