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

We appreciate the reviewer’s encouraging feedback and provide a detailed clarification to address the reviewer’s concerns:

(Previous empirical success of GNNs for QPs). Thank you very much for your suggestion. We kindly refer the reviewer to Sections 1 and 2, which provide a review of previous empirical successes. For your convenience, we have highlighted them both in the revised paper and in this response:

By conceptualizing QP problems as graphs, where all information including coefficients and boundaries are encoded into the graph’s attributes, GNNs can efficiently handle these QP tasks (Nowak et al., 2017; Wang et al., 2020b; 2021; Qu et al., 2021; Gao et al., 2021; Tan et al., 2024; Jung et al., 2022). Such a graph representation is illustrated in Figure 1. This approach leverages key advantages of GNNs: they naturally adapt to varying graph sizes, allowing the same model to be applied to various QP problems, and they are permutation invariant, ensuring consistent outputs regardless of node order.

To the best of our knowledge, this particular representation is only detailed in Jung et al. (2022), yet it forms the foundation or core module for numerous related studies. For instance, removing nodes in V and their associated edges reduces the graph into the assignment graph used in graph matching problems (Nowak et al., 2017; Wang et al., 2020b; 2021; Qu et al., 2021; Gao et al., 2021; Tan et al., 2024). In these cases, the linear constraints $Ax\circ b$ are typically bypassed by applying the Sinkhorn algorithm to ensure that $x$ meets these constraints. Another scenario involves LP and MILP: removing edges associated with $Q$ simplifies the graph to a bipartite structure, which reduces the LCQP to an LP (Chen et al., 2023a; Fan et al., 2023; Liu et al., 2024; Qian et al., 2024). Further, by incorporating an additional node feature, an approach detailed in Section 4, this bipartite graph is also capable of representing MILP (Gasse et al., 2019; Chen et al., 2023b; Nair et al., 2020; Gupta et al., 2020; Shen et al., 2021; Gupta et al., 2022; Khalil et al., 2022; Paulus et al., 2022; Scavuzzo et al., 2022; Liu et al., 2022b; Huang et al., 2023).

If you believe any critical references or examples have been overlooked, we would be happy to include them.

(Size and depth of GNNs). We certainly agree with you that the size and depth of GNNs are crucial in practice and we would like to kindly highlight a result implied by our analysis regarding the depth of GNNs: All our universal approximation results are true for GNNs with $\mathcal{O}(m+n)$ layers, since the WL test has at most $\mathcal{O}(m+n)$ iterations with strict color refinement (as mentioned after Algorithm 1). Regarding the size of GNNs, we believe this is an important topic for future research, and we honestly pointed it out in the updated conclusion section.

We hope these clarifications address your concerns. If you have further questions or require additional clarifications, we would be more than happy to provide them.

We appreciate the reviewer’s thoughtful feedback and provide a detailed clarification to address the reviewer’s concerns:

(Application scenarios for MP-tractable and unfoldable MI-LCQPs). An application scenario for these types of problems is: all the coefficients in the objective function are continuously distributed. With this assumption, we show in Proposition D.3 that MI-LCQPs are unfoldable and MP-tractable with probability 1. This ensures that all theorems presented in our paper can be directly applied. Notably, the dataset used in our experiments, which includes portfolio problems and SVMs, consists entirely of unfoldable and MP-tractable instances. These discussions have been included in Section 4.3 and Appendix D.

(Our contributions beyond the above scenarios). Although in some manually crafted datasets (like the counterexamples presented in our paper), "bad" instances (MP-intractable or foldable) may cause GNNs to fail, our theoretical results still offer practical insights. The two proposed criteria, MP-tractability and unfoldability, are both computationally efficient to verify, with a polynomial complexity detailed in Section 4.3. Practitioners can use these criteria to evaluate their datasets before applying GNNs. Alternatively, if difficulties arise during GNN training on MI-LCQPs, checking for MP-tractability and unfoldability may help identify the issue. Although GNNs have been widely applied to QP tasks (e.g., Nowak et al., 2017; Wang et al., 2020b, 2021; Qu et al., 2021; Gao et al., 2021; Tan et al., 2024; Jung et al., 2022), there remains a significant lack of theoretical studies. Our findings explicitly clarify what GNNs can and cannot do for QP tasks, provide insights and theoretical guidance in this domain.

