Holonomy-Aware Graph Reduction for Belief Propagation over Non-Abelian Groups

Belief propagation is an inference method that passes local messages along the edges of a graph to estimate each variable's marginal distribution. It is exact on trees and often fails on dense, loopy graphs. Two classical results show that simplifying the graph can repair it. Watanabe proved that repeatedly stripping leaves, degree-2 pass-through vertices and bridges ("w-reduction") reduces the question of whether belief propagation has a unique answer to a small irreducible core, characterized through the Ihara zeta function of the graph (Uniqueness of Belief Propagation on Signed Graphs). Leisenberger, Pernkopf and Knoll showed that deleting the weakest-coupled edges first (BETHE-OPT) repairs the energy landscape that belief propagation implicitly minimizes, with an error bound equal to the deleted coupling $|J_{ij}|$ (Fixing the Bethe approximation). Both results are proven only for binary ±1 spins, where an edge carries a single number and a cycle is "frustrated" or not according to the sign of a product.

We propose to extend this reduction toolkit to models whose variables take values in a finite non-Abelian group $G$, such as $S_3$, the quaternions $Q_8$, or the simple group $A_5$, with couplings that depend on the relative element $g_i^{-1}g_j$. The core idea is that in such models an edge is not a scalar strength but a family of small matrices, one per irreducible representation of $G$. Frustration around a cycle is then a matrix product, or holonomy, whose value depends on edge order and cannot be read off edge magnitudes. The resulting procedure has three parts. It collapses degree-2 chains exactly by ordered group convolution. It tests uniqueness on the reduced core with a representation-resolved non-backtracking operator. It prunes edges by how much they contribute to that operator's spectral radius rather than by their individual strength. The question is whether this ordering-sensitive criterion beats the obvious scalar generalizations on group-valued models, and whether it degrades to exactly BETHE-OPT when $G=\mathbb{Z}_2$.

Core Claim

Take a pairwise model with variables $g_i \in G$, edge factors $f_e(g_i^{-1}g_j) > 0$, and optional local fields. The non-commutative Fourier transform maps each edge factor to normalized matrices $A_e(\rho) = \hat f_e(\rho)/\hat f_e(\mathbf{1})$, where $\rho$ ranges over nontrivial irreducible representations of dimension $d_\rho$ and $\mathbf{1}$ is the trivial one. Linearizing belief propagation around its uniform fixed point in the field-free case shows that a message perturbation in channel $\rho$ is carried across edge $e$ by $A_e(\rho)$. This motivates the operator

$$ B_\rho[(u\to v),(v\to w)] = A_{vw}(\rho)\ \text{ if } w \neq u, \text{ and } 0 \text{ otherwise}, $$

which is a non-backtracking matrix on directed edges whose entries are $d_\rho\times d_\rho$ blocks. It is a matrix-weighted analogue of the Ihara zeta machinery Watanabe uses. We make three claims. The first, a theorem target, is that leaf removal and degree-2 collapse are exact. A leaf is absorbed into its neighbor's field, and a chain $f_1, f_2$ collapses to the ordered convolution $f_1 * f_2$, whose Fourier matrices are $A_{e_1}(\rho)A_{e_2}(\rho)$. Collapse therefore preserves every $B_\rho$ cycle product. The second, a conjecture to be proven or refuted, is that $\max_\rho \mathrm{spr}(B_\rho) < 1$ on the w-reduced core is sufficient for a unique fixed point in the field-free model. When $G=\mathbb{Z}_2$ this reduces to the known scalar condition. The third, an empirical claim, is that greedily deleting the edge whose removal most lowers $\max_\rho \mathrm{spr}(B_\rho)$ on the reduced core gives lower marginal error at equal edge budget than any scalar criterion when couplings have similar strength but different holonomy.

A concrete case shows why the third claim is not vacuous. On $S_3$, let three edges of a triangle each strongly favor a different transposition. Every edge then has the same scalar strength. The holonomy in the two-dimensional representation is the product of three reflection matrices. That product is itself a reflection, an element of order two, whereas transposition patterns whose product is trivial yield the identity. Scalar criteria cannot distinguish these configurations, but belief propagation behaves differently on them.

Relation to Prior Work

The binary reduction results above supply the method and constrain it. Watanabe's w-reduction gives us the reduction operators and the zeta-function route to uniqueness, and we generalize its weights from signs to representation matrices. BETHE-OPT gives the greedy deletion loop. Its Theorem 4, which says deleting edges almost always worsens the partition-function estimate $Z$, is a negative result we inherit rather than escape, so we report $\log Z$ error alongside marginal error.

The non-Abelian side motivates the representation-theoretic view and supplies tools. Fast transforms for non-Abelian 2-groups (Fast Quantum Fourier Transforms for a Class of Non-Abelian Groups) show these Fourier matrices are cheap to compute. Our use is classical, not a quantum algorithm. Kempe and Shalev's result that Fourier sampling over most $S_n$ subgroups carries no information (The hidden subgroup problem and permutation group theory) warns that representation channels can wash out. We test for this directly with $A_5$, which has no Abelian quotient at all.

The closest work joining the two directions treats graph structure as fixed while doing non-Abelian algebra on top. Lensky et al. use degree-2/3/4 graphs as a canvas for braiding Ising anyons but never compress the graph (Graph gauge theory of mobile non-Abelian anyons). Fechisin et al. build group-valued cluster states only on 1D chains (Noninvertible Symmetry-Protected Topological Order in a Group-Based Cluster State). Sheffer et al. decompose solvable groups recursively on a rigid lattice (Preparing topological states with finite depth simultaneous commuting gates). None of them defines reduction operators whose correctness depends on non-commutative cycle products, which is what we do.

