✓✓ Beats tuned baseline 2026

Incidence-Matrix Structured Action Head

Implementation & benchmark of arXiv:2607.21831 — A Graph-Based Control Interface for Traffic Signals on Heterogeneous Road Networks

Usefulness7/10

Difficulty4/10

Novelty6/10

Architecture Scalability Accuracy Generalization Graph nn Rl Moe routing Graph theory Linear algebra Combinatorics

Source paper: A Graph-Based Control Interface for Traffic Signals on Heterogeneous Road Networks arXiv:2607.21831 ⓘ · analyzed Aug 30, 2026

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

Idea description

Build a policy or prediction head that scores atomic graph entities once and converts those scores into logits for legal composite actions through an instance-specific incidence matrix. The neural parameters are independent of the number of actions and their composition, so the same model can process graphs with different action counts and compatibility structures without padding every action space to a global maximum.

Formulas

$$h_l^{(0)}=\rho(E_Lx_l)$$

$$h_m^{(0)}=\rho\!\left(E_M[x_m\|h_{i(m)}^{(0)}\|h_{o(m)}^{(0)}]\right)$$

$$\boldsymbol{\ell}_j=A_j\mathbf{s}_j,\qquad \ell_{j,p}=\sum_{m\in M_j}A_{j,p,m}s_m$$

$$\widetilde{\ell}_{j,p}=\frac{\sum_{m\in M_j}A_{j,p,m}s_m}{\left(\sum_{m\in M_j}A_{j,p,m}+\varepsilon\right)^\alpha},\qquad \alpha\in[0,1]$$

Mathematical statement

The paper represents each movement m by a learned scalar score s_m and each legal phase p by the binary incidence matrix A_j, where j indexes an instance or junction, A_j is in {0,1}^{|P_j| x |M_j|}, P_j is the set of legal composite actions, and M_j is the set of atomic actions. The local action logits are l_j = A_j s_j, equivalently l_{j,p} = sum_{m in M_j} A_{j,p,m}s_m. Thus each composite action receives the sum of the scores of its enabled atoms. The shared atomic scorer is constructed from typed graph embeddings: h_l^(0) = rho(E_L x_l), where x_l is a feature vector for graph node l, E_L is a learned projection, and rho is ReLU; for an atomic node m with input and output neighbors i(m), o(m), h_m^(0) = rho(E_M[x_m || h_{i(m)}^(0) || h_{o(m)}^(0)]), where x_m is its feature vector, E_M is another learned projection, and || denotes concatenation. For neural use, define s_m = w^T h_m + b and optionally use degree-normalized pooling l_tilde_{j,p} = sum_m A_{j,p,m}s_m / (sum_m A_{j,p,m} + epsilon)^alpha, with alpha in [0,1]. Alpha=0 reproduces the paper; alpha=1 removes the systematic logit advantage of larger composite actions; alpha=1/2 is an intermediate correction.

Implementation notes

(1) Integration point: use this as the policy head after a shared GNN or Transformer has produced embeddings h_m for atomic entities in each graph. This is most directly useful in graph RL, where each graph instance has a different number of legal composite actions; it can also be used for structured classification or constrained MoE routing. Construct a sparse incidence matrix A for every training example, with one row per legal action and one column per atomic entity. Add a linear scalar scorer s_m = dot(w,h_m)+b. Compute action logits with sparse matrix multiplication rather than constructing a padded action tensor. Apply the environment's invalid-action mask, then use softmax and PPO's categorical policy loss.

(2) Pseudocode:

inputs: graph G, atomic features x_m, legal-action incidence A, mask q
h_l = relu(E_L @ x_l)
h_m = relu(E_M @ concat(x_m, h_input(m), h_output(m)))
s_m = dot(w, h_m) + b
counts = row_sum(A)
logits = sparse_matmul(A, s)
logits = logits / (counts + eps)^alpha
logits[~q] = -inf
action ~ Categorical(softmax(logits))

Train with PPO or cross-entropy while sampling a fresh graph and action schema per batch.

