# Backward-Equivalent Quotient GNN

- ID: 1121
- Canonical URL: https://synthcore.org/idea/1121/backward-equivalent-quotient-gnn
- API JSON: https://synthcore.org/api/idea/1121.json
- API Markdown: https://synthcore.org/api/idea/1121.md
- Verification status: beats_baseline
- Source: [arXiv:2607.18776](https://arxiv.org/abs/2607.18776)
- Category: architecture
- Solves: speedup, stability
- ML areas: graph-nn, training-dynamics, inference-speedup
- Math tags: graph-theory, linear-algebra, dynamical-systems, control-theory
- Ratings: usefulness 8/10; difficulty 5/10; novelty 6/10

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

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

## Key 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},$$

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

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

### Mechanism check

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

### 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/216/bench_report.json)
- [quotient_gnn_experiment.py](https://synthcore.org/code/216/quotient_gnn_experiment.py)
- [report.md](https://synthcore.org/code/216/report.md)
- [report_bench_2026-08-30T205250.md](https://synthcore.org/code/216/report_bench_2026-08-30T205250.md)
- [results.json](https://synthcore.org/code/216/results.json)
- [stage2_bench.py](https://synthcore.org/code/216/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/216)

## Disclaimer

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