# Adversarial Decision-Equivalent Training

- ID: 2028
- Canonical URL: https://synthcore.org/idea/2028/adversarial-decision-equivalent-training
- API JSON: https://synthcore.org/api/idea/2028.json
- API Markdown: https://synthcore.org/api/idea/2028.md
- Verification status: failed_benchmark
- Source: [arXiv:2608.09036](https://arxiv.org/abs/2608.09036)
- Category: training
- Solves: accuracy, generalization, stability
- ML areas: graph-nn, loss, training, optimizer
- Math tags: optimization, combinatorics, game-theory
- Ratings: usefulness 8/10; difficulty 6/10; novelty 6/10

## Idea description

Train a graph cost predictor not only on the nominal shortest-path decision, but on budget-limited edge perturbations that cause its predicted path to disagree with the true shortest path. The perturbation is an interdiction vector that adds known delays to selected edges, forcing the model to learn path-cost margins and relative rankings rather than merely any cost function that reproduces the nominal argmin.

## Mathematical statement

The paper's PFL baseline is the edge-cost MSE $\ell_{\mathrm{MSE}}(\hat{\boldsymbol c};\boldsymbol c)=\|\hat{\boldsymbol c}-\boldsymbol c\|_2^2$, where $\boldsymbol c\in\mathbb R^{|E|}$ is the vector of true arc costs and $\hat{\boldsymbol c}=f_\theta(G,w)$ is the neural prediction. Its DFL regret is $\ell_{\mathrm{DFL}}(\hat{\boldsymbol c};\boldsymbol c)=\boldsymbol c^\top(\boldsymbol y^*(\hat{\boldsymbol c})-\boldsymbol y^*(\boldsymbol c))$, where $\boldsymbol y^*(q)$ is a binary source-to-target path minimizing $q^\top\boldsymbol y$ over all feasible paths. The paper exhibits the decision-equivalence class $\mathcal F_{DFL}=\{f:\mathbb R^2\to\mathbb R^2\mid f(w)=\boldsymbol a w+\boldsymbol b,\ b_1=b_2,\ a_1>a_2\}$: every predictor in this class preserves the nominal path ordering and therefore has zero DFL loss despite incorrect slopes. Interdiction uses $\boldsymbol x\in\{0,1\}^{|E|}$ with $\sum_{e\in E}x_e\le B$ and adds $\boldsymbol d\odot\boldsymbol x$ to arc costs, where $B$ is the perturbation budget and $d_e\ge0$ is the known delay on edge $e$. The adapted adversarial DFL objective is $\mathcal L_{A\text{-}DFL}(\theta)=\max_{\boldsymbol x:\,\boldsymbol x\in\{0,1\}^{|E|},\ \mathbf1^\top\boldsymbol x\le B}(\boldsymbol c+\boldsymbol d\odot\boldsymbol x)^\top[\boldsymbol y^*(\hat{\boldsymbol c}+\boldsymbol d\odot\boldsymbol x)-\boldsymbol y^*(\boldsymbol c+\boldsymbol d\odot\boldsymbol x)]$. This maximization searches for scenarios that break nominal decision equivalence.

## Key formulas

- $$\ell_{\mathrm{MSE}}(\hat{\boldsymbol c};\,\boldsymbol c)=\|\hat{\boldsymbol c}-\boldsymbol c\|_2^2$$
- $$\ell_{\mathrm{DFL}}(\hat{\boldsymbol c};\,\boldsymbol c)=\boldsymbol c^{\top}\left(\boldsymbol y^{\ast}(\hat{\boldsymbol c})-\boldsymbol y^{\ast}(\boldsymbol c)\right)$$
- $$\mathcal F_{DFL}=\{f:\mathbb R^{2}\rightarrow\mathbb R^{2}\mid f(w)=\boldsymbol a w+\boldsymbol b,\ b_{1}=b_{2},\ a_{1}>a_{2}\}$$
- $$\mathcal L_{A\text{-}DFL}(\theta)=\max_{\substack{\boldsymbol x\in\{0,1\}^{|E|}\\\mathbf1^\top\boldsymbol x\le B}}(\boldsymbol c+\boldsymbol d\odot\boldsymbol x)^\top\left[\boldsymbol y^*(\hat{\boldsymbol c}+\boldsymbol d\odot\boldsymbol x)-\boldsymbol y^*(\boldsymbol c+\boldsymbol d\odot\boldsymbol x)\right]$$

## Implementation notes

Integrate this at the output of a graph neural network that predicts one nonnegative cost $\hat c_e$ per edge. During training, replace the nominal shortest-path loss with a worst-case scenario loss. For each graph, compute $\hat{\boldsymbol c}=f_\theta(G,w)$ and obtain the oracle costs $\boldsymbol c$. Generate feasible interdiction vectors $x$ satisfying $x_e\in\{0,1\}$ and $\sum_e x_e\le B$. For small graphs, enumerate all subsets of at most $B$ edges; for larger graphs, use greedy or beam search, repeatedly adding the edge whose delay produces the largest current regret and retaining the top $K$ scenarios. For every candidate $x$, form $q_{pred}=\hat c+d\odot x$ and $q_{true}=c+d\odot x$, then compute the predicted and oracle shortest paths. Evaluate $R_x=q_{true}^\top[y^*(q_{pred})-y^*(q_{true})]$ and backpropagate through the maximum-regret scenario. Because exact shortest paths are discrete, use a temperature-$\tau$ soft shortest-path layer during backpropagation, replacing hard selection by $y_\tau^*(q)=\operatorname{softmin}_{y\in\mathcal P}(q^\top y/\tau)$, or use a perturb-and-MAP finite-difference gradient while retaining exact paths for evaluation. Mix robust and nominal losses as $L=\lambda\max_xR_x+(1-\lambda)R_{x=0}+\beta\|\hat c-c\|_2^2$, with $\lambda$ increased from 0 to 1 during training. The exact mathematical components are the budgeted scenario constraint, shortest-path oracle, and regret; the soft temperature, beam width, and mixing schedule are empirical approximations. First test on randomly generated 20-node directed graphs with two or three alternative routes, comparing MSE-PFL, nominal DFL, and A-DFL at equal training steps. Measure nominal regret, worst-case regret over all budget-$B$ interdictions, path disagreement rate, and cost MSE. Success means lower worst-case regret and fewer adversarial path flips at similar nominal regret, even if MSE does not improve. Then validate on a small road-network benchmark with $B=1,2$ using an exactly enumerated adversary.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: harms
- Verdict: Built a reproducible two-route MVP with exact budgeted interdiction enumeration, hard shortest-path evaluation, and differentiable nominal/adversarial training surrogates. The math check observed the predicted regret onset, linear slope, and scaling law exactly. Adversarial training reduced worst-case regret from 0.099685 to 0 and flip rate from 0.325 to 0 versus nominal decision training at equal setup, but MSE performed best overall on this simple task, so this is evidence for the mechanism rather than a general performance win.

### Mechanism check

- Verdict: Built a reproducible two-route MVP with exact budgeted interdiction enumeration, hard shortest-path evaluation, and differentiable nominal/adversarial training surrogates. The math check observed the predicted regret onset, linear slope, and scaling law exactly. Adversarial training reduced worst-case regret from 0.099685 to 0 and flip rate from 0.325 to 0 versus nominal decision training at equal setup, but MSE performed best overall on this simple task, so this is evidence for the mechanism rather than a general performance win.
- Confidence: 8/10
- Limitations: Only a two-edge/two-route synthetic system was tested, with a simple realizable predictor and B=1; no 20-node random graphs, road-network benchmark, larger budgets, beam search, GPU path, or broader seed sweep was evaluated. The training objective uses cross-entropy on oracle choices rather than a fully differentiable exact regret expression.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 0/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [README.md](https://synthcore.org/code/767/README.md)
- [bench_report.json](https://synthcore.org/code/767/bench_report.json)
- [report.md](https://synthcore.org/code/767/report.md)
- [report_bench_2026-09-02T161645.md](https://synthcore.org/code/767/report_bench_2026-09-02T161645.md)
- [results.json](https://synthcore.org/code/767/results.json)
- [route_track.py](https://synthcore.org/code/767/route_track.py)
- [run_experiment.py](https://synthcore.org/code/767/run_experiment.py)
- [stage2_bench.py](https://synthcore.org/code/767/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/767)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.