Exact Locality Limits of Message Passing for Graph-Energy Optimization

How many message-passing layers are required to minimize a graph energy? For sourced Dirichlet energies on a path of diameter $D$, we determine the exact minimax depth over two opposite endpoint-source orientations. Every $K$-local algorithm has worst-orientation energy gap at least $\frac{a^2}{2}(D-2K-2{)}_{+}$, where $a>0$ 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 $\lfloor (D-1)/2\rfloor$ rounds, so this is the exact complexity for every target gap below $a^2/2$. 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 $K$-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.