Unverified 2026

Compact Abelian Graph Positional Codes

Implementation & benchmark of arXiv:2607.07939 — Dimension and Order Bounds for Isometric Embeddings of Graphs into Abelian Cayley Graphs, and the Abelian Dividend

Usefulness5/10

Difficulty7/10

Novelty7/10

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

Source paper: Dimension and Order Bounds for Isometric Embeddings of Graphs into Abelian Cayley Graphs, and the Abelian Dividend arXiv:2607.07939 ⓘ · analyzed Aug 30, 2026

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

Idea description

Replace one-hot node IDs or large positional encodings in a GNN with coordinates from a compact abelian Cayley graph. The coordinates preserve graph-shortest-path geometry exactly, while Fourier characters of cyclic factors provide smooth neural features with fewer channels.

Formulas

$$k_{\min}(G)=\min\{k:\ G\hookrightarrow\mathrm{Cay}(\mathbb{Z}_{2}^{k},S)\ \text{isometrically for some }S\}$$

$$\nu(G)=\min|\Gamma|\quad\text{over all isometric embeddings into abelian Cayley graphs}$$

$$k_{\min}(G)\geq\max\bigl(\mathrm{diam}(G),\lceil\log_{2}n\rceil\bigr),\qquad \nu(G)\geq\max\bigl(n,2\,\mathrm{diam}(G)\bigr)$$

$$p_{v,j,q}=\cos\!\left(\frac{2\pi q\,\phi_j(v)}{m_j}\right),\qquad s_{v,j,q}=\sin\!\left(\frac{2\pi q\,\phi_j(v)}{m_j}\right),\quad \phi(v)=(\phi_1(v),\ldots,\phi_r(v))\in\prod_{j=1}^r\mathbb{Z}_{m_j}$$

Mathematical statement

The paper defines $k_{\min}(G)=\min\{k:G\hookrightarrow\mathrm{Cay}(\mathbb{Z}_2^k,S)\text{ isometrically for some }S\}$, where $G$ is a finite connected graph, $S$ is a generating set, and an isometric embedding preserves every pairwise graph distance. For general finite abelian hosts it defines $\nu(G)=\min|\Gamma|$, minimizing the group order over isometric embeddings into abelian Cayley graphs. The necessary bounds are $k_{\min}(G)\geq\max(\mathrm{diam}(G),\lceil\log_2 n\rceil)$ and $\nu(G)\geq\max(n,2\,\mathrm{diam}(G))$, where $n=|V(G)|$ and $\mathrm{diam}(G)$ is the graph diameter. Given a found embedding $\phi:V(G)\to\Gamma=\prod_{j=1}^r\mathbb{Z}_{m_j}$, use cyclic characters $p_{v,j,q}=\cos(2\pi q\phi_j(v)/m_j)$ and $s_{v,j,q}=\sin(2\pi q\phi_j(v)/m_j)$. The group coordinates preserve the Cayley metric, while these character features avoid treating modular integers as ordinary Euclidean scalars.

Implementation notes

Integrate the representation at the input of a message-passing GNN or graph Transformer, before the first node projection. For each training graph $G=(V,E)$, search for an injective map $\phi:V\to\Gamma$, with $\Gamma=\prod_j\mathbb{Z}_{m_j}$, and a generator set $S\subseteq\Gamma$ such that graph distances equal distances in the corresponding Cayley graph. For an MVP, restrict candidate factors to $m_j\in\{2,3,4,5,6,8\}$, enumerate assignments for graphs with at most 12 or 20 nodes, and verify every candidate using Floyd-Warshall distances $d_G(u,v)$ and Cayley distances $d_\Gamma(\phi(u),\phi(v))$. Minimize host order $|\Gamma|=\prod_jm_j$, subject to the necessary constraint $|\Gamma|\geq\max(n,2\,\mathrm{diam}(G))$. If exhaustive search is too expensive, use simulated annealing with objective $\sum_{u<v}|d_G(u,v)-d_\Gamma(\phi(u),\phi(v))|$, plus collision and host-size penalties, and retain only zero-error solutions. Convert each coordinate into one or two low-frequency Fourier pairs using the displayed sine/cosine equations, concatenate them with node attributes, and use the normal node encoder. Compare raw modular coordinates, Fourier features, one-hot IDs, Laplacian eigenvectors, and random-walk positional encodings. The first cheap experiment should use MUTAG, ENZYMES, or synthetic graphs up to 12 nodes with a 3-layer GIN. Record accuracy, parameter count, positional-feature memory, and robustness to node relabeling and unseen graph sizes. Success means matching or exceeding Laplacian-PE accuracy with fewer positional channels or lower memory, while preserving performance under arbitrary node permutations.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.