Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs

Reply to "Methods And Evaluation Criteria": Thank you for the encouraging comments, and we really appreciate it. We agree that generalization analysis is an important direction, especially for structured problems like LCQPs and MI-LCQPs, and we will highlight it as a key avenue for future work in the revised paper.

While we do not provide a theoretical generalization analysis, we included an empirical study in Section F.4 and Figure 6 (Appendix F), to investigate the generalization performance of GNNs on QP tasks. The results show that as the number of training instances increases, the generalization gap decreases and performance improves. This suggests that GNNs have the potential to generalize to unseen QPs drawn from the same distribution, provided sufficient and appropriately sampled training data.

Reply to "Other Comments Or Suggestions": Thanks for the detailed comments, and we will fix these typos following your suggestions.

Reply to "Questions For Authors": We acknowledge that our proofs use a similar high-level framework to those in Chen et al. (2023a;b). However, we would like to respectfully emphasize that there are several important and non-trivial differences in the technical details. These include:

• We have richer counterexamples for MI-LCQPs (Chen et al. (2023b) only have counterexamples for the feasibility).
• We establish the connection between the expressive power of the WL test and the specific properties of LCQPs and MI-LCQPs. In particular, we have some new analysis handling the quadratic terms in Appendix A that is not directly from Chen et al. (2023a;b), and we show that the GNN approximation theory for feasibility/optimal objective can hold with a weaker assumption than the optimal solution (GNN-analyzability vs GNN-solvability), which is also not covered in Chen et al. (2023b).
• We design the graph representation (sometimes with hyperedges, see Appendix E) to fully encode all elements of these quadratic programs; and we develop theoretical analysis involving hyperedges for QCQPs. Technically, the representation and analysis of hyperedges in Appendix E are significantly different.

To reviewer: Thank you for your insightful comments. Due to the 5000-character limit, our responses must be brief, but we’d be happy to elaborate on any specific points in the next stage of rebuttal.

Reply to "Essential References Not Discussed": Thanks for highlighting this relevant work. We’ll cite and discuss it in the revision. This concurrent study [1] proposes an unrolling-based framework for convex LCQPs with explicit complexity bounds, while our work analyzes GNNs’ expressive power for broader problem classes (including mixed-integer LCQPs) with universal approximation results, though without complexity bounds. The two are complementary.

Reply to Weakness 1: We will include a more detailed comparison with Wu et al. (2024) in the revision.

• Methodologies differ: Wu et al. use a tripartite graph for general QCQPs, while we use a variant of bipartite graph tailored to (MI-)LCQPs.
• Results differ with partial overlap: both cover convex LCQPs, but Wu et al. include quadratic constraints, whereas we handle mixed-integer cases and offer an alternative quadratic constraint approach.

Notably, while Appendix E discusses QCQPs, our method differs structurally: Wu et al. add nodes for quadratic terms, while we use hyperedges, leading to a hypergraph GNN.

Reply to Weakness 2: We agree that analyzing GNN parameter complexity is important. While our current results are non-parametric, we will add a discussion: The algorithm-unrolling paper by Yang et al. [1] provides a way to estimate parameter complexity, as each layer's parameters in [1] are explicitly defined. Moreover, prior work (e.g., [2]) shows that unrolling can be viewed as a structured GNN. These links suggest that one may derive GNN complexity bounds for (MI-)LCQPs from unrolling results.

[2] Li et al. "On the Power of Small-size Graph Neural Networks for Linear Programming." NeurIPS 2024.

Reply to Weakness 3: We'll clarify this in the revision: The graph representation can indeed be extended to polynomial optimization. We suggest modeling terms like $F_{j_1,...,j_k}x_{j_1}\cdots x_{j_k}$ as hyperedges:

• $(w_{j_1},...,w_{j_k})$ for objectives
• $(v_i,w_{j_1},...,w_{j_k})$ for constraints

Our QCQP analysis (Appendix E) shows a concrete example of this idea: hypergraph GNNs can approximate such properties, suggesting potential for broader extension to convex polynomial optimization.

