# Discrete Adversarial Attacks and Submodular Optimization with Applications to Text Classification

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2018.

## Built on by (most cited first, 30 of 35)

- [RADAR: Robust AI-Text Detection via Adversarial Learning](https://mlsanity.com/paper/2307.03838/) (2023)
- [Measure and Improve Robustness in NLP Models: A Survey](https://mlsanity.com/paper/2112.08313/) (2021)
- [Certified Robustness to Text Adversarial Attacks by Randomized [MASK]](https://mlsanity.com/paper/2105.03743/) (2021)
- [Achieving Model Robustness through Discrete Adversarial Training](https://mlsanity.com/paper/2104.05062/) (2021)
- [ALLSH: Active Learning Guided by Local Sensitivity and Hardness](https://mlsanity.com/paper/2205.04980/) (2022)
- [Data Poisoning for In-context Learning](https://mlsanity.com/paper/2402.02160/) (2024)
- [A Word is Worth A Thousand Dollars: Adversarial Attack on Tweets Fools Stock Predictions](https://mlsanity.com/paper/2205.01094/) (2022)
- [Adversarial Robustness for Tabular Data through Cost and Utility Awareness](https://mlsanity.com/paper/2208.13058/) (2022)
- [Are AlphaZero-like Agents Robust to Adversarial Perturbations?](https://mlsanity.com/paper/2211.03769/) (2022)
- [Auditing and Generating Synthetic Data with Controllable Trust Trade-offs](https://mlsanity.com/paper/2304.10819/) (2023)
- [Holistic Adversarial Robustness of Deep Learning Models](https://mlsanity.com/paper/2202.07201/) (2022)
- [Input-agnostic Certified Group Fairness via Gaussian Parameter Smoothing](https://mlsanity.com/paper/2206.11423/) (2022)
- [Re-evaluating Word Mover's Distance](https://mlsanity.com/paper/2105.14403/) (2021)
- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)
- [PAD: Towards Principled Adversarial Malware Detection Against Evasion Attacks](https://mlsanity.com/paper/2302.11328/) (2023)
- [AdaLoss: A computationally-efficient and provably convergent adaptive gradient method](https://mlsanity.com/paper/2109.08282/) (2021)
- [Adversarial Attacks and Defenses for Social Network Text Processing Applications: Techniques, Challenges and Future Research Directions](https://mlsanity.com/paper/2110.13980/) (2021)
- [Revisiting Character-level Adversarial Attacks for Language Models](https://mlsanity.com/paper/2405.04346/) (2024)
- [Robust Text Classification: Analyzing Prototype-Based Networks](https://mlsanity.com/paper/2311.06647/) (2023)
- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)
- [Adversarial Machine Learning in Text Analysis and Generation](https://mlsanity.com/paper/2101.08675/) (2021)
- [Lost In Translation: Generating Adversarial Examples Robust to Round-Trip Translation](https://mlsanity.com/paper/2307.12520/) (2023)
- [Using Constraint Programming and Graph Representation Learning for Generating Interpretable Cloud Security Policies](https://mlsanity.com/paper/2205.01240/) (2022)
- [Word Tour: One-dimensional Word Embeddings via the Traveling Salesman Problem](https://mlsanity.com/paper/2205.01954/) (2022)
- [Adversarial AI in Insurance: Pervasiveness and Resilience](https://mlsanity.com/paper/2301.07520/) (2023)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [Adversarial Sample Enhanced Domain Adaptation: A Case Study on Predictive Modeling with Electronic Health Records](https://mlsanity.com/paper/2101.04853/) (2021)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Moving Other Way: Exploring Word Mover Distance Extensions](https://mlsanity.com/paper/2202.03119/) (2022)

## Abstract (arXiv)

Adversarial examples are carefully constructed modifications to an input that completely change the output of a classifier but are imperceptible to humans. Despite these successful attacks for continuous data (such as image and audio samples), generating adversarial examples for discrete structures such as text has proven significantly more challenging. In this paper we formulate the attacks with discrete input on a set function as an optimization task. We prove that this set function is submodular for some popular neural network text classifiers under simplifying assumption. This finding guarantees a 1-1/e approximation factor for attacks that use the greedy algorithm. Meanwhile, we show how to use the gradient of the attacked classifier to guide the greedy search. Empirical studies with our proposed optimization scheme show significantly improved attack ability and efficiency, on three different text classification tasks over various baselines. We also use a joint sentence and word paraphrasing technique to maintain the original semantics and syntax of the text. This is validated by a human subject evaluation in subjective metrics on the quality and semantic coherence of our generated adversarial text.