Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs
Authors: Ziang Chen
Xiaohan Chen
Jialin Liu
Xinshang Wang
Wotao Yin
Venue: ICML 2025 poster (2025)
Keywords: Graph Neural Networks
Quadratic Programming
Learning to Optimize
Primary area: deep_learning->graph_neural_networks
TL;DR: This paper explores the theoretical expressive power of GNNs for quadratic programs.

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. However, the theoretical understanding of GNNs in this context remains limited. Specifically, it is unclear what GNNs can and cannot achieve for QP tasks in theory. This work addresses this gap in the context of linearly constrained QP tasks. In the continuous setting, we prove that message-passing GNNs can universally represent fundamental properties of quadratic programs, including feasibility, optimal objective values, and optimal solutions. In the more challenging mixed-integer setting, while GNNs are not universal approximators, we identify a subclass of QP problems that GNNs can reliably represent.

Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs
Ziang Chen 1
Xiaohan Chen *2 Jialin Liu *
Xinshang Wang?
Wotao Yin
Abstract
1. Introduction
Quadratic programming (QP) is an important type of optimization problem with applications (Vogelstein et al., 2015; Markowitz, 1952; Rockafellar, 1987). It aims to minimize a quadratic objective function while satisfying specified constraints. When all the constraints are linear, we call a QP problem linearly constrained quadratic program (LCQP). When they also involve quadratic inequalities, we call the problem quadratically constrained quadratic pro- gram (QCQP). When some variables are restricted to inte- gers, the problem becomes focuses on LCQP and its mixed-intege variant, MI-L.CQP.
Quadratic programming (QP) is the most widely applied category of problems in nonlinear pro- gramming. 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 pre- conditioner. 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 charac- teristics of an optimization instance and provide adaptive guidance accordingly to crucial config- urations during the solving process, or directly provide an approximate solution. However, the theoretical understanding of GNNs in this context remains limited. Specifically, it is unclear what GNNs can and cannot achieve for QP tasks in the- ory. This work addresses this gap in the context of linearly constrained QP tasks. In the continu- ous setting, we prove that message-passing GNNs can universally represent fundamental properties of convex quadratic programs, including feasi- bility, optimal objective values, and optimal so- lutions. In the more challenging mixed -inteer setting, while GNNs are not universal approxima- tors, identify subclass of QP problems that GNNs can reliably represent.
QP. This study
In many applications, finding solutions quickly is prioritized over perfect precision. For instance, ride-hailing platforms like Uber or Lyft require quick driver-passenger matching to reduce wait times, even without optimal solutions. Similarly, financial trading algorithms must rapidly adjust portfolios to market changes, prioritizing speed over optimality.
Unfortunately, existing methods for QP often rely on com- putationally expensive techniques such as matrix decom- position and the preconditioned conjugate gradient method (PCG). For example, LU decomposition typically requires O(n²) operations for 2013), though advanced algorithms can achieve lower com- plexities. The PCG method requires O(n²)) operations per iteration, with slow convergence for ill-conitiooed matri- ces (Shewchuk, 1994). These challenges highlight the need for novel approaches to meet real-time application demands.
matrix (Golub & Van Loan,
Machine learning brings new chances to QP. Recent research shows that deep neural networks (DNNs) can significantly improve the efficiency when solving QP. Based on DNNs' role, these studies can be categorized as: (Type I). DNNs generate adaptive configurations for QP solvers. tailored to specific QP instances, thereby accelerating the solving process. (Bonami et al., 2018; 2022; Ichnowski et al., 2021; Getzelman Balaprakash, 2021; Jung et al., 2022; King et al., 2024). This approach requires DNNs capture in- depth features of QP instances and provide customized guid- ance to the solver. (Type II). DNNs replace or warm-start a QP solver. Here, DNNs take in a QP and directly output an approximate solution. These solutions can be used as final
"Equal contribution 'Department Mathematics, Mas- sachusetts Institute of Technology, Cambridge, MA, United States 2 DDcision Intelligence Lab, Damo Academy, Alibaba US, Belle- vue. WA, United States DDepartment of Statistics and Data Science, University of Central Florida, Orlando, FL, United States. Corre- spondence to: Jialin Liu <jialin. liu@uefffa. ucf.edu>>
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Expressive Power of GNNs for QP
outputs or as initial guesses accelerate QP solvers (Nowak et al., 2017; Chen al., 2018; Karg & Lucia, 2020; Wang et al., 2020a:b; 2021; Qu et al., 2021; Gao et al., 2021; Bert- simas & Stellato, 2022; Liu et al., 2022a; Sambharya et al., 2023; Pei et al., 2023; Tan et al., 2024).
grams (MILPs), but their analysis highly depends on the linear structure and does not cover nonlinear programs like QP. A concurrent study by Wu et al. (2024) investigates GNN representations for quadratically constrained quadratic programs (QCQPs) using a tripartite graph structure. While both studies address convex LCQPs, the methodologies and focus differ: Wu et al. (2024) consider general QCQPs, including quadratic constraints, and use a tripartite graph representation, whereas our work focuses on (MI-)LCQPS with a bipartite graph construction. Our analysis also covers mixed-inted integer settings and proposes an alternative approach to handling quadratic constraints, yielding partially overlap- ping but distinct results.
GNNs. Among the various types of DNNs, this paper fo- cuses on graph neural networks (GNNs) (Scarselli et al., 2008). By conceptualizing QPs as graphs (Figure 1), GNNs can be applied and efficiently handle these tasks (Nowak et al., 2017: Wang et al., 2020b; 2021; Qu et al., 2021; Gao et al., 2021: Tan ct al., 2024: Jung et al., 2022). For in- stance, Wang et al. (2021) use GNNs to solve Lawler's QAP (Lawler, 1963), while Wang et al. (2019); Yu et al. (2020) apply GNNs to Koopman-Beckman''s 2007). They exploit key strengths of GNNs: adaptability to varying graph sizes, allowing the same model applied to var- ious QPs, and permulation invariance, ensuring consistent outputs regardless of node order.
Beckmann's 's QAP (Loiola et al.,
Contributions. As several studies have empirically shown that incorporating GNNs can significantly enhance the per- formance of QP solvers, this paper aims to theoretically an- alyze the expressive power of GNNs in such tasks, identify potential areas for improvement, and highlight key consider- ations. Specifically, the contributions of this paper include:
Expressive power. Despite their notable advantages, GNNs face fundamental limitations. As Xu et al. (2019) pointed out, GNNs' expressive power is limited: they are not uni- versal approximators for all graph-based functions. Here, expressive power, core concept in deep learning theory, measures the existence of neural networks under a given structure that can approximate (or represent) a broad class of functions, and universal approximation guarantees that a model can approximate any functions within its domain.
(GNN for LCQP). In the continuous setting, where all variables are allowed to take fractional numbers, we provide an affirmative answer to question (1) with convexity and present a nonconvex counterexample.
(GNN for MI-LCQP). In mixed-integer settings, where some variables must be integers, we provide counterex- amples showing that GNNs cannot universally solve all tasks, giving a negative answer to question (l).
The contrast between the successful empirical applications of GNNs and their theoretical limitations reveals signif- icant gap. However, in practice, GNNs do not need to approximate all possible functions but only specific, mean- ingful mappings relevant to QPs. This leads to the key question motivating this work: Can GNNs, despite their lim- itations for general graph-bused mappings, exhibit sufficient expressive power to predict the key properties of OPs?
Despite this limitation, we identify specific, precisely defined subclasses of MI-LCQP where GNNs succeed. Importantly, we also present criteria for determining whether an MI-LCQP belongs to this subclass, which can be efficiently verified numerically.
2. Preliminaries
We focus on linearly constrained quadratic programming (I.CQP), which is formulated as follows:
To address this question, tions according to the nature of the application. For Type applications, we investigate whether GNNs can accurately map a QP to its critical features, focusing on the feasibil- ity and optimal objective value. For Type II, we explore whether GNNs can map a QP to one of its optimal solutions. Therefore, we ask:
focus two types of fune-
1 1 T -
min ZER"
Qx to x, S.t. Ar ob b, 15ISu. u.
(2)
where Q E Rax C AE m b Rm. 1
(IR U (=o0)))",, u E (RU(+oC)) and o E ) 1m In this paper, we always assume that Q is symmetric.
Can GNNs accurately predict the feasibility, optimal objective value, and an optimal solution of QP?
Basic concepts of LCQPs. An x satisfying all constraints of (2) is named a feasible solution. The set of all feasible solutions, X =: {a E R" : Ax o b, < x I u), is referred to as the feasible set. The LCQP is feasible if this set is non-empty; otherwise, it is infeasible. The value of ar Qu + c x is the objective value. Its infimum across X is termed the optimal objective value. If this infimum is -oo (the objective value could indefinitely decrease), the LCQP is named unbounded. A feasible and bounded LCQP must yield an optimal solution (Eaves, 1971).
The literature has explored the expressive powers of GNNs on general graph tasks (Xu et al., 2019; Azizian & Lelarge, 2021; Geerts & Reutter, 2022; Zhang et al., 2023; Li & Leskovec, 2022; Sato, 2020). However, sigmificant gaps remain in understanding how these results relate to QP. The most relevant works Chen et al. (2023;;b) investigate the expressive power of GNNs for (mixed-ine sixeed-ntteger linear pro-
2

---

Expressive Power of GNNs for QP
Qu Q12 Q21 Q22
I1
U1
02
min
Ci 2
+
C2
+
C3 33
+
1 [ 22 23)
I2
(6 S
(b2,
Q33
A
A12
A22
A23
s.t.
#1
2 h,
72
lz;
33
U3
101 =
W/2 =
W3 =
A
+
A12 2/2
b
(c,14,
(o2, b2 +00)
(cs: -00-00, Uz)
A22 22
A23
3
b2
UQ2
Q22
Q33
Q21
Figure 1. LCQP and its graph representation: All the information from the LCQP is fully encoded within the node edge attributes.
Graph representation. We present a graph structure, termed the I.CQP-graph, GL.OP = (V. W, A, Q, Hv. Hw), ) that encodes all the elements of a LCQPP The graph contains two distinct types of nodes: Nodes V = {1, 21,2..... m) labeled as i, represent the i-th constraint and are called con- straint nodes; Nodes in W {1, (1. n labeled as j. represent the j-th variable and are known as variable nodes. An edge connects i E V to j E W if Aij is nonzero, with Ag serving as the edge weight. Similarly, the edge between nodes j.J E W exists if Qjs' * O, with Qiy' as the edge weight. Self loops (j = j') are permitted. Attributes (or fea- tures) U; (b,, 9;) are attached the i-th constraint node for V. The collection of all such attributes is denoted as Hv = (V1, .2..... um). Attributes wy (c,, ly. uy) are attached to the j-th variable node for j E W and their collection is denoted as Hw (W1, W2, W.).
The architecture includes L standard message- paatagggg lay- ers where each layer (where 1 < 1 S L) updates node attributes by locally aggregating neighbor information:
st = S (s!++ Σ 96 (t) .Aa)
JEAM
+) - ( (15)
Σ gh (5) An). (s)),
Σ 9f o Qgr)) J'ENT
IENY
where SV S.W gi Ii W Q
99 are trainable local updates in GNNs and NWW = = E W Aij # +),, [j E V
A, + 0), and A/W (j' ew: Qir + 0} are the sets of neighbors. Finally, there are two types of output layers. For applications where the GNN maps I.CQ to a real value, such as evaluating properties like feasibility of LCQP, graph-level output layer is employed that computes a single real number encompassing the entire graph:
Such a representation, illustrated by Figure I, is a fundamen- tal and "minimal" approach in the sense that every entry in (A, b, c, Q, L, u, o)) is used exactly once. While this particular representation is only detailed in Jung al. (2022), it forms the foundation of 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). Removing edges associated with Q simplifies the graph to bipartite structure and reduces LCQP to LP (Chen et al., 2023a; Fan et al., 2023; Liu et al., 2024; Qian et al., 2024). By adding an extra node feature, an approach detailed in Section 4, this graph can also express mixed-integer programs (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
==ri Σ o Σ )
E
NEV
JEW
Alternatively, if the GNN is required to map the LCQP- graph to a vector E RR", assigning a real number to each variable node as its output (as is typical in applications where GNNs are used to predict solutions), then node- level output should be utilized:
8 E for j E W.
y, = 12
NEV JEW
Here, r1 and 72 are trainable output functions. In our theo- retical analysis, we assume all the mappings fV, f. (0 S S T.), of S.W,9
:Pe (1 S L),, and r1, to be contin- uous. In practice, these continuous mappings are usually parameterized by multilayer perceptrons (MLPs) and their parameters are learned from data.
Definition 2.1 (Space of LCQP-graphs). The set of all ICQP-graphs, denoted as 91 comprises graphs with m constraints and n variables, where Q is symmetric.
et al., 2022; Paulus et al., 2022; Scavuzzo et al., 2022: Liu
al., 2022b; Huang et al., 2023; Wang et al., 2024).
GNNs for LCQPs. Given the graph representation, we present pressage-passingg graph neural networks (hereafter referred to simply as GNNs) for LCQPs. They take in an LCQP- -grahh GLCop (including the node and edge attributes) and update node attributes sequentially across layers via a message-passinng paasiigg mechanism. Initially, node attributes are updated separately using embedding mappings fý .&W:
Definition 2.2 (Spaces of GNNs). The collection of all GNNs, denoted as FLCQP for graph-level outputs (or J.W FL.CPP
'The space G is equipped with the subspacc topology induced from the product space {AA, b. c, Q, A mmx b E Rm "IR, E _=Xn I E (- u E (R U (+oa))" E (5.=,>)m} Áll Euclidean spaces have standard Eudlidean topologies, discrete spaces equipped with the discrete topology, and their unions are disjoint unions.
24 = =1' f(((()) (1:) for i V, and 19 = f (w,) for j E W.
3

---

Expressive Power of GNNs for QP
for node-level outputs), consists of all GNNs constructed using continuous mappings fi S. (0
linear programs (Chen et al., 2023a), as feasibility is solely determined by the constraints, independent of the objective function, and all LCQP constraints are linear.
< 1 S L),
oy II b sisis L), and ri T2). Definition 2.3 (Target mappings). We define:
However, using GNNs to predict the optimal objective value or an optimal solution is highly non-trivial due to the non- linear term x Qx. Fortunately, when restricting LCQPs to convex cases, GNNs can universally represent the optimal objective value and an optimal solution for these LCQPs.
Feasibility mapping: Ireas (GLoP) = 1 if GLOOp is feasi- ble and (Grco)) = 0 if it is infeasible.
Optimal objective mapping: Pasy(G E R U (+ computes the optimal objective value of GLoQe- & (Gi(C)) = +oo means the problem is infeasible and 2 (GLCQp) = oo means unboundedness.
Theorem 3.3. For any P satisfyyng Assumption 3.1 with PiQ = 0] 1 (Q is positive semidefinite almost surely), and for any > 0, there exists Fi E FFi.cop such that
Optimal solution mapping: For feasible and bounded LCQP problem (i.e., Panj (GLOo)) E R), an optimal so- lution exists though it might not be unique. However, the optimal solution with the smallest 2y-norm must be unique if Q = 0, i.e Q is positive semi-definite, and we define it as @
P[ + [IPas(Ghcoe)ER) <e. Addtitionally, if LP (GLCOP) E RR = L, then for any c, > 0, there exists F2 E FLOOP such that
(3)
PP [| - & Dooj (GLCCO))
<E <8)<E.
(4)
Given the definitions above, we can formally pose the ques- tion in (1) as follows: Is there any F E FLCO that well approximates teas or Pay? Similarly, is there any function Fw E FL that well approximates sal (G
This theorem indicates that GNNs can approximate the opti- mal objective value mapping Pot very well in two senses: (I) GNN can predict whether the optimal objective value is real number =oo, i.e., whether the LCQP problem is feasible and bounded or not. (II) For data distribution over feasible and bounded LCQP problems, GNN can approxi- mate the optimal objective. Finally, we prove that GNN can approximate the optimal solution map Psol-
3. Universal approximation for convex LCQPs
This section presents our main theoretical results for the expressive power of GNNs for representing properties of LCQPs. In particular, we show that for any convex LCQP data distribution, there always is GNN that can predict LCQP properties, in the sense of universally approximating target mappings in Definition 2.3, within a given error tol- erance. A Although is known in the previous literature that there exists some continuous function that cannot be approx- imated by GNNs with arbitrarily small error, see e.g., Xu et al. (2019); Azizian & Lelarge (2021); Geerts & Reutter (2022), our results in this section indicate that approximat- ing the target mappings of LCQPs do not suffer from this limitation.
Theorem 3.4. For any P satisfying Assumption 3.1 with PiQ = 0] = P Pnj af..COO)))))) E RR] =1,, 1, and any c, O. there exists Fw E FFlcOP such that
[[]] (GLCO) - soa
> 8] <e.
The detailed proofs of Theorems 3.3 and 3.4 will be pre- sented in Appendix A. We briefly describe the main idea here. The WeiersWeissss theorem and its variants are powerful tool for proving universal- approximation type re- sults. Recall that the classic version of the Stone- Weierstrass theorem states that under some assumptions, a function class F can uniformly approximate every continuous function if and only if it separates points, i.c., for any x # x', one has F(x) F F(x') for some F E F. Otherwise, we say and x' are indistinguishable by any F E F. Therefore, the key component in the proof is to establish some separation results in the sense that two LCQP-graphs with different optimal objective values (or different optimal solutions with the smallest fn-nmm) must be distinguished by some GNN in the class FLCQP (or J.W /.Co.).. is shown Xu et al. (2019); Azizian & Lelarge (2021); Geerts & Reutter (2022) that the separation power* of GNNs is equivalent to the Weisfeiler- Lehman (WI.) test (Weisfeiler & Leman, 1968), a classical algorithm for the graph isomorphism problem. We show that, any two LCQP- -rrphg that are indistinguisabble by
Assumption 3.1. P is a Borel regular probability measure defined on the space of LCQP-graphs 9ic@p
The assumption of Borel regularity is generally satisfied for most data distributions in practice.
Theorem 3.2. For any P satisfying Assumption 3.1 and any > O, there exists F E FicOp such that F(GGuu))) & acts as a classifier for LCQP-feasibilit with an error of up to e
PP |[[FrCucce)> + 2 4eees (GLCop)] < <,
where I. is the indicator function: LF(Gua))> 1 if F(GLCOF) > 3; IF((LCC))>> = 0 otherwise.
This result suggests that a GNN is universal classifier for LCQP feasibility: for any data distribution of LCQPs satisfying Assumption 3.1, there exists a GNN that can classify LCQP feasibility with arbitrarily high accuracy. This is a natural extension of the feasibility classification for
Giivn two sets of functions, F and F', both defined over domain X, if F separating points and x' implies that F also separates and x' for any x, E X, then the separation power of J' is considered to stronger than or equal to that of F.
4