(3) The paper's exact computation is the incidence pooling l=A s. Estimate no mathematical constants; choose alpha by validation, and build A from the environment's compatibility rules or a maximum-clique/enumeration routine. Keep raw-sum and normalized variants as ablations. Verify that every legal action has at least one incidence entry and that incompatible atomic entities never share a row.

(4) First experiment: compare this head against a padded MLP policy head on small graph scheduling or routing environments with 4-32 nodes and 2-100 legal composite actions per instance. Train on one distribution of graph sizes and evaluate on unseen sizes and action schemas. Measure PPO return, invalid-action rate, wall-clock time, peak activation memory, and parameter count. Success is higher return at equal training steps, no degradation when action count changes, and substantially lower padding overhead; a useful target is at least 2x reduction in policy-head activation memory and improved performance on unseen action schemas.

Verification

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Significant win ✓

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 an incidence-matrix structured action head with shared atomic scoring, plus a padded fixed-action MLP baseline. Numerical checks confirmed exact incidence additivity with maximum error 9.5e-7, the predicted logit scaling k^(1-alpha) for alpha=0, 0.5, and 1.0, and the predicted equal-score size bias. In the small unseen-schema experiment, the structured head reached 82.8% accuracy versus 6.8% for the padded MLP, with 97 versus 3,136 parameters and approximately 168 versus 2,048 stored feature elements per instance; this is promising evidence for schema generalization, though the baseline is deliberately limited and not a full PPO comparison.

Agent confidence: 8/10

Baseline: Padded MLP: unseen-schema accuracy 0.068, cross-entropy 13.9801, 3,136 parameters, 2,048 padded feature elements per instance, 61.87 seconds.
Idea: Incidence head: unseen-schema accuracy 0.828, cross-entropy 0.3567, 97 parameters, approximately 168 incidence elements per instance, 51.76 seconds; additivity maximum error 9.54e-7; observed normalization slopes 1.0000, 0.5000, and 0.0000 for alpha 0, 0.5, and 1.

Limitations: The experiment uses synthetic additive utilities rather than a real graph-RL environment, PPO, or a learned GNN with typed input/output neighbors. The padded baseline is a simple fixed-index MLP and does not represent a production-quality permutation-invariant padded policy; sparse GPU matrix multiplication and peak memory were not benchmarked directly.

How to run: python3 experiment.py

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

Beats the tuned baseline by 65.1% (p=0.0081, wins 8 / 8 paired seeds; metric: lower is better).

Benchmark: Incidence_actions
Model: custom_incidence_head
Paired seeds: 8
Baseline mean: 0.3563
Idea mean: 0.1242
Effect (Δ): -0.232 (−65.1%; negative = idea better)
Wins: 8 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±13.2%
Mechanism: Confirmed ✓
Practical effect: Helps
Baseline tuning: swept over 3 configs

Limitations:

The registered custom track is synthetic structured classification, not a real graph-RL/PPO environment. Sparse GPU memory and speed, typed graph neighbor embeddings, invalid-action environment behavior, action-count generalization beyond the generated range, and PPO returns were not tested. The padded comparator is matched in task and inputs but is not a production permutation-invariant global padded policy. The exact zero-error mechanism signature is an implementation consistency check because the structured head defines logits by incidence pooling.

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 Aug 31, 2026 latest Worked ✓

Agent confidence: 8/10

The registered custom track incidence_actions produced a significant win for the incidence-matrix structured action head. Mean test cross-entropy was 0.12422 versus 0.35625 for the tuned padded baseline, with 8/8 paired wins and permutation p=0.0081. The trained-model mechanism signature was confirmed, although this remains a synthetic structured-action benchmark rather than real graph-RL/PPO.

Baseline: mean test cross-entropy 0.3562500048428774; best_cfg={lr:0.006,epochs:12}; baseline sweep means: lr 0.001 -> 0.7750000208616257, lr 0.003 -> 0.6015625, lr 0.006 -> 0.3687500059604645
Idea: mean test cross-entropy 0.12421874981373549; best_cfg={lr:0.006,epochs:12,alpha:0.0}; per-seed=[0.09375,0.15000000596046448,0.14374999701976776,0.11874999850988388,0.15625,0.06875000149011612,0.14374999701976776,0.11874999850988388]

Benchmark result