Adversarial Perturbations in Discrete Feature Spaces

33 concepts24 papers1 proposal

In adversarial machine learning, the standard paradigm relies on a convenient mathematical luxury: continuity. When attacking an image classifier, an algorithm computes the gradient of the loss function with respect to the input pixels and shifts the image by an infinitesimal step in that direction. The resulting image looks identical to a human, but completely misleads the model.

But what happens when the data consists of medical codes, financial transactions, or server logs?

In these domains, data is categorical and discrete. There is no such thing as an "infinitesimal shift" from blood type A to blood type B, or from a GET request to a POST request. Modifying a discrete feature requires a categorical swap—a discrete jump that breaks the foundational mathematical assumptions of traditional gradient-based attacks and defenses.

Understanding how to evaluate and secure models operating on discrete feature spaces requires moving away from continuous geometry and embracing combinatorial optimization.

The Geometry of Discrete Failure

To understand why traditional attacks fail on categorical data, consider how discrete variables are typically presented to a neural network: one-hot encoding. A categorical feature with $K$ possible values is mapped to a vertex of a $K$-dimensional simplex (e.g., [1, 0, 0]).

When a standard gradient-based attack computes a step, it yields a continuous vector like [0.98, 0.02, 0.00]. This point lies in the interior of the simplex, representing an impossible, non-executable state. As Ihai Rosenberg et al. note in Adversarial Machine Learning Attacks and Defense Methods in the Cyber Security Domain, small mathematical shifts do not correspond to valid changes in structured domains like cybersecurity.

If an algorithm attempts to force these continuous updates back into valid discrete states, it encounters severe architectural biases. As demonstrated by Zhipeng He et al. in TabAttackBench: A Benchmark for Adversarial Attacks on Tabular Data, gradient-based optimization methods frequently overlook categorical features entirely. Because modifying a one-hot encoded variable requires flipping multiple dimensions simultaneously to maintain a valid probability distribution, standard attack algorithms are mathematically incentivized to focus exclusively on continuous numerical features, leaving a massive portion of the data's feature space unexploited.

Continuous Perturbation:  [1.0, 0.0, 0.0]  ---(+0.01)--->  [1.01, 0.01, -0.02]  (Invalid State)
Discrete Perturbation:    [1.0, 0.0, 0.0]  ---(Swap)--->   [0.0,  1.0,  0.0]   (Valid State)

This blind spot is highly dangerous. In financial sequence modeling, for instance, Ivan Fursov et al. discovered in Adversarial Attacks on Deep Models for Financial Transaction Records that discrete categorical identifiers (such as merchant codes) exert a significantly stronger influence on model decisions than continuous variables like transaction amounts.

The Combinatorial Nightmare

If we cannot use gradients to glide smoothly toward an adversarial example, we must search for discrete value swaps. This transforms the problem from continuous optimization into an $L_0$-norm combinatorial search: finding the minimum number of feature dimensions to alter to change the model's prediction.

For an input with $N$ categorical features, each capable of taking $K$ values, the search space is discrete and exponentially large. Finding the globally optimal perturbation is an NP-hard challenge.

To bypass this computational wall, researchers leverage specific mathematical structures within classifiers:

1. Submodular Maximization

When a classifier's decision boundary satisfies certain smoothness properties, the impact of making discrete feature swaps can exhibit submodularity—a discrete analogue of concavity where adding a perturbation yields diminishing returns. In Towards Understanding the Robustness Against Evasion Attack on Categorical Data, Hongyan Bao et al. proved that treating discrete evasion attacks as a submodular maximization problem allows algorithms to achieve provable approximation guarantees, making domain-agnostic robustness assessments mathematically tractable.

2. Greedy and Bandit Heuristics

