mlsanityData to 7 Oct 2026

Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretation

arXiv 2405.08645 ↗First posted 14 May 2024cs.LG cs.FLcited by 0

Not on the map. Why?

Abstract (arXiv)

Graph convolutional neural networks (GCNs) are powerful tools for learning graph-based knowledge representations from training data. However, they are vulnerable to small perturbations in the input graph, which makes them susceptible to input faults or adversarial attacks. This poses a significant problem for GCNs intended to be used in critical applications, which need to provide certifiably robust services even in the presence of adversarial perturbations. We propose an improved GCN robustness certification technique for node classification in the presence of node feature perturbations. We introduce a novel polyhedra-based abstract interpretation approach to tackle specific challenges of graph data and provide tight upper and lower bounds for the robustness of the GCN. Experiments show that our approach simultaneously improves the tightness of robustness bounds as well as the runtime performance of certification. Moreover, our method can be used during training to further improve the robustness of GCNs.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 46 of its 74 references that are in the map. First posted on arXiv 14 May 2024.

Builds on

46 of 74 references.

References · 46

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2013Intriguing properties of neural networkscited by 5,114
  3. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  4. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  5. 2017Convolutional 2D Knowledge Graph Embeddingscited by 729
  6. 2019Multi-scale Attributed Node Embeddingcited by 543
  7. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  8. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
  9. 2018Adversarial Attack on Graph Structured Datacited by 300
  10. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  11. 2019Algorithms for Verifying Deep Neural Networkscited by 221
  12. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
34 more
  1. 2018Formal Security Analysis of Neural Networks using Symbolic Intervalscited by 185
  2. 2020Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifierscited by 183
  3. 2018Adversarial Attack and Defense on Graph Data: A Surveycited by 166
  4. 2018Efficient Formal Safety Analysis of Neural Networkscited by 165
  5. 2022Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boundcited by 92
  6. 2016Measuring Neural Net Robustness with Constraintscited by 90
  7. 2020Towards More Practical Adversarial Attacks on Graph Neural Networkscited by 76
  8. 2021TDGIA:Effective Injection Attacks on Graph Neural Networkscited by 67
  9. 2019Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifierscited by 65
  10. 2021Introduction to Neural Network Verificationcited by 63
  11. 2019Certifiable Robustness to Graph Perturbationscited by 62
  12. 2019Certifiable Robustness and Robust Training for Graph Convolutional Networkscited by 59
  13. 2020Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbationcited by 57
  14. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  15. 2019Attacking Graph-based Classification via Manipulating the Graph Structurecited by 53
  16. 2021Single Node Injection Attack against Graph Neural Networkscited by 45
  17. 2019Perfectly Parallel Fairness Certification of Neural Networkscited by 42
  18. 2020A Survey of Adversarial Learning on Graphscited by 42
  19. 2021Understanding Structural Vulnerability in Graph Convolutional Networkscited by 37
  20. 2019Attacking Graph Convolutional Networks via Rewiringcited by 32
  21. 2020Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothingcited by 29
  22. 2021Reachability Is NP-Complete Even for the Simplest Neural Networkscited by 27
  23. 2018Attack Graph Convolutional Networks by Adding Fake Nodescited by 26
  24. 2020Indirect Adversarial Attacks via Poisoning Neighbors for Graph Convolutional Networkscited by 16
  25. 2023Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networkscited by 16
  26. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  27. 2023Hierarchical Randomized Smoothingcited by 9
  28. 2024Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attackscited by 9
  29. 2021Reachability analysis of neural networks using mixed monotonicitycited by 3
  30. 2019Generalizable Adversarial Attacks with Latent Variable Perturbation Modellingcited by 2
  31. 2023Graph Adversarial Immunization for Certifiable Robustnesscited by 2
  32. 2023Structure-Aware Robustness Certificates for Graph Classificationcited by 2
  33. 2021An Introduction to Robust Graph Convolutional Networkscited by 1
  34. 2023Complex Network Effects on the Robustness of Graph Convolutional Networkscited by 1

Built on by

Not cited yet.