# Compact Abelian Graph Positional Codes

- ID: 564
- Canonical URL: https://synthcore.org/idea/564/compact-abelian-graph-positional-codes
- API JSON: https://synthcore.org/api/idea/564.json
- API Markdown: https://synthcore.org/api/idea/564.md
- Verification status: unverified
- Source: [arXiv:2607.07939](https://arxiv.org/abs/2607.07939)
- Category: architecture
- Solves: memory, accuracy, scalability
- ML areas: graph-nn, embedding, retrieval
- Math tags: graph-theory, combinatorics, algebra, linear-algebra
- Ratings: usefulness 5/10; difficulty 7/10; novelty 7/10

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

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

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

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

## Disclaimer

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