# Følner-Gated Message Passing

- ID: 2062
- Canonical URL: https://synthcore.org/idea/2062/f-lner-gated-message-passing
- API JSON: https://synthcore.org/api/idea/2062.json
- API Markdown: https://synthcore.org/api/idea/2062.md
- Verification status: failed_benchmark
- Source: [arXiv:2608.09796](https://arxiv.org/abs/2608.09796)
- Category: architecture
- Solves: stability, memory, scalability
- ML areas: graph-nn, memory, inference-speedup, training
- Math tags: dynamical-systems, graph-theory, combinatorics, optimization
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

## Idea description

Add an online receptive-field expansion monitor to a graph neural network and use it to gate message-passing depth or invoke graph pooling. For a sampled node set F and propagation neighborhood K, continue fine-scale propagation only while the growth ratio |KF|/|F| is close to one; when it is persistently expansive, replace further propagation with pooling, local attention, or long-range skip messages. This transfers the paper's Følner-versus-paradoxical mechanism into an architecture-level control rule for oversquashing and explosive activation or memory growth.

## Mathematical statement

For a finite node set F and a finite set K of allowed one-step graph moves, define the K-neighborhood KF={k·x:k∈K,x∈F}, or equivalently KF=N_K(F) in an ordinary graph. The Følner condition is |KF|≤(1+ε)|F|, where ε>0 is a tolerance. Fiberwise amenability asserts that, after enlarging the allowed context to a set L, every finite seed M has an intermediate F satisfying M⊆F⊆LM and the Følner inequality. The contrasting non-amenable condition gives an L such that LM contains n pairwise disjoint translated copies Kx, implying strong expansion and replicated receptive-field demand. In a finite graph, estimate r_K(F)=|N_K(F)|/|F| and its multistep version r_K^(q)(F)=|N_{K^q}(F)|/|F|. The neural controller uses r_K(F)≤1+ε as the low-growth regime and r_K(F)≥1+δ, or repeated growth across q layers, as the expansive regime. This is a finite-graph proxy for the paper's dichotomy rather than a claim that every finite graph has an exact amenability classification.

## Key formulas

- $$KF=\{k\cdot x:k\in K,\ x\in F\},\qquad |KF|\leq(1+\varepsilon)|F|.$$
- $$M\subseteq F\subseteq LM,\qquad |KF|\leq(1+\varepsilon)|F|.$$
- $$r_K(F)=\frac{|N_K(F)|}{|F|},\qquad r_K^{(q)}(F)=\frac{|N_{K^q}(F)|}{|F|}.$$
- $$LM\supseteq\bigsqcup_{i=1}^{n}Kx_i\quad\Longrightarrow\quad |LM|\geq n|K|\ \text{when the translates }Kx_i\text{ are disjoint}.$$

## Implementation notes

1. Integration point: use a residual message-passing GNN with L layers, hidden state h_v^ell, and a lightweight controller before each layer. For a minibatch of seed nodes, sample F from the current receptive-field nodes or from a fixed-size frontier. Let K be the one-hop move set, optionally including self-loops and two-hop edges. Compute an approximate neighborhood F_next=N_K(F) using sparse adjacency expansion, and estimate r=|F_next|/max(1,|F|). Maintain an exponential moving average r_bar and a consecutive-expansion counter. 2. Pseudocode: initialize F from the seed batch and r_bar=1; at layer ell compute F_next=N_K(F), r=|F_next|/max(1,|F|), and r_bar=beta*r_bar+(1-beta)*r. If r_bar≤1+epsilon, execute h^{ell+1}=h^ell+alpha_ell MSG_K(h^ell). Otherwise execute local message passing and a pooled skip: h^{ell+1}=h^ell+g MSG_K(h^ell)+(1-g)U(POOL(F_next)), where g=sigmoid(a((1+delta)-r_bar)). Optionally coarsen F by selecting cluster representatives whenever r_bar>1+delta for q consecutive layers. 3. Computed quantities are sparse frontier cardinalities, sampled expansion ratios, the gate, and pooled features. Estimate expansion on 4–8 random seed sets and report confidence intervals. The paper contributes the operational Følner/paradoxical criterion; the finite-graph estimator, gate, and pooling are the ML adaptation. 4. First cheap experiment: compare a 6-layer GCN or GraphSAGE baseline, fixed pooling, and Følner-gated GraphSAGE on cycle graphs, 2D grids, 3-regular random graphs, and finite 3-regular trees, using node classification with synthetic labels depending on radius-3 neighborhoods. Use identical parameter counts and train for 100 epochs. Measure validation accuracy, peak frontier size, activation memory, and oversmoothing through average pairwise cosine similarity. The quantitative prediction is that cycles and grids will show r_K(F) approaching 1 for sufficiently large sampled F, while trees and expanders will maintain r_K(F)>1+delta; the gate should activate predominantly on the latter. The measured activation boundary should occur near r_bar=1+delta, and gated propagation should reduce peak receptive-field memory by at least 25% on expansive graphs without reducing radius-3 accuracy by more than 2 percentage points.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: inconclusive
- Verdict: Built a reproducible Følner-gated six-layer message-passing prototype with frontier expansion monitoring, EMA gating, pooled skips, exact graph sanity checks, and a four-graph classification comparison. The core mechanism manifested: cycle ratios matched 1+2/m exactly, tree-ball ratios matched the exact expansive-growth calculation, and the sigmoid gate's 0.5 boundary matched r=1+delta=1.35 for all tested slopes. The mini-experiment did not show a general accuracy or speed win: gating activated on all finite graphs because the sampled frontier expanded, and accuracy was usually lower than baseline; therefore this is a mechanism-validation success, not evidence of a practical model improvement.

### Mechanism check

- Verdict: Built a reproducible Følner-gated six-layer message-passing prototype with frontier expansion monitoring, EMA gating, pooled skips, exact graph sanity checks, and a four-graph classification comparison. The core mechanism manifested: cycle ratios matched 1+2/m exactly, tree-ball ratios matched the exact expansive-growth calculation, and the sigmoid gate's 0.5 boundary matched r=1+delta=1.35 for all tested slopes. The mini-experiment did not show a general accuracy or speed win: gating activated on all finite graphs because the sampled frontier expanded, and accuracy was usually lower than baseline; therefore this is a mechanism-validation success, not evidence of a practical model improvement.
- Confidence: 6/10
- Limitations: The implementation uses dense adjacency matrices and a global pooled skip rather than sparse minibatch graph sampling or learned local pooling. It does not measure true activation memory, FLOPs, peak GPU memory, confidence intervals, fixed pooling, or radius-3 labels as specified. The auxiliary EMA persistence approximation disagreed with the discrete recurrence for r=1.6 and r=2.0, so it was not used to claim a win.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.5225
- Paired wins: 6/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/830/bench_report.json)
- [report.md](https://synthcore.org/code/830/report.md)
- [report_bench_2026-09-01T113846.md](https://synthcore.org/code/830/report_bench_2026-09-01T113846.md)
- [results.json](https://synthcore.org/code/830/results.json)
- [run_experiment.py](https://synthcore.org/code/830/run_experiment.py)
- [stage2_folner_bench.py](https://synthcore.org/code/830/stage2_folner_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/830)

## Disclaimer

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