# Smith-normal-form Cayley positional encoding

- ID: 562
- Canonical URL: https://synthcore.org/idea/562/smith-normal-form-cayley-positional-encoding
- API JSON: https://synthcore.org/api/idea/562.json
- API Markdown: https://synthcore.org/api/idea/562.md
- Verification status: beats_baseline
- Source: [arXiv:2607.07920](https://arxiv.org/abs/2607.07920)
- Category: architecture
- Solves: accuracy, scalability, memory
- ML areas: graph-nn, attention, embedding
- Math tags: graph-theory, algebra, linear-algebra, combinatorics
- Ratings: usefulness 7/10; difficulty 6/10; novelty 7/10

## Idea description

Replace heuristic graph positional encodings with exact finite-abelian-group coordinates derived from edge-class increments and cycle constraints. Relative positions become group differences, allowing a graph transformer to share parameters across repeated generator displacements while retaining exact path consistency and compact cyclic coordinates.

## Mathematical statement

The paper defines the metric-parallel edge relation $e=\{u,v\}\;\varphi\;f=\{x,y\}$ by $d(u,x)=d(v,y)$ and $d(u,y)=d(v,x)$, where $d$ is graph shortest-path distance. Use connected components of this relation, or a cheaper candidate partition, as generator classes $C_1,\ldots,C_k$. Orient each edge $e=(u,v)$ and define its class increment as the standard basis vector $\sigma(e)=s_i\mathbf e_i\in\mathbb Z^k$ when $e\in C_i$, with $s_i\in\{+1,-1\}$ determined by orientation. For every directed cycle $\gamma$, form the signed cycle-class incidence vector $c_\gamma=\sum_{e\in\gamma}\sigma(e)\in\mathbb Z^k$. Let $L=\operatorname{span}_{\mathbb Z}\{c_\gamma\}$ be the cycle lattice. The universal vertex label is the path integral $z(v)=\sum_{e\in P_{r\to v}}\sigma(e)\pmod L$, which is path-independent because differences of two paths are cycles. The finite group is $A=\mathbb Z^k/L$; Smith normal form $ULV=D=\operatorname{diag}(q_1,\ldots,q_r,0,\ldots,0)$ exposes cyclic factors $\mathbb Z_{q_1}\times\cdots\times\mathbb Z_{q_r}$ and any free factors. In the binary special case, reduce the same quotient modulo two. For an isometric labeling, the paper's Join Lemmas assert that the finest consistent partition supplies labels preserving graph distances in the corresponding Cayley host; in an ML adaptation, this claim should be tested rather than assumed for arbitrary approximate partitions.

## Key formulas

- $$e\;\varphi\;f\quad\Longleftrightarrow\quad d(u,x)=d(v,y)\ \text{and}\ d(u,y)=d(v,x),\qquad e=\{u,v\},\ f=\{x,y\}.$$
- $$c_\gamma=\sum_{e\in\gamma}\sigma(e)\in\mathbb Z^k,\qquad L=\left\langle c_\gamma:\gamma\ \text{is a directed cycle}\right\rangle_{\mathbb Z},\qquad A=\mathbb Z^k/L.$$
- $$z(v)=\sum_{e\in P_{r\to v}}\sigma(e)\pmod L,\qquad z(v)-z(u)=\sigma(u,v)\pmod L.$$
- $$ULV=D=\operatorname{diag}(q_1,\ldots,q_r,0,\ldots,0),\qquad A\cong\mathbb Z_{q_1}\times\cdots\times\mathbb Z_{q_r}\times\mathbb Z^{k-r}.$$

## Implementation notes

Integrate this at graph preprocessing and at the relative-position input of a graph transformer. For each training graph, choose a root vertex, compute all-pairs shortest paths or bounded BFS distances, and mark candidate edge pairs satisfying the paper's $\varphi$ test. Build edge classes $C_i$ from connected components of this relation; for large graphs, replace all-pairs testing by sampled edge pairs or local distance signatures. Orient every edge once and assign $\sigma(e)=+\mathbf e_i$ when it follows the class orientation and $-\mathbf e_i$ otherwise. Construct a cycle basis with a spanning tree: each non-tree edge plus the tree path to its endpoints gives one fundamental cycle. Stack the corresponding integer vectors $c_\gamma$ as columns of an integer matrix $B$, compute its Smith normal form, and map each $z(v)$ into the finite cyclic coordinates of $A$. Verify path independence by checking that every fundamental-cycle vector is zero in the quotient. At every attention layer, compute $g_{uv}=z(v)-z(u)$, embed each cyclic coordinate with learned sine/cosine features or a lookup table, and add an MLP output $b(g_{uv})$ to the attention logit. Pseudocode: `classes <- phi_components(edges); basis <- fundamental_cycles(G); B[:,j] <- sum(sign(e)*onehot(class(e)) for e in basis[j]); SNF(B)->(U,D,V); z[root]=0; BFS assign z[v]=z[u]+sigma(u,v) mod D; attention_logit(u,v)+=MLP(embed(z[v]-z[u]))`. The exact math supplies the cycle quotient and SNF; class coarsening and feature encoding are empirical choices. First test on synthetic cycles, grids, Petersen graphs, and random Cayley graphs with a small graph transformer on node classification or shortest-path prediction. Compare Laplacian eigenvectors, random-walk encodings, and shortest-path bias at equal positional dimension. Success means higher accuracy, better extrapolation to larger graphs, fewer positional dimensions, and zero path-inconsistency.

## Verification

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: helps
- Verdict: Built an exact small-graph MVP for metric-parallel edge classes, fundamental cycle-class lattices, SNF invariants, and path/edge consistency certification. On C5, C6, 3x3 torus, and Petersen graphs, all tested fundamental cycles and edge increments passed with zero failures; nontrivial torsion factors included 2 for C6, 3 for the torus, and four 2-factors for Petersen. This verifies the core quotient/path-consistency phenomenon and shows modest coordinate compression on C5 and Petersen, but no neural-network accuracy or speed win was tested.

### Mechanism check

- Verdict: Built an exact small-graph MVP for metric-parallel edge classes, fundamental cycle-class lattices, SNF invariants, and path/edge consistency certification. On C5, C6, 3x3 torus, and Petersen graphs, all tested fundamental cycles and edge increments passed with zero failures; nontrivial torsion factors included 2 for C6, 3 for the torus, and four 2-factors for Petersen. This verifies the core quotient/path-consistency phenomenon and shows modest coordinate compression on C5 and Petersen, but no neural-network accuracy or speed win was tested.
- Confidence: 7/10
- Limitations: No graph-transformer training, task accuracy, extrapolation, runtime, memory, Laplacian/random-walk baseline, or large-graph scalability evaluation was performed. The exact checks use tiny synthetic graphs and validate the constructed fundamental-cycle certificate; they do not establish distance preservation for arbitrary approximate partitions.

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

- [README.md](https://synthcore.org/code/256/README.md)
- [bench_report.json](https://synthcore.org/code/256/bench_report.json)
- [cayley_graph_track.py](https://synthcore.org/code/256/cayley_graph_track.py)
- [cayley_posenc.py](https://synthcore.org/code/256/cayley_posenc.py)
- [experiment.py](https://synthcore.org/code/256/experiment.py)
- [report.md](https://synthcore.org/code/256/report.md)
- [report_bench_2026-09-02T161118.md](https://synthcore.org/code/256/report_bench_2026-09-02T161118.md)
- [results.json](https://synthcore.org/code/256/results.json)
- [stage2_bench.py](https://synthcore.org/code/256/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/256)

## Disclaimer

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