If submodularity cannot be guaranteed, greedy search strategies often prove surprisingly effective. In AdvCat: Domain-Agnostic Robustness Assessment for Cybersecurity-Critical Applications with Categorical Inputs, Hélène Orsini et al. demonstrated that simple greedy search strategies are theoretically optimal for identifying vulnerabilities in categorical models. To scale this to high-dimensional spaces, Hongyan Bao et al. introduced a framework in Towards Efficient and Domain-Agnostic Evasion Attack with High-Dimensional Categorical Inputs that pairs gradient-based feature ranking with multi-armed bandit exploration, isolating high-leverage categorical features without exhaustive brute-force searching.

Real-World Constraints: Cost, Utility, and Semantics

In computer vision, an adversarial perturbation is bounded by a small $L_p$-norm to ensure it remains invisible to the human eye. In discrete domains, this metric loses its meaning. Changing a binary flag from 0 to 1 has an $L_p$ distance of exactly 1, regardless of whether that flag represents a harmless configuration or a critical system error.

Instead of imperceptibility, discrete perturbations must respect semantic consistency and functionality preservation.

+-----------------------------------------------------------------------+
| Continuous Space (Images)       | Discrete Space (Tabular/Logs)       |
+-----------------------------------------------------------------------+
| Constraint: Small Lp-norm       | Constraint: Cost, Utility, Semantics|
| Effect: Infinitesimal shift     | Effect: Categorical value swap      |
| Goal: Human imperceptibility    | Goal: System validity / Feasibility |
+-----------------------------------------------------------------------+

As argued by Klim Kireev et al. in Adversarial Robustness for Tabular Data through Cost and Utility Awareness, robustness frameworks for tabular data must be centered on adversarial cost (the real-world effort or money required to alter a feature) and utility (the net profit an attacker gains). For example, an attacker might easily forge a minor log entry, but changing a medical history or a bank account age is either impossible or prohibitively expensive.

Furthermore, naive substitution risks creating impossible data states. If an optimization framework treats categorical features as continuous values during robust training, it inadvertently allows the model to defend against impossible data points. As Aras Selvi et al. show in Wasserstein Logistic Regression with Mixed Features, allowing these unrealistic perturbations forces models to become overly conservative, ultimately degrading their predictive accuracy on valid, real-world data.

Designing Robust Discrete Defenses

Because discrete spaces resist standard gradient-based adversarial training, defending models requires alternative paradigms that either bypass explicit attack generation or map discrete tokens into inherently stable spaces.

Attack-Free Evaluation

Rather than running expensive combinatorial optimization loops during training to find adversarial examples, the authors of Attack-free Evaluating and Enhancing Adversarial Robustness on Categorical Data (Yujun Zhou et al.) proposed an analytical framework. By mathematically bounding the model's sensitivity to discrete $L_0$ shifts without explicitly generating attacks, they avoid the computational bottlenecks of combinatorial optimization while providing rigorous robustness guarantees.

Universal Robust Embeddings

Another powerful approach is to fix the vulnerability at the input layer. In Transferable Adversarial Robustness for Categorical Data via Universal Robust Embeddings, Klim Kireev et al. developed a method that maps discrete categories into a continuous embedding space designed such that discrete swaps correspond to bounded, predictable continuous shifts. This allows even non-neural models, such as Random Forests, to inherit transferable adversarial robustness against discrete manipulation.

By shifting the focus from continuous gradients to structured, combinatorial optimization, researchers are closing the vulnerability gap, ensuring that machine learning models remain resilient even when the world they process is fundamentally discrete.

Key Foundational Work

Is Feature Selection Secure against Training Data Poisoning? (2015) — contributed 1 concept elements to this direction.
On the Robustness of Cooperative Multi-Agent Reinforcement Learning (2020) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_discrete_feature_perturbation_a9b2a2a4,
  title = {discrete feature perturbation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-feature-perturbation/rdr_a9b2a2a4be8a4697aa05f7d1ae50d1d4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_discrete_feature_perturbation_a9b2a2a4_v1,
  title = {discrete feature perturbation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-feature-perturbation/rdr_a9b2a2a4be8a4697aa05f7d1ae50d1d4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake