Group-Lifted Message Passing
Implementation & benchmark of arXiv:2607.28621 — Lifting Lifted Product Codes
Source paper: Lifting Lifted Product Codes arXiv:2607.28621 ⓘ · analyzed Aug 31, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Turn a small base message-passing graph into a family of larger graphs by replicating every base node across a finite fiber and wiring replicas with permutations derived from a group extension. Use one shared local neural update on every lifted copy, so parameter count stays that of the base graph while the lifted graph supplies additional global paths and larger effective receptive fields.
Formulas
Mathematical statement
The construction starts from the short exact sequence $1\longrightarrow K\xlongrightarrow{\chi}H\xlongrightarrow{\pi}G\longrightarrow 1$, where $K$ is the finite fiber group, $H$ is the extension group, $G$ is the base labeling group, $\chi$ is injective, and $\pi$ is surjective. A section $\sigma:G\to H$ satisfies $(\pi\circ\sigma)(g)=g$ for every $g\in G$, but need not be a homomorphism. For a base graph with edge labels $g_e\in G$, represent each lifted node as $(v,k)$ with $k\in K$. Each base edge receives a bijection $\rho_e:K\to K$; in the regular cyclic case, $\rho_e(k)=k\,\kappa_e$. The lifted edge set is $((u,k),(v,\rho_e(k)))$ for every base edge $e=(u,v)$ and every $k\in K$. This is a $|K|$-sheeted cover: each base vertex has $|K|$ preimages and the local degree is preserved. The neural update uses shared parameters across fibers: $h'_{v,k}=\phi(h_{v,k},\sum_{e:u\to v}M_{g_e}(h_{u,\rho_e^{-1}(k)}))$. The transferable asset is controlled global rewiring with unchanged local incidence and parameter sharing.
Implementation notes
1. Integration point: implement this as a replacement for the adjacency and message-routing stage of a sparse GNN, graph Transformer, or local attention block. Start with a base graph containing $n$ nodes and labeled directed edges $(u,v,g_e)$; choose a finite fiber $K=\{0,\ldots,t-1\}$ and create $nt$ lifted hidden states. Do not duplicate trainable weights per fiber. 2. Pseudocode: initialize H_lift[v,k] = H_base[v] + fiber_embedding[k]; for each layer set M=0; for every base edge (u,v,g,perm), where perm[k] is the precomputed permutation $\rho_e(k)$, accumulate M[v,perm[k]] += message_g(H_lift[u,k]); update H_lift = phi(H_lift, M) using the displayed formula; pool with out[v] = mean_k(H_lift[v,k]) or retain fibers for prediction. 3. Mathematics versus estimation: the exact objects are the extension maps $\chi,\pi$, section $\sigma$, and edge permutations. For an MVP, use cyclic $K=\mathbb{Z}_t$ and set $\rho_e(k)=(k+\kappa_e)\bmod t$; later generate $\kappa_e$ from a nonabelian finite group or section defects $\sigma(g_1)\sigma(g_2)\sigma(g_1g_2)^{-1}$. Verify every edge map is bijective and every lifted node preserves base degree. 4. First experiment: train a 6-layer GNN on synthetic graphs whose labels depend on long-cycle parity or distant node pairs. Compare the base graph, random $t$-replication with equal degree, and group lifts with $t\in\{2,4,8\}$. Measure accuracy, shortest-path statistics, wall-clock time, memory, and loss at equal FLOPs. Success is higher accuracy or faster convergence at equal parameters; reject it if lifting only increases runtime without beating random rewiring.
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.