Research map / Adversarial robustness and security / Attacks on text and graphs
Robust Graph Neural Networks via Unbiased Aggregation
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.
Analyzes l1-based robust GNNs (SoftMedian, TWIRLS, ElasticGNN) as a unified robust estimator with estimation bias, and proposes RUNG, a GNN built by unrolling a Quasi-Newton IRLS solver for an MCP-penalized unbiased graph signal estimator.
Problem
Robust GNNs that rely on l1-based graph smoothing show aligned robustness but degrade catastrophically under strong adaptive attacks as the attack budget grows, often falling below MLP; the cause is estimation bias from l1 penalties.
Approach
Unify SoftMedian, TWIRLS and ElasticGNN as l1-based robust graph smoothing, attribute their large-budget failure to estimation bias, and replace the l1 penalty with the MCP penalty solved by a diagonal-Hessian Quasi-Newton IRLS whose unrolled iterations form the aggregation layers of RUNG.
Key results
- Under adaptive local attack on Cora ML at 100% budget, RUNG reaches 70.7±10.6 accuracy versus 46.7±11.0 for SoftMedian and 36.0±8.8 for TWIRLS.
- Under adaptive global attack on Cora ML at 40% perturbation, RUNG attains 65.1±1.2 versus 60.8±0.3 for TWIRLS-T, the strongest baseline at that budget.
- Under adaptive local attack on Cora ML at 200% budget, RUNG keeps 69.3±9.0 while GCN drops to 0.0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MCP instead of ℓ1 penalty (ablation) | RUNG · Cora ML adaptive local attack, 200% | accuracy: 14.0 \pm 7.4 -> 69.3 \pm 9.0 | Helped |
| Use MCP instead of ℓ1 penalty (ablation) | RUNG · Cora ML adaptive global attack, 40% | accuracy: 59.8\pm0.8 -> 65.1 \pm 1.2 | Helped |
| Use MCP instead of ℓ1 penalty (ablation) | RUNG · Cora ML adaptive global attack, 0% (clean) | accuracy: 85.8 \pm 0.5 -> 84.6 \pm 0.5 | Mixed |
| Use RUNG instead of the strongest baseline | Cora ML adaptive local attack · Cora ML adaptive local attack, 200% | accuracy: 40.7 \pm 11.8 -> 69.3 \pm 9.0 | Helped |
| Use RUNG instead of the strongest baseline | Cora ML adaptive global attack · Cora ML adaptive global attack, 40% | accuracy: 60.8 \pm 0.3 -> 65.1 \pm 1.2 | Helped |
| Use RUNG instead of APPNP | Cora ML clean evaluation · Cora ML adaptive local attack, 0% (clean) | accuracy: 84.7 \pm 6.8 -> 84.0 \pm 5.3 | No clear effect |
Surprising findings
- The l1-based robust GNNs (SoftMedian, TWIRLS, ElasticGNN) share closely aligned robustness yet collapse below the graph-agnostic MLP as attack budgets grow.
Limitations
- Improvement over robust baselines is more significant under large budgets than small ones.
- Experiments focus on homophilic graphs; heterophilic generalization left to future work.
- Efficiency of RUNG could be further improved.
Experimental setup
Datasets: Cora ML Citeseer Ogbn-Arxiv
Benchmarks: Cora ML Citeseer Ogbn-Arxiv
Metrics: node classification accuracy on attacked nodes estimation bias sum of squared feature deviation
Baselines: MLP GCN APPNP GAT GNNGuard RGCN GRAND ProGNN Jaccard-GCN SoftMedian TWIRLS TWIRLS-T
Builds on: APPNP TWIRLS ElasticGNN SoftMedian IRLS
Closest papers by meaning
- Reliable Graph Neural Networks via Robust Aggregation (NeurIPS 2020 · similarity 0.93)
- Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks (ICLR 2024 · similarity 0.91)
- Robustness of Graph Neural Networks at Scale (NeurIPS 2021 · similarity 0.90)
- Robust Graph Condensation via Classification Complexity Mitigation (NeurIPS 2025 · similarity 0.87)
- Enhancing Graph Classification Robustness with Singular Pooling (NeurIPS 2025 · similarity 0.87)
- A Simple and Yet Fairly Effective Defense for Graph Neural Networks (AAAI 2024 · similarity 0.87)
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.