# Edge-Supported Polynomial State Space

- ID: 1084
- Canonical URL: https://synthcore.org/idea/1084/edge-supported-polynomial-state-space
- API JSON: https://synthcore.org/api/idea/1084.json
- API Markdown: https://synthcore.org/api/idea/1084.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.17664](https://arxiv.org/abs/2607.17664)
- Category: architecture
- Solves: scalability, stability, accuracy
- ML areas: graph-nn, ssm, rnn, world-model
- Math tags: dynamical-systems, graph-theory, linear-algebra, tensor-decomposition, control-theory
- Ratings: usefulness 8/10; difficulty 5/10; novelty 8/10

## Idea description

Replace a complete tensor/Kronecker polynomial lift of a graph dynamical system with observables selected only from the support of the interaction graph. The lifted state can then be propagated by a sparse structured linear operator, while the first omitted degree is treated as an explicit residual or learned closure. This gives a graph-aware polynomial state-space layer for neural ODEs, graph RNNs, and world models.

## Mathematical statement

Let $G=(\mathcal V,\mathcal E)$ be a directed graph with $n=|\mathcal V|$, let $x\in\mathbb R^p$ be the base state, and let the dynamics be $\dot x=A_\ell x+f_Q(x)$, where $A_\ell$ is linear and $f_Q$ is a quadratic vector field. For the SEIR example, $p=4n$ and $f_Q$ contains only monomials $S_iI_j$ for $(i,j)\in\mathcal E$, with coefficient proportional to $\beta a_{ij}$. Define $\Phi_d^{\mathcal E}(x)=T_d^{\mathcal E}x^{\otimes d}$, where the sparse selection tensor $T_d^{\mathcal E}$ retains only monomials recursively generated from active edges and lower-degree observables. The lifted state is $z_d^{\mathcal E}(x)=\operatorname{col}(x,\Phi_2^{\mathcal E}(x),\ldots,\Phi_d^{\mathcal E}(x))$. The chain rule gives $\dot z_d^{\mathcal E}=K_d^{\mathcal E}z_d^{\mathcal E}+r_d^{\mathcal E}$, where $K_d^{\mathcal E}$ contains within-degree linear couplings and quadratic couplings from degree $k$ to degree $k+1$, and $r_d^{\mathcal E}=\operatorname{col}(0,\ldots,0,\mathcal L_{f_Q}\Phi_d^{\mathcal E}(x))$ is the first omitted degree-$d+1$ contribution. The key property is that dictionary size depends on graph support rather than all ordered tensor indices.

## Key formulas

- $$\dot{x}=A_\ell x+K_{1,2}^{\mathcal E}\Phi_2^{\mathcal E}(x),\qquad \Phi_d^{\mathcal E}(x)=T_d^{\mathcal E}x^{\otimes d}.$$
- $$z_d^{\mathcal E}(x)=\operatorname{col}\left(x,\Phi_2^{\mathcal E}(x),\ldots,\Phi_d^{\mathcal E}(x)\right),\qquad \frac{d}{dt}z_d^{\mathcal E}(x)=K_d^{\mathcal E}z_d^{\mathcal E}(x)+r_d^{\mathcal E}(x).$$
- $$r_d^{\mathcal E}(x)=\operatorname{col}\left(0,\ldots,0,\mathcal L_{f_Q}\Phi_d^{\mathcal E}(x)\right),\qquad \mathcal L_{f_Q}\Phi_d^{\mathcal E}(x)=D\Phi_d^{\mathcal E}(x)f_Q(x).$$
- $$\dim\Phi_2^{\mathcal E}=O(p+|\mathcal E|),\quad\text{whereas a complete degree-2 lift has }O(p^2)\text{ coordinates.}$$

## Implementation notes

1. Integration point: implement this as a fixed feature encoder and linear recurrent or ODE block inside a graph RNN or neural ODE. Given adjacency support $\mathcal E$, enumerate only base coordinates and active quadratic monomials such as $S_iI_j$; recursively construct degree-3 and higher monomials by differentiating the retained monomials under the known or learned quadratic interaction map. Use sparse COO indices for $T_d^{\mathcal E}$ and sparse block matrices for $K_d^{\mathcal E}$. 2. Pseudocode: initialize `z=[x]`; for `k=2,...,d`, append `select_edge_monomials(z,E)`; compute `dz=K_d@z`; optionally compute `r_hat=closure_mlp(z)` only in the final block; integrate `z <- solver_step(z,dz+r_hat,dt)`; decode the base state from the first $p$ coordinates. 3. Computed quantities are the graph support, sparse monomial indices, and exact linear/quadratic coefficient blocks when physical dynamics are known. For a learned model, estimate $K_d$ by least squares or gradient descent and estimate the closure from the observed residual $\dot z-K_dz$. 4. First cheap experiment: use a synthetic $n=32$ SEIR or quadratic graph system with an Erdős-Rényi or ring graph, comparing a dense polynomial lift, an edge lift, and a standard message-passing GNN at equal parameter count. Train one-step and rollout prediction. Measure dictionary size, wall-clock cost, rollout error, and $\|r_d\|_2$. The quantitative prediction is that degree-2 edge features scale linearly with $|\mathcal E|$ and remain far below the dense $p^2$ baseline; for fixed graph support, changing edge weights should not change feature dimension, while residual magnitude should increase with maximum weighted incoming intensity $\max_i\sum_j|a_{ij}|$ and approximately quadratically with state amplitude for the cubic omitted term.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built an edge-supported degree-2 polynomial state-space module and deterministic verification/mini-experiment scripts. The chain-rule identity matched finite differences with maximum error 3.88e-10, feature dimension scaled with observed slope 1.0 versus the predicted linear dependence on |E|, residual amplitude scaling had observed log-log slope 3.0, and interaction-weight scaling had slope 1.0000000000000004. The mechanism manifested clearly; the sparse model used 96 versus 1024 quadratic features and achieved near-zero exact-task test error, although its small NumPy encoder timing was not faster than dense encoding.

### Mechanism check

- Verdict: Built an edge-supported degree-2 polynomial state-space module and deterministic verification/mini-experiment scripts. The chain-rule identity matched finite differences with maximum error 3.88e-10, feature dimension scaled with observed slope 1.0 versus the predicted linear dependence on |E|, residual amplitude scaling had observed log-log slope 3.0, and interaction-weight scaling had slope 1.0000000000000004. The mechanism manifested clearly; the sparse model used 96 versus 1024 quadratic features and achieved near-zero exact-task test error, although its small NumPy encoder timing was not faster than dense encoding.
- Confidence: 9/10
- Limitations: Only degree-2 observables and a synthetic quadratic graph system were tested. No learned closure, higher-degree recursive dictionary, neural ODE integration, SEIR dynamics, GPU implementation, long-horizon rollout, or large-scale sparse performance benchmark was evaluated; the timing comparison is a small NumPy CPU microbenchmark.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.3069
- Paired wins: 6/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/195/bench_report.json)
- [edge_polynomial_ssm.py](https://synthcore.org/code/195/edge_polynomial_ssm.py)
- [mini_experiment.py](https://synthcore.org/code/195/mini_experiment.py)
- [mini_results.json](https://synthcore.org/code/195/mini_results.json)
- [report.md](https://synthcore.org/code/195/report.md)
- [report_bench_2026-08-30T195436.md](https://synthcore.org/code/195/report_bench_2026-08-30T195436.md)
- [results.json](https://synthcore.org/code/195/results.json)
- [stage2_bench.py](https://synthcore.org/code/195/stage2_bench.py)
- [verify_edge_polynomial.py](https://synthcore.org/code/195/verify_edge_polynomial.py)
- [Download all files as ZIP](https://synthcore.org/download/195)

## Disclaimer

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