# Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theory

arXiv: https://arxiv.org/abs/2503.14299 · HTML: https://mlsanity.com/paper/2503.14299/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 45 references that are in the map.
- First posted on arXiv 18 Mar 2025.

## Builds on (most cited first, 27 of 27)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks](https://mlsanity.com/paper/2003.01690/) (2020)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [Mitigating Adversarial Effects Through Randomization](https://mlsanity.com/paper/1711.01991/) (2017)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [Robustness via curvature regularization, and vice versa](https://mlsanity.com/paper/1811.09716/) (2018)
- [Stochastic Activation Pruning for Robust Adversarial Defense](https://mlsanity.com/paper/1803.01442/) (2018)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [Randomization matters. How to defend against strong adversarial attacks](https://mlsanity.com/paper/2002.11565/) (2020)
- [Theoretical evidence for adversarial robustness through randomization](https://mlsanity.com/paper/1902.01148/) (2019)
- [The Many Faces of Adversarial Risk](https://mlsanity.com/paper/2201.08956/) (2022)
- [Adversarial Robustness of Stabilized NeuralODEs Might be from Obfuscated Gradients](https://mlsanity.com/paper/2009.13145/) (2020)
- [Mixed Nash Equilibria in the Adversarial Examples Game](https://mlsanity.com/paper/2102.06905/) (2021)
- [The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification](https://mlsanity.com/paper/2204.12676/) (2022)
- [Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classification](https://mlsanity.com/paper/2206.09098/) (2022)
- [Local Competition and Stochasticity for Adversarial Robustness in Deep Learning](https://mlsanity.com/paper/2101.01121/) (2021)
- [Towards Consistency in Adversarial Classification](https://mlsanity.com/paper/2205.10022/) (2022)
- [On the robustness of randomized classifiers to adversarial examples](https://mlsanity.com/paper/2102.10875/) (2021)
- [On the existence of solutions to adversarial training in multiclass classification](https://mlsanity.com/paper/2305.00075/) (2023)
- [Characterizing the Optimal 0-1 Loss for Multi-class Classification with a Test-time Attacker](https://mlsanity.com/paper/2302.10722/) (2023)
- [On the Role of Randomization in Adversarially Robust Classification](https://mlsanity.com/paper/2302.07221/) (2023)
- [Rethinking Feature Uncertainty in Stochastic Neural Networks for Adversarial Robustness](https://mlsanity.com/paper/2201.00148/) (2022)

## Abstract (arXiv)

Randomization as a mean to improve the adversarial robustness of machine learning models has recently attracted significant attention. Unfortunately, much of the theoretical analysis so far has focused on binary classification, providing only limited insights into the more complex multiclass setting. In this paper, we take a step toward closing this gap by drawing inspiration from the field of graph theory. Our analysis focuses on discrete data distributions, allowing us to cast the adversarial risk minimization problems within the well-established framework of set packing problems. By doing so, we are able to identify three structural conditions on the support of the data distribution that are necessary for randomization to improve robustness. Furthermore, we are able to construct several data distributions where (contrarily to binary classification) switching from a deterministic to a randomized solution significantly reduces the optimal adversarial risk. These findings highlight the crucial role randomization can play in enhancing robustness to adversarial attacks in multiclass classification.