Which Algorithms Can Graph Neural Networks Learn?

Summary

The paper studies when message-passing neural networks (MPNNs) can learn, rather than merely represent, discrete graph algorithms, and delivers worst-case size-generalization guarantees rather than the in-distribution PAC-style bounds that dominate the prior generalization literature for GNNs. The conceptual move is to package algorithmic learnability as three ingredients — a hypothesis class whose Lipschitz constant admits a computable certificate $B_{\boldsymbol\theta}$, a target algorithm that can be uniformly approximated inside that certificate budget, and a pseudo-metric on the input space with finite covering numbers — and then to run a standard cover-plus-Lipschitz-control argument through that setting. Under Definition 1 and Theorem 2, minimizing a certificate-regularized empirical loss on a cover of $\mathcal V_1(\mathcal G)$ suffices to approximate the target on inputs of arbitrary size. The framework then plugs into MPNNs by producing pseudo-metrics for normalized-sum, mean, and max/min aggregation (Theorem 3), from which the paper derives worked examples for truncated PageRank, Bellman–Ford, and a knapsack-as-shortest-path reduction. The complementary negative side (Section 3, Lemma 6) shows that architectures matching 1-WL cannot form finite Lipschitz classes on graph families with unbounded degree, cleanly delimiting the framework's scope. A specialised, constructive result (Theorem 4 / Theorem 16) gives an explicit $K+1$-path training set and a differentiable, layer-weighted $\ell_1$ regulariser for $K$-step Bellman–Ford, extending Nerem et al. (2025) by replacing their non-differentiable $\ell_0$ penalty. The contribution is genuine and pushes NAR theory beyond expressivity in a way that is meaningfully more general than prior work, and execution of the released code confirms the central empirical story — a marked-source MPNN learns Bellman–Ford and extrapolates from 64 to 1024 nodes, a standard MPNN does not, and the tailored regulariser generalizes best. The main conceptual limitation is that Definition 1 is sufficient but not tight — it converts learnability into cover construction, which is intractable in general — and the constructive Bellman–Ford result carries exponential $K$ dependence in $\eta$ and the edge-weight scale that is never reconciled with the $\eta=0.1$ regime used in the experiments.

Strengths

• Conceptual contribution. Decoupling learnability into (i) a computable Lipschitz certificate on the class, (ii) an approximate-realizability assumption on the target with the same certificate budget, and (iii) finite covering numbers on the input space is a clean framing that separates what the class can express from what a certificate-regularised loss can force. This is the right level of abstraction for size generalization, and it is respected consistently through the paper.
• Coverage of aggregations, including max/min. Extending finite-Lipschitzness to max/min-aggregation MPNNs on Hausdorff hyperspaces unlocks Bellman–Ford, MST-cost, and the DP reductions; the paper is correct that this is the first explicit such result, and it is technically the most novel machinery in the appendix.
• Concrete, differentiable Bellman–Ford result. Theorem 16 identifies an explicit $K+1$-path training set and a differentiable layer-weighted $\ell_1$ regulariser, both of which are stronger than the Nerem et al. (2025) baseline in the specific senses claimed (smaller training set, drop-in gradient-based optimisation). The path-graph construction is elegant.
• Explicit impossibility side. Lemma 6 (unbounded-degree families break the covering-number condition) and Proposition 5 (SSSP and MST need individualization / (1,1)-WL) balance the positive results with clean negative statements, giving the paper a well-scoped map of what MPNNs can and cannot learn algorithmically.
• Core empirical claims hold up under execution. Running the released code confirms the Q1 size-generalization result (relative-MAE flat at ~0.003 from 64 to 1024 nodes), the Q2 expressivity gap (standard MPNN ~0.82-0.97 versus marked-source ~0.003, a ~200x separation), the depth-matching requirement (two layers cannot learn three steps, reproducing Table 9 within a few percent), and the theory-predicted parameter structure (near-zero biases, sparse positive weights, largest weight in the first aggregation FNN). These first-hand reproductions materially raise confidence in the paper's central message.

Weaknesses

• Several algebraic steps in the main learnability proof do not go through as printed. The stated cover radius $r = 6(1+\varepsilon B_{f^*})$ grows with the desired accuracy and target-Lipschitz constant, whereas it should shrink; the certificate-substitution line inverts a small reciprocal into a large quantity; and the pivotal inequality $36(1+\varepsilon B_{f^*}^2)^2 \le 36\varepsilon$ is false for any $\varepsilon<1$ since the left side is $\ge 36$. These look like a consistent numerator/denominator inversion rather than a conceptual flaw — Lemma 10 handles the analogous case correctly — but the core theorem as printed cannot be verified.
• Knapsack example collides with the paper's own edge-weight positivity assumption. The DAG uses edges of weight $-v_i$ so the shortest-path distance equals $-\text{OPT}$, but the edge-weighted-graph definition, the Bellman–Ford instances, and the Lipschitz machinery all require $w_G(e) \ge 0$. As presented the knapsack instance is not covered by the theorems it invokes; a non-negative reformulation would resolve this. The layer count $K=n$ also appears to undercount the sink relaxation by one.
• Theorem 4's guarantee is relative, not additive. Since $x^{(K)}$ is unbounded on large graphs, "additive error $\varepsilon(x^{(K)}+1)$" is effectively a relative bound; the current wording understates that absolute error grows with the true distance.
• The theoretical $\eta$/weight-scale regime is never reconciled with the experiments. Theorem 16 requires a regularization scale of order $10^9$ for the tested $K=2, m=2$, while the experiments use $\eta=0.1$. The successful generalization is therefore evidence about the practical regime, not a validation of the bound, and the main text does not warn the reader.
• The framework is sufficient-but-not-constructive. Definition 1 turns learnability into cover construction, which the paper concedes is intractable except for Bellman–Ford. No sampling-based or heuristic $\varepsilon$-net procedure is offered for the general case, so the general guarantee is largely existential — a genuine conceptual limit of the framing.
• Empirical scope is narrow and lacks a prior-work baseline. All experiments fix weights to Uniform[1,100] with no distribution shift, despite the worst-case OOD framing; and there is no head-to-head against Nerem et al. (2025) or a CLRS-style baseline, despite the paper positioning itself as an improvement over the former.
• Statistical support is thin. All tables use three seeds; in Table 2 the $\ell_2$ standard deviations exceed the means, and the "less stable / slightly worse" claim rests on no stability metric or significance test. The regularized training loss is moreover highly seed-sensitive (an independent run reached 3.97 versus the reported 2.05), so the reported $\pm 0.015$ std understates true run-to-run variability.
• The proposed regulariser is never distinguished from plain $\ell_1$ in the main text. Since $\ell_{\text{reg}}$ is described as "an $\ell_1$-based method," the reader cannot tell what separates it from the plain-$\ell_1$ row; the actual delta (layer-dependent weights $w(k)$) appears only in the appendix.
• Load-bearing metrisation citation is imprecise. The Kantorovich–Rubinstein metrisation of sub-probability measures $M_{\le 1}(\mathcal X)$ is attributed to a result usually stated for probability measures; the bounded-test-function twist that the whole IDM construction rests on needs a sharper reference.
• Accumulated notation and cross-reference slips. The Lemma 75/76 swap in the MST reduction, the backwards contradiction direction in the short SSSP proof, the incomplete approximability definition (missing $B_{\boldsymbol\theta}\le B_{f^*}$ and an unclosed parenthesis), the $\xi^K$ PageRank bound omitting the initial-gap factor, and the "mean and max" attribution that silently drops min — individually minor, they accumulate.

Reproducibility & code

Execution used the released repository and author-provided checkpoints; the Q1/Q2/Q3 training and evaluation code ran without incident, but several headline and appendix experiments required new code or could not be reproduced.

