Structural Causal Models Reveal Confounder Bias in Linear Program Modelling
This work addresses a potential vulnerability in optimization algorithms, which are fundamental to AI, by showing how causal models can expose adversarial risks, though it is incremental in extending adversarial concepts beyond classification tasks.
The paper investigates whether adversarial attacks, typically studied in deep neural networks, can be generalized to optimization problems, specifically Linear Programs (LPs), by using Structural Causal Models (SCMs) to reveal confounder bias that enables adversarial-style attacks. It provides formal proofs and demonstrates this on three combinatorial problems, including Linear Assignment and Shortest Path.
The recent years have been marked by extended research on adversarial attacks, especially on deep neural networks. With this work we intend on posing and investigating the question of whether the phenomenon might be more general in nature, that is, adversarial-style attacks outside classical classification tasks. Specifically, we investigate optimization problems as they constitute a fundamental part of modern AI research. To this end, we consider the base class of optimizers namely Linear Programs (LPs). On our initial attempt of a naïve mapping between the formalism of adversarial examples and LPs, we quickly identify the key ingredients missing for making sense of a reasonable notion of adversarial examples for LPs. Intriguingly, the formalism of Pearl's notion to causality allows for the right description of adversarial like examples for LPs. Characteristically, we show the direct influence of the Structural Causal Model (SCM) onto the subsequent LP optimization, which ultimately exposes a notion of confounding in LPs (inherited by said SCM) that allows for adversarial-style attacks. We provide both the general proof formally alongside existential proofs of such intriguing LP-parameterizations based on SCM for three combinatorial problems, namely Linear Assignment, Shortest Path and a real world problem of energy systems.