# Local separating-code positional encodings

- ID: 1799
- Canonical URL: https://synthcore.org/idea/1799/local-separating-code-positional-encodings
- API JSON: https://synthcore.org/api/idea/1799.json
- API Markdown: https://synthcore.org/api/idea/1799.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.04608](https://arxiv.org/abs/2608.04608)
- Category: architecture
- Solves: accuracy, sample-efficiency, scalability
- ML areas: graph-nn, embedding, attention
- Math tags: combinatorics, graph-theory, information-theory
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

## Idea description

Replace globally unique node IDs with a small discrete alphabet labeling whose ordered local neighborhood words uniquely identify nodes. Feed these separating words to a GNN or graph transformer as positional features, preserving node distinguishability with bounded local receptive fields.

## Mathematical statement

Let G be a finite group, let [q] be an alphabet of q symbols, let f:G    o[q] be a labeling, and let Y=(y_1,\ldots,y_k) be an ordered pattern of distinct group elements. The translated observation is W_{f,Y}(g)=(f(gy_1),\ldots,f(gy_k)). The pair (f,Y) is separating when W_{f,Y}(g)
e W_{f,Y}(h) for every distinct g,h\in G. The connected parameter restricts Y to a connected Cayley-graph window containing the identity and generators. For a general graph, replace group offsets gy_i by deterministic ordered walk endpoints or canonical neighbor slots. The transferable property is injectivity of a finite local code, which gives an explicit collision criterion for positional representations.

## Key formulas

- $$W_{f,Y}(g)=\bigl(f(gy_{1}),\ldots,f(gy_{k})\bigr).$$
- $$(f,Y)\text{ is separating}\quad\Longleftrightarrow\quad W_{f,Y}(g)\neq W_{f,Y}(h)\ \text{for all }g\neq h.$$$$
- $$\mathcal{L}_{\mathrm{sep}}(f,Y)=\sum_{(u,v)\in\mathcal{P}}\exp\!\left(-\frac{\|\phi(W_{f,Y}(u))-\phi(W_{f,Y}(v))\|_2^2}{\tau}\right),$$
- $$\operatorname{csep}_{q}(G,S)=\min\{|Y|:\ Y\text{ is a connected Cayley window containing }\{1\}\cup S\text{ and }(f,Y)\text{ is separating for some }f:G\to[q]\}.$$

## Implementation notes

Integrate this at the input of a message-passing GNN or graph transformer as a local positional-code module. Choose an ordered connected window Y=(y_1,...,y_k), with y_1 equal to the center node and the remaining offsets defined by graph distances, generator directions, or fixed canonical neighbor slots. Maintain label logits A[v,i,c] for the symbol at local position i of node v, where c is one of q symbols. During training, convert logits to soft labels with Gumbel-Softmax; during evaluation, use argmax labels. For each node v, gather the ordered code C_v=[one_hot(f(v\cdot y_1)),...,one_hot(f(v\cdot y_k))], flatten it, and map it through a small MLP before adding it to the node embedding or concatenating it to transformer query and key inputs. Sample node pairs (u,v), compute d_uv=||C_u-C_v||_2^2, and optimize the collision surrogate L_sep=sum exp(-d_uv/tau), where P is the sampled pair set and tau is annealed from a high to low temperature. Add a hard collision metric by hashing the discrete code words and reporting the fraction of duplicate hashes. The paper’s exact mathematical target is injectivity of v\mapsto W(v); the soft exponential loss and Gumbel relaxation are engineering adaptations. Test first on 2D grid graphs, cycles, and small Cayley-like graphs, comparing no positional encoding, random IDs, Laplacian eigenvectors, and separating codes. Measure node-classification accuracy, graph isomorphism discrimination, collision rate, and the number of GNN layers required to reach baseline accuracy. Success is higher accuracy at fixed depth or zero code collisions with q^k much smaller than the number of nodes.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: Built and ran a cyclic-Cayley local separating-code verifier plus a tiny downstream linear readout. The mechanism manifested: random collision pair probability followed q^-k, expected collision counts followed n(n-1)/(2q^k), and optimized codes became separating at k=ceil(log_q n) in all tested settings while remaining impossible below the code-capacity bound. The positional code improved the toy held-out readout over a constant baseline, but this is not evidence of broad GNN accuracy or cross-graph generalization.

### Mechanism check

- Verdict: Built and ran a cyclic-Cayley local separating-code verifier plus a tiny downstream linear readout. The mechanism manifested: random collision pair probability followed q^-k, expected collision counts followed n(n-1)/(2q^k), and optimized codes became separating at k=ceil(log_q n) in all tested settings while remaining impossible below the code-capacity bound. The positional code improved the toy held-out readout over a constant baseline, but this is not evidence of broad GNN accuracy or cross-graph generalization.
- Confidence: 8/10
- Limitations: Tested only cyclic graphs with overlapping windows and a small synthetic readout, not 2D grids, general graphs, trained message-passing GNNs, Gumbel-softmax optimization, Laplacian/random-ID baselines, runtime/FLOPs, or cross-graph transfer.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.8074
- Paired wins: 5/8
- Benchmark verdict: no measurable effect

## Artifacts

- [bench_local_codes.py](https://synthcore.org/code/672/bench_local_codes.py)
- [bench_report.json](https://synthcore.org/code/672/bench_report.json)
- [report.md](https://synthcore.org/code/672/report.md)
- [report_bench_2026-08-31T213136.md](https://synthcore.org/code/672/report_bench_2026-08-31T213136.md)
- [results.json](https://synthcore.org/code/672/results.json)
- [toy_classifier.py](https://synthcore.org/code/672/toy_classifier.py)
- [verify_local_codes.py](https://synthcore.org/code/672/verify_local_codes.py)
- [Download all files as ZIP](https://synthcore.org/download/672)

## Disclaimer

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