# Diagonalizable Directed Message Passing

- ID: 2290
- Canonical URL: https://synthcore.org/idea/2290/diagonalizable-directed-message-passing
- API JSON: https://synthcore.org/api/idea/2290.json
- API Markdown: https://synthcore.org/api/idea/2290.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.14439](https://arxiv.org/abs/2608.14439)
- Category: architecture
- Solves: stability, accuracy, scalability
- ML areas: graph-nn, ssm, training-dynamics
- Math tags: spectral-theory, linear-algebra, graph-theory, dynamical-systems
- Ratings: usefulness 8/10; difficulty 6/10; novelty 7/10

## Idea description

Replace arbitrary directed-edge weights in a graph neural ODE or recurrent message-passing layer by weights constructed to make the directed Laplacian diagonalizable. This removes Jordan-block coupling, allowing the linearized graph dynamics to be represented as independent eigenmodes rather than modes with polynomial transients such as t^k exp(lambda t).

## Mathematical statement

Let G=(V,E) be a weakly connected loopless digraph with positive arc weights omega_ij. The in-degree Laplacian is L=D-A, where A_ij=omega_ji when arc (v_j,v_i) exists and D_ii is the weighted indegree of vertex v_i. Select a spanning directed acyclic subgraph with one source per root strongly connected component. Assign its edges so all non-source weighted indegrees are distinct; its Laplacian L_D is triangular with distinct nonzero diagonal entries and semisimple zero eigenvalues. Restore every omitted edge with common weight epsilon, giving L(epsilon)=L_D+epsilon R. If q_epsilon(s)=det(sI-L(epsilon))/s^r is the reduced characteristic polynomial, then sufficiently small positive epsilon preserves simple nonzero roots. The first collision is detected by Disc(q_epsilon)=0.

## Key formulas

- $$A_{ij}=\begin{cases}\omega_{ji},&(v_j,v_i)\in E,\\0,&\text{otherwise},\end{cases}\qquad L=D-A,\qquad D_{ii}=\sum_{j:(v_j,v_i)\in E}\omega_{ji}.$$
- $$L(\varepsilon)=L_D+\varepsilon R,\qquad q_\varepsilon(s)=\frac{\det(sI-L(\varepsilon))}{s^r}.$$
- $$\operatorname{Disc}(q_\varepsilon)=0\Longleftrightarrow q_\varepsilon\text{ has a repeated nonzero eigenvalue},\qquad 0<\varepsilon<\varepsilon_c:=\inf\{\varepsilon>0:\operatorname{Disc}(q_\varepsilon)=0\}.$$
- $$e^{-\tau L(\varepsilon)}=V\operatorname{diag}(e^{-\tau\lambda_1},\ldots,e^{-\tau\lambda_n})V^{-1}\quad\text{when }L(\varepsilon)=V\Lambda V^{-1}.$$

## Implementation notes

Integration point: use the construction before training a directed graph neural ODE, graph state-space model, or recurrent layer with propagation dh/dt=-tau Lh+f_theta(h,x), or residual update h_(k+1)=h_k-eta Lh_k+f_theta(h_k,x_k). Compute strongly connected components, choose a directed spanning forest with one source per root SCC, and topologically order its edges. Assign selected-edge weights greedily so every non-source weighted indegree is distinct, for example target indegrees d_i=i delta. Set every omitted edge to epsilon. Pseudocode: `SCC=tarjan(G); T=choose_rooted_forest(G,SCC); omega=assign_positive_distinct_indegrees(T); Ld=laplacian(T,omega); R=laplacian(G\T,unit_weights); scan eps_grid; L=Ld+eps*R; eig=eigvals(L); gap=min_pairwise_nonzero_gap(eig); choose largest safe eps; run model`. The paper supplies the forest construction and diagonalizability guarantee; code estimates eigenvalues, eigenvectors, condition number, and the discriminant numerically. First experiment: compare this design with unit and random weights on a directed GCN or graph neural ODE using Cora and synthetic directed stochastic block graphs. Sweep epsilon across the predicted collision boundary. Measure eigenvalue gaps, eigenvector condition number, modal reconstruction error, and hidden-state norm over long horizons. Prediction: below epsilon_c there are no nonzero eigenvalue collisions and reconstruction error is numerical precision; at the first discriminant root, the gap vanishes and conditioning sharply worsens. A defective baseline should show polynomial Jordan transients, while the designed model should remove them.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built a reproducible directed-Laplacian weighting experiment for a 3-node chain with a restored edge. The math predictions manifested: the reduced-polynomial discriminant predicted the first collision at epsilon_c=0.1715728753, and the numerical collision matched it with gap 5.0e-8 and discriminant 1.8e-15. The measured eigenvalue gap matched the predicted square-root discriminant within 4.8e-15; conditioning worsened from 8.68 at epsilon=0.1 to 1279.8 near the collision, while the unit-weight chain was defective with condition number 2.66e16.

### Mechanism check

- Verdict: Built a reproducible directed-Laplacian weighting experiment for a 3-node chain with a restored edge. The math predictions manifested: the reduced-polynomial discriminant predicted the first collision at epsilon_c=0.1715728753, and the numerical collision matched it with gap 5.0e-8 and discriminant 1.8e-15. The measured eigenvalue gap matched the predicted square-root discriminant within 4.8e-15; conditioning worsened from 8.68 at epsilon=0.1 to 1279.8 near the collision, while the unit-weight chain was defective with condition number 2.66e16.
- Confidence: 9/10
- Limitations: Only a 3-node synthetic graph was tested; no GNN training, graph neural ODE benchmark, Cora data, FLOP/speed comparison, larger SCC construction, or general discriminant root solver was evaluated. The transient norm remains affected by nonnormality even for diagonalizable matrices, so the primary evidence is from eigenvalue, discriminant, conditioning, and modal-reconstruction checks.

### Practical benchmark

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

## Artifacts

- [bench_report.json](https://synthcore.org/code/802/bench_report.json)
- [experiment.py](https://synthcore.org/code/802/experiment.py)
- [report.md](https://synthcore.org/code/802/report.md)
- [report_bench_2026-09-01T105443.md](https://synthcore.org/code/802/report_bench_2026-09-01T105443.md)
- [results.json](https://synthcore.org/code/802/results.json)
- [stage2_bench.py](https://synthcore.org/code/802/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/802)

## Disclaimer

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