# Finite-group relative message passing

- ID: 563
- Canonical URL: https://synthcore.org/idea/563/finite-group-relative-message-passing
- API JSON: https://synthcore.org/api/idea/563.json
- API Markdown: https://synthcore.org/api/idea/563.md
- Verification status: beats_baseline
- Source: [arXiv:2607.07920](https://arxiv.org/abs/2607.07920)
- Category: architecture
- Solves: accuracy, scalability, generalization
- ML areas: graph-nn, attention, embedding
- Math tags: graph-theory, algebra, linear-algebra, combinatorics
- Ratings: usefulness 6/10; difficulty 5/10; novelty 8/10

## Idea description

Use the quotient group's generator classes as a finite relation vocabulary and tie message functions by group displacement instead of by individual graph edges. This creates a compact, exactly consistent relation-aware GNN that can recognize repeated local structure and transfer parameters across graph instances sharing the same Cayley geometry.

## Mathematical statement

Let $A=\mathbb Z^k/L$ be the quotient constructed from signed cycle-class incidences, with vertex labels $z:V\to A$. Every edge in class $C_i$ has displacement $a_i=[\mathbf e_i]\in A$ or $-a_i$ according to orientation. The Cayley-host interpretation uses a fixed finite set of group generators, while the quotient ensures that the sum of displacements around every graph cycle vanishes: $\sum_{e\in\gamma}\sigma(e)=0$ in $A$. Consequently, a message rule indexed by displacement is globally consistent rather than dependent on an arbitrary path. Define a tied update $h_v^{\ell+1}=\psi_\ell(h_v^\ell,\sum_i\sum_{u:(u,v)\in C_i}\alpha_i^\ell(h_u^\ell,h_v^\ell)W_i^\ell h_u^\ell)$, where $W_i^\ell$ is shared by all edges with generator displacement $a_i$ and $\alpha_i^\ell$ is an optional attention gate. The number of relation parameters is controlled by the number of quotient generators rather than the number of edges. The cycle quotient provides the concrete consistency guarantee: compositions of edge relations agree whenever two paths have the same endpoints.

## Key formulas

- $$A=\mathbb Z^k/L,\qquad L=\left\langle\sum_{e\in\gamma}\sigma(e):\gamma\ \text{is a cycle}\right\rangle_{\mathbb Z},\qquad \sum_{e\in\gamma}\sigma(e)=0\ \text{in }A.$$
- $$a_i=[\mathbf e_i]\in A,\qquad z(v)-z(u)=\pm a_i\ \text{for every edge }(u,v)\in C_i.$$
- $$h_v^{\ell+1}=\psi_\ell\!\left(h_v^\ell,\sum_{i=1}^{k}\sum_{u:(u,v)\in C_i}\alpha_i^\ell(h_u^\ell,h_v^\ell)W_i^\ell h_u^\ell\right).$$

## Implementation notes

Modify a message-passing GNN's edge update rather than its node encoder. Precompute the $\varphi$-based partition and quotient labels. For each directed edge $(u,v)$, store its signed generator index $(i,s)$ and quotient displacement $g_{uv}=s a_i$. Replace an edge-specific MLP or unconstrained relation embedding with a shared bank of matrices $W_i$; optionally use separate matrices for positive and negative orientations. Each layer executes `msg = gate(h[u], h[v], embed(g_uv)) * (W[class_uv, sign_uv] @ h[u])`; aggregate messages by destination, then apply a residual update and normalization. In a transformer variant, use the displacement embedding as an additive attention bias while retaining parameter tying across all edges in the same class. Compute a spanning-tree cycle basis and the integer cycle matrix offline; Smith normal form is needed only during preprocessing, so training performs simple class and coordinate lookups. Record the compression ratio $|E|/k$, parameter count, throughput, and validation accuracy. The first cheap experiment should use 2-6 layer models on synthetic Cayley graphs and graph-isomorphism-style node labeling, followed by transfer between graph sizes. Compare GCN, GAT, and R-GCN with equal parameter budgets. Expected success is equal or better validation accuracy with fewer relation parameters, improved accuracy on larger held-out graphs, and faster inference. An ablation must compare exact cycle-quotient labels against raw local edge classes; removing cycle consistency should reduce transfer and expose whether the algebraic construction matters.

## Verification

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: helps
- Verdict: Built a self-contained finite-group relative message-passing MVP with Z_n x Z_m quotient labels, signed generator relations, exact cycle/displacement verification, and a source-to-larger-graph transfer test. The quotient consistency check passed, and the relation-tied model achieved MSE 0.00662 versus 2.83665 for GCN on 6x6 and 0.00547 versus 3.05603 on 8x8, showing a clear relation-awareness and transfer signal. This is promising but not a fair equal-parameter win: the tied model has 1,313 parameters versus 545 for GCN, and the synthetic target directly encodes the supplied relation classes.

### Mechanism check

- Verdict: Built a self-contained finite-group relative message-passing MVP with Z_n x Z_m quotient labels, signed generator relations, exact cycle/displacement verification, and a source-to-larger-graph transfer test. The quotient consistency check passed, and the relation-tied model achieved MSE 0.00662 versus 2.83665 for GCN on 6x6 and 0.00547 versus 3.05603 on 8x8, showing a clear relation-awareness and transfer signal. This is promising but not a fair equal-parameter win: the tied model has 1,313 parameters versus 545 for GCN, and the synthetic target directly encodes the supplied relation classes.
- Confidence: 7/10
- Limitations: Only a synthetic one-hop regression task was tested; no GAT/R-GCN, attention gates, raw-class ablation, equal-parameter comparison, timing, Smith normal form implementation, or real graph benchmark was included.

### 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/1389/bench_report.json)
- [experiment.py](https://synthcore.org/code/1389/experiment.py)
- [graph_track.py](https://synthcore.org/code/1389/graph_track.py)
- [report.md](https://synthcore.org/code/1389/report.md)
- [report_bench_2026-09-04T194616.md](https://synthcore.org/code/1389/report_bench_2026-09-04T194616.md)
- [results.json](https://synthcore.org/code/1389/results.json)
- [run_bench.py](https://synthcore.org/code/1389/run_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/1389)

## Disclaimer

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