(Assumptions regarding unique optimal solutions). We would like to kindly argue that we do NOT need uniqueness of optimal solutions. For continuous LCQP, we allow multiple optimal solutions, and we show that GNNs can approximate the optimal solution with the smallest $\ell_2$ norm (Definition 2.3). For MI-LCQP, we also allow multiple optimal solutions, and define a total ordering on the optimal solution set, and show that GNNs can approximate the minimal element in the optimal solution set. Discussions have been included in Appendix C.

We hope these clarifications address your concerns. If you have further questions or require additional clarifications, we would be more than happy to provide them. We greatly appreciate it if you could update your evaluation should you find these responses satisfactory.

Dear Reviewer fJ5r,

Thank you for your insightful comments and constructive feedback. We have carefully reviewed and addressed each of your concerns in our detailed responses.

Given the impending rebuttal deadline, we kindly request your review of our responses to ensure that all issues have been addressed satisfactorily. Should you require further clarification or additional details, we would be happy to provide any necessary explanations.

We truly appreciate your time and effort in reviewing our work.

Best regards.

We appreciate the reviewer’s thoughtful feedback and provide a detailed clarification to address the reviewer’s concerns:

(MP-tractability and Unfoldability: Addressing Weakness 1 and Question 1). We kindly refer the reviewer to Section 4.3, where we provide practical insights regarding MP-tractability and unfoldability. Below is a summary of the key points, along with some addtional discussions during this rebuttal:

• (Occurance of MP-tractability and unfoldability). In practice, the frequency of MP-tractable and unfoldable instances largely depends on the dataset, particularly the level of symmetry in the data. When there is symmetry in MI-LCQP, it becomes foldable; and higher symmetry increases the risk of being MP-intractable. Fortunately, unfoldable and MP-tractable instances make up the majority of the MI-LCQP set (shown in Appendix D). The dataset used in our experiments, which includes synthetic MI-LCQPs, portfolio problems, and SVMs, consists entirely of unfoldable and MP-tractable instances. However, it's important to note that in some challenging, artificially created datasets like MIPLIB 2017 (Gleixner et al., 2021), about 1/4 of the examples exhibit significant symmetry in half of the variables.
• (Impact of symmetry on the use of GNNs). When a dataset contains a significant proportion of “bad” instances (MP-intractable or foldable), achieving high training accuracy becomes impossible, as discussed in Section 4.1. Regardless of their size, GNNs cannot distinguish two distinct MI-LCQPs as symmetry makes them indistinguishable. As a result, a GNN that performs well on one such instance will inevitably fail on the other.
• (Our contributions and practical insights). Our theoretical results provide practical insights, as the two proposed criteria, MP-tractability and unfoldability, are both efficient to verify with a polynomial complexity detailed in Section 4.3. Practitioners can use these criteria to evaluate their datasets before applying GNNs. Alternatively, if difficulties arise during GNN training on MI-LCQPs, checking for MP-tractability and unfoldability may help identify the issue. Although GNNs have been widely applied to QP tasks (e.g., Nowak et al., 2017; Wang et al., 2020b, 2021; Qu et al., 2021; Gao et al., 2021; Tan et al., 2024; Jung et al., 2022), there remains a significant lack of theoretical studies. Our findings explicitly clarify what GNNs can and cannot do for QP tasks, and provide theoretical insights in this domain.
• (How to handle bad instances?). As we discussed, bad instances typically exhibit strong symmetry. To fix this issue, there are two potential approaches: (I) Adding Additional Features: Incorporating additional features, such as random features, can help differentiate nodes in a symmetric graph. For instance, if two nodes have identical features, adding a random feature ensures they are no longer identical (and thus not symmetric). Such techniques have been explored in the GNN literature for various graph tasks [R1] (II) Using Higher-order GNNs: Higher-order GNNs can separate nodes that standard message-passing GNNs consider identical, thereby enhancing the expressive power of the model [R2]. Addressing symmetric graph data remains an active and important area in the GNN community, making this a promising direction for future research on MI-LCQPs. We have included the above discussion in our revision to highlight this point. (Section 4.3)

(Other Assumptions: Addressing Weakness 2 and Question 2). We respectfully argue that all the assumptions mentioned by the reviewer are reasonable and align with common practices in the QP and GNN communities. Below are the details for each assumption:

• (Symmetry of Q). This assumption is standard in QP studies, as any QP can be equivalently transformed into another QP with a symmetric Q. For example,

(Illustration of the WL test: Addressing Question 5). We kindly refer the reviewer to Appendix D.1 (Figure 5), where we provide an illustration of the WL test. In this section, we include a small example to demonstrate the process of the WL test and how the node colors are updated. Due to the limitation of pages, it may be challenging to incorporate this content into the main text, we have added a pointer to this example in title of Algorithm 1 for the readers' convenience. Please see our revised paper for details.

We hope these clarifications address your concerns. If you have further questions or require additional clarifications, we would be more than happy to provide them. We greatly appreciate it if you could update your evaluation should you find these responses satisfactory.

References added in rebuttal

[R1] Sato et al. "Random features strengthen graph neural networks." Proceedings of the 2021 SIAM international conference on data mining (SDM). 2021.

[R2] Morris, et al. "Weisfeiler and leman go neural: Higher-order graph neural networks." Proceedings of the AAAI conference on artificial intelligence. 2019.

[R3] Veličković, et al. "Graph attention networks." arXiv preprint arXiv:1710.10903. 2017.

[R4] Schwan R, Jiang Y, Kuhn D, Jones CN. PIQP: A Proximal Interior-Point Quadratic Programming Solver. In2023 62nd IEEE Conference on Decision and Control (CDC) 2023 Dec 13 (pp. 1088-1093). IEEE.

[R5] https://github.com/qpsolvers/maros_meszaros_qpbenchmark/

Dear Reviewer LrCY,

Thank you for your insightful comments and constructive feedback. We have carefully reviewed and addressed each of your concerns in our detailed responses.

Given the impending rebuttal deadline, we kindly request your review of our responses to ensure that all issues have been addressed satisfactorily. Should you require further clarification or additional details, we would be happy to provide any necessary explanations.

We truly appreciate your time and effort in reviewing our work.

Best regards.

We appreciate the reviewer’s thoughtful feedback and provide a detailed clarification to address the reviewer’s concerns:

(Novelty regarding continuous LCQP). While our work draws some inspiration from (Chen et al., 2023a), there are substantial differences in conclusions regarding LPs and QPs. Consider the following two LPs:

$\min \sum_{j=1}^6 x_j ~~ \textup{s.t.}~ x_1 + x_2 = 2,x_2 + x_3 = 2,x_3 + x_4 = 2,x_4 + x_5 = 2,x_5 + x_6 = 2,x_6 + x_1 = 2$

and

$\min \sum_{j=1}^6 x_j ~~ \textup{s.t.}~ x_1 + x_2 = 2,x_2 + x_3 = 2,x_3 + x_1 = 2,x_4 + x_5 = 2,x_5 + x_6 = 2,x_6 + x_4 = 2$

Both of them share a common optimal solution $(1,1,1,1,1,1)$, and hence the two LPs share a common optimal objective value $6$. However, by adding the same quadratic term, their optimal solution and optimal objective varies. Specifically, let's consider the two QPs:

$\min \sum_{j=1}^6 x_j + {\color{blue}{x_1^2}} ~~ \textup{s.t.}~ x_1 + x_2 = 2,x_2 + x_3 = 2,x_3 + x_4 = 2,x_4 + x_5 = 2,x_5 + x_6 = 2,x_6 + x_1 = 2$

