- 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
- 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.
- 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
- 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.
- 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
- 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?
- 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
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.
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−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 edges of an n-vertex graph of bounded maximum degree leaves components of at most K vertices, the ℓ1 error is linear in K/n, with quadratic dependence on the state count q, plus an edge-deletion error. The Euclidean refinement includes a K/n branch independent of q. This counterintuitive independence concerns Euclidean convexification error, not probe count or neural width. For a task objective that is L-Lipschitz on the convex hull in the chosen metric, multiplying this estimate by L 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 h, a generic pairwise q-state energy can be computed in nqO(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.