✗ Failed on benchmark 2026

Adversarial Decision-Equivalent Training

Implementation & benchmark of arXiv:2608.09036 — Decision-Focused Learning in Network Interdiction Games

Usefulness8/10

Difficulty6/10

Novelty6/10

Training Accuracy Generalization Stability Graph nn Loss Training Optimizer Optimization Combinatorics Game theory

Source paper: Decision-Focused Learning in Network Interdiction Games arXiv:2608.09036 ⓘ · analyzed Sep 1, 2026

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

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.

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]$$

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.

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

Failed on benchmark

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

Stage 2 · Practical benchmark result: Significantly worse ✗

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

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.

Agent confidence: 8/10

Baseline: MSE: nominal regret 0.000000, worst-case regret 0.000000, flip rate 0.000, cost MSE 0.000513; nominal DFL: nominal regret 0.000000, worst-case regret 0.099685, max 0.438445, flip rate 0.325, cost MSE 0.041751
Idea: A-DFL: nominal regret 0.000000, worst-case regret 0.000000, max 0.000000, flip rate 0.000, cost MSE 0.056332; mechanism slope 1.0000000000000002 and scaling error 0

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.

How to run: python3 run_experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.09036) Sep 2, 2026

Significantly WORSE than the tuned baseline (+5122.4%, p=0.0081, wins 0 / 8 paired seeds).

Benchmark: Budgeted_route_costs
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 0.0024
Idea mean: 0.1244
Effect (Δ): 0.122 (+5122.4%; negative = idea better)
Wins: 0 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±2528.2%
Mechanism: Not confirmed ✗
Practical effect: Hurts
Baseline tuning: swept over 6 configs

Limitations:

The built-in tracks lack shortest-path graph structure, so the accepted custom two-parallel-route track was used. It tests four edges and budget B=1, not larger random graphs or road networks; the training surrogate is a soft route expectation over five enumerated scenarios, with exact hard regret evaluation.

How to run: python3 stage2_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 2, 2026 latest Failed ✗

Agent confidence: 10/10

The registered custom graph-decision track budgeted_route_costs was benchmarked end-to-end with matched mlp_tiny systems, a tuned six-configuration baseline sweep, three idea settings, and 8 paired seeds. The adversarial method was significantly worse on independent test MSE (paired delta +0.1220390537, permutation p=0.0081), and its measured worst-case regret was slightly worse, so this is not a win.

Baseline: test MSE mean 0.0023824744; best lr=0.01, wd=0.0001; worst-regret mean 0.0062907608
Idea: test MSE mean 0.1244215281; best lr=0.01, wd=0.0001; worst-regret mean 0.0063806495; mechanism confirmed=false

Benchmark result