# Incidence-Matrix Structured Action Head

- ID: 1254
- Canonical URL: https://synthcore.org/idea/1254/incidence-matrix-structured-action-head
- API JSON: https://synthcore.org/api/idea/1254.json
- API Markdown: https://synthcore.org/api/idea/1254.md
- Verification status: beats_baseline
- Source: [arXiv:2607.21831](https://arxiv.org/abs/2607.21831)
- Category: architecture
- Solves: scalability, accuracy, generalization
- ML areas: graph-nn, rl, moe-routing
- Math tags: graph-theory, linear-algebra, combinatorics
- Ratings: usefulness 7/10; difficulty 4/10; novelty 6/10

## 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.

## 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.

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

## 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:
```text
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

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: helps
- Verdict: 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.

### Mechanism check

- Verdict: 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.
- Confidence: 8/10
- 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.

### Practical benchmark

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

## Artifacts

- [bench_report.json](https://synthcore.org/code/502/bench_report.json)
- [custom_incidence_actions.py](https://synthcore.org/code/502/custom_incidence_actions.py)
- [experiment.py](https://synthcore.org/code/502/experiment.py)
- [report.md](https://synthcore.org/code/502/report.md)
- [report_bench_2026-08-31T161750.md](https://synthcore.org/code/502/report_bench_2026-08-31T161750.md)
- [results.json](https://synthcore.org/code/502/results.json)
- [stage2_bench.py](https://synthcore.org/code/502/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/502)

## Disclaimer

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