acceptodds
Under review as a conference paper at ICLR 2027

Exact Locality Limits of Message Passing for Graph-Energy Optimization

Abstract

How many message-passing layers are required to minimize a graph energy? For sourced Dirichlet energies on a path of diameter , we determine the exact minimax depth over two opposite endpoint-source orientations. Every -local algorithm has worst-orientation energy gap at least , where is the source amplitude, even with arbitrary nonlinear computation, unbounded messages, source-independent labels and randomization. Source flooding and a source-adapted polynomial graph filter both attain an exact minimizer in rounds, so this is the exact complexity for every target gap below . On arbitrary weighted graphs, the general bound charges the optimal energy on edges hidden from the sources, and the exact two-orientation local minimax is a least-squares value over the source balls. For -local message-passing networks with scalar-potential outputs and locally supplied sources, this gives a necessary depth independent of width or training; it is a limit of local communication, not of neural networks in general, and global-attention models, which leave the local class, solve the same task with one or two blocks in our path controls. Trained GCN, GIN and GraphSAGE depth sweeps (10–20 seeds, training-budget ablation), including the Les Mis\'erables and karate-club topologies compared against the exact minimax curve, separate this causal barrier from architecture- and optimization-induced error above it.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
GNN, Message Passing, Graph Energy

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_gMpdOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the communication depth required to minimize sourced Dirichlet energies using local message passing. For paths with opposite endpoint-source orientations, it establishes a sharp energy-gap lower bound and the exact depth required for sufficiently accurate optimization, attained by source flooding and a source-adapted polynomial filter. For arbitrary weighted graphs, Theorem 3.3 characterizes the exact two-orientation minimax gap through a constrained least-squares problem, with attainability allowing precomputed, orientation-independent labels. Further results cover product strips and independently signed dipoles on spider graphs. Experiments with local GNNs, training-budget ablations, and global-attention controls illustrate the communication barrier and additional architecture or optimization error.

Critical strengths
  1. The lower bounds apply to a broad class of local algorithms. The model permits arbitrary nonlinear computation, unbounded messages, fixed labels, and randomized algorithms evaluated in expected energy gap. The result therefore identifies a communication limitation rather than a limitation of a particular architecture or optimizer. Matching constructions establish sharp depth thresholds on the specified graph families.

  2. The general-graph minimax characterization provides more information than the hidden-edge bound alone. Theorem 3.3 captures additional compatibility constraints, illustrated by the asymmetric-path counterexample. It provides a computable benchmark for assessing how much error is unavoidable under a given communication radius.

Critical weaknesses

The main limitation concerns the breadth of the learning implications. Theorem 3.3 provides an exact characterization for a fixed graph and source template, with attainability allowing template-dependent precomputed labels. The independent-bit extension broadens the instance family through a structured spider construction. These scope limitations temper the broader impact, but do not undermine the value of the sharp minimax characterization and matching constructions. On balance, I consider this a useful theoretical contribution and lean toward acceptance.

Questions for authors

I have no further substantive clarification questions. My remaining reservation concerns the significance of the contribution within its stated scope.

1 comment

Thank you for the careful reading and for pointing out substantial issues with the limitations. Reviewer ypUd\texttt{ypUd} raised the same points, and we refer you to our detailed response to that review. The revision addresses the major reviewer concerns across four areas:

  1. Mathematical correctness: We repair the inaccurate claims about exactness and establish depth-uniform optimal constructions.
  2. Broader significance: We extend our exact minimax theory to shared solvers with varying source configurations and interacting potentials.
  3. Practical relevance: We demonstrate that exact certificates improve communication-depth selection beyond what simpler locality arguments can achieve.
  4. Empirical validation: We show that trained shared GNNs closely approach the theoretical limits on held-out source configurations.
Reviewer_3A5COpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper works on minimizing Dirichlet energy on graphs. Graph neural networks (GNN) work by message passing between nodes. The distance that the messages can travel is dependent on the number of layers in the GNN. The paper asks the following question (and I quote): can this propagation obstruction be stated as a sharp optimization lower bound inside an actual graph-energy family?

I believe the question states that the lower bound on the optimal Dirichlet energy is a function of the number of layers in the GNN. Of course that should depend on the type of the GNN, its parameterization, the optimization algorithm, etc.

Critical strengths

The paper proves a number of theorems, which seem to have been empirically validated.

Critical weaknesses

The paper reads as if it is produce by AI end-to-end. It does not appear to have given much thought to the possibility that some humans may read it. Numerous technical jargons and symbols were used before definition. For example, what is x in Eq (1)? Most interestingly, in a paper on optimization bounds, not even a definition of the optimization problem is given.

I perceive no effort at making the theorems easy to understand for the audience, perhaps by restating them in simple forms. I found no discussion of how each theorem relates to the next, or how each relates to the real world. Line 454 contains a paragraph on its relation to graph learning, which I do not understand.

The experimental section talks about successes and failures, without even explaining what counts as successes and failures. If this is not evidence that the paper is written by AI, I don't know what is.

Questions for authors

Given the state of the the paper, I do not feel questions would be useful. They will just become prompts fed to AI.

2 comments

Thank you for your careful reading and for identifying these substantial presentation issues. We agree that the original exposition introduced too much notation before explaining the optimization task, the relationships among our results, and how to interpret the experiments. We have revised the main text to clarify these points. The density of the original manuscript was due to tight space constraints. In compliance with ICLR policy, we have disclosed our use of generative AI and large language models (LLMs) in both the submission form and the AI disclosure section of the manuscript. As noted by other reviewers, our lower bounds apply to a broad class of local algorithms. The model permits arbitrary nonlinear computation, unbounded messages, fixed labels, and randomized algorithms evaluated in expected energy gap. The result therefore isolates an intrinsic communication bottleneck that holds regardless of the specific architecture or optimizer. Matching constructions establish sharp depth thresholds on the specified graph families. The general-graph minimax characterization provides more information than the hidden-edge bound alone. Theorem 3.3 captures additional compatibility constraints, as illustrated by the asymmetric-path counterexample, and provides a computable benchmark for assessing the unavoidable error under a given communication radius.

We thank the reviewer again for their careful and constructive feedback. We would appreciate it if you could take another look at our rebuttal and revised manuscript, particularly the new theoretical results on shared solvers with varying source configurations (Theorem 3.9), the depth-selection implications beyond receptive-field reasoning (Corollary 3.8), and the held-out experiments.

We have also clarified the scope of our claims regarding exactness.

We would be grateful to hear whether these additions address your reservations and whether you might consider updating your assessment.

Reviewer_ypUdOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the communication depth required to minimize sourced Dirichlet energies. For a fixed graph and source template with an unknown global sign, it derives a hidden-edge energy lower bound and an exact local minimax characterization through constrained least squares. On paths with opposite endpoint sources, it obtains an exact high-accuracy depth threshold, attained by source flooding and a source-adapted polynomial filter. Extensions cover product strips, independently signed spider branches, and convex edge energies. Experiments compare trained message-passing networks with the theoretical certificates and examine optimization budgets and global-attention controls.

Critical strengths
  1. The general-graph minimax certificate contains useful information beyond receptive-field counting. Theorem 3.3 captures compatibility costs at the boundary between reached and unreached vertices, which the hidden-edge bound misses. The asymmetric P5 example distinguishes a²/2 from 3a²/4, while the random-tree example distinguishes depth 14, where the hidden-edge bound vanishes, from depth 20, where the exact minimax vanishes. This is the paper's strongest contribution.

  2. The experiments appropriately distinguish communication limits from training failure. The two source orientations share parameters, the authors explicitly identify the evaluation as a finite-family representation diagnostic, and longer training resolves several apparent failures above the necessary depth. Some trained networks closely approach V_K on grids and real-network topologies. The matching polynomial construction also usefully establishes that nonlinearity is unnecessary to attain the path threshold.

Critical weaknesses
  1. The significance of the exact characterization remains limited by the fixed-template information problem. The connection between message passing and LOCAL computation is established, as are finite-time spectral recovery principles; the advance here is the exact energy-error characterization for a restricted family, rather than a new locality obstruction (Loukas, 2020; Sundaram and Hadjicostis, 2007). In Theorem 3.3, the graph and source template are fixed, only the common sign is unknown, and attainment permits labels containing the precomputed restricted solution. This is explicitly disclosed and mathematically legitimate, but substantially limits the interpretation as guidance for learned graph-energy solvers. The experiments broaden topology coverage while still fitting and evaluating each model on the same two source orientations. The independent-bit spider construction retains separable branches. Although the boundary-cost certificate is useful, the paper does not yet establish a sufficiently consequential implication for shared solvers with varying source configurations or a broader graph-learning problem. This limitation in significance is my main reservation.

  2. Some claims of exactness exceed the proved results. Page 5 states that SOURCEFLOOD realizes the minimax value on paths, strips, and spiders. On P5 with a=1 and K=0, however, the specified algorithm outputs (2,0,0,0,-2), with gap 2, while V_0=1 is attained by (1,0,0,0,-1). It attains the exact solution at K*, but not the entire minimax curve. Similarly, the conclusion claims closed-form exact minimax gaps on spiders, whereas Theorem A.2 establishes a lower bound and an exact high-accuracy depth. For n=1 and D0=3, its K=0 bound is a²/2, but the exact value is 3a²/4, by the reflected asymmetric-P5 example. These are repairable scope errors, but matter in a paper whose central contribution is exactness.

Questions for authors
  1. Additional theoretical or empirical evidence concerning significance. Can the exact certificate support a consequential depth-selection or solver-design result when parameters and labels must be shared across varying source locations or relative strengths? A result for interacting source patterns, or a concrete application showing how V_K improves a useful decision beyond ordinary receptive-field reasoning, would materially strengthen my assessment. The present fixed-template diagnostic and separable spider extension leave this question open.

  2. Mathematical clarification of the claimed sharpness. How should the page-5 attainment statement and the conclusion's spider claim be revised in light of the counterexamples above? Is there a modified algorithm attaining V_K at every depth, or a stronger spider minimax formula beyond the stated depth theorem? Please distinguish these claims explicitly.

2 comments

We thank the reviewer for a careful report. Both counterexamples are correct; changes are in blue, and all original numbering is preserved (new: 3.7–3.9, A.3, F.3–F.4, Tables 3–5, Fig. 7).

1. Exactness (W2, Q2)

(a) SourceFlood below K⋆K^\star. The page-5 claim is removed. On P5P_5, a=1a=1, K=0K=0 it outputs (2,0,0,0,−2)(2,0,0,0,-2) with gap 2>V0=12>V_0=1; in general its gap is a22[(D−2K−2)+2(D/2−K−1)2]>VK\frac{a^2}{2}[(D-2K-2)+2(D/2-K-1)^2]>V_K (Prop. 3.7(iv)), from overshoot on the two frontier edges. A depth-uniform algorithm exists: ClampedFlood outputs s(min⁡(K+1,δ/2)−r)s(\min(K+1,\delta/2)-r). Prop. 3.7 proves VK=a22max⁡(D−2K−2,0)V_K=\frac{a^2}{2}\max(D-2K-2,0) at every depth (hence KεK_\varepsilon for every ε≥0\varepsilon\ge0), attained by ClampedFlood with generic labels and by a degree-KK polynomial filter (Fig. 5 is now a theorem). Strips: VK=a22qmax⁡(D−2K−2,0)V_K=\frac{a^2}{2q}\max(D-2K-2,0), same rule.

(b) Spiders. Thm. A.2 is now titled a depth law; "closed form on spiders" is removed. New Prop. A.3: the single-leg value VKleg=a22[(D0−2K−2)+(K+1)2K+1+Rn,K]V_K^{\rm leg}=\frac{a^2}{2}\big[(D_0-2K-2)+\frac{(K+1)^2}{K+1+R_{n,K}}\big] (Rn,0=1R_{n,0}=1; Rn,K=1+K/(n−1)R_{n,K}=1+K/(n-1) for K≥1,n≥2K\ge1,n\ge2), giving the reviewer's 3a2/43a^2/4; the exact average-case value nVKlegnV_K^{\rm leg}; and only a bracket nVKleg≤MK≤nVKleg+⌊n/2⌋ρKnV_K^{\rm leg}\le M_K\le nV_K^{\rm leg}+\lfloor n/2\rfloor\rho_K for the worst case (not tight: 2<7/3<5/22<7/3<5/2 at n=2,D0=5,K=1n=2,D_0=5,K=1). We state that no closed-form worst case is known for 1≤K<K⋆1\le K<K^\star, n≥2n\ge2. We also fixed two similar overstatements (Fig. 5 caption; App. C).

2. Significance (W1, Q1)

We now credit Loukas (2020) and Sundaram–Hadjicostis (2007) for the obstruction itself; our contribution is its exact value. Three additions:

(a) Shared solvers (Thm. 3.9). For atoms bjb_j with disjoint supports and bθ=∑jθjbjb^\theta=\sum_j\theta_jb_j, with θj\theta_j independent and symmetric (sites on/off, signs and strengths varying), every KK-local rule shared by the family has Eθ[gap]≥∑jτj2VK(j)\mathbb E_\theta[\text{gap}]\ge\sum_j\tau_j^2V_K^{(j)}, τj2=Eθj2\tau_j^2=\mathbb E\theta_j^2, with equality for one linear rule. This holds on any graph, with arbitrarily overlapping potentials (no separability). The family's exact depth is max⁡jK0(j)\max_jK_0^{(j)}. The worst case is bracketed and, for finite families, a convex program (Prop. F.3).

(b) A depth decision receptive fields get wrong (Cor. 3.8, Prop. F.4). VK=0V_K=0 iff the potential is constant on the whole unreached set, not per component. On a comb (d=10d=10, teeth ℓ=6\ell=6) no hidden edge carries energy at K=4K=4, yet every 4-local algorithm keeps 67.6% of the gap; exactness needs 1010. Random tree: 14 / 17 (1%) / 20 (exact). On grid, karate club and small-world graphs the two rules agree (Table 3); the effect is large on tree-like graphs.

(c) Held-out experiment. One GIN or GraphSAGE network on the karate club, three sites, θj=0\theta_j=0 w.p. 0.3 else U[−1,1]U[-1,1], fresh draws per step, 8192 held-out configurations, 5 seeds. Predicted values for K=0..4K=0..4: 0.1626,0.0831,1.26×10−3,0,00.1626, 0.0831, 1.26\times10^{-3}, 0, 0. No run falls below the optimal rule on the held-out set; for K≤1K\le1 runs are within 10−410^{-4} of it, and from K0=3K_0=3 the residual is ≤7.3×10−4\le7.3\times10^{-4} (0.17% of the initial gap).

Limits (Sec. 6): fixed graph and dictionary with disjoint supports; attainment uses graph-specific labels; worst case for interacting sources is a convex program, not a formula; the experiment covers one graph.

We thank the reviewer again for their careful and constructive feedback. We would appreciate it if you could take another look at our rebuttal and revised manuscript, particularly the new theoretical results on shared solvers with varying source configurations (Theorem 3.9), the depth-selection implications beyond receptive-field reasoning (Corollary 3.8), and the held-out experiments.

We have also addressed both mathematical counterexamples and clarified the scope of our exactness claims.

Since the revision directly targets your main concerns regarding significance and mathematical sharpness, we would be grateful to hear whether these additions address your reservations and whether you might consider updating your assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.