Research map / Graph learning / GNN architectures
Collective Certified Robustness against Graph Injection Attacks
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 the first collective certified robustness scheme against graph injection attacks, casting certification as a binary quadratic-constrained program relaxed to LP via customized linearization.
Problem
Certifying GNN node predictions against graph injection attacks (GIA) is limited to sample-wise certificates that verify each target node independently, which is overly pessimistic when a single perturbed graph attacks many nodes at once.
Approach
Certify a set of target nodes jointly by upper-bounding the number of non-robust nodes under a worst-case attacker that allocates injected nodes' edges, formulated as a BQCLP over randomized-smoothing message-interference bounds, then relaxed to an LP (Collective-LP1 via standard product linearization; Collective-LP2 via a customized reformulation using z = A2^T 1 that needs fewer auxiliary variab
Key results
- On Citeseer with 140 injected nodes, Collective-LP2 certifies 81.2% of target nodes while sample-wise certifies 0.0%.
- Collective-LP2 solves in about 1 minute at rho=140 and is consistently faster than Collective-LP1.
- On Cora-ML at p_e=0.7, p_n=0.9, rho=140, Collective-LP2 improves certified ratio by 216% over Collective-LP1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use collective rather than sample-wise certification | GIA certification · Cora-ML, ρ=140, p_e=0.9, p_n=0.8 | certified ratio: 0.000 -> 0.600 | Helped |
| Use collective rather than sample-wise certification | GIA certification · Citeseer, ρ=140, p_e=0.9, p_n=0.8 | certified ratio: 0.000 -> 0.730 | Helped |
| Use customized LP2 relaxation instead of standard LP1 relaxation (ablation) | Collective certification · Cora-ML, ρ=140, p_e=0.9, p_n=0.8 | certified ratio: 0.600 -> 0.726 | Helped |
| Use customized LP2 relaxation instead of standard LP1 relaxation (ablation) | Collective certification · Citeseer, ρ=140, p_e=0.9, p_n=0.8 | certified ratio: 0.730 -> 0.812 | Helped |
| Use collective LP certification rather than sample-wise certification at a small attack budget | GIA certification · Cora-ML, ρ=20, p_e=0.9, p_n=0.8 | certified ratio: 1.000 -> 0.950 | Hurt |
| Use collective LP certification rather than sample-wise certification at a small attack budget | GIA certification · Citeseer, ρ=20, p_e=0.9, p_n=0.8 | certified ratio: 1.000 -> 0.970 | Hurt |
| Relax the original BQCLP to LP2 (ablation) | Collective certification · Attack budgets ρ≤12 | certified ratio: approximately 5% | Hurt |
Surprising findings
- At small injection budgets the LP-based collective certificate is weaker than sample-wise certification, attributed to relaxation integrity gap.
- The LP relaxation loses roughly 5% certified ratio relative to the original integer program at small budgets.
Limitations
- LP relaxation introduces an integrity gap, weakening certification at small injection budgets.
- Original collective problem is NP-hard, so certification relies on relaxation.
- Evaluated only on two small citation datasets with GCN and GAT.
Experimental setup
Datasets: Cora-ML Citeseer
Benchmarks: Cora-ML Citeseer
Metrics: certified ratio clean accuracy runtime
Baselines: Sample-wise node-aware bi-smoothing Collective-LP1
Builds on: node-aware bi-smoothing randomized smoothing for graph certification collective certification for graph modification attacks
Closest papers by meaning
- Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations (CVPR 2025 · similarity 0.87)
- Stronger and Transferable Node Injection Attacks (AAAI 2024 · similarity 0.86)
- Exact Certification of (Graph) Neural Networks Against Label Poisoning (ICLR 2025 · similarity 0.86)
- Robustness Inspired Graph Backdoor Defense (ICLR 2025 · similarity 0.85)
- A Simple and Yet Fairly Effective Defense for Graph Neural Networks (AAAI 2024 · similarity 0.84)
- Robust Graph Neural Networks via Unbiased Aggregation (NeurIPS 2024 · similarity 0.84)
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.