Research map / Adversarial robustness and security / Attacks on text and graphs
Certifiable Robustness to Graph Perturbations
Aleksandar Bojchevski, Stephan Günnemann
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train ρ-PPNP with robust cross-entropy instead of standard cross-entropy (ablation) | ρ-PPNP · Citeseer test split | F1 score: 0.70 -> 0.72 | Improved |
| Add a robust hinge-margin penalty to standard cross-entropy | ρ-PPNP · Citeseer test split | F1 score: 0.70 -> 0.73 | Improved |
| Use robust cross-entropy rather than the hinge-margin loss (ablation) | ρ-PPNP robust training · Citeseer | certifiable robustness | Mixed |
| Robustly train with either RCE or CEM at local attack strength s=10 | ρ-PPNP · Citeseer | percentage of certifiably robust nodes: around 13% increase | Improved |
| Lower the damping factor α | ρ-PPNP · Cora-ML and Citeseer | certifiable robustness | Improved |
| Lower the damping factor α | ρ-PPNP · Cora-ML and Citeseer | accuracy: at most 0.5% | No clear effect |
| Restrict the attacker with a global edge-perturbation budget in addition to local budgets | ρ-PPNP certificates · Cora-ML and Citeseer | number of certifiably robust nodes | Improved |
| Allow edge additions as well as removals instead of allowing only edge removals | ρ-PPNP · Cora-ML, Citeseer, and Pubmed | percentage of certifiably robust nodes | Hurt |
| Use ρ-PPNP rather than label propagation | semi-supervised node classification · Cora-ML and Citeseer | certifiable robustness | Improved |
| Use feature propagation rather than ρ-PPNP | semi-supervised node classification · Cora-ML and Citeseer | certifiable robustness | Hurt |
| Increase local attack strength and its corresponding local perturbation budget | ρ-PPNP certificates · Cora-ML and Citeseer | percentage of certifiably robust nodes | Hurt |
| Train using local attack strength s=10 rather than s=6 (ablation) | ρ-PPNP robust training · Citeseer | certifiable robustness | Improved |
Closest papers by meaning
- Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks (ICLR 2024 · similarity 0.90)
- Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations (CVPR 2025 · similarity 0.90)
- 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.89)
- Robust Graph Neural Networks via Unbiased Aggregation (NeurIPS 2024 · similarity 0.89)
- Robust Graph Condensation via Classification Complexity Mitigation (NeurIPS 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.