and

$\min \sum_{j=1}^6 x_j + {\color{blue}{x_1^2}} ~~ \textup{s.t.}~ x_1 + x_2 = 2,x_2 + x_3 = 2,x_3 + x_1 = 2,x_4 + x_5 = 2,x_5 + x_6 = 2,x_6 + x_4 = 2$

For the first QP, the optimal solution changes to $(0, 2, 0, 2, 0, 2)$ with an optimal objective value of $6$. In contrast, the second QP retains $(1, 1, 1, 1, 1, 1)$ as the optimal solution, but its objective value increases to $7$. This demonstrates that conclusions regarding optimal objectives and solutions for LPs cannot be directly extended to LCQPs.

Our findings show that GNNs can effectively capture such differences. Notably, while Theorem 3.2 (on feasibility) can be directly adapted from LP results, Theorems 3.3 and 3.4, which address the objective and solution, introduce significant novel contributions. The new techniques are mainly in the proofs of Lemma Lemma A.4 and Theorem A.2.

(Novelty regarding mixed-integer LCQP). We acknowledge that the concept of unfoldable MI-LCQP is inspired by the definition of MILPs in (Chen et al., 2023b). However, we introduce several novel contributions in this paper:

• (MP-tractability). In Theorems 4.6 and 4.7, we use a new concept named MP-tractability instead of unfoldability in (Chen et al., 2023b). MP-tractability is a weaker assumption than unfoldability: while all unfoldable MI-LCQPs are MP-tractable (as rigorously proved in Appendix D), not all MP-tractable problems are unfoldable. This difference can be clearly illustrated with an example that is MP-tractable but not unfoldable:

(Novely regarding QCQPs: Added in rebuttal). To add more nontrivial theoretical contributions, we extended our techniques and proved that GNNs can universally approximate the properties of quadratically constrained quadratic programs (QCQPs), which requires hyperedges and is significantly different from (Chen et al., 2023a; Chen et al., 2023b). More specifically, we add hyperedges in encode the quadratic terms in the constriants and the GNN architecture involving edge features is proved with sufficiently strong separation power for QCQPs. In comparison, GNNs in (Chen et al., 2023a; Chen et al., 2023b) only use vertex features. Please check Appendix E of our revision.

(Empirical Validation). To address this concern, we train GNNs on the Maros and Meszaros Convex Quadratic Programming Test Problem Set, which contains 138 quadratic programs that are designed to be challenging. We apply equilibrium scaling to each problem and also scale the objective function so that the $Q$ matrix will not contain too large elements. We collecte the optimal solutions and objective values of the test instances using an open-sourced QP sovler called PIQP [R1], which is benchmarked to achieve best performances on the Maros Meszaros test set among many other solvers [R2]. PIQP solves 136 problem instances successfully, which are then used to train four GNNs with with embedding size of $64,128,256,512$.

The results are included in the updated draft in Appendix F.5. We observe that while the broad range of numbers of instances in the Maros Meszaros test set caused numerical difficulties for training, GNNs can still be trained to fit the objectives and solutions. And we can observe similar tendency as in the synthesized experiments that the expressive power increases as the model capacity enlarges when we increase the embedding size.

(Handwaving Claims in Proofs). We have updated our appendix for the sake of completeness and highlighted the modifications, please kindly refer to our revision.

We hope these clarifications address your concerns. If you have further questions or require additional clarifications, we would be more than happy to provide them. We greatly appreciate it if you could update your evaluation should you find these responses satisfactory.

References added in rebuttal

[R1] Schwan R, Jiang Y, Kuhn D, Jones CN. PIQP: A Proximal Interior-Point Quadratic Programming Solver. In2023 62nd IEEE Conference on Decision and Control (CDC) 2023 Dec 13 (pp. 1088-1093). IEEE.

[R2] https://github.com/qpsolvers/maros_meszaros_qpbenchmark/

Dear Reviewer y6ua,

Thank you for your insightful comments and constructive feedback. We have carefully reviewed and addressed each of your concerns in our detailed responses.

Given the impending rebuttal deadline, we kindly request your review of our responses to ensure that all issues have been addressed satisfactorily. Should you require further clarification or additional details, we would be happy to provide any necessary explanations.

We truly appreciate your time and effort in reviewing our work.

Best regards.

Thanks for the response. I still have some concerns.

1. Novelty of continuous LCQP. In Section (Novelty regarding continuous LCQP), the authors mention that 'The new techniques are mainly in the proofs of Lemma A.4 and Theorem A.2.'
   Based on my reading of the paper, I think: a) The proof framework for continuous LCQP is very much the same as before, with the only difference being Lemma A.4 (half page proof). b) Lemma A.4 and Thm A.2 are new, but relatively straightforward. Lemma A.4 and Thm A.2 primarily address the non-linearity introduced by LCQP. Previously, linearity ensures re-assgining values of coordinates of an optimal solution will keep the objective value. For the current problem, the convexity (ensured by positive semidefiniteness of the quadratic terms) ensures that the re-assigining will not increase the objective value. This modification seems to be relatively straightforward.

2. Novelty of mixed-integer LCQP. In Subsection MP-tractability in Section Novelty regarding mixed-integer LCQP, the aurthors wrote that "In Theorems 4.6 and 4.7, we use a new concept named MP-tractability instead of unfoldability in (Chen et al., 2023b).” However, the concept of MP-tractability was introduced in an earlier work [1] for MILP. The discussion on the relationship between unfoldable and MP-tractable has also appeared in [1]. Thus, it seems that the contribution of the current paper is to apply MP-tractability to MI-LCQP. The adaptation is relatively straightforward.

Overall, I still think the significant overlap with Chen et al. (2023a), and the relation with [1] shows the lack of sufficient novelty.

Reference:
[1] Chen, Ziang, et al. "Rethinking the capacity of graph neural networks for branching strategy." arXiv preprint arXiv:2402.07099 (2024).

Thank you very much for your reply and for your comments. The reviewer's concern primarily focuses on the contributions of our paper. Let us address this by considering the following questions:

• Is QP important? Yes, QP is a fundamental problem with extensive applications in operations research, finance, scientific computing, and more. Advancing our understanding of QPs and their interaction with GNNs is both impactful and relevant to the research community.
• Do the previous results on LP (or MILP) directly imply results on QP? No. LP is a special case of QP, so while results for QP can imply results for LP, the reverse is not true. This distinction, combined with the significance of QP, highlights the necessity of the results and conclusions presented in our paper.
• Does our work deliver useful insights to the community? Yes, our paper offers clear guidance to practitioners, particularly in understanding what GNNs can and cannot achieve for QP tasks.

Therefore, we believe our findings are meaningful and merit publication.

Regarding connections to prior works, we have already addressed them transparently and will further clarify them in our revision:

• Chen et al. (2023a): All conclusions and lemmas directly used from this paper have been clearly acknowledged in the main text and the appendix.
• [1]: In our revision, we will explicitly clarify that the criteria in our paper extend the concept introduced in [1], with the key difference being the additional requirements on the matrix $Q$, which reflect the unique properties of QPs.

We appreciate the reviewer’s thoughtful feedback and provide a detailed clarification to address the reviewer’s concerns:

(MP-tractable Class). We kindly refer the reviewer to Section 4.3, where we provide practical insights and discuss the complexity of verifying MP-tractability. Below is a summary of the key points:

• (Verifying MP-tractability). In practice, both MP-tractability can be efficiently verified by applying the WL test (Algorithm 1), which requires at most $\mathcal{O}(m+n)$ iterations. The complexity of each iteration is bounded by the number of edges in the graph, which, in our context, is the number of nonzeros in matrices $A$ and $Q$: $\text{nnz}(A)+\text{nnz}(Q)$. Therefore, the overall complexity of Algorithm 1 is $\mathcal{O}((m+n)\cdot (\text{nnz}(A)+\text{nnz}(Q)))$. After running Algorithm 1, MP-tractability can be directly verified using Definition 4.4. It is worth noting that although MI-LCQP is generally NP-hard, verifying MP-tractability is significantly simpler than solving the MI-LCQP itself.
• (Frequency of MP-tractable instances). In practice, the occurrence of MP-tractable instances largely depends on the dataset, particularly the level of symmetry (regarding symmetry, we provide definition and examples in Section 4.3) within the MI-LCQPs: higher symmetry increases the risk of being MP-intractable. Fortunately, MP-tractable instances make up the majority of the MI-LCQP set (shown in Appendix D). The dataset used in our experiments, which includes synthetic MI-LCQPs, portfolio problems, and SVMs, consists entirely of MP-tractable instances, so that the theorems in our paper can be directly validated. However, it's important to note that in some challenging, artificially created datasets like MIPLIB 2017 (Gleixner et al., 2021), about 1/4 of the examples exhibit significant symmetry.

(Potentially Shortening Presentation). Yes, there is a clear difference between the second part of Theorem 3.3 and Theorem 3.4, which lies in the output layer of the GNNs. In Theorem 3.3, The GNN produces a graph-level output (i.e., a single real number for the entire graph). Accordingly, the GNN is selected from ${\mathcal{F}}\_\mathrm{LCQP}$. In contrast, in Theorem 3.4, The GNN produces a node-level output (i.e., a real number for each node). In this case, the GNN is selected from the space $\mathcal{F}^W_{\mathrm{LCQP}}$. Relevant definitions can be found at the beginning of Page 4 and in Definition 2.2. This distinction similarly applies to Theorems 4.7 and 4.9.

(Handwaving Claims in Proofs). We have updated our appendix for the sake of completeness and highlighted the modifications, please kindly refer to our revision.

(Proof of Separation Powers). Theorems A.2 and A.3 in Appendix A establish the separation properties referenced on Page 5. In these theorems, we use the notation $G_{\mathrm{LCQP}} \sim \hat{G}\_{\mathrm{LCQP}}$ to indicate that $G_{\mathrm{LCQP}}$ and $\hat{G}_{\mathrm{LCQP}}$ are indistinguishable by the WL test (and, equivalently, by any GNNs). We have updated our draft to further clarify the connection between the discussions on Page 5 and the results in Appendix A.

We hope these clarifications address your concerns. If you have further questions or require additional clarifications, we would be more than happy to provide them. We greatly appreciate it if you could update your evaluation should you find these responses satisfactory.

Dear Reviewer aVvJ,

Thank you for your insightful comments and constructive feedback. We have carefully reviewed and addressed each of your concerns in our detailed responses.

Given the impending rebuttal deadline, we kindly request your review of our responses to ensure that all issues have been addressed satisfactorily. Should you require further clarification or additional details, we would be happy to provide any necessary explanations.

We truly appreciate your time and effort in reviewing our work.

Best regards.

We appreciate the reviewer’s thoughtful feedback, particularly regarding concerns about the novelty of our work. Below, we provide a detailed clarification of our contributions to address these concerns:

(Continuous LCQP). While our work draws some inspiration from (Chen et al., 2023a), there are substantial differences in conclusions regarding LPs and QPs. Consider the following two LPs:

$\min \sum_{j=1}^6 x_j ~~ \textup{s.t.}~ x_1 + x_2 = 2,x_2 + x_3 = 2,x_3 + x_4 = 2,x_4 + x_5 = 2,x_5 + x_6 = 2,x_6 + x_1 = 2$

and

$\min \sum_{j=1}^6 x_j ~~ \textup{s.t.}~ x_1 + x_2 = 2,x_2 + x_3 = 2,x_3 + x_1 = 2,x_4 + x_5 = 2,x_5 + x_6 = 2,x_6 + x_4 = 2$

