# Decoration-Iteration Graph Coarsening

- ID: 760
- Canonical URL: https://synthcore.org/idea/760/decoration-iteration-graph-coarsening
- API JSON: https://synthcore.org/api/idea/760.json
- API Markdown: https://synthcore.org/api/idea/760.md
- Verification status: unverified
- Source: [arXiv:2607.11661](https://arxiv.org/abs/2607.11661)
- Category: architecture
- Solves: scalability, accuracy, stability
- ML areas: graph-nn, training-dynamics, regularization
- Math tags: statistical-mechanics, renormalization, graph-theory, probability
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Construct a graph-neural layer that analytically eliminates fast auxiliary nodes inside repeated decorated motifs and replaces each motif by an effective edge or hyperedge. The effective interaction is computed from the log-partition function of the eliminated variables, while a residual neural correction can model violations of the assumed local motif structure.

## Mathematical statement

For a decorated edge with endpoint states \(\sigma_i,\sigma_j\in\{-1,+1\}\) and auxiliary state \(s\in\{-1,0,+1\}\), define the local Boltzmann weight \(W(\sigma_i,\sigma_j)=\sum_s\exp[-\beta E(s,\sigma_i,\sigma_j)]\). The decoration-iteration representation fits \(W(\sigma_i,\sigma_j)=A\exp[K_{\mathrm{eff}}\sigma_i\sigma_j+h_{\mathrm{eff}}(\sigma_i+\sigma_j)]\), where \(A>0\) is a normalization, \(K_{\mathrm{eff}}\) is the induced endpoint coupling, \(h_{\mathrm{eff}}\) is the induced field, and \(\beta\) is inverse temperature. Writing \(W_{++}=W(+1,+1)\), \(W_{--}=W(-1,-1)\), and \(W_{+-}=W(+1,-1)\), the exact parameters are \(K_{\mathrm{eff}}=\frac14\log(W_{++}W_{--}/W_{+-}^2)\), \(h_{\mathrm{eff}}=\frac14\log(W_{++}/W_{--})\), and \(A=(W_{++}W_{--}W_{+-}^2)^{1/4}\). The symmetric solvable regime is \(h_{\mathrm{eff}}=0\), equivalently \(W_{++}=W_{--}\).

## Key formulas

- $$W(\sigma_i,\sigma_j)=\sum_{s\in\{-1,0,+1\}}\exp[-\beta E(s,\sigma_i,\sigma_j)]$$
- $$W(\sigma_i,\sigma_j)=A\exp\left[K_{\mathrm{eff}}\sigma_i\sigma_j+h_{\mathrm{eff}}(\sigma_i+\sigma_j)\right]$$
- $$K_{\mathrm{eff}}=\frac{1}{4}\log\frac{W_{++}W_{--}}{W_{+-}^{2}},\qquad h_{\mathrm{eff}}=\frac{1}{4}\log\frac{W_{++}}{W_{--}}$$
- $$h_{\mathrm{eff}}=0\Longleftrightarrow W_{++}=W_{--}$$

## Implementation notes

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.

## Disclaimer

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