acceptodds
Under review as a conference paper at ICLR 2027

On Sparse Graph Limits for Neural Combinatorial Optimization

Abstract

Graph neural networks are often trained on small graphs and deployed on larger ones, raising the question of which graph information must be preserved for combinatorial optimization values to transfer across sizes. We establish size-transfer guarantees for normalized graph optimization values using finite collections of energy features. For affine objectives, including MAX-CUT, coloring defect, and independent-set density, differences in task value are controlled by discrepancies in normalized scalar energy probes on all bounded-degree graphs. For general Lipschitz objectives, such as those with balance penalties, an additional representation error appears; this error vanishes on hyperfinite graph families but can remain bounded away from zero on expanders. Thus, at fixed degree bound, state space, Lipschitz constant, and target accuracy, a finite energy representation independent of graph size suffices universally for affine tasks and asymptotically for general Lipschitz tasks on hyperfinite families. These results yield prediction guarantees under explicit conditions on encoder accuracy, readout stability, and representation coverage, together with statistical generalization bounds. Theoretically, we prove Shapley-Folkman bounds with sharp parameter dependence, including a dimension-free regime, and realize the resulting energy features with a fixed-weight message-passing network using random node initialization on bounded-treewidth graphs. Experiments with exact solvers and trained models test the resulting transfer guarantees.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, generalization, size generalization, neural combinatorial optimization, graph limits

Reviews

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

This paper investigates size generalization in combinatorial optimization on bounded-degree graphs, focusing on whether a finite set of scalar ground-state energy features can capture enough information to predict normalized optimization values across graph sizes. The analysis builds on quotient sets from sparse graph limit theory. The main theoretical results establish transfer guarantees for affine objectives, including MAX-CUT, coloring defect, and independent-set density. The authors extend the analysis to general Lipschitz objectives by identifying an additional convexification error and showing that it asymptotically vanishes for hyperfinite graph families. They further examine the limitations of these guarantees through expander-based counterexamples and derive quantitative bounds on the convexification error. A separate construction demonstrates how the relevant energy features can be computed by a fixed-weight MPNN with random initialization on bounded-treewidth graphs. The empirical evaluation includes exact energy-probe computations on synthetic graph families, comparisons against trained GNN baselines, and experiments involving a neural MAX-CUT solver.

Critical strengths
  1. A clear and meaningful distinction between affine and constrained graph optimization objectives.

The paper clarifies what information scalar ground-state energy probes preserve and why this information is sufficient to establish transfer guarantees for affine objectives, but may be insufficient for nonlinear objectives involving balance constraints. The expander-based counterexample makes this limitation particularly clear and concrete.

  1. Substantive quantitative theoretical results.

Beyond qualitative arguments about representation, the paper provides quantitative results, including the convexification bound in Theorem 5, an analysis of its sharpness, and bounds on task-value transfer. Together, these results offer a more precise understanding of when energy-based representations can support size generalization. The fixed-weight MPNN construction also provides a useful connection between the graph-limit theory and graph learning.

Critical weaknesses
  1. A substantial gap remains between the theoretical representation results and their practical relevance to neural combinatorial optimization.

The strongest predictive results rely on 45 exact energy probes computed using specialized dynamic programming algorithms, followed by ridge regression. While these experiments demonstrate that the energy features contain useful information, they do not establish whether the proposed neural encoder can learn or efficiently compute these features.

Theorem 15 provides a representational existence result rather than a guarantee of practical trainability, and the corresponding MPNN construction is not evaluated experimentally. Moreover, the relevant experiments focus on bounded-treewidth graphs, where dynamic programming can already compute the target optimization values directly.

  1. The novelty of the mathematical results relative to existing theory require stronger justification.

The quotient-set framework and the qualitative connection between repeated disjoint unions and convexification have precedents in the graph-limit literature, including Borgs et al. (2018). Shapley–Folkman-type arguments for separable nonconvex problems are also well established.

The paper acknowledges these connections and makes additional contributions through quantitative convexification bounds, sharpness analyses, and neural representation results. Nevertheless, I am not yet convinced that these advances collectively constitute a sufficiently substantial new contribution.

Questions for authors
  1. Practical and computational value of the proposed representation.

The main predictive results rely on exact energy probes computed using specialized solvers. How does the total computational cost of obtaining these probes compare with directly solving the target optimization problems using dynamic programming on the same bounded-treewidth graphs? Is there a setting in which the proposed representation offers a clear computational or learning advantage?

Additionally, the TL;DR states that the energy features can be computed exactly by a fixed-weight GNN, whereas Theorem 15 appears to provide an approximation guarantee rather than exact computation. Could the authors clarify this apparent discrepancy?

  1. Novelty and significance relative to existing theory.

Could the authors clarify which mathematical result they consider the most significant advance beyond what is already established in the quotient-convergence literature and classical Shapley–Folkman theory?

Beyond the finite-size bounds and sharpness analyses, what new guarantees do the results provide for neural graph learning or combinatorial optimization that were not previously available?

2 comments

Thank you for recognizing the affine-versus-constrained distinction and the quantitative results as substantive contributions. We have revised the manuscript to clarify the mathematical advance and computational scope.

W1. Practical relevance and the exact-probe experiments.

The exact-probe experiments address whether the proposed representation retains useful task information across sizes (which is what the theory suggests). Exact evaluation isolates this question from encoder errors.

To address the dependence on exact features, we have analyzed perturbations of the fitted 45-probe readout. On the test set, an error of at most 2×10−42\times10^{-4} in every raw probe coordinate is sufficient to keep mean absolute errors (MAEs) for coloring defect, MAX-CUT density, and independence density below the reported mean GPS–RWSE baseline MAEs. The calculation freezes the readout and training normalization and includes standardization; the sensitivities and certified ceilings appear in revised Appendix C.13 (p. 30, Table 3) and our response to BuCH, Q2. This supplies a conservative sufficient accuracy target for approximate encoders. Achieving it through learning remains an exciting next question: probes are optima over global assignments, so matching local statistics alone does not guarantee accurate energies. Below, Q1 addresses the computational cost.

W2. Novelty relative to quotient convergence and Shapley–Folkman theory.

Our principal technical contribution is Theorem 5, its sharpness analysis, and its Euclidean refinement. The quotient formalism and Shapley–Folkman mechanism are classical. Earlier work contains special disjoint-union examples: a quantitative cycle-union construction in Borgs et al. (2017, Example 5) [1] and a convex-hull limit for repeated regular bipartite components in Borgs et al. (2018, §3.3.7) [2]. Our theorem turns this mechanism into a finite-graph estimate under arbitrary bounded-component decompositions, with separately matching state-count and component-scale examples.

Concretely, when deleting at most εn\varepsilon n edges of an nn-vertex graph of bounded maximum degree leaves components of at most KK vertices, the ℓ1\ell^1 error is linear in K/nK/n, with quadratic dependence on the state count qq, plus an edge-deletion error. The Euclidean refinement includes a K/n\sqrt{K/n} branch independent of qq. This counterintuitive independence concerns Euclidean convexification error, not probe count or neural width. For a task objective that is LL-Lipschitz on the convex hull in the chosen metric, multiplying this estimate by LL bounds the finite-graph task-value error from replacing attainable profiles with their convex hull. Thus a supplied decomposition certifies when unconstrained energies retain sufficient information for that task.

Q1. Computational cost, potential advantage, and exact versus approximate computation.

Given a tree decomposition of width hh, a generic pairwise qq-state energy can be computed in nqO(h)nq^{O(h)} time; separately computing 45 probes requires 45 energy solves, with their state counts. For these few known targets, dynamic programming is the natural option to isolate encoder errors. In a proper supervised learning setup, one may also look at amortizing feature computation across many subsequent tasks, which is outside of the scope of the current paper (which deals mainly with representation theorems).

We also thank the reviewer for point out the overclaim in the TL;DR. The corrected wording for the TL;DR is “approximated to prescribed accuracy by a fixed-weight MPNN with random node initialization on bounded-degree, bounded-treewidth graphs.”.

Q2. What additional guarantees follow for neural graph learning?

We believe that our most significant contribution is the task-dependent characterization: affine task values are controlled by energy discrepancy on all bounded-degree graphs, while general Lipschitz task values incur the quantified convexification error. This holds uniformly across graph sizes, akin to famous regularity lemmas.

In NAR, strong methods such as ANYCSP report 24–48 hours of training per model, while giving general guarantees for learned size transfer remains challenging. We hope to bring some theory to the table by establishing sufficient conditions for a representation to preserve task values across sizes. In spirit, if your method accurately approximates a sufficiently rich bank of energy probes, it retains the information needed to predict normalized values of the affine tasks (and to some extents, Lipschitz tasks) covered by that bank.

References

