Decoration-Iteration Graph Coarsening

1. Integration point: use this as a preprocessing or first layer for graphs containing repeated three-node decorated edges, molecular fragments, mesh cells, or bipartite factor-graph motifs. Keep endpoint nodes as the coarse graph and eliminate the auxiliary node before message passing. For each motif, parameterize a local energy \(E_\theta(s,\sigma_i,\sigma_j,x)\), where \(x\) contains edge features, and enumerate the three auxiliary states exactly. 2. Pseudocode: compute Wpp=sum_s exp(-beta*E(s,+1,+1)), Wmm=sum_s exp(-beta*E(s,-1,-1)), and Wpm=sum_s exp(-beta*E(s,+1,-1)); set Keff=.25*log(Wpp*Wmm/Wpm**2) and heff=.25*log(Wpp/Wmm); send the coarse message m_ij = MLP([h_i,h_j,Keff,heff]) along the retained edge; optionally add the original auxiliary-node message as a gated residual. 3. Computed from the paper's mechanism: exact marginalization, effective coupling, effective field, and normalization. Estimated empirically: the local energy network, the residual gate, and downstream task loss. 4. First cheap experiment: train on synthetic node-classification or graph-regression datasets made by replacing every edge in a small grid or Cora-sized graph with a random three-state decorated node. Compare a standard GNN, a GNN with explicit auxiliary nodes, and this coarsened layer at equal message-passing FLOPs. The falsifiable prediction is that, when the data-generating auxiliary node follows the assumed local energy, coarsening preserves predictions while reducing graph size by approximately the auxiliary-node fraction. The learned effective field should cross zero precisely when measured conditional endpoint weights satisfy \(W_{++}=W_{--}\), and errors should grow sharply when the auxiliary interactions become nonlocal.