AI Paper Atlas

Research map / Graph learning / GNN architectures

Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More

Aleksandar Bojchevski, Johannes Gasteiger, Stephan Günnemann

ICML 2020 · Graph learning › GNN architectures · approach: Robustness, privacy, and fairness of GNNs · 8 citations (OpenAlex)

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 changedWhereMeasuredEffect
Use sparsity-aware data-dependent flip probabilities (p+=0.01, p-=0.6) instead of uniform flipping (p+=p-=0.1) (ablation)GCN attribute certificates on Cora-ML · Cora-ML attribute perturbationsavg max certified radius rd: 2.03 -> 9.99Improved
Sparsity-aware smoothing with deletion-only flips (p+=0) instead of uniform flipping (ablation)GCN attribute certificates on Cora-ML · Cora-ML attribute perturbationsavg max certified radius rd: 2.03 -> 18.66Improved
Sparsity-aware randomization in place of randomized ablation certificate (ablation)GCN attribute certificates on Cora-ML · Cora-ML attribute perturbationsavg max certified radius rd: 2.01 -> 9.99Improved
Certificate with same flip probabilities as Lee et al. (2019) on discretized ImageNet, now computed via region partitionCertificate efficiency · Discretized ImageNet (K=256)certificate computation time: 4 days -> 2.5 msImproved
Sparsity-aware flip probabilities (p+=0.1, p-=0.2) vs. uniform p+=p-=0.2 on binarized MNIST (ablation)CNN certificates on binarized MNIST · Binarized MNISTcertified ratio w.r.t. rdImproved
Multi-class (Bonferroni) certificate instead of binary-class certificate (ablation)CNN certificates on binarized MNIST · Binarized MNISTcertified ratioImproved
Multi-class certificate instead of binary-class certificate (ablation)GCN on Cora-ML · Cora-ML attribute perturbationscertified ratioImproved
Deletion-only smoothing (p+=0) instead of adding flips, certifying rd (ablation)GAT, GCN, APPNP graph structure certificates · Cora-ML graph perturbationscertified ratio for rdImproved
Certifying with GAT/GCN/APPNP models: attribute robustness orderingGNN base models · Cora-ML attribute perturbationscertified ratioMixed
Joint smoothing of graph and attributes with separate flip probabilities/radii vs single-input certificationGCN joint certificates on Cora-ML · Cora-ML joint graph and attribute perturbationscertified ratioHurt

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy