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

Authors: Ziang Chen, Xiaohan Chen, Jialin Liu, Xinshang Wang, Wotao Yin
Primary area: learning on graphs and other geometries & topologies
Keywords: Quadratic programs, mixed-integer quadratic programs, graph neural networks, universal approximation

Abstract:
Quadratic programming (QP) is the most widely applied category of problems in nonlinear programming. Many applications require real-time/fast solutions, though not necessarily with high precision. Existing methods either involve matrix decomposition or use the preconditioned conjugate gradient method. For relatively large instances, these methods cannot achieve the real-time requirement unless there is an effective preconditioner. Recently, graph neural networks (GNNs) opened new possibilities for QP. Some promising empirical studies of applying GNNs for QP tasks show that GNNs can capture key characteristics of an optimization instance and provide adaptive guidance accordingly to crucial configurations during the solving process, or directly provide an approximate solution. Despite notable empirical observations, theoretical foundations are still lacking.

In this work, we investigate the expressive or representative power of GNNs, a crucial aspect of neural network theory, specifically in the context of QP tasks, with both continuous and mixed-integer settings. We prove the existence of message-passing GNNs that can reliably represent key properties of quadratic programs, including feasibility, optimal objective value, and optimal solution. Our theory is validated by numerical results.

Decision: reject
Reviewer scores: 5, 3, 6, 6, 6, 8

Reviews and discussion:
<thread>
creation date:
1730079390430

thread_type:
official_review

<thread_object>
creator: reviewer_cx5b

<content>
summary:
The paper investigates the expressive power of Graph Neural Networks (GNNs) for solving linearly constrained quadratic programming (LCQP) and its mixed-integer variant (MI-LCQP). The authors focus on a key question: Do GNNs possess sufficient expressive power to predict feasibility, optimal objective value, and an optimal solution? The paper provides an affirmative answer for general LCQPs but a negative one for general MI-LCQPs. However, the authors also identify specific subclasses of MI-LCQP for which the answer is affirmative.

strengths:
This paper establishes a solid theoretical foundation for the application of GNNs to LCQPs and MI-LCQPs. The writing is clear.

weaknesses:
1. In order to strengthen the motivation, I would suggest including a survey of previous empirical successes of GNNs in quadratic programming or providing 2-3 specific examples of recent empirical successes of GNNs in quadratic programming, along with brief descriptions of the key results and implications.
2. The paper lacks an analysis of GNN size and depth. These factors are crucial in practical applications.

questions:
Refer to "Weakness"
</content>
</thread_object>

</thread>
<thread>
creation date:
1730457956746

thread_type:
official_review

<thread_object>
creator: reviewer_fj5r

<content>
summary:
This work investigates the expressive power of graph neural networks (GNNs) in representing both continuous and discrete quadratic programs (QPs). Specifically, it validates three key capabilities related to the empirical performance of GNNs for QPs: accurately predicting feasibility, optimality, and optimal solutions. By answering these questions, the study bridges the gap between theoretical and empirical aspects, shedding light on the strong performance observed in prior research in this field. The authors also provide sufficient numerical results to support their claims.

strengths:
1. Theoretical foundation: The paper successfully bridges the gap between theoretical predictions and empirical results by demonstrating the capacity of GNNs to represent QPs.
2. Solid theoratical proofs: The authors provide well-founded proofs to support their theoretical claims.
3. Impactful: The discoveries in this work pave the way for further exploration of GNN applications in accelerating solutions to QP problems, holding the potential for significant empirical advancements.
4. The paper is generally well-written and easy to follow.

weaknesses:
The primary concern regarding this work is the specific type of MI-LCQPs that can be represented by GNNs. 
Providing examples of application scenarios for this type of problem would help strengthen the authors' claims, as mixed-integer problems with unique optimal solutions do not appear to be very common in practice.

questions:
Please refer to "Weakness".
</content>
</thread_object>

</thread>
<thread>
creation date:
1730560985272

thread_type:
official_review

<thread_object>
creator: reviewer_lrcy

<content>
summary:
This work explores the expressive power of GNNs for LCQP and MI-LCQP, representing a significant contribution to the field. The authors provide a valuable framework and a theoretical foundation to demonstrate GNNs' capabilities in representing feasibility, optimal objective values, and solutions for LCQPs. Detailed proofs and well-structured analysis are commendable, and the organization of the paper is logical and flows well.

strengths:
The paper offers a strong contribution to understanding the expressive power of Graph Neural Networks (GNNs) for Quadratic Programming (QP), particularly for linearly constrained (LCQP) and mixed-integer (MI-LCQP) problems. The strengths of the paper include:
1. The authors have innovatively connected GNNs with LCQPs and MI-LCQPs, an area that has received limited attention, thereby expanding the potential applications of GNNs in optimization.
2. The proofs are well-structured, and the reliance on the Weisfeiler-Lehman (WL) test to support the expressive power of GNNs is a thoughtful and sound approach. 
3. The paper is well-organized, with a logical flow from background concepts to theoretical contributions and then to experimental results. 
4. The significance of this work lies in its potential impact on optimization problems where approximate solutions are acceptable.

weaknesses:
Several aspects could be improved for greater applicability and clarity:
1. The assumptions such as MP-tractability and unfoldability in Section 4, as well as the requirements for Q to be symmetric and the mappings to be continuous, might limit the broader applicability of the results in practical scenarios. 
2. Certain assumptions, such as the existence of an optimal solution for MI-LCQPs and continuity in mappings, are necessary for the proofs but lack a detailed discussion of their purpose and impact on the proof process. Without understanding why these assumptions are critical, readers might find it difficult to gauge the generalizability and limitations of the theoretical results.
3. The experimental validation relies on randomly generated LCQP and MI-LCQP instances, which may not fully capture the diversity and complexity of real-world problems. 
4. While embedding size is explored, there are few ablation studies to test other aspects of the model, such as alternative message-passing mechanisms or different GNN architectures.

questions:
Here are several questions and suggestions for the authors:
1. Could the authors elaborate on the situations where MP-tractability and unfoldability assumptions might not hold? Are there practical examples where these conditions might fail, and how would that impact the use of GNNs in those cases?
2. The paper includes several assumptions, such as Q being symmetric and the mappings being continuous. Could the authors explain why these assumptions are necessary and how they influence the proof process? 
3. Beyond the testing on synthetic data, can the authors discuss the limitations or difficulties of applying for the GNN in practical LCQP and MI-LCQP problems, e.g., applications or optimizations in power system operations or financial portfolio? 
4. Could the authors provide more experimental insights into how different message-passing mechanisms or GNN architectures might affect performance? 
5. The WL test is central to the theoretical results but may be challenging for some readers. Can the authors provide more intuitive insights or examples to illustrate how the WL test is applied in this context?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730679568673

thread_type:
official_review

<thread_object>
creator: reviewer_avvj

<content>
summary:
In this article the authors present new regarding the expressivity of GNNs for Quadratic Programming, and more specifically for Quadratic Programs (QPs) with linear constraints (continuous and mixed integer). In particular, they explicit a class of QPs (called MP-tractable) such that for each QP in the class, there exists a GNN that can provide accurate information about the feasability and the optimal value of the QP. The main results are stated in Theorem 3.3 and Theorem 3.4, and hold in probability, given a distribution on the considered class of QPs.

strengths:
- The paper has complete introduction and clearly states the contribution.

- The authors combine results in Approximation Theory and properties of GNNs to answer fundamental questions about their expressivity in the framework of QPs.

- The authors present positive and negative results regarding this expressive power.

- The authors have added numerical experiments to illustrate and support their claims.

Overall, I find the motivations of the study and the results interesting. In particular the positive results in the positive semi-definite case interesting. However, I have some reservations as detailed next.

weaknesses:
- The MP-tractable class is not very insightful or practical to work with. Can the authors elaborate if the criterion they propose is efficient to be tested? (as one of the initial motivations in the introduction was to improve efficiency in solving QPs?)

- The presentation of the technical parts could be shortened for clarity.  Cf. also my two questions below.

- The notations and statements in the proofs of the appendix are not very well chosen, making them more difficult to follow for ``superficial'' reasons. The authors do not include a lot of their proofs, very often coming from other papers.

questions:
- Can the authors elaborate on the difference of second part of Theorem 3.3 and Theorem 3.4? Isn't it true that Theorem 3.4 implies the second part of Theorem 3.3 simply by continuity of the evaluation of the objective function?

- Same question applies to Th. 4.7 vs Th. 4.9.

- (Due to weakness 1) In which part exactly did the authors prove the separation property claimed page 5?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730735359263

thread_type:
official_review

<thread_object>
creator: reviewer_y6ua

<content>
summary:
The paper investigates the expressive power of GNNs in representing key properties of quadratic programs (QP) and mixed-integer QP (MI-QP). It provides a theoretical foundation for using GNNs to approximate feasibility, optimal objective values, and solutions for QPs. The study includes both theoretical proofs and experimental results.

strengths:
1. **Importance of GNN for QP**: The paper tackles an important problem by providing a theoretical foundation on the representational power of GNNs for quadratic programming, which is relevant to various practical applications.
2. **Clarity of Writing**: The paper is well-structured, making it easy to follow. The clear explanations and organized framework enhance readability and accessibility.

weaknesses:
1. **Novelty and Limited Contributions**: While the paper aims to establish theoretical insights into GNNs' representation capabilities for QPs, much of its theoretical approach relies on Chen et al. (2023a, b), which studies the representation power of GNNs for LP and MILP. The paper’s theoretical contributions to the QP domain are thus incremental and may lack non-trivial novelty.

2. **Empirical Validation**: Although the paper includes some experimental validation, the scope is limited. A stronger empirical component using QP benchmark datasets is needed to substantiate the claims further. Additionally, the current experiments focus mainly on synthetic data, which may not sufficiently represent real-world QP applications.

3. **Handwaving Claims in Proofs**: Several proof sections lack rigor and rely on handwaving arguments. For example, statements like "xxx can be proved following the same lines as in the proof of Theorem xxx in Chen et al. (2023a), with trivial modifications to generalize results for LP-graphs to the LCQP setting," fail to provide a rigorous and self-contained argument, making it challenging for readers to verify the results.

questions:
Compared to Chen et al. (2023a, b), what are the non-trivial contributions of the theoretical analysis?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731079354120

thread_type:
official_review

<thread_object>
creator: reviewer_n1f6

<content>
summary:
This paper studies whether GNN can represent key properties (such as feasibility, optimal value, and optimal solution) of LCQP (Linearly Constrained Quadratic Programming) and MI-LCQP (Mixed-Integer LCQP) problems. The study establishes the following theoretical results:

1. **LCQP**: GNNs can universally represent the feasibility of LCQPs. For **convex** LCQPs, GNN can also universally represent the optimal values and optimal solutions.

2. **MI-LCQP**: GNNs can NOT universally represent MI-LCQPs in terms of either feasibility, optimal values, or optimal solutions. The authors provide counter-examples to prove it. Then, the authors identify a subset of MI-LCQPs, on which the GNNs can universally represent MI-LCQPs in terms of all the three key properties.

The authors further provide small-scale experimental evidence to support the theoretical results.

strengths:
1. The paper studies a crucial topic in the field of learning to optimize (L2O). GNNs have been extensively utilized for learning key properties—primarily optimal solutions—of optimization problems. By focusing on the representational power of GNNs in this context, the study offers theoretical insights and potential practical guidance.

2. In previous work, significant progress has been made in analyzing the representation power of GNNs in LP and MILP. Extending this analysis to nonlinear programming problems like LCQP and MI-LCQP is good. This paper made a commendable exploration of these extensions.

3. The paper is well-written and highly accessible, making it easy to follow.

weaknesses:
My major concern lies in distinguishing the analysis in this paper from previous studies of GNN's representation power on LP/MILP (Chen et al. (2023a), Chen et al. (2023b)). Two significant similarities raise questions about the originality of the analysis technique:

1. To prove the universal representation power of LCQP,  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). If this understanding is correct, the theoretical innovation for LCQPs might be limited.

2. The definition of unfoldable MI-LCQPs, which allows GNNs to achieve universal representation, closely mirrors the definition of unfoldable MILPs in Chen et al. (2023b). Furthermore, the proof techniques for establishing the representation power for unfoldable MI-LCQPs appear largely similar to those used for unfoldable MILPs in the prior work.

In summary, while the paper provides a comprehensive extension to LCQPs and MI-LCQPs, it is unclear whether its main proofs represent substantial innovations or are direct (albeit not completely trivial) extensions of the methodologies in Chen et al. (2023a, 2023b).

questions:
I will consider changing my opinion if the authors can address my comments in "weakness".
</content>
</thread_object>

</thread>
<thread>
creation date:
1732156850944

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Revised paper has been uploaded

comment:
We have uploaded the revised version of our paper, incorporating modifications to **both the main text and the appendix** to address the reviewers' concerns. All revisions are highlighted in blue. If you have further questions or require additional clarifications, we would be more than happy to provide them.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies whether GNN can express solutions and feasibility properties of LCQP and MI-LCQP  problems. To this end, they extend existing proof techniques.

This paper received a mixed bag of reviews. The strengths include the topic's importance, examples of positive and negative results, and the paper's organization. The weaknesses include the writing of the proofs is not completely clear (one reviewer mentioned "handwaving" and another reviewer mentioned that they were difficult to follow); and the limited novelty given how similar the results and proof techniques are to Chen et al. (2023a, 2023b). To respond to this last weakness, the authors added additional theoretical results for QCQPs during the rebuttal period. These new results were not reviewed by most of the reviewers. The only reviewer that directly acknowledged them claimed that this addition wasn't well integrated into the main narrative of the paper.