✓✓ Beats tuned baseline 2026

Backward-Equivalent Quotient GNN

Implementation & benchmark of arXiv:2607.18776 — Aggregation of Evolutionary Game Dynamics on Large-Scale Weighted Networks

Usefulness8/10

Difficulty5/10

Novelty6/10

Architecture Speedup Stability Graph nn Training dynamics Inference speedup Graph theory Linear algebra Dynamical systems Control theory

Source paper: Aggregation of Evolutionary Game Dynamics on Large-Scale Weighted Networks arXiv:2607.18776 ⓘ · analyzed Aug 30, 2026

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

Idea description

Partition graph nodes into backward-equivalent classes and run message passing on the K-node quotient graph instead of the original N-node graph. If every node in a class receives the same aggregate message from every source class and shares the same local update map, class-constant node representations remain class-constant at every layer, making the quotient computation exactly equivalent to the full GNN on that invariant subspace.

Formulas

$$\sum_{j\in H_b}a_{ij}=\sum_{j\in H_b}a_{i'j}=:\bar a_{ab},\qquad i,i'\in H_a,$$

$$AP=P\bar A,\qquad P_{ia}=\mathbf{1}[i\in H_a],\qquad \bar A_{ab}=\sum_{j\in H_b}a_{ij},$$

$$z_a^{\ell+1}=f_a\!\left(z_a^\ell,\sum_{b=1}^{K}\bar a_{ab}\,\phi_b(z_b^\ell)\right),\qquad h^\ell=Pz^\ell,$$

$$e_{\ell+1}\le L\left(e_\ell+\|R\|\,\|z^\ell\|\right),\qquad R_{iab}=\sum_{j\in H_b}a_{ij}-\bar a_{ab},$$

Mathematical statement

Let V be the N-node graph, partitioned into classes H_1,...,H_K, and let A=(a_{ij}) be a weighted adjacency matrix. The partition is equitable if, for every source class H_b and every i,i' in target class H_a, $\sum_{j\in H_b}a_{ij}=\sum_{j\in H_b}a_{i'j}=:\bar a_{ab}$. Let the node update be $h_i^{\ell+1}=f_a(h_i^\ell,\sum_j a_{ij}\phi_b(h_j^\ell))$ for i in H_a, with shared functions within each class. If $h_i^0=z_a^0$ for all i in H_a, induction gives $h_i^\ell=z_a^\ell$ and the exact quotient dynamics $z_a^{\ell+1}=f_a(z_a^\ell,\sum_b\bar a_{ab}\phi_b(z_b^\ell))$. The lifting operator $P\in\{0,1\}^{N\times K}$, with $P_{ia}=1$ iff i\in H_a, satisfies $AP=P\bar A$, where $\bar A=(\bar a_{ab})$. For an approximately equitable partition, define residual $R_{iab}=\sum_{j\in H_b}a_{ij}-\bar a_{ab}$; if the update has Lipschitz constant L, the representation mismatch is bounded recursively by $e_{\ell+1}\le L(e_\ell+\|R\|\|z^\ell\|)$, so approximation error is predicted to grow according to the quotient dynamics' gain.

Implementation notes

Use this as a graph encoder for graphs with repeated motifs, duplicated agents, or large populations. First compute a partition by color refinement: initialize each node color from its input-feature type and degree, then repeatedly replace its color by a tuple containing its current color and sorted or hashed weighted neighbor-color histograms. Stop when colors stabilize; these colors define candidate classes H_a. Verify exactness by checking that every node in H_a has identical total edge weight into every H_b. Construct P and the K-by-K quotient matrix $\bar A$. Replace the full layer $h_{\mathrm{next}}=\sigma(W_{\mathrm{self}}h+A\phi(h)W_{\mathrm{msg}})$ with $z_{\mathrm{next},a}=\sigma(W_{\mathrm{self},a}z_a+\sum_b\bar A_{ab}\phi(z_b)W_{\mathrm{msg},ab})$, then recover node outputs with $h=Pz$. Pseudocode: colors=refine(A,features); classes=groups(colors); residual=max_class_weight_variation(A,classes); barA=class_weight_sums(A,classes); for layer in layers: z=layer(z,barA); h=P@z. The paper supplies the exact invariance condition and quotient construction; the implementation estimates classes, numerical tolerances, and each layer's empirical Lipschitz gain. The first cheap experiment should use stochastic-block graphs with N=10,000 nodes and K=20 planted classes, class-constant initial features, and a node-label or graph-diffusion prediction task. Compare a full GNN against the quotient GNN. The quantitative prediction is that exact equitable partitions produce discrepancy below $10^{-6}$ at every layer, up to floating-point error. Perturb edge weights to obtain residual norm $\|R\|$; at fixed depth, the quotient-to-full representation error should scale approximately linearly with $\|R\|$, while runtime should scale with K rather than N and approach an N/K speedup when the quotient is dense.

