✓✓ Beats tuned baseline 2026

Smith-normal-form Cayley positional encoding

Implementation & benchmark of arXiv:2607.07920 — Minimal Isometric Embeddings of Graphs into Cayley Graphs of Finite Abelian Groups

Usefulness7/10

Difficulty6/10

Novelty7/10

Architecture Accuracy Scalability Memory Graph nn Attention Embedding Graph theory Algebra Linear algebra Combinatorics

Source paper: Minimal Isometric Embeddings of Graphs into Cayley Graphs of Finite Abelian Groups arXiv:2607.07920 ⓘ · analyzed Aug 30, 2026

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

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.

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}.$$

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.

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

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

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

Stage 1 — Mechanism check agent confidence 7/10

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.

Agent confidence: 7/10

Baseline: Raw generator-class coordinate dimensions: C5 5, C6 3, Torus3 1, Petersen 5.
Idea: Quotient coordinate dimensions: C5 4 (1.25x raw/quotient), C6 3 (1.0x), Torus3 1 (1.0x), Petersen 4 (1.25x); path_failures=0 and edge_failures=0 for every graph.

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.

How to run: python3 experiment.py

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

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

Benchmark: Cayley_cycle_distance
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 0.0575
Idea mean: 0.0005
Effect (Δ): -0.057 (−99.2%; negative = idea better)
Wins: 8 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±17.5%
Mechanism: Confirmed ✓
Practical effect: Helps
Baseline tuning: swept over 3 configs

Limitations:

Tested one synthetic cyclic Cayley graph with a fixed 32-node cycle, one shared tiny MLP architecture, and distance regression only. It did not test general graphs, approximate edge partitions, explicit SNF computation beyond the cyclic quotient, graph transformers/attention, larger-scale memory or speed, or comparisons with Laplacian/random-walk encodings.

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

Agent confidence: 9/10

Built a custom cyclic Cayley-graph benchmark because no built-in track contained graph positional-encoding structure. The exact Z_32 quotient check passed with zero cycle-sum and edge-increment errors, and the trained relative-coordinate system achieved substantially lower test MSE than the matched endpoint-coordinate baseline: 0.000477 versus 0.057501, with all 8 paired seeds winning and permutation p=0.0081. The trained-model translation signature confirmed the predicted invariance: idea output change 0.0 versus baseline 0.2194.

Baseline: test MSE mean 0.0575008038431406, std 0.011260127917232875, best lr=0.01
Idea: test MSE mean 0.0004770873465531622, std 0.0002546983835343552, best lr=0.01; paired delta=-0.05702371649658744; p=0.0081; 8/8 wins

Benchmark result