✓✓ Beats tuned baseline 2026

Kesten–Stigum Attenuated Message Passing

Implementation & benchmark of arXiv:2607.16676 — The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy

Usefulness8/10

Difficulty5/10

Novelty6/10

Architecture Accuracy Stability Scalability Graph nn Architecture Training dynamics Probability Stochastic processes Information theory

Source paper: The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy arXiv:2607.16676 ⓘ · analyzed Aug 30, 2026

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

Idea description

Replace uniform graph-convolution aggregation with a distance-aware message transform whose strength decays as $\gamma^k$. At hop $k$, transform the learned local evidence with $2\operatorname{artanh}(\gamma^k z)$ before summation, so distant nodes have a provably shrinking influence window rather than accumulating unbounded noisy evidence.

Formulas

$$T_{\ell}=\sum_{k=0}^{\ell}\sum_{v:d(o,v)=k}2\operatorname{artanh}\!\big(\gamma^{k}t(X_v)\big),\qquad t(x)=\frac{\rho_{+}(x)-\rho_{-}(x)}{\rho_{+}(x)+\rho_{-}(x)}.$$

$$\left|2\operatorname{artanh}(\gamma^k t(X_v))\right|\leq 2\operatorname{artanh}(\gamma^k),$$

$$\kappa=\gamma^2\Delta,\qquad |\mathcal{E}(\ell)-\mathcal{E}(\ell')|\leq C\,\kappa^{(\ell+1)/3}\quad(\kappa<1,\ \ell'>\ell).$$

$$\ell\gtrsim \frac{3\log(C/\varepsilon)}{\log(1/\kappa)}\quad\Longrightarrow\quad |\mathcal{E}(\ell)-\mathcal{E}(\ell')|\leq\varepsilon.$$

Mathematical statement

The paper's classifier is $T_{\ell}=\sum_{k=0}^{\ell}\sum_{v:d(o,v)=k}2\operatorname{artanh}(\gamma^k t(X_v))$, with $t(x)=(\rho_+(x)-\rho_-(x))/(\rho_+(x)+\rho_-(x))$. Here $o$ is the root node, $d(o,v)=k$ is graph distance, $\rho_+$ and $\rho_-$ are class-conditional feature densities, $t(X_v)\in[-1,1]$ is bounded local evidence, and $\gamma$ is the edge-label correlation. The transform clips hop-$k$ evidence to $[-2\operatorname{artanh}(\gamma^k),2\operatorname{artanh}(\gamma^k)]$, creating a shrinking receptive-field contribution. The governing branching-process quantity is $\kappa=\gamma^2\Delta$, where $\Delta$ is average degree: subcritical $\kappa<1$ implies geometric depth saturation, while supercritical $\kappa>1$ implies geometrically useful additional depth.

Implementation notes

Integrate this into the message-update line of a sparse GNN, preferably a GraphSAGE or GCN operating on sampled radius-$L$ neighborhoods. First compute a scalar local evidence $z_v$ from the node embedding, for example $z_v=\tanh(w^\top h_v+b)$, so $z_v\in(-1,1)$. For each root node, maintain BFS distance $k$ and replace the usual hop contribution by $m_v=2\operatorname{atanh}(\operatorname{clip}(\gamma^k z_v,-1+\delta,1-\delta))$, with numerical clamp $\delta=10^{-6}$. Sum or attention-pool these messages by hop and feed the resulting statistic to the classifier; alternatively use the transform inside every sampled-neighborhood aggregation layer. Initialize $\gamma\in(0,1)$ from a validation estimate of edge-label correlation, or make $\gamma=\sigma(a)$ learnable with a penalty preventing values near one. Estimate $\Delta$ as the mean training-graph degree and report $\kappa=\gamma^2\Delta$. The theorem supplies the geometric attenuation and the subcritical depth heuristic; $C$, feature evidence, and the best learned $\gamma$ must be estimated empirically. The first experiment should use a 2-layer GCN/GraphSAGE baseline and an 8-layer version on sparse CSBM or Cora with randomly subsampled edges. Compare uniform aggregation against this rule at equal hidden size and sampled edges. Measure validation accuracy, gradient norms, performance versus depth, and calibration. Success is delayed oversmoothing, less erratic accuracy as depth increases, and equal accuracy with fewer sampled hops or layers.

Verification

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

Stage 2 · Practical benchmark result: Significant win ✓

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

How to read this: The implementation beat the baseline, but the claimed mechanism did not reproduce at benchmark scale. The gain may come from another effect; treat the cause as unresolved.

Stage 1 — Mechanism check agent confidence 8/10

Built and ran a reproducible toy verification of Kesten–Stigum attenuated message passing. The hop-wise influence bound matched exactly (maximum absolute error 0), the swept shell-variance ratio matched κ=γ²Δ within 0.0051 with 100% decay/growth regime agreement, and the subcritical κ=0.81 curve showed attenuation retaining 0.929 accuracy at depth 8 versus uniform aggregation falling to 0.781. In the supercritical κ=2.42 setting both methods reached 1.0 accuracy, so the mechanism is supported in this toy model but not established as a general GNN improvement.

Agent confidence: 8/10

Baseline: Uniform shell aggregation: subcritical best accuracy 0.8129 and depth-8 accuracy 0.7813; supercritical depth-8 accuracy 1.0000.
Idea: Attenuated atanh aggregation: subcritical best/depth-8 accuracy 0.9289; supercritical depth-8 accuracy 1.0000. Influence-bound error 0.0; κ-ratio maximum absolute error 0.0050; regime agreement 1.0.

Limitations: This is a synthetic independent-shell moment approximation, not an actual sparse GCN/GraphSAGE implementation, Cora benchmark, learned gamma experiment, calibration study, FLOP comparison, or exact graph simulation. The influence-bound check directly evaluates the proposed formula, and the classification curves use Gaussian shell statistics rather than explicitly materialized branching trees.

How to run: python3 ks_attenuated_experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.16676) Sep 2, 2026