Research Program

The theory track first proves exactness of leaf absorption and ordered chain collapse for general pairwise factors, including fields at the eliminated vertex. In that case the collapsed factor is no longer a function of $g_i^{-1}g_k$ alone, and we handle it through the decomposition on $G\times G$. It then attempts the uniqueness conjecture by adapting the Bethe-Hessian/zeta argument to block weights. Reaching only a local-stability statement rather than global uniqueness would be an honest partial result.

The algorithm track implements the full pipeline: w-reduce, compute $B_\rho$ for all irreducible representations, prune greedily, then run belief propagation on the pruned graph. Because each step needs only a dominant eigenvalue, and each $B_\rho$ has $2|E|\,d_\rho$ rows, the cost stays small for the groups we study.

The empirical track builds a benchmark of group-valued models where exact answers are computable. These use $G \in \{\mathbb{Z}_2, \mathbb{Z}_3, S_3, D_4, Q_8\}$ on the complete graph with $N=10$ (45 edges) and on the $5\times 5$ grid, matching the synthetic settings of BETHE-OPT. For $S_3$ on $K_{10}$, brute force has about $6\times10^7$ states, which is feasible. $A_5$ is used on small cyclic graphs with chords, where fixing one variable's value by gauge symmetry keeps exact enumeration near $10^7$ states. Couplings are drawn at controlled strength with independently controlled holonomy, either aligned, where the cycle product is the identity, or frustrated.

Baselines

The naive reference point is plain belief propagation on the unreduced graph, both undamped and with damping tuned on held-out instances. This is the "do nothing" option. The only reported figure for it is in the binary case: standard BP marginal error rates near 0.8 on dense attractive Ising models with $N=10$ and 45 edges (Fixing the Bethe approximation).

The strongest existing competitor is the direct generalization of BETHE-OPT to many-state variables. Each edge is scored by its dynamic range $\tfrac12\log(\max f_e/\min f_e)$, which reduces to $|J_{ij}|$ for $\mathbb{Z}_2$ and inherits the same bound on free-energy discrepancy for any bounded factor. The file reports no number for this on group-valued models. The binary reference is the finding that reducing from 45 to 20–25 edges "significantly dropped the error" (same paper). We run it with the identical edge-budget schedule, the same belief-propagation implementation, and the same convergence tolerance. Beating it means lower mean absolute marginal error at matched edge count across frustrated-holonomy instances, without losing on aligned instances. A further requirement is that the two methods give identical deletion orders on $\mathbb{Z}_2$, which serves as a correctness check.

The information-theoretic baseline is Chow-Liu pruning by pairwise mutual information computed from exact pairwise marginals. This is an oracle advantage we grant deliberately. Abelianization replaces $G$ by $G/[G,G]$ and runs binary or cyclic BETHE-OPT. Two ablations isolate our ingredients: the spectral-radius score applied without prior chain collapse, and chain collapse followed by the scalar score. Random deletion at matched budget anchors the bottom of the comparison.

Why not just…?

Why not just use the scalar dynamic-range generalization of BETHE-OPT? This is the real threat. It has a clean error bound, and on models with heterogeneous edge strengths it may match us. Its blind spot is predictable: at equal edge strengths it ranks edges by ties or noise, while holonomy decides which cycles destabilize belief propagation. Our holonomy sweep at fixed strength decides the question. If the scalar score matches ours even there, the non-Abelian structure does not matter for pruning, and we would report the reduction-plus-uniqueness test as the only contribution.

Why not just one-hot encode group elements and use Potts-model tools or Chow-Liu? One-hot Potts treatment is exactly what the dynamic-range score already captures. Chow-Liu ignores the group action, and in the binary setting it did no better than the cheaper coupling criterion, and worse in strong local fields (Fixing the Bethe approximation). We include it with oracle mutual information, so a loss to it would be meaningful.

Why not just reduce to the Abelian part of the group? For $A_5$ the Abelianization is trivial, so this baseline sees no couplings at all. For $S_3$ it keeps only the sign representation and discards the two-dimensional channel, where non-commuting holonomy lives. The $A_5$ and $S_3$ results show directly how much is lost.

Why not just use classical topological reducers such as PrunIT or $k$-cores? These preserve homology using neighborhood containment (Reduction Algorithms for Persistence Diagrams of Networks: CoralTDA and PrunIT). They are blind to edge factors, so they cannot be exact for inference except where they coincide with leaf and chain removal, which our method already includes.

Proposed Experiments

The first decisive check is the $\mathbb{Z}_2$ sanity test. Our pipeline must reproduce BETHE-OPT's deletion order and error curve on $K_{10}$ and the $5\times5$ grid. The second is the fixed-strength holonomy sweep on $S_3$, $D_4$ and $Q_8$, measuring marginal error, $\log Z$ error and convergence rate against edge budget for every baseline. The third tests whether $\max_\rho \mathrm{spr}(B_\rho)$ computed on the w-reduced core predicts convergence: we plot it against the observed convergence probability and look for a sharp transition near 1, which would support the uniqueness conjecture empirically. The fourth runs the $A_5$ small-graph study to see whether representation channels stay informative for a non-solvable group or wash out as Kempe and Shalev's results might suggest. Finally, we track the partition-function trade-off throughout. If holonomy-aware pruning improves marginals but worsens $\log Z$ more than scalar pruning does, we state that plainly as the non-Abelian form of BETHE-OPT's Theorem 4.