Verification

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

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

How to read this: The implementation beat the baseline, but the claimed mechanism did not reproduce at benchmark scale. The gain may come from another effect; treat the cause as unresolved.

Stage 1 — Mechanism check agent confidence 9/10

Built a NumPy quotient-GNN MVP with color refinement, equitable-partition verification, quotient construction, exact lifting, approximate residual perturbations, and timing. Exact partitions satisfied AP=PĀ to 2.8e-16 and full-vs-quotient discrepancies stayed below 1.5e-15 across 10 layers. Approximation error scaled linearly with residual (R²=0.9973), while depth propagation remained stable and decreased for the chosen contractive layer; quotient inference was about 99.4x faster than the dense full graph.

Agent confidence: 9/10

Baseline: Dense full GNN: 0.01332 s for 5 layers at N=2400
Idea: Quotient GNN: 0.000134 s for 5 layers at K=20; speedup 99.37x. Exact max discrepancy 1.44e-15; residual-error linear fit slope 0.03926, R² 0.99726; depth-12/depth-1 error ratio 0.0308.

Limitations: This is a deterministic NumPy toy experiment with dense matrices and linear message passing, not a trained task or sparse production implementation. Color refinement was tested on the constructed graph but the planted partition was used for the theorem checks; GPU execution, memory scaling beyond N=2400, nonlinear learned updates, and graph classification accuracy were not tested.

How to run: python3 quotient_gnn_experiment.py

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

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

Benchmark: Custom:csbm_radius_graph
Model: FullGraphNet vs QuotientGraphNet
Paired seeds: 8
Baseline mean: 0.1184
Idea mean: 0.1016
Effect (Δ): -0.0169 (−14.2%; negative = idea better)
Wins: 8 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Not confirmed ✗
Practical effect: Helps
Baseline tuning: swept over 3 configs

Limitations:

The benchmark uses a small fixed 21-node graph motif rather than large sparse graphs, so inference speed and N/K scaling were not measured. The quotient and full systems were trained separately, and the model-derived equivalence signature failed; a stricter shared-parameter/lifted-state implementation is needed to isolate exact invariant-subspace equivalence. Only the existing CSBM graph classification track was tested, not graph regression or large-population deployment.

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

Agent confidence: 8/10

Built a graph-structured quotient GNN benchmark using the canonical bench training loop, with identical datasets, optimizer, epochs, hidden width, and a shared learning-rate union for baseline and idea sweeps. The quotient model achieved lower test cross-entropy than the tuned full-graph baseline on all 8 paired seeds: mean 0.10156 versus 0.11844, delta -0.016875, permutation p=0.0081, so the bench verdict is idea better (significant). The mechanism signature was not confirmed because separately trained systems produced a 4.58 maximum logit difference on class-constant probes; this does not invalidate the observed task-metric win but limits the invariance claim in this implementation.

Baseline: FullGraphNet, best lr=0.003: test cross-entropy mean 0.1184375, std 0.0190369, 8 seeds
Idea: QuotientGraphNet, best lr=0.01: test cross-entropy mean 0.1015625, std 0.0151006, 8 seeds
Mechanism signature confirmed: false
Paired delta: -0.0168750 (idea minus baseline), all 8 paired wins
Permutation p value: 0.0081
Relative improvement percent: 14.24

Benchmark result