Research map / Adversarial robustness and security / Attacks on text and graphs
Exact Certification of (Graph) Neural Networks Against Label Poisoning
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.
Derives the first exact sample-wise and collective certificates against label flipping for wide NNs and GNNs by reformulating the SVM-with-NTK bilevel poisoning problem as a MILP solved with Gurobi.
Problem
Certifying worst-case robustness of (graph) neural networks to label flipping poisoning attacks; no exact certificates existed for GNNs or even for NNs in general.
Approach
Use the NTK equivalence of wide networks trained with soft-margin loss to kernelized SVMs, replace the inner SVM dual with KKT conditions, and linearize all non-linear terms exactly into a mixed-integer linear program, giving exact sample-wise and collective (whole test set) certificates.
Key results
- Collective certificate for Cora-MLb at epsilon=0.2 certifies >40% of test predictions for all shown GNNs, whereas the sample-wise certificate certifies none.
- For Cora-MLb at epsilon=0.05, APPNP achieves 79.1±10.9% certified accuracy versus 52.8±5.8% for GraphSAGE and 22.7±5% for MLP.
- Collective certified ratios show a robustness plateau for intermediate budgets (epsilon in [0.15,0.3]); e.g., SGC and APPNP drop only 0.8% from epsilon 0.2 to 0.25.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a collective rather than sample-wise certificate | LabelCert · Cora-MLb, ε=0.2 | certified ratio | Helped |
| Use linear activation in place of ReLU | GCN (forming SGC) · Across evaluated datasets | certifiable robustness ranking | Helped |
| Increase depth in a GNN with skip-connections | GCN Skip-α and GCN Skip-PC · Evaluated datasets | certifiable robustness | Hurt |
| Increase the amount of graph information | GNNs · Cora-MLb, up to intermediate attack budgets | certifiable robustness | Helped |
| Increase the amount of graph information | GNNs · Stronger attack budgets | certifiable robustness | Hurt |
| Increase graph density and homophily | GCN on random graph models · CSBM | certifiable robustness | Helped |
| Use row rather than symmetric graph normalization | SGC and GCN · Cora-MLb and Citeseerb | certifiable robustness | Mixed |
| Use collective instead of sample-wise certification | LabelCert · Intermediate perturbation ε=0.2 | certified ratio: >40% | Helped |
| Increase perturbation budget from ε=0.2 to ε=0.25 | SGC and APPNP collective certificates · Evaluated datasets | certified ratio: 0.8% | No clear effect |
| Use the incomplete instead of exact multiclass certificate | GCN · Citeseer, ε=0.01 | certified accuracy: 10.7 ± 2.5 -> 10.7 ± 2.5 | No clear effect |
| Use the incomplete instead of exact multiclass certificate | SGC · Citeseer, ε=0.02 | certified accuracy: 9.3 ± 5.2 -> 8.7 ± 4.7 | No clear effect |
Surprising findings
- Certified robustness plateaus for intermediate perturbation budgets across datasets and most architectures.
- Linear activation (SGC) is consistently better ranked than GCN, and depth with skip-connections tends to hurt certifiable robustness.
Limitations
- Exact MILP certification is NP-hard and only scales to graphs about the size of Cora-ML or Citeseer.
- Certificates hold exactly only for infinite-width networks; finite-width guarantees are probabilistic and not directly computable.
- Cause of the robustness plateau is not understood and is left to future work.
Experimental setup
Datasets: Cora-ML Citeseer Polblogs Wiki-CS Cora Chameleon CSBM CBA
Benchmarks: Cora-MLb Citeseerb CSBM Cora-ML Citeseer
Metrics: certified ratio certified accuracy
Baselines: MLP exhaustive enumeration
Builds on: QPCert Neural Tangent Kernel SVM dual formulation SGC APPNP
Closest papers by meaning
- Rethinking Label Poisoning for GNNs: Pitfalls and Attacks (ICLR 2024 · similarity 0.90)
- Clean-Label Graph Backdoor Attack in the Node Classification Task (AAAI 2025 · similarity 0.89)
- Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations (CVPR 2025 · similarity 0.89)
- Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks (ICLR 2024 · similarity 0.86)
- Certified but Private: Scalable Zero-Knowledge Proofs for the Formal Verification of Neural Networks (NeurIPS 2026 · similarity 0.86)
- Collective Certified Robustness against Graph Injection Attacks (ICML 2024 · similarity 0.86)
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.