On Representing Convex Quadratically Constrained Quadratic Programs via Graph Neural Networks
Authors: Chenyang Wu
Qian Chen
Akang Wang
Tian Ding
Ruoyu Sun
Wenguo Yang
Qingjiang Shi
Venue: Accepted by TMLR ()

Abstract: Convex quadratically constrained quadratic programs (QCQPs) involve finding a solution within a convex feasible region defined by quadratic constraints while minimizing a convex quadratic objective function. These problems arise in various industrial applications, including power systems and signal processing. Traditional methods for solving convex QCQPs primarily rely on matrix factorization, which quickly becomes computationally prohibitive as the problem size increases. Recently, graph neural networks (GNNs) have gained attention for their potential in representing and solving various optimization problems such as linear programs and linearly constrained quadratic programs. In this work, we investigate the representation power of GNNs in the context of QCQP tasks. Specifically, we propose a new tripartite graph representation for general convex QCQPs and properly associate it with message-passing GNNs. We demonstrate that there exist GNNs capable of reliably representing key properties of convex QCQPs, including feasibility, optimal value, and optimal solution. Our result deepens the understanding of the connection between QCQPs and GNNs, paving the way for future machine learning approaches to efficiently solve QCQPs.

Published in Transactions on Machine Learning Research (11/2025)
On Representing Convex Quadratically Constrained Quadratic Programs via Graph Neural Networks
Chenyang Wu', Qian Chen Akang Wang?.1", Tian Ding", Ruoyu Sun Wenguo Yang",, and Qingjiang Shi2.5
'University of Chinese Academy of Sciences, China
Shenzhen Research Institute of Big Data, China
Schooo of Science and Enginocring, The Chinese University of Hong Kong, Shenzhen, China
"School of Data Science, The Chinese University of Hong Kong, Shenzhen, China
5School of Computer Science and Technology, Tongji University, Shanghai, China
Reviewed on OpenReview: http::///oooaaneess...e.//rreee2
Abstract
Convex quadratically constrained quadratic programs (QCQPs) involve finding a solution within a convex feasible region defined by quadratic constraints while minimizing a convex quadratic objective function. These problems arise in various industrial applications, including power systems and signal processing. Traditional methods for solving convex QCQPs primarily rely on matrix factorization, which quickly becomnes computationally prohibitive as the problem size increases. Recently, graph neural networks (GNNs) have gained attention for their potential in representing and solving various optimization problems such as linear programs and linearly constrained quadratic programs. In this work, we investigate the representation power of GNNs in the context of QCQP tasks. Specifically, we propose a new tripartite graph representation for general convex QCQPs and properly associate it with message-passing GNNs. We demonstrate that there exist GNNs capable of reliably representing key properties of convex QCQPs, including feasibilily, optimal value, and oplimal solution. Our result deepens the understanding of the connection between QCQPs and GNNs, paving the way for future machine learning approaches to efficiently solve QCQPs.
1 Introduction
Quadratic programs (QPs) are pivotal class of optimization problems where the objective function is quadratic, and the constraints are typically linear or quadratic. Based on the nature of constraints, QPs can be further classified as linearly constrained quadratic programs (LCQPs) and quadratically constrained quadratic programs (QCQPs). When the objective and constraint matrices are positive semi-definite, the problem becomes a convex QCQP, making it both theoretically interesting and practically important. Couvex QCQPs arise in various critical applications such as robust optimization in uncertain environments (Ben-'all & Boyd & Vandenberghe 2004), power flow Bienstock al. 2020). and signal processing (Luo
Nemirovski 2001
ct al. 2010
Solving QPs, especially those with quadratic constraints, presents significant. challenges. Traditional methods often involve computationally intensive procedures that would struggle with scalability and real-time processing requirements. For example, the interior- point method (Nocedal & Wright 1999) for a general n-variable QP involves solving a sequence of linear systems equations, necessitating matrix decomposition with runtime complexity of (nz²). This leads to substantial computational burden in the large-scale case. Similarly, active-set algorithms (Gill al. 2019), which work by iteratively adjusting the set of active constraints, can also become computationally demanding the number of constraints and variables increase.
"Corresponding authors: Wengno Yang SyangugSucas..cccns Akang Wang <wangakang@ksrbbd.ccmm

---

Published in Transactions on Machine Learning Research (11/2025)
In recent years, advances in machine learning (ML) have opened new avenues for enhancing the solving process of QPs. There are mainly two categories of MT-aided QP methods. The first category aims to learn adaptive configurations of a specific QP algorithm or solver to accelerate the solving process (Bonami et al., 2018: Ichnowski et al.) 2021: Jung et al. 2022), while the second focuses on prodicting an initial solution of QPs, which is either directly laken as a final solution or further refined by subsequent algorithms or
QP solvers [Bertsimas & Stellato, 2022 Gao a 2021; Sambharya et al.) 2023: Tan et al. 2024 Wang
eet al. 2020 Xiong et al.). Additionally, Xiong et al. (2024) proposes a hypergraph-based framework for solving QCQPs. Most of these methods utilize graph neural networks (GNNs) to leverage the structural properties of graph-structured data, making them particularly well-suited for representing the relationships and dependencies inherent in QPs. By encoding QP instances into graphs, GNNs can capture intricate features and provide adaplive guidance or approximale solutions efficiently.
In addition to these studies, theoretical research on the expressive power of GNNs (Zhang et al. 2024 Li &
Leskovee 2022) and their relation to optimization problems has further strengthened the understanding of their capabilities. For instance, Chen et. al. (2023a) and Chen et al. (2023b) established theoretical foundations for applying GNNs to solving linear programs (LPs) and mized-integer linear programs, respectively. Further, such foundations are extended to LCQPs and their discrete variant, mixed-integer LCQPs in CChnn et al. (024)..
Previous studies have empirically and theoretically demonstrated the utility of GNNs in speeding up existing QP solvers and directly approximating solutions for various QP instances. However, the question of whether GNNs can accurately predict key properties of QCQPs, such as feasibility, optimal objective volue, and optimal solution, remains open. This paper aims to address the aforementioned gap by exploring both theoretical foundations and practical implementation of using GNNs for solving convex QCQPs. Specifically, we propose tripartite graph representation for general convex QCQPs, and establish theoretical foundations of applying GNNs to optimize QCQPs. The distinct contributions of this paper can be summarized as follows.
Graph Representation. We propose a novel tripartite graph representation for general QCQPs, which divides a QCQP into three types of nodes: lincar-term, quadratic-term, and constraint nodes, with edges added between heterogeneous nodes to indicate problem parameters.
Theoretical Foundation. We conduct analysis on the seporalion power as well as approzimation power of passage-passing GNNs (MP-GNNss. We showed that MP-GNNs are capable of capturing some key propertics of convex QCQPs.
Empirical Evidence. We conduct initial numerical tests of the tripartite instances. The results showed that MP-GNNs can be trained to approximate the key properties well.
on small QCQP
Building on the theoretical insights of our work, we establish a deeper understanding of the equivalence properties in convex QCQPs. By examining what key properties of QCQPs can be represented by GNNs, we gain a clearer view of QCQPs' intrinsic geometry and feasibility structure.
Although our work is primarily theoretical, it opens up interesting opportumities for future empirical investigation. In particular, our insights can inform the design of practical GNN-based solvers that improve efficiency in tackling convex QCQPs. Moreover, while our main focus is on convex QCQPs, many solvers for more general, non-convex QCQPs rely on relaxation steps involving convex QCQPs at intermediate stages. Consoquently, our insights could help accelerate or guide the solving of these relaxation- subproblemss offering a pathway to enhanced performance even in non-convex scenarios.
Notations
Throughout this paper, scalars or vectors are denoted by lowercase letters (e.g., a), and matrices are denoted by uppercase letters (e.g., A). For a vector a, we denote its i-th entry by a, For a matrix A, the entry in the i-th row and the j-th column is denoted by aij. We use and 1 to denote vectors or matrices with all-zero and all-one entries, respectively. For any positive integers m, n with m < n, we define [m, n)] == {m, m + +,....,, ,n} to be the set of all integers ranging from to n. For brevity, define [n] == [1: []: (1, ,n).
2

---

Published in Transactions on Machine Learning Research (11/2025)
2 Graph Representation of QCQPs
2.1
Quadratically Constrained Quadratic Programs
In this work, we study QCQPs defined in the following form:
min TER"
f(z)= -
Qr Qr+pxx
1
Q'x+ (p') x + b so vie [m]
(2.1)
s.t. 2"
where Q E g"x", P.p' R" o' (RO("=)))" and x" O (++o))) The problem has n optimization variables and m constraints. We refer to the tuple (m,n) the problem size of QCQP. Both the objective function and the constraints associated with quadratic functions. The QCQP problem is conver if Q and Q''s are all positive semi-definile.
We denote the feasible set of Problem (2. by X. If 00 the QCQP is said to be feasible; otherwise, it is said to be infeasible. A feasible QCQP is said to be bounded if the objective is bounded from below on X, i,e., there exists z E IR such that (xx 2 z for every x X; otherwise, is said to be unbounded. For a feasible and bounded QCQP, remark that QCQP always admits an optimal solution if it is feasible and bounded, but such optimal solution might not be unique.
X' is said be an optimal solution if f(x*) S f(x) for every X. We
2.2 Tripartite Representation of QCQPs
The first thcoretical result demonstrating the representation power of GNNs in solving optimization problems was provided by Chen et al. (023a]). Their work employs bipartite graph representation where variables and constraints are modeled as nodes. In this encoding, the linear constraint coefficients are edge fcatures, the right-hand-side values are constraint node features, and the objective coefficients are variable node features. They showed that GNNs based on this graph representation can universally approximate the optimal solution of LPs, as well as properties of fcasibility and boundedness. This bipartite graph modeling was later extended by encoding quadratic objective terms edge features between variable nodes to analyze the representation power of GNNs for LCQPs (Chen al. 2024).
Despite these advances, it remains challenging to develop graph representation to encode all information of general QCQPs while maintaining simplicity for GNN processing. Due to the presence of quadratic terms, a QCQP generally involves O(n² x m) coefficients. Consequently, a graph encoding all QCQP information inherently exhibits a complexity of the same order, O(n² x m). There are two natural extensions of the traditional bipartite representation of LPs/LCQE QCQPs.
Hyperedge Representation. This approach adds hyperedges the traditional bipartite graph represent quadratic coefficients, turning the graph into hypergraph. However, the best of our knowledge, most of the current. GNN architectures struggle to handle hyperedges.
Vector Feature Representation. In this extension, all coefficients are encoded as features associated with the variable nodes and the m constraint. nodes, resulting in graph with vector features of varying sizes, depending the problem. However, existing GNNs generally incapable of processing features of varying dimensions.
To fill this gap, we introduce an undirected tripartite graph representation GqcQp == (V. E) that encodes all elements of a QCQP (21). Compared to the traditional bipartite graph modeling for LPs and LCQPs, our tripartite graph representation introduces an additional class of nodes to model the quadratic terms of variables. This modification allows us represent QCQPs without any loss of information. In this paper, we will show that the tripartite representation enables GNNs to universally approximate solutions for convex QCQPs.
3

---

Published in Transactions on Machine Learning Research (11/2025)
Quadratic-tem Nodes
Pjj
min Σ
23
+ Σ
Σ 1-1
Pg M
(1/2
Qn
f-1
s>k
1
s.f. 2
Σ
Pj
Vi C [m) D' x
(2
(b:)
Variable Nodes
Constraint Nodos
QCQP formulation
Tripartite representation
Figure 1: tripartite representation of QCQPs. consists of three types of nodes: variable nodes, quadratic- term nodes, and constraint nodes. All nodes and the edges connecting them are associated with coefficients from the formulation features.
Formally, we model QCQP as a tripartite graph with node sets representing variables, quadratic terms, and constraints.
Variable nodes (V1): Let V1 == fui..... und, where node uj corresponds to variable zj and is associaled with the feature tuple (py, x/. x/)).
Quadratic term nodes (V2): Let C e [n] j of quadratic term indices with non-zero coefficients in either the objective or at least one constraint.
k, | - l0j.al > 0} be the set
Then, 1/2 {uga (j, E C}. The feature for node Uj 2ạj, if j k, and Pi if j k.
Constraint nodes (V)): Let V/ = (m....,,mm) where node e corresponds to the i-th constraint and is associated with the feature b,.
The full node set is V = Vi VVV.VV The QCQP graph contains three edge sets, each with associated weights:
V11V/ edges (E12): Connect variable node uy E V1 to quadratic node 4/ E V22 if = jo j = k.
The weight is defined as Wuy == if k, and 2 otherwise.
Vi-Va edges (Eis): Connect uy E V1 to constraint node e E V3 the linear coefficient př # 0. The weight is defined as Way.er = p)j
V/-Va edges (E2s): Connect dy E V22 to G E V3 if the quadratic coefficient L/,x # The weight is defined as Wey,u. 24', if > k, and of,s otherwisc.
The full edge set is given by E = F12 U E13 U Ezg. For any edge, define Wz,y == Wy. for connected nodes and y.
We illustrate this representation in Figure I
We remark that there is a one-to-one mapping between a QCQP and its tripartite graph representation GocQr. Our representation has two major advantages:
Our representation forms simple graph, making it compatible with most existing GNNs. This facilitates the development of more efficient and task-specific GNN architectures.
Our reprosentation can leverage the sparsity nature of QCQP problems. That is, the numbers of nodes and edges are also controlled by the total number of nonzero coefficients. Thus, our representation be efficiently applied to large and sparse instances.
'Throughout, we for variable nodes, for quadratic nodes, constraint nodes. Indices i, J. and refer constraints, variables, and quadratic terms, respectively.
4

---

Published in Transactions on Machine Learning Research (11/2025)
Embedding Layer har 92(h))
Message-Passigg Layer
si(h h
htt
V2
V3
V
V2
ht
getsc 050fe New Ria)
AM
g1()))
A 93(h))
Sub-layer
Sub-layer
layars
Readout Layer
A+ 1.
V
V2
V2
hT
V
hT
Mera gi(htxx M (erttr
Ateic
A/
AetLee
y Toue Toue Tax, nT (TT))
Sub-layer
Sub-layer
Figure 2: An overview of the GNN architecture.
Definition (Spaces of Convex QCQP-graphs). We denoted by SCCQP the set of tripartite graph representa- tions for all convex QCQPs with variables and constraints,
3 Theoretical Results
3.1 Tripartite MP-GNNs
To study the capability of GNNs in representing QCQPs, we tailor the general MP-GNNs for the tripartite nature of the introducod QCQP graph reprosentation. An overview is depicted in Figure 2
Specifically, we consider the lamily of tripartite MP-GNNs consisting an embedding layer, T message-passing layers (each comprised of four sub-layers), and a readout layer, detailed as follows:
Embedding Layer. The initial features for all nodes are obtained by projecting their input features into a hidden space ho using learnable embedding functions:
0000 gi(h")
Vu Vi,
000 + (h()
Yo E V2,
0 + (19) Ve V3.
where h", h", and h are the input features of nodes in Vi, V2, and V/2 respectively, and gi 99.92.0 of are the embedding functions for each node type.
PassaagePPassnng Layer. Each message message-passing layer employs four distinct sub-layers to update node features, using learnable functions ft and gf- Each sub-layer updates the features of nodes one set by aggregating messages from specific subset of neighboring nodes, detailed below.
For any QCQP graph in Caoqe: the associated convex QCQP can be characterized by its coefficient tuple (Q. (Q (r' pm (b) p =h, where Q,Q² E sT. We define a topology on Fqcqr: for Q,Q* and p.p" we use of the linear mappings defined by the matrices and vectors, and for sh. z b cuclidean
the topology induced by the topology and discrete topology introducing an infinity indicator.
infinite values. numerical experiments, we represent, the infinite values by

---

Published in Transactions on Machine Learning Research (11/2025)
Sub-layer 1: Update Quadratic Nodes from Variables (Vi + V2):
h t of hht NEV
(eref((h(")) Ye E V2.
This step computes an intermediate representation ht"" for each quadratic node v based on incoming messages from variable nodes u E V1. Sub-layer 2: Update Constraint Nodes from Variables and Quadratic Nodes (V++12 + V3):
1itlic + 92 (ht mia: mba) Vc E V3.
where mia == Ewev, (hhet and mba = Evers (o,e)ā(h"")) denote the messages from variable nodes and quadratic nodes, respectively. This sub-layer produces the updated constraint node features for the next step.
Sub-layer 3: Update Quadratic Nodes from Constraints (V/ - V2):
t1 t
g3
R. Σ Wo fo CEVV
Vo E V2.
Here, the intermediale representations he are updated using the new constraint node features 1 produce the final quadratic node features for this layer. Sub-layer 4: Update Variable Nodes from Constraints and Quadratic Nodes (Va+12 + V()::
1 + g4 (ht man m2i) Vu E V1,
where m4i = Ecevs (hhhtt and m²i Evevs ((hh+ are the messages from constraint nodes and the updated quadratic nodes, respectively. This completes the update cycle for the layer.
The four sub-layers implement structured, alternating update scheme. The first two sub-layers propagate information from variable nodes to constraint nodes, passing through the quadratic nodes to incorporate information about quadratic terms. This allows the constraint node representations to be informed by the current stale of the variables and their quadratic interactions.
Conversely, the last two sub-layers propagate information in the reverse direction, from the updated constraint nodes to the variable nodes. By again routing messages through the quadratic nodes, the network learns the relationship between constraints and quadratic terms, using this to refine the variable node representations. This bidirectional, structured pesssge-passingg crucial for capturing the complex dependencies when representing QCQPs.
Readout Layer.
The readout layer maps the final node features from the T-th pessaae--assiing layer an output y E I using learnable function fout- We consider output types:
Graph-level output = 1): The output scalar representing the entire graph. We compute it as:
y fout (a1, (22, (z)
where 01 = = ITT 02 = Evev, AT,, and 0g = Ecev, hTee are the aggregated features from variable, quadratic, and constraint nodes, respectively.
Node-level output (s = n): The output is vector where each component corresponds to variable node. For each node új E VT:
y = fout (hTm ai.,, a2, 02), Vj E [n]
where 11,u, = Enev, (uy) T.u aggregates features from all other variable nodes, providing contextual information about the graph excluding node uy itself.

---

Published in Transactions on Machine Learning Research (11/2025)
Definátion 2 (Spaces of GNNs). Let Facqr (R*) denote the collection of all tripartite MP-GNNs, parameterized by continuous embedding functions of: I E (1, continuous hidden functions in the message passing layers gi with E 21, 2, 4], hi with L E 21, 3, 4, 5, 6), and the continuous readout function fout Specifically, for a given problem size (m, n) of QCQP, there exists a subset of GNNs in Focor(R*) that maps the input space PQCQP the output space R This subset of GNNs are denoted by FQCQP (R.)).
We define the following target functions, characterizing some key properties on learning an end-to-end network to predict the optimal solutions of convex QCQPs:
Definition 3 (Target mappings). Let Gooqp be tripartite graph representation of a QCQP problem. We define the following target mappings.
if the QCQP problem is feasible and Feasibility mapping: We define PRas(GQcQp) (GoosGG = 0 otherwise.
Boundedness mapping: for a feasible QCQP problem, we define Abouna 1 if the QCQP problem is bounded and @bonad = 0 otherwise.
Optimal value mapping: for a feasible and bounded QCQP problem, we set Popt (Gocqr) to be its optimal objective value.
Optimal solution mapping: for a feasible, bounded QCQP problem, there must exist at least an optimal solution, but the optimal solution might not be unique. However, the QCQP is convex, there exists a unique optimal solution x" with the smallest 42-norm among all optimal solutions. Therefore, for conver QCQP we define the optimal solution mapping to be &u (Gqcop) = x². Since the optimal solution with the smallest fy-norm may not be unique for non-convex QCQPs, we do not define its optimal solution mapping F
3.2 Universal approximation for convex QCQPs
Our theoretical analysis rests the following key lemma, which establishes that the tripartile WL-test can transfer solutions between equivalent QCQP instances.
Lemma 1. Let I,Σ (with given sizes m, n, encoded by G, E @@cap) be two QCQP instances. If the tripartite WL-test cannot separate G from G, then for any feasible solution x of I, there exists a feasible solution ē for I such that:
f TTTii+pTee fo T tJ+
(ii) ||ا|| I ||0||2.
Lemma resolves fundamental challenge. Tn LPs/I.CQPs, solution transfer between equivalent. instances can be achieved through straightforward averaging of variable values within node color classes. For QCQPs, this direct approach fails because the average of products does not equal the product of averages. Our core contribution is proving that the slable colorings generated by the tripartite WT.test provide sufficient. structural information to overcome this limitation. The solution 7 is constructed by averaging the values of the original solution & across all variables belonging to the same color class in G. While this averaging does not preserve individual quadratic terms, we prove that the collective quadratic forms- the weighted sums of quadratic terms within each constraint-ars appropriately controlled due to the color stability of the graph representation. This ensures that feasibility is maintained in I and the objective value is non-increasing, This lemma establishes the fundamental separation power of the tripartite WL-test: il can distinguish between QCQP instances that have different optimal values or solution structures.
Building on this foundation, we demonstrate that for convex QCQPs, any target function in Definition can be universally approximated by MP-GNNs. Formally, we have the following theorem.
II fact, Scction 3.3 shows that there exists pair of non-convex QCQPs that cannot be distinguished by any MP-GNNs based tripartite graph representation. Thus, even if optimal solution mapping for non-convex QCQPs is defined, MP-GNNs rannot universally approximate it.
7

---

Published in Transactions on Machine Learning Research (11/2025)
Theorem 1. For any probability measure P on the space of convex QCQPs JQCQP and any o, 0, there exists F F QCQP (R*) such that for any target mapping SQCQP I defined in Definition 3 we have
P ((I @(Gocqr)]l > 6) <.
(3.1)
Theorem highlights that sufficiently expressive GNNs can predict the feasibility, boundedness, optimal value, and optimal solution for convex QCQP problems with an arbitrarily small error. The proof of Theorem provided in Appendix A The convexity requirement is essential for theoretical results. Convexity ensures that the averaged solution constructed in Lemma | not only remains feasible but also satisfies (i). This property enables the translation of the WL-test's separation power into the GNN's approximation capability for the target functions 4.
the critical objective value bound in condition
3.3 MP-GNNs can not represent general non-convex QCQPs
In contrast to convex QCQPs, MP-GNNs based on tripartite graph representation do not possess universal representation power for non-convex QCQPs. Formally, we have the following propositions.
Proposition 1. There exists non-convex QCQP instances I, encoded by tripartile graph representation G, G respectively, such that ((G) # Deeas G),, but any GNN F E FFqcqp (R) gives F(G) F(G). Proposilion There exists non-convex QCQP instances I, encoded by tripartile graph representation G, G respectively, such that
(i) (G)) * (G);
(ii) the optimal solution sets I and I do not intersect;
(iii) any GNN F E Focqr (R) gives F(G) = F(G).
Proposition implies that GNNs camnot universally predict the feasibility of non-convex QCQPs. Proposition implies that GNNs can neither universally predict the optimal value nor the optimal solution of non-convex QCQPs. We prove both propositions by constructing counter-example. Below we present. the counter-example for Proposition 2
We defer the formal proof of both propositions to Appendix C
Consider the following pair of non-convex QCQPs:
min
22 + 12 2z + F445 Fg + 2824
xER
(3.2)
E <
s.t.
min #ERs
T1 + T2ll' + Tz + T4dl T550 + Tg
(3.3)
s.t. Σ
For the former, the optimal objective value Pabj = 2 and all optimal solutions are given by
x Rº 21 +
x2 + x3 0, + 20 + x6 0, Σ
For the latter, the optimal objective value Pabj = -1, and all optimal solutions are given by
V6
E 12
1 = 25 -T2 -
We see that the optimal values of Problem 3.2) and Problem 3.3 are different, and their optimal solution sets do not intersect. The tripartite graph representations of the two instances are illustrated in Figure We
8

---

Published in Transactions on Machine Learning Research (11/2025)
min
2142 + #2
2321 + 2425 + 26 2624
921
s.t. 11
130
min
2132 1223 + 1324 + 14 x556 1671
8.t. Σ 1 1
Figure 3: Left: two QCQP instances for proving Prop. 1 representations to show the difference.
Right: Parts of the corresponding tripartite graph
will further demonstrate appendix C that any GNNs on the two tripartite graphs gives the same output. Thus, Problem (3.2) and Problem 3.3 serve as a valid counter-example for proving Proposition P
We remark that Propositions and demonstrate limitations specific our proposed tripartite MP-GNN architecture. They do not rule out the potential for other, more powerful graph representations network architectures to achieve universal approximation for non-convex QCQPs.
4 Computational Experiments
In this section, we present empirical experimenss to validate the proposed theoretical results. The corresponding source code is available at https:/ggthubl.com//aaayy//////p
4.1 Learning tasks
In Theorem we established that there exists function F E FQcQp (I*) capable of approximating the target mapping + with an arbitrarily small error. To empirically confirm this claim, design three supervised learning lasks to find such functions Freas Fohj and Fant, which are responsible for predicting feasibility, objective values, and optimal solutions, respectively. For each task, let {(G., x)) be a given dataset, where G, represents a QCQP instance and y; denotes its corresponding label. The function family Facqp (R*) is constructed using the tripartite MP-GNNs as defined in Definition 2 With all these ingredients ready, the learned function obtained by F arg min sera (R*) N Em=,. T. (. Wi), where I(::) is the loss function. Specifically, we use mean squared error for predicting objective values and optimal solutions, while binary cross-entropy loss is employed for predicting feasibility. We chose cross-entropy loss for this binary classification task as it is more suitable than a regression based approach that would be needed we were to predict numerical degrees of constraint violation instcad of final fcasibility state.
4.2
Data generation
To facilitate the supervised learning approach described above, we generate three datasets of convex QCQPs by randomly sampling coefficients from normal distributions. These datasets consist of a general QCQP (GP), a constrained least squares problem (CLS), and a trust-region subproblem (TRS). The formulation and generation strategy for each dataset are outlined below.
GP: A general QCQP formulation is given in 22.1 All coefficients of Q, p, Q', p¹, and bi in the objective and constraints are independently sampled from the normal distribution A/ 1). The lower and upper bounds z and z are set be and 1, respectively. The number of variables and constraints for instances in this dataset are set 30 and 5, respectively. We generate small dataset for general QCQPs because larger-scale instances with more constraints tend to be predominately infeasible.

---

Published in Transactions on Machine Learning Research (11/2025)
CLS: Constrained least squares problems with quadratic constraints common in various applications. We examine the following CLS problem:
min EER"
||A bll
(4.1)
s.t. T Qz c
The elements in A, and Q are sampled from the standard normal distribution (0, 1), while elements in are sampled from (111)), 1). For this datasct, the number of variables set to 500, and the sparsity (the proportion of zero clements) of Q is set to 0.95.
TRS: The trust-region subproblem another form of convex QCQP, defined by the following formulation:
min ZER"
x xTQu + 2cTx
(4.2)
s.t. |0||² < A
The coefficients in Q and e are independently sampled from the standard normal distribution WV 1) and A is sampled from (1,, 1). Like the CLS dataset, the number of variables is set to 500, and the sparsity of is set to 0.95.
To ensure that the generated instances remain convex, we adjust all sampled matrices Q and Qis corresponding to the quadratic terms in both the objective function and the constraints. Specifically, each matrix is modified by replacing it with Q - al, where a < 0 is the minimal eigenvalue of Q. This adjustment ensures that the matrices are positive semi-definite, thus guaranteeing the convexity of the corresponding QCQP instances.
For each dataset, we generate 1,000 instances for training and 300 instances for validation. All instances are solved using the IPOPT solver (Wächter & Biegler 2006). The resulting feasibility, objective values, and optimal solutions are collected as labels.
4.3 GNN architecture and training settings
For the GNN described in Section 3.1 there are three classes of functions .gi....,. .. (hG....,,$f) ,T)]T= and R remain unspecified. The first class, "f].....91).. are two-layer MLPs with layer widths of [d, d], and ReLU as activations, where the inputs of each function are concatenated together. The second class, (hf..... Ng /T are linear transformations with output dimension d followed by ReLU activations. The last one, It, is also a two-layer MLP with ReLU activation, with widths of [d. 1] for predicting feasibility and objective values, and [d, n] for predicting solutions. The hyper-parameter T is set to 2. For training, we utilized the Adam optimizer with a learning rate of 0.0001 and a batch size of 16.
4.4
Main results
In this section, we present the main results for tasks with different learning targets. For the GP dataset, we perform tasks to predict the feasibility, objective value, and optimal solution. However, the feasibility task is omitted for the CLS and TRS datasets, as their sampled instances are predominantly feasible.
Training loss vs. numbers of parameters. The results from Table show the training loss for models with different numbers of parameters. Generally, the losses are small across all models, validating the claim in Thcorem 3.1 Morcover, we observe a consistent trend: as the number of parameters increases, the training loss decreases.
For the GP dataset, the feasibility, objective, and solution losses all decrease the number of parameters incrcascs, with the loss for the largest model (6.7M paramcters) being particularly small, especially for the objective and feasibility largets. For the CLS dataset, similar trends are observed, with the loss for the objective function decreasing substantially from 0.0994 (15K parameters) to 0.0016 (6.7M parameters). The solution loss in CLS remains relatively stable but still decreascs as the number of parameters incrcases. Finally, in the TRS dataset, both the objective and solution losses follow a similar pattern, with the objective loss improving significantly from 2.98 (15K parameters) to 0.0171 (6.7M parameters).
10

---

Published in Transactions on Machine Learning Research (11/2025)
Table Training loss vs. numbers of parameters.
# Parameters
Dataset
Target
15K
21K
42K
126K
1.7M
6.7M
feasibility
0.2114
0.0992
0.0883
0.0779
0.0254
0.0044
GP
objective 0.0853
0.0293
0.0218
0.0185
0.0110
0.0034
solution 0.0604
0.0419
0.0413
0.0407
0.0397
0.0350
objective 0.0994
0.0196
0.0135
0.0096
0.0020
0.0016
CLS
solution 0.2333
0.1454
0.0175
0.0173
0.0171
0.0169
objective 2.1098
0.1979
0.1089
0.0996
0.0265
0.0171
TRS
solution
1.2004
0.4294
0.4035
0.4022
0.4017
0.4010
Validation loss vs. number of samples. The validation loss results presented in Table 2 indicate that the validation loss remains small across all configurations, highlighting the generalization capability of the models. Additionally, as the number training samples increases, the validation loss decreases, reflecting the benefit of having more data for model training.
Table 2: Validation loss vs. numbers of training samples.
# Samples
Dataset
Target
100
300
500
700
1,000
fcasibility
0.5857
0.3167
0.1940
0.1885
0.1004
GP
objective 0.1067
0.0577
0.0514
0.0421
0.0296
solution
0.1149
0.0439
0.0438
0.0434
0.0427
objective 0.0136
0.0121
0.0107
0.0086
0.0049
CLS
solution 0.0181
0.0179
0.0178
0.0177
0.0177
objective 0.2131
0.0933
0.0834
0.0792
0.0596
TRS
solution
0.4081
0.4055
0.4054
0.4054
0.4054
For the GP dataset, the validation loss for feasibility, objective, and solution all decrease as the number of samples increases. Notably, the solution loss stabilizes after 500 samples, while the objective and feasibility losses continue to improve as the number of samples grows, with the best performance observed at 1,000 samples. The CLS dataset shows clear reduction in the objective loss the number of samples increases, with the loss dropping from 0.0136 for 100 samples to 0.0049 for 1,000 samples. The solution loss in CLS remains relatively stable across different sample sizes. Finally, for the TRS datasct, the objective loss improves from 0.2131 at 100 samples to 0.0596 at 1,000 samples, while the solution loss remains nearly constant across all sample sizes.
In conclusion, both the training and validation loss results highlight the effectiveness the models, showing that increasing the number of parameters and training samples leads to improved performance in terms of both training and generalization.
4.5 Additional comparative results
Runtime comparison. Table reports the average solving time (in seconds) and standard deviation across the validation instances for several QCQP solvers IPOPT (Wächter & Biegler 2006), Gurobi (Gurobi Optimization, LLC, 2025), MOSEK (ApS 2025). SCS (O'Donoghue et al. 2016), and ECOS (Domahidi et al, 2013) together with the inference time our GNN. The results demonstrate that our GNN-based approach delivers a substantial speedup, often by orders of magnitude, compared all baseline solvers. However, it is important to note that the accuracy of these baseline solvers (S 10-6) significantly surpasses that of the
11

---

Published in Transactions on Machine Learning Research (11/2025)
GNN, reported in Section 4.4 precision.
(with minimal level of 10 10-2), indicating trade-off between speed and
Table Comparison of runtime (in seconds) with solvers having tolerance of 10
Method
GP
GLS
TRS
IPOPT
0.0374( = 0.0044)
0.0602( + 0.0115)
0.0670( = 0.0158)
GUROBI
0.0054( + 0.0004)
0. 0.1091( + 0.0138)
1.8921 + 0.2751)
MOSEK
0.0300( + 0.0033)
0.4014( + 0.0274)
0.2264( + 0.0079)
SCS
0.0311 + 0.0058)
0.6799 + 1.0300)
0.1466(
+ 0.8167)
ECOS
0.0314 0.0040)
4.4056 + 0.4668)
1.6713(
= 0.3785)
GNN
0.0024 0.0032)
0.0022( 0.0030)
0.0023( 0.0031)
Impact of sparsity. We conducted an ablation study on datasets CLS and TRS by varying sparsity (fraction of zero coefficients) from 0.95 to 0.8. Table reports the training losses. As sparsity decreases,
Table 4: Training loss on different levels of sparsity.
Sparsity
Dataset
Target
0.95
0.9
0.85
0.8
objective
0.0020
0.0036
0.0058
0.0096
CLS
solution
0.0171
0.0217
0.0279
0.0323
objective 0.0265
0.0497
0.1084
0.1844
TRS
solution
0.4017
0.5338
0.7415
0.9042
losses increase consistently, reflecting the added difficulty of denser problems with more complex interactions. Our focus highly sparse cases (e.g., 0.95) is motivated by their prevalence in practice for example, over 35% of QPLib (Furini et al. 2019 instances exhibit sparsity above 0.95.
In addition to comparisons on runtime and sparsity, we also provide evaluations on a real-world dataset, QPLIB, and on a task of predicting boundednoss, which can be found in Appendix D
4.6 Discussions
The computational elliciency of our tripartite GNN stems from two key design choices. First, the graph structure naturally exploits problem sparsity, edges correspond directly to non-zero parameters, ensuring high efficiency for real-world, sparse instances. Second, the architecture uses simple mussage-passing layers where the split-layer design organizes computations without increasing the total number of matrix operations, incurring minimal overhead. We remark that our universal approximation theorem establishes expressive power but does not quantify the parameters required for a given approximation error; deriving such bounds remains an important direction for future work.
5 Conclusions
This paper introduces new tripartite graph representation specifically designed for QCQPs. By leveraging the capabilities of MP-GNNs, this approach shows thcoretical promise in predicting key propertics of QCQPs with arbitrary desired accuracy, including feasibility, boundedness, optimal values, and solutions. Initial numerical experiments validate the effectiveness our framework. This work advances learning toiiing-t--ptmmizee by extending GNNs QCQP problems, which have been challenging for traditional graph-based L20 methods. Our findings may inspire future research into more specialized GNN architectures and principled approaches to controlling GNN sizes for practical QCQP applications, going beyond the basic GCN structure used here.
12

---

Published in Transactions on Machine Learning Research (11/2025)
Acknowledgments
This work supported by the National Key R&D Program of China under grant 2022YFA1003900. Qian Chen and Akang Wang also acknowledge support from National Natural Science Foundation of China (Grant No. 12301416), Guangdong Basic and Applied Basic Research Foundation (Grant No. 2024A1515010300, and Shenzhen Science and Technology Program (Grant No. JCX,220250004199333044);
References
MOSEK ApS. The MOSEK Python Fusion API manual. Version 11.0., 2025. URL https://docs.mont mosek cut///atte///yybbootttooonnontt.
Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2020.
Aharon Ben- Tal and Arkadi Nemirovski. Lectures on modern conver optimization: analysis, algorithms, and engineering applications. STAM, 2001.
Dimitris Bertsimas and Bartolomeo Stellato. Online mixed-integer optimization in milliseconds. INFORMS
Journal on Computing, 2224))2229-2248, 2022.
Dan Bienstock, Mauro Escobar, Claudio Gentile, and Leo Liberti. Mathematical programming formulations for the alternating current optimal power flow problem. 4OR, 18(3):249 292, 2020.
Pierre Bonami, Andrea Lodi, and Giulia Zarpellon. Learning a classification of mixed-integer quadratic programming problems. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26 29, 2018, Proceedings 15, pp. 604. Springer, 2018.
Stephen Boyd and Lieven Vandenberghe. Conver optimization. Cambridge university press, 2004.
Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing linear programs by graph neural networks. In The Eleventh International Conference on Learning Represenlations, 2023a.
Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing mixed-integer lincar programs by graph neural networks. In The Eleventh International Conference on Learning Representations, 2023b.
Ziang Chen, Xiaohan Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. Expressive power of graph neural networks for (mixed-integer) quadratic programs. arXiv preprint arXi::2406.06 05938, 2024.
Alexander Domahidi, Eric Chu, and Stephen Boyd. Ecos: An socp solver for embedded systems. In 2013 European control conference (ECC), pp. 3071-3076. IEEE, 2013.
Fabio Furini, Emiliano Traversi, Pictro Belotti, Antonio Frangioni, Ambros Gleixner, Nick Gould, Leo Liberti, Andrea Lodi, Ruth Misener, Hans Mittelmann, et al. Qplib: a library of quadratic programming instances. Mathematical Programming Computation, 11:237-2600 265,, 2019.
Quankai Gao, Fudong Wang, Nan Xue, Jin-Gang Yu, and Gui-Song Xia. Deep graph matching under quadratic constraint. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 5069-5078, 2021.
Philip Gill, Walter Murray, and Margaret H Wright. Practical optimization. SIAM, 2019.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2025. URL https: http:://wwwwgg.obb.o com.
Jeffrey Ichnowski, Paras Jain, Bartolomeo Stellato, Goran Banjac, Michael Luo, Francesco Borrelli, Josoph E Gonzalez, Ion Stoica, and Ken Goldberg. Accelerating quadratic optimization with reinforcement learning. Advances in Neural Information Processing Systems, 34:21043-2100 21055, 2021.
13

---

Published in Transactions on Machine Learning Research (11/2025)
Haewon Jung, Junyoung Park, and Jinkyoo Park. Learning context-aware adaptive solvers to accelerate quadratic programming. arXiv preprint urXiv:2211.12444 2022.
Pan Li and Jure Leskovec. The expressive power of graph neural networks. Graph Neural Networks: Foundations, Prontiers, and Applications, pp. 53-98, 2022.
Zhi-Quan Luo, Wing-Kin Ma, Anthony Man-Cho So, Yinyu Ye, and Shuzhong Zhang. Semidefinite relaxation quadratic optimization problems. IEEE Signal Processing Magazine, 27(3):20 34, 2010.
Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999.
Brendan O'Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 169(3):1042 1068, June 2016. URL http://stanford. http://ttaroorttteeee/o////ppppp oo
httd://booy//pppps/ssss...s html
Rajiv Sambharya, Georgina Hall, Brandon Amos, and Bartolomeo Stellato. End-to-end learning to warm-start for real-time quadratic optimization. In Leurning for Dynamics and Coutrol Conference, pp. 220 234.
PMLR, 2023.
Haoru Tan, Chuang Wang, Sitong Wu, Xu-Yao Zhang, Fei Yin, and Cheng-Lin Liu. Ensemble quadratic assignment network for graph matching. International Journal of Computer Vision, pp. 1 1-23, 2024.
Andreas Wächter and Lorenz T Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlincar programming. Mathematical programming, 106:25-57, 2006.
Tao Wang, He Liu, Yidong Li, Yi Jin, Xiaohui Hou, and Haibin Ling. Learning combinatorial solver for graph matching. in 2020 icce. In CVF Conference Computer Vision and Pattern Recognition, CVPR, pp. 13 19, 2020.
Jinxin Xiong, Xi Gao, Linxin Yang, Jiang Xue, Xiaodong Luo, and Akang Wang. Solving quadratic programs via deep unrolled douglas- rachford splitting. Transactions on Machine Learning Research.
Zhixiao Xiong, Fangyu Zong, Huigen Ye, and Hua Xu. Neuralqp: A general bypergraph-basee based optimization framework for large-scale qoqps. arXie preprint 2rXiv:24 10.000...... 03720, 2024.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks powerful memorizers: tight analysis of memorization capacity. Advances in Neural Information Processing Systems, 32, 2019.
Bingxu Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, and Zhong Liu. The expressive power of graph neural networks: A survey, IEEE Transactions on Knowledge and Data Engineering, 2024.
14

---

Published in Transactions on Machine Learning Research (11/2025)
A Detailed proof of main theorem
A.1 Sketch of the proof
We provide a brief outline of this proof:
(i) Separation Power of WL-Test: We first establish that the WL-test has sufficient separation power on the defined target functions.
(ii) Connection tripartite MP-GNNs:
We then demonstrate the relationship between the separation power of tripartite MP-GNNs and that of the Tripartite WI-Lests, showing that the GNNs separate target functions. This result, combined with the generalized Weierstrass theorem, leads to our approximation power conclusions.
(iii) Universal Approximation: Assuming the target functions are continuous and have compact support, we prove universal approximation. In this step, we also specify the problem size and apply the Generalized Weierstrass Theorem (Theorem 22 of Azizian & Lelarge (2020))
(iv) Addressing Discontinuities: Since the target functions are neither continuous nor compactly supported, particularly at the boundary of the convex QCQPs universe IQCQP> construct continuous approximation of the target function to apply universal approximation, ensuring convergence in measure.
A.2 WL-test tripartite graph representation
Here we describe our Tripartite WL.testt, which is the WL.testt counterpart of the tripartite MP-GNNs:
Embedding. Initial colors CO. Co.v and C assigned based on their corresponding features and node types (e.g., from V1, V2, Vz):
0M. <- (f()) for a E Vi,
C + (f())(((v) for v E V2,
C + HASH;(f(c)) for CE V3.
Here, refer the color of node after the t-th message-passing layer as C
Update quadratic nodes via variable nodes (Vi - V2):
C.. HASH
CCe
Σ
wo, (A.HHHA)SCC)))) .V V/2
NEV
Update constraint nodes via variable and quadratic nodes (V,, 1/2 Vg):
Ct+li + HASH
Ch.. WvVi
Σ
Σ VEV.
Wr (A.H((H .vc E
Wn.
Update quadratic nodes again via constraint nodes (V3 + V2):
C <-
HASH
HASHH(HHH .u V/2
Update variable nodes via constraint and quadratic nodes (Vs, V/2 + Vi):
1 +- HASH
C Σ
We, HASH(CCHH.) Σ W.., (....HHH((CH))) Vu E
nEVss
Termination and Readout. Once a termination condition is met, return the color collection
(CTT") DeV, (CT."))CV (TTT))
Multiple accurrences members are counted instead rejected.
15

---

Published in Transactions on Machine Learning Research (11/2025)
All hash functions are real-valued and assumed to be collision-free.
In this paper, we terminate the Tripartite WL-test only when the algorithm stabilizes i.e. when the number of distinct colors no longer changes in an iteration (after all four color updates). Despite not imposing a forced iteration limit, the WL-test is guaranteed to terminate in a finite number of iterations, denoted by T: Proposition 3 (Tripartite WL-test terminates in finite iterations). The Tripartite WL-test stabilizes in finite number of iterations.
Proof. It is straightforward to observe from the formulation that if two nodes have different colors, they will continue to have different colors after an (sub-)iteration. Therefore, the number of iteralions required for stabilization is capped by the number of distinct nodes, which is finite.
We say that the Tripartite WT-lest separales two graphs if the resulting collection of colors differs between the two graphs. We claim that the Tripartite WL-test has the same separation power as its network counterpart, specifically the tripartite MP-GNNs:
Proposition 4 (Tripartite MP-GNNs have equal separation power the Tripartite WL.-Test). Given two instances I and I (correspondingly encoded by graphs G and G), the following holds:
(i) For graph-level output cases, the two instances are separated by FQcQp (R), i.e.,
F(G) = F(G), Fmmm (I) (R)
and only if the two instances are also separated by the Tripartite WL-test.
(ii) For node-level output cases, i.c., R = R", the two instances are separated by FQCQP(() (R), i.e.,
F(G) = F(G), AF E FQOQP (R")
if and only if the two instances are separated by the Tripartite WL-test, and additionally, the variables are correspondingly indexed. Specifically, Cli.us = C must hold for all j E [n]]
For the detailed proof of this proposition, Appendix B.3
A.3 Proof of main theorem
Now we can prove the main theorem. First, we the following proposition. Proposition 5. Let I,I (encoded by G, G' E (QCQP) be two QCQP instances. If the tripartite WL-test fails to separate the two instances, then the following holds:
(i) If one is feasible, the other is also feasible, i... (G) 4 feas (G)
(ii) Assume both instances are feasible. If one is unbounded, the other also unbounded.
(iii) Assume both instances are bounded. Then they have equal optimal values, i.c., (Gbj(G) Ponj (G).
(iv) Assume both instances are bounded and that the variables and constraints are indexed such that Tu, CTa,, Then they have the same optimal solution, with the least fn-norm, i.e., &ool = Gual (G).
Proof. Passing feasibility. Assume that I is feasible, and let x be a feasible solution. By Lemma I we obtain another solution z for instance I, which implics the fcasibility of I. By switching the roles of and I, we prove the reverse claim.
$ For simplicity, we exclude the final iteration showing that the algorithm has stabilized and return the last iteration in which stabilization occurred.
16

---

Published in Transactions on Machine Learning Research (11/2025)
Passing unboundedness. Assume that I is unbounded, i... for any M > 0, there exists solution aM such that the objective (xx v -M For each RM, we can construct solution Eas for I such that the objective f(īM) S f( - - implying that I is also unbounded. Again, by switching the roles of I and I, we prove the reverse claim.
Passing optimal values. Assume that I feasible and bounded, and let x be its optimal solution. By Lemma we construct solution for I such that:
implying that (G) S (G) Similarly, we can show that Pobj(G) S @aby(G), and thus (G) (G).
Passing optimal solutions. To prove the last claim, we need the construction of I from the detailed proof of Lemna 1 (see Appendix B.2).. Assume that I is feasible and bounded, and let x be its optimal solution (with the least f2-norm). By Lemma 1 we construct y for I and for by switching the roles of I and I.
We have f(z) S f(v) S fxx) and ||=|| S llyll S ||=]|, which implics that is not worse than the given optimal solution 2, and thus = By the construction of the averaged solution (and the assumption CT.a, CT. ) we have y = 2. Combining the two equalities, we conclude that x = y.
Lot F be the optimal solution of G. and we have ||ج||| & |lvl = ||=||. By switching the roles of I and I, we obtain ||a||| S ||ā||, and thus || = || Similarly, we have f(z) S f(v) s f(x), and by switching the roles, f(G) fxx)
Since |Bl|| ||>||| ||ح||| and f(y) fz) f()), by uniqueness, we conclude that y I. proving the fourth claim.
The next step is to extend this separation power to approximation power, which leads to our main theorem. We utilize the generalized Weisnstrass-Stone theorem (Theorem 22 and Lemma 36 of Azizian & Lelarge (2020)) ) and Lusin's theorem.
By applying the generalized Weierstrass-Stont theorem, we establish the following proposition, which demonstrates the approximation power on equivariant. functions with compact support.
Proposition 6 (Uniform Approximation on Continuous Equivariant Functions with Compact Support). Let
De: G + R be a general continuous target function defined on a compact subset G. S 9QcQP. such that:
If 1, the output remains unchanged if the input graph is re-indexed.
If n, the output re-indexes accordingly if the input graph is re-indexed.
If the following holds:
Fma = F(G), FocOp (R*) + (G) =+()) vG, G e
,V, vG,
(A.1)
i.e., the family QQcQr (R²) separates the target function +, then for any 8 > 0, there exists a function
F3 F (R$) such that:
[F((G) (GG) <
(A.2)
For the detailed proof, see Appendix B.4
However, the requirement for the larget function to apply the proposition loo strong. In fact, all target functions defined in 3 are non-continuous and not defined on a compact subset, although equivariance naturally holds. Therefore, we soek continuous approximation with compact support that can be uniformly approximated. By applying Lusin's theorem, we construct the following continuous approxination: Proposition (Contimuous Approximation with Compact Support). Let $ : @acqp + R be a general target function that measurable under the probability mcasure P. For any E 0, there exists compact subset g.a.n C 9ocqr, such that TP(G E G. > E, and $ gm continuous.
17

---

Published in Transactions on Machine Learning Research (11/2025)
By combining all the lemmas and propositions, now prove the main theorem.
Proof of Theorem Let & be any target function defined in Definition
3
By Proposition 7 Φ is continuous on a compact subset - S mm.
QOOP with P(G E g. 21- [
We construct 22,4 ((a,))) ("th This subset is continuous with compact support, ensuring that
① 92.0
remains an equivariant function, with the following measure control:
PP(G E go > 1
(A.3)
Since by Proposition and the fact that the Tripartite WL-test has equal separation power as the tripartite MP- GNNs, the target functions equivariant and separated by FQCQP(R*) (R*). Thus, may apply Proposition 6 and obtain F' FQCOP( (IR*) such that:
[F()) (G)] < 8, Gete
This implies that P(I[F(G) - < < > 1-
B Proof of propositions in Section A
This section provides complete proofs several propositions Section A that were not immodiately proven.
B.1 Equivariance
We begin by describing equivariance, a key tool used to capture the fact that the indexing of variables and constraints is irrelevant:
Definition 4. Given function f x + Y, where X and Y are subsets of Euclidean spaces, and group E that acts continuously X and Y, the function f is called equivariant (with respect to the group Σ) if the following holds:
EX
Since the indexing of variables and constraints does not affect the problem, take Σ = Sn Sm, which represents all possible re-indexings of variables and constraints. When applied to both the input and output spaces, we re-index the variables, constraints, and possible solutions (in cases where the output is a solution x E RR). Specifically, we have:
(T())*(1) = qj.k
Px()) = Pj
(6)
4 (().x(()) 4j,k
T() = P)
by(1)
aL (() J
aU x())
where the tilde symbols Q. ì, ,h, I. denote the re-indexed vectors and matrices.
For R R, the action on the output space is the identity map: (T,,)()) = id. For R R wo correspondingly re-index the output, i.c., (T, ()))(() = fÿ.
We also apply the permutations to:
A point in Ra (such as solution), by (T,, (x)))))) zz--
18

---

Published in Transactions on Machine Learning Research (11/2025)
A subset of IR" by applying the permutation to each element in the subset, or to its indicator function by permuting the underlying set.
Equivariance allows show that the indices do not matter, while the inputs (in the form of cocfficient. tuples) necessarily carry these indices.
Remark: Given the group Σ and its action on both the input and output, all massagg-passing layers are automatically equivariant. Thus, requiring E QoQp (R*) to be equivariant is equivalent to requiring the readout layer to be equivariant. This why the readout function must take specific forms in the two cases. While the defined forms do not cover all possible equivariant readout functions, they are general enough capture the separation power.
B.2 Proof of Lemma
For simplicity of proof, we extend the definitions of Lobi and Psol to the entire space SQCQP by assigning a default value of (or O, depending graph G. This occurs when the corresponding instance is either infeasible or unbounded,, and the optimal value or optimal solution does not exist. By doing so, all target functions are defined on the same space &QCQP- Morcover, since we approximate fcasibility and boundedness, we can distinguish whether the output is the default value or genuinely happens to be 0 (or 0).
the output dimension s) when the target function is not defined at
Let I and I be two instances (with Tripartite graph representations G and G S (Qoor that are not separated by the Tripartite WL-test. Without loss of generality, we assume that the variables and constraints are correspondingly indexed, i.e. CT, CT.a; and CT. CTA hold for all i,j.
We first introduce the following notations. Let I be any color, and we collect all nodes of a graph G with color 1, denoting this collection as G(T). Throughout this paper, we use J for the colors of variable nodes, K for quadratic nodes, and I for constraint nodes.
We now present the following lemma:
Lemma 2. Given the graph G, let the Tripartite WL-test stabilize after T 2 O iterations. The sum weights from a certain node one color to all nodes of another color depends only on the color the given node. Specifically, the sum (taking J for variable nodes and K for quadratic nodes as an example) is:
KJG) = Σ
Wu.v
CF.P=K
and is well-defined with u E G(J) arbitrarily chosen.
Similarly, for any color of constraints I, color of variables J, and color of quadratic terms K, the following sums are well-defined:
S(JI;G) = Σ
T.u =
Wy.c:
Cre=I
S(IKK;G) Σ
C.. =
We.
CTe=K
S(KI;;) = Σ
C.'.v = K
Wg,es
GT
S(JKKG)
Wa,wr
CT. =
CTe=K
S(KJ);))
Σ
Woass
CT. = K
CTa=]
Proof. Let v be two nodes with color K= = C.. = C.... further iterations do not separate additional node pairs, i.c.,
Since the Tripartite WL-test has stabilized,
Σ Wn, ww,, HASHHHHSTTTTT
Σ
W HASH(C (TT)..
19

---

Published in Transactions on Machine Learning Research (11/2025)
Rearranging according to J = CTi get:
Σ
Σ CT.EE
Wu. HASH(J)
Σ
E CT.
Wa,n" HASH(J).
Assuming that the hash function is collision-frett we conchude that:
Σ
Σ
Wu,y'
CTREE
CTA=J
i.c., S(K,J; = Ecth= Wans.
CT K is well-defined.
The other claims follow similarly.
By summing all weights between two colors I and J, we derive the following lemma: Lemma 3. Let J and K be arbitrary node colors. Then, the following holds:
[G(J)S(U, K; (C(K))((K,,;C),
and similar equalities hold between and J, and between I and K.
Proof. Summing all edges between all nodes with CT. J and C+. K, and re-arranging the sum according to u and v, by Lemma 2 we have:
-
The other two claims are similar.
We now ready to proceed. We construct ī ক - Hy, where J CT.,, We claim that satisfies all the required conditions.
First, we analyze the linear part of the constraints and the objective. Let fin (x) := p² x represent the linear part of the i-th constraint. For certain color T of constraint nodes, we have:
Pin (T)
Σ
F
Σ Σ 2イ
BJEG(J)
S(1,
[G(T) Σ
G(J)))
(B.1)
G(() Σ S(JII) Σ Zj
ByEG(J)
Σ Σ
Σ
GG() aEG(I) J JEG(J)
Σ (a)
G((I)
GEG())
Here, Ej is the average the nodes with color J, so is determined by J, and denote its value Fz.
20

---

Published in Transactions on Machine Learning Research (11/2025)
We define fin(2) p. For the objective part, have:
p3 EPlIG(J)ER
pJ Σ zj
(B.2)
KGEG(J)
-E Pjaj
where Ps. Pj are the features of the variables, which are determined by the color = CT.ss CT. We denote this value by Pj = Pj = pJ.
Quadratic part. We define Squaa (a) I'x as the quadratic part of the i-th constraint.
For certain color I of constraint nodes, we have the following:
fquad (
Σ
2
(V2(
Σ
Tr
2
K
8 (G(K)((K)
Σ S(I, (K))
Since all Ug E (G) have üj, ūg as neighbors Vi(G), JK : TzJx is well-defined. This equation shows that the value fquad (z) depends only on the color = CTT,, and not on the specific selection of & E G(I).
(z) Therefore, (z) reduces to the sum, and we claim that (i) ( holds.
Next, consider the partial derivative. Let = CT.u, and have:
0 Σ
Squadl (i)
Σ
Σ
wluj, (3))
GEG(T)
(EE((T)
Σ
Σ
Σ
w(u, U..)) C.)
GEG()) K (G(K)
(B.3)
Σ S(K,T)
Σ
w(uj, U3,k)
Σ EG(K)
Since uj is one of the neighbors in Ug and yy E G(K) has exactly two neighbors in Vi(G),, we know that the color of un depends only on the colors = TT,rk and J CT.,,. This makes FKyJ = I well-defined, with uy E G(J) and Uj E G(K).
Thus, the derivative 0, Ec,ea()) depends only on CT,M,, i.e.,
CT.Sh Tii5 On Σ GEG(I)
Fqud (I) O, C.EG(T)
Σ
fqund (z).
(B.4)
By equation B.4 we know that T is a local optimal point within the linear space:
E"
Σ
=; = Σ zz}.
With the convexity assumption, the local optimal point is global minimum. Since x is in this linear space, claim that:
Σ
Squad (T) < Σ
(x).
(B.5)
4EG()
GEG(T)
21

---

Published in Transactions on Machine Learning Research (11/2025)
Combining equation B.5 with the fact that fquad (8) and fquaa (z) are equal for all C₁ G(I), control the quadratic parts:
fquad (T) Squad (T)
Σ
fq quad (z)
G((T)
CEE(()
(B.6)
Squaa (x).
[G(T)
QEE((T
For the objective part, we define fquad (2) 1 T
2 Qz. Similarly, we have:
1 (ūg,))āū
quad (T)
2 2
E
(T
Fg,xEG(K)
1 Σ
Σ MOSNET
2 K V),EE((K)
= Squad (T).
We also have:
dgaquad (J) Σ
Σ
Σ
Σ
(K,
K
which depends only on J = CTiy, Here, (K) = (ug,), and uy E G(K) is well-defined by the stable
color assumption.
Combination of the two parts.
The color CT.a = CT. determines the RHS by by. Defining Soons (w) Squad (x) Sím (2)), and similarly for I, we have:
Ioons ( Iquad (T) + (i)
Σ
(Fquad()) + flim (x))
|G(L)
aEG(T)
1
Σ
feons(x) (x)
|G(I] CEEG()
by-
For the objective, we similarly have:
Jauad ( + Fin(TT) S fquaa( + fum (x).
This completes the proof that 5 is the solution for I, satisfying the condition given in Proposition 1
22

---

Published in Transactions on Machine Learning Research (11/2025)
B.3 Proof of Proposition 4
We prove the separation power by simulating the tripartite WL-test using tripartite MP-GNNs. We define the hidden representation h²', produced by some network, as a one-hot representation of the colors CV if all h4 are onc-hot vectors, and they take the same value if and only they have the same color C
First, we consider the color initialization. We collect all the features paired with the node types (i.e., variable nodes, quadratic nodes, and constraint nodes). Then we select 9.,233 to map the features one-hot vectors, where the enumeration serves as the only index with the value 1.0. For example, if the feature h of a variable node is enumerated by r, then of maps h" to h cr.
It's easy to see that the embedded hidden feature h is onc-hot representation of the initial color CO.
Next, we consider the first refinement. Assuming that h is a one-hot representation of O and gi = id is a simple and proper hash function, the concatenated vector
ho. Σ
NEV
is a representation of the colors Ch. which is generally not one-hot. The same holds for the other three concatenated vectors from the remaining three sub-layers. By Theorem 3.2 of Yun al. 2019 network with four fully connected layers and ReLU activation maps these values back to one-hot. Therefore, select fi to concatenate the imputs and then pass them through a 4-layered MLP with ReLU activation, so that the aggregated hidden representation he is once again one-hot.
Similarly, we get 12,3,4 and 35.3..3.6 and simulate an iteration of the Tripartite WL-test with a round of four message-passee saaagggg sub-layers.
In the case of graph-lovel output, the readout function takes the following form:
R(-) = fout
Σ
Tiu
j.k
Since the hidden representation is one-hot representation of CTr, if two instances are not separated by the tripartite messagc-passing GNN, they are not separated by this subset of GNNs (given fixed initialization and free readout function). Consequently, all entries must be equal, and the two instances are not separated by the Tripartite WL-test.
Similarly, in the case of node-level output, all equivariant readout functions take the form:
R(-); fout (TTus
Σ
Trus Σ
T.
Σ hTa
j.k
Moreover, the variables are Thus, all entries must. be equal, and the two instances are not separated. correspondingly indexed.
Conversely, we use induction to prove that for all E N, the colors C+ separate more than the hidden features Wt,, i.e.,
C a Cit.a' + h = h.w, Vu,u' E Vn FF Fm (RC)
(B.7)
and similar claims hold for the other three sub-iterations.
For / = 0 (iee., right after embedding), the statement is obviously true. Now, assume that after some sub-iteration (say, before the first sub-iteration of iteration t 2 1, with the other sub-iterations following similarly), the statoment holds.
Let v, satisfy:
Σ Wr,, HASH((".. = Σ W. (ASH(C
23

---

Published in Transactions on Machine Learning Research (11/2025)
Organizing the sum by C.." J, and assuming the hash function is collision-free, we have:
Wayy
Waye's
YJ.
(B.8)
N:COMMM m
Next, we organize the sum Eu of by the value of h By the induction assumption, the set {u: hia = hJ is the union of {u Ch. = Jil for some colors J.. Summing the equality in equation B.8 over the colors, we have:
Wu,v
E
Wa,dy Vh.
hr.==
Thus, we conclude:
Σ Σ ww.ofi(h)) = E
E wcht.mmb
E fi(ht.)
which completes the induction.
For the case of graph-level output, this means that all entries of the input to the readout function equal for the two graphs, i..,
Σ
h
Σ
h
I = Σ
-
E
Σ
J.k
3.k
and the GNNs give the same output for all possible readout functions.
For the case of node-level output, we again have:
Tun -(17AS
T.us
h
T.s.
Σ TTRA
In
Σ Σ
h
j.k
3.k
Here, we use the assumption that the variables are correspondingly indexed to guarantee hTMs = T.3.
B.4 Proof of Proposition 6
The requirement for the general target function & is simply equivariance under re-indexing. Thus, we need to verify the conditions required by the generalized Weierstrass theorem (Theorem 22 of Azizian Lelarge (2020)) to apply.
First, we verify that F= FQQQ (R*) is sub-algebra. By multiplying the readout function by X, construct XF E Fmmn (Qqqr("") (R*). Now, we construct the sum and product of two functions Fi, F2 (QcQr((*))
Given Fl and F2, proceed follows:
We construct
gf. ( = [ (1"*), gi. (h We give similar constructions for g2.r and gh.
After initialization, all hidden features take the form f.. = [h h6 (considering variable nodes as an example, and similarly for quadratic nodes). We construct
( = lgi (htp (i. (h422))
and
(h Ewanhi-")
Si (1ip) Σ Wanld (.20) Si (h
Σ Want di f.
We give similar constructions for other gf,r, f' Using this construction, we compute both hidden representations in one concatenated network.
24

---

Published in Transactions on Machine Learning Research (11/2025)
Finally, we obtain F Fi F2 by constructing R(-) R1(-A)) (2((a)))))))))))))))) and similarly for F FiX Thus, we conclude that Fi + F2, Fi x F2 E FQQQP(R") (R²).
Next, we verify the inclusion p(Feca)) - F):
Graph-level output case. In this case; we have Fscal and ay id, so the two sides are exactly the same.
Node-level output case. Given any R1 that maps the final hidden representation to graph-level output, R1 1, RR, R,...., R1) is valid equivariant readout function in the node-level case. Thus, given any F E E QCQP((R) (R), we can construct F" E QcQp (R") (R") using Rí 1,, along with all the / and y functions, and conclude that any pair (G1, G2) E p(Fscal) is not separated by the Tripartite WL-test.
For any pair of graphs (G,G) that not separated by the Tripartite WL.test, after re-indexing variables and constraints, all F E F map them to the same output. This means that, without re-indexing, all F F map the two graphs to outputs that differ at most by re-indexing, Thus, (G, G) is contained in p( o F). This completes our verification.
Applying the Generalized Weierstrass-Stone theorem to the sub-algebra F == F
QCQP (R*) completes the proof.
C Proof of propositions in Section 3.3
The two instances are QCQP instances. Both graphs G and G consist of the following:
variable nodes, i.e., U or ūy where j E [6]. All nodes carry the feature h" = (0, 10, here we assume that S x; S by the unit ball constraint.
12 effective quadratic nodes. The squared nodes carry h (0), while others carry the feature h"s (1).
1 constraint node e representing the unit ball constraint. The node carries feature (-1) for both graphs.
We now verify that the Tripartite WL-test does not separate the graphs:
After initialization, we have hy f00u a.u HASH, ((0, 1), h2 1PPis h (())) hg := h HASH₂((1) and no == 0 = 0 ((1H)
After the first sub-iteration, have
h Ro,5. HASH(HG. 241).
and
75 R0,0, HASH (N.. 211),
which remains equal for all v E V2(G) and 5 E VG)
After the second oub-iteration, we have
h h.c h HASH (22 0, 0.1)).
which remains equal for both graphs.
After the third sub-iteration, we have
h1 = 1. 115s = HASH(H), 1- -1)),
and
h : h4v1, HASH(5), 0),
which remains equal for both graphs.
25

---

Published in Transactions on Machine Learning Research (11/2025)
After the final sub-iteration, we have
h = h 1. 11." HASH(H)) 0, hi2 + +1-1g))
which remains equal for both graphs.
The Tripartite WL-test terminates after one iteration since no further node pairs are separated.
The Tripartite WL-test returns C which is the same for both instances. Thus, conclude that the two graphs are not separated, with variables and constraints correspondingly indexed. By Proposition | we conclude that, in both the node-level and graph-level cases, tripartite MP-GNNs cannot separate the two instances.
Therefore, we conclude that tripartite MP-GNNs cannot approximate the optimal solution or optimal value for non-convex QCQP instances (even QP instances). To demonstrate that tripartite MP-GNNs cannot. accurately predict feasibility, slightly modify the two instances:
Proof of Proposilion instances:
We reconstruct the objective as constraint. Specifically, consider the following two
min WERS
0
3
s.t.
31
T2I3 + 23 Z445 + 2546 I6F1 S
(C.1)
6
Σ
1
and
min wER
0
3
s.t.
T1 r223 + 2331 2ATs + 25 I6 S
(C.2)
Σ 2 <
Clearly, instance C.1 is not feasible, while instance C.2 is feasible.
In the graph generated by the Tripartite graph representation, we change the objective to another special constraint and add dummy objective. Similarly, we that tripartite MP-GNNs fail to separate I
and Z.
]
D Additional experiments
Evaluation on the QPLIB dataset. We incorporated dataset derived from real-world instances in QPLib. Due to computational constraints, we used all instances in QPLIB that are convex and have no more than 5,000 nonzeros as training sets, and augmented these instances by perturbations. Below, we report the training and validation losses in Table 5 and Table t respectively.
Table Training loss vs. numbers of parameters on QPLIB.
# Parameters
Target
15K
42K
126K
450K
1.7M
objective
4.3306
0.9986
0.8679
0.7999
0.6614
solution
19.2789
18.9083
18.8303
18.7472
18.6495
As shown, both training and validation losses improve consistently with increased model capacity and training samples. Such trend supports the method's effectiveness real-world QCQP instances.
26

---

Published in Transactions on Machine Learning Research (11/2025)
Table 6: Validation loss vs. numbers training samples on QPLIB.
# Samples
Target
100
300
500
700
1000
objective
1.5414
0.8922
0.8564
0.6176
0.5598
solution
19.9106
19.7552
19.6981
19.6788
19.6165
Evaluation boundedness. We further evaluated performance the task of predicting the boundedness of convex QCQPs. Specifically, unbounded cases arise when there exists direction d such that Qd = 0 and d'd < 0 for both the objective and constraints. To examine performance under these challenging edge cases, we generated dedicated dataset by randomly enforcing such conditions. Using the same training setup as in Scction 4.4, the corresponding training and validation losses are reported in Tables anddd
Table 7: Training loss vs. number of parameters on predicting boundedness.
#Params
21k
42k
126k
1.7M
6.7M
Train loss 0.6933
0.2504
0.1241
0.0470
0.0427
Table 8: Validation loss vs.
number of training samples predicting boundedness.
#Samples
100
300
500
700
1000
Valid loss 0.6876
0.3495
0.2786
0.2360
0.1285
The results show a clear trend: training loss decreases with larger model sizes, and validation loss improves with more training data. These results suggest. that our approach is capable of learning effectively on unbounded problem instances.
27


Reviews:
[{"review_id": "cKrzfXsSam", "reviewer": "Reviewer_9eGe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main contribution of the paper is the design of the graph representation of a QCQP and the associated GNN, as well as the mathematical result on universal approximation, which to my knowledge are novel and potentially interesting to the community.\n\nI do not have major concerns about the work, but suggest that the authors consider the questions and comments below.\n\n1) >There are two natural extensions of the traditional bipartite representation of LP/LCQP to QCQP.\n\nTo make the work more self-contained, the authors should discuss how bipartite graph structure has been used in the literature to represent LPs and LCQPs, and concretely highlight why this approach does not extend to QCQPs.\n\n2) >In this method, all coefficients are encoded as features associated with the n variable nodes and the m constraint nodes, resulting in a graph with vector features of varying sizes, depending on the problem. However, existing GNNs are generally incapable of processing features of varying dimensions.\n\nThis paragraph is not clear. Why is this not an issue in LP and LCQP?\n\n3) >We remark that there is a one-to-one mapping between a QCQP and its tripartite graph representation $G_{QCQP}$.\n\nThis is not clear to me. Is this statement proved in the paper? I do not see why this is true, particularly because the $b_i$ terms in a QCQP do not appear in the graph representation.\n\n4) Regarding Section 4, it is good that authors provide results highlighting the limitations of the proposed architecture when the QCQP is non-convex. To confirm, this does not say anything about whether non-convex QCQPs can possibly be universally approximated by other graph structure?\n\n5) Regarding running time comparison in Section 5 -- I do not think comparing the running time alone is meaningful. IPOPT solver is slower, but should have a higher accuracy. The information in Table 3 should be juxtaposed with the solution quality so we can better understand the trade-off.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**I work on optimization but have limited knowledge of GNNs. Therefore, I am not able to assess a major and important part of the contribution. My review is based on my best understanding from reading the main paper (I did not check the proofs in the appendix).**\n\nThe paper studies representing convex QCQPs using GNNs, and proposes a tripartite representation which separates the variable, objective, and constraint information into three types of nodes: variables, quadratic terms, and constraints. The authors introduce a corresponding GNN architecture and prove that it can approximate any QCQP arbitrarily well. They also provide negative results showing that non-convex QCQPs cannot be represented by the proposed architecture. Some empirical results are provided that show solution quality improvement as the number of GNN parameters increases and reduced running time compared to a standard QCQP solver.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see my main questions and comments above. Some other minor typos are:\n\n1) > The first theoretical result demonstrating the representation power of GNNs in solving optimization problems was provided by Yin et al. Chen et al. (2023a).\n\nDo the authors want to reference Yin et al. or Chen et al.?\n\n2) The reference to Problem 3.3 on the bottom of page 8 repeats, and Problem 3.3 is not properly linked to the equation.", "broader_impact_concerns": "No foreseeable ethical concerns to my knowledge.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xvrA9nQlt4", "reviewer": "Reviewer_Uu7y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nS1. The formulation of a tripartite graph to represent a QCQP appears to be a natural extension of the approaches explored in [1] and [2].\n\nS2. The proposed tripartite message-passing GNN demonstrates potential in effectively solving convex QCQPs by capturing key attributes such as feasibility, boundedness, optimal solutions, and optimal values.\n\nS3. The proof of universal approximation for convex QCQPs is compelling, and the accompanying counterexample is both clear and sound.\n\n\nWeaknesses:\n\nW1. The experimental evaluation appears somewhat underwhelming, as the datasets used are simulated, of at most moderate size, and do not adequately reflect the breadth of the theoretical claims made for the tripartite message-passing GNNs.\n\nW2. This work lacks a discussion on the computational aspects and limitations of the proposed GNN approach. Further analysis of computational complexity, network size, and the role of sparsity would help clarify the practical scenarios where the method can be effectively applied.\n\nW3. The proof appears to be an extension of the result presented in [2]. The authors are encouraged to highlight the key innovations and challenges addressed to better distinguish their contribution. Additionally, the writing in Section 3.1 feels disjointed and would benefit from restructuring to provide clearer context and motivation, which are currently lacking.\n\n[1] Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing mixed-integer linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations, 2023.\n\n[2] Ziang Chen, Xiaohan Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. Expressive power of graph neural networks for (mixed-integer) quadratic programs. arXiv preprint arXiv:2406.05938, 2024.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work focuses on the representational capacity of Graph Neural Networks (GNNs) for solving convex Quadratically Constrained Quadratic Programs (QCQPs). While previous studies have demonstrated the effectiveness of GNNs for linear and linearly constrained quadratic programs, this work investigates their ability to reliably capture key properties of general convex QCQPs through a tripartite graph formulation. This formulation underpins the proposed tripartite message-passing GNNs, which are used to assess feasibility, boundedness, optimal values, and optimal solutions of convex QCQPs.\n\nThe authors establish a universal approximation theorem tailored to convex QCQPs and provide a counterexample showing that message-passing GNNs cannot represent general non-convex QCQPs. The experimental section supports the theoretical findings using three convex QCQP instances: a general QCQP, a constrained least squares problem, and a trust-region subproblem, each generated via variants of normal distributions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.\tSection 3.1 would benefit from additional context and motivation, particularly in explaining the utility of its components rather than merely describing the dynamics of the sub-layers.\n\n2.\tThe proof of universal approximation should more clearly highlight the specific challenges addressed and how they differ from or extend the work of Chen et al. (2024).\n\n3.\tA discussion on the computational requirements of the tripartite message-passing GNN, including its practical advantages and limitations, would enhance the presentation.\n\n4.\tWhile the experiments focus on three synthetic convex QCQP datasets, incorporating a real-world dataset could better demonstrate the practical applicability of the proposed method.\n\n5.\tSince sparsity is fixed at 0.95, an ablation study varying the sparsity level could yield more informative insights.\n\n6.\tComparisons to additional baseline solvers such as the Operator Splitting QP Solver, Splitting Conic Solver, and Embedded Conic Solver, along with IPOPT, would strengthen the evaluation.\n\n7.\tIncluding examples that demonstrate the approach's handling of infeasibility, unboundedness, and multiple optimal solutions would showcase its robustness.\n\n8.\tThe final sentence of the first paragraph in the Introduction contains a clause after the comma that appears unrelated to the preceding content.\n\n9.\tThere is a typo in the first sentence of the final paragraph preceding the Notations section.\n\n10.\tIn Section 2.2, Yin et al. is cited in the text but is missing from the list of references.", "broader_impact_concerns": "Not very applicable here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HRfUCRCZVX", "reviewer": "Reviewer_ttAE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n1. Novel Representation:\nThe paper introduces a tripartite graph representation tailored for convex QCQPs. To the best of my knowledge, this is a novel contribution  in the literature. This structured representation enables a natural application of GNNs, which aligns well with the growing body of research exploring the integration of learning-based models with traditional optimization frameworks.\n\n2. Rigorous Theoretical Foundation:\nThe authors provide solid theoretical analysis to support their proposed framework. I have reviewed the proofs and find them to be overall correct. Particularly noteworthy is the result showing that GNNs cannot represent certain properties of non-convex QCQPs, establishing a clear boundary of applicability for the proposed method. This theoretical insight enriches our understanding of the representational power of GNNs in optimization.\n\n3. Empirical Validation:\nThe paper backs up its theoretical claims with a set of numerical experiments. These experiments demonstrate the feasibility of using GNNs to approximate key aspects of convex QCQPs, including feasibility, optimal value, and solutions. This empirical evidence helps validate the practical relevance of the proposed framework and suggests possible applications in large-scale or real-time settings.\n\n4. Toy example and illustrating figures:\nI like the writing style of the paper which help to follow the key ideas of the paper. \n\n# Weaknesses\n1. Heavy Notation:\nThe notation used in the paper is quite heavy, making the paper more difficult to follow.\n\n2. Limited Prediction Accuracy:\nAlthough the paper includes numerical evaluations, the reported accuracy of the GNN predictions appears relatively poor. In many practical settings, particularly those requiring precise optimization outputs, an error threshold on the order of $10^{-3}$ is generally expected. The authors should either improve the model’s prediction performance or clarify the contexts in which the current level of accuracy is acceptable.\n\n3. Unjustified Runtime Comparisons:\nThe comparison of inference runtime between the trained GNN and classical solvers is somewhat misleading. It is well known that once trained, neural networks, including GNNs, can make predictions very quickly, so comparing inference time to solver runtimes does not yield meaningful insights. Moreover, among the classical solvers, IPOPT is not generally considered state-of-the-art for convex QCQPs, it is more useful for general convex nonlinear programming problems; solvers like Gurobi or MOSEK are typically more efficient and robust. It would be more convincing to compare against such baselines, or at least discuss the rationale behind the current solver choices.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a novel tripartite graph representation for general convex QCQPs and demonstrates how this structure can be effectively used with message-passing GNNs. The authors show that GNNs, when applied to this new representation, can reliably capture essential properties of convex QCQPs, such as feasibility, optimal value, and optimal solution. This work bridges convex optimization and graph-based machine learning, offering a certain new perspective in solving large-scale QCQPs and expanding the representational capacity of GNNs in mathematical optimization.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. **Simplify Notation for Clarity**  \n   The current notation is sometimes dense and may be difficult for readers to follow, especially those less familiar with convex QCQPs or GNN architectures. Please consider simplifying the notation where possible and providing more intuitive explanations alongside the formal definitions to enhance readability.\n\n2. **Report Higher-Accuracy Results**  \n   To better understand the limitations and potential of the proposed method, please include computational results that target a solution accuracy of at least $10^{-3}$. This level of precision is often required in practical applications and would help clarify whether the framework can meet such standards, or if there are fundamental obstacles to achieving this level of accuracy.\n\n3. **Justify Loss Function Choice for Feasibility Prediction**  \n   The use of cross-entropy loss for predicting feasibility raises questions, particularly because feasibility is typically a geometric or algebraic property rather than a classification label. Please clarify the rationale behind this choice and consider discussing whether alternative formulations might be more appropriate.\n\n4. **Compare with Stronger Baselines**  \n   The current comparison with IPOPT may not be sufficient, as IPOPT is not generally optimized for convex QCQPs. Please consider adding comparisons with more appropriate state-of-the-art solvers such as **Gurobi** or **MOSEK**, which are widely recognized for their efficiency and robustness in handling convex quadratic problems. This would provide a more meaningful benchmark for evaluating the performance of your GNN-based approach. Please also consider a proper way to compare the overal efficiency not just the inference time.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)