• Headline aggregates reproduce. The Q1 size-generalization result, the Q2 expressivity gap, the depth-matching control (two layers insufficient for three steps, matching Table 9 to within a few percent), the repeated-application four-step result (~0.0014, favorable as claimed), and the theory-predicted parameter structure all reproduce qualitatively and in magnitude from the shipped code and checkpoints.
• Three-layer three-step result fails to reproduce. A freshly trained three-layer MPNN did not converge (training loss ~28.4 versus ~4 for two layers) and produced test scores ~0.83/0.97, roughly 100x worse than the reported 0.0075/0.0155 and indistinguishable from the failed 1-WL baseline. The shipped code hardcodes training to two steps and documents no depth-3 recipe, so this claim is not reproducible from the artifacts as provided.
• Q3 table values diverge even though the ordering holds. The executed sweep reproduces $\ell_{\text{reg}} < \ell_1 < \ell_2$ and the greater $\ell_2$ instability, but per-cell scores decrease monotonically with size rather than staying flat as in Table 2, consistent with single-seed vs three-seed evaluation. The released "$\ell_2$" switch also implements $\sum w^2$ (weight decay), not $\lVert w\rVert_2$.
• Degree-invariance claim cannot be checked. The dataset builder ships only one ER generator (fixed edge probability 0.1); there is no constant-average-degree generator, so the ER-constdeg column and the paired comparison behind "average degree does not affect performance" could not be produced.
• Cora/Citeseer results lack code and rest on a weak metric. There is no citation-network loader or weighting/source protocol; a reconstructed evaluation came out ~8x below the reported values and, tellingly, two-step Bellman–Ford from a single source reaches only ~8 nodes in Cora and ~2 in Citeseer, so the metric is dominated by trivially unreached nodes.
• Reported regularized-loss and peak-weight values are seed-anecdotal. The Q1 training loss (2.05) and peak weight (1.5) were not matched (an independent run gave 3.97 and 0.82); both are dominated by which sparse minimizer SGD reached.
• Figures have no generating code. The convergence figures rely on Gaussian smoothing and a theory-derived gray region with no shipped plotting/orchestration code; no figure or panel could be regenerated.

Recommended Changes

Essential

• Repair the algebra in the main learnability proof. Reconcile the cover radius $r$, the certificate substitution, and the $36(1+\varepsilon B_{f^*}^2)^2 \le 36\varepsilon$ step — the natural fix moves $\varepsilon$ into the denominator so $r$ shrinks with $\varepsilon$, mirroring Lemma 10 — and verify all downstream substitutions.
• Fix the knapsack construction to obey edge-weight positivity. Shift the $-v_i$ weights into a non-negative range (correcting in the readout) or state a signed-weight extension with the corresponding changes to the Lipschitz appendix, and re-count the layers ($n$ vs $n+1$).
• Restate Theorem 4's guarantee as relative (or additive+relative). Replace "additive error $\varepsilon(x^{(K)}+1)$" with an explicitly relative formulation.
• Reconcile theory and experiment on $\eta$ and the weight scale. Add a paragraph noting that $\eta=0.1$ is far below Theorem 16's requirement, and either run near the theoretical scale or demonstrate the F.2 bias-removal path that removes the exponential factor.
• Release the depth-3 training recipe and confirm Table 7's three-layer row. Provide the configuration/hyperparameters that train a converging three-layer model, since the shipped artifacts reproduce ~100x-worse scores indistinguishable from the failed baseline.
• Add a weight-distribution-shift experiment and a Nerem et al. (2025) baseline. Both are needed to substantiate the OOD framing and the claimed improvement over prior work.
• Ship the missing artifacts. In priority order: a constant-degree ER generator (unblocks the degree-invariance claim), a Cora/Citeseer adapter plus weighting/source protocol on a non-degenerate metric (more steps or multiple sources), the plotting/smoothing scripts for the figures, and sweep/aggregation scripts so the tables can be rebuilt.

Suggested

• Report the regularized loss and peak weight over more independent seeds. The $\pm 0.015$ std on a value that shifted from 2.05 to 3.97 across a single seed change reflects seed reuse, not stability.
• Report a stability metric and significance for Q3, given the $\ell_2$ standard deviations exceed their means, and soften the "less stable" language accordingly.
• Anchor $\ell_{\text{reg}}$ vs plain $\ell_1$ in the main text (the layer-weighted $w(k)$ difference), and note in Table 2's caption that the "$\ell_2$" row is squared-$\ell_2$/weight decay.
• Tighten Definition 1 and the approximability statement by stating $B_{\boldsymbol\theta}\le B_{f^*}$, closing the stray parenthesis, and using $d_{\mathcal X}$ consistently.
• Sharpen the Kantorovich–Rubinstein citation to the exact bounded-test-function statement for $M_{\le 1}(\mathcal X)$.
• Foreground the non-constructive nature of the general framework beyond the current Limitations paragraph, and add at least heuristic guidance for cover construction outside Bellman–Ford.
• Fix the accumulated slips: the Lemma 75/76 swap, the backwards contradiction direction in the short SSSP proof, the $\xi^K$ PageRank initial-gap factor, and the "mean and max" phrasing that should read "mean, max, and min."