[1] Borgs, Chayes, and Gamarnik. Convergent Sequences of Sparse Graphs: A Large Deviations Approach. Random Structures & Algorithms, 2017. Example 5.

[2] Borgs, Chayes, Cohn, and Zhao. An Lp Theory of Sparse Graph Convergence II: LD Convergence, Quotients, and Right Convergence. Annals of Probability, 2018. §3.3.7.

The rebuttal clarifies how Theorem 5 extends earlier convexification results and gives a concrete accuracy target for approximating the 45 energy probes. Whether a learned encoder can meet that target at a cost competitive with direct dynamic programming remains open, so I am keeping my rating.

Reviewer_BuCHOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper asks which graph representations can preserve normalized combinatorial optimization values across graphs of different sizes. It represents a graph through its attainable node-state and edge-state statistics and shows that scalar ground-state energies determine the convex hull of these statistics. This representation supports transfer for affine objectives on all bounded-degree graphs. For general Lipschitz objectives, replacing the attainable statistics with their convex hull introduces an error, which vanishes as graph size grows within hyperfinite families.

The main contributions are quantitative bounds, along with examples showing where those bounds are sharp, a randomized message-passing construction with fixed weights for boundedtree width graphs, and a lower bound on the required depth.

Critical strengths
  • supporting quantitative bounds by meaningful sharpness examples: Thm 5 bounds the error introduced by replacing attainable quotient statistics with their convex hull. Remark 7 and Appdix E.2.5 support the separate dependence on state-space size and component size, while equation (48) gives a dimension-independent bound in the Euclidean setting. With Corollary 6 and Prop 8, these results explain when unconstrained energies contain enough information and why they can fail for objectives that depend on balance.

  • explicitly addressing independence from graph size: Lemma 20 and Thm 15 use local rank quantization and bound the fraction of unsuccessful roots. These steps give a concrete argument for graph-order independence beyond an appeal to universality on graphs of bounded size. The construction builds on an existing partition oracle for bounded-treewidth graphs. Thm 16 provides a complementary depth lower bound for the task under clearly stated assumptions about locality, bounded states, and the readout.

Critical weaknesses
  • Guarantees for learned predictors remain conditional: Corollary 14 requires uniformly accurate encoding, a stable readout, and a training set that covers the relevant representations. Thm 15 establishes that an encoder with fixed weights exists, but the experiments obtain their probe features through exact dynamic programs tailored to each graph family. Therefore, they do not evaluate the encoder constructed in the thm. The held-out-family and probe-count studies in Appendix C.12 provide further evidence for the representation, but they do not show that training learns a representation with the required properties. The authors acknowledge this limitation, which still limits what the results establish about size generalization in practice.

  • The interpretation of E9 goes further than the theory supports. Appndix C.13, lines 1579–1583, attributes the remaining MAX-CUT error entirely to optimization. However, Thm 11 concerns optimal task values and the information contained in energy features. It doesn't establish that the particular 4-layer network used to produce solutions can express optimal assignments. Its restricted receptive field could also limit the solutions it can represent. The experiment does not distinguish this possible approximation error from a failure to optimize the network’s parameters.

Questions for authors
  1. What evidence supports attributing E9’s remaining error entirely to optimization? In particular, can the authors distinguish limitations of the chosen network class from a failure to find good parameters within that class? If the current evidence does not allow this distinction, could the interpretation be narrowed accordingly? Clarifying this point would address my main concern about the connection drawn between the representation theorem and the performance of the neural solver.

  2. How sensitive are the reported prediction gains to approximation errors in the energy features? Appendices C.11–C.12 compute the probe energies exactly and fit ridge readouts on standardized features. Could the authors report the readouts’ sensitivity to feature perturbations, including the effect of standardization, and quantify the probe accuracy needed to retain the advantage over the learned baselines in Appendix C.13? This would clarify how demanding the exact-probe results are to reproduce with an approximate neural encoder.

3 comments

Thank you for the thoughtful review. We have expanded experiment E9 with an architectural error bound and controlled depth/training experiments, and quantified the fitted readouts' sensitivity to approximate probes, including standardization. The sensitivity analysis and E9 appear in revised Appendices C.13–C.14 (pp. 30–33).

W1. Guarantees for learned predictors.

Our framework is a representation result that captures the task-specific sufficient information with a single shared encoder. We do not make any claims on the optimization process (such claim is exceedingly rare in the literature and usually comes with very idealized settings). When necessary to test specific parts of our theory (e.g. whether the identified information is indeed sufficient), we obtain these information directly and exactly with dynamic programming in order to not introduce confounding errors. In details: Corollary 14 gives a transfer guarantee for the quotient-set representation conditional on encoder accuracy, readout stability, and coverage of the relevant representations. Theorem 15 supplies a fixed-weight randomized MPNN that approximately computes a finite energy bank on bounded-degree, bounded-treewidth graphs, with weights independent of graph order. Exact dynamic-programming probes isolate whether the representation contains the required information; they test a finite probe bank's predictive value. The MPNN guarantees the prescribed accuracy and confidence for each input graph, using one architecture across graph orders.

To gently emphasize, our principal contribution is a quantitative, task-dependent theory of scalar-energy representations: finite-graph convexification bounds with separately sharp parameter dependences, a dimension-independent Euclidean branch, and graph-order-independent neural realizability. Community interest in these structural questions is reflected in graphon convergence and expressivity [1–4], graphops [5,8], attributed-graph limits [6], and densifying regularity [7] at NeurIPS, ICLR, and ICML.

In the latest revision, to make the conditional guarantee more concrete, Q2 gives a sufficient probe-accuracy threshold on the experimental split. This directly addresses how demanding approximate probes would need to be for the fitted readout. Learning such an encoder uniformly over a graph class remains an exciting open question: small training error alone does not control accuracy on graphs of arbitrarily large order. A learned encoder may use another architecture; for the Q2 certificate, its outputs must approximate the raw energy coordinates within the stated absolute tolerance.

W2. E9 and the source of the remaining MAX-CUT error.

We thank the reviewer in pointing this out. In revised Appendix C.14, we replaced the optimization-only interpretation with an architectural analysis and tested improvements in both depth and training. The value-representation theorem does not establish that a particular network can generate optimal assignments. Our new analysis directly addresses this distinction.

On an even cycle with n≥max⁡{4,4t+2}n\geq\max\{4,4t+2\} vertices, every fixed equivariant depth-tt rule with iid node initialization has expected cut error at least 1/(4t+2)1/(4t+2) per vertex, before rounding. Depth tt means that each output depends only on inputs within tt edges. Sample node labels independently conditional on the predicted probabilities. The endpoint labels of an odd path of length 2t+12t+1 are then independent and identically distributed, so they agree with probability at least 1/2, forcing an uncut edge. For E9's four-layer network, this gives a 1/18 floor on all eleven even test cycles, regardless of training. This directly establishes the architectural limitation raised by the reviewer.

We also constructed an orientation-free local Gaussian filter with exact error 1/(2t+2)1/(2t+2), computed in tt message-passing rounds. At depth 16, its error 1/34 beats the universal depth-4 floor 1/18. Together, the bounds establish the optimal Θ(1/t)\Theta(1/t) error scale among fixed equivariant local rules with iid node initialization on sufficiently long even cycles. Note that the filter is a separate fixed-weight architecture. Below, Q1 tests improvements within the original learned-network family.

Q1. Distinguishing architectural limitations from optimization failure.

We have revised E9 (Appendix C.14) to replace the optimization-only attribution with evidence for architectural limitations and optimization headroom.

We varied depth and updates, retaining width 64, 72 training graphs with at most 30 vertices, and 66 test graphs with 120–360 vertices. Depth counts message-passing layers; updates are full-batch optimizer steps. Error is maximum cut minus the product-Bernoulli expected cut, divided by vertex count. Expected cuts are computed from predicted probabilities under independent node labels. We average equally over graphs and 16 fresh node-initialization draws per graph. Values are mean ± sample standard deviation over three training seeds; lower is better.

DepthUpdatesTest error (mean ± SD)
48000.0951 ± 0.0004
432000.0916 ± 0.0013
168000.0603 ± 0.0025
1632000.0502 ± 0.0007

At fixed depth, more training reduces error by approximately 3.7% at depth 4 and 17% at depth 16, demonstrating optimization headroom. Increasing both depth and training reduces error by 47%. The equal layer-update comparison, 16×800 versus 4×3200, favors depth, although parameter counts and computation differ. W2's floor concerns even cycles; the table averages all test families. Allocating the remaining error requires certifying each model class's best achievable error, a challenging nonconvex problem for further work.

Q2. Sensitivity to approximate energy probes.

Including standardization, absolute error at most 2×10−42\times10^{-4} in every raw probe on every test graph suffices to retain lower mean absolute error (MAE) than the reported GPS–RWSE means for all three tasks. We reproduced the 45-probe ridge experiment with the fitted readouts and training normalization fixed.

