Holonomy-Fixed State Filter
Implementation & benchmark of arXiv:2607.16037 — Contextual Fraction on Permutation Gain Graphs: Exact Algorithms, Query Lower Bounds, and Dynamic Maintenance
Source paper: Contextual Fraction on Permutation Gain Graphs: Exact Algorithms, Query Lower Bounds, and Dynamic Maintenance arXiv:2607.16037 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Add a preprocessing and inference module to a permutation-labeled graph network that computes the states globally compatible with all cycle transports. The module masks node or root-state logits to this fixed-point set, replacing exponential global assignment search with graph traversal plus permutation-table operations. A soft version can use the fixed-point mass as an auxiliary compatibility regularizer during training.
Formulas
Mathematical statement
Let G=(V,E) be a connected graph, let O be a finite state set, and let each oriented edge e=(u,v) carry a permutation g_e:O o O, with g_(v,u)=g_e^{-1}. Choose a root r and a spanning tree, and let T_v:O o O be the permutation obtained by transporting from r to v along the tree. For every non-tree edge e=(u,v), define its root-based holonomy permutation by h_e=T_v^{-1}\circ g_e\circ T_u. Let H=\langle h_e:e
otin E(T)\rangle\leq\operatorname{Sym}(O) be the subgroup generated by the fundamental-cycle holonomies. The globally compatible root states are the common fixed points F=\operatorname{Fix}(H)=\{o\in O:h(o)=o\ \forall h\in H\}; it is sufficient to test the generators h_e rather than enumerate every element of H. For an H-invariant root distribution p, the paper gives \operatorname{NCF}(e)=p(F) and \operatorname{CF}(e)=1-p(F). The engineering opportunity is to use the exact binary mask 1_F as a constraint on neural state distributions, and p(F)=\sum_{o\in F}p_o as a differentiable compatibility score.
Implementation notes
1. Integration point: use this module before a graph neural network's state decoder or immediately after its root-state logits. Inputs are a connected graph edge list, a permutation table g_e of shape [|O|] for every oriented edge, and root logits z of shape [batch, |O|]. The module can also provide a graph-level compatibility feature to the message-passing network. 2. Pseudocode: choose root r and build a spanning tree with DFS or BFS; set T_r to the identity permutation and propagate T_v=g_(u,v) composed with T_u along tree edges; initialize mask[o]=True; for every chord e=(u,v), compute h=T_v^{-1} composed with g_e composed with T_u, then set mask[o] = mask[o] and (h[o]==o); let F={o:mask[o]}; compute p=softmax(z), compatibility=sum(p[o] for o in F), and either train with L=L_task+lambda*(-log(compatibility+epsilon)) or set masked_logits[o]=-infinity for o not in F at inference. If F is empty, skip hard masking and return compatibility zero, or use a learned unconstrained fallback. 3. Computed exactly from the paper: tree transports, chord holonomies, F, and p(F). Estimated empirically: lambda, epsilon, and whether hard filtering or the soft loss is preferable; no subgroup enumeration is needed because generators suffice. Cache T_v and the mask when the graph is static. For a dynamic graph, recompute only the affected chord holonomy and rescan O(|O|) states. 4. First experiment: use a synthetic graph task with |O| in {8,16,32}, random permutation edge labels, and targets generated from a planted compatible root state. Compare a standard message-passing decoder, hard fixed-point masking, and the soft compatibility loss at equal parameter count. Measure exact assignment accuracy, invalid-edge rate, calibration, and preprocessing latency. The expected signal is lower invalid-assignment rate and faster convergence; on graphs with many inconsistent cycles, the hard mask should reduce decoder search from |O| candidates to |F| and provide near-zero compatibility violations whenever F is nonempty.
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.