Reply to Question 1: Yes, there are. In QBLIB, 77 out of 96 binary-variable linear constraint QPs are GNN-friendly. Detailed results can be found in the paragraph “Frequency of GNN-friendly instances in practice” and in Table 2 (Page 22). We'll add this statistic to Section 4.3 (Page 7) in the revision.

Reply to Question 2: Compared to standard NNs, GNNs provide some unique theoretical advantages:

• Permutation Invariance/Equivariance

  • In QPs, swapping variable/constraint order should permute solutions accordingly.
  • Standard neural networks lack built-in permutation invariance/equivariance, requiring explicit training on all $O(n!)$ input permutations. In contrast, GNNs inherently maintain this property through their graph-based architecture, automatically handling variable/constraint reordering without additional training.

• Scalability to Varying Sizes

  • In GNNs, the learnable functions ($g$'s and $r$'s) and their parameters are shared across nodes and do not depend on the specific index $i,j$, enabling direct application to new problem sizes without retraining.
  • Standard NNs need fixed input/output dimensions, requiring architectural changes for size variations.

These points were briefly mentioned at Lines 64–67 (left column), and we will expand them in the revision.

Reply to Question 3: While our proofs share a high-level framework with Chen et al. (2023a; b), we highlight several non-trivial technical advances:

1. Enhanced Counter-Examples

   • Chen et al. (2023b) only show feasibility counterexamples
   • We provide richer counterexamples (feasibility, optimal objective, and optimal solution) for MI-LCQPs

2. New Theoretical Connections

   • Connect the expressive power of the WL test to key properties of (MI-)LCQPs.
   • Novel analysis of quadratic terms (Appendix A)
   • Prove GNN approximation under weaker assumptions (GNN-analyzability vs GNN-solvability). Chen et al. (2023b) always assume GNN-solvability.

3. Hypergraph Innovations

   • Develop novel hyperedge representations and analysis for QCQPs (Appendix E)
   • Significant technical differences from Chen et al. (2023a; b) that do not involve hypergraphs.

While our work builds on prior studies, we believe it makes valuable contributions. Given the importance of QPs, a theoretical foundation for GNNs in this setting is both timely and impactful. Our proposed criteria—GNN-analyzable and GNN-solvable—serve as practical tools for assessing datasets and diagnosing issues in MI-LCQP training.

To reviewer: Thank you for your valuable comments. Due to the 5000-character limit, our responses must be brief, but we’d be happy to elaborate on any specific points in the next stage of rebuttal.

Reply to "Experimental Designs Or Analyses": We agree that the training error on the Maros-Mészáros test set is relatively higher compared to synthetic datasets. This is primarily due to its inherent diversity. The 138 quadratic programs are sourced from multiple domains (CUTE library, Brunel Optimization Group, and seven other institutions), making the dataset highly heterogeneous with few instances per application scenario.

This contrasts with prior successful empirical work on learning to solve QPs (Nowak et al., 2017; Wang et al., 2020b, 2021; Qu et al., 2021; Gao et al., 2021; Tan et al., 2024), which typically focus on single domains with more consistent problem structures.

While we recommend practitioners train GNNs on domain-specific instances, our theoretical goal requires validating GNNs' general ability to represent (MI-)LCQPs. Despite the dataset's challenges, we observe consistent improvement in GNN expressivity with increased model capacity (e.g., larger embeddings), mirroring trends in synthetic experiments.

Finally, we note the issue of numerical instability. Unlike synthetic datasets, Maros-Mészáros problems involve coefficients with wide-ranging magnitudes (e.g., from -780600000 to 1, after being converted to one-sided), making training numerically challenging. Despite this, GNNs demonstrate the ability to fit optimal objective values and solutions.

Reply to "Relation To Broader Scientific Literature": While our proofs share a high-level framework with Chen et al. (2023a; b), we highlight several non-trivial technical advances:

1. Enhanced Counter-Examples

   • Chen et al. (2023b) only show feasibility counterexamples
   • We provide richer counterexamples (feasibility, optimal objective, and optimal solution) for MI-LCQPs

2. New Theoretical Connections

   • Connect the expressive power of the WL test to key properties of (MI-)LCQPs
   • Novel analysis of quadratic terms (Appendix A)
   • Prove GNN approximation under weaker assumptions (GNN-analyzability vs GNN-solvability). Chen et al. (2023b) always assume GNN-solvability.

3. Hypergraph Innovations

   • Develop novel hyperedge representations and analysis for QCQPs (Appendix E)
   • Significant technical differences from Chen et al. (2023a; b) that do not involve hypergraphs.

While our work builds on prior studies, we believe it makes valuable contributions. Given the importance of QPs, a theoretical foundation for GNNs in this setting is both timely and impactful. Our proposed criteria—GNN-analyzable/solvable—serve as practical tools for assessing datasets and diagnosing issues in MI-LCQP training.

Additionally, we agree that generalization analysis is crucial, and will highlight this as key future work in the revision.

Reply to Weakness: It is the latter. We will further clarify the convex assumption in the revised manuscript:

1. Page 2 (Contributions): Clarify convexity assumption and nonconvex counterexample
2. Page 4: Rename Section 3 → "Universal approximation for convex LCQPs"
3. Page 5: Add nonconvex LCQP counterexample showing GNN indistinguishability despite different optima.

Consider a convex LCQP $\min~~ \frac{1}{2} \begin{bmatrix}x_1 & x_2\end{bmatrix} \begin{bmatrix}1 & 0 \\\\ 0 & 1\end{bmatrix} \begin{bmatrix}x_1 \\\\ x_2\end{bmatrix}, \quad\text{s.t.}~~ -1\leq x_1,x_2\leq 1,$ and a nonconvex LCQP $\min~~ \frac{1}{2} \begin{bmatrix}x_1 & x_2\end{bmatrix} \begin{bmatrix}0 & 1 \\\\ 1 & 0\end{bmatrix} \begin{bmatrix}x_1 \\\\ x_2\end{bmatrix}, \quad\text{s.t.}~~ -1\leq x_1,x_2\leq 1.$ These two LCQPs are indistinguishable by GNNs, and they have different optimal objective/solution.

Reply to "Other Comments Or Suggestions": We'll fix these typos in the revision.

Reply to "Questions For Authors:" Thank you for this insightful comment. We fully agree that $k$-hop GNNs exhibit stronger separation power than MP-GNNs. In the proof of Prop. 4.2 (Appendix B), we construct MI-LCQP instances with distinct optimal objectives that MP-GNNs cannot distinguish. But 3-hop GNNs can distinguish them. Crucially, when we scale these examples to 10 variables/10 constraints (one graph with 20 connected nodes vs. two 10-node components), 3-hop GNNs fail while 5-hop GNNs succeed, confirming that larger $k$ reduces unsolvable cases. We will include this analysis in the revision.

For QCQPs, Appendix E.1 presents a hypergraph GNN framework, with universal approximation analysis (Theorems E.2–E.4). While (MI-)LCQPs anchor our main narrative, we agree that unifying LCQP/QCQP/higher-order extensions via hypergraph GNNs is a compelling direction for future work, which we will emphasize.

To reviewer: Thank you for your detailed comments! Due to the 5000-character limit, our responses must be brief, but we’d be happy to elaborate further in the next rebuttal stage.

Reply to "Claims And Evidence": We will clearly state the convex assumption in the revision:

1. Page 2 (Contributions): Clarify convexity assumption and nonconvex counterexample
2. Page 4: Rename Section 3 → "Universal approximation for convex LCQPs"
3. Page 5: Add nonconvex LCQP counterexample showing GNN indistinguishability despite different optima.

Consider a convex LCQP $\min~~ \frac{1}{2} \begin{bmatrix}x_1 & x_2\end{bmatrix} \begin{bmatrix}1 & 0 \\\\ 0 & 1\end{bmatrix} \begin{bmatrix}x_1 \\\\ x_2\end{bmatrix}, \quad\text{s.t.}~~ -1\leq x_1,x_2\leq 1,$ and a nonconvex LCQP $\min~~ \frac{1}{2} \begin{bmatrix}x_1 & x_2\end{bmatrix} \begin{bmatrix}0 & 1 \\\\ 1 & 0\end{bmatrix} \begin{bmatrix}x_1 \\\\ x_2\end{bmatrix}, \quad\text{s.t.}~~ -1\leq x_1,x_2\leq 1.$ These two LCQPs are indistinguishable by GNNs, and they have different optimal objective/solution.

Reply to "Theoretical Claims":

(I) We will clarify in our revision that in the GNN-solvable case, GNNs can approximate not only the optimal solution but also the feasibility and the optimal objective, as GNN solvability implies GNN-analyzability (Prop. D.1).

(II) We acknowledge this conclusion is more synthetic, hence its appendix placement. In Section 4.3, we'll clarify:

1. GNN-solvable/analyzable cases dominate under specific distributional assumptions
2. Real-world datasets (e.g., QPlib) may contain GNN-insolvable cases (Appendix D)

Reply to "Experimental Designs Or Analyses":

(I) While (MI)LP and (MI-)LCQP input graphs differ due to $Q$, our GNN architecture can emulate LP/MILP cases by setting $g_l^Q = 0$, making the architectures equivalent when $Q$ is ignored.

(II) We re-measure the solving times in Table 1 and present the average solving times and standard deviations below. While the solving times are different due to changes in hardware environment and system load, the advantage of GNN with large batch sizes is consistent. We will update Table 1 and Fig. 2-4.

(III) We run two more sets of experiments on different random seeds, which decide the problem generation, GNN initialization, and stochastic optimization. The results are consistent. For example, over three experiments of training a GNN with an embedding size of 256 to fit the optimal solutions of 500 LCQP problems, the average relative errors we can achieve are $2.83\times 10^{-3}$, $2.69\times 10^{-3}$ and $2.84\times 10^{-3}$. We will add the full results in the revision.

(IV) We apologize for using the confusing term "validation set" in F.4. The set was never seen during training. Hence, the results in Fig. 4 are the generalization results that you asked for. We will change the terms to avoid confusion.

(V) We performed GNN training on 73 GNN-solvable instances from QPLib that provide the optimal solutions and objectives. We train GNNs of embedding sizes 128, 256, and 512 to fit the objectives and solutions. The training errors we achieved are shown below. GNNs can fit the objective values well and demonstrate the ability to fit solutions. The results show the model capacity improves as the model size increases. We will include the training curves in the revision.

Reply to "Other Comments Or Suggestions": We will revise accordingly.

Reply to "Questions For Authors":

(I) The difficulty hierarchy differs by problem type:

• LCQP: feas (Assump 3.1) < obj (+convexity) < sol (+feasible/bounded)

• MI-LCQP: feas/obj (Assump 4.5 + GNN-analyzable) < sol (+GNN-solvable)

Convexity isn't required for MI-LCQP due to inherent integer non-convexity.

(II) Yes, it is presented at the beginning of our rebuttal.

(III) Theoretically, our GNN architecture (Page 3) achieves 1-WL expressivity when mappings ($g$'s, $r$'s) are injective (Xu et al., 2019), satisfied by our continuous function assumption.

Practically, MLP implementations limit expressivity, but with sufficiently large MLPs, the expressivity can closely approximate that of 1-WL on specific datasets, as Section 5 shows.

(IV) We will correct it.

(V) GNN-solvability requires all variable nodes to be distinguishable (no symmetry), while GNN-analyzability permits some symmetry, and requires that edges with identical node-color pairs must share weights. (For example, if two edges both connect a blue node to a red node, they must have the same weight) This requirement implies WL-equivalent nodes share edge-level properties (see Fig.5).