Both of them share a common optimal solution $(1,1,1,1,1,1)$, and hence the two LPs share a common optimal objective value $6$. However, by adding the same quadratic term, their optimal solution and optimal objective varies. Specifically, let's consider the two QPs:

$\min \sum_{j=1}^6 x_j + {\color{blue}{x_1^2}} ~~ \textup{s.t.}~ x_1 + x_2 = 2,x_2 + x_3 = 2,x_3 + x_4 = 2,x_4 + x_5 = 2,x_5 + x_6 = 2,x_6 + x_1 = 2$

and

$\min \sum_{j=1}^6 x_j + {\color{blue}{x_1^2}} ~~ \textup{s.t.}~ x_1 + x_2 = 2,x_2 + x_3 = 2,x_3 + x_1 = 2,x_4 + x_5 = 2,x_5 + x_6 = 2,x_6 + x_4 = 2$

For the first QP, the optimal solution changes to $(0, 2, 0, 2, 0, 2)$ with an optimal objective value of $6$. In contrast, the second QP retains $(1, 1, 1, 1, 1, 1)$ as the optimal solution, but its objective value increases to $7$. This demonstrates that conclusions regarding optimal objectives and solutions for LPs cannot be directly extended to LCQPs.

Our findings show that GNNs can effectively capture such differences. Notably, while Theorem 3.2 (on feasibility) can be directly adapted from LP results, Theorems 3.3 and 3.4, which address the objective and solution, introduce significant novel contributions. The new techniques are mainly in the proofs of Lemma Lemma A.4 and Theorem A.2.

(Mixed-integer LCQP). We acknowledge that the concept of unfoldable MI-LCQP is inspired by the definition of MILPs in (Chen et al., 2023b). However, we introduce several novel contributions in this paper:

• (MP-tractability). In Theorems 4.6 and 4.7, we use a new concept named MP-tractability instead of unfoldability in (Chen et al., 2023b). MP-tractability is a weaker assumption than unfoldability: while all unfoldable MI-LCQPs are MP-tractable (as rigorously proved in Appendix D), not all MP-tractable problems are unfoldable. This difference can be clearly illustrated with an example that is MP-tractable but not unfoldable:

(QCQPs: Added in rebuttal). To add more nontrivial theoretical contributions, we extended our techniques and proved that GNNs can universally approximate the properties of quadratically constrained quadratic programs (QCQPs), which is significantly different from (Chen et al., 2023a; Chen et al., 2023b). More specifically, we add hyperedges to encode the quadratic terms in the constriants and the GNN architecture involving edge features is proved with sufficiently strong separation power for QCQPs. In comparison, GNNs in (Chen et al., 2023a; Chen et al., 2023b) only use vertex features. Please check Appendix E of our revision.

We hope these clarifications address your concerns. If you have further questions or require additional clarifications, we would be more than happy to provide them. We greatly appreciate it if you could update your evaluation should you find these responses satisfactory.

Dear Reviewer n1f6,

Thank you for your insightful comments and constructive feedback. We have carefully reviewed and addressed each of your concerns in our detailed responses.

Given the impending rebuttal deadline, we kindly request your review of our responses to ensure that all issues have been addressed satisfactorily. Should you require further clarification or additional details, we would be happy to provide any necessary explanations.

We truly appreciate your time and effort in reviewing our work.

Best regards.

Thank you to the authors for providing a detailed reply. However, I find that some of my concerns remain unaddressed:

Theoretical Framework: My concern is not about the difference between LP and QP but rather about the theoretical framework used in the paper. Specifically, the approach appears to be a direct extension of the framework used by Chen et al. (2023a) for LPs. I repeat my earlier comment here:

“… the authors leverage the Stone-Weierstrass theorem to establish the GNN's approximation capabilities based on their separation capabilities. This approach appears identical to that used by Chen et al. (2023a) for LPs. In particular, the proof ideas of Theorems 3.3 and 3.4 (illustrated on Page 5) seem directly translatable to LPs, with minimal modification (i.e., replacing LCQPs with LPs)…”

