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

## Abstract

Abstract. Quadratic programming (QP) is the most widely applied category of problems in nonlinear programming. Many applications require real-time/fast solutions, though not necessarily with high precision. Existing methods either involve matrix decomposition or use the preconditioned conjugate gradient method. For relatively large instances, these methods cannot achieve the real-time requirement unless there is an effective preconditioner. Recently, graph neural networks (GNNs) opened new possibilities for QP. Some promising empirical studies of applying GNNs for QP tasks show that GNNs can capture key characteristics of an optimization instance and provide adaptive guidance accordingly to crucial configurations during the solving process, or directly provide an approximate solution. Despite notable empirical observations, theoretical foundations are still lacking.
In this work, we investigate the expressive or representative power of GNNs, a crucial aspect of neural network theory, specifically in the context of QP tasks, with both continuous and mixed-integer settings. We prove the existence of message-passing GNNs that can reliably represent key properties of quadratic programs, including feasibility, optimal objective value, and optimal solution. Our theory is validated by numerical results.

## 1. Introduction

Quadratic programming (QP) is an important type of optimization problem, with extensive applications across domains such as graph matching, portfolio optimization, and dynamic control [vogelstein2015fast, markowitz52, rockafellar1987linear]. The goal of QP is to minimize a quadratic objective function while satisfying specified constraints. These constraints can vary, leading to different subcategories of QP.
When all the constraints are linear, we call a QP problem a linearly constrained quadratic program (LCQP). When they also involve quadratic inequalities, we call the problem a quadratically constrained quadratic program (QCQP).
Furthermore, if the problem requires some variables to be integers, we call it mixed-integer QP. In this study, we focus on LCQP and its mixed-integer variant MI-LCQP.

In many real-world applications, finding solutions quickly is crucial, even if they are not perfectly precise. For example, in transportation systems, such as ride-hailing platforms like Uber or Lyft, matching drivers with passengers requires quick decision-making to minimize waiting times, even if the optimal solution is not attained. Similarly, in financial trading, algorithms must swiftly adjust investment portfolios in response to market changes, even if it is not the most optimal move.

Unfortunately, existing methods for solving QP often rely on some computationally expensive techniques such as matrix decomposition and the preconditioned conjugate gradient method. For instance, matrix decomposition techniques like LU decomposition typically require $\mathcal{O}(n^{3})$ operations for a matrix with size $n\times n$ [golub2013matrix], although more advanced algorithms can achieve lower complexities. Similarly, the preconditioned conjugate gradient method involves $\mathcal{O}(n^{2})$ operations per iteration, and a high condition number of the matrix can lead to slow convergence or numerical instability [shewchuk1994introduction]. These considerations underscore the clear need for novel techniques to address the demands of real-time applications.

Machine learning (ML) brings new chances to QP. Recent research indicates that deep neural networks (DNNs) can significantly improve the efficiency of the QP solving process. Based on the role of DNNs in the solving process, these studies can be broadly categorized into two classes:

- •
Type I: DNNs are used to accelerate an existing QP solver by processing QP instances along with relevant intermediate solving information. The DNNs then generate adaptive configurations tailored to the specific instance and context, optimizing the QP solving process. Success in this application relies on the DNN’s ability to capture in-depth features of QP instances and provide customized guidance to the solver [bonami2018learning, bonami2022classifier, ichnowski2021accelerating, getzelman2021learning, jung2022learning, king2024metric].
- •
Type II: DNNs replace or warm-start a QP solver. Here, DNNs take in a QP instance and directly output an approximate solution. This approximate solution can be used directly or as an initial solution for further refinement by a QP solver [nowak2017note, chen2018approximating, karg2020efficient, wang2020combinatorial, wang2020learning, wang2021neural, qu2021adaptive, gao2021deep, bertsimas2022online, liu2022revocable, sambharya2023end, pei2023reinforcement, tan2024ensemble].

Among the various types of DNNs, this paper focuses on graph neural networks (GNNs) due to their properties that align well with QP tasks. GNNs [scarselli2008graph] are defined on graphs and have been applied widely in many areas such as recommender systems, traffic management, and chemistry [wu2020comprehensive, zhou2020graph]. By conceptualizing QP problems as graphs, where all pertinent information including coefficients and boundaries are encoded into the graph’s attributes, GNNs can efficiently process and solve these QP tasks [nowak2017note, wang2020learning, wang2021neural, qu2021adaptive, gao2021deep, tan2024ensemble, jung2022learning]. An example of such a graph representation is illustrated in Figure 1. This approach leverages key advantages of GNNs: they adapt naturally to different sizes of graphs, allowing the same model to be applied to various QP problems without modification, and they are permutation invariant, ensuring that the output remains consistent regardless of the order of nodes. These features make GNNs particularly suitable for QP tasks, including their simplified forms like linear programming (LP).

Figure: Figure 1. An illustrative example of LCQP and its graph representation.

However, despite notable empirical results, a systematic understanding of GNN for QP is still lacking. To thoroughly understand its pros and cons, some critical questions must be addressed:

- •
(Existence). Are there GNNs that can either capture the essential characteristics of QPs or provide approximate solutions? This question is named the expressive power of GNNs.
- •
(Trainability). If such GNNs exist, can we find them? The process of finding such GNNs is named training, which involves gathering data, creating a method to measure success or failure (a loss function), and then refining the GNN to reduce the loss function.
- •
(Generalization). Can a trained GNN perform effectively on QP instances it has not previously encountered? This concerns the generalization ability of GNNs.

This paper primarily addresses the first question about the expressive power. For Type I applications, we investigate whether GNNs can accurately map a QP to its crucial features, focusing on feasibility and the optimal objective value. For Type II, we examine whether GNNs can map a QP to one of its optimal solutions. Formally, the question motivating this paper is:

$$ (1.1) Are there GNNs that can accurately predict the feasibility, optimal objective value, and an optimal solution of a QP? $$

The literature has explored the expressive capabilities of GNNs on general graph tasks [xu2019powerful, azizian2020expressive, geerts2022expressiveness, zhang2023expressive, li2022expressive, sato2020survey] and their ability to approximate continuous functions on graphs [azizian2020expressive, geerts2022expressiveness]. However, significant gaps remain in fully understanding how these capabilities relate to QP, as the connections between QP features (such as feasibility and optimal objective value) and graph properties have not been thoroughly established.

Contributions of this paper include:

- •
(GNN for LCQP). We provide an affirmative answer to question (1.1), establishing a theoretical foundation for using GNNs for LCQP, across both Type I and II applications.
- •
(GNN for MI-LCQP). In the case of MI-LCQP, our findings generally suggest a negative answer to question (1.1). However, we identify specific, precisely defined subclasses of MI-LCQP where GNNs can accurately predict feasibility, boundedness, and an optimal solution.
- •
(Experimental Validation). We conduct experiments that directly validate the above results.

## 2. Preliminaries

This section introduces foundational concepts and preliminary definitions. We focus on linearly constrained quadratic programming (LCQP), which is formulated as follows:

$$ (2.1) $\min_{x\in\mathbb{R}^{n}}~{}~{}\frac{1}{2}x^{\top}Qx+c^{\top}x,\quad\textup{s. t.}~{}~{}Ax\circ b,\ l\leq x\leq u,$ $$

where $Q\in\mathbb{R}^{n\times n}$, $c\in\mathbb{R}^{n}$, $A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^{m}$, $l\in(\mathbb{R}\cup\{-\infty\})^{n}$, $u\in(\mathbb{R}\cup\{+\infty\})^{n}$, and $\circ\in\{\leq,=,\geq\}^{m}$. In this paper, we assume $Q$ is symmetric and positive semidefinite, then the problem (2.1) is a convex program.

Basic concepts of LCQPs. An $x$ that satisfies all the constraints of (2.1) is named a feasible solution. The set of all feasible solutions, defined as $X=:\{x\in\mathbb{R}^{n}:Ax\circ b,\ l\leq x\leq u\}$, is referred to as the feasible set. The LCQP is considered feasible if this set is non-empty; otherwise, it is infeasible. The value of $\frac{1}{2}x^{\top}Qx+c^{\top}x$ is named the objective (function) value. Its infimum across the feasible set is termed the optimal objective value. If this infimum is unattainable ($-\infty$), suggesting the objective value could indefinitely decrease, the LCQP is deemed unbounded. Conversely, when the optimal objective value is realized, the corresponding $x$ is identified as an optimal solution. According to [eaves1971quadratic], a feasible and bounded LCQP must yield an optimal solution, though it might not be unique.

Graph representation of LCQPs. We introduce a graph structure, termed the LCQP-graph $G_{\textup{LCQP}}=(V,W,A,Q,H_{V},H_{W})$, that encodes all the elements of a LCQP (2.1). Particularly,

- •
The graph contains two distinct types of nodes. Nodes in $V=\{1,2,\dots,m\}$, labeled as $i$, represent the $i$-th constraint and are called constraint nodes. Nodes in $W=\{1,2,\dots,n\}$, labeled as $j$, represent the $j$-th variable and are known as variable nodes. The union set $V\cup W$ includes all the vertices of the entire LCQP-graph $G_{\textup{LCQP}}$.
- •
The graph comprises two distinct edge types. An edge connects $i\in V$ to $j\in W$ if $A_{ij}$ is nonzero, with $A_{ij}$ serving as the edge weight. Similarly, the edge between nodes $j,j^{\prime}\in W$ exists if $Q_{jj^{\prime}}\neq 0$, with $Q_{jj^{\prime}}$ as the edge weight. Self loops ($j=j^{\prime}$) are permitted.
- •
Attributes/features $v_{i}=(b_{i},\circ_{i})$ are attached to the $i$-th constraint node for $i\in V$. The collection of all such attributes is denoted as $H_{V}=(v_{1},v_{2},\dots,v_{m})$.
- •
Attributes/features $w_{j}=(c_{j},\ell_{j},u_{j})$ are attached to the $j$-th variable node for $j\in W$. The collection of all such attributes is denoted as $H_{W}=(w_{1},w_{2},\dots,w_{n})$.

Such a representation is illustrated by an example shown in Figure 1. To the best of our knowledge, this particular representation is only detailed in [jung2022learning], yet it forms the foundation or core module for numerous related studies.
For instance, removing nodes in $V$ and their associated edges reduces the graph into the assignment graph used in graph matching problems [nowak2017note, wang2020learning, wang2021neural, qu2021adaptive, gao2021deep, tan2024ensemble]. In these cases, the linear constraints $Ax\circ b$ are typically bypassed by applying the Sinkhorn algorithm to ensure that $x$ meets these constraints.
Another scenario involves LP and MILP: removing edges associated with $Q$ simplifies the graph to a bipartite structure, which reduces the LCQP to an LP [chen2022representing-lp, fan2023smart, liu2024learning, qian2024exploring]. Further, by incorporating an additional node feature—an approach detailed in Section 4—this bipartite graph is also capable of representing MILP [gasse2019exact, chen2022representing-milp, nair2020solving, gupta2020hybrid, shen2021learning, gupta2022lookback, khalil2022mip, paulus2022learning, scavuzzo2022learning, liu2022learning, huang2023searching]. Notably, the body of work on MILP using this approach extends well beyond the cited references, indicating its robust and growing interest.
The demonstrated empirical success of utilizing graph representations and GNNs in various optimization tasks underpins the motivation for this paper: we aim to explore the theoretical foundations of these methodologies.

GNNs for solving LCQPs. Building on the established concepts, we present message-passing graph neural networks (hereafter referred to simply as GNNs) tailored for LCQPs using LCQP-graphs. These GNNs take in an LCQP-graph $G_{\textup{LCQP}}$ (including all the node features and edge weights) as input and update node features sequentially across layers via a message-passing mechanism. Initially, node features $s_{i}^{0},t_{j}^{0}$ are computed using embedding mappings $f_{0}^{V},f_{0}^{W}$:

- •
$s_{i}^{0}=f_{0}^{V}(v_{i})$ for $i\in V$, and $t_{j}^{0}=f_{0}^{W}(w_{j})$ for $j\in W$.

The architecture includes $L$ standard message-passing layers where each layer (where $1\leq l\leq L$) updates node features by locally aggregating neighbor information:

- •
$s_{i}^{l}=f_{l}^{V}\big{(}s_{i}^{l-1},\sum_{j\in W}A_{ij}g_{l}^{W}(t_{j}^{l-1}
)\big{)}$ for $i\in V$, and
- •
$t_{j}^{l}=f_{l}^{W}\big{(}t_{j}^{l-1},\sum_{i\in V}A_{ij}g_{l}^{V}(s_{i}^{l-1}
),\sum_{j^{\prime}\in W}Q_{jj^{\prime}}g_{l}^{Q}(t_{j^{\prime}}^{l-1})\big{)}$ for $j\in W$.

Finally, there are two types of output layers. For applications where the GNN maps LCQP-graphs to a singular real value, such as evaluating properties like feasibility of the LCQP, a graph-level output layer is employed that computes a single real number encompassing the entire graph:

- •
$y=r_{1}\big{(}\sum_{i\in V}s_{i}^{L},\sum_{j\in W}t_{j}^{L}\big{)}\in\mathbb{R}$.

Alternatively, if the GNN is required to map the LCQP-graph to a vector $y\in\mathbb{R}^{n}$, assigning a real number to each variable node as its output (as is typical in applications where GNNs are used to predict solutions), then a node-level output should be utilized. This output layer computes the value for the $j$-th output as follows:

- •
$y_{j}=r_{2}\big{(}\sum_{i\in V}s_{i}^{L},\sum_{j\in W}t_{j}^{L},t_{j}^{L}\big{)}$.

In our theoretical analysis, we assume all the mappings $f_{l}^{V},f_{l}^{W}\ (0\leq l\leq L)$, $g_{l}^{V},f_{l}^{W},g_{l}^{Q}\ (1\leq l\leq L)$, and $r_{1},r_{2}$ to be continuous. In practice, these continuous mappings are learned from data. We aim to find mappings that enable all the LCQP-graphs $G_{\textup{LCQP}}$ from a dataset to be mapped accurately to their desired outputs $y$. To achieve this, we parameterize these mappings using multilayer perceptrons (MLPs) and optimize them within the parametric space. Based on all the concepts above, we present some definitions.

###### Definition 2.1 (Space of LCQP-graphs) .

The set of all LCQP-graphs, denoted as $\mathcal{G}^{m,n}_{\textup{LCQP}}$, comprises graphs with $m$ constraints and $n$ variables, where the matrix $Q$ is symmetric and positive semidefinite.

###### Definition 2.2 (Spaces of GNNs) .

The collection of all message-passing GNNs, denoted as $\mathcal{F}_{\textup{LCQP}}$ for graph-level outputs (or $\mathcal{F}_{\textup{LCQP}}^{W}$ for node-level outputs), consists of networks constructed using continuous mappings $f_{l}^{V},f_{l}^{W}\ (0\leq l\leq L)$, $g_{l}^{V},f_{l}^{W},g_{l}^{Q}\ (1\leq l\leq L)$, and $r_{1}$ (or $r_{2}$).

Note that the input graph size for GNNs within $\mathcal{F}_{\textup{LCQP}}$ and $\mathcal{F}_{\textup{LCQP}}^{W}$ is unspecified, as the functions $f_{l}^{V},f_{l}^{W}\ (0\leq l\leq L)$, $g_{l}^{V},f_{l}^{W},g_{l}^{Q}\ (1\leq l\leq L)$, and $r_{1}$ (or $r_{2}$) are independent of $m,n$. This independence highlights a key advantage of GNNs discussed in Section 1: their adaptability to various graph sizes, allowing the same model to be consistently applied across different QPs.

###### Definition 2.3 (Target mappings) .

We define three mappings for LCQPs.

- •
Feasibility mapping: $\Phi_{\textup{feas}}(G_{\textup{LCQP}})=1$ if the LCQP problem associated to $G_{\textup{LCQP}}$ is feasible and $\Phi_{\textup{feas}}(G_{\textup{LCQP}})=0$ if it is infeasible.
- •
Optimal objective value mapping: $\Phi_{\textup{obj}}(G_{\textup{LCQP}})\in\mathbb{R}\cup\{\pm\infty\}$ computes the optimal objective value of the LCQP problem associated to $G_{\textup{LCQP}}$. $\Phi_{\textup{obj}}(G_{\textup{LCQP}})=+\infty$ means the problem is infeasible and $\Phi_{\textup{obj}}(G_{\textup{LCQP}})=-\infty$ means the problem is unbounded.
- •
Optimal solution mapping: For an feasible and bounded LCQP problem $G_{\textup{LCQP}}$, i.e., $\Phi_{\textup{obj}}(G_{\textup{LCQP}})\in\mathbb{R}$, there must exist an optimal solution [eaves1971quadratic] though it might not be unique. However, the optimal solution with the smallest $\ell_{2}$-norm must be unique if $Q\succeq 0$ by similar argument as in [chen2022representing-lp]*Remark 2.2 and we define it as $\Phi_{\textup{sol}}(G_{\textup{LCQP}})$.

Given the definitions above, we can formally pose the question in (1.1) as follows: Is there any $F\in\mathcal{F}_{\textup{LCQP}}$ that well approximates $\Phi_{\textup{feas}}$ or $\Phi_{\textup{obj}}$? Similarly, is there any function $F_{W}\in\mathcal{F}_{\textup{LCQP}}^{W}$ that well approximates $\Phi_{\textup{sol}}(G_{\textup{LCQP}})$?

###### Definition 2.1 (Space of LCQP-graphs) .

###### Definition 2.2 (Spaces of GNNs) .

###### Definition 2.3 (Target mappings) .

## 3. Unversal approximation of GNNs for LCQPs

This section presents our main theoretical results for the expressive power of GNNs for representing properties of linearly constrained quadratic programs (LCQPs). In particular, we show that for any LCQP data distribution, there always exists a GNN that can predict LCQP properties, in the sense of universally approximating target mappings in Definition 2.3, within some given error tolerance. Such results answer the question (1.1) positively. We state the assumption required for our main theorems.

###### Assumption 3.1 .

$\mathbb{P}$ is a Borel regular probability measure on $\mathcal{G}^{m,n}_{\textup{LCQP}}$ (^1^11The space $\mathcal{G}^{m,n}_{\textup{LCQP}}$ is equipped with the subspace topology induced from the product space $\big{\{}(A,b,c,Q,l,u,\circ):A\in\mathbb{R}^{m\times n},b\in\mathbb{R}^{m},c\in \mathbb{R}^{n},Q\in\mathbb{R}^{n\times n},l\in(\mathbb{R}\cup\{-\infty\})^{n}, u\in(\mathbb{R}\cup\{+\infty\})^{n},\circ\in\{\leq,=,\geq\}^{m}\big{\}}$, where all Euclidean spaces have standard Eudlidean topologies, discrete spaces $\{-\infty\}$, $\{+\infty\}$, and $\{\leq,=,\geq\}$ have the discrete topologies, and all unions are disjoint unions.).

The assumption of Borel regularity is generally satisfied for most data distributions in practice, including discrete distributions, gaussian distributions, etc.

We first state the universal approximation result of MP-GNNs for representing the feasibility of LCQP directly implied by the previous work [chen2022representing-lp] on linear programs, as feasibility is solely determined by the constraints, independent of the objective function, and all LCQP constraints are linear.

###### Theorem 3.2 ( [ chen2022representing-lp ] *Theorem 3.2) .

For any probability measure $\mathbb{P}$ on $\mathcal{G}^{m,n}_{\textup{LCQP}}$ satisfying Assumption 3.1 and any $\epsilon>0$, there exists $F\in\mathcal{F}_{\textup{LCQP}}$ such that $\mathbb{I}_{F(G_{\textup{LCQP}})>\frac{1}{2}}$ can act as a classifier for LCQP-feasibility, with an error of up to $\epsilon$:

$$ $\mathbb{P}\big{[}\mathbb{I}_{F(G_{\textup{LCQP}})>\frac{1}{2}}\neq\Phi_{ \textup{feas}}(G_{\textup{LCQP}})\big{]}<\epsilon,$ $$

where $\mathbb{I}_{\cdot}$ is the indicator function: $\mathbb{I}_{F(G_{\textup{LCQP}})>\frac{1}{2}}=1$ if $F(G_{\textup{LCQP}})>\frac{1}{2}$; $\mathbb{I}_{F(G_{\textup{LCQP}})>\frac{1}{2}}=0$ otherwise.

Secondly, we show that there always exist GNNs that can approximate the optimal objective value mapping $\Phi_{\textup{obj}}$ very well in two senses: (1) GNN can predict whether the optimal objective value is a real number or $\pm\infty$, i.e., whether the LCQP problem is feasible and bounded or not. (2) For a data distribution over feasible and bounded LCQP problems, GNN can approximate the real-valued optimal objective value mapping.

###### Theorem 3.3 .

Let $\mathbb{P}$ be a probability measure on $\mathcal{G}^{m,n}_{\textup{LCQP}}$ satisfying Assumption 3.1.

- (1)
For any $\epsilon>0$, there exists $F_{1}\in\mathcal{F}_{\textup{LCQP}}$ such that
$\mathbb{P}\big{[}\mathbb{I}_{F_{1}(G_{\textup{LCQP}})>\frac{1}{2}}\neq\mathbb{
I}_{\Phi_{\textup{obj}}(G_{\textup{LCQP}})\in\mathbb{R}}\big{]}<\epsilon.$
- (2)
If $\mathbb{P}[\Phi_{\textup{obj}}(G_{\textup{LCQP}})\in\mathbb{R}]=1$, then for any $\epsilon,\delta>0$, there exists $F_{2}\in\mathcal{F}_{\textup{LCQP}}$ such that
$\mathbb{P}\left[|F_{2}(G_{\textup{LCQP}})-\Phi_{\textup{obj}}(G_{\textup{LCQP}
})|>\delta\right]<\epsilon.$

Our last theorem for LCQP is that GNN can approximate the optimal solution map $\Phi_{\textup{sol}}$ that returns the optimal solution with the smallest $\ell_{2}$-norm of feasible and bounded LCQP problems.

###### Theorem 3.4 .

Let $\mathbb{P}$ be a probability measure on $\mathcal{G}^{m,n}_{\textup{LCQP}}$ satisfying Assumption 3.1 and assume that $\mathbb{P}[\Phi_{\textup{obj}}(G_{\textup{LCQP}})\in\mathbb{R}]=1$. For any $\epsilon,\delta>0$, there exists $F_{W}\in\mathcal{F}_{\textup{LCQP}}^{W}$ such that

$$ $\mathbb{P}\left[\|F_{W}(G_{\textup{LCQP}})-\Phi_{\textup{sol}}(G_{\textup{LCQP }})\|>\delta\right]<\epsilon.$ $$

The proofs of Theorem 3.3 and Theorem 3.4 will be presented in Appendix A. We briefly describe the main idea here. The Stone-Weierstrass theorem and its variants are a powerful tool for proving universal-approximation-type results. Recall that the classic version of the Stone-Weierstrass theorem states that under some assumptions, a function class $\mathcal{F}$ can uniformly approximate every continuous function if and only if it separates points, i.e., for any $x\neq x^{\prime}$, one has $F(x)\neq F(x^{\prime})$ for some $F\in\mathcal{F}$. Otherwise, we say $x$ and $x^{\prime}$ are indistinguishable by any $F\in\mathcal{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 $\ell_{2}$-norm) must be distinguished by some GNN in the class $\mathcal{F}_{\textup{LCQP}}$ (or $\mathcal{F}_{\textup{LCQP}}^{W}$). It is first established in [xu2019powerful] that the separation power(^2^22Given two sets of functions, $\mathcal{F}$ and $\mathcal{F}^{\prime}$, both defined over the same domain $X$, if $\mathcal{F}$ separating points $x$ and $x^{\prime}$ implies that $\mathcal{F}^{\prime}$ also separates $x$ and $x^{\prime}$ for any $x,x^{\prime}\in X$, then the separation power of $\mathcal{F}^{\prime}$ is considered to be stronger than or at least equal to that of $\mathcal{F}$.) of message-passing GNNs is equivalent to the Weisfeiler-Lehman (WL) test [weisfeiler1968reduction], a classical algorithm for the graph isomorphism problem, which is further developed in many recently works, see e.g. [azizian2020expressive, geerts2022expressiveness, chen2022representing-lp]. We show that, any two LCQP-graphs that are indistinguishable by the WL test, or equivalently by all message-passing GNNs, even if they are not isomorphic, some of their structures must be identical, which guarantees that they must have identical optimal objective value and identical optimal solution with the smallest $\ell_{2}$-norm.

###### Assumption 3.1 .

###### Theorem 3.2 ( [ chen2022representing-lp ] *Theorem 3.2) .

###### Theorem 3.3 .

###### Theorem 3.4 .

## 4. The capacity of GNNs for MI-LCQPs

In this section, we discuss the expressive power of GNNs for mixed-integer linearly constrained quadratic programs (MI-LCQPs), for which the general form is almost the same as (2.1) except that some entries of $x$ are constrained to be integers: $x_{j}\in\mathbb{Z},\ \forall~{}j\in I$, where $I\subset\{1,2,\dots,n\}$ collects the indices of all integer variables. Before proceeding, we extend LCQP-graphs and the corresponding GNNs and target mappings to the MI-LCQP setting.

MI-LCQP-graph is modified from the LCQP-graph (Section 2 and Figure 1) by adding a new entry to the feature of each variable node $j\in W$. The new feature is $w_{j}=(c_{j},l_{j},u_{j},\delta_{I}(j))$ where $\delta_{I}(j)=1$ if $j\in I$ and $\delta_{I}(j)=0$ otherwise. We use $\mathcal{G}_{\textup{MI-LCQP}}^{m,n}$ to denote the collection of all MI-LCQP-graphs with $m$ constraints, $n$ variables, and symmetric and positive semi-definite $Q$.

GNNs for MI-LCQP-graphs are constructed following the same mechanism as for LCQP-graphs, with the difference that the message-passing layer is modified as

- •
$s_{i}^{l}=f_{l}^{V}\big{(}s_{i}^{l-1},\sum_{j\in\mathcal{N}_{i}^{W}}g_{l}^{W}(
t_{j}^{l-1},A_{ij})\big{)}$ for $i\in V$, and
- •
$t_{j}^{l}=f_{l}^{W}\big{(}t_{j}^{l-1},\sum_{i\in\mathcal{N}_{j}^{V}}g_{l}^{V}(
s_{i}^{l-1},A_{ij}),\sum_{j^{\prime}\in\mathcal{N}_{j}^{W}}g_{l}^{Q}(t_{j^{
\prime}}^{l-1},Q_{jj^{\prime}})\big{)}$ for $j\in W$,

where $\mathcal{N}_{i}^{W}=\{j\in W:A_{ij}\neq 0\}$, $\mathcal{N}_{j}^{V}=\{j\in V:A_{ij}\neq 0\}$, and $\mathcal{N}_{j}^{W}=\{j^{\prime}\in W:Q_{jj^{\prime}}\neq 0\}$ are the sets of neighbors. We use $\mathcal{F}_{\textup{MI-LCQP}}$ and $\mathcal{F}_{\textup{MI-LCQP}}^{W}$ to denote the GNN classes for MI-LCQP-graphs with graph-level and node-level output, respectively.

Target mappings for MI-LCQPs considered in this section are also similar to those in Definition 2.3. In particular, the feasibility mapping $\Phi_{\textup{feas}}$ and the optimal objective value mapping $\Phi_{\textup{obj}}$ are defined in the same way as in Definition 2.3, while the optimal solution mapping $\Phi_{\textup{sol}}$ can only be defined on a subset of the class of feasible and bounded MI-LCQPs, which will be discussed in Section 4.2.

### 4.1. GNNs cannot universally represent MI-LCQPs

In this subsection, we present some counter-examples illustrating the fundamental limitation of GNNs for representing properties of MI-LCQPs. It is known in the previous literature that there exists some continuous function that cannot be approximated by GNNs with arbitrarily small error, see e.g., [xu2019powerful, azizian2020expressive, geerts2022expressiveness], and our results in Section 3 indicates that properties of LCQPs do not suffer from this fundamental limitation. However, when integer variables are introduced, GNN will fail to distinguish some pairs of MI-LCQP-graphs with different properties.
The first pair of counter-examples (feasible vs infeasible) is directly from [chen2022representing-milp] for MILPs which also allies for MI-LCQPs since adding a quadratic term in the objective function of an MILP problem does not change the feasible region.

###### Proposition 4.1 ( [ chen2022representing-milp ] *Lemma 3.2) .

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 $\mathcal{F}_{\textup{MI-CLQP}}$.

The next two propositions, not covered in [chen2022representing-milp], show that GNNs have limited separation power to distinguish two feasible MILP problems with different optimal objective values and two feasible MILP problems with the same optimal objective values and disjoint optimal solution sets.

###### Proposition 4.2 .

There exist two feasible MI-LCQP problems, with different optimal objective values, such that their graphs are indistinguishable by any GNN in $\mathcal{F}_{\textup{MI-CLQP}}$.

###### Proposition 4.3 .

There exist two feasible MI-LCQP problems with the same optimal objectives but disjoint optimal solution sets, such that their graphs are indistinguishable by any GNN in $\mathcal{F}_{\textup{MI-CLQP}}^{W}$.

Propositions 4.1, 4.2, and 4.3 indicate that there exist some MI-LCQP data distribution on which it is impossible to train a GNN to predict MI-LCQP properties, regardless of the size or the complexity of the GNN. In particular, one can just choose the uniform distribution over pairs of instances satisfying Propositions 4.1, 4.2, and 4.3, for which any GNN making good approximation on one instance must fail on the other.

We explicitly present a pair of MI-LCQP instances that prove Proposition 4.2 in Figure 2 while deferring the examples for Propositition 4.3 to Appendix B.

Figure: Figure 2. MI-LCQP instances proving Proposition 4.2

We can observe that the two MI-LCQP-graphs are not isomorphic, but all vertices of the same color have the same information from neighbors. For example, each red vertex $w_{j}$ has two blue neighbors with $A_{ij}=1$ and is connected to itself with a self-loop $Q_{jj}=1$. Therefore, even if they are not isomorphic, they lead to the same output for any GNN in $\mathcal{F}_{\textup{MI-LCQP}}$, for which we include a detailed proof in Appendix B. However, they have different properties. Particularly, they are both feasible but have different optimal objective values. More specifically, the optimal objective value of the first instance is $\frac{9}{2}$ that can be achieved at $(1,0,1,0,1,0)$. For the second instance, the constraints $x_{1}+x_{2}\geq 1$, $x_{2}+x_{3}\geq 1$, $x_{3}+x_{1}\geq 1$, and $x_{1},x_{2},x_{3}\in\{0,1\}$ imply that at least two of $x_{1},x_{2},x_{3}$ take the value of $1$. A similar analysis also applies to $x_{4},x_{5},x_{6}$, and hence, the optimal objective value of the second instance is $6\neq\frac{9}{2}$.

###### Proposition 4.1 ( [ chen2022representing-milp ] *Lemma 3.2) .

###### Proposition 4.2 .

###### Proposition 4.3 .

### 4.2. GNNs can represent particular types of MI-LCQPs

We have shown a fundamental limitation of GNNs to represent properties of general MI-LCQP problems. Therefore, a natural question is *whether we can identify a subset of $\mathcal{G}_{\textup{MI-LCQP}}$ on which it is possible to train reliable GNNs*. To address this, we need to gain a better understanding for the separation power of GNNs or equivalently the WL test, according to the discussion following Theorem 3.4. We state in Algorithm 1 the WL test for MI-LCQP-graphs associated to $\mathcal{F}_{\textup{MI-LCQP}}$ or $\mathcal{F}_{\textup{MI-LCQP}}^{W}$, where $C_{i}^{l,V}$ and $C_{j}^{l,W}$ are understood as the color of $i\in V$ and $j\in W$ at the $l$-th iteration.

Figure: Algorithm 1 The WL test for MI-LCQP-graphs

Initially, each vertex is labeled a color according to its attributes ($v_{i}$ or $w_{j}$). In the case that the hash functions introduce no collisions, two vertices are of the same color at the $l$-th iteration if and only if at the $(l-1)$-th iteration, they have the same color and the same information aggregation from neighbors in terms of multiset of colors and edge weights. This is a *color refinement* procedure.
One can have a partition of the vertex set $V\cup 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 a partition is strictly refined in the first $\mathcal{O}(m+n)$ iterations and will remain stable or unchanged afterward if no collision, see e.g. [chen2022representing-lp]*Appendix A. We provide an explicit example of the color refinement and the partition generated by WL test in Figure 6 of the Appendix.

Intuitively, vertices in the same class of the final stable partition generated by the WL test will always have identical features in message-passing layers for all GNNs in $\mathcal{F}_{\textup{MI-LCQP}}$ or $\mathcal{F}_{\textup{MI-LCQP}}^{W}$, and vice versa, since the color refinement procedure in Algorithm 1 follows the same mechanism as the message-passing process. Therefore, for identifying a subset of $\mathcal{F}_{\textup{MI-LCQP}}$ on which GNNs have sufficiently strong separation power, we propose the following definition, which basically states that vertices in the same class generated by the WL test can indeed be treated same in some sense.

###### Definition 4.4 (Message-passing-tractable MI-LCQP) .

In the same setting as in Definition 4.8, we say that $G_{\text{MI-LCQP}}$ is message-passing-tractable (MP-tractable) if the followings hold:

- (a)
For any $p\in\{1,2,\dots,s\}$ and $q\in\{1,2,\dots,t\}$, $A_{ij}$ is constant in $i\in I_{p},j\in J_{q}$.
- (b)
For any $q,q^{\prime}\in\{1,2,\dots,t\}$, $Q_{jj^{\prime}}$ is constant in $j\in J_{q},j^{\prime}\in J_{q^{\prime}}$.

We use $\mathcal{G}_{\textup{MP}}^{m,n}\subset\mathcal{G}_{\textup{MI-LCQP}}^{m,n}$ to denote the collection of all MP-tractable MI-LCQP-graphs with $m$ constraints and $n$ variables.

The analysis in [chen2022representing-lp]*Appendix A suggests that all rows/columns of the submatrix $(A_{ij})_{i\in I_{p},j\in J_{q}}$ (or $(Q_{jj^{\prime}})_{j\in J_{q},j^{\prime}\in J_{q^{\prime}}}$) are equal as multisets of entries, and the MP-traceability further requires that all elements in those multisets are the same.
Definition 4.4 is generalized from prior work on MILPs [chen2024rethinking] and with the assumption of MP-tractability, the universal approximation results can be established for GNNs to represent $\Phi_{\textup{feas}}$ and $\Phi_{\textup{obj}}$.

###### Assumption 4.5 .

$\mathbb{P}$ is a Borel regular probability measure on $\mathcal{G}^{m,n}_{\textup{MI-LCQP}}$ (^3^33The topology of $\mathcal{G}_{\textup{MI-LCQP}}^{m,n}$ is defined in the same way as $\mathcal{G}_{\textup{LCQP}}^{m,n}$.).

###### Theorem 4.6 .

Let $\mathbb{P}$ be a probability measure on $\mathcal{G}^{m,n}_{\textup{MI-LCQP}}$ satisfying Assumption 4.5 and $\mathbb{P}[G_{\textup{MI-LCQP}}\in\mathcal{G}_{\textup{MP}}^{m,n}]=1$. For any $\epsilon>0$, there exists $F\in\mathcal{F}_{\textup{MI-LCQP}}$ such that

$$ $\mathbb{P}\big{[}\mathbb{I}_{F(G_{\textup{MI-LCQP}})>\frac{1}{2}}\neq\Phi_{ \textup{feas}}(G_{\textup{MI-LCQP}})\big{]}<\epsilon.$ $$

###### Theorem 4.7 .

Let $\mathbb{P}$ be a probability measure on $\mathcal{G}^{m,n}_{\textup{MI-LCQP}}$ satisfying Assumption 4.5 and $\mathbb{P}[G_{\textup{MI-LCQP}}\in\mathcal{G}_{\textup{MP}}^{m,n}]=1$. The followings are true:

- (1)
For any $\epsilon>0$, there exists $F_{1}\in\mathcal{F}_{\textup{MI-LCQP}}$ such that
$\mathbb{P}\big{[}\mathbb{I}_{F_{1}(G_{\textup{MI-LCQP}})>\frac{1}{2}}\neq
\mathbb{I}_{\Phi_{\textup{obj}}(G_{\textup{MI-LCQP}})\in\mathbb{R}}\big{]}<\epsilon.$
- (2)
If $\mathbb{P}[\Phi_{\textup{obj}}(G_{\textup{MI-LCQP}})\in\mathbb{R}]=1$, then for any $\epsilon,\delta>0$, there exists $F_{2}\in\mathcal{F}_{\textup{MI-LCQP}}$ such that
$\mathbb{P}\left[|F_{2}(G_{\textup{MI-LCQP}})-\Phi_{\textup{obj}}(G_{\textup{MI
-LCQP}})|>\delta\right]<\epsilon.$

We then discuss the expressive power of GNNs to represent optimal solutions to MI-LCQP problems. Different from the LCQP setting, the optimal solution to an MI-LCQP problem may not exist even if it is feasible and bounded, i.e., $\Phi_{\textup{obj}}(G_{\textup{MI-LCQP}})\in\mathbb{R}$. Thus, we have to work with $\mathcal{G}_{\textup{sol}}^{m,n}\subset\Phi_{\textup{obj}}^{-1}(\mathbb{R})
\subset\mathcal{G}_{\textup{MI-LCQP}}^{m,n}$ where $\mathcal{G}_{\textup{sol}}^{m,n}$ is the collection of all MI-LCQP-graphs for which an optimal solution exists. For $G_{\textup{MI-LCQP}}\in\mathcal{G}_{\textup{sol}}^{m,n}$, it is possible that it admits multiple optimal solution. Moreover, there may even exist multiple optimal solutions with the smallest $\ell_{2}$-norm due to its non-convexity, which means that we cannot define the optimal solution mapping $\Phi_{\textup{sol}}$ using the same approach as in the LCQP case. To uniquely define $\Phi_{\textup{sol}}$, we need the following concept.

###### Definition 4.8 (Unfoldable MI-LCQP) .

Let $G_{\text{MI-LCQP}}\in\mathcal{G}_{\textup{MI-LCQP}}^{m,n}$ be a MI-LCQP problem and let $(\mathcal{I},\mathcal{J})$ be the final stable partition of $V\cup W$ generated by WL test without collision, where $\mathcal{I}=\{I_{1},I_{2},\dots,I_{s}\}$ is a partition of $V=\{1,2,\dots,m\}$ and $\mathcal{J}=\{J_{1},J_{2},\dots,J_{t}\}$ is a partition of $W=\{1,2,\dots,n\}$. We say that $G_{\text{MI-LCQP}}$ is unfoldable if $t=n$ and $|J_{1}|=|J_{2}|=\cdots=|J_{n}|=1$, i.e., all vertices in $W$ have different colors. We use $\mathcal{G}_{\textup{unfold}}^{m,n}\subset\mathcal{G}_{\textup{MI-LCQP}}^{m,n}$ to denote the collection of all unfoldable MI-LCQP-graphs with $m$ constraints and $n$ variables.

The MI-LCQP unfoldability is a generalization of the MILP unfoldability proposed in [chen2022representing-milp]. If we assume that $G_{\textup{MI-LCQP}}\in\mathcal{G}_{\textup{sol}}^{m,n}$ is unfoldable, then using the same approach as in [chen2022representing-milp]*Appendix C, one can define a total ordering on the optimal solution set and hence define $\Phi_{\textup{sol}}(G_{\textup{MI-LCQP}})$ as the minimal element in the optimal solution set, which is unique and permutation-equivariant, meaning that if one relabels vertices of $G_{\textup{MI-LCQP}}$, then entries of $\Phi_{\textup{sol}}(G_{\textup{MI-LCQP}})$ are relabelled accordingly. It can be proved that the unfoldability implies the MP-tractability but there exist MP-tractable instances that are not unfoldable (see Appendix C).

With the assumption that the MI-LCQP data distribution is supported in $\mathcal{G}_{\textup{sol}}^{m,n}\cap\mathcal{G}_{\textup{unfold}}^{m,n}$, a positive result for GNNs to represent the optimal solution mapping can be derived.

###### Theorem 4.9 .

Let $\mathbb{P}$ be a probability measure on $\mathcal{G}^{m,n}_{\textup{MI-LCQP}}$ satisfying Assumption 4.5 and $\mathbb{P}[G_{\textup{MI-LCQP}}\in\mathcal{G}_{\textup{sol}}^{m,n}\cap\mathcal
{G}_{\textup{unfold}}^{m,n}]=1$. For any $\epsilon,\delta>0$, there exists $F_{W}\in\mathcal{F}_{\textup{MI-LCQP}}^{W}$ such that

$$ $\mathbb{P}\left[\|F_{W}(G_{\textup{MI-LCQP}})-\Phi_{\textup{sol}}(G_{\textup{ MI-LCQP}})\|>\delta\right]<\epsilon.$ $$

The proofs for Theorems 4.6, 4.7, and 4.9 can be found in Appendix D. As the concluding remarks for this section, we would like to mention that although there exist MI-LCQP problems that are not MP-tractable/unfoldable, the MP-tractable/unfoldable MI-LCQP class is already rich enough to cover many applications. In particular, it can be proved MI-LCQP-graphs are generically MP-tractable/unfoldable (see Section C for details).

###### Definition 4.4 (Message-passing-tractable MI-LCQP) .

###### Assumption 4.5 .

###### Theorem 4.6 .

###### Theorem 4.7 .

###### Definition 4.8 (Unfoldable MI-LCQP) .

###### Theorem 4.9 .

## 5. Numerical experiments

#### A study on the expressive power

We train GNNs to fit $\Phi_{\textup{obj}}$ or $\Phi_{\textup{sol}}$ for LCQP or MI-LCQP instances.(^4^44Since LCQP and MI-LCQP are linearly constrained, predicting feasibility falls to the case of LP and MILP, which has been numerically investigated in [chen2022representing-lp] and [chen2022representing-milp]. Hence we omit the feasibility experiments here.) For both LCQP and MI-LCQP, we randomly generate 100 instances, each of which contains 10 constraints and 50 variables. The generated MI-LCQPs are all unfoldable and MP-tractable with probability one. The optimal solutions and corresponding objective function values are collected using existing solvers. Details on the data generation and training schemes can be found in Appendix E.
We train four GNNs with four different embedding sizes and record their relative errors averaged on all instances during training.(^5^55The relative error of a GNN $F_{W}$ on a single problem instance $G$ is defined as $\|F_{W}(G)-\Phi(G)\|_{2}/\max(\|\Phi(G)\|_{2},1)$, where $\Phi$ could be either $\Phi_{\textup{obj}}$ or $\Phi_{\textup{sol}}$.) The results are reported in Figure 3.
We can see that GNNs can fit $\Phi_{\textup{obj}}$ and $\Phi_{\textup{sol}}$ well for both LCQP and MI-LCQP.
These results validate Theorems 3.3,3.4,4.7 and 4.9 on a small set of instances. We also observe that a larger embedding size increases the capacity of a GNN, resulting in not only lower final errors but also faster convergence.

Figure: (a) Fit $\Phi_{\textup{obj}}$ for LCQP
Refer to caption: x1.png

To further validate the theorems on a larger scale, we expand the number of problem instances to 500 and 2,500, and conduct training on the four GNNs along with a larger variant with an embedding size of 1,024. The results are reported in Figure 4. We can observe that GNN can achieve near-zero fitting errors as long as it has a large enough embedding size and thus enough capacity for approximation.

Figure: (a) Fit $\Phi_{\textup{obj}}$ for LCQP
Refer to caption: x5.png

#### A study on the generalization ability

Besides investigating GNNs’ approximation capacity, we also explore their generalization ability. However, the instances used in previous experiments are generic. Here, we generate new LCQP instances by varying only $c$, while keeping other components fixed. Training GNNs with an embedding size of 512 on these instances and testing them on a separate validation set, we observe in Figure 5 that as the number of training instances increases, the generalization gap decreases and validation error improves. With 25,000 training instances, we achieve a satisfactory validation error below $10^{-2}$ for $\Phi_{\mathrm{obj}}$. Results of fitting $\Phi_{\mathrm{sol}}$ can be found in Appendix E.

Figure: Figure 5. Train and validation errors when fitting $\Phi_{\mathrm{obj}}$ for LCQP.
Refer to caption: x9.png

## 6. Conclusion

This paper establishes theoretical foundations for using GNNs to represent the feasibility, optimal objective value, and optimal solution, of LCQPs and MI-LCQPs. In particular, we prove the existence of GNNs that can predict those properties of LCQPs universally well and show with explicit examples that such results are generally not true for MI-LCQPs when integer constraints are introduced. Moreover, we precisely identify subclasses of MI-LCQP problems on which such universal approximation results are still valid. Our findings are also verified numerically.

Let us also comment on the limitations and future directions. Firstly, our universal approximation theorems only show the existence of the GNNs, without discussing the complexity, training, and generalization, which are all important future directions. Secondly, the research conducted in this paper is mainly theoretical and does not cover large-scale experiments. It would be interesting to explore the probability of building machine-learning-based general solvers for large-scale QPs.

## Appendix A Proofs for Section 3

In this appendix, we present the proofs for theorems in Section 3. The proofs will based on Weisfeiler-Lehman (WL) test and its separation power to distinguish LCQP problems with different properties.

The Weisfeiler-Lehman (WL) test [weisfeiler1968reduction] is a classical algorithm for the graph isomorphism problem. In particular, it implements color refinement on vertices by applying a 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 is worth noting that WL test may incorrectly identify two non-isomorphic graphs as isomorphic. We slightly modify the standard WL test to fit the structure of LCQP-graphs, see Algorithm 2.

Figure: Algorithm 2 The WL test for LCQP-graphs

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 LCQP-graphs $G_{\textup{LCQP}},\hat{G}_{\textup{LCQP}}\in\mathcal{G}_{\textup{LCQP}}^{m,n}$, let $\{\{C_{i}^{L,V}\}\}_{i=0}^{m},\{\{C_{j}^{L,W}\}\}_{j=0}^{n}$ and $\{\{\hat{C}_{i}^{L,V}\}\}_{i=0}^{m},\{\{\hat{C}_{j}^{L,W}\}\}_{j=0}^{n}$ the color multisets output by Algorithm 2 on $G_{\textup{LCQP}}$ and $\hat{G}_{\textup{LCQP}}$.

- (a)
We say $G_{\textup{LCQP}}\sim\hat{G}_{\textup{LCQP}}$ if for all $L\in\mathbb{N}$ and all hash functions, $\{\{C_{i}^{L,V}\}\}_{i=0}^{m}=\{\{\hat{C}_{i}^{L,V}\}\}_{i=0}^{m}$ and $\{\{C_{j}^{L,W}\}\}_{j=0}^{n}=\{\{\hat{C}_{j}^{L,W}\}\}_{j=0}^{n}$.
- (b)
We say $G_{\textup{LCQP}}\stackrel{{\scriptstyle W}}{{\sim}}\hat{G}_{\textup{LCQP}}$ if for all $L\in\mathbb{N}$ and all hash functions, $\{\{C_{i}^{L,V}\}\}_{i=0}^{m}=\{\{\hat{C}_{i}^{L,V}\}\}_{i=0}^{m}$ and $C_{j}^{L,W}=\hat{C}_{j}^{L,W},\ \forall~{}j\in\{1,2,\dots,n\}$.

Our main finding leading to the results in Section 3 is that, for LCQP-graphs in the same equivalence class, even if they are non-isomorphic, their optimal objective values and optimal solutions must be the same (up to a permutation perhaps).

###### Theorem A.2 .

For any $G_{\textup{LCQP}},\hat{G}_{\textup{LCQP}}\in\mathcal{G}_{\textup{LCQP}}^{m,n}$, if $G_{\textup{LCQP}}\sim\hat{G}_{\textup{LCQP}}$, then $\Phi_{\textup{obj}}(G_{\textup{LCQP}})=\Phi_{\textup{obj}}(\hat{G}_{\textup{
LCQP}})$.

###### Theorem A.3 .

For any $G_{\textup{LCQP}},\hat{G}_{\textup{LCQP}}\in\mathcal{G}_{\textup{LCQP}}^{m,n}$ that are feasible and bounded, if $G_{\textup{LCQP}}\sim\hat{G}_{\textup{LCQP}}$, then there exists some permutation $\sigma_{W}\in S_{n}$ such that $\Phi_{\textup{sol}}(G_{\textup{LCQP}})=\sigma_{W}(\Phi_{\textup{sol}}(\hat{G}_
{\textup{LCQP}}))$. Furthermore, if $G_{\textup{LCQP}}\stackrel{{\scriptstyle W}}{{\sim}}\hat{G}_{\textup{LCQP}}$, then $\Phi_{\textup{sol}}(G_{\textup{LCQP}})=\Phi_{\textup{sol}}(\hat{G}_{\textup{
LCQP}})$.

We need the following lemma to prove Theorem A.2 and Theorem A.3.

###### Lemma A.4 .

Suppose that $M\in\mathbb{R}^{n\times n}$ is a symmetric and positive semidefinite matrix and that $\mathcal{J}=\{J_{1},J_{2},\dots,J_{t}\}$ is a partition of $\{1,2,\dots,n\}$ satisfying that for any $q,q^{\prime}\in\{1,2,\dots,t\}$, $\sum_{j^{\prime}\in J_{q^{\prime}}}M_{jj^{\prime}}$ is a constant over $j\in J_{q}$. For any $x\in\mathbb{R}^{n}$, it holds that

$$ (A.1) $\frac{1}{2}x^{\top}Mx\geq\frac{1}{2}\hat{x}^{\top}M\hat{x},$ $$

where $\hat{x}\in\mathbb{R}^{n}$ is defined via $\hat{x}_{j}=y_{q}=\frac{1}{|J_{q}|}\sum_{j^{\prime}\in J_{q}}x_{j^{\prime}}$ for $j\in J_{q}$.

###### Proof.

Fixe $x\in\mathbb{R}^{n}$ and consider the problem

$$ (A.2) $\min_{z\in\mathbb{R}^{n}}~{}~{}\frac{1}{2}z^{\top}Mz,\quad\textup{s.t.}~{}~{} \sum_{j\in J_{q}}z_{j}=\sum_{j\in J_{q}}x_{j},\ q=1,2,\dots,t,$ $$

which is a convex program. The Lagrangian is given by

$$ $\mathcal{L}(z,\lambda)=\frac{1}{2}z^{\top}Mz-\sum_{q=1}^{t}\lambda_{q}\left( \sum_{j\in J_{q}}z_{j}-\sum_{j\in J_{q}}x_{j}\right).$ $$

It can be computed that

$$ $\frac{\partial}{\partial z_{j}}\mathcal{L}(z,\lambda)=\sum_{j^{\prime}=1}^{n}M _{jj^{\prime}}z_{j^{\prime}}-\lambda_{q},\quad j\in J_{q},$ $$

and

$$ $\frac{\partial}{\partial\lambda_{q}}\mathcal{L}(z,\lambda)=\sum_{j\in J_{q}}x_ {j}-\sum_{j\in J_{q}}z_{j},$ $$

It is clear that

$$ $\frac{\partial}{\partial\lambda_{q}}\mathcal{L}(\hat{x},\lambda)=\sum_{j\in J_ {q}}x_{j}-\sum_{j\in J_{q}}\hat{x}_{j}=0,$ $$

by the definition of $\hat{x}$. Furthermore, consider any fixed $q\in\{1,2,\dots,t\}$ and we have for any $j\in J_{q}$ that

$$ $\frac{\partial}{\partial z_{j}}\mathcal{L}(\hat{x},\lambda)=\sum_{q^{\prime}=1 }^{t}y_{q^{\prime}}\sum_{j^{\prime}\in J_{q^{\prime}}}M_{jj^{\prime}}-\lambda_ {q}=0,$ $$

if $\lambda_{q}=\sum_{q^{\prime}=1}^{t}y_{q^{\prime}}\sum_{j^{\prime}\in J_{q^{
\prime}}}M_{jj^{\prime}}$ that is independent in $j\in q$ since $\sum_{j^{\prime}\in J_{q^{\prime}}}M_{jj^{\prime}}$ is constant over $j\in J_{q}$ for any $q^{\prime}\in\{1,2,\dots,t\}$. Since the problem (A.2) is convex and the first-order optimality condition is satisfied at $\hat{x}$, we can conclude that $\hat{x}$ is a minimizer of (A.2), which implies (A.1).
∎

###### Proof of Theorem A.2 .

Let $G_{\textup{LCQP}}$ and $\hat{G}_{\textup{LCQP}}$ be the LCQP-graphs associated to (2.1) and

$$ (A.3) $\min_{x\in\mathbb{R}^{n}}~{}~{}\frac{1}{2}x^{\top}\hat{Q}x+\hat{c}^{\top}x, \quad\textup{s.t.}~{}~{}\hat{A}x\ \hat{\circ}\ \hat{b},\ \hat{l}\leq x\leq\hat {u},$ $$

Suppose that there are no collisions of hash functions or their linear combinations when applying the WL test to $G_{\textup{LCQP}}$ and $\hat{G}_{\textup{LCQP}}$ and there are no strict color refinements in the $L$-th iteration.
Since $G_{\textup{LCQP}}\sim\hat{G}_{\textup{LCQP}}$, after performing some permutation, there exist $\mathcal{I}=\{I_{1},I_{2},\dots,I_{s}\}$ and $\mathcal{J}=\{J_{1},J_{2},\dots,J_{t}\}$ that are partitions of $\{1,2,\dots,m\}$ and $\{1,2,\dots,n\}$, respectively, such that the followings hold:

- •
$C_{i}^{L,V}=C_{i^{\prime}}^{L,V}$ if and only if $i,i^{\prime}\in I_{p}$ for some $p\in\{1,2,\dots,s\}$.
- •
$C_{i}^{L,V}=\hat{C}_{i^{\prime}}^{L,V}$ if and only if $i,i^{\prime}\in I_{p}$ for some $p\in\{1,2,\dots,s\}$.
- •
$\hat{C}_{i}^{L,V}=\hat{C}_{i^{\prime}}^{L,V}$ if and only if $i,i^{\prime}\in I_{p}$ for some $p\in\{1,2,\dots,s\}$.
- •
$C_{j}^{L,W}=C_{j^{\prime}}^{L,W}$ if and only if $j,j^{\prime}\in J_{q}$ for some $q\in\{1,2,\dots,t\}$.
- •
$C_{j}^{L,W}=\hat{C}_{j^{\prime}}^{L,W}$ if and only if $j,j^{\prime}\in J_{q}$ for some $q\in\{1,2,\dots,t\}$.
- •
$\hat{C}_{j}^{L,W}=\hat{C}_{j^{\prime}}^{L,W}$ if and only if $j,j^{\prime}\in J_{q}$ for some $q\in\{1,2,\dots,t\}$.

Since there are no collisions, we have from the vertex color initialization that

- •
$v_{i}=(b_{i},\circ_{i})=\hat{v}_{i}=(\hat{b}_{i},\hat{\circ}_{i})$ and is constant over $i\in I_{p}$ for any $p\in\{1,2,\dots,s\}$.
- •
$w_{j}=(c_{j},l_{j},u_{j})=\hat{w}_{j}=(\hat{c}_{j},\hat{l}_{j},\hat{u}_{j})$ and is constant over $j\in J_{q}$ for any $q\in\{1,2,\dots,t\}$.

For any $p\in\{1,2,\dots,s\}$ and any $i,i^{\prime}\in I_{p}$, one has

$$ $\displaystyle C_{i}^{L,V}=C_{i^{\prime}}^{L,V}$ $\displaystyle\implies\sum_{j\in W}A_{ij}\text{HASH}\left(C_{j}^{L-1,W}\right)= \sum_{j\in W}A_{i^{\prime}j}\text{HASH}\left(C_{j}^{L-1,W}\right)$ $\displaystyle\implies\sum_{j\in W}A_{ij}\text{HASH}\left(C_{j}^{L,W}\right)= \sum_{j\in W}A_{i^{\prime}j}\text{HASH}\left(C_{j}^{L,W}\right)$ $\displaystyle\implies\sum_{j\in J_{q}}A_{ij}=\sum_{j\in J_{q}}A_{i^{\prime}j}, \quad\forall~{}q\in\{1,2,\dots,t\}.$ $$

One can obtain similar conclusions from $C_{i}^{L,V}=\hat{C}_{i^{\prime}}^{L,V}$ and $\hat{C}_{i}^{L,V}=\hat{C}_{i^{\prime}}^{L,V}$, and hence conclude that

- •
For any $p\in\{1,2,\dots,s\}$ and $q\in\{1,2,\dots,t\}$, $\sum_{j\in J_{q}}A_{ij}=\sum_{j\in J_{q}}\hat{A}_{ij}$ and is constant over $i\in I_{p}$.

Similarly, the followings also hold:

- •
For any $p\in\{1,2,\dots,s\}$ and $q\in\{1,2,\dots,t\}$, $\sum_{i\in I_{p}}A_{ij}=\sum_{i\in I_{p}}\hat{A}_{ij}$ and is constant over $j\in J_{q}$.
- •
For any $q,q^{\prime}\in\{1,2,\dots,t\}$, $\sum_{j^{\prime}\in J_{q^{\prime}}}Q_{jj^{\prime}}=\sum_{j^{\prime}\in J_{q^{
\prime}}}\hat{Q}_{jj^{\prime}}$ and is constant over $j\in J_{q}$.

If $G_{\textup{LCQP}}$ or (2.1) is infeasible, then $\Phi_{\textup{obj}}(G_{\textup{LCQP}})=+\infty$ and clearly $\Phi_{\textup{obj}}(G_{\textup{LCQP}})\geq\Phi_{\textup{obj}}(\hat{G}_{\textup
{LCQP}})$. If (2.1) is feasible, let $x\in\mathbb{R}^{n}$ be any feasible solution to (2.1) and define $\hat{x}\in\mathbb{R}^{n}$ via $\hat{x}_{j}=y_{q}=\frac{1}{|J_{q}|}\sum_{j^{\prime}\in J_{q}}x_{j^{\prime}}$ for $j\in J_{q}$. By the proofs of Lemma B.2 and Lemma B.3 in [chen2022representing-lp], we know that $\hat{x}$ is a feasible solution to (A.3) and $c^{\top}x=\hat{c}^{\top}\hat{x}$. In addition, we have

$$ $\displaystyle\frac{1}{2}x^{\top}Qx$ $\displaystyle\overset{\eqref{eq:xMx_hatxMhatx}}{\geq}\frac{1}{2}\hat{x}^{\top} Q\hat{x}=\frac{1}{2}\sum_{q,q^{\prime}=1}^{t}\sum_{j\in J_{q}}\sum_{j^{\prime} \in J_{q^{\prime}}}\hat{x}_{j}Q_{jj^{\prime}}\hat{x}_{j^{\prime}}=\frac{1}{2} \sum_{q,q^{\prime}=1}^{t}y_{q}y_{q^{\prime}}\sum_{j^{\prime}\in J_{q^{\prime}} }Q_{jj^{\prime}}$ $\displaystyle=\frac{1}{2}\sum_{q,q^{\prime}=1}^{t}y_{q}y_{q^{\prime}}\sum_{j^{ \prime}\in J_{q^{\prime}}}\hat{Q}_{jj^{\prime}}=\frac{1}{2}\sum_{q,q^{\prime}= 1}^{t}\sum_{j\in J_{q}}\sum_{j^{\prime}\in J_{q^{\prime}}}\hat{x}_{j}\hat{Q}_{ jj^{\prime}}\hat{x}_{j^{\prime}}=\frac{1}{2}\hat{x}^{\top}\hat{Q}\hat{x},$ $$

which then implies that

$$ $\frac{1}{2}x^{\top}Qx+c^{\top}x\geq\frac{1}{2}\hat{x}^{\top}\hat{Q}\hat{x}+ \hat{c}^{\top}\hat{x},$ $$

and hence that $\Phi_{\textup{obj}}(G_{\textup{LCQP}})\geq\Phi_{\textup{obj}}(\hat{G}_{\textup
{LCQP}})$. Till now we have proved $\Phi_{\textup{obj}}(G_{\textup{LCQP}})\geq\Phi_{\textup{obj}}(\hat{G}_{\textup
{LCQP}})$ regardless of the feasibility of $G_{\textup{LCQP}}$. The reverse direction $\Phi_{\textup{obj}}(G_{\textup{LCQP}})\leq\Phi_{\textup{obj}}(\hat{G}_{\textup
{LCQP}})$ is also true and we can conclude that $\Phi_{\textup{obj}}(G_{\textup{LCQP}})=\Phi_{\textup{obj}}(\hat{G}_{\textup{
LCQP}})$.
∎

###### Proof of Theorem A.3 .

Under the same setting as in the proof of Theorem A.2, the results can be proved using the same arguments as in the proof of Lemma B.4 and Corollary B.7 in [chen2022representing-lp].
∎

###### Corollary A.5 .

For any feasible and bounded $G_{\textup{LCQP}}\in\mathcal{G}_{\textup{LCQP}}^{m,n}$ and any $j,j^{\prime}\in\{1,2,\dots,n\}$, if $C_{j}^{L,W}=C_{j^{\prime}}^{L,W}$ holds for all $L\in\mathbb{N}_{+}$ and all hash functions, then $\Phi_{\textup{sol}}(G_{\textup{LCQP}})_{j}=\Phi_{\textup{sol}}(G_{\textup{LCQP
}})_{j^{\prime}}$.

###### Proof.

Let $\hat{G}_{\textup{LCQP}}$ be the LCQP-graph obtained from $G_{\textup{LCQP}}$ by relabeling $j$ as $j^{\prime}$ and relabeling $j^{\prime}$ as $j$. By Theorem A.3, we have $\Phi_{\textup{sol}}(G_{\textup{LCQP}})=\Phi_{\textup{sol}}(\hat{G}_{\textup{
LCQP}})$, which implies $\Phi_{\textup{sol}}(G_{\textup{LCQP}})_{j}=\Phi_{\textup{sol}}(\hat{G}_{
\textup{LCQP}})_{j}=\Phi_{\textup{sol}}(G_{\textup{LCQP}})_{j^{\prime}}$.
∎

It is well-known from previous literature that the separation power of GNNs is 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. [chen2022representing-lp, xu2019powerful, azizian2020expressive, geerts2022expressiveness]. We have established in Theorem A.2, Theorem A.3, and Corollary A.5 that the separation power of $\Phi_{\textup{obj}}$ and $\Phi_{\textup{sol}}$ is upper bounded by the WL test (Algorithm 2) that shares the same information aggregation mechanism as the GNNs in $\mathcal{F}_{\textup{LCQP}}$ and $\mathcal{F}_{\textup{LCQP}}^{W}$. Therefore, Theorem 3.3 and Theorem 3.4 can be proved using standard arguments in the previous literature.

###### Proof of Theorem 3.3 .

Based on Theorem A.2, Theorem 3.3 can be proved following the same lines as in the proof of Theorem 3.4 in [chen2022representing-lp], with trivial modifications to generalize results for LP-graphs to the LCQP setting.
∎

###### Proof of Theorem 3.4 .

Based on Theorem A.3 and Corollary A.5, Theorem 3.4 can be proved following the same lines as in the proof of Theorem 3.6 in [chen2022representing-lp], with trivial modifications to generalize results for LP-graphs to the LCQP setting.
∎

###### Definition A.1 .

###### Theorem A.2 .

###### Theorem A.3 .

###### Lemma A.4 .

###### Proof.

###### Proof of Theorem A.2 .

###### Proof of Theorem A.3 .

###### Corollary A.5 .

###### Proof.

###### Proof of Theorem 3.3 .

###### Proof of Theorem 3.4 .

## Appendix B Proofs for Section 4.1

This section presents the proofs of Proposition 4.2 and Proposition 4.3.

###### Proof of Proposisition 4.2 .

