△ Mechanism confirmed, baseline not beaten 2026

Mean-field rainbow relation router

Implementation & benchmark of arXiv:2608.31130 — Colorful Exponential Random Graph Models

Usefulness7/10

Difficulty5/10

Novelty7/10

Architecture Accuracy Stability Generalization Graph nn Attention Moe routing Probability Graph theory Combinatorics Optimization

Source paper: Colorful Exponential Random Graph Models arXiv:2608.31130 ⓘ · analyzed Sep 2, 2026

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

Idea description

Replace independent edge-type logits in a relational graph neural network with a mean-field fixed-point router derived from a colored ERGM. Each edge's color distribution is influenced by its own relation bias and by the expected number of rainbow triangles it forms with neighboring edges, allowing the model to learn coordinated multilayer structures.

Formulas

$$\mathbb{P}_{n}(\mathscr{X})=\frac{1}{Z_{n}}\exp\left\{2\sum_{a=1}^{3}\beta_{a}|E_{a}(\mathscr{X})|+\frac{\beta_{4}}{n}\triangle_{\mathrm{rb}}(\mathscr{X})\right\}.$$

$$\mathcal{F}(p)=2\sum_{i<j}\sum_{a=1}^{3}\beta_a p_{ij}^{a}+\frac{\beta_4}{n}\sum_{i<j<k}\sum_{\substack{a,b,c\in\{1,2,3\}\\a,b,c\ \mathrm{pairwise\ distinct}}}p_{ij}^{a}p_{ik}^{b}p_{jk}^{c}+\tau\sum_{i<j}\mathsf{H}(p_{ij}),\qquad \mathsf{H}(p_{ij})=-\sum_{a=1}^{3}p_{ij}^{a}\log p_{ij}^{a}.$$

$$r_{ijk}^{a}=\sum_{\substack{b,c\in\{1,2,3\}\\a,b,c\ \mathrm{pairwise\ distinct}}}p_{ik}^{b}p_{jk}^{c},\qquad p_{ij}^{a}\leftarrow\frac{\exp\left((2\beta_a+(\beta_4/n)\sum_{k\ne i,j}r_{ijk}^{a})/\tau\right)}{\sum_{d=1}^{3}\exp\left((2\beta_d+(\beta_4/n)\sum_{k\ne i,j}r_{ijk}^{d})/\tau\right)}.$$

Mathematical statement

The paper's rainbow-triangle ERGM assigns a coloring $\mathscr{X}$ of the complete graph a probability proportional to $\exp\{2\sum_{a=1}^{3}\beta_a|E_a(\mathscr{X})|+(\beta_4/n)\triangle_{\mathrm{rb}}(\mathscr{X})\}$. Here $n$ is the number of vertices, $E_a(\mathscr{X})$ is the set of edges with color $a\in\{1,2,3\}$, $\triangle_{\mathrm{rb}}$ is the number of triangles whose three edge colors are pairwise distinct, and $\beta_1,\beta_2,\beta_3,\beta_4$ are energy coefficients. For a differentiable neural adaptation, let $p_{ij}^a$ be the probability that edge $(i,j)$ has color $a$, with $\sum_a p_{ij}^a=1$. Define the conditional rainbow score for assigning color $a$ to edge $(i,j)$ through vertex $k$ as $r_{ijk}^{a}=\sum_{b,c\in\{1,2,3\}\text{ such that }a,b,c\text{ are pairwise distinct}}p_{ik}^{b}p_{jk}^{c}$. The entropy-regularized mean-field free energy is $\mathcal{F}(p)=2\sum_{i<j}\sum_a\beta_a p_{ij}^a+(\beta_4/n)\sum_{i<j<k}\sum_{a,b,c\text{ pairwise distinct}}p_{ij}^ap_{ik}^bp_{jk}^c+\tau\sum_{i<j}\mathsf{H}(p_{ij})$, where $\mathsf{H}(p)=-\sum_a p^a\log p^a$ and $\tau>0$ is temperature. Coordinate stationarity gives the implementable update $p_{ij}^a\leftarrow\operatorname{softmax}_a((2\beta_a+(\beta_4/n)\sum_{k\ne i,j}r_{ijk}^{a})/\tau)$. The paper's $1/n$ normalization keeps the motif contribution extensive and prevents the update magnitude from growing with graph size.

Implementation notes