Broader Class of MP-Tractable Problems: I understand that all unfoldable MI-LCQPs are MP-tractable, but not vice versa. However, it has been proved that MI-LCQPs are unfoldable almost surely under some mild conditions. What are the significance and importance of identifying the broader class of MP-tractable?

Extension to QCQP: I appreciate the authors’ effort to add an extension to QCQP in the appendix. However, I have concerns regarding the timing and relevance of this additional contribution for the following reasons:

1. The conclusion that "GNNs can universally represent convex QCQP" overlaps significantly with another ICLR submission (link). Given that all ICLR submissions are publicly accessible during the rebuttal period, I encourage the authors to explicitly elaborate on how their newly added content differs from the existing submission. (Please correct me if I am misunderstanding the principles regarding overlap and independence.)
2. While the original submission focuses on LCQP, the extension to QCQP feels like a late addition that is not well integrated into the main narrative of the paper. To incorporate this result, the authors have made significant modifications to the graph representation and corresponding GNN formulation. These changes do not seem like a natural extension of the LCQP framework but rather a distinct and separate development.

Thank you very much for your reply and for your comments. Please find our point-to-point response below.

Extension to QCQP (1): Thanks for pointing out this concurrent paper. The main difference between their work and ours is the structure of the graph representation. In their paper, QCQPs are represented as a tripartite graph (with three groups of nodes representing variables, constraints, and quadratic terms), whereas our approach retains a bipartite structure with additional hyperedges representing coefficients of quadratic terms. These two approaches are significantly different and they are developed independently.

Here we do not intend to evaluate which approach is better, especially given the limited time remaining before the rebuttal deadline. However, we believe that comparing these two methods would be an interesting direction for future research. In our revision, we will explicitly highlight this concurrent paper and clarify the key differences.

Extension to QCQP (2): Despite that our results/analysis are different for LCQPs and QCQPs, they are closely related. Specifically, the QCQP-graph is obtained by adding additional hyperedges in the LCQP-graph, rather than developing an entirely new architecture from scratch. We will clearly highlight this connection in our revision. Therefore, we believe that our QCQP results are suitable to be included in our current paper as an extension.

Broader Class of MP-Tractable Problems: In our paper (Appendix D), we prove that MI-LCQPs are almost surely unfoldable under the assumption that the linear objective coefficients $c \in \mathbb{R}^n$ are continuously distributed. However, in practice, particularly with manually designed instances (as opposed to randomly generated ones), foldability does occur, as discussed in Section 4.3. To further address the reviewer's concern, we performed additional experiments on QPLIB (https://qplib.zib.de/). In this dataset, 19 out of 96 binary-variable linear constraint instances are foldable. Furthermore, when coefficients are quantized (which increases the level of symmetry in the dataset), the ratio of foldable instances increases. (shown in the table below)

Quantization refers to rounding continuous or high-precision values to discrete levels. For example, rounding coefficients of QP instances to the nearest integer reduces precision but can simplify analysis and potentially uncover additional properties. In our study, we examine foldable instances at different quantization step sizes (0.1, 0.5, and 1) to explore their tractability.

While foldable instances are generally challenging for GNNs, a significant proportion of these hard instances are MP-tractable. For example, with a quantization step size of 1 (rounding coefficients to integers), 36 out of 63 foldable instances are MP-tractable. According to our theorems, GNNs can at least predict feasibility and boundedness (objective value) for such instances. Detailed results are as follows:

The results clearly show the significance of identifying the broader class of MP-tractable, we will add the results to our revision.

Theoretical Framework: We agree with you that our analysis for LCQPs is generalized from Chen et al. (2023a) for LPs. We believe that introducing such analysis and results to the QP community is a valid contribution and is meaningful, regardless of technical difficulty, as QP is an important family of nonlinear optimization with numerous real-world applications and GNNs are widely applied for solving QPs. Additionally, we have other technical contributions such as richer counter-examples for MI-LCQPs and the analysis for QCQPs.