---

Expressive Power of GNNs for QP
(Observation f). The two LCQPs are not equivalent, and their graph representations are not isomorphic. Both LCQPs are feasible and bounded, with identical optimal objective values, as 1 x = 6 results in _ x + 1"x = 24. However, they are not equívalent because their solution sets differ. Specifically, (3,3, 0, 0, 0, 0, 0) is a solution to (5) but not to (6), while (2. 2, 0, 0, 0,0) is a solution to (6) but not to (5). Furthermore, their graph representations differ: in the first graph, the 7 variables form two groups- -nn 2 nodes and the other with 5-where nodes in each group are connected eyclically. In the second graph, the variables form two groups, but one with 3 nodes and the other with 4,
1 1TT11 11 x +1 1'x,,
min rER 2-
s.t. Ø1 82 = 0, T2 - 01 = 0,
11
23 24 = 0, T4 I5 0,
(5)
25 26 = 0, Fg 87 0, 27
33 = 0,
22 + + I5 I6
Σ7 6
0 1 33,v E 11, 73.
one with
(Observation II). The two graphs cannot be distinguished by any GNNs, even after multiple rounds of message pass- ing. Initially, both graphs are indistinguishable as they share identical node attributes: seven red nodes, seven blue nodes, and one brown node. During message passing, each red node receives identical updates due to symmetric connec- tions: one blue node with weight Aij = 1, another with As = 11 the brown node with A. = 1, and all seven red nodes with Q3y- = 1. As a result, the red node's attribute updated as (an informal but illustrative equation):
08
TTT1 5 11 1 1Tx, =ER"
min
s.t.
22 = 0, I2 I3 0, Z3 21 0,
24 35 = 0, I5 - I6 0,
t = f1" red node, gf (blue node, 1) + +y (blue node, -))
f6 87 = 0, 87 - J1 = O,
21 + 29 + 2 F4 + I5 + I6 + 87 =6
+9, (brown node, 1), 7 9 (red node, 1)).
0 05 x 3 (1,2.... 7]
After the update, all red nodes 12 (1 ر < 7) in both graphs retain identical attributes and are still indistinguishable. The same applies to the blue and brown nodes. Therefore, re- gardless of how many message- paagging rounds occur, both graphs will still have seven red nodes, seven blue nodes, and one brown node. This holds for any parameterized map- pings used in GNNs (f)", f." 9y 9/" and ) meaning GNN can differentiate between the two instances.
16
(Observation III). They share the common optimal solu- 6 6
tion with the smallest fz-norm: (9 7: 7: 7: 7: 7. 9), which follows from 1 TT I = 6 and the Cauchy-Schware inequality.
the WI. test, or equivalently by all GNNs, even they are not isomorphic, they must have identical optimal objective value and identical optimal solution with the smallest tn-norm
Note that these observations are not mere coincidences; we have established this conclusion in general for LCQPs (see Definition A. Theorem A.2, and Theorem A.3).
An illustrative example. We the two LCQPs, (5) and (6). each with 7 variables and 8 constraints, to illus- trate our findings. All variable nodes share the attribute wy = (1, 0, 3) for 1 < j < 7, which represents an objective coefficient of cj = 1, lower bound 1, = O, upper bound " = We refer to these nodes as "red nodes." " The first seven constraint nodes 94 (for 1 < S 7) are assigned the same attribute, U; (0, =). which we label as "blue nodes". The eighth constraint node Us is unique, with the attribute Ug- (6,=), -), and is called the "brown node." Any red node is connected to blue node with weight A.j = 1 (solid lines), another blue node with weight Ai = -1 (dashed lines), the brown node with weight Ai = (green lines), and all seven red nodes with 2 = (brown curves).
Additionally, similar results can be extended to QCQPs under certain assumptions, though it is beyond the main focus of this paper. The details are deferred to Appendix E.
A nonconvex counterexample. At the end of this section, we comment that Theorems 3.3 and 3.4 do not hold if the convexity assumption (PIQ 0] 1) is removed. In particular, consider a convex LCQP
min (m1 x2)
() 0)
1)
x1
s.t. - 1 $01,02 1
x22
and a nonconvex LCQP
(1
min (m 22)
( 0
S.L. - 01 $
12
5

---

Expressive Power of GNNs for QP
Following the aforementioned argument, one can verify that these two LCQP instances are indistinguishable by any GNNs. On the other hand, the first convex LCQP has optimal objective being O and the optimal solution being (0, 0), while the second nonconvex I.CQ has an optimal objective being- -1 and optimal solutions being (1, -1) and (-1,1). This indicates that the conclusions in Theorems 3.3 and 3.4 do not hold true for the data distribution that is sup- ported on aforementioned instances with equal probability, since a GNN making accurate prediction on one instance must fail on the other.
choose the uniform distribution over pairs of instances satis- fying Propositions 4.1, 4.2, and 4.3: any GNN making good approximation on one instance must fail on the other.
The detailed proofs are provided in Appendix B. Here we present a pair of MI-LCQPs that prove Proposition 4.3.
A counterexample. We modify the two LCQPs in (5) and (6) into two MI-LCQPs by introducing integer constraints all variables: specifically, Ij E Z for i E {1...., .7). Consequently, the node attributes wy are updated to wj (1,033, 3, 1), where the last entry, 1, indicates the integral constraint 57 = 1. All other components of the graphs remain unchanged, as described in Section 3. With this modification, the node attributes w remain identical for all W. Since all other graph components are unchanged, the same argument from Section 3 applies: any GNNs can- not distinguish the two MI-LCQPs.
4. The capacity of GNNs for MI-LCQPs
In this section, we turn to mixed-integer linearly constrained quadratic program (MI-LCQP), which is almost the same as LCQP (2) except that some entries of are constrained to be integers: zj Z, vj I, where I C (1,2...... collects the indices of all integer variables.
However, the mixed- inttegr setting differs from the con- tinuous one: the two problems no longer share the same solution (9. 6 6
MI-L.CP--rrahh is modified from the LCQP-graph by adding a new entry to the feature of each variable node j E W. The new feature is w = (cy. Ly, uy, (i) where 1 if j E 7 and (7( = otherwise. We use g... MM-LCQP to denote the collection of all MI-LCQP-grapha
7 71 7 71 7 9). Instead, they have disjoint op- timal solution sets. The first instance has an unique feasible (and thus optimal) solution (3, 0, O, 0, O, 0), while in the second instance, it is (2, 2, 2, 0).
G
5)(
4.2. GNNs can represent particular types of MI-LCQPs
GNNs for MI-LCQP-graphs are constructed using the same framework as those for LCQP-graphs, differing only in the input feature wj as defined above. We use FMI-LCOP and J- LCOP to denote the GNN classes for MI-LCQP- graphs with graph-level and node-level output, respectively.
We have shown a fundamental limitation of GNNs to repre- sent MI-LCQP general. natural question arise: Whether we can identify a subset of GMI-LCOP on which it is possible to train reliable GNNs. To address this, we need gain better understanding for the separation power of GNNs, or equivalently, of the WL test, according to the discussion following Theorem 3.4. We state in Algorithm the WL test for MI-LCQP -agLpps associated to FMI-LCQP or J-
Target mappings for MI-LCQPs also similar to those in Definition 2.3. In particular, teas and dajj are defined in Definition 2.3, while the optimal solution mapping & can only be defined on subset of the class of feasible and bounded MI-LCQPs, as discussed in Appendix C.
MI-LCQP A Algorithm 1 The WL test (Ref. to App. D for an example)
4.1. GNNs cannot universally represent MI-LCQPs
Require: G (V, W, A, Q, Hv, Hw). and iteration limit L. Initialization: C. hash(v:), and Gg.W = hash(w;). 2: for = 1,2,... L do
In this subsection, we answer the question (1) for MI-LCQP. When integer variables are introduced, the situation changes.
3: C.. hash -.V [(C) Ab))
Particularly, we present some counter-examples illustrating the fundamental limitation of GNNs in this context.
4: C/ = hash (C-- 1.W
[C 1.. A.s) Assty
[(C)- .Qp) (By))yeen exwwr.
Propusition 4.1. There exist two MI-LCQP problems, with one being feasible and the other being infeasible, such that their graphs are indistinguishable by any GNN in FML-CLQP. Proposition 4.2. There exist two feasible MI-LCQP prob- lems, with different optimal objective values, such that their graphs are indistinguishable by any GNN in FML.CLOP Proposition 4.3. There exist two feasible MI-LCQP prob- lems with the same optimal objectives but disjoint optimal solution sets, such that their graphs are indistinguishable by any GNN in F MI-CLQP
5: end for
6: return All vertex colors C.C.V W.C.
Here, C.VV and Cl.. are the colors of node E V and node j E W at the 1-th iteration. The "hash" function is any injective (collision-free free) mapping, independent of j. In practice, standard built-in hash functions can be used.
The WL test mimics GNNs iterative updates, replacing learnable mappings with hash functions. While hash func- tions cannot directly map graph to desired outcomes, they effectively distinguish nodes and differentiate graphs
is indicated that for some MI-LCQP data distribution, it is impossible to train a GNN to predict MI-LCQP proper- ties, regardless of the GNN's size, Particularly, one can
Initially, each vertex is labeled a color by a hash function
6

---

Expressive Power of GNNs for QP
according its attributes (vy or wy.) At the I-th iteration, two vertices are of the same color if and only if the (1- 11th iteration, they have the same color and the same information aggregation from neighbors. This is a color refinement procedure. One can have a partition of the vertex set V NUW W at each iteration based on vertices' colors: two vertices are classified in the same class if and only if they are of the same color. Such partition is strictly refined in the first (m n) iterations and will remain stable or unchanged afterward, see e.g., Berkholz et al. (2017).
exists F E FMI-LCOP such that
P F|[r(Gmuoor)>> * Preas ( (GMI-LCOP]] <G and there exists Fi E FMI-LCOP such that
(7)
P (GmMAcop)) F I (GMAaCGCOO))) <c.
(8)
Additionally, if (GMILLCOP)) E BR] = 1, for any e, 0, there exists F22 E FMILCOP such that
PP [IMMLCOO)) & ooyj (GMI-LCOP) 6] <. 99)
To extend these results to predicting optimal solutions, we need to assume the MI-LCQPs have an optimal solution. We denote " as the set of MI-LCQPs with an optimal solution. The assumption is expressed as GMI-LCOP E +%%
Revisit the counterexample in Section 4.1: As analyzed earlier, applying the WL test to the two MI-LCQPs results in all variable nodes W having identical colors (red nodes), meaning they belong to the same class in the WL. test's s final stable partition. Nodes in the same class of this partition will always share identical attributes across all layers of any GNNs, and vice versa, because the color refinement process in Algorithm 1 mirrors GNNs' update mechanisms. How- ever, while the desired GNN output is (3,3, 0, 0, O, 0, 0), GNNs cannot differentiate between these variables, result- ing in outputs where 1/1 = = y/- This contradiction is the core reason for GNNs' failure on these counterexamples.
Theorem 4.7. For any I satisfying Assumption 4.5 and L(G E gool n 9 = 1, and for any c, 5 > 0. there exists Fww E F-W
MI.LCQP such that
P F[] (GML-LCQE) - D Paao(Gx-LLcop ) > 81 <c
Theorems 4.6 and 4.7 indicate the subsets of MI-LCQPs
where GNNs can succeed: For GNN-analyzable MI-LCQPs, GNNs can approximate their feasibility and optimal objec- tive; For GNN-solvable ones, GNNs can approximate their optimal solutions. Proofs are available in Appendix C.
To address this issue, we propose to: (I) Restrict the focus to MI-LCQPs where each node in the graph representation has a unique color (i.e., every class in the partition contains exactly one node), ensuring GNNs can separate all nodes. or (II) Allow partitions with classes containing multiple nodes but impose additional conditions within each class to ensure the desired output does not rely on distinguishing between these nodes. Therefore, define as follows.
4.3. Discussions of "friendly" MI-L.CQPs
To better illustrate the practical implications of Theo- rems 4.6 and 4.7, make some discussions of GNN- analyzability and GNN-solvability here.
Analyzability vs Solvability. While all GNN-solvable MI- LCQPs must be GNN- aaalyaaly not all GNN-analyzaabe problems are necessarily GNN-solvable. Related discus- sions, proofs and examples are detailed in Appendix D.
Definition 4.4 (GNN-friendly MI-LCQPs). Consider a MI-
LCQP problem GMI.LCOP E MMi-LOge and apply the WL. test to obtain the final stable partition JI, where =
{T,, [e....,TTs] Is} partitions V = 2,, m and J =
Since solvability is a stronger condition than analyzability, when problem is GNN-solvable, GNNs can approximate not only the optimal solution (Theorem 4.7) but also the feasibility and the optimal objective (Theorem 4.6). In this sense, learning the solution mapping is a stricter requirement than learning the feasibility and optimal objective.
(J1,J2,.. .., J+3 partitions W = 21, n.]. Then, GMIL.QOP is called "GNN-solvable" i ====p n and |-|== |32] = = [J,| = 1, i.e., all vertices in W have different colors. We use Gaavaable C gmm. GMILL.oP to denote the collection of all GNN-solvable MI-LCQPs.
Frequency of friendly instances. In practice, the frequency of GNN-analyzabl and GNN-solvable instances largely de- pends on the the level of symmetry in the dataset. Here, two variables labeled with the same color by the WL test are said to be symmetric. When there is symmetry in a MI-LCQP, it becomes GNN--isoolvable; and higher symmetry increases the risk of being ENNNinamalyzable Examples provided by (5) and (6) admit strong symmetry across all variables, mak- ing them neither GNN- -aN-aanlyeabll nor GNN-solvable. Fortu- nately, GNN-solvable and GNN-analyzable instances make up the majority of the MI-LCQP set, under specific distribu- tional assumptions (see e.g. Proposition D.3). This explains the observed success of GNNs for QPs in the existing litera- ture and addresses the gap between theoretical limitations
GMILLCOP is called "GNN-analyzablee" if: (1) For any p E {1, ...,,...... }} and E (1,2,...,,. 1),,
A.j is constant across all E I E Jq. (2) For any 9. 96 f1,2..... f). Qiy' is constant across j Jq E Jg. The set of all such MI-LCQPs is denoted by Ganalyzable MI-LCCP
GNN-solvability extends "unfoldability" in the context of MILP (Chen et al., 2023b), and annlaaaalyyaiilityy extends "MP-tractabilitty" (Chen et al., 2024). With such definitions, we can establish GNNs' expressive power for MI-LCQPs. Assumption 4.5. is Borel regular probability measure defined on the space of 1--LCO--grrphh gm.n MI-LCOP
Theorem 4.6. For any IP satisfying Assumption 4.5 and L| E Immilyaablel = 1, and for any e. > 0, there
7

---

Expressive Power of GNNs for QP
10a.
Emb, 5ize 64
10"
Emb, Size 64
10
Emb. Size - 64
Emb. Size 64
10.2
Emb. Size
Emb. Sac
Relative Emar
10-1
Emb, Size 128
Size
Relatve Ernor
Emb. Size = 250
Size
betattee Error
100
256
128
Relative
Emb. Size 512
10
Emb, Size - 512
10-3
Emb. Size - 512
Emb Size 512
10
10-3
10
10.4.
10
10-
10-1
10
500
1000
1500
2500
5000
7500
10000
2000
4000
6000
2500
5000
7500
10000
Epoch
Epoch
Epoch
Epoch
(a) Fit Payy for LCQP
(b) Fit Puat for LCQP
(c) Fit Pay for MI-LCQP
(d) Fit duat for MI-LCQP
Figure 2. Relative errors when training GNNs to fit Pasj and Puot for LCQP (2a-2b) and MI-LCQP (2c-2d) with various embedding sizes.
0.2
0.2
0.10
+ 100 Samples
Relative ertor
100 Samples
Rolatve enar
100 Samples
Relattve error
T 100 Samples
500 Samples
500 Samples
500 Samples
500 Samples
Relathv
2500 Samples
0.1
2500 Samples
9.1
2500 Samples
0.2
2500 Samples
0.05
0.00
20
24
2a
24
0.0
2
2'
20
20
2
20
2
Hidden embedding size
embedding
Hidder embedding
Hidden embedding sice
(a) Fit Pay for LCQP
(b) Fit Putt for LCQP
(c) Fit Pay for MI-LCQP
(d) Fit Punl for MI-LCQP
Figure 3. Validation larger scale. The figures illustrate the relative errors for various combinations of embedding sizes and numbers
of training samples. We can achieve near zero errors when the GNN is large enough.
and empirical success discussed in Section 1. The dataset used in Section 5 consists entirely of GNN-solvable and GNN-analyzable instances. However, in some challenging, artificially collected or created datasets, such as QPlib (Fu- rini et al., 2019), it's possible to be GNN-insolvable or even GNN-inanalyzable (see in Appendix D.2 for details).
and 50 variables. The generated MI-LCQPs are all GNN- solvable and GNN--aalyzable with probability one. Details on the data generation and training schemes can be found in Appendix G. We train four GNNs with four different embedding sizes and record their relative errors averaged on all instances during training. The results are reported in Figure 2. We can see that GNNs can fit Ponj and & well for both LCQP and MI-LCQP. These results validate Theorems 3.3,3.4,4.6 and 4.7. We also observe that larger embedding size increases the capacity of a GNN, resulting in not only lower final errors but also faster convergence.
Numerical verification. While GNN-analyzability and GNN-solvability depend on the dataset, they can be ef- ficiently verified in practice. One may first apply Algo- rithm 1, which requires at most Om + n) iterations. The single-iteration complexity is bounded by the number of edges in the graph (Shervashidze et al., 2011), which, in our context, is the number of nonzeros in matrices A and Q: nn) + mnz(Q), Therefore, Algorithm I's complex- ity is ((mm + n)- (nnz(A) nnz(Q))). Afterward, both conditions can be directly verified using Definition 4.4.
Validation on a larger scale. To further validate the theo- rems, we expand the number of problem instances to 500 and 2,500. The results, reported in Figure 3, show that GNN achieves near-zero fitting errors when it has large enough embedding size and thus enough capacity for approximation, which directly validate Theorems 4,4.3.4,4.6 and 4.7.
Therefore, these criteria provide practitioners with a prac- tical tool to evaluate datasets before applying GNNs. Ad- ditionally, if challenges arise during GNN training on MI- LCQPs, verifying them can help identify potential issues.
Various types of LCQP. Besides the generic LCQP for- mulation (2), we also extend the numerical experiments to other types of optimization problems, namely portfolio op- timization and support vector machine (SVM) following Jung et al. (2022). The results are reported in Figure 4. We can observe similar fitting behaviors as those in the generic LCQP experiments where the expressive power of GNNs in- crease as they become larger, evidenced by the fitting errors decreasing to near zero when the embedding size increases.
5. Numerical experiments
We present numerical experiments in this section.
Numerical validation of GNNs expressive power. We train GNNs to fit Pabi or a for LCQP or MI-LCQP in- stances. For both LCQP and MI-LCQP, we randomly gen- crate 100 instances, each of which contains 10 constraints
Real dataset. To further examine the universal approxima- tion results on more realistic QP problems. For LCQP, we train GNNs on the Maros and Meszaros Problem Set (Maros
Coodes are available at httts://githhbt com/ /iuilllgit/GNN *Since LCQP and MI-LCQP are linearly constrained, predict- ing feasibility falls to the case of LP and MILP in Chen et al. (2023a;b). Hence we omit the feasibility experiments.
'The relative enror of GNN Fw single problem instance G is defined as [Fw(GG) +CC)lla/ max ([) 1), where d could be either Pay or P
8

---

Expressive Power of GNNs for QP
0.06
Relabve ener
0.04
100 Samples
500 Sampless
Relativs arter
0.10
100 Samples Samples 2500 Samples
Reative arer
0.04
100 Samples Samples
Relative arter
0.10
500 Samples
100 Samples
2500 Samples
2500 Samples
2500 Samples
0.02-
0.05
9.02
0.05
0.00
0.00
0.00
0.00
2.
27
23F
20
2
2
2'
2
22
2
Hidden embedding size
Hidden embedding size
Hidden embedding size
Hidden ambedding size
(a) Fit Pary for portfolio
(b) Fit Paal for portfolio
(c) Fit day for SVM
(d) Fit Psot for SVM
Figure 4. Various types of LCQP: portfolio optimization and SVM optimization problems. The figures illustrate the best relative errors
achieved during training for various combinations of embedding sizes and numbers of training samples.
Emb Sor 64
Embh 5an
Emb. Sae 254
Emb. San
105+
Crb S3n 254
Emb 12d
Cmb- -12
750
Erdi 5 Emb Sae 512
Tantrer
1x-00-
brb sie 512
Emb.
Than Emtr
4x10-
20-3
088
3x10-1
3x
2002
4007
1000
5320
20000
2000
4000
5000
3000
10002
0
2000
4000
5000
9300
23000
2000
4000
1000
5000
10000
(a) Fit Payy on Maros Meszaros
(b) Fit Pas on Maros Meszaros
(c) Fit Pay on QPLib
(d) Fit 4ua on QPLib
Figure 5. Training errors on real datasets: Convex LCQP (5a-5b) and MI- MI-LCQP (5c-5d).
Table Average solving times (millisecondss) GNN and OSQP.
Batch Size
10
100
1,000
OSQP GNN
4.48+3.62
13.62+16.72
5.37
0.504+0.14p
142 0.089#0.002
& Mészááos, 1999), which contains 138 challenging convex LCQPs. The results are shown in Figure 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 to some extent. 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. Details are deferred Appendix G.
deviations are shown in Table 1. The sufficiently acceler- ated computation validates GNNs' capacity as a real-time QP solver fast warm-start, numerically supporting the rationality of our theoretical study of GNNs for QPs.
Generalization. Besides investigating GNNs' expressive capacity, we also explore their generalization ability and observed positive results. As generalization is beyond this work's scope, the results are provided in Appendix G.
6. Conclusions and future directions
For MI-LCQP, we perform GNN training 73 GNN- solvable instances from QPLib (Furini et al., 2019) that pro- vide 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 in Figures 5c-5d. 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.
This paper establishes theoretical foundations for using GNNs to represent the feasibility, optimal objective value, and optimal solution of LCQPs and MI-LCQPS. We prove GNNs can universally approximate these properties for LCQPs and show this is in general not true for MI-LCQPs, except for specific subclasses we identify. Future research directions include studying the training dynamics, general- ization behavior, and size requirements of GNNs. In particu- lar, the algorithm- digoritnnuunrollnng provides a way to estimate GNN sizes, as it explicitly defines the number of parameters per layer, and prior work (e.g.. (Li et al., 2024)) shows algorithm-unrolling is a structured GNN. These connections suggest that GNN complexity bounds for (MI-)ICCPPs may be derived from the algorithn-unrollng literature. Another compelling direction for future work is to unify LP, LCQP, QCQP, and extensions on higher-order polynomial optimization via hypergraph GNNs.
Computation complexity. GNNs are superior over QP solvers in terms of running time, especially when we fully exploit parallel computing with GPU acceleration. To show this, we measure the average running time using OSQP (Stel- lato et al., 2020) and a trained GNN with different batch sizes over the 1,000 synthetic LCQP problems generated in the experiment above. We applied OSQP solve all instances to relative error of 10-3, which is slightly less accurate than the trained GNN (with an average relative er- ror of 6.31 x 10-4). The average solving times and standard
unrolling framework by Yang al. (2024)
9

---

Expressive Power of GNNs for QP
Impact Statement
Chen, Z., Liu, J., Wang, X., Lu, J., and Yin, W. On rep- resenting linear programs by graph neural networks. In The Eleventh International Conference on Learning Rep- resentations, 2023a.
This paper explores the expressive power of GNNs for QP tasks. Given the wide applications of QP in industry, our work could have broad societal impacts. However, as this study is primarily theoretical, we do not identify any specific societal impacts that must be specifically highlighted here.
Chen, Z., Liu, J., Wang, X., Lu, J., and Yin, W. On repre- senting mixed-integer linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations, 2023b.
Acknowledgements
The work of Ziang Chen is supported in part by the National Science Foundation via grant DMS-2509011.
Chen, Z.,, Liu, J., Chen, X., Wang, X., and Yin, W. Rethink- ing the capacity of graph neural networks for branching strategy. arXiv preprint arXiv:240..07099 2024.
References
Chen, Z., Zhang, Q., and Wang. R.
On the expressive power of subgraph graph neural networks for graphs with bounded cycles. arXiv preprint arXiv:2502.03703, 2025.
Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard, M., al. Tensorflow: system for large-scale machine learning. In 12th USENIX symposium on operating systems design and implementation (OSDI 16), pp. 265-283, 2016.
Eaves, B. C. On quadratic programming. Management
Science, 17(11):69--71, 1971.
Azizian, W. and Lelarge, M. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021.
Fan, Z., Wang, X., Yakovenko, O., Sivas, A. A., Ren, O., Zhang, Y., and Zhou, Z. Smart initial basis selection for linear programs. In International Conference on Machine Learning, pp. 9650-9664, PMLR, 2023.
Berkholz, C., Bonsma, P., and Grohe, M. Tight lower and upper bounds for the complexity of canonical colour re- finement. Theory of Computing Systems, 60:581-614, 2017.
Feng, J., Chen, Y., Li, F., Sarkar, A., and Zhang, M. How powerful are k-hop message passing graph neural net- works. Advances Neural Information Processing Sys- lems, 35:4776-4790, 2022.
Bertsimas, D. and Stellato, B. Online mixed-integer opti- mization in milliseconds. INFORMS Journal on Comput- ing, 34(4):2229-2248, 2022.
Furini, F., Traversi, E., Belotti, P., Frangioni, A., Gleixner, A., Gould, N., Liberti, L., Lodi, A., Misener, R., Mittel- mann, H., et al. Qplib: a library of quadratic program- ming instances. Mathematical Programming Compula- tion, 11:237-265,
Bonami, P., Lodi, A., and Zarpellon, G. Learning a classifi- cation of mixed-integer quadratic programming problems. In Integration of Constraint Programming, Artificial In- telligence, and Operations Research: 15th International Conference, CPATOR 2018, Delft, The Netherlands, June 26-29, 2018 Proceedings 15, pp. 595-604. Springer, 2018.
Gao, Q. Wang, F., Xue, N., Yu, J.-G., and Xia, G.-S. Deep graph matching under quadratic constraint. In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5069-5078, 2021.
Bonami, P., Lodi, A., and Zarpellon, G. A classifier to decide on the linearization of mixed-integer quadratic problems in eplex. Operations research, 70(6):3303- 3320, 2022.
Gasse, M., Chételat, D., Ferroni, N., Charlin, L., and Lodi, A. Exact combinatorial optimization with graph convolu- tional neural networks. Advances in neural information processing systems, 32, 2019.
Caron, S., Zaki, A., Otta, P., Arnström, D., Carpentier, J., Yang, F., and Leziart, P.-A. qpbenchmark: Benchmark for quadratic programming solvers available in Python, 2024. URL qpbenchmark.
Geerts, F. and Reutter, J. L. Expressiveness and approxima- tion properties of graph neural networks. In International Conference on Learning Representations, 2022.
com/ hanm/ppslveers////
Getzelman, G. and Balaprakash, P. Learning to switch opti- mizers for quadratic programming, In Asian Conference on Machine Learning, pp. 1553-1568. PMLR, 2021.
Chen, S., Saulnier, K., Atanasov, N., Lee, D. D., Kumar, V., Pappas, G. J., and Morari, M. Approximating ex- plicit model predictive control using constrained neural networks. In 2018 Annual American control conference (ACC), pp. 1520-1527 IEEE, 2018.
Golub, G. H. and Van Loan, C. F. Matrix computations. JHU press, 2013.
10

---

Expressive Power of GNNs for QP
Gupta, P., Gasse, M., Khalil, E., Mudigonda, P., Lodi, A., and Bengio, Y. Hybrid models for learning branch. Advances in neural information processing systems, 33: 18087-18097, 2020.
regularization for outlier-robust graph matching. In The Eleventh International Conference Learning Repre- sentations, 2022a.
Liu, D., Fischetti, M., and Lodi, A. Learning to search in local branching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 3796-3803, 2022b.
Gupta, P., Khalil, E. B., Chetélat, D., Gasse, M., Bengio, Y., Lodi, A., and Kumar, M. Lookback for learning to branch. arXiv preprint arXiv:2206. 14987, 2022.
Huang, T., Ferber, A. M., Tian, Y., Dilkina, B., and Steiner, B. Searching large neighborhoods for integer linear pro- grams with contrastive learning. In International Con- ference on Machine Learning, pp. 13869-13890. PMLR, 2023.
Liu, T., Pu, S., Ge, D., and Ye, Y. Learning pivot smart expert. In Proceedings the AAAI Conference Artificial Intelligence, volume 38, pp. 8073-8081, 2024.
Loiola, E. M., De Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P., and Querido, A survey for the quadratic assignment problem. European journal of operational research, 176(2):657-600, 2007.
Ichnowski, J., Jain, P., Stellato, B., Banjac, G., Luo, M., Borrelli, F., Gonzalez, J. E., Stoica, I., and Goldberg, K. Accelerating quadratic optimization with reinforcement learning. Advances in Neural Information Processing Systems,
Markowitz, H. Portfolio selection. The Journal of Finance, 7(1):77-91, 1952.
2021.
Jung, H., Park, J., and Park, J. Learning context-aware adaptive solvers to accelerate quadratic programming. arXiv preprint arXiv:2211. 1...222111./44,, 2022.
Maros, I. and Mészáros, C. A repository of convex quadratic programming problems. Optimization methods and soft- ware, 11(1-4)671-681, 1999.
Karg, B. and Lucia, S. Efficient representation and ap- proximation of model predictive control laws via deep learning. IEEE Transactions on Cybernetics, 50(9):3866- 3878, 2020.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In Pro- ceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Khalil, E. B., Morris, C., and Lodi, A. Mip-gnn: A data- driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 36, pp. 10219-10227, 2022.
Nair, V., Bartunov, S., Gimeno, F, von Glehn, I., Li- chocki, P., Lobov, I., O'Donoghue, B., Sonnerat, N., Tjandraatmadja, C., Wang, P., et al. Solving mixed in- teger programs using neural networks. arXiv preprint urXiv:2012.1 2...20022..3800 13349, 2020.
King, E., Kotary, J., Fioretto, F., and Drgona, J. Metric learn- ing to accelerate convergence of operator splitting meth- ods for differentiable parametric programming. arXiv preprint arXiv:2404.00883 2024.
Nowak, A., Villar, S., Bandeira, A. S.. and Bruna, J. A note on learning algorithms for quadratic assignment with graph neural networks. stat, 1050:22, 2017.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6995 2014.
Paulus, M. B., Zarpellon, G., Krause, A., Charlin, L., and Maddison, C. Learning cut by looking ahead: Cut- ting plane selection via imitation learning. In Inter- national Conference on Machine Learning, pp. 17584- 17600. PMLR, 2022.
Lawler, E. L. The quadratic ussignment problem. Manage- ment science, 9(4):5865599, 1963.
Li, and Leskovec, The expressive power of graph neural networks. Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 63-98, 2022.
Pei, C., Xu, Z., You, S., Sun, J., and Dai, R. Reinforcement sorning-guidess quadratically constrained quadratic pro- gramming for enhanced convergence and optimality. In 2023 62nd IEEE Conference on Decision and Control (CDC), pp. 7293-7298. IEEE, 2023,
Li, Q. Ding, T., Yang, L., Ouyang, M., Shi, Q., and Sun, R. On the power of small-size graph neural networks for linear programming. Conference on Neural Information Processing Systems, 2024.
The Tiihty- Annual
Qian, C., Chételat, D.,, and Morris, C. Exploring the power graph neural networks in solving linear optimization problems. In International Conference on Artificial Intel- ligence and Statistics, pp. 1432-1440. PMLR, 2024.
Liu, C., Jiang, Z., Wang, R., Huang, L., Lu, P., and Yan, Revocable deep reinforcement learning with affinity

---

Expressive Power of GNNs for QP
Qu, J., Ling, H., Zhang, C., Lyu, X., and Tang, Z. Adaptive edge attention for graph matching with outliers. In I/CAI, pp. 966-972, 2021.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. arXiv preprint 1rXiv:1710. 10903, 2017.
Rockafellar, R. 'T. Linear-quas -uuaar-quadratic programming and opti- mal control. SIAM Journal Control and Optimization, 25(3):781-814 1987.
Vogelstein, J. T., Conroy, M., Lyzinski, V., Podrazik, L. J., Kratzer, S. G., Harley, T., Fishkind, D. E., Vogel- stein, R. J., and Priebe, C. E. Fast approximate quadratic programming for graph matching. PLOS one, 10(4): e0121002, 2015.
Sambharya, R., Hall, G., Amos, B., and Stellato, B. End- to-end learning to warm-start for real-time quadratic opti- mization. In Learning for Dynamics and Control Confer- ence, pp. 220-234, PMLR, 2023.
Wang. H. P., Liu, J., Chen, X., Wang, X., Li, P., and Yin, W. DIG-MILP: deep instance generator for mixed- integer linear programming with feasibility guarantee. Transactions on Machine Learning Research, 2024.
Sato, R. A survey on the expressive power of graph neural networks. arXiv preprint 200300000 2020.
Wang, R., Yan, J., and Yang, X. Learning combinatorial embedding networks for deep graph matching. In Pro- ceedings of the IEEE/CVF international conference computer vision, pp- 3056-3065, 2019.
Sato, R., Yamada, M., and Kashima, H. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pp. 333-341. SIAM, 2021.
Wang, R., Yan, J., and Yang. X. Combinatorial learning of robust deep graph matching: an embedding based approach. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(6):6984-700M) 2020a.
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
Scavuzzo, L., Chen, F. Y., Chételat, D., Gasse, M., Lodi, A., Yorke-Smith, N., and Aardal, K. Learning to branch with tree mdps. arXiv preprint arXiv: 1107, 2022.
Wang, R., Yan, J., and Yang. X. Neural graph matching net- work: Learning lawler's 's quadratic assignment problem with extension to hypergraph and multiple- graph match- ing. IEEE Transactions on Pattern Analysis and Machine Inielligence, 44(9):5261-522 2021.
Schwan, R., Jiang, Y., Kuhn, D., and Jones, C. N. Piqp: A proximal interior-point quadratic programming solver. In 2023 62nd IEEE Conference on Decision and Control (CDC), pp. 1088-1093, IEEE, 2023.
Wang. T., Liu, H., Li, Y., Jin, Y., Hou, X., and Ling, H. Learning combinatorial solver for graph matching. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 7568-7577, 2020b.
Shen, Y., Sun, Y., Eberhard, A., and Li, X. Learning primal heuristics for mixed integer programs. In 2021 Interna- tional Joint Conference on Neural Networks (IJCNN), pp- 1-8. IEEE, 2021.
Weisfeiler, B. and Leman, The reduction of a graph to canonical form and the algebra which appears therein. NT1, Series, 2(9):12-16, 1968.
Shervashidze, N., Schweitzer, P., Van Leeuwen, J., Mehlhorn, K., and Borgwardt, K. M. Weisteiler-lchman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Wu, C., Chen, Q., Wang, A., Ding, T., Sun, R., Yang, W., and Shi, Q. On representing convex quadratically con- strained quadratic programs via graph neural networks. arXiv preprint arXiv:2411.13800 2024.
Shewchuk, R. An introduction the conjugate gradient method without the agonizing pain. Technical report, Carnegie Mellon University, 1994.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Stellato, B., Banjac. G., Goulart, P. Bemporad, A., and Boyd, S. OSQP: operator splitting solver for quadratic programs. Mathematical Programming Computation. 12(4))637-672, 2020. doi: 10.1007/ s12532-020-000179-22 URL https: http:::/ddoooooo////// 1007 1007/s12532-020-00111
Yang, L., Li, B., Ding, T., Wu, J., Wang, A., Wang, Y., Tang, J., Sun, R., and Luo, X. An efficient unsupervised frame- work for convex quadratic programs via deep unrolling. arXiv preprint arXiv:2412.01055 2024.
Tan, H., Wang. C., Wu, S., Zhang, X.-Y., Yin, F., and Liu, C.-L. Ensemble quadratic assignment network for graph matching. International Journal of Computer Vision. pp.
Yu, T., Wang, R., Yan, J., and Li, B. Learning deep graph matching with channel-independeed embedding and hun- garian attention. In International Conference on Learning Representations, 2020.
1-23, 2024.
12

---

Expressive Power of GNNs for QP
Zhang, B., Fan, C., Liu, S., Huang, K., Zhao, X., Huang, J., and Liu, Z. The expressive power of graph neural networks: A survey. arXiv preprint arXiv:2308.08233. 2023.
13

---

Expressive Power of GNNs for QP
A. Proofs for Section 3
In this appendix, we present the proof' for theorems in Section 3. The proof' will based on Weisfeiler-Lchman (WL) test and its separation power to distinguish LCQP problems with different properties (different feasibility, different optimal objective, or different optimal solution with the smallest Eg norm).
The Weisfeiler-Lehman (WL) test (Weisfeiler & Leman, 1968) is classical algorithm for the graph isomorphism problem. In particular, it implements color refinement on vertices by applying hash function on the previous vertex color and aggregation of colors from neighbors, and identifies two graphs as isomorphic if their final color multisets are the same. It worth noting that WL test may incorrectly identify two non-isomorphic graphs as isomorphic. We slightly modify the standard WL test, see Algorithm
Algorithm 2 The linear-form WL test
Require: A LCQP-graph G = (V,WA, Q, Hv, Hw) and iteration limit L > 0. 1: Initialize with C. hush( and C..W = hash(ws).
2: for 1 1,2, ... L do
3: Refine the colors
C... = hash
C
C1-1V
A.y hash (c/-1
Qir hash (cF- (prl )
C = hash
c/ 1l-1.
Aighasi (c.
(c.-l.v)
Σ
4: end for
5: return The multisets containing all colors
(...V B &O. o
Please note that, Algorithm 2 is special case of Algorithm and, as such, has weaker separation power. However, sufficient for distinguishing LCQPs with different key properties. Notably, proving universal approximation under a weaker WL test leads to even stronger conclusion: if weaker WL test (or equivalently, a less powerful GNN) separate LCQPs, it automatically implies that these LCQPs can also be separated under a stronger WL test.
We define two equivalence relations as follows. Intuitively, LCQP- graphs in the same equivalence class will be identified as isomorphic by WL test, though they may be actually non-isomorphic.
Definition A.1. For two LCQP-graphs GLOOP, GLOUP N. B.m & Dy= be color multisets output by Algorithm 2 on GLCOp and GLCOP.
KCf. B and let (C..V BT
1. We say GLCor ~ GLCOP if [. B &.O. Wm and &C,. = C.C. Vi hold for all L E N and all hash functions.
2. We say GLOOp* W. GLOGP if (.C. all hash functions.
V. H C.C.v. Im and c... =O C.. Vj (1.2.... ..... n). for all L N and
Our main finding leading to the results in Section 3 is that, for LCQP graphs in the same equivalence class, even if they non-isomorphic, their optimal objective values and optimal solutions must be the same (up to a permutation perhaps).
Theorem A.2. For any GLCOP, ČLOOP E G. with Q, Q 0. if GLCOP ~ GLCOP then 2 (GLCOp) (Paj(Crcoo))
Theorem A.3. For any GLCOP, GLCOP E Guoo with Q, ž that are feasible and bounded, GL.CP ~ GLoge. then W GLcor.
there exists some permutation ow E Sn such that aea (GL.or))))) = ow aw (T (Gucor)). Furthermore, if GLoge then so (GLCQe) = @aal (.aoGG)
We need the following lemma to prove Theorem A.2 and Theorem A.3.
14

---

Expressive Power of GNNS for QP
Lemma A.4. Suppose that M R is symmeiric and positive semidefinite matrix and that J (J.,d Jt is partition of (1, ,,,,...,10 satisfying that for any q.96 (1,2,....1) Eyed, Ma is constant over j E Tq. For any x E IR" , it holds that
1 T Mx 2 1 _ _ Mé,
(10)
2
2
where & E RR is defined via 8, Y4 J Eyes, zÿ for Jq.
Proof. Fix a E I" and consider the problem
1 2 M2,
min =ER" 2
s.t. Σ
Σ
zj q= 1.2....,t
(11)
jEJ,
JEJ,
which is convex program. The Lagrangian is given by
((2, 2² Mr
Σ
X
Σ Rjj Σ
zjj
g=1
jEJ.
jEJo
It can be computed that
0
8 Σ
[(2, ()=
Marizz Ago
j Jq
0zg
j'=1
and
((2, (), = Σ
g3 Σ
2j+
07g
JEJ/
jEJq
It is clear that
0 ((; =
Σ
Σ
0,
07g9
JEJg
JEJq
by the definition of é. Furthermore, consider any fixed q E f1.2.....tt t}
and we have for any E Jg that
((2, = Σ Yo' Σ J'EJ
May Ag =0,
0zj
q'=1
X, = Ey= Ue Eyer May that is independent in j E q since Σye,, M,y is constant over j Jg for any of E (1,2,.... t). Since the problem (11) is convex and the first-order optimality condition is satisfied at ât we can conclude that à is minimizer of (11), which implies (10).
Proof of Theorem A.2. Let GL.OO and GL.Oop be the LCCP-graphs associated (2) and
min EER"
2 x T éTe, s.t. Ax ó b, i S x < ú,
(12)
Suppose that there are no collisions of hash functions or their linear combinations when applying the WL to GLCOP and GLoOp and there are no strict color refinements in the L-th iteration. Since GLcge ~ GLCOE, after performing some permutation, there exist I = (h, J2,.... , I,) and J (J1,J,....,dl that are partitions of (1,2,..., m) and nn., respectively, such that the followings hold:
C.. C.V. if and only if i Ip for some p E 21,2.... ..,.). s}.
A... C...V if and only i Ip for some p E {1, 2, s}.
G..V C.V.V and only if E Tp for some p E (1, 2, .8.
88.
15

---

Expressive Power of GNNs for QP
C... 3' W. if and only j,j Jg for some q {1,2,... .., ,.).
Cf.. = =Og C..W if and only if j.J E Jg for some E {,, .).
C... = C..W if and only if j,j' E Jg for some {1, ................................ ...,,,... ..,
Since there are no collisions, we have from the vertex color initialization that
2 = (b,, 0;) = 8 = (b, 0,) and constant over i E Ip for any p E (1,2...., wi - (cg.lg. U5) - = - (2 2 úg) and is constant over j E Jy for any a E 21,
For any p E (1,2....,.) of and any i, E Ip. one has
C..y -/.
Σ
A1yhash
(CH-LIH)
Σ
Ar Aryhash (cH-1,8))
jEW
jEW
Σ Aighash
(CL.W) =
Σ Aayhash (CL.W)
jEW
jEW
Σ
Auj
Σ
Arj. 4
f1.2....tth t].
jEJ,
JEJy
One can obtain similar conclusions from C...V
C... and C...V V and hence conclude that
For any p E (1,2..... s} and g (1,2..... ................................ t). EjE,, Ais Eje,, Ag and is constant over i Ip- Similarly, the followings also hold:
For any E (1,2....,, and E (1,2....,, EiEr, Aij EiEI, Ai and is constant over j E Jg-
For any q. E (1, f3. (.. Qir Eje,, Qiy and is constant over j Jq.
If GLCOP (2) is infeasible, then oby (LCCO) too and clearly abb (GLCOP) 2 Lan((G If (2) is feasible, let
1 R" be any feasible solution to (2) and define & E I via 2j V4 [r,1 EyeJ, Ty for j E Jg- By the proofs of
Lemma B.2 and Lemma B.3 in Chen et al. (2023a), we know that a feasible solution to (12) and c x = cTá. a. In addition, we have
1
Qx
(10)
Qi
Σ
Σ
2
1 Σ
yaya Σ Qi
2
=EEd J'E y'Ed
4.4'=1
j'Ela
Σ
Σ
Qu - ΣΣΣΣ
2 =
1
2
4.4"
fEEdy
9-0' =1jE,,
which then implies that
Qu + c 2 1 T +
5"
and hence that Dooy (GLCOp) 2 Pony (GLOOP). Till now we have proved Poog (GLoor) > ( regardless of the feasibility of GLogr. The reverse direction Payy (Gooo) T (Glcoe) is also true and we conclude that P (Gloop) oony (GLCoP).
Proof of Theorem A.3. Under the same setting as in the proof of Theorem A.2, the results can be proved. We present the proof here.
16

---

Expressive Power of GNNs for QP
Let x R be the optimal solution to (2) with the smallest fg-norm, and let & E R" be defined as in the proof of Theorem A.2. By the arguments in the proof of Theorem A.2, # is optimal solution (12). In particular, & is also an optimal solution to (2) since one can set (A, 6, è, Q, 6) (A, b, c. U,,,,,)) Therefore, by the minimality of ||x|| we have that
||||| & ||l|
E
1
Ij
q=1jEJa
jEJa
@=l
which implies that zy is constant in j E Jg and x = S. Thus, also an optimal solution to (12).
Let w/ IR" be the optimal solution to (12) with the smallest f--nomm. Then ||-l|| S ||]||
|| and the reverse direction
||=||| $ ||='|] is also true, which implies that ||||| ||='||- Therefore, we have z' by the uniqueness of the optimal
solution with the smallest norm.
Noticing that the above arguments are made after permuting vertices in V and W, we can conclude that aan (Gt.CO)) = ow ( a (ooo(()))))) for some ow E Sn. Additionally, if GLCOP W GLCOP. then there no need to perform the permutation on W and we have saa (GL.O)))))) = .u (a
Corollary A.5. For any GLCOr E SLcOp that is feasible and bounded and any j.j E (1,2..... ifC. C..W holds for all E N+ and all hash functions, then & sal ssal (G..oo)) = Paal (G.cCP))))
Proof. Let GLOOp be the LrQph obtained from GL.OP by relabeling j as j' and relabeling j' as j. By Theorem A.3, we have DaatGGr.o Taa (GI.co)), which implies @aa(Grr)))) s. 2a (G.COP)))))
is well-known from previous literature that the separation power of GNNs equivalent to that of WL test and that GNNs can universally approximate any continuous function whose separation is not stronger than that of WL test; see e.g. Chen al. (2023a); Xu et al. (2019); Azizian & Lelarge (2021); Geerts & Reutter (2022). We have established in Theorem A.2, Theorem A.3, and Corollary A.5 that the separation power of Poty and L is upper bounded by the WL test (Algorithm 2) that shares the same information aggregation mechanism as the GNNs in FL.COp and LCQP- Theorem 3.3 and Theorem 3.4 will be proved following this idea.
Proof Theorem 3.3. Theorem 3.3 can be proved based on Theorem A.2.
The separation power of GNNs is equivalent to that of the WL test, i.., for any GLCOP, GL.OP PLcop with Q, = 0.
GL.COp Gr.Cop > F(Gr.op) F(Crcoo), V F E FiCOP,
(13)
which combined with Theorem A.2 leads to that
F(GLCOF)= = F(GLOOr), A F E FLCOP = Pobj (GLCop) = Doty (GoLG))))))
(14)
indicating that the separation power of FL.GOp is upper bounded by that of Pati-
The indicator function T&an())R : 90 + {0, 1} C TR is measurable, i.e., T0 and ক-, (0) are both Lebesgue measurable, and hence by Lusin's theorem, there exists compact and permutation-invarian subspace X c Grcop such that PIGTop XX] < and that (E) restricted on X is continuous. Therefore, by the Stone- Weierstrass theorem and (14),
we have that there exists F, E FLCOP satisfying
sup G
[i(C.o)))) - [a <
Therefore, it holds that
P [T # Ta <
g
x \x|
<6,
which proves (3). Additionally, (4) can be proved by applying similar arguments to Poyj T (R) R. where D (R) Gho0 is the collection of feasible and bounded GLCor Glcor
17

---

Expressive Power of GNNs for QP
Proof of Theorem 3.4. Theorem 3.4 can be proved based on Theorem A.3 and Corollary A.5.
In addition to (13), it can be proved that the separation powers of GNNs and the WL test equivalent in the following sense:
For any Griqp; Gr.cop E R.CoP GLCOP W. CL and only if Fw (G.CO) = Fw for all Pw E LOOP
For any GLOOP E C.CO and any j.j' E W. C... Fw (GLCOP) = Fw (GI.Co)yy for all Fw E JW
j C...W for any and any hash function if and only if
Therefore, with Theorem A.3 and Corollary A.5, the separation power GNNs is upper bounded by that of 4 sol in the following sense that for any GLoge, GLCOp LLCOP with Q, Q = 0 and any j.J' W.
F(GLCOP) F(CLCOp), F FLCO implies sso = ow (4 (Ssol (GLcqp)) for some ow E Sn.
(GLCo)) = Fw (GLooP), Y Fw E Filcop implies P (GLCO))) a (GLCoP).
FG FG A Fw F.W
LCQP implies P (GI.CO))))) D (G.COP))))))''
The optimal solution mapping Psol 0b
(R) R" is measurable, i.c. & 2 (A) Lebesgue measurable for any Borel measurable A R", and hence by Lusin's 's theorem, there exists compact and permutation-invarie subspace X C and that Lool restricted X is continuous. Therefore, applying the generalized
$ (R) such that P[ obj [R] Chone-Weierstrass theorem for equivariant functions (Azizian & Lelarge, 2021, Theorem 22), we know that there exists Fw E FFLCOP satisfying
sup GuogrX
|| (GLCQP) - P (GI.CO)) || < 6.
Therefore, holds that
TP
[I] [il (W Pat > S T (R)(X) <6
which completes the proof.
B. Proofs for Section 4.1
The proof of Proposisition 4.1 directly from Chen et al. (2023b) since adding a quadratic term the objective function of an MILP problem does change the feasible region. However, Proposisitions 4.2 and 4.3 are not covered in Chen et al. (2023b) and present their proofs here.
Proof of Proposisition 4.2. As discussed in Section 4.1, we consider the following two examples whose optimal objective values are 2 and 6, respectively.
9
min 2
Σ
Zt 1=1
1=1
31 +
2
12 12
72
x t 2 1 2 1o
2 21,
xy E (0,1),
RATS
F4
WTT
min #E26
- 2 Σ 2
2
1=1
1
25
215
s.t. 3 + 32
+ 2
x4
+ 15 21 13 + 2 21, +2 1
125
ky E (0.1), Vje (1.2. 6).
18

---

Expressive Power of GNNS for QP
Denote GMI-LCOP and GMI-LCOP as the graph representations of the above two MI-LCQP problems. Let o/ 1 and 8/. 1/ be the attributes at the 1-th layer when apply a GNN F E -MILLCOP to GMILLOP and GMI..CQP- We will prove by induction that for any 0 v 1 < L, the followings hold:
(a) $ $ and is constant over i E
(b) 1 13 and is constant over j E 2,,,,...6 6).
It is clear that the conditions (a) and (b) are true for = O, since e = i; = (1,2) is constant in E (1, ,6). and
w 10j- = (1, 1, 1) is constant in j E 21, .6]............................. Now suppose that the conditions (a) and (b) are true for ( - where 1 < L. We denote that g/~1 = =s
8, d-1 Vi (1,2,...,6 and d 1 = - V jj E 2 6). It can
be computed for any E {1,2.... .,,....,,,,........ .6] and E (1,2.....
.2....,6] 6} that
Σ
M "t'(
(1) Ais)
= S - 1
229 2 (d-"1.1) 1)) = 5/.
jEN
12 ll 1
Σ
96 (s)-), ,Ai)); Σ
gi Qz5))
iENY
S'ENT
= f.W (1-1, 2gl (s' g) (t- ,1) =
which proves (a) and (b) for 1. Thus, we can conclude that F F(GMI-LCOP) = F(GMI-LCOP), A F FMI-LCOP.
We also remark that, although the two MI-LCQP graphs with distinct optimal objective values presented above are indistinguishable by GNNs considered in this paper, they can be distinguished by 3-hop GNNs (Feng et al., 2022; Chen et al., 2025). Crucially, when we scale these examples to 10 variables and 10 constraints (one graph with 20 connected nodes and the other with two 10-node components). 3- 3-hop GNNs fail while 5-hop GNNs succeed, confirming that larger in k-hop GNNs reduces GNN-unfriendly cases, though they do not solve all MI-LCCPPS.
Proof of Proposition 4.3. Consider the following two MI-LCQPs:
81
RERT 2" 11 x ++11 11 2,
min
0, 32
23 34 0, 34 I5
84
ss - d6 0, d6 IT #7 x3 0,
8 2 22 24 26 + T6 87 = 6
05 2, <3, E2, Vj 11, 7)
7).
and
22
T xCR? 2"
min
11 x + 1,
s.t.
0, 22
0,
0,
24
0, 25 Ig
237A
76 87 0, Ø7 I4
21 + 22 + 3I 24 + 25 + Hg + 87
0 S 2, 33, 22 EZ, Vj 6 [1, (1,
26
1006
19

---

Expressive Power of GNNs for QP
As mentioned in Section 4.1, both problems feasible with the same optimal objective value, but have disjoint optimal solution sets.
On the other hand, it can be analyzed using the same argument as in the proof of Proposition 4.2 that for any 0 s 1 S L that
(a) s // is constant over E .1. 7), and sis = s/g.
(b) t) t is constant over j (1. 7).
These conditions guarantee that F(GMILLCOP) F(GMILCOO)) F FMI-LCOP and Fw Fw(GMLLCOO) Fw Fw (GMILCOO)) & Fw E FMI-COP-
C. Proofs for Section 4.2
This section collects the proof' of Theorems 4.6 and 4.7. Similar to the LCQP case, the proofs are also based the WL test (Algorithm 1) and its separation power to distinguish MI-LCQP problems with different properties. We define the separation power of Algorithm as follows.
Definition C.I. Let GMILLCO, GMLLLOP E MILLCP be two MI-LCQP--rann -gaaphs and let C.C. B C.C.".C
By= and
be color multisets output by Algorithm on GMILLOP and GMILCOP. N.C D C.C. Di=
1. We say GMILLCOP GMILLCOP if (.C.V.V Bm (CC.VVV 1 and (C,. (C,,"BB CCC.CC and all hash functions.
By= hold for all E
2. We say GMILLOOP ~ GMILCOP if (.C. Di=0 = (.C.v. pm and C. = C... (1, n.. for all L E and all hash functions.
The key component in the proof is to show that for GNN-sovahheGGNNaamlyyabb MI-LCQP problems, they are indistinguishable by the WL test, then they must share some common properties.
Theorem C.2. For two GNN-analyzable MALCQP-grapha GMILCOP,, GMLL.OP E gm,n aanilyzable" if GMILLCP ~ GMILCOP. then
icaas (GMILLCOP) = Prass (GMLLCOP) and Panj (GMILLOPP) = L (GMILLCO)))))
Proof. Let GMILLCPP and GMILLCOP the MI-LCQP-graphs associated
min #ER"
Arob, 1abb, E2 VjET.
(15)
and
+ s.t. Ar i is 2, E EZ, Vjei. J
1
min ZER
(16)
Suppose that there are no collisions hash functions or their linear combinations when applying the WL test to GMELLQO
and GMI-LCOP and there are no strict color refinements in the L-th iteration. Since GMI-LCOP GMI-LCOP and both of them are GNN-analyzable, after performing some permutation, there exist = (71, I2...., I,} and J = (J,, J2, Je) that are partitions (1, 2,...,,,,, and 21,2,..., n), respectively, such that the followings hold:
c... C... if and only i / E Ip for some p E {1.2...... s).
C.. C...V if and only i, i' e Ip for some p E {1, 1..,.....5 s3.
GL.Y = C..VV if and only i, i E p for some E {1, (1.)....,8).
c..W = ch. W if and only if j. E Jg for some { [1, ...
c..W = &L.W W. if and only if j.j' E Jg for some (1,2.....4
..... ...
20

---

Expressive Power of GNNs for QP
C..W - if and jf E J9 for some q E (1, .............
By similar analysis as in the proof of Theorem A.2, we have
(a) e 6 and is constant over i Ip for any p E (1, s}.
(b) w = ر and is constant over j E Jg for any g E {1,2 .t.,,
(c) For any p E (1, .} and any q E {1, (1.2....,tf) t}. [Ay i E J4D = [AA 1 1 E J and is constant over i E Ip-
(d) For any p E (1, {e and any q E {1, ..,2,....f... .1. [Ay :1 1, = [Aa : 1 and is constant over j E Jq-
(e) For any q.d e (1, f), KQpr I' E Jv B (4r : E Jg' and is constant over j Jg-
Note that GMLLCOP and GMILCOP are both GNN-analyzable, i.e., all submatrices (Agj)iEt, (Aig) (0sr))ese. and (Q have identical entries. The above conditions (c)-() suggest that
(f) For any p E (1,2..... 5s and any q E t). A.j Aig and is constant over i Ip.J Jg.
(g) For any q. E (1, t), Q3y² Q3 and is constant over j J Jg--
Combining conditions (a), (b), (f), and (g), we can conclude that GMILLCOP and GMILLCP are actually identical after applying some permutation, i.e., they are isomorphie, which implies Preas (GMI-LCuP) Preas (GMLLCCQP) and @aby (GMI-LCO)))
oony (GMI-LCO))
MI-LCQP optimal solution mapping set- Before stating the next result, we present the definition of the MI-LCQP optimal solution mapping a Different from the LCQP setting, the optimal solution to an MI-LCQP problem may not exist even is feasible and bounded, i.e., Paay(GiiLLoop E R. Thus, we have to work with P C & is the collection of all MI-LCQP-graphe for which an optimal solution exists. For GMI-LCOP E gol it is possible that it admits multiple optimal solution. Moreover, there may even exist multiple optimal solutions with the smallest fo-norm due to its non-convexity. which means that we cannot define the optimal solution mapping L using the same approach as in the LCQP case. If we further assume that GMI-LCQP E 9m is GNN-solvable, then using the same approach as in Chen et al. (2023b, Appendix C), one can define a total ordering the optimal solution set and hence define & (GMI-LCQP) as the minimal element in the optimal solution set, which is unique and ietuutatioonequiariann meaning that if one relabels vertices of GMI-LOOP. then entries of sol (GMM-LO)))) are relabeled accordingly. In particular, since the WL test applied on GMLL.OOP E Ih n g yields distinct vertex colors, one can uniquely find a permutation o E S, that orders 1, 1.2..... n lexicographically. Then sol (o (GMI-LCOP) is defined as the vector x E R² so that (Ia(1), (Ta(I),Fa(()) (.. is minimized in the lexicographic sense among all optimal solutions of GMILCOP-
Pobj (R) C Mi-LCOP where "
Theorem C.3. For any two MALLC@--rraph GMILLOP,, GMILLCP E 9im n that are GNN-solvable with nonempty optimal solution sets, if GMI-LCOP GMI-LCOP. then there exists some permutation ow E S, such that a (GMILLO))))) ow (Daa (. Furthermore, if GMILLOOP W GMaLLOo, then Pant (GMLLLO))))) &Dal (GmIlcop).
Proof. By Proposition D.I, GMI-LCOP and GMILLCOP are also GNN-analyzable, and hence. If G ~ GMILLCOP then they are isomorphic by the analysis in the proof of Theorem C.2, and hence, P (SM(LLM))))) = ow ( (C for
some permutation ow E S,, If GMILLOP W GMILLCPP, then the same analysis in the proof of Theorem C.2 applies and these two graphs are identical after applying some permutation on V with the labeling in W unchanged, which guarantees ya (CM)) = . @a GML.
As discussed in the main test before Definition 4.4, for GNN-analyeable and GNN-solvable MI-LCQP instances, vertices with essentially different properties will be distinguished by WL test or GNNs. For such GNN-friendly instances, GNNs have provably strong expressive power. In fact, with Theorem C.2 and Theorem C.3, one can prove Theorem 4.6 and Theorem 4.7, via a similar argument when we prove Theorems 3.3 and 3.4.
21

---

Expressive Power of GNNs for QP
Proof of Theorem 4.6. Theorem 4.6 can be proved based Theorem C.2. We only present the proof of (7) since (8) and (9) can be proved with almost the same lines.
The separation power of GNNs is equivalent to that of the WL test, i.e., for any GMILLOOP- GMLL.COP E MILCOP
GML.LCOP GMILCOP = F(GMILCOP) F(GMLLCO)) V FMLLCOP:
(17)
which combined with Theorem C.2 leads that for GMI-LCQP, GMI-LCOP E G annalzzable
F(GML-LCOO) = F(GMIILOOP), V F FMILLQP = 4 tens Prens (GMILLCQP) P (GMI-LCCP))
(18)
indicating that the separation power of FMI-LOOP is upper bounded by that of Diess on Gamaly
annalyzable
The function ieass unaalyzable {0, 1] C IR is measurable, i.e., Feas (0) and $ (0) are both Lebesgue measurable, and hence by Lusin's theorem, there exists a compact and permuration-invarian subspace X C Imi amuiyzzale such that
PP aaniiyyzabl XX] and that fcas restricted on X is continuous. Therefore, by the Stone-Weierstran theorem and (18), we have that there exists F E FMI-LCOP satisfying
|((GMLLCOO) Diens (GMI-LOqe) < GasscueE
sup
Therefore, holds that
P I [(Chaaror)) + Deems (GMILLC)))))) S
Golai anaalyzable
|x]
<G
which proves (7).
Proof of Theorem 4.7. In addition (17), it be proved that the separation powers of GNNs and the WL test equivalent in the following sense:
For any GMI-LCOP, GMILLCOP E MI-LCQP GMI-LCOP W. GMILLOP if and only if Fw (GMI-LCOP) Fww (GMILLOO)) for all Fw E FW
For any GMI-LCOP IMiLcOP and any j.j' E W,W C. = =C for any L E N and any hash function if and only if Fw (GMI-LCOP)) = Fw (GMLLCCc))) for all Fw E JW
MI-LCQP
Therefore, with Theorem C.3, the separation power GNNs is upper bounded by that of 2na on 9 n mm.n in the
following sense: for any GMI-LCOP, GMI-LCQP E 9 n n solvable
om.n
F FGMM) F(GMILCOP)) Y F FMLlCOP implies P LCMIL aw ( (GMI for some ow Sn-
Fw (GMILCCO)) Fw (GMLLCOO))) V Fw E JW LC implies Psol (GMI-LLO)))) 4 (GMILLCOP).
Fw (GMILLCC))) Fw (GMLLLCC, A Fw E F.W implies = j' and hence & (GMI P (GMLLGML..
The optimal solution mapping s 9 n solvablc + R" is measurable, i.e., 20 (A) is Lebesgue measurable for any Borel measurable A C RR, and hence by Lusin's theorem, there exists a compact and permutation-invarian subspace X C G n gm,n such that PPiCmi n Gooraale [X] < e and that & restricted on X is continuous. Therefore, applying the generalized Stone- Weierstrass theorem for equivariant functions (Azizian & Lelarge, 2021, Theorem 22), we know that there exists Fw MMILLOOPP satisfying
mm.n
J-W
sup Ox
|FW (GMI-LCOP) - & (GMHLCOO))) < 6.
Therefore, holds that
IP [|] Fw (GmLlcop) +Ian (Gm(GMMLLCP))] 8) S PP (g n salvable |X] <E
which completes the proof.
22

---

Expressive Power of GNNs for QP
the sum aggregation, and all results still valid for the weighted average aggregation. In particular, all proofs (such the proof of Theorem A.2) hold almost verbatimly for the average aggregation. The attention aggregation (Veličković et al., 2017) has stronger separation power, which implies that all universal approximation results still hold. Moreover, all the counter examples for MI-LCQPs work for every aggregation approach, since the color refinement in Algorithm is implemented on multisets, with separation power stronger than or equal to all aggregations of neighboring information.
Discussions various GNN architectures: In work
D. Characterization of GNN-analyzability and GNN-solvability
This section provides detailed discussion of these conditions for MI-LCQP graphs, defined in Section 4.3.
D.1. Relationship between GNN-analyzability and GNN-solvability
We first prove that GNN-solvability implies GNN-analyzability but they are not equivalent, Proposition D.I. If GM E IMLLCCP is GNN-solvable, then it is also GNN-analyzable.
Proof. Let (I,J) be the final stable partition of V W.W generated by WL test GMI.LCOP without collision, where I= (41,42....,44 },} is partition of V 21,2..... m and J {J1, J2, ................................ J1) is partition of W .1. ,,), Since we assume that GMILLOP is GNN-insolvable, we have = n and |J1] [J2] 4,44 E (1,2,... .J. the submatrix (0ir),,,,J'e,, is a x matrix and hence has identical entries.
|Jl 1. Then for any
l).
Consider any p E WL test. Then for any i, i'' Ip. we have
and E ,t. Suppose that the color positioning stabilized at the L-th iteration of
C.. c
{ hash (CH-L,W,A)) .Ao) :j E : - }}
hash (CH-1,,,,,)
: : JENN] }}
{{i j E J,) = (1Ai : E Jq
which implies that the submatrix (At)) has identical entries since |.y1 Therefore, GMI-LCOP GNN- analyzable. Proposition D.2. There exist GNN-analyzable instances in MiL that are GNN-solvable.
min s.t.
1d2 + 21 2 1
82 23
W1
211
-1 + <
W122
05 1
4/2
21. 23 EZ
Initialization
1= 2
MI-LCQP problem
MI-LCCQP-rraph
The WL test (Algorithm 1)
Figure 6. Example for proving Proposition D.2
Proof. Consider the example in Figure 6, for which the final stable partition is I = (1), (2) and J = (1,33), It not GNN-solvable since the class 31 in J has two elements. However, it is GNN-analyzable since An = A13 =1 and A21 = A23 =
D.2. Frequency of GNN-analyzability and GNN-solvability
mm It can be proved that a generic MI-LCQP-graph in MMLLCOP is GNN-solvable almost surely under some mild conditions. Intuitively, c E Rn is randomly sampled from a continuous distribution with density, then almost surely holds that I # Zz' for any j # j', which implies that the vertices in W have different colors initially and always, if there are no collisions of hash functions.
23

---

Expressive Power of GNNs for QP
Proposition D.3. Let P be probability measure over GMI-LCOP such that the marginal distribution P. of IR has density. Then LOGE solvablll 1.
Proof. Since the marginal distribution P. has density, almost surely we have for any * j' that
cj * cy
Cg. Cg
CO.
C.S * cjy
22 0,
where we assumed that no collisions happen in hash functions. Therefore, any j.J' E W with + j' are not the same class of the final stable partition (I, which proves the GNN-solvability.
Im. As direct corollary of Proposition D.1 and Proposition D.3, a generic MI-LCQP graph in MI-LCOP must also be GNN- analyzable.
Corollary D.4. Let P be a probability measure over LOP such that the marginal distribution Pe of TR" has density. Then PiGMI-LCOP E I analyzaalle 1.
Frequency of GNN-friendly instances in practice. While MI-LCQPs are almost surely GNN-solvable under some assump- tion, however, in practice, particularly with manually designed instances (as opposed to randomly generated ones). hard instances GGNN-insolvable or even inanalyzable) does occur. We performed experiments on QPLIB (httss//qppli.zibb zib.de/). In this dataset, 19 out of 96 binary-variable linear constraint instances are -an-vvislv Furthermore, when coefficients are quantized (which increases the level of symmetry in the dataset), the ratio of GNN-insolvable instances increases. (shown in the table below)
Quantization refers to rounding continuous or high-preciste 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 instances at different quantization step sizes (0.1, 0.5, and 1).
While -NNiinsolvable instances are generally challenging for GNNs, a significant proportion of these hard instances are GNN-analyzable. For example, with a quantization step size of (rounding coefficients to integers), 36 out of 63 GNN-insolvable instances are GNN-analyzable. According to our theorems, GNNs can least predict feasibility and boundedness (objective value) for such instances. Detailed results are as follows:
Table 2. Frequency of GNN-analyyyiiiity and solvability
Original data set
Step size 0.1
Step size 0.5
Step size
Total
96
96
96
96
GNN-insolvable
19
23
42
63
GNN-insolvable but analyzable
0
1
19
36
How to handle bad instances? If a dataset contains a significant proportion of GNN-insolvable or -anniinnnl instances (highly symmetric structures), we suggest two potential approaches: (I) Adding features: Introducing additional features can differentiate nodes in symmetric graphs. For example, adding random feature to nodes with identical attributes ensures they are no longer symmetric (Sato et al., 2021). (II) Using higher-order GNNs: These models can distinguish nodes that standard message-passing GNNs cannot, enhancing their expressive power (Morris et al., 2019). In particular, we highlight the potential of k-hop GNNs (Feng et al., 2022), which have greater expressive power than message- message-passing GNNs (MP-GNNs). the proof of Proposition 4.2 (Appendix B), we construct MI-LCQP instances with different optimal objective values that MP-GNNs cannot distinguish. However, 3-hop GNNs are able to distinguish them. When these instances scaled to graphs with 10 variables and 10 constraints (resulting in one 20-node connected graph vs. two disjoint 10-node graphs), 3-hop GNNs fail while 5-hop GNNs succeed. This observation is investigated in (Chen et al., 2025) on general graphs and suggests that increasing lt reduces the number of indistinguishable cases and may enhance solvability.
E. Extension to quadratically constrained quadratic programs
general quadratically constrained quadratic programming (QCQP) is given by
1 Qz Tx CCTa s.t. 5" P. af x s b, 1sis m, 15s5u,
min =ER" 2"
(19)
24

---

Expressive Power of GNNs for QP
where P; E Ruxx symmetric, C, 4g RR" IR, e (R J (-oo))" and a (R (+oo))" We denote
A
Q1
aml R for consistent notation with (2).
E.1. Graph representation and GNNs for QCQPs
Graph representation for QCQPs The QCQP-graph for representing (19) is based on the LCQP-graph introduced in Section 2. More specifically, The QCQP graph can be constructed by incorporating the information from P (Pi, , into the LCQP graph:
The multiset fi. is viewed as hyperedge with weight (H) for each E and j.J' E W, where j = jj' is allowed.
We use Pocop denote the set of all QCQP-graphs with m constraints and n variables.
GNNs for solving QCQP Note GNNs -cQpps that iterate vertex features with message-passing mechanism, which does not naturally adapt to the hyperedges in QCQP graphs. Thus, one idea is to add edge features for each pair (i,j), E V,j e W. We describe the GNN architecture for QCQP tasks in detail as follows.
The initial layer computes node features si 19 and edge features ef via embedding:
of fo' (u:) for E V.
19 10' (11z) for j W. and
c = (Ai) for i E V.je E W.
The 1-th pesssag--passing layers = 1,2,.... L) update the node features using neighbors' information:
o = ( Ejew of , foriev.
1 1 (t)-) Eiev (
(st . Eyew Qira (1)6((177)) for j E W, and
d = f. (c) Eyew (P)) (t)) )) for E V.W..
Finally, there are two types output layers. The graph-level output computes a single real number for the whole graph
y ri (Eiev s Ejew t5) E R.
and the node-level output computes vector y IR" with the j-th entry being
y; = T2( (Erev st Ejew 14).
We use Focqp (or Fd(Oo) to denote the collection all message-passing GNNs with graph-level (or node-level) outputs that are constructed by continuous fg f .10 fÝ .JW .SF.0 oh gl"" of .i (1 s L), and rı (or r2).
E.2. Universal Approximation of GNNs for QCQPs
For QCQPs, we still consider the three target mappings. i.e., the feasible mapping Press -ocop + {0,1). the optimal objective value mapping oobj Goooe R U {+oo), and the optimal solution mapping Pabj that computes the unique optimal solution with the smallest f2-m of feasible and bounded QCQPs with Q, P. > 0, 1, 2, m. The main results that GNNs can universally approximate these three target mappings are stated as follows.
om,a Assumption E.I. P is a Borel regular probability measure on G
TTee space gm.e equipped with the subspace topology induced from the product space ((A, b, c, Q, P, u, o) R RT c TR. Q E Rexn P (Raxn)m m 1 (RU (-oo))) (R u (+oo))*) ]. where all Euclidean spaces have standard Eudlidean topologies, discrete spaces { (-oo 00) and [+00} have the discrete topologies, and unions are disjoint unions.
25

---

Expressive Power of GNNs for QP
Theorem E.2. Let IP be probability measure satisfying Assumption E.I and PPQ = 0] PIP,
1, i 1,2,..... m.
For any O, there exists F LMLL such that
P P o Deass (Gooo) <6
Theorem E.3. Let IP be probability measure satisfying Assumption E.I and IPQ > 0] P[ 1, 1,2,..... m.. For any 0, there exists F1 Facqe such that
[P[ Fi (Gocor)> # (Coco)))) <.
Additionally, if Pf (Gocop) IR] = 1, for any 8 O, there exists F2 Focop such that
P ([ & Lon 6] <E
Theorem E.4. Let IP be probability measure satisfying Assumption E.I and PPQ = 0] = PPP 0J = i= ..2, m.
For any e, > O, there exists Fw & FCCO such that
IP (W - Pan > <e.
Similarly, the proofs of Theorem E.2, F.3, and E.4 are based showing that the WI. test associated with the GNN classes FacQp and QCQP have sufficiently strong separation power to distinguish QCQP problems with different properties. We will present and prove such separation results (Theorem E.5, Theorem E.6, and Corollary E.7) in the rest of this subsection, and do not repeat the same arguments as described in the Proof of Theorem 3.3 and Theorem 3.4.
We state in Algorithm the WL test for QCQPs. For QCQP-CQQPPEETPPP -ggpphs Gocop, Gycor E &OCOP.
1. We say Gocop ~ Gooop if (C., D (C, D and (.f. B3= = M.O. Bi=o hold for all e N and all hash functions.
2. We say Gooop W. GoCOp if CC A = C.O b and C.. O VjE .I.2....,.. for all L e N and m).
all hash functions.
Algorithm 3 The WL test for QCQP-Graphs
Require: A QCQP-graph G WV, A,Q, Hv, Hw) and iteration limit 0. 1: Initialize with
ca.. = hash(u;), C..W = hash(w,), Ci hash(Aig).
2: for 1,2, 1,2,... ... do
3: Refine the color
C.V. hash
c C.-LV
Σ
hash (CI-I. c
(1-.W,,1,118 cl118)
JEW
C.. hash
c G1-1. Σ
hash (c.-1, B.vYCol-.. cl-1.E)
Σ j'ew
hash ( C.-1.
C..
hash
C1-1.B Σ
hashh 1.W.
1j
J'EW
4: end for
L. W By- 5: return The multisets containing all vertex colors C.C.V. oi fC,
Theorem E.S. Given Googe, Gocor E Gooup with Q, Q. for all i E (1,2,..., m)) if Gooor ~ Gycop. then
feas (Goco)) = 1e (Ggoge) and aay Googo) a (Gocop).
26

---

Expressive Power of GNNs for QP
Proof. We only show the proof of 4 dayy (Gocop) (aay(Ggo and icess (Gocop) Pteas (Gooop) will be direct corollary.
Let Goooe and Gycop the QCQP-graph associated to (19) and
1 x' T = s.t. ,0 x P.x 2
1
min ZER"
+ 0 x isis is
(20)
2-
Suppose that there are no collisions of hash functions or their linear combinations when applying the WL test to G and G and there no strict color refinements in the L-th iteration. Since G and G are indistigguishable by the WL test, after performing some permutation, there exist I = {71, .,. ] and J = J2.,J2..... J.) that are partitions of n), respectively, such that the followings hold:
1.......m. and
ct.y C.V. if and only if i E Ip for some p E {1, .1,
c.. C.V. if and only if i, E Ip for some p E {1. 2, .......... .).
C.. C.V. if and only i, Ip for some p E {1, 2,.,................ 8).
cj. J.W if and only if j.j Jg for some q {1. ..... .t].
cf. G &..W if and only if j.j E Jg for some q (L, 2, ............ .t.
Gf.W = - C...W if and only if j.y E Jg for some E {1.2. ...,..., .t.
The followings hold by the same arguments as in the proof of Theorem A.2:
b, by and is constant over i Ip. for any p {1,2......5)
(c), (, uz) (cj, fj. ú.)) and is constant over j E Jg for any a (1,2,...,44
$) and E {1,2..... t) EjE,, Aij = EsE,, Aig and is constant over i Ip- For any p E (1,2...., $) and g (1, t). Eier, Aij Eier, Acg and is constant over j E Jq-
For any E
For any q.46 E D,E,,,,,,,,,, Qi Eyer, Qiy and is constant over j E Jg.
1. Eye,,
Fix E (1,2..... $) and q. E 2,, t}. For any j.م E Jq. we have
C..W C..
Σ hash (CL- ,
Σ hash (Ch-LIV ,ry CL-LEE)
iEV
SEV
(Che :iE 10}} = cf1 : Ip ]]
Σ hasls : E Ip
jeEw
(P.ly hash Ch 1, :iElo
JeW
(P)is :iEl
(Pilggrii
Σ E(P)ir E (P.)ppp
IEI,
iel,
27

---

Expressive Power of GNNs for QP
where jرJ E Jg. This concludes that One can do similar analysis for C..W = C.. and Cf. =.y
Σ EPiiy Σ Σ(P))s JEE,
J'E
is constant jver j E Jg-
Let x E R" be any feasible solution to (19) and define & E R" via ãz = yo p E {1.2...., it follows from
1 Jo
Eyes, Ty for j E Jq. For any
P. + a. x s bi. i l.
r
2
and Lemma A.4 that
Tp iELp
1
Σ
8,
p vely
1 Σ
b: 2
2"
1 T
[p1
1 Σ Ps
x+
Tp iEIp
1
ai
x
SEI,
T
T
Σ
Ps
++
Σe a
i =
1 T
Σ
Ps
Σ
a
a.
2
[4p)
1p iEl,
2
[1
Ip
iEl,
iEl,
Note that for any i E Ip and any q E E11,2, ,,,,,,,
(t,, we have
CN. = OL.Y
Σ hash
,0%-118) = Σ hash
(CH-L,W, -LL-I.E)
JEW
JEW
(OOE :j E J1)} - 11/ :j E Je 11
Σ (C--111) j E Ju
PEW
Σ
(P&) hash : E Jnj 101)
N'EW
Ja 11 - 11
11-
(P)) :j Jo
Σ
(Pe)s) Jg
NEJ
Σ Σ
(Piss- = Σ (P:)))
jEJ, JEJ
jEJ
Therefore, it holds that
1 L Pv
1 PTa Vie
-
[pl selp
and hence that
P by ViEl.
We thus know that è is feasible solution to (12). In addition, we have
x 2 La = - T Q7 + ēT a,
N" Qr + 1r
which implies that L (GQcOo)))) > 4 wby (Gyoor). The reverse direction Dong (Gycoe) S (ocy(G is also true and we
can conclude that & eay (Goco) = D (gooor).
28

---

Expressive Power of GNNs for QP
Theorem E.6. For any GoCOp, Gooop &Qoop with GoCOP Gocop, then there exists some permulation ow E Sn such that & (Gocop) ow (Dsoao (GoCQ))) Furthermore, if Goooo R Gooop, then sol (Gooop) sett (GgGo)))
E m) that are feasible and bounded, if
Proof. Based on Theorem E.5, Theorem E.6 can be proved by the same arguments in the proof of Lemma B.4 and Corollary B.7 in Chen et al. (2023a), which is included in the proof of Theorem A.2.
Corollary E.7. For any Gocop Socop that is feasible and bounded and any j.j' E (1,2,...,, if C Cj. holds for all L E M+ and all hash functions, then sol (Gqcop); sol (Gocop))
Proof. Let Gocor be the QCQP-graph obtained from GQOop by relabeling j as j' and relabeling j' as j. By Theorem E.6, we have (GooO)))))) = . (Goco))) which implies Paol (Gocor); = P Ba (Gocor); = Paal (GQCO))))))
F. Potential extension to polynomial optimization
Beyond QCQPs, the hyperedge- based approach may extend more complex settings such polynomial optimization. We outline a high-level idea: consider monomial term fj..ja....... "h 2J ..- Zy in polynomial objective or constraint,
If the term appears in the objective, we model it hyperedge [ [wj; -......, Wi, B: if it appears in the i-th constraint, we model it as { (t, Whi Wjz..... Wja J. We conjecture that GNNs operating properties of convex polynomial optimization. As supporting evidence, our QCQP analysis in Appendix E shows that second-order hypergraph GNNs already achieve universal approximation for core properties, suggesting promise for broader generalizations.
such hypergraphs
approximate key
G. Implementation details and additional numerical results
In this section, explain how formulate the optimization problems used in the numerical experiments and how to randomly generate problem instances. We mainly follow the settings of OSQP (Stellato et al., 2020) with slight modifications.
G.1. Random LCQP and MI-LCQP instance generation
Generic LCQP and MI-LCQP generation. For all instances generated and used in numerical experiments, set 10 and = 50, which means each instance contains 10 constraints and 50 variables. The sampling schemes of problem components are described below.
Matrix Q in the objective function. We sample sparse, symmetric and positive semidefinite Q using the make_ make_sparse wwwrsspaaesppee spd__atrrixxxx_pp__aaa__aapa____ matrix function provided by the scikit-leaxe Python package, which imposes sparsity the Cholesky factor. We set the pha value to 0.95 so that there will be around 10% non-zero elements in the resulting Q matrix.
The coefficients in the objective function: Cj (00,0.12).
The non-zero elements in the coefficient matrix: Ai NN(0 1). The coefficient matrix A contains 100 non-zero elements. The positions are sampled randomly.
The right hand side of the linear constraints: b, 10,
The constraint types o. We first sample equality constraints following the Bernoulli distribution (ernoull((033). Then other constraints takes the type S. Note that this is equivalent sampling and 2 constraints separately with equal probability, because the elements in A and 6 sampled from symmetric distributions.
The lower and upper bounds of variables: I5, uy (O0 10?). We swap their values i, > uy after sampling.
(MI-LCQP only) The variable types are randomly sampled. Each type (continuous or integer) occurs with equal probability.
29

---

Expressive Power of GNNs for QP
After instance generation is done, collect labels, i.e., the optimal objective function values and optimal solutions, using of the commercial solvers.
LCQP instance generation for generalization experiments. In this setting, we only sample different coefficients c for different LCQP instances. We sample other components only once, i.e., Q. A, b, L, and o in (2), and keep them constant and shared by all instances. We also slightly adjust the distributions from which these components are sampled as described below.
Matrix Q. We follow the same sampling scheme above.
The coefficients in the objective function: Cj (O 1/n).
The non-zero elements in the coefficient matrix: Ai (0 1/n). The coefficient matrix A contains 100 non-zero elements. The positions are sampled randomly.
The right hand side b of the linear constraints: 6, (0, 1/n).
The constraint types o. We follow the same sampling scheme as above.
The lower and upper bounds of variables: (3, Uj N00, 1). We swap their values if >> uy after sampling.
For the generalization experiments, we first generate 25,000 LCQP instances for training, and then take the first 100/500/25,000 ,000001000000000 instances to form the smaller training sets. This ensures that the smaller training sets are subsets of the larger sets. The test contains 1,000 instances that are generated separately.
Portfolio optimization formulation and instance generation. The portfolio optimization problems formulated below.
min = 1 T Dr +
1 p x
(21)
2
2
s.t. y = Fx, 1 1x=1,
x 20
Here: x E IR and E R' are the optimization variables, D E R a diagonal matrix with non-negative diagonal elements, F E gixs the factor modeling matrix. We generate portfolio optimization instances following the scheme below.
We set = 50 and / = 5, resulting in LCQP instances with m 6 constraints and 55 variables.
The diagonal elements of D are independently sampled from uniform distribution: D;: (O, vt). D is then used to
form the matrix Q -2²1)
Tt
The coefficients μ in the objective function: ~ NN 1).
The non-zero elements the factor modeling matrix F: Fij ~ (0, 1). The coefficient matrix F contains 25 non-zero elements. The positions are sampled randomly.
SVM optimization formulation and instance generation. The support vector machine optimization problems are formulated as below.
min 2,
=x T T
(22)
s.t. t diagly) Dr +1, t20
Here I and / RR the optimization variables, D Rix is the data matrix, y IR' is the binary label vector, and À is hyperparameter which we set to 1/2. We generate SVM optimization instances following the scheme below.
We set s = 5 and = 50.
The non-zero elements in the data matrix D: Diş ~ N(-00.1.0.1 for i t/2; Dy ~ NV otherwise. The coefficient matrix D contains 100 non con-zero elements. The positions are sampled randomly.
The binary label vector y: Yi for i < 1//2: y: otherwise.
30

---

Expressive Power of GNNs for QP
Training Validation
10-2
Relative error
Relative error
10-2
10-4
10-6
Training
Validation
10-3
100
5000
10000 15000 20000 25000
100
5000
10000 15000 20000 25000 Number of instances
Number of instances
(a) Fit Potj for LCQP
(b) Fit 2 for LCQP
Figure 7. Training and errors when training GNNs with emhedding size of 512 on different numbers of LCQP problem instances fit da and sol-
G.2. Details of GNN implementation
We implement GNN with Python 3.9 and TensorFlow 2.16.1 (Abadi et al., 2016). Our implementation built by extending the GNN implementation in Gasse et al. (2019).² The embedding mappings fo eW are parameterized as linear layers followed by non-linear activation function; (N ./" .9",."" ,9 J and the output mappings v1, are parameterized as 2-layer multi-layer perceptrons (MLPs) with respective learnable parameters. The parameters of all linear layers are initialized as orthogonal matrices. We use ReLU as the activation function.
In our experiments, train GNNs with embedding sizes of 64, 128, 256, 512 and 1,024. We show in Table 3 the number of learnalle parameters in the resulting network with each embedding size.
Table 3. Number of learnable parameters in GNN with different embedding sizes.
Embedding size
Number of parameters
64
112,320
128
445,824
256
1,776,384
512
7,091,712
1,024
30,436,352
G.3. Details of GNN training
We adopt Adam (Kingma & Ba. 2014) to optimize the learnable parameters during training. We use an initial learning rate of 5 10-4 for all networks. We set the batch size 2,500 or the size of the training set, whichever the smaller. each mini-batch, we combine the graphs into large graph to accelerate training. All experiments conducted on single NVIDIA Tesla V100 GPU.
We use mean squared relative error as the loss function, which is defined as
Fl (G) (G) max ( 1)2
Lg(Fw)= EG-g
(23)
where Fi is the GNN, G is mini-batch sampled from the whole training set, a problem instance the mini-batch G. and (G) is the label instance G. During training, we monitor the average training error in each epoch. the training loss does not improve for 50 epochs, will half the learning rate and reset the parameters of the GNN to those that yield the lowest training error so far. We observe that this helps stabilize the training process significantly and can also improve the final loss achieved.
"ee https::////........ / //t::://tttttt wwtp://oo/////////oo
31

---

Expressive Power of GNNs for QP
G.4. Generalization results LCQP
Figure 7 shows the variations of training and test errors when training GNNS of embedding size of 512 on different numbers of LCQP problem instances. We observe similar trends for both prediction tasks, that the generalization gap decreases and the generalization ability improves more instances used for training. This result implies the potential of applying trained GNNs to solve QP problems that are unseen during training but are sampled from the same distribution, as long as enough training instances are accessible and the instance distribution is specific enough (in contrast to the generic instances used in experiments of Figure 2 and 3).
G.S. Details for on Maros-Meszaros test set
To show the fitting ability of GNNs on more realistic QP problems, we train GNNs on the Maros and Meszaros Convex Quadratic Programming Test Problem Set (Maros Mészáros, 1999). which contains 138 quadratic programs that are designed 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 collect the optimal solutions and objective values of the test instances using an open-sourced QP solver called PIQP (Schwan et al., 2023), which benchmarked to achieve best performances the Maros Meszaros test set among many other solvers (Caron al., 2024). PIQP solves 136 problem instances successfully, which are then used to train four GNNs with embedding size of 64, 128, 256, 512. The training protocol follows the experiments using synthesized QP instances in Section 5.
32


Reviews:
[{"review_id": "fcThANSMhW", "reviewer": "Reviewer_ADeR", "summary": "The paper establishes that message-passing GNNs can express the feasibility, optimal value and optimal solution of convex linearly constraint quadratic programs as well as of mixed-integer linearly constraint quadratic programs, if they adhere to certain conditions often true in practice. Negative results are provided for mixed-integer linearly constraints quadratic programs in general. Numerical experiments validate the approximation results.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__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.\n\n__Reply to \"Claims And Evidence\":__ We will clearly state the convex assumption in the revision:\n1. **Page 2 (Contributions):** Clarify convexity assumption and nonconvex counterexample  \n2. **Page 4:** Rename Section 3 → \"Universal approximation for *convex* LCQPs\"  \n3. **Page 5:** Add nonconvex LCQP counterexample showing GNN indistinguishability despite different optima.\n\nConsider a convex LCQP\n$$\\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,$$\nand a nonconvex LCQP\n$$\\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.$$\nThese two LCQPs are indistinguishable by GNNs, and they have different optimal objective/solution.\n\n__Reply to \"Theoretical Claims\":__\n\n__(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).\n\n__(II)__ We acknowledge this conclusion is more synthetic, hence its appendix placement. In Section 4.3, we'll clarify:  \n1) GNN-solvable/analyzable cases dominate *under specific distributional assumptions*  \n2) *Real-world* datasets (e.g., QPlib) may contain GNN-insolvable cases (Appendix D)\n\n__Reply to \"Experimental Designs Or Analyses\":__\n\n__(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.\n\n__(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.\n\n| GNN | BS=1 | BS=10 | BS=100 | BS=1000 | OSQP |\n|---|---|---|---|---|---|\n| Time | 53.62±16.72 | 5.37±1.87 | 0.504±0.142 | 0.089±0.002 | 4.48±3.62 |\n\n__(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.\n\n__(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.\n\n__(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.\n\n| emb_size | 128 | 256 | 512 |\n|---|---|---|---|\n| objective | 3.28E-04 | 9.05E-07 | 4.00E-07 |\n| solution | 6.57E-01 | 6.72E-01 | 6.06E-01 |\n\n__Reply to \"Other Comments Or Suggestions\":__ We will revise accordingly.\n\n__Reply to \"Questions For Authors\":__ \n\n__(I)__ The difficulty hierarchy differs by problem type:  \n\n- **LCQP:** feas (Assump 3.1) < obj (+convexity) < sol (+feasible/bounded)  \n\n- **MI-LCQP:** feas/obj (Assump 4.5 + GNN-analyzable) < sol (+GNN-solvable) \n\nConvexity isn't required for MI-LCQP due to inherent integer non-convexity. \n\n__(II)__ Yes, it is presented at the beginning of our rebuttal.\n\n__(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. \n\n*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.\n\n__(IV)__ We will correct it.\n\n__(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).", "claims_and_evidence": "In the introduction, it is claimed that GNNs can accurately predict the feasibility, optimal value and solution of a linearly constraint QP. However, the last two claims require the additional assumption of a convex quadratic program (i.e., positive semidefinite $Q$). This should be reflected in the claim. Other than this, all claims are clear and provided with convincing evidence.", "methods_and_evaluation_criteria": "Yes, for details see Experimental Designs Or Analyses.", "theoretical_claims": "I checked the argumentations in the main draft, I did go over some arguments in the appendix, but did not check the proofs in the appendix in detail.\n\nTwo minor issues:\n\n**(I)** Lines 357-360 (left column) reads as if in the GNN-solvable case, GNNs can approximate the optimal solution, but not feasibility. Given Prop. D.1, this should not be true. I would make this more clear.\n\n**(II)** I think the proof leading to the statement that GNN-solvable and GNN-analyzable instances make up the majority of the MI-LCQP set could be assumed very synthetic. Coefficients in the objective would never be set to irrational numbers, it is rather reasonable to even assume that in practice $c$ may be the same for many $j$. The empirical investigation on QPLIB is interesting and supports that the assumption of randomly sampling $c$ from $\\mathbb{R}^n$ and using properties of $\\mathbb{R}$ seems too strong to explain the real-world occurrences of GNN-solvable/analyzable instances.", "experimental_designs_or_analyses": "Yes, some issues:\n\n**(I)** I'm not convinced of omitting the experiments where GNNs are used to fit $\\Phi_{feas}$ based on arguing that feasibility falls to the case of LP and MILP (Chen et al. 2023). This is as due to the fact that the input graph representing a LCQP / MI-LCQP is still different to the one for an LP / MILP and thus, the empirical behavior of a GNN on the changed input graph is still interesting.\n\n**(II)** Fig 2 to 4 and Tabl. 1 are missing standard deviations.\n\n**(III)** The experimental details mention that four GNNs are trained and averaged over all instances during training. I would have assumed that the same experiments are also repeated for several seeds, which seems not to be the case.\n\n**(IV)** While for showing approximation results, it is not necessary for the GNNs to be applied to unseen instances, I would be curious about how well the GNNs actually generalize to unseen instances. This is slightly touched upon in F.4 where results on the validation set are shown, but no results on a held-out test set are provided. It would be easy to generate a few more random instances to test this behavior.\n\n**(V)** GNNs expressiveness results are not tested on practical MI-LCQP instances. Have you considered GNN-solvable/analyzable instances from QPLib?", "relation_to_broader_scientific_literature": "As universal approximation of message-passing GNNs has been investigated for LPs and MILPs, extending the study to QPs seems natural and important, especially as there are several works, also cited in this work, on empirically learning to solve QPs using GNNs.", "essential_references_not_discussed": "All essential related work has been discussed.", "other_strengths_and_weaknesses": "The paper is written in a very clear fashion and good to follow. As the results on LCQPs and MI-LCQPs have not been known, the results are significant. The idea to the research question may not be the most original, as after this problem has been approached for LPs and MILPs by Chen et al. (2023a, b) it is natural to extend the question to other optimization problems. However, it required new ideas to proof and is still an important and significant result, providing important theoretical grounding and guiding for the empirical developments in the field.", "other_comments_or_suggestions": "* The definition of $\\Phi_{sol}$ for an MI-LCQP is quite hidden in the mids of App. C, it would be helpful to make it more prominent.\n* In Section 2, the mappings $g$ and $r$ are used before they are introduced.\n* Define the $\\succeq$ operator in Line 154 (second column). Here it is used for a positive semi-definite matrix. However, in the ML literature, it is sometimes used for matrix inequalities.\n* Line 047 \"with with\"\n* Section 3 header misses a \"i\" in \"Universal\"\n* Line 061 and 062, use \\citet for Wang & Yu's works\n* Line 169/170 \"there always be\" -> \"there always is\"", "questions_for_authors": "**(I)** It seems that predicting the optimal objective value / solution is more difficult than predicting if an LCQP is feasible (for the first, the requirement of convexity is needed, for the second not). Can you comment on how the three problems relate to one another in some sense of difficulty hierarchy? \n\n**(II)** Do you have a negative result for non-convex LCQPs?\n\n**(III)** In Lines 188-192 (second column) the authors state that any two LCQP-graphs that are indistinguishable by the WL test, or equivalently by all GNNs, must have identical optimal value and solution. As Xu et al. (2019) showed that message-passing GNNs are upper bounded by the 1-WL but not necessarily reach its expressivity, does the proposed family of GNN architectures reach 1-WL expressivity?\n\n**(IV)** Section 2, node-level output: There is some issue with the definition of $y$. It is indexed by $j$ even though defined for each $i \\in V$. Shouldn't it be defined for each $j \\in W$?\n\n**(V)** Can you give some intuition on what \"GNN-analyzable\" means?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Dcgonlji7U", "reviewer": "Reviewer_PHmc", "summary": "This paper provides a theoretical analysis to investigate the expressive power of standard Message-Passing GNNs (MPGNNs) in solving the Linearly Constrained Quadratic Program (LCQP) and Mixed-Integer (MI) LCQP tasks. Specifically, the paper focuses on three mappings\nwith MPGNNs: feasibility mapping, optimal objective mapping, and optimal solution mapping. The theoretical findings are well-validated with a comprehensive experiment.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__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.\n\n__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.\n\nThis 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.\n\nWhile 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.\n\nFinally, 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.\n\n__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:\n\n1. **Enhanced Counter-Examples**  \n   - Chen et al. (2023b) only show feasibility counterexamples\n   - We provide richer counterexamples (feasibility, optimal objective, and optimal solution) for MI-LCQPs\n\n2. **New Theoretical Connections**  \n   - Connect the expressive power of the WL test to key properties of (MI-)LCQPs\n   - Novel analysis of quadratic terms (Appendix A)\n   - Prove GNN approximation under weaker assumptions (GNN-analyzability vs GNN-solvability). Chen et al. (2023b) always assume GNN-solvability.\n\n3. **Hypergraph Innovations**  \n   - Develop novel hyperedge representations and analysis for QCQPs (Appendix E)\n   - Significant technical differences from Chen et al. (2023a; b) that do not involve hypergraphs.\n\nWhile 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.\n\nAdditionally, we agree that generalization analysis is crucial, and will highlight this as key future work in the revision.\n\n__Reply to Weakness:__ It is the latter. We will further clarify the convex assumption in the revised manuscript:\n1. **Page 2 (Contributions):** Clarify convexity assumption and nonconvex counterexample  \n2. **Page 4:** Rename Section 3 → \"Universal approximation for **convex** LCQPs\"  \n3. **Page 5:** Add nonconvex LCQP counterexample showing GNN indistinguishability despite different optima.\n\nConsider a convex LCQP\n$$\\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,$$\nand a nonconvex LCQP\n$$\\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.$$\nThese two LCQPs are indistinguishable by GNNs, and they have different optimal objective/solution.\n\n__Reply to \"Other Comments Or Suggestions\":__ We'll fix these typos in the revision.\n\n__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.\n\nFor 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.", "claims_and_evidence": "Yes. The claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. I have checked the proofs listed in section 3 and section 4.", "experimental_designs_or_analyses": "Yes. The paper conducts neumerical experiments to validate the GNN's expressive power to fit optimal objective mapping and optimal solution mapping on the LCQP amd MI-LCQP. The authors utilize both real-world datasets and synthetic dataset. For the experiment results of real-world datasets (Appendix F.5), in general, the training errors are high. This may indicate that standard MPGNNs may struggle with real-world QPs. It would be better to provide a discussion to analyze why.", "relation_to_broader_scientific_literature": "The paper explore the MPGNNs' expressive power for LP and MILP to the LCQP tasks. Specifically, the paper utilizes the Weisfeiler-Lehman (WL) test to prove that separation power (Section 3, Appendix A) for non-linear QP. In addition, the differences\nbetween LCQP and MI-LCQP universality (Theorems 3.2–3.4 vs. Propositions 4.1–4.3) are well-explained, particularly the counterexamples that demonstrate MPGNNs limitations in mixed-integer settings.\n\nHowever, Theorems and their proofs in sections 3 and 4 for QP and MIQP are almost direct extensions from (Chen et al. 2023a;b) which focused on LP and MILP, making this work incremental to previous works and thus may lack novelty and non-trivial contributions.\n\nIn addition, high expressiveness of the hypothesis space does not necessarily lead to better generalization performance in theory (universal neural models are in fact easy to acquire). It would be a great plus to complete the theoretical analysis by providing generalization bounds.", "essential_references_not_discussed": "None witnessed", "other_strengths_and_weaknesses": "Strengths: \n\n1)Though this work mainly focuses on the theoretical part, the identification of \"GNN-friendly\" subclasses (Definition 4.4) and the criteria for verifying them (Section 4.2) provide insights into real-world tasks; \n\n2) The numerical validation that was conducted on both synthetic and benchmark datasets (Maros-Meszaros) strengthens the practical effect.\n\n\nWeakness: In the preliminaries section, Q is defined to be symmetric, however, it’s defined to be positive semidefinite in Theorem 3.3 and 3.4. It’s confusing whether “(Q is positive semidefinite almost surely)” in Theorem 3.3 refers to a real-world fact or the previous condition.\nIf it’s the latter, then the theorems do not guarantee the affirmative answer when Q is symmetric but not positive semidefinite. If it’s the former, the fact should be stated clearly out of the theorem.", "other_comments_or_suggestions": "The writings could be improved, e.g., typos. (e.g. Line 668 “Fixe”) and having legends for figures.", "questions_for_authors": "The paper proves the expressive power limitations of standard MPGNNs for LCQP problems through WL equivalence (Theorem 3.2–3.4). Recent works have shown that high-order or hypergraph GNNs offer greater expressive power than standard MPGNNs[1]. Is it possible to\napply the approach used in the paper to these GNNs to address such limitations? In addition, for Quadratically Constrained Quadratic Programs (QCQP) discussed in Appendix E, constraints may involve interactions between multiple variables (e.g., xixj <= b), and hyperedges in a hypergraph can naturally represent such relationships. It would be interesting to investigate the possibility of providing a universal analysis for LCQP and QCQP.\n\n[1] Feng, Jiarui, et al. \"How powerful are k-hop message passing graph neural networks.\" Advances in Neural Information Processing Systems 35 (2022): 4776-4790", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sw4AJJpfvA", "reviewer": "Reviewer_tWyf", "summary": "This work proves that message-passing GNNs can universally represent fundamental properties of quadratic programs, including feasibility, optimal objective values, and optimal solutions. They also prove that GNNs are not universal for mixed-integer problems.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__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.\n\n__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.\n\n__Reply to Weakness 1:__ We will include a more detailed comparison with Wu et al. (2024) in the revision.\n\n* Methodologies differ: Wu et al. use a tripartite graph for general QCQPs, while we use a variant of bipartite graph tailored to (MI-)LCQPs. \n* 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.\n\nNotably, 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.\n\n__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.\n\n[2] Li et al. \"On the Power of Small-size Graph Neural Networks for Linear Programming.\" NeurIPS 2024.\n\n__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: \n\n- $(w_{j_1},...,w_{j_k})$ for objectives  \n- $(v_i,w_{j_1},...,w_{j_k})$ for constraints  \n\nOur 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.\n\n__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.\n\n__Reply to Question 2:__ Compared to standard NNs, GNNs provide some unique theoretical advantages:\n\n* __Permutation Invariance/Equivariance__  \n   - In QPs, swapping variable/constraint order should permute solutions accordingly. \n   - __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.\n\n* __Scalability to Varying Sizes__\n   - 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.  \n   - Standard NNs need fixed input/output dimensions, requiring architectural changes for size variations.\n\nThese points were briefly mentioned at Lines 64–67 (left column), and we will expand them in the revision.\n\n__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:\n\n1. **Enhanced Counter-Examples**  \n   - Chen et al. (2023b) only show feasibility counterexamples  \n   - We provide richer counterexamples (feasibility, optimal objective, and optimal solution) for MI-LCQPs\n\n2. **New Theoretical Connections**  \n   - Connect the expressive power of the WL test to key properties of (MI-)LCQPs.\n   - Novel analysis of quadratic terms (Appendix A)\n   - Prove GNN approximation under weaker assumptions (GNN-analyzability vs GNN-solvability). Chen et al. (2023b) always assume GNN-solvability.\n\n3. **Hypergraph Innovations**  \n   - Develop novel hyperedge representations and analysis for QCQPs (Appendix E)\n   - Significant technical differences from Chen et al. (2023a; b) that do not involve hypergraphs.\n\nWhile 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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "This work also provides NN/GNN universality and complexity for solving convex quadratic programs [1].\n\n[1] Yang, L., Li, B., Ding, T., Wu, J., Wang, A., Wang, Y., ... & Luo, X. (2024). An Efficient Unsupervised Framework for Convex Quadratic Programs via Deep Unrolling. arXiv preprint arXiv:2412.01051.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is well-written.\n2. The theoretical results on GNN universality for QP are solid and important for its applications.\n\nWeakness:\n1. The authors mention a concurrent work by Wu et al. (2024) that explores a tripartite graph representation and its associated GNN for QCQP, investigating its expressive power (line 105). Since convex QP is a special case of QCQP, the authors should compare and discuss their results and methodology with those of Wu et al. (2024).\n2. Beyond establishing universality, the parameter complexity of the GNN is not addressed. Understanding this complexity is crucial for evaluating its superiority compared to standard neural networks, which are also universal approximators for continuous mappings.\n3. Although the framework is demonstrated for LP and QP, it is unclear whether this graph representation approach can be generalized to more complex problems, such as polynomial optimization. Clarification or extension to these cases would strengthen the paper's contribution.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Are there any real-world MI-LCQPs that are GNN-friendly?\n2. Is there any theoretical advantage to using GNNs instead of regular neural networks when solving QPs?\n3. Could the authors clarify the specific methodological contributions of this work compared with the established methods in [1,2]?\n\n[1] Chen, Z., Liu, J., Wang, X., Lu, J., and Yin, W. On representing linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations, 2023a.\n[2] Chen, Z., Liu, J., Wang, X., Lu, J., and Yin, W. On representing mixed-integer linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations, 2023b.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ziKn8GunSa", "reviewer": "Reviewer_4Q8A", "summary": "In this work the authors study quadratic optimization problems with linear constraints and answer the question if the objective value, feasibility and optimal solution of this problem class can be approximated by a class of graph neural networks. More precisely they study the standard graph representation of LCQPs and show that if all decision variables are continuous there exists graph neural networks which (i) can approximate the objective value up to an arbitrary accuracy with high probability, (ii) can decide if the corresponding problem is feasible with high probability, and (iii) can predict the optimal solution with minimal l2 norm up to an arbitrary accuracy with high probability. On the contrary the authors show that, if some of the variables may be restricted to be integer, the latter results do not hold in general. However, they can derive subclasses of LCQPs for which (i)-(iii) hold. Finally, the authors showcase approximation capabilities of GNNs in some numerical experiments.\n\n\"## update after rebuttal\nNo update.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__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.\n\nWhile 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.\n\n__Reply to \"Other Comments Or Suggestions\":__ Thanks for the detailed comments, and we will fix these typos following your suggestions.\n\n__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: \n* We have richer counterexamples for MI-LCQPs (Chen et al. (2023b) only have counterexamples for the feasibility). \n* 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). \n* 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.", "claims_and_evidence": "All the claims made in the submission are thoroughly explained and proved. The authors even provide experimental results which are in my opinion not necessary for such a theoretical work, since finding the GNN which approximates the metrics of the problem class depends a lot on the learning algorithm and hyperparameter setting and is a task for a completely different study.", "methods_and_evaluation_criteria": "The work is mainly theoretical and all results are properly explained and proved. The experimental confirmation of the expressiveness of the GNNs is a nice addition to the theoretical results showing that even standard training methods already lead to GNNs which nearly perfect approximate the desired property of the LCQPs. However, in practical settings the more important question is if the GNNs generalize well on unseen data, i.e., did the learning algorithm indeed find a GNN which has the theoretically desired expressiveness on the whole problem class. The latter question is not answered in detail and is in my opinion not needed for this work.", "theoretical_claims": "I briefly checked the proofs in the Appendix without checking every detail.", "experimental_designs_or_analyses": "Soundness of the experimental design is very satisfying, see comments above.", "relation_to_broader_scientific_literature": "The work closely builds on the work of Chen et al (2023) where the same methodology is used for linear problems. However, extending the work to quadratic problems is valuable and relevant for the research field.", "essential_references_not_discussed": "No references.", "other_strengths_and_weaknesses": "Strengths: \n- the paper is very well written and all concepts and proofs are mathematically thoroughly presented. I could not find any mathematical flaws in the main paper.", "other_comments_or_suggestions": "- Line 47: \"with with\"\n- Line 64: exploits -> exploit", "questions_for_authors": "- What was the main difficulty to extend the work of Chen et al. (2023) to the quadratic setting?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper investigates the theoretical expressiveness of message-passing Graph Neural Networks (GNNs) in approximating key properties of linearly constrained quadratic programs (LCQPs) and their mixed-integer counterparts (MI-LCQPs). The authors demonstrate that GNNs can approximate feasibility, optimal objective values, and optimal solutions in the convex LCQP setting. For the more challenging MI-LCQP case, they introduce novel concepts of GNN-analyzability and GNN-solvability, identifying subclasses where GNNs retain expressive power. Theoretical insights are backed by experimental validations on synthetic and real-world datasets.

Overall the reviewers liked the paper (with one weak reject though) and I tend to agree with slight reservations here and there. The discussion was good. All things considered I will recommend weak acceptance.
Decision: Accept (poster)