# Towards Efficient and Domain-Agnostic Evasion Attack with High-dimensional Categorical Inputs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 40 references that are in the map.
- First posted on arXiv 13 Dec 2022.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailment](https://mlsanity.com/paper/1907.11932/) (2019)
- [Adversarial Examples for Evaluating Reading Comprehension Systems](https://mlsanity.com/paper/1707.07328/) (2017)
- [BERT-ATTACK: Adversarial Attack Against BERT Using BERT](https://mlsanity.com/paper/2004.09984/) (2020)
- [TextBugger: Generating Adversarial Text Against Real-world Applications](https://mlsanity.com/paper/1812.05271/) (2018)
- ["Liar, Liar Pants on Fire": A New Benchmark Dataset for Fake News Detection](https://mlsanity.com/paper/1705.00648/) (2017)
- [Black-box Generation of Adversarial Text Sequences to Evade Deep Learning Classifiers](https://mlsanity.com/paper/1801.04354/) (2018)
- [FakeNewsNet: A Data Repository with News Content, Social Context and Spatialtemporal Information for Studying Fake News on Social Media](https://mlsanity.com/paper/1809.01286/) (2018)
- [Adversarial Training Methods for Semi-Supervised Text Classification](https://mlsanity.com/paper/1605.07725/) (2016)
- [Audio Adversarial Examples: Targeted Attacks on Speech-to-Text](https://mlsanity.com/paper/1801.01944/) (2018)
- [TESSERACT: Eliminating Experimental Bias in Malware Classification across Space and Time](https://mlsanity.com/paper/1807.07838/) (2018)
- [Crafting Adversarial Input Sequences for Recurrent Neural Networks](https://mlsanity.com/paper/1604.08275/) (2016)
- [Sparse and Imperceivable Adversarial Attacks](https://mlsanity.com/paper/1909.05040/) (2019)
- [Yelp Dataset Challenge: Review Rating Prediction](https://mlsanity.com/paper/1605.05362/) (2016)
- [Towards Crafting Text Adversarial Samples](https://mlsanity.com/paper/1707.02812/) (2017)
- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [Adversarial Attacks for Tabular Data: Application to Fraud Detection and Imbalanced Data](https://mlsanity.com/paper/2101.08030/) (2021)
- [Exploring Adversarial Examples in Malware Detection](https://mlsanity.com/paper/1810.08280/) (2018)
- [Greedy Attack and Gumbel Attack: Generating Adversarial Examples for Discrete Data](https://mlsanity.com/paper/1805.12316/) (2018)
- [On the Suboptimality of Thompson Sampling in High Dimensions](https://mlsanity.com/paper/2102.05502/) (2021)

## Built on by (most cited first, 3 of 3)

- [Constrained Adaptive Attack: Effective Adversarial Attack Against Deep Neural Networks for Tabular Data](https://mlsanity.com/paper/2406.00775/) (2024)
- [TabularBench: Benchmarking Adversarial Robustness for Tabular Deep Learning in Real-world Use-cases](https://mlsanity.com/paper/2408.07579/) (2024)
- [Insights on Adversarial Attacks for Tabular Machine Learning via a Systematic Literature Review](https://mlsanity.com/paper/2506.15506/) (2025)

## Abstract (arXiv)

Our work targets at searching feasible adversarial perturbation to attack a classifier with high-dimensional categorical inputs in a domain-agnostic setting. This is intrinsically an NP-hard knapsack problem where the exploration space becomes explosively larger as the feature dimension increases. Without the help of domain knowledge, solving this problem via heuristic method, such as Branch-and-Bound, suffers from exponential complexity, yet can bring arbitrarily bad attack results. We address the challenge via the lens of multi-armed bandit based combinatorial search. Our proposed method, namely FEAT, treats modifying each categorical feature as pulling an arm in multi-armed bandit programming. Our objective is to achieve highly efficient and effective attack using an Orthogonal Matching Pursuit (OMP)-enhanced Upper Confidence Bound (UCB) exploration strategy. Our theoretical analysis bounding the regret gap of FEAT guarantees its practical attack performance. In empirical analysis, we compare FEAT with other state-of-the-art domain-agnostic attack methods over various real-world categorical data sets of different applications. Substantial experimental observations confirm the expected efficiency and attack effectiveness of FEAT applied in different application scenarios. Our work further hints the applicability of FEAT for assessing the adversarial vulnerability of classification systems with high-dimensional categorical inputs.