As discussed in Section 4.1, we consider the following two examples whose optimal objective values are $\frac{9}{2}$ and $6$, respectively.
$\begin{split}\min_{x\in\mathbb{R}^{6}}&~{}~{}\frac{1}{2}\sum_{i=1}^{6}x_{i}^{2
}+\sum_{i=1}^{6}x_{i},\\
\text{s.t.}&~{}~{}x_{1}+x_{2}\geq 1,\ x_{2}+x_{3}\geq 1,\ x_{3}+x_{4}\geq 1,\\
&~{}~{}x_{4}+x_{5}\geq 1,\ x_{5}+x_{6}\geq 1,\ x_{6}+x_{1}\geq 1,\\
&~{}~{}x_{j}\in\{0,1\},\ \forall~{}j\in\{1,2,\dots,6\}.\end{split}$
$\begin{split}\min_{x\in\mathbb{R}^{6}}&~{}~{}\frac{1}{2}\sum_{i=1}^{6}x_{i}^{2
}+\sum_{i=1}^{6}x_{i},\\
\text{s.t.}&~{}~{}x_{1}+x_{2}\geq 1,\ x_{2}+x_{3}\geq 1,\ x_{3}+x_{1}\geq 1,\\
&~{}~{}x_{4}+x_{5}\geq 1,\ x_{5}+x_{6}\geq 1,\ x_{6}+x_{4}\geq 1,\\
&~{}~{}x_{j}\in\{0,1\},\ \forall~{}j\in\{1,2,\dots,6\}.\\
~{}\end{split}$
$\min~{}\frac{1}{2}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}
\definecolor[named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}&{\color[
rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}&{\color[rgb]{0.1953125,0.78515625,0.1953125}
\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}
\end{bmatrix}\begin{bmatrix}1&0.1&\\
0.1&1&\\
&&1\end{bmatrix}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}\definecolor
[named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}\\
{\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}\\
{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor
}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}\end{bmatrix}+\begin{bmatrix}1&2&3
\end{bmatrix}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}\definecolor[
named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}\\
{\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}\\
{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor
}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}\end{bmatrix}$ %Reduce the space between columns s.t.
$2{\color[rgb]{0.203125,0.59765625,1}\definecolor[named]{pgfstrokecolor}{rgb}{
0.203125,0.59765625,1}x_{1}}$
$+$
${\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}$
$\leq 5$
${\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}$
$+$
$3{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{
pgfstrokecolor}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}$
$\geq 0$
$0\leq{\color[rgb]{0.203125,0.59765625,1}\definecolor[named]{pgfstrokecolor}{
rgb}{0.203125,0.59765625,1}x_{1}},{\color[rgb]{1,0.296875,0.234375}
\definecolor[named]{pgfstrokecolor}{rgb}{1,0.296875,0.234375}x_{2}},{\color[
rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{
0.1953125,0.78515625,0.1953125}x_{3}}\leq 1$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$
$\min~{}\frac{1}{2}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}
\definecolor[named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}&{\color[
rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}&{\color[rgb]{0.1953125,0.78515625,0.1953125}
\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}
\end{bmatrix}\begin{bmatrix}1&0.1&\\
0.1&1&\\
&&1\end{bmatrix}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}\definecolor
[named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}\\
{\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}\\
{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor
}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}\end{bmatrix}+\begin{bmatrix}1&2&3
\end{bmatrix}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}\definecolor[
named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}\\
{\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}\\
{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor
}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}\end{bmatrix}$ %Reduce the space between columns s.t.
$2{\color[rgb]{0.203125,0.59765625,1}\definecolor[named]{pgfstrokecolor}{rgb}{
0.203125,0.59765625,1}x_{1}}$
$+$
${\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}$
$\leq 5$
${\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}$
$+$
$3{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{
pgfstrokecolor}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}$
$\geq 0$
$0\leq{\color[rgb]{0.203125,0.59765625,1}\definecolor[named]{pgfstrokecolor}{
rgb}{0.203125,0.59765625,1}x_{1}},{\color[rgb]{1,0.296875,0.234375}
\definecolor[named]{pgfstrokecolor}{rgb}{1,0.296875,0.234375}x_{2}},{\color[
rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{
0.1953125,0.78515625,0.1953125}x_{3}}\leq 1$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$
Denote $G_{\textup{MI-LCQP}}$ and $\hat{G}_{\textup{MI-LCQP}}$ as the graph representations of the above two MI-LCQP problems.
Let $s_{i}^{l},t_{j}^{l}$ and $\hat{s}_{i}^{l},\hat{t}_{j}^{l}$ be the features at the $l$-th layer when apply a GNN $F\in\mathcal{F}_{\textup{MI-LCQP}}$ to $G_{\textup{MI-LCQP}}$ and $\hat{G}_{\textup{MI-LCQP}}$. We will prove by induction that for any $0\leq l\leq L$, the followings hold:

- (a)
$s_{i}^{l}=\hat{s}_{i}^{l}$ and is constant over $i\in\{1,2,\dots,6\}$.
- (b)
$t_{j}^{l}=\hat{t}_{j}^{l}$ and is constant over $j\in\{1,2,\dots,6\}$.

It is clear that the conditions (a) and (b) are true for $l=0$, since $v_{i}=\hat{v}_{i}$ is constant in $i\in\{1,2,\dots,6\}$, and $w_{j}=\hat{w}_{j}$ is constant in $j\in\{1,2,\dots,6\}$. Now suppose that the conditions (a) and (b) are true for $l-1$ where $1\leq l\leq L$. We denote that $s^{l-1}=s_{i}^{l-1}=\bar{s}_{i}^{l-1},\ \forall~{}i\in\{1,2,\dots,6\}$ and $t^{l-1}=t_{j}^{l-1}=\hat{t}_{j}^{l-1},\ \forall~{}j\in\{1,2,\dots,6\}$. It can be computed for any $i\in\{1,2,\dots,6\}$ and $j\in\{1,2,\dots,6\}$ that

$$ $\displaystyle s_{i}^{l}$ $\displaystyle=f_{l}^{V}\left(s_{i}^{l-1},\sum_{j\in\mathcal{N}_{i}^{W}}g_{l}^{ W}(t_{j}^{l-1},A_{ij})\right)=f_{l}^{V}\left(s^{l-1},2g_{l}^{W}(t^{l-1},1) \right)=\hat{s}_{i}^{l},$ $\displaystyle t_{j}^{l}$ $\displaystyle=f_{l}^{W}\left(t_{j}^{l-1},\sum_{i\in\mathcal{N}_{j}^{V}}g_{l}^{ V}(s_{i}^{l-1},A_{ij}),\sum_{j^{\prime}\in\mathcal{N}_{j}^{W}}g_{l}^{Q}(t_{j^{ \prime}}^{l-1},Q_{jj^{\prime}})\right)$ $\displaystyle=f_{l}^{W}\left(t^{l-1},2g_{l}^{V}(s^{l-1},1),g_{l}^{Q}(t^{l-1},1 )\right)=\hat{t}_{j}^{l},$ $$

which proves (a) and (b) for $l$. Thus, we can conclude that $F(G_{\textup{MI-LCQP}})=F(\hat{G}_{\textup{MI-LCQP}}),\ \forall~{}F\in\mathcal
{F}_{\textup{MI-LCQP}}$.
∎

###### Proof of Proposition 4.3 .

Consider the following two MI-LCQPs:
$\begin{split}\min_{x\in\mathbb{R}^{7}}&~{}~{}\frac{1}{2}x^{\top}\mathbf{1}
\mathbf{1}^{\top}x+\mathbf{1}^{\top}x,\\
\text{s.t.}&~{}~{}x_{1}-x_{2}=0,\ x_{2}-x_{1}=0,\\
&~{}~{}x_{3}-x_{4}=0,\ x_{4}-x_{5}=0,\\
&~{}~{}x_{5}-x_{6}=0,\ x_{6}-x_{7}=0,\ x_{7}-x_{3}=0,\\
&~{}~{}x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}=6\\
&~{}~{}0\leq x_{j}\leq 3,\ x_{j}\in\mathbb{Z},\ \forall~{}j\in\{1,2,\dots,7\}.
\end{split}$
$\min~{}\frac{1}{2}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}
\definecolor[named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}&{\color[
rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}&{\color[rgb]{0.1953125,0.78515625,0.1953125}
\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}
\end{bmatrix}\begin{bmatrix}1&0.1&\\
0.1&1&\\
&&1\end{bmatrix}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}\definecolor
[named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}\\
{\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}\\
{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor
}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}\end{bmatrix}+\begin{bmatrix}1&2&3
\end{bmatrix}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}\definecolor[
named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}\\
{\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}\\
{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor
}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}\end{bmatrix}$ %Reduce the space between columns s.t.
$2{\color[rgb]{0.203125,0.59765625,1}\definecolor[named]{pgfstrokecolor}{rgb}{
0.203125,0.59765625,1}x_{1}}$
$+$
${\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}$
$\leq 5$
${\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}$
$+$
$3{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{
pgfstrokecolor}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}$
$\geq 0$
$0\leq{\color[rgb]{0.203125,0.59765625,1}\definecolor[named]{pgfstrokecolor}{
rgb}{0.203125,0.59765625,1}x_{1}},{\color[rgb]{1,0.296875,0.234375}
\definecolor[named]{pgfstrokecolor}{rgb}{1,0.296875,0.234375}x_{2}},{\color[
rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{
0.1953125,0.78515625,0.1953125}x_{3}}\leq 1$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$$w_{7}$
and
$\begin{split}\min_{x\in\mathbb{R}^{7}}&~{}~{}\frac{1}{2}x^{\top}\mathbf{1}
\mathbf{1}^{\top}x+\mathbf{1}^{\top}x,\\
\text{s.t.}&~{}~{}x_{1}-x_{2}=0,\ x_{2}-x_{3}=0,\ x_{3}-x_{1}=0,\\
&~{}~{}x_{4}-x_{5}=0,\ x_{5}-x_{6}=0,\\
&~{}~{}x_{6}-x_{7}=0,\ x_{7}-x_{4}=0,\\
&~{}~{}x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}=6\\
&~{}~{}0\leq x_{j}\leq 3,\ x_{j}\in\mathbb{Z},\ \forall~{}j\in\{1,2,\dots,7\}.
\end{split}$
$\min~{}\frac{1}{2}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}
\definecolor[named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}&{\color[
rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}&{\color[rgb]{0.1953125,0.78515625,0.1953125}
\definecolor[named]{pgfstrokecolor}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}
\end{bmatrix}\begin{bmatrix}1&0.1&\\
0.1&1&\\
&&1\end{bmatrix}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}\definecolor
[named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}\\
{\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}\\
{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor
}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}\end{bmatrix}+\begin{bmatrix}1&2&3
\end{bmatrix}\begin{bmatrix}{\color[rgb]{0.203125,0.59765625,1}\definecolor[
named]{pgfstrokecolor}{rgb}{0.203125,0.59765625,1}x_{1}}\\
{\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}\\
{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor
}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}\end{bmatrix}$ %Reduce the space between columns s.t.
$2{\color[rgb]{0.203125,0.59765625,1}\definecolor[named]{pgfstrokecolor}{rgb}{
0.203125,0.59765625,1}x_{1}}$
$+$
${\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}$
$\leq 5$
${\color[rgb]{1,0.296875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{
1,0.296875,0.234375}x_{2}}$
$+$
$3{\color[rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{
pgfstrokecolor}{rgb}{0.1953125,0.78515625,0.1953125}x_{3}}$
$\geq 0$
$0\leq{\color[rgb]{0.203125,0.59765625,1}\definecolor[named]{pgfstrokecolor}{
rgb}{0.203125,0.59765625,1}x_{1}},{\color[rgb]{1,0.296875,0.234375}
\definecolor[named]{pgfstrokecolor}{rgb}{1,0.296875,0.234375}x_{2}},{\color[
rgb]{0.1953125,0.78515625,0.1953125}\definecolor[named]{pgfstrokecolor}{rgb}{
0.1953125,0.78515625,0.1953125}x_{3}}\leq 1$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$$w_{7}$
One can easily verify that both problems are feasible. The feasible region of the first problem is $\{(3,3,0,0,0,0,0)\}$ and the feasible region of the second problem is $\{(2,2,2,0,0,0,0)\}$. Thus, the two problems have the same optimal objective value, say $24$, but their optimal solution sets are disjoint, without any common element.

On the other hand, it can be analyzed using the same argument as in the proof of Proposition 4.2 that for any $0\leq l\leq L$ that

- (a)
$s_{i}^{l}=\hat{s}_{i}^{l}$ is constant over $i\in\{1,2,\dots,7\}$, and $s_{8}^{l}=\hat{s}_{8}^{l}$.
- (b)
$t_{j}^{l}=\hat{t}_{j}^{l}$ is constant over $j\in\{1,2,\dots,7\}$.

These two conditions guarantee that $F(G_{\textup{MI-LCQP}})=F(\hat{G}_{\textup{MI-LCQP}}),\ \forall~{}F\in\mathcal
{F}_{\textup{MI-LCQP}}$ and $F_{W}(G_{\textup{MI-LCQP}})=F_{W}(\hat{G}_{\textup{MI-LCQP}}),\ \forall~{}F_{W
}\in\mathcal{F}_{\textup{MI-LCQP}}$.
∎

###### Proof of Proposisition 4.2 .

###### Proof of Proposition 4.3 .

## Appendix C Characterization of unfoldability and MP-tractability

In this section, we discuss some further characterizations of the unfoldability and the MP-tractability for MI-LCQP-graphs defined in Section 4.2.

We first prove that the unfoldability implies the MP-tractability but they are not equivalent.

###### Proposition C.1 .

If $G_{\textup{MI-LCQP}}\in\mathcal{G}_{\textup{MI-LCQP}}^{m,n}$ is unfoldable, then it is also MP-tractable.

###### Proof.

Let $(\mathcal{I},\mathcal{J})$ be the final stable partition of $V\cup W$ generated by WL test on $G_{\textup{MI-LCQP}}$ without collision, where $\mathcal{I}=\{I_{1},I_{2},\dots,I_{s}\}$ is a partition of $V=\{1,2,\dots,m\}$ and $\mathcal{J}=\{J_{1},J_{2},\dots,J_{t}\}$ is a partition of $W=\{1,2,\dots,n\}$. Since we assume that $G_{\textup{MI-LCQP}}$ is foldable, we have $t=n$ and $|J_{1}|=|J_{2}|=\cdots=|J_{n}|=1$. Then for any $q,q^{\prime}\in\{1,2,\dots,t\}$, the submatrix $(Q_{jj^{\prime}})_{j\in J_{q},j^{\prime}\in J_{q^{\prime}}}$ is a $1\times 1$ matrix and hence has identical entries.

Consider any $p\in\{1,2,\dots,s\}$ and $q\in\{1,2,\dots,t\}$. Suppose that the color positioning is stabilized at the $L$-th iteration of WL test. Then for any $i,i^{\prime}\in I_{p}$, we have

$$ $\displaystyle C_{i}^{L,V}=C_{i^{\prime}}^{L,V}$ $\displaystyle\implies$ $\displaystyle\left\{\left\{\text{HASH}\left(C_{j}^{L-1,W},A_{ij}\right):j\in \mathcal{N}_{i}^{W}\right\}\right\}=\left\{\left\{\text{HASH}\left(C_{j}^{L-1, W},A_{i^{\prime}j}\right):j\in\mathcal{N}_{i}^{W}\right\}\right\}$ $\displaystyle\implies$ $\displaystyle\left\{\left\{A_{ij}:j\in J_{q}\right\}\right\}=\left\{\left\{A_{ i^{\prime}j}:j\in J_{q}\right\}\right\},$ $$

which implies that the submatrix $(A_{ij})_{i\in I_{p},j\in J_{q}}$ has identical entries since $|J_{q}|=1$. Therefore, $G_{\textup{MI-LCQP}}$ is MP-tractable.
∎

###### Proposition C.2 .

There exist MP-tractable instances in $\mathcal{G}_{\textup{MI-LCQP}}^{m,n}$ that are not unfoldable.

###### Proof.

Figure: Figure 6. Example for proving Proposition C.2

Consider the example in Figure 6, for which the final stable partition is $\mathcal{I}=\{\{1\},\{2\}\}$ and $\mathcal{J}=\{\{1,3\},\{2\}\}$. It is not unfoldable since the class $\{1,3\}$ in $\mathcal{J}$ has two elements. However, it is MP-tractable since $A_{11}=A_{13}=1$ and $A_{21}=A_{23}=1$.
∎

We then show that a generic MI-LCQP-graph in $\mathcal{G}_{\textup{MI-LCQP}}^{m,n}$ must be unfoldable. Intuitively, if $c\in\mathbb{R}^{n}$ is randomly sampled from a continuous distribution with density, then almost surely it holds that $x_{j}\neq x_{j^{\prime}}$ for any $j\neq j^{\prime}$, which implies that the vertices in $W$ have different colors initially and always, if there are no collisions of hash functions.

###### Proposition C.3 .

Let $\mathbb{P}$ be a probability measure over $\mathcal{G}_{\textup{MI-LCQP}}$ such that the marginal distribution $\mathbb{P}_{c}$ of $c\in\mathbb{R}^{n}$ has density. Then $\mathbb{P}[\mathcal{G}_{\textup{MI-LCQP}}\in\mathcal{G}_{\textup{unfold}}^{m,n
}]=1$.

###### Proof.

Since the marginal distribution $\mathbb{P}_{c}$ has density, almost surely we have for any $j\neq j^{\prime}$ that

$$ $c_{j}\neq c_{j^{\prime}}\implies C_{j}^{0,W}\neq C_{j^{\prime}}^{0,W}\implies C _{j}^{l,W}\neq C_{j^{\prime}}^{l,W},\quad\forall~{}l\geq 0,$ $$

where we assumed that no collisions happen in hash functions. Therefore, any $j,j^{\prime}\in W$ with $j\neq j^{\prime}$ are not the in same class of the final stable partition $(\mathcal{I},\mathcal{J})$, which proves the unfoldability.
∎

As a direct corollary of Proposition C.1 and Proposition C.3, a generic MI-LCQP-graph in $\mathcal{G}_{\textup{MI-LCQP}}^{m,n}$ must also be MP-tractable.

###### Corollary C.4 .

Let $\mathbb{P}$ be a probability measure over $\mathcal{G}_{\textup{MI-LCQP}}$ such that the marginal distribution $\mathbb{P}_{c}$ of $c\in\mathbb{R}^{n}$ has density. Then $\mathbb{P}[\mathcal{G}_{\textup{MI-LCQP}}\in\mathcal{G}_{\textup{MP}}^{m,n}]=1$.

###### Proposition C.1 .

###### Proof.

###### Proposition C.2 .

###### Proof.

###### Proposition C.3 .

###### Proof.

###### Corollary C.4 .

## Appendix D Proofs for Section 4.2

This section collects the proofs of Theorems 4.6, 4.7, and 4.9. Similar to the LCQP case, the proofs are also based on the WL test (Algorithm 1) and its separation power to distinguish MI-LCQP problems with different properties. We define the separation power of Algorithm 1 as follows.

###### Definition D.1 .

Let $G_{\textup{MI-LCQP}},\hat{G}_{\textup{MI-LCQP}}\in\mathcal{G}_{\textup{MI-LCQP
}}^{m,n}$ be two MI-LCQP-graphs and denote $\{\{C_{i}^{L,V}\}\}_{i=0}^{m},\{\{C_{j}^{L,W}\}\}_{j=0}^{n}$ and $\{\{\hat{C}_{i}^{L,V}\}\}_{i=0}^{m},\{\{\hat{C}_{j}^{L,W}\}\}_{j=0}^{n}$ as the color multisets output by Algorithm 1 on $G_{\textup{MI-LCQP}}$ and $\hat{G}_{\textup{MI-LCQP}}$.

- (a)
We say $G_{\textup{MI-LCQP}}\sim\hat{G}_{\textup{MI-LCQP}}$ if for all $L\in\mathbb{N}$ and all hash functions, $\{\{C_{i}^{L,V}\}\}_{i=0}^{m}=\{\{\hat{C}_{i}^{L,V}\}\}_{i=0}^{m}$ and $\{\{C_{j}^{L,W}\}\}_{j=0}^{n}=\{\{\hat{C}_{j}^{L,W}\}\}_{j=0}^{n}$.
- (b)
We say $G_{\textup{MI-LCQP}}\stackrel{{\scriptstyle W}}{{\sim}}\hat{G}_{\textup{MI-
LCQP}}$ if for all $L\in\mathbb{N}$ and all hash functions, $\{\{C_{i}^{L,V}\}\}_{i=0}^{m}=\{\{\hat{C}_{i}^{L,V}\}\}_{i=0}^{m}$ and $C_{j}^{L,W}=\hat{C}_{j}^{L,W},\ \forall~{}j\in\{1,2,\dots,n\}$.

The key component in the proof is to show that for unfoldable/MP-tractable MI-LCQP problems, if they are indistinguishable by WL test, then they must share some common properties.

###### Theorem D.2 .

For any two MP-tractable MI-LCQP-graphs $G_{\textup{MI-LCQP}},\hat{G}_{\textup{MI-LCQP}}\in\mathcal{G}_{\textup{MP}}^{m
,n}$, if $G_{\textup{MI-LCQP}}\sim\hat{G}_{\textup{MI-LCQP}}$, then $\Phi_{\textup{feas}}(G_{\textup{MI-LCQP}})=\Phi_{\textup{feas}}(\hat{G}_{
\textup{MI-LCQP}})$ and $\Phi_{\textup{obj}}(G_{\textup{MI-LCQP}})=\Phi_{\textup{obj}}(\hat{G}_{\textup
{MI-LCQP}})$.

###### Proof.

Let $G_{\textup{MI-LCQP}}$ and $\hat{G}_{\textup{MI-LCQP}}$ be the MI-LCQP-graphs associated to

$$ (D.1) $\min_{x\in\mathbb{R}^{n}}~{}~{}\frac{1}{2}x^{\top}Qx+c^{\top}x,\quad\textup{s. t.}~{}~{}Ax\circ b,\ l\leq x\leq u,\ x_{j}\in\mathbb{Z},\ \forall~{}j\in I.$ $$

and

$$ (D.2) $\min_{x\in\mathbb{R}^{n}}~{}~{}\frac{1}{2}x^{\top}\hat{Q}x+\hat{c}^{\top}x, \quad\textup{s.t.}~{}~{}\hat{A}x\ \hat{\circ}\ \hat{b},\ \hat{l}\leq x\leq\hat {u},\ x_{j}\in\mathbb{Z},\ \forall~{}j\in\hat{I}.$ $$

Suppose that there are no collisions of hash functions or their linear combinations when applying the WL test to $G_{\textup{MI-LCQP}}$ and $\hat{G}_{\textup{MI-LCQP}}$ and there are no strict color refinements in the $L$-th iteration.
Since $G_{\textup{MI-LCQP}}\sim\hat{G}_{\textup{MI-LCQP}}$ and both of them are MP-tractable, after performing some permutation, there exist $\mathcal{I}=\{I_{1},I_{2},\dots,I_{s}\}$ and $\mathcal{J}=\{J_{1},J_{2},\dots,J_{t}\}$ that are partitions of $\{1,2,\dots,m\}$ and $\{1,2,\dots,n\}$, respectively, such that the followings hold:

- •
$C_{i}^{L,V}=C_{i^{\prime}}^{L,V}$ if and only if $i,i^{\prime}\in I_{p}$ for some $p\in\{1,2,\dots,s\}$.
- •
$C_{i}^{L,V}=\hat{C}_{i^{\prime}}^{L,V}$ if and only if $i,i^{\prime}\in I_{p}$ for some $p\in\{1,2,\dots,s\}$.
- •
$\hat{C}_{i}^{L,V}=\hat{C}_{i^{\prime}}^{L,V}$ if and only if $i,i^{\prime}\in I_{p}$ for some $p\in\{1,2,\dots,s\}$.
- •
$C_{j}^{L,W}=C_{j^{\prime}}^{L,W}$ if and only if $j,j^{\prime}\in J_{q}$ for some $q\in\{1,2,\dots,t\}$.
- •
$C_{j}^{L,W}=\hat{C}_{j^{\prime}}^{L,W}$ if and only if $j,j^{\prime}\in J_{q}$ for some $q\in\{1,2,\dots,t\}$.
- •
$\hat{C}_{j}^{L,W}=\hat{C}_{j^{\prime}}^{L,W}$ if and only if $j,j^{\prime}\in J_{q}$ for some $q\in\{1,2,\dots,t\}$.

By similar analysis as in the proof of Theorem A.2, we have

- (a)
$v_{i}=\hat{v}_{i}$ and is constant over $i\in I_{p}$ for any $p\in\{1,2,\dots,s\}$.
- (b)
$w_{j}=\hat{w}_{j}$ and is constant over $j\in J_{q}$ for any $q\in\{1,2,\dots,t\}$.
- (c)
For any $p\in\{1,2,\dots,s\}$ and any $q\in\{1,2,\dots,t\}$, $\{\{A_{ij}:j\in J_{q}\}\}=\{\{\hat{A}_{ij}:j\in J_{q}\}\}$ and is constant over $i\in I_{p}$.
- (d)
For any $p\in\{1,2,\dots,s\}$ and any $q\in\{1,2,\dots,t\}$, $\{\{A_{ij}:i\in I_{p}\}\}=\{\{\hat{A}_{ij}:i\in I_{p}\}\}$ and is constant over $j\in J_{q}$.
- (e)
For any $q,q^{\prime}\in\{1,2,\dots,t\}$, $\{\{Q_{jj^{\prime}}:j^{\prime}\in J_{q^{\prime}}\}\}=\{\{\hat{Q}_{jj^{\prime}}
:j^{\prime}\in J_{q^{\prime}}\}\}$ and is constant over $j\in J_{q}$.

Note that $G_{\textup{MI-LCQP}}$ and $\hat{G}_{\textup{MI-LCQP}}$ are both MP-tractable, i.e., all submatrices $(A_{ij})_{i\in I_{p},j\in J_{q}}$, $(\hat{A}_{ij})_{i\in I_{p},j\in J_{q}}$, $(Q_{jj^{\prime}})_{j\in J_{q},j^{\prime}\in J_{q^{\prime}}}$, and $(\hat{Q}_{jj^{\prime}})_{j\in J_{q},j^{\prime}\in J_{q^{\prime}}}$ have identical entries. The above conditions (c)-(e) suggest that

- (f)
For any $p\in\{1,2,\dots,s\}$ and any $q\in\{1,2,\dots,t\}$, $A_{ij}=\hat{A}_{ij}$ and is constant over $i\in I_{p},j\in J_{q}$.
- (g)
For any $q,q^{\prime}\in\{1,2,\dots,t\}$, $Q_{jj^{\prime}}=\hat{Q}_{jj^{\prime}}$ and is constant over $j\in J_{q},j^{\prime}\in J_{q^{\prime}}$.

Combining conditions (a), (b), (f), and (g), we can conclude that $G_{\textup{MI-LCQP}}$ and $\hat{G}_{\textup{MI-LCQP}}$ are actually identical after applying some permutation, i.e., they are isomorphic, which implies $\Phi_{\textup{feas}}(G_{\textup{MI-LCQP}})=\Phi_{\textup{feas}}(\hat{G}_{
\textup{MI-LCQP}})$ and $\Phi_{\textup{obj}}(G_{\textup{MI-LCQP}})=\Phi_{\textup{obj}}(\hat{G}_{\textup
{MI-LCQP}})$.
∎

###### Theorem D.3 .

For any two MI-LCQP-graphs $G_{\textup{MI-LCQP}},\hat{G}_{\textup{MI-LCQP}}\in\mathcal{G}_{\textup{sol}}^{
m,n}\cap\mathcal{G}_{\textup{unfold}}^{m,n}$ that are unfoldable with nonempty optimal solution sets, if $G_{\textup{MI-LCQP}}\sim\hat{G}_{\textup{MI-LCQP}}$, then there exists some permutation $\sigma_{W}\in S_{n}$ such that $\Phi_{\textup{sol}}(G_{\textup{MI-LCQP}})=\sigma_{W}(\Phi_{\textup{sol}}(\hat{
G}_{\textup{MI-LCQP}}))$. Furthermore, if $G_{\textup{MI-LCQP}}\stackrel{{\scriptstyle W}}{{\sim}}\hat{G}_{\textup{MI-
LCQP}}$, then $\Phi_{\textup{sol}}(G_{\textup{MI-LCQP}})=\Phi_{\textup{sol}}(\hat{G}_{\textup
{MI-LCQP}})$.

###### Proof.

By Proposition C.1, $G_{\textup{MI-LCQP}}$ and $\hat{G}_{\textup{MI-LCQP}}$ are also MP-tractable, and hence, all analysis in the proof of Theorem D.2 applies. If $G_{\textup{MI-LCQP}}\sim\hat{G}_{\textup{MI-LCQP}}$, then they are isomorphic and $\Phi_{\textup{sol}}(G_{\textup{MI-LCQP}})=\sigma_{W}(\Phi_{\textup{sol}}(\hat{
G}_{\textup{MI-LCQP}}))$ for some permutation $\sigma_{W}\in S_{n}$. If $G_{\textup{MI-LCQP}}\stackrel{{\scriptstyle W}}{{\sim}}\hat{G}_{\textup{MI-
LCQP}}$, then these two graphs will become identical after applying some permutation on $V$ with the labeling in $W$ unchanged, which guarantees $\Phi_{\textup{sol}}(G_{\textup{MI-LCQP}})=\Phi_{\textup{sol}}(\hat{G}_{\textup
{MI-LCQP}})$.
∎

With Theorem D.2 and Theorem D.3, one can adopt standard argument in the previous literature to prove Theorems 4.6, 4.7, and 4.9.

###### Proof of Theorem 4.6 .

Based on Theorem D.2, Theorem 4.6 can be proved following the same lines as in the proof of Theorem 3.2 in [chen2022representing-lp], with straightforward modifications to generalize results for LP-graphs to the MI-LCQP setting.
∎

###### Proof of Theorem 4.7 .

Based on Theorem D.2, Theorem 4.7 can be proved following the same lines as in the proof of Theorem 3.4 in [chen2022representing-lp], with straightforward modifications to generalize results for LP-graphs to the MI-LCQP setting.
∎

###### Proof of Theorem 4.9 .

Based on Theorem D.3 and the unfoldability assumption that different vertices in $W$ will eventually have different colors in the WL test without collision, which automatically provides a result of the same spirit as Corollary A.5, Theorem 4.9 can be proved following the same lines as in the proof of Theorem 3.6 in [chen2022representing-lp], with straightforward modifications to generalize results for LP-graphs to the MI-LCQP setting.
∎

###### Definition D.1 .

###### Theorem D.2 .

###### Proof.

###### Theorem D.3 .

###### Proof.

###### Proof of Theorem 4.6 .

###### Proof of Theorem 4.7 .

###### Proof of Theorem 4.9 .

## Appendix E Implementation details and additional numerical results

### E.1. Random LCQP and MI-LCQP instance generation

Generic LCQP and MI-LCQP generation. For all instances generated and used in our numerical experiments, we set $m=10$ and $n=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_sparse_spd_matrix function provided by the scikit-learn Python package, which imposes sparsity on the Cholesky factor. We set the alpha value to 0.95 so that there will be around $10\%$ non-zero elements in the resulting $Q$ matrix.
- •
The coefficients $c$ in the objective function: $c_{j}\sim\mathcal{N}(0,0.1^{2})$.
- •
The non-zero elements in the coefficient matrix: $A_{ij}\sim\mathcal{N}(0,1)$. The coefficient matrix $A$ contains 100 non-zero elements. The positions are sampled randomly.
- •
The right hand side $b$ of the linear constraints: $b_{i}\sim\mathcal{N}(0,1)$.
- •
The constraint types $\circ$. We first sample equality constraints following the Bernoulli distribution $Bernoulli(0.3)$. Then other constraints takes the type $\leq$. Note that this is equivalent to sampling $\leq$ and $\geq$ constraints separately with equal probability, because the elements in $A$ and $b$ are sampled from symmetric distributions.
- •
The lower and upper bounds of variables: $l_{j},u_{j}\sim\mathcal{N}(0,10^{2})$. We swap their values if $l_{j}>u_{j}$ after sampling.
- •
(MI-LCQP only) The variable types are randomly sampled. Each type (continuous or integer) occurs with equal probability.

After instance generation is done, we collect labels, i.e., the optimal objective function values and optimal solutions, using one 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$, $u$ and $\circ$ in (2.1), 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 as above.
- •
The coefficients $c$ in the objective function: $c_{j}\sim\mathcal{N}(0,1/n)$.
- •
The non-zero elements in the coefficient matrix: $A_{ij}\sim\mathcal{N}(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: $b_{i}\sim\mathcal{N}(0,1/n)$.
- •
The constraint types $\circ$. We follow the same sampling scheme as above.
- •
The lower and upper bounds of variables: $l_{j},u_{j}\sim\mathcal{N}(0,1)$. We swap their values if $l_{j}>u_{j}$ after sampling.

For the generalization experiments, we first generate 25,000 LCQP instances for training, and then take the first 100/500/25,00/5,000/10,000 instances to form the smaller training sets. This ensures that the smaller training sets are subsets of the larger sets. The validation set contains 1,000 instances that are generated separately.

### E.2. Details of GNN implementation

We implement GNN with Python 3.9 and TensorFlow 2.16.1 [abadi2016tensorflow]. Our implementation is built by extending the GNN implementation in [gasse2019exact].(^6^66See [https://github.com/ds4dm/learn2branch](https://github.com/ds4dm/learn2branch).)
The embedding mappings $f_{0}^{V},f_{0}^{W}$ are parameterized as linear layers followed by a non-linear activation function; $\{f_{l}^{V},f_{l}^{W},g_{l}^{V},g_{l}^{W},g_{l}^{Q}\}_{l=1}^{L}$ and the output mappings $r_{1},r_{2}$ 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, we train GNNs with embedding sizes of 64, 128, 256, 512 and 1,024. We show in Table 1 the number of learnable parameters in the resulting network with each embedding size.

**Table 1. 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 |

### E.3. Details of GNN training

We adopt Adam [kingma2014adam] to optimize the learnable parameters during training. We use an initial learning rate of $5\times 10^{-4}$ for all networks. We set the batch size to 2,500 or the size of the training set, whichever is the smaller. In each mini-batch, we combine the graphs into one large graph to accelerate training. All experiments are conducted on a single NVIDIA Tesla V100 GPU.

We use mean squared relative error as the loss function, which is defined as

$$ (E.1) $\displaystyle L_{\mathcal{G}}(F_{W})=\mathbb{E}_{G\sim\mathcal{G}}\left[\frac{ \|F_{W}(G)-\Phi(G)\|_{2}^{2}}{\max(\|\Phi(G)\|,1)^{2}}\right],$ $$

where $F_{W}$ is the GNN, $\mathcal{G}$ is a mini-batch sampled from the whole training set, $G$ is a problem instance in the mini-batch $\mathcal{G}$, and $\Phi(G)$ is the label of instance $G$.
During training, we monitor the average training error in each epoch. If the training loss does not improve for 50 epochs, we 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 to stabilize the training process significantly and can also improve the final loss achieved.

### E.4. Full generalization results on LCQP

Figure: (a) Fit $\Phi_{\textup{obj}}$ for LCQP
Refer to caption: x10.png

Figure 7 shows the variations of training and validation errors when training GNNs of an 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 as more instances are 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 3 and 4).

## Peer Reviews

confidence: 5
contribution: 2
initial_rating: 5
presentation: 3
questions: I will consider changing my opinion if the authors can address my comments in "weakness".
soundness: 3
strengths: 1. The paper studies a crucial topic in the field of learning to optimize (L2O). GNNs have been extensively utilized for learning key properties—primarily optimal solutions—of optimization problems. By focusing on the representational power of GNNs in this context, the study offers theoretical insights and potential practical guidance.

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

3. The paper is well-written and highly accessible, making it easy to follow.
summary: This paper studies whether GNN can represent key properties (such as feasibility, optimal value, and optimal solution) of LCQP (Linearly Constrained Quadratic Programming) and MI-LCQP (Mixed-Integer LCQP) problems. The study establishes the following theoretical results:

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

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

The authors further provide small-scale experimental evidence to support the theoretical results.
weaknesses: My major concern lies in distinguishing the analysis in this paper from previous studies of GNN's representation power on LP/MILP (Chen et al. (2023a), Chen et al. (2023b)). Two significant similarities raise questions about the originality of the analysis technique:

1. To prove the universal representation power of LCQP,  the authors leverage the Stone-Weierstrass theorem to establish the GNN's approximation capabilities based on their separation capabilities. This approach appears identical to that used by Chen et al. (2023a) for LPs. In particular, the proof ideas of Theorems 3.3 and 3.4 (illustrated on Page 5) seem directly translatable to LPs, with minimal modification (i.e., replacing LCQPs with LPs). If this understanding is correct, the theoretical innovation for LCQPs might be limited.

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

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

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Compared to Chen et al. (2023a, b), what are the non-trivial contributions of the theoretical analysis?
soundness: 3
strengths: 1. **Importance of GNN for QP**: The paper tackles an important problem by providing a theoretical foundation on the representational power of GNNs for quadratic programming, which is relevant to various practical applications.
2. **Clarity of Writing**: The paper is well-structured, making it easy to follow. The clear explanations and organized framework enhance readability and accessibility.
summary: The paper investigates the expressive power of GNNs in representing key properties of quadratic programs (QP) and mixed-integer QP (MI-QP). It provides a theoretical foundation for using GNNs to approximate feasibility, optimal objective values, and solutions for QPs. The study includes both theoretical proofs and experimental results.
weaknesses: 1. **Novelty and Limited Contributions**: While the paper aims to establish theoretical insights into GNNs' representation capabilities for QPs, much of its theoretical approach relies on Chen et al. (2023a, b), which studies the representation power of GNNs for LP and MILP. The paper’s theoretical contributions to the QP domain are thus incremental and may lack non-trivial novelty.

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

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

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: - Can the authors elaborate on the difference of second part of Theorem 3.3 and Theorem 3.4? Isn't it true that Theorem 3.4 implies the second part of Theorem 3.3 simply by continuity of the evaluation of the objective function?

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

- (Due to weakness 1) In which part exactly did the authors prove the separation property claimed page 5?
soundness: 3
strengths: - The paper has complete introduction and clearly states the contribution.

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

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

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

Overall, I find the motivations of the study and the results interesting. In particular the positive results in the positive semi-definite case interesting. However, I have some reservations as detailed next.
summary: In this article the authors present new regarding the expressivity of GNNs for Quadratic Programming, and more specifically for Quadratic Programs (QPs) with linear constraints (continuous and mixed integer). In particular, they explicit a class of QPs (called MP-tractable) such that for each QP in the class, there exists a GNN that can provide accurate information about the feasability and the optimal value of the QP. The main results are stated in Theorem 3.3 and Theorem 3.4, and hold in probability, given a distribution on the considered class of QPs.
weaknesses: - The MP-tractable class is not very insightful or practical to work with. Can the authors elaborate if the criterion they propose is efficient to be tested? (as one of the initial motivations in the introduction was to improve efficiency in solving QPs?)

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

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

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Here are several questions and suggestions for the authors:
1. Could the authors elaborate on the situations where MP-tractability and unfoldability assumptions might not hold? Are there practical examples where these conditions might fail, and how would that impact the use of GNNs in those cases?
2. The paper includes several assumptions, such as Q being symmetric and the mappings being continuous. Could the authors explain why these assumptions are necessary and how they influence the proof process? 
3. Beyond the testing on synthetic data, can the authors discuss the limitations or difficulties of applying for the GNN in practical LCQP and MI-LCQP problems, e.g., applications or optimizations in power system operations or financial portfolio? 
4. Could the authors provide more experimental insights into how different message-passing mechanisms or GNN architectures might affect performance? 
5. The WL test is central to the theoretical results but may be challenging for some readers. Can the authors provide more intuitive insights or examples to illustrate how the WL test is applied in this context?
soundness: 3
strengths: The paper offers a strong contribution to understanding the expressive power of Graph Neural Networks (GNNs) for Quadratic Programming (QP), particularly for linearly constrained (LCQP) and mixed-integer (MI-LCQP) problems. The strengths of the paper include:
1. The authors have innovatively connected GNNs with LCQPs and MI-LCQPs, an area that has received limited attention, thereby expanding the potential applications of GNNs in optimization.
2. The proofs are well-structured, and the reliance on the Weisfeiler-Lehman (WL) test to support the expressive power of GNNs is a thoughtful and sound approach. 
3. The paper is well-organized, with a logical flow from background concepts to theoretical contributions and then to experimental results. 
4. The significance of this work lies in its potential impact on optimization problems where approximate solutions are acceptable.
summary: This work explores the expressive power of GNNs for LCQP and MI-LCQP, representing a significant contribution to the field. The authors provide a valuable framework and a theoretical foundation to demonstrate GNNs' capabilities in representing feasibility, optimal objective values, and solutions for LCQPs. Detailed proofs and well-structured analysis are commendable, and the organization of the paper is logical and flows well.
weaknesses: Several aspects could be improved for greater applicability and clarity:
1. The assumptions such as MP-tractability and unfoldability in Section 4, as well as the requirements for Q to be symmetric and the mappings to be continuous, might limit the broader applicability of the results in practical scenarios. 
2. Certain assumptions, such as the existence of an optimal solution for MI-LCQPs and continuity in mappings, are necessary for the proofs but lack a detailed discussion of their purpose and impact on the proof process. Without understanding why these assumptions are critical, readers might find it difficult to gauge the generalizability and limitations of the theoretical results.
3. The experimental validation relies on randomly generated LCQP and MI-LCQP instances, which may not fully capture the diversity and complexity of real-world problems. 
4. While embedding size is explored, there are few ablation studies to test other aspects of the model, such as alternative message-passing mechanisms or different GNN architectures.

---

confidence: 4
contribution: 4
initial_rating: 6
presentation: 4
questions: Please refer to "Weakness".
soundness: 4
strengths: 1. Theoretical foundation: The paper successfully bridges the gap between theoretical predictions and empirical results by demonstrating the capacity of GNNs to represent QPs.
2. Solid theoratical proofs: The authors provide well-founded proofs to support their theoretical claims.
3. Impactful: The discoveries in this work pave the way for further exploration of GNN applications in accelerating solutions to QP problems, holding the potential for significant empirical advancements.
4. The paper is generally well-written and easy to follow.
summary: This work investigates the expressive power of graph neural networks (GNNs) in representing both continuous and discrete quadratic programs (QPs). Specifically, it validates three key capabilities related to the empirical performance of GNNs for QPs: accurately predicting feasibility, optimality, and optimal solutions. By answering these questions, the study bridges the gap between theoretical and empirical aspects, shedding light on the strong performance observed in prior research in this field. The authors also provide sufficient numerical results to support their claims.
weaknesses: The primary concern regarding this work is the specific type of MI-LCQPs that can be represented by GNNs. 
Providing examples of application scenarios for this type of problem would help strengthen the authors' claims, as mixed-integer problems with unique optimal solutions do not appear to be very common in practice.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: Refer to "Weakness"
soundness: 3
strengths: This paper establishes a solid theoretical foundation for the application of GNNs to LCQPs and MI-LCQPs. The writing is clear.
summary: The paper investigates the expressive power of Graph Neural Networks (GNNs) for solving linearly constrained quadratic programming (LCQP) and its mixed-integer variant (MI-LCQP). The authors focus on a key question: Do GNNs possess sufficient expressive power to predict feasibility, optimal objective value, and an optimal solution? The paper provides an affirmative answer for general LCQPs but a negative one for general MI-LCQPs. However, the authors also identify specific subclasses of MI-LCQP for which the answer is affirmative.
weaknesses: 1. In order to strengthen the motivation, I would suggest including a survey of previous empirical successes of GNNs in quadratic programming or providing 2-3 specific examples of recent empirical successes of GNNs in quadratic programming, along with brief descriptions of the key results and implications.
2. The paper lacks an analysis of GNN size and depth. These factors are crucial in practical applications.

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

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

Decision: Reject