# Histogram-Controlled Cluster Updates for Iterative GNNs

- ID: 1172
- Canonical URL: https://synthcore.org/idea/1172/histogram-controlled-cluster-updates-for-iterative-gnns
- API JSON: https://synthcore.org/api/idea/1172.json
- API Markdown: https://synthcore.org/api/idea/1172.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.20130](https://arxiv.org/abs/2607.20130)
- Category: architecture
- Solves: speedup, stability, scalability
- ML areas: graph-nn, inference-speedup, training-dynamics
- Math tags: graph-theory, combinatorics, probability, optimization
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

## Idea description

Replace node-by-node scheduling in an iterative message-passing network with a learned scheduler that selects one graph cluster at a time, while updating all nodes in that cluster synchronously. The scheduler observes a quantized histogram of local residual weights, making its state invariant to permutations of nodes inside a cluster and independent of cluster cardinality.

## Mathematical statement

Use a sparse bipartite graph G=(V,C,E), where V are neural state nodes and C are local constraint or aggregation nodes. Let delta_j in {0,1} indicate whether factor c_j currently has a residual, disagreement, or constraint violation. For node v_i, define the local mismatch weight omega_i as the sum of delta_j over neighboring factors. Partition V into clusters C_a. For a cluster of size B_a, define h_{a,r} as the fraction of its nodes whose quantized mismatch weight equals bin r. The quantizer q maps the possible degree range [0,A_max] into R bins. Thus the observation has fixed dimension R rather than dimension B_a. A scheduler selects action a_t, and every node in the selected cluster is updated from the same pre-update state. A Q-learning controller uses the temporal-difference recursion Q(s,a) <- Q(s,a) + alpha [r + gamma max_{a'} Q(s',a') - Q(s,a)].

## Key formulas

- $$\omega_i=\sum_{c_j\in\mathcal N(v_i)}\delta_j,\qquad \delta_j\in\{0,1\}$$
- $$h_{a,r}=\frac{1}{B_a}\sum_{v_i\in\mathcal C_a}\mathbf 1\!\left\{q(\omega_i)=r\right\},\qquad q(\omega)=\left\lfloor \frac{R\omega}{A_{\max}}\right\rfloor$$
- $$Q(s,a)\leftarrow Q(s,a)+\alpha\left[r+\gamma\max_{a'}Q(s',a')-Q(s,a)\right]$$
- $$\mathbf x_{i,t+1}=F_\theta\!\left(\mathbf x_{i,t},\{\mathbf x_{u,t}:u\in\mathcal N(i)\}\right)\quad\forall v_i\in\mathcal C_{a_t}$$

## Implementation notes

Integrate this into a recurrent GNN or neural algorithmic solver that currently performs T full message-passing sweeps. First partition graph nodes into fixed clusters using METIS, BFS blocks, or balanced random blocks, and store node indices for every cluster. At each micro-step, compute a local residual for every factor. For a constraint-solving GNN, use delta_j = 1 when the factor is violated. For a supervised denoising GNN, use delta_j = 1 when the factor residual norm exceeds a threshold tau. Compute omega_i by summing residual indicators over neighboring factors, clip it to [0,A_max], quantize it with q(omega) = floor(R omega / A_max), and form the normalized R-bin histogram for every cluster. Concatenate all cluster histograms, the fraction of active factors, and the previous action, then feed the state to a small scheduler MLP. Select a cluster by argmax Q(s,a), or use epsilon-greedy exploration while training the scheduler. For the selected cluster, gather all neighbor states from the pre-update tensor, run the GNN update for every selected node in one batched operation, and scatter the outputs simultaneously. This preserves within-cluster parallelism and prevents accidental sequential ordering. Use reward r_t = -sum_j delta_{j,t+1} - lambda, where lambda penalizes a scheduling decision. The mathematical quantities are the residual weights, quantizer, histogram, and temporal-difference update; tau, lambda, cluster construction, and exploration rate are empirical choices. The first experiment should use a 10-layer recurrent GNN on synthetic graph-coloring, SAT, or matching instances with 1,000 to 10,000 nodes. Compare full synchronous sweeps, random cluster order, greedy largest-residual selection, and learned scheduling at equal wall-clock budget. Record residual mass, task accuracy, GPU utilization, and the number of sequential decisions. Success means lower residual or higher accuracy with at least 2x fewer sequential scheduling decisions and no instability from stale states.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: harms
- Verdict: Built a readable toy implementation of histogram observations, quantization, synchronous cluster scattering, and a residual-driven cluster selector. Histogram permutation/cardinality invariance and quantizer thresholds matched exactly; the stale sequential-vs-synchronous error followed the predicted eta^2 law with maximum error 1.1e-16. The mini-comparison ended at residual 74 for both full synchronous and histogram-selected updates, so the mechanism is real but this experiment did not establish a practical speedup or lower residual.

### Mechanism check

- Verdict: Built a readable toy implementation of histogram observations, quantization, synchronous cluster scattering, and a residual-driven cluster selector. Histogram permutation/cardinality invariance and quantizer thresholds matched exactly; the stale sequential-vs-synchronous error followed the predicted eta^2 law with maximum error 1.1e-16. The mini-comparison ended at residual 74 for both full synchronous and histogram-selected updates, so the mechanism is real but this experiment did not establish a practical speedup or lower residual.
- Confidence: 8/10
- Limitations: This is a small synthetic continuous-signal toy, not a trained recurrent GNN or Q-learning scheduler. It does not test METIS/BFS partitioning, GPU wall-clock utilization, learned policies, graph coloring/SAT accuracy, larger graphs, or statistical averages over multiple problem seeds.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 0/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [bench_report.json](https://synthcore.org/code/467/bench_report.json)
- [experiment.py](https://synthcore.org/code/467/experiment.py)
- [report.md](https://synthcore.org/code/467/report.md)
- [report_bench_2026-08-31T130730.md](https://synthcore.org/code/467/report_bench_2026-08-31T130730.md)
- [results.json](https://synthcore.org/code/467/results.json)
- [stage2_bench.py](https://synthcore.org/code/467/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/467)

## Disclaimer

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