Let wkw_k be a fitted coefficient of standardized feature kk, and sks_k its training standard deviation plus 10−1210^{-12}. The raw-energy sensitivity is L=∑k∣wk∣/skL=\sum_k|w_k|/s_k. If every coordinate error is bounded by η\eta, each prediction changes by at most LηL\eta, so test MAE increases by at most that amount. The division by sks_k accounts for standardization, including features with small training variance.

Coloring defect is the minimum monochromatic-edge count under two-state assignments; MAX-CUT and independence are the maximum cut size and independent-set size. All three are divided by vertex count. The certified column is exact-probe MAE plus LηL\eta at η=0.0002\eta=0.0002, rounded upwards. GPS–RWSE is the neural baseline with random-walk structural encodings; its column contains the reported three-seed mean MAE on this split.

TaskExact-probe MAERaw sensitivity LLCertified MAE upper boundReported GPS–RWSE MAE
Coloring defect0.0005222.9440.0011110.0046
MAX-CUT density0.0005382.8130.0011010.0085
Independence density0.00018417.4400.0036730.0039

Thus the observed advantage does not require exact energy evaluation: arbitrary, biased or correlated errors bounded by 0.0002 per raw coordinate preserve lower MAE than the reported baseline means for all three fitted readouts on this test split. Independence density sets the tightest tolerance. This provides a sufficient accuracy target for approximate encoders across all 45 probes. We will feature these experiments prominently in our revisions.

References

[1] Ruiz, Chamon, and Ribeiro. Graphon Neural Networks and the Transferability of Graph Neural Networks. NeurIPS, 2020.

[2] Keriven, Bietti, and Vaiter. Convergence and Stability of Graph Convolutional Networks on Large Random Graphs. NeurIPS, 2020.

[3] Levie. A Graphon-Signal Analysis of Graph Neural Networks. NeurIPS, 2023.

[4] Böker et al. Fine-grained Expressivity of Graph Neural Networks. NeurIPS, 2023.

[5] Le and Jegelka. Limits, Approximation and Size Transferability for GNNs on Sparse Graphs via Graphops. NeurIPS, 2023.

[6] Rauchwerger, Jegelka, and Levie. Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs. ICLR, 2025.

[7] Kouchly et al. Efficient Learning on Large Graphs using a Densifying Regularity Lemma. ICLR, 2026.

[8] Amran, Gilat, and Levie. A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation. ICML, 2026.

Thank you for the rebuttal. The additional material clarifies some of my concerns. Thus, i raise the score into “weak accept”

Reviewer_WZ2tOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies transferability of graph neural networks under sparse graph limits for combinatorial optimization. Specifically, it asks what size-independent information about a bounded-degree graph must be kept so that normalized values of combinatorial optimization problems can be predicted transferred across graph size. For this, the authors use the notion of partition convergence, where the graph is identified with profiles its vertex colorings can produce (i.e., size of each color class and weights between the classes). As the tasks considered (such as max cut, independent set, …) factorize over the set of profiles, the target transfers if the profiles are similar in the suitable metric (under regularity of the task). When the set of profiles is only queried through scalar energy features (i.e., optimal values of linear costs over it), for affine objectives of the profile, transferability can be obtained on all graphs, but for more general Lipschitz objectives additionally the gap between the profile set and its convex hull appears, which can be bounded for hyperfinite graphs but remain constant for expander graphs. In terms of GNN transferability, the authors show generalization bounds and the existence of a MPNN approximating such features on graphs of bounded treewidth, which yields transferability. The paper concludes by performing proof-of-concept experiments on synthetic graph families for exact energies with linear readouts and trained GNNs.

Critical strengths
  • The research question is well-posed and interesting. While the literature of GNN transferability has grown significantly, most of the works have been task-agnostic and dealing with dense graphs, so I feel that since this analysis is more task-dependent and combinatorial optimization is an important use case of GNNs (or often also analyzed for extrapolation/neural algorithmic reasoning), this work is a relevant addition to this line of research.
  • While prior works, e.g. [1,2], developed “representations” on the graph limit (e.g., DIDMs, tree distance) that the entire hypothesis class of GNNs factorize over. In this work, however, the representation comes from the side of the task (i.e., the representation is the coarsest under which the task class is continuous), which is a natural perspective for combinatorial optimization. The mathematical tools used in the paper (albeit not a contribution of this work), such as partition convergence, are adequate and elegant for studying this problem.
  • The paper is mostly open about limitations and, from what I can tell, credits the foundational work on graph limit theory appropriately.
Critical weaknesses
  • While interesting, a lot of the theory is restating and applying existing tools, mostly from [3], and the relation to GNNs seems to be somewhat more of a corollary of the existing theory.
  • I am unsure if any of the GNN transferability bounds can have any quantitative value, but I feel that some of the bounds might be vacuous. For example, cor. 14 assumes that the network outputs energy features and the readout is Lipschitz, which I did not see established for any trained model anywhere, and depth for thm. 15 even at treewidth 2 would need to be of order max_degree^76 * alpha^{-45} (where alpha controls the error, up to the logarithmic factor), so I suspect the bound might already get excessively large for pretty much all nontrivial cases.
  • Similar as in the rest of the GNN transferability literature, “transferability” means here that the normalized target is already close to its limit along the graph sequence so that the larger test graphs are essentially in distribution on the graph limit space, which is different from extrapolation/neural algorithmic reasoning [4,5] where the objective is to learn the algorithm (i.e., the target on the large graph might be different from the small graphs and generalization does not come from the instances of different sizes just looking similar to the model). While, e.g., [5] is cited and shallowly engaged with in l. 131-136, this distinction should be made clearer in the introduction (especially since this work also deals with combinatorial optimization).
  • I feel that the experiments do not convincingly test the theory. E.g., the transfer experiments just use affine targets (for which the gap from the convex hull vanishes), and the considered models should transfer by construction.
  • The main body is very dense and hard to understand, which is partly in the nature of this work but I think in some cases the theory could be made more intuitive and self-contained in the main body. These are just suggestions, but for readers familiar with GNN transferability but perhaps not experts on all aspects of graph limits, it might make sense to briefly discuss the relation between partition convergence and local-global or action convergence. I also feel that the introduction gets technical too quickly. When I first read l. 56-70, I did not really understand the concept of q-quotients/partition convergence (or for a reader that is not familiar with the underlying graph limit literature, it is probably impossible to know what “scalar energy features” are), so I had to skip directly to sec. 2. I might also introduce fig. 2 before fig. 1, as it is more foundational for understanding the basic mathematical objects.

[1] Jan Böker, Ron Levie, Ningyuan Huang, Soledad Villar, Christopher Morris. Fine-grained Expressivity of Graph Neural Networks. NeurIPS 2023.

[2] Levi Rauchwerger, Stefanie Jegelka, Ron Levie. Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs. ICLR 2025.

[3] Christian Borgs, Jennifer Chayes, David Gamarnik. Convergent Sequences of Sparse Graphs: A Large Deviations Approach. Random Structures & Algorithms 2017.

[4] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S. Du, Ken-ichi Kawarabayashi, Stefanie Jegelka. How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks. ICLR 2021.

[5] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, Haggai Maron. From Local Structures to Size Generalization in Graph Neural Networks. ICML 2021.

Questions for authors
  • Is there any reason (theoretical or empirical) why one should expect a trained MPNN to factor through the energies? The way I understand it right now is that this is an assumption that the theory makes / it is only shown that such a network exists.
  • Could you add an experiment where the convexification gap actually matters?
  • Have you analyzed whether any of the bounds are quantitatively predictive?
4 comments

Thank you for identifying the task-dependent perspective as a useful addition to GNN transferability. We have revised the manuscript to clarify the mathematical advance, distinguish realizability from training, and improve presentation as suggested. In more detail:

W1. Novelty beyond existing theory.

We agree that our framework uses the classical partition-convergence formalism studied by Borgs et al. (2017). The convexification proof also uses the classical Shapley–Folkman mechanism. Our principal technical contribution is the general finite-graph bound and its sharpness analysis: we control the cost of taking the convex hull of the quotient set under an arbitrary bounded-component decomposition, with separately sharp state-count and component-scale dependences. The Euclidean bound also has a q-independent branch. This might be of independent interest: in coloring, q is the number of colors, and a bound on Euclidean convexification error independent of that number is peculiar.

Earlier work gives a quantitative cycle-union example [1, Example 5] and a repeated-component convex-hull limit [2, §3.3.7]. These do not give the general quantitative convex theory meant here: a finite-graph error bound that applies once a decomposition is given, together with examples matching the state-count and component-scale dependences separately. This complements the microcanonical approach by the original paper [1] by tying the information loss to the task structure itself. Affine tasks lose no information, while Lipschitz tasks incur the stated error. Q2 tests the latter distinction. Revised Section 1.1 (p. 3) now separates these contributions from the classical tools they use.

W2. How useful are the bounds quantitatively?

Your calculation for Theorem 15 is correct. Its contribution is graph-order-independent realizability: for a fixed probe bank and prescribed accuracy and confidence, one finite architecture with fixed weights achieves the stated approximation guarantee for each graph in a fixed bounded-degree, bounded-treewidth class. The stated depth is a worst-case upper bound from the local partition oracle; we do not claim that its exponents are necessary or that it prescribes a practical network depth. Improving these degree and accuracy dependences remains open.

Classical regularity provides context for such structural guarantees. Szemerédi regularity has unavoidable tower-type partition bounds [3], while Frieze–Kannan weak regularity has worst-case partition size 2Θ(ε−2)2^{\Theta(\varepsilon^{-2})} [4]. These concern partition size, rather than neural depth: they provide context for the structural result, not evidence that our neural bound is numerically tight. A useful depth bound would need a more efficient local construction. Whether regularity methods can yield one is open.

Our main convexification bound is more direct: its finite-size term is linear in K/nK/n in ℓ1\ell^1, with a dimension-independent K/n\sqrt{K/n} branch in ℓ2\ell^2, alongside the edge-deletion error. Here K bounds component size after deletion, and n is graph order. The estimates retain the decomposition's K(ε)K(\varepsilon) cost. This q-free bound does not imply a q-free probe count or neural width, it's simply the rate of convergence. Covering the full quotient-set space introduces a separate statistical cost. Revised Section 5 distinguishes these roles (pp. 8–10) while Q3 below directly compares the convexification rate and constant with experiment E6.

W3. Size transfer versus algorithmic extrapolation.

We agree with this distinction and have stated it in the introduction (pp. 1–2): our transfer guarantee concerns nearby task representations, not learning an algorithm. Note however that even the choice of graph topology (what 'nearby' means exactly) is very contested in non-Euclidean domains. For our result, the relevant point is what each topology preserves. For example, growing bounded-degree graph sequences converge to zero in the graphon cut metric even when their normalized task values differ. The task-side question is therefore which notion of closeness suffices for those values. Our answer uses partition convergence and identifies when scalar energies can replace the full quotient set. This is a representational result within the graph-limit notion of transfer identified by the reviewer.

W4. What do the experiments test?

Q2 below directly addresses the request to test a task where convexification loses information. Recall that even for the affine experiments, sufficiency of all energies does not guarantee that a chosen finite bank and fitted readout achieve low error. They test whether those finite features support prediction across sizes. The nonlinear test then isolates a setting where even all energies cannot determine the value. These are distinct predictions of the theory.

Note also that affineness still covers normalized optimum values of very hard tasks such as fixed-q coloring defect, maximum independent set, and MAX-CUT. As context for the solver-learning problem, ANYCSP uses a recurrent GNN guiding stochastic search on an expanded constraint-value graph. It trains separate task models with 500,000 updates and batches of 25 instances: 12.5 million sampled instances and 24–48 hours per model [5, §§4.1–4.3]. These solvers learn to search for assignments. Our fixed-feature experiments isolate how much task information the probes retain across sizes. Building a learned encoder that retains this information is the next algorithmic step that is outside of the scope of this paper.

W5. Presentation and relation to other graph limits.

We incorporated the specific suggestions: the introduction now explains quotient sets and scalar energies before using them, and the quotient figure precedes the decomposition figure (p. 2). Section 2 (p. 4) explains that quotient statistics retain aggregate colored-neighborhood information and are moments of graphop action observations, essentially a different convergence mode than local–global or action convergence. These changes make the basic objects and their relation to known transferability frameworks explicit.

Q1. Why expect a trained MPNN to encode the energies?

Theorem 15 provides a candidate architecture and proves approximate realizability. We do not claim that ordinary training learns the probes. This is the distinction behind Corollary 14's encoder-accuracy assumption. Furthermore, the proposed energy representation is sufficient, not necessary; a trained network could retain the relevant task information in another form. While it is exciting to think about an optimization theorem, such theory are exceedingly rare in the literature as far as we know.

Q2. A nonlinear test where convexification matters.

We investigated this in E5 and supplemented it with exact enumeration. The revised main paper now highlights this test. Consider the soft balanced-cut task Φ(G)=min⁡(p,W)∈S2(G)(∣p1−1/2∣+W12)\Phi(G)=\min_{(p,W)\in\mathcal S_2(G)}(|p_1-1/2|+W_{12}), where p1p_1 is the fraction of vertices in state 1, W12W_{12} is crossing edges divided by vertex count, and S2(G)\mathcal S_2(G) collects all two-state assignment statistics.

E5 computes this value exactly on twenty random cubic graphs of orders 8,10,12,14, obtaining Φ(G)∈[1/6,1/2]\Phi(G)\in[1/6,1/2]. Each disjoint self-union satisfies Φ(G⊔G)=0\Phi(G\sqcup G)=0, since the copies can receive opposite states. Every normalized unary–pairwise energy agrees on G and G⊔GG\sqcup G, by additivity. Any energy-only predictor therefore has mean absolute error (MAE) at least Φ(G)/2≥1/12\Phi(G)/2\geq1/12 on the equally weighted pair, regardless of training or probe count. Our further exact enumeration of mK4mK_4, for m=1,…,32m=1,\ldots,32, confirms Φ(K4)=1/2\Phi(K_4)=1/2 and Φ(K4⊔K4)=0\Phi(K_4\sqcup K_4)=0, giving an MAE floor of 1/4. This matches the theory: scalar energies determine only the convexified quotient set, which preserves affine optima but can change nonlinear task values. The positive MAE floor on these pairs demonstrates that the resulting information loss cannot be repaired by adding probes or improving training within an energy-only representation.

Q3. Are the bounds quantitatively predictive?

Yes, for the main convexification estimate, E6 checks the predicted convergence rate. Consider Gm=mK4G_m=mK_4, the disjoint union of m copies of K4K_4, with two states, maximum degree D=3D=3, component size K=4K=4, and graph order n=4mn=4m. No edges need deletion. Write κ2,1\kappa_{2,1} for the Hausdorff distance between the full two-state quotient set and its convex hull in the paper's ℓ1\ell^1 metric. Theorem 5 gives κ2,1(Gm)≤24/m\kappa_{2,1}(G_m)\leq24/m, while a direct calculation gives exactly κ2,1(Gm)=7/(2m)\kappa_{2,1}(G_m)=7/(2m). Thus the predicted K/nK/n rate, equivalently n−1n^{-1} for this family, is correct; the general upper bound is conservative by the constant factor 48/7≈6.8648/7\approx6.86.

Here κ^\widehat\kappa is E6's mesh-based estimate of the same full Hausdorff gap; multiplying by m removes the predicted 1/m decay. The exact rescaled gap is 3.5 and the theorem's rescaled upper bound is 24 throughout.

Copies mmVertices nnNumerical mκ^m\widehat\kappaExact mκ2,1m\kappa_{2,1}Theorem 5 upper bound on mκ2,1m\kappa_{2,1}
143.5003.50024
283.5003.50024
4163.5003.50024
8323.4923.50024
16643.4923.50024
321283.4923.50024

The small undershoot for m≥8m\geq8 reflects the mesh missing the maximizer. Revised Appendix C.12, E6 (p. 30), thus checks the fixed-q ℓ1\ell^1 finite-size rate and its conservative constant. It does not test the q-free Euclidean branch, neural depth, or statistical generalization rates. For the trained networks, no matching rate is established; obtaining one needs control of the learned encoder and readout as well as graph convergence. The value of E6 is to test the main bound directly, on a family where the exact gap is known.

References

[1] Borgs, Chayes, and Gamarnik. Convergent Sequences of Sparse Graphs: A Large Deviations Approach. Random Structures & Algorithms, 2017.

[2] Borgs, Chayes, Cohn, and Zhao. An Lp Theory of Sparse Graph Convergence II: LD Convergence, Quotients, and Right Convergence. Annals of Probability, 2018.

[3] Gowers. Lower Bounds of Tower Type for Szemerédi’s Uniformity Lemma. Geometric and Functional Analysis, 1997.

[4] Conlon and Fox. Bounds for Graph Regularity and Removal Lemmas. Geometric and Functional Analysis, 2012.

[5] Tönshoff et al. One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction. IJCAI, 2023.

Thank you very much for the thorough rebuttal! As I think this has strengthened the paper, I will update my score to 3 (weak accept).

Comments on the paper

1 comment

Dear reviewers, the authors responded to your reviews. Could you please go over the responses, see if you have any further questions, and if appropriate, reassess your evaluation of the paper?

Note that the deadline for all reviewer-author discussions is November 18th.

Thanks, AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.