Beats the tuned baseline by 8.7% (p=0.0081, wins 8 / 8 paired seeds; metric: lower is better).

Benchmark: Custom:csbm_radius_graph
Model: GraphNet
Paired seeds: 8
Baseline mean: 0.1184
Idea mean: 0.1081
Effect (Δ): -0.0103 (−8.7%; negative = idea better)
Wins: 8 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Not confirmed ✗
Practical effect: Helps
Baseline tuning: swept over 0 configs

Limitations:

Only the custom fixed radius-2 graph task was tested; no Cora, sparse sampled neighborhoods, deeper GNNs, calibration, FLOP measurements, learnable gamma, or external graph datasets were evaluated. The mechanism signature measured learned hidden evidence rather than the exact pre-classifier shell contribution and therefore failed confirmation despite the task-metric win.

How to run: python3 ks_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 30, 2026 latest Worked ✓

Agent confidence: 7/10

Built a structurally matched custom radius-2 graph classification track and paired uniform versus Kesten–Stigum attenuated GraphNet systems using identical data, architecture, epochs, and shared learning-rate search space. The idea improved mean test cross-entropy from 0.11844 to 0.10812 across all 8 paired seeds, with permutation p=0.0081, satisfying the benchmark's significant-win criterion. The model-derived mechanism signature was not confirmed: observed shell ratios were [1.000, 1.019, 0.979] versus predicted [1.000, 0.500, 0.250].

Baseline: Mean test cross-entropy 0.1184375 ± 0.0174525; best lr=0.003; per-seed [0.1000, 0.0950, 0.1425, 0.1225, 0.1125, 0.1475, 0.1175, 0.1100].
Delta mean: -0.0103125 (-8.71% relative to baseline); all 8 paired seeds improved; permutation p=0.0081.
Idea: Mean test cross-entropy 0.1081250 ± 0.0185300; best lr=0.01, gamma=0.5; per-seed [0.0900, 0.0800, 0.1325, 0.1150, 0.1050, 0.1375, 0.1075, 0.0975].
Mechanism signature: map[confirmed:false max_abs_ratio_error:0.728622 observed_model_shell_ratio:[1 1.019423 0.978622] predicted_shell_ratio:[1 0.5 0.25]]

Benchmark result