(1) Integration point: add a relation-type router before message passing in a relational GNN or graph transformer. For every candidate edge $(i,j)$, output three logits $u_{ij}^a$, convert them to probabilities $p_{ij}^a$, and use $p_{ij}^a$ to mix three relation-specific message operators. Apply two or three mean-field refinement iterations per forward pass; use sampled two-hop neighbors for large graphs. (2) Pseudocode: initialize $p_{ij}=\operatorname{softmax}(u_{ij})$; repeat $T=2$ to $5$ times: for each sampled third vertex $k$, compute $r_{ijk}^{a}=\sum_{b,c\text{ pairwise distinct from }a}p_{ik}^{b}p_{jk}^{c}$; set $s_{ij}^{a}=2\beta_a+(\beta_4/n)\sum_k r_{ijk}^{a}$; update $p_{ij}=\operatorname{softmax}(s_{ij}/\tau)$, optionally with damping $p\leftarrow(1-\alpha)p+\alpha\operatorname{softmax}(s/\tau)$. Then compute relation-weighted messages and the task loss. (3) Compute the motif score from the current minibatch graph; estimate the sum over $k$ by uniform neighbor sampling and multiply by the inverse sampling probability. Learn $\beta_a$, $\beta_4$, and $\tau$, but constrain $\tau\ge 0.05$ and initialize $\beta_4=0$. (4) First experiment: use a three-relation GNN on a small multilayer citation or knowledge-graph benchmark, comparing the same backbone with independent edge logits, a standard attention router, and this router. Match parameters, training steps, and sampled triples; report accuracy and wall-clock overhead. (5) Pre-register mechanism tests: as $\beta_4/\tau$ increases, measure empirical rainbow-triangle density and edge-color entropy. The proposed mechanism predicts a smooth increase at high temperature, followed by a sharp slope increase or symmetry-breaking transition; fit the maximum finite-difference slope and require it to exceed the independent-router control by at least two standard deviations. At $\beta_4=0$, refinement should have no effect beyond unary logits; verify that the mean absolute change in $p$ is below $10^{-4}$. At fixed $\beta_4$, doubling graph size should not double motif-logit magnitude because of the $1/n$ normalization; require the median magnitude ratio to remain between $0.8$ and $1.25$. Falsify the transfer if motif refinement gives no reproducible improvement over the independent router, produces no entropy or slope signature, or becomes unstable before the predicted transition.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Inconclusive

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

Stage 1 — Mechanism check agent confidence 7/10

Built and numerically verified the mean-field rainbow router with simplex-preserving updates, the beta4=0 unary reduction, rainbow-density response, and 1/n scaling behavior. With perturbed initialization, increasing beta4 raised rainbow density from 0.2171 to 0.2222 and entropy toward log(3), while strong coupling produced symmetry breaking and entropy collapse. The tiny predictive proxy did not show a downstream win: refined routing NLL was worse than the unary baseline, 1.0203 versus 0.8018, so the mechanism signal is real but its task benefit remains unproven.

Agent confidence: 7/10

Baseline: Unary independent router proxy test NLL: 0.801826. Extended normalized motif-score medians for n=8,16,32,48: 0.1731, 0.2020, 0.2164, 0.2212.
Idea: Mean-field router proxy test NLL: 1.020303. Perturbed sweep rainbow density rose from 0.2171 at beta4=0 to 0.2222 at moderate coupling; strong coupling with larger perturbation reached density 0.4998 and entropy 0.1553.

Limitations: This is a small NumPy toy experiment, not a relational GNN or citation/knowledge-graph benchmark. The perturbed mechanism sweep was run interactively and is not included in results.json. Learned beta parameters, neighbor sampling, GPU implementation, full-GNN wall-clock comparison, and statistical multi-seed task evaluation were not tested.

How to run: python3 rainbow_router_experiment.py

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

Ahead of the baseline (−20.0%) but not statistically significant (p=1, wins 1 / 8 paired seeds).

Benchmark: Relational_graph_classification
Model: local_relational_gnn
Paired seeds: 8
Baseline mean: 0.0039
Idea mean: 0.0031
Effect (Δ): -0.0008 (−20.0%; negative = idea better)
Wins: 1 / 8 paired seeds
p-value: 1 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Confirmed ✓
Practical effect: Inconclusive
Baseline tuning: swept over 3 configs

Limitations:

Used fixed eight-node relational graphs with a small 400/160 train/test split. Larger graphs, neighbor sampling, learned constrained beta/tau, citation or knowledge-graph data, and detailed wall-clock overhead were not tested.

How to run: python3 bench_rainbow.py

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

Stage 2 — Benchmark Sep 3, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented the mean-field rainbow router in an end-to-end shared relational GNN and evaluated it on eight paired seeds. Rainbow density increased as predicted, but the task-error improvement was not significant, so this is not a benchmark win.

Baseline: mean test error 0.00390625; best lr=0.006, tau=0.5
Delta mean: -0.00078125
Idea: mean test error 0.00312500; best lr=0.006, tau=0.5, beta4=3.0
Idea wins: 1
N pairs: 8
P value: 1

Benchmark result