mlsanityData to 7 Oct 2026

Hierarchical Randomized Smoothing

arXiv 2310.16221 ↗First posted 24 Oct 2023cs.LG cs.AI cs.CVcited by 9

Not on the map. Why?

Abstract (arXiv)

Real-world data is complex and often consists of objects that can be decomposed into multiple entities (e.g. images into pixels, graphs into interconnected nodes). Randomized smoothing is a powerful framework for making models provably robust against small changes to their inputs - by guaranteeing robustness of the majority vote when randomly adding noise before classification. Yet, certifying robustness on such complex data via randomized smoothing is challenging when adversaries do not arbitrarily perturb entire objects (e.g. images) but only a subset of their entities (e.g. pixels). As a solution, we introduce hierarchical randomized smoothing: We partially smooth objects by adding random noise only on a randomly selected subset of their entities. By adding noise in a more targeted manner than existing methods we obtain stronger robustness guarantees while maintaining high accuracy. We initialize hierarchical smoothing using different noising distributions, yielding novel robustness certificates for discrete and continuous domains. We experimentally demonstrate the importance of hierarchical smoothing in image and node classification, where it yields superior robustness-accuracy trade-offs. Overall, hierarchical smoothing is an important contribution towards models that are both - certifiably robust to perturbations and accurate.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 54 of its 68 references that are in the map. First posted on arXiv 24 Oct 2023.

Builds on

54 of 68 references.

References · 54

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  5. 2013Intriguing properties of neural networkscited by 5,114
  6. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 4,993
  7. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  8. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,510
  9. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  10. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
  11. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  12. 2018Robustness May Be at Odds with Accuracycited by 873
38 more
  1. 2021How Attentive are Graph Attention Networks?cited by 818
  2. 2017One pixel attack for fooling deep neural networkscited by 579
  3. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 462
  4. 2019On Evaluating Adversarial Robustnesscited by 442
  5. 2017Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Rankingcited by 332
  6. 2021Unsolved Problems in ML Safetycited by 291
  7. 2019Adversarial Examples Improve Image Recognitioncited by 283
  8. 2018Certified Adversarial Robustness with Additive Noisecited by 178
  9. 2020Randomized Smoothing of All Shapes and Sizescited by 146
  10. 2019Adversarial Training Can Hurt Generalizationcited by 131
  11. 2020SoK: Certified Robustness for Deep Neural Networkscited by 100
  12. 2020(De)Randomized Smoothing for Certifiable Defense against Patch Attackscited by 97
  13. 2019Sparse and Imperceivable Adversarial Attackscited by 95
  14. 2018SparseFool: a few pixels make a big differencecited by 94
  15. 2020Intrinsic Certified Robustness of Bagging against Data Poisoning Attackscited by 90
  16. 2020Towards More Practical Adversarial Attacks on Graph Neural Networkscited by 76
  17. 2020Consistency Regularization for Certified Robustness of Smoothed Classifierscited by 73
  18. 2019Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifierscited by 65
  19. 2019Certifiable Robustness to Graph Perturbationscited by 62
  20. 2019Certifiable Robustness and Robust Training for Graph Convolutional Networkscited by 59
  21. 2019Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablationcited by 59
  22. 2020Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbationcited by 57
  23. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  24. 2021PointGuard: Provably Robust 3D Point Cloud Classificationcited by 49
  25. 2021Boosting Randomized Smoothing with Variance Reduced Classifierscited by 47
  26. 2021Improved, Deterministic Smoothing for L_1 Certified Robustnesscited by 39
  27. 2023Are Defenses for Graph Neural Networks Robust?cited by 38
  28. 2020Higher-Order Certification for Randomized Smoothingcited by 36
  29. 2023Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directionscited by 28
  30. 2021Intriguing Properties of Input-dependent Randomized Smoothingcited by 24
  31. 2023Revisiting Robustness in Graph Machine Learningcited by 19
  32. 2023RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletioncited by 17
  33. 2023Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networkscited by 16
  34. 2020Certified Robustness of Graph Classification against Topology Attack with Randomized Smoothingcited by 12
  35. 2022Robust and Accurate -- Compositional Architectures for Randomized Smoothingcited by 12
  36. 2020Tight Second-Order Certificates for Randomized Smoothingcited by 10
  37. 2022TPC: Transformation-Specific Smoothing for Point Cloud Modelscited by 10
  38. 2022Localized Randomized Smoothing for Collective Robustness Certificationcited by 10

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 4; 2025: 2; 2026: 2.

9 papers.

  1. 2024Soft Prompt Threats: Attacking Safety Alignment and Unlearning in Open-Source LLMs through the Embedding Spacecited by 88
  2. 2025Probabilistic Stability Guarantees for Feature Attributionscited by 9
  3. 2023Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attackscited by 8
  4. 2024Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attackscited by 5
  5. 2025Bridging the Theoretical Gap in Randomized Smoothingcited by 2
  6. 2024Training More Robust Classification Model via Discriminative Loss and Gaussian Noise Injectioncited by 1
  7. 2024Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretationcited by 0
  8. 2026Laplace-Bridged Randomized Smoothing for Fast Certified Robustnesscited by 0
  9. 2026Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacycited by 0