- 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
-
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.
-
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.
Thank you for the careful reading and for pointing out substantial issues with the limitations. Reviewer 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: