On Designing General and Expressive Quantum Graph Neural Networks with Applications to MILP Instance Representation
Authors: Xinyu Ye
Hao Xiong
Jianhao Huang
Ziang Chen
Jia Wang
Junchi Yan
Venue: ICLR 2025 Poster (2025)
Keywords: Quantum machine learning
Mixed-integer linear programming
Graph learning
Primary area: foundation or frontier models, including LLMs

Abstract: Graph-structured data is ubiquitous, and graph learning models have recently been extended to address complex problems like mixed-integer linear programming (MILP). However, studies have shown that the vanilla message-passing based graph neural networks (GNNs) suffer inherent limitations in learning MILP instance representation, i.e., GNNs may map two different MILP instance graphs to the same representation. In this paper, we introduce an expressive quantum graph learning approach, leveraging quantum circuits to recognize patterns that are difficult for classical methods to learn. Specifically, the proposed General Quantum Graph Learning Architecture (GQGLA) is composed of a node feature layer, a graph message interaction layer, and an optional auxiliary layer. Its generality is reflected in effectively encoding features of nodes and edges while ensuring node permutation equivariance and flexibly creating different circuit structures for various expressive requirements and downstream tasks. GQGLA is well suited for learning complex graph tasks like MILP representation. Experimental results highlight the effectiveness of GQGLA in capturing and learning representations for MILPs. In comparison to traditional GNNs, GQGLA exhibits superior discriminative capabilities and demonstrates enhanced generalization across various problem instances, making it a promising solution for complex graph tasks.

Published as a conference paper at ICLR 2025
ON DESIGNING GENERAL AND EXPRESSIVE QUANTUM GRAPH NEURAL NETWORKS WITH APPLICATIONS TO MILP INSTANCE REPRESENTATION
Xinyu Yc', Hao Xiong', Jianhao Huang', Ziang Chen', Jia Wang", Junchi Yan 1. Shanghai Jiao Tong University, Shanghai. China. Massachusetts Institute of Technology. Massachusettss, United States.
f nyu ye, taxuexh, huang jh202 e jtu edu. z ang@mit edd,, {jiawang, yan yanjunchi jejjtt- jts.jdu..cc .nd..cn
ABSTRACT
Graph-structured data is ubiquitous, and graph learning models have recently been extended to address complex problems like mixed-integer linear programming (MILP). However, studies have shown that the vanilla message-passing based graph neural networks (GNNs) suffer inherent limitations in learning MILP in- stance representation, i.e.. GNNs may map two different MILP instance graphs to the same representation. In this paper, we introduce an expressive quantum graph learning approach, leveraging quantum circuits to recognize patterns that are difficult for classical methods to learn. Specifically, the proposed General Quantum Graph Learning Architecture (GQGLA) is composed of a node feature layer, a graph message interaction layer, and an optional auxiliary layer. Its generality is reflected in effectively encoding features of nodes and edges while ensuring node permutation equivariance and ficxibly creating different circuit structures for various expressive requirements and downstream tasks. GQGLA is well suited for learning complex graph tasks like MILP representation. Experimental results highlight the effectiveness of GQGLA in capturing and learning representations for MILPs. In comparison to traditional GNNs, GQGLA exhibits superior discrimina- tive capabilities and demonstrates enhanced generalization across various problem instances, making it a promising solution for complex graph tasks.
INTRODUCTION
Mixed-integer linear programming (MILP) serves general optimization formulation appli-
cable to diverse real-world optimization scenarios, such as transportation (Schouwenaars et al., 2001), scheduling (Floudas & Lin, 2005b), and production planning (Askari-Nasab al., 201 1). MILP aims to minimize a linear objective func- tion while adhering to linear constraints. Apart from the classic non-learning solvers that of- ten resort to heuristics, recent learning-bant based models have been actively studied, and graph neural networks (GNNs) are considered a suit- able backbone to represent the mappings for MILP instances in various stages of MILP solv- ing processes (Khalil al., 2022; Gupta et al., 2022; Wang et al., 2023; Li et al., 2025). MILP instance can be regarded
(a) Feasible
(b) Infeasible
min X
min Σ % S.L.
s.t.
+ +Xg
2, +.
0 S $1x EB
(12.....
0 Sx s Lx, Ex (1.
(0111.0) Kya
GNN
GNN
F(G.)
Fsel
weighted bipartite graph with node features, as illus- trated Fig. I and Fig. Due to the beneficial property of GNN, permutations on variables or constraints of MILP do not essentially change
Figure 1: A pair of GNN-intractuble MILPs G2 and G2. (a) feasible and (b) is infeasible. Although their edge connectivity and fcasibility are different, GNNs embed them into the same representation.
"Correspondence author who is also affiliated with Shanghai Innovation Institute. Work was partly supported by NSFC (62222607), Shanghai Municipal Science and Technology Major Project (2011SHZDZX0102),

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of QNNs for classical graph data on several aspects: whether the models provide implementable circuits, enjoy permutation equivariance, consider nulti-dimensional node or edge features, utilize quantum (Q) layers or classical (C) layers, and the manner of readout. Compared to other methods, our proposed model addresses multiple aspects, can be applied to both node-level and graph-level tasks, and achieves advantage validation over GNNs in learning graph representations.
Method
Quantum Circuit
Embodied
Permutation Equivariance
Attribute
Layer
Readout
Application
QGNN (Verdon al., 2019)
Tomegraphy
& Graph homorphism Clessiication
Learning Hamiltonian Dynumics
QGCN [Zheng et 2021)
Node & Edge
Q
Estimation
Image Classification
(Ai epoQGNN
st,, 2022)
Node Node
Q &
Tomography
Graph Classifcation
EQGC (Mernyci et 2022)
Estimation
Synthetic Cycle Graph Classilication
Ours
Node & Edge
Estimation
Graph Classification Rogression
the problem itself. This can prevent the model from overfitting the variable/constraint orders in the training data. However, a recent study (Chen et al., 2023) revealed that the classical GNNs based on the pessaag-passsing mechanism suffer fundamental limitations in graph representation, especially for MILP graphs, i.e., GNNs do not have sufficient power to distinguish some different instances. Specifically, as shown in Fig. 1, two different MILP instances can be eventually embedded into the identical representation by GNNs, thus failing to predict the feasibility of MILP. Moreover, in real-world scenarios, there are numerous MILPs that GNNs cannot distiguish (Chen et al., 2023), which means that practitioners using GNNs may not benefit from this.
As we can see, classical GNNs face fundamental limitations in learning graph representation. To overcome this challenge, we turn to quantum machine learning (QML), which is an emerging field that combines the power of quantum computing with the capabilities of machine learning. QML has shown immense potential in recent years, such as recognizing patterns that are intractable using classical methods (Biamonte et al., 2017). In this paper, we aim to associate nodes with qubits and edges with quantum entanglement, investigating graph structures that are indistinguishable from classical GNNs and exploring effective approaches for constructing quantum graph neural networks.
Designing a quantum learning framework for unstructured data, such as graph data, is still in its nascent stages. Although some quantum neural networks (Verdon et al., 2019; Zheng et al., 2021; Ai et al., 2022; Mernyei et al., 2022; Yan et al., 2023) designed to handle graph data have been proposed, they struggle to effectively apply to complex graph tasks such as MILP graphs because they fail to address the following challenges simultaneously. i) Since complex graph data usually contains node and edge features, it is important to design a reasonable node/edge feature encoding strategy that enables the quantum circuit to utilize these features to learn effective node representations.ii As mentioned carlier, classic GNNs possess the beneficial property of permutation equivariance. However, designing a quantum circuit that conforms to permutation equivariance is nontrivial and requires careful design. iii) Unlike building hybrid classical-quantum quantum layers, designing full quantum cireuits for classical graph data and verifying them in practical graph tasks is challenging. Moreover, we provide a detailed discussion of related works in Appendix A and Table here as a summary.
To tackle the above challenges, we propose general quantum graph learning architecture named GQGLA. This method aims to provide a quantum solution for complex graph tasks like learning MILP representation and demonstrate superior discriminative power over classical GNNs. The generality of GQGLA is reflected in the following five aspects. i) GQGLA can encode node and edge features. We design learnable features associated with each feature and flexible encoding schemes to better learn node representations. ii) With the proposed parameter-sharing strategy, all the layers in GQGLA possess the beneficial property of permutation equivariance, and we provide the theoretical proof in Sec. 4.3. iii) GQGLA can incorporate an optional auxiliary layer to enhance the expressive power of the model. iv) The types of quantum gates in GQGLA are adjustable under our configuration principle, allowing flexible use across different scenarios. v) By designing different measurement layers, GQGLA can be applied to graph tasks at various levels, such as graph classification, graph regression, and node property prediction. We summarize the main contributions:
1) To explore the potential of quantum machine learning for learning general quantum graph learning architecture (GQGLA). The method is based on fully quantum circuits compatible with current devices and is capable of effectively encoding the features of nodes and edges while ensuring node permutation equivariance. GQGLA can flexibly create different circuit
data, we present
2

---

Published as a conference paper at ICLR 2025
structures to meet various expressive requirements and downstream tasks. Moreover, we theoretically prove the permutation equivariance of GQGLA.
2) We implement GQGLA in an application for learning MILP representation, which is evaluated on three tasks: predicting feasibility, the optimal value, and the optimal solution. Numerical experiments demonstrate the advantage of GQGLA over classic GNNs in learning MILP representations. GQGLA has better discriminative power to handle GNN-intractable MILPs. also shows that GQGLA has better generalization and uses fewer parameters.
3) The superior discriminative power of GQGLA over GNNs not only provides a promising solution for more challenging graph tasks but also shows the practicability of current quantum machine learning methods. This will encourage further exploration of the potential of QNNs over their classical counterparts.
PRELIMINARIES
We provide the basics of quantum computing and quantum machine learning in simple and understandable way in Appendix B, ensuring that readers with a background in linear algebra but not familiar with quantum computing can gain a basic understanding of the quantum technologies used in our paper. The matrix forms of all quantum gates mentioned in the paper provided in Table 9. Next, we will introduce the specific form of MILP graphs and the types of MILP datasets.
2.1
MILP GRAPHS AND THE LIMITATION OF CLASSIC GNNS
Graph Representation for MILPs. An instance defined as follows A E R E CE
CE R
min c xr, s.t. Ax o b, 1 I S u, Ij E R ViET, ZER
(I)
where I and u represent the upper and lower
bounds on variables, where 1 E [R U { { E (R {+oo]])* and o E sistent with Chen et al. (2023), the mathe- matical operators {S, are mapped into numerical value {0, 2, respectively. I S {I..... 9) represents the index set of integer variables. The feasible solution is defined as
min
G + C282
Con-
s.t.
4 a us
A + A 4
E 0. otherwise
1 s x uz
A2rZ1 + AzzA2 ' by
f² (4,
fi (b,, 9))
f (2,
V2
1 (bz.
the set X Xfea = fo E RR Ar o b, 1 < S u, Hj Z, Vi E l}. while Xfea 0 means the MILP problem is infeasible. Fea- sible MILPs have an optimal objective value E X [eaa] If there exists f E Xee such that c à S C x. v. E Xyea then an optimal solution. Nevertheless, the optimal solution may not always exist because the op- timal objective value can be arbitrarily good, where the MILP problem is unbounded and categorized as feasible with an optimal objective value of -o. Following the protocol in Gasse et al. (2019) and
A weighted bipartite graph of a MILP instance. is the variable node associated with feature SV and 8j indicates the constraint node asso- ciated with feature S.S. The edge between v; and 8y means the j-th constraint involves the i-th variable.
Figure 2:
Yoby = inf
Chen et al. (2023), we formulate MILP as weighted bipartite graph to interpret variable-constraintt relationships, as illustrated in Fig. 2. The vertex set is VU S, where V (Ui,.... Vi. . with U, representing the i-th variable and S = {sI..... "J.-.. constraint. The edge connected is and 8 has weight Ar,-- Based on Eq. (1), the vertex &n e V is associated with a feature vector SV = (c,, 4, ui Ei), where e, E {0, represents whether variable i takes an integer value. The vertex sy is equipped with wwo-dimensional vector ff 9)). There is no edge between vertices in the same vertex set (V or S). The weighted bipartite graph with node features named an MII.Piinduced graph or MILP graph.
[sp} with s, representing the j-th
Classic GNNs may Fail on General MILPs. Recall that Chen et al. (2023) has shown that GNNs may embed two different (one feasible and one not) MILPs into an identical embedding. In fact, there are infinitely many pairs of MILP instances that can puzzle GNNs. Therefore, Chen et al. (2023) call this class of MILPs that confuse GNNs as foldable MILPs, while the rest of the MILPs are named unfoldable MILPs. In this paper, we refer to them as MILPs, respectively. Fig. gives an example of a pair of MILPs in the GNN intracctalle MILP dataset. In this case, S. (1,0, 1, 1), for all v2 V and 1 =), for all 8, S. All edge
MILPs and CNN-tractable
3

---

Published as a conference paper at ICLR 2025
Block (t
18]
Classical Optimizer
Feature
Node
Graph message interaction layer
Auxilary layer
Block
Block
X
layer
2)
T)
U2(HH,0
Ug (4
U,(r)
Update Parameters
180
X
Measurement
The overall architecture of our GQGLA. The node feature layer encodes and learns node features into the quantum circuit, and the graph message interaction layer contains a variable update layer and constraint update layer. The auxiliary layer optional and is used enhance the model's capacity. All layers are designed to preserve the equivariance of the node permutation.
Figure 3:
weights are equal to I, which means that the only difference between the two bipartite graphs lies in the connectivity of edges. However, these two MILP instances have different feasibility. Fig. (a) is feasible, e-g. x = (0, 1, 0, 1, 0, 1) is feasible solution, while Fig. (b) is infeasible as there are no integer decision variables that can satisfy the equality constraint 2 + 222 + 2z3) 3. Appendix E, illustrates why GNN has no ability to distinguish between them. The limitation of GNNs means that directly applying GNNs to represent general MILPs may fail.
GENERAL QUANTUM GRAPH LEARNING ARCHITECTURE
Fig. 3 shows the overall framework of GQGLA, which consists of the node feature layer, graph message interaction layer, auxiliary layer, and measurement layer. The first three layers form a block. After the block is iteratively repeated I times, Pauli-Z measurement is performed. This section introduces the design details of each layer in GQGLA using MILP graphs as an example. The next section presents how GQGLA can be applied various levels of graph tasks of MILP and demonstrates its permutation equivariance and discriminative power.
3.1 NODE FEATURE LAYER
Fig. 4 (a) exemplifies node feature layer with two variable nodes and two constraint nodes. The variable nodes v; have four features (ci, 1,,4,,4, G), and the constraint nodes sj have two features (by, oj). Suppose that each qubit encodes two features, as shown in Fig. 4 (c). Specifically, W(I) and D(0) represent two different types of single-qubit quantum gates, including {Rx(0), (0), Rz(0)} where 0 indicates the parameter of the gate. We can set 0 as either trainable parameters or con- stant to encoded. The selection principle of single-qubit quantum gates (W (0) and ((0)) will be described in Sec. 3.4. In this case, the first qubit encodes the features C₁ and 4, and the second qubit encodes the features un and é1. That is, the first two qubits are used represent the node 11. When fewer features are encoded on each qubit, more qubits are used to richer node representation. However, this also leads to increased model complexity, so we set w as a hyperparameter to denote the maximum number of features that each qubit can encode, balancing the speed and accuracy. Fig. shows the case where w 2, and we also provide another illustration of w in Fig. 8 in Appendix. Moreover, the same feature dimension (e.g., C₁ and 62) shares the identical trainable parameter (i.e., at,, i in the W(c + at,1) and W (c2 + 1t) In other words, the trainable parameters are related only the feature dimension, not to the permutation of the nodes. Thereby, even if the order of nodes changes (e.g., encoding node 0/2 using the first two qubits), each node's 's features assigned the same trainable parameters, ensuring that the learned node feature representation remains invariant. In this way, the node feature layer can preserve the node permutation equivariance, Sec. 4.3 for proof. The node feature layer encodes
(c) Node Feature Layer
(s)
[0]
[[G
D daa)
G,
M..
P1
[00]
W(u (xs)
D(e a.a)
(10)
W(c
( 0x.3)
(bu
100
Wi,,, + +())
D(e; + dca))
$1 10)
(b,
(1,, +
Sharing
Paramiterrs
Trainable
$2 (0)
W(0, + (iss)
D(s; +(a
(lr 0g(1,69.0)
Figure 4: Node features are encoded into the circuit using angle encoding, and each feature is associated with a trainable parameter to learn the node repre- sentation. For node permutation equivariance, the same feature dimension (e.g., C1 and (2) shares the identical trainable parameter (i.e., 02,1).
represent a node, resulting
4

---

Published as a conference paper at ICLR 2025
(a) Variable Update layer
(b) Constraint Udate layer
(d) Measurement layer
x
Yn
KiA Rtal
(c)
FiAcs Be.
X
FeAu-Rul Rud
Pul
Y4,
Kou Rus
KiAa Aol
600 A
X
MC (A.
(4,
050
Paui2
Figure 5: The quantum graph message interaction layer. (a) Variable update layer. Controlled-A K gates are used to learn the information interaction between variable nodes and constraint nodes, while controlled-G(A) gates are utilized to learn the internal interaction between qubits representing the same variable nodes. (b) Constraint update layer. Controlled- K gates are turned upside down and followed by G(0) gates to update the representation of constraint nodes. (c) Omitted node feature layers and graph message interaction layers. (d) Measurement layer using Pauli-Z measurement.
all variable features HV E RRxx and constraint features H E RPx2 can be defined as:
(,) (s, u, www.su...aaVbllee.o...
3.2 QUANTUM GRAPH MESSAGE INTERACTION LAYER
We employ two-qubit quantum gates to entangle the qubits representing two nodes connected by an edge. By harnessing the mechanism of quantum entanglement, we can learn the information interaction in MILP graphs. Fig. 5 exemplifies the graph message interaction layer for the MILP graph Fig. 4 (a), which contains three edges. Specifically, this layer includes two parts: the variable update layer and the constraint update layer. We set the two-qubit quantum gates as controlled- (()) E [Rx (0), Ry (0), R2 (0)}. In the variable update layer, the control qubit controlled- K (0) gate the constraint node, and its target qubit is the variable node. Different edges share an identical trainable parameter 3r as illustrated in the first three gates in Fig. (a). In this case, one variable node is represented by two qubits. Interestingly, the order of controlled-K gates can be arbitrary due to the character of bipartite graphs, i... whether the controlled- K (An + 3) or the controlled- K (A22 + 3) is applied first does not change the unitary of the UK layer. We refer to this property as edge permutation invariance. In the MILP graph, the edge feature is the edge weight, but GQGLA can also be applied cases with multi-dimensionll edge features, as illustrated Fig. 9 in the Appendix. Moreover, the controlled-G gate is applied to these two qubits to learn the interaction of internal information within one node, where controlled-G(O) E (CRx(0), CRy In the constraint update layer, the controlled-It gates are turned upside down and are followed by G()) gates to update the feature representation of constraint nodes. The selection principle of and G gates will be described in Sec. 3.4. The unitary of the 1-th graph message interaction layer can be represented by (A, 3x) = Uge (A, (e) ) Uge (A, Bt), with formulas shown in Eq. 10. We also provide simple and intuitive explanation in Appendix D.2.4. Furthermore, theoretically prove the node permutation invariance of this layer in Sec. 4.3.
(0)).
3.3 AUXILIARY LAYER
To further enhance the expressiveness the model, inspired by Wu et al. (2021), we introduce an optional auxiliary layer, which can facilitate the interaction of information within the graph. Speeifically, each auxiliary qubit connected to all other nodes through symmetric two-qubit gates Rzz(7). In this way, the model can increase the width and number of parameters. For the qubits representing one variable, trainable parameters "/,,1 and 7/ are assigned, while the parameter "r,3 is assigned the qubit representing constraints. The unitary of the auxiliary layer defined as Ua (1)). We can choose varying number of auxiliary qubits based on the requirements of different tasks. The node feature layer, graph message interaction layer, and auxiliary layer are regarded as block. After iterating this block I' times, the unitary matrix of the overall circuit is equal to
Ungt (A, H,) = II UH oz (A
(3)
where & contains all trainable parameters a, and
5

---

Published as a conference paper at ICLR 2025
3.4 CONFIGURATION PRINCIPLE OF GQGLA
In GQGLA, the quantum gates W(0), D(0), k(0), and G(0) are selected from {Rx (0), Ry (0), Rz (z)))) = (
), exp(- (xx(-i00=2]. where (a., By σ=) are Pauli matrices form basis for the real vector space of 2 x Hermitian matrices. {io,, lo y. 10, form basis for the real Lie algebra su(2), which exponentiates to the special unitary group (2))). When two quantum gates are adjacent in GQGLA, they are expected to be of different types. This enables the encoding of various features or trainable parameters on different bases, thereby enriching the information encoded in the circuit and preventing the quantum circuit from confusing different features. There are six possible configurations GQGLA, which are summarized Table 10.
GQGLA WITH APPLICATION TO MILP
As the application of GQGLA, predicting feasibility, optimal objective value, and optimal solution of MILP graphs can be regarded as the task of graph classification, graph regression, and node property prediction, respectively. As we can see, learning the MILP representation is sufficiently complex task that fully utilizes GQGLA, thereby comprehensively showcasing its capabilities.
4.1 MEASUREMENT LAYER
As shown in Fig. 5 (d), we add a measurement layer at the end of the quantum circuit. After the measurement operation, the quantum information can translated into classical information. In the measurement layer, we measure only the first qubit representing each node using Pauli-Z measurement. That is. for q variable nodes and p constraint nodes, GQGLA outputs q + p results. The output of the GQGLA is defined as (AA, H, θ) = {(0 ut where O₂ represents i-th observable. For predicting the feasibility and optimal value of MILP graphs, we define drea (A, H) Σ (A, H. θ fra)is Oatj [A, H) = 2+p
(A (A, H, g)) ( (A, H, (0) y==1
((A, H, Obb );- For )i 1=1 As can be seen, the three tasks use the same circuit structure of GQGLA but employ different trainable parameters and different ways to utilize the information obtained by measurements.
predicting the optimal solution, we define disal [A H) = ( A, H, S
4.2 TRAINING AND TESTING
For predicting the feasibility, Úsea = Óiea (A, H), we utilize the negative log-likelihood as the loss train GQGLA. In the testing, we set an indicator function 21/2
[0, ffaa S 1/2
U 1/2 = 1 Úfea > 1/2
to caleulate the error rate: 1, (EM Vfea Uy.. 1122); where M indicates the number of tested MILP instances, evaluate the number of correct predictions for feasibility.
For predicting the optimal solutions, Dsol Adsa((,, A, H). where À is the maximum range of variables of the training sample, i.e., max ((abb(()). abb)) (b 1 We use the mean square error as the training and testing metric: Mī. Σm ||ysst 1 Ilg. where yoa is the ground truth.
For predicting the optimal values, Kobjj SAponi (A, H), where å max((1 is the maximum range of coefficients of training sample. We also use the mean square error to train or evaluate, i.e, 1 EM-1 (Wt) Voby) )
M
4.3 PERMUTATION EQUIVARIANCE AND INVARIANCE
Permutation equivariance and invariance are fundamental requirements for graph neural networks. In this section, we will demonstrate that the proposed quantum graph learning architecture possesses these desirable properties. Let G (A, (A, H²) represent MILP graph with g variable nodes and p constraint nodes. 7g and म. are the permutations of variable nodes and constraint nodes, respectively. Ag E B and A, E BPxP are permutation matrices representing permutation Ty and up. respectively. Additionally, we define a permutation kptp on the (q + p) elements to indicate the overall permutation on all nodes of the MILP graph. Agtp is the permutation matrix of the

---

Published as a conference paper at ICLR 2025
permutation Tetz- A is the unitary representation of Tp which indicates the permutation of qubits representing nodes. Based on this, we give the definition of a permutation equivariant circuit.
Defintion 1. (Permutation Equivariant Circuit). A parameterized quantum circuil U is permutation equivariant for MILP graphs (A, H" HH) if satisfies
UA AgH 9) = -U, 0) H)
(5)
where Ag and Ap are the permutation matrices for permutation Th E S" and Tp E S", respectively. A E TB22 x2" is the unitary of permutation "qtp"
Appendix D.I provides the formulation and detailed explanation of Definition 1. After measuring the quantum circuit, we can consider the model to be a mapping ø E Rotp, According to Definition 1, we can obtain the permutation equivariance of the mapping.
Defintion 2. (Permutation Equivariant Mapping). A mapping 6(-) E R9-P is permutation equivariant for MILP graphs (A, H1 IIn) it satisfies
((ppAAg Ay Aptt") Agto M(A, H", H³),
(6)
where Aqtp is the permutation matrix representing the permutation Tg+p. i.e., [Ag E (Bltt))x((tt))
Aqtp
Ap
It indicates that the mapping result after node permutation 6(A,.AA,, A,H") is equal to the result of applying the permutation Typp to the original result A, HÝ, H²). In addition, result of the permutation equivariant mapping as a value to obtain the other mapping k E The mapping is permutation invariant if changing the order of inputs does not alter the mapping output.
aggregate the
Defintion (Permutation Invariant Mapping). A mapping x(-) E R. is permutation invariant for MILP graphs if it satisfies
A(ApAAg AqH ArHt) HV H²).
Theorem 1. In the proposed GQGLA, the circuit U Upegg! ( (A,H,, H., ②) is permutation equiv- ariant circuit. After Pauli-Z Z measurement, the output of the circuit (AA, H, aoo) = @ (A, H) is permutation equivariant mapping. (Aa H) = >it ( , θ fea); and @ayy H)
Ettp (AA, H, Oobs); ; are permutation invariant mapping.
Appendix D.2 provides detailed proof of Theorem offering theoretical guarantees of permutation cquivariance and invariance for our proposed GQGLA.
4.4 SUPERIOR DISCRIMINATIVE POWER OVER GNNS
As mentioned earlier, Chen et al. (2023) have shown that GNNs may fail to distinguish two MILP graphs, which is because of the fundamental limitations of GNNs. Xu al. (2018) have shown that GNNs are at most as powerful as the Weisfeiler-LLhmaal (WL) test (Weisfeiler & Leman, 1968) in distinguishing graph structures. However, as the WL test iteratively updates the label of vertices in a graph only based on the label of their neighboring vertices, if two graphs exhibit subtle structural differences not reflected in the degree of vertices or the patterns of local neighbors, the WL test will fail to distinguish between these two graphs, as shown in Fig. 1. See Appendix E. for a detailed explanation of why GNN fails on the MILPs. By contrast, benefiting from quantum entanglement between nodes, GQGLA can capture the difference in edge connectivity between two MILP graphs. Different edges result in variations graph-message interaction layer Uk. i.e., exp( -ii (ia)e AI P.),Pk ))) We give the detailed proof in Appendix E.2.
EXPERIMENTS
In the experimental section, compare the performance between classical GNNs and quantum machine learning algorithms on the learning representation of MILP graphs. The construction the MILP dataset is in line with Chen et al. (2023) (see details in Appendix G). We use Adam (Kingma &
7

---

Published as a conference paper at ICLR 2025
Table 2: Performance Comparison on the GNN-tractable MILP dataset.
Feasibility (Ratc of Erex 11/10-2
Optimal Value (MSE 1) /10-2
Optinnal Solution (MSF 4) /10-1
MIL MILP-GNN
K.Sine
8
24
(Chenn of al., 20123)
Train
6.72 = 0.17
5.424 0.21
4,29 0.12
1.52% 0.4
1.122 0.6
0.662 Dos
7.54 0.11
6.39 0.t6
5,47:: 0.15
Test
7.66 0.19
6,744
0.00
5,02 0.11
2.35 0.07
1.4 0.05
1.76 0.04
8.22 0.7
7.574 0.11
6.31 0.5
GOGLA
Train
7:22 D.11
6,55+ 0.13
5,57= 0.08
110+ 0.44
1.0+ 0.22
0.98+ 001
6.30= 0.14
5.79+ 0.10
5.70+ am
Test
734 102
6.65+
5.74=
1,26
1133 0.0
111+
6,37= 0.11
6.03+
5,99 ou0
Ba, 2014) with an initial learning rate of 0.1 to find the optimal parameters of GQGLA, and batch size single machine with 4 2.20GHz CPUs and four NVIDIA A100 GPU. The source code is written using Torch NorchQuantum (Wang et al., 2022a), a PyTorch-based library for quantum computing, which can simulate quantum circuits with up to 26 qubits. In Table 10 of Appendix F. the performance of all possible types of GQGLA are compared, and we finally select (W()), ((0), (0), G(0)) = (Rx (0), R2 (0), Ry (8), Rz (0)) for the following experiments.
is set at 16. Experiments are performed
5.1 COMPARISON WITH CLASSICAL GNNS
We first compare the GNN used in Chen et al. (2023) named MILP-GNN as it is designed for MILP. Our GQGLA model has a hyperparameter to control the number of circuit parameters, i.e., the number of blocks T. MILP-GNN also has a hyperparameter embedding size d controlling the number of parameters. We vary these two hyperparameters separately for evaluation.
Experiments on -NN-intractable MILP Dataset. GNN-intractable MILPs contain many pairs of WL indistinguishable graphs that cannot be distinguished by classic GNNs (Chen et al., 2023). Here, we randomly generate 2, 000 GNN- inttaatteeeeb MILPs with 12 variables and 6 constraints, and there are 1, 0000 feasible MILPs while the others are infeasible. The error rate serves as the evaluation criterion for predicting the feasibility of GNN-intractable MILPs. We compare our GQGLA with the classical GNNs, i.e., MILP-GNT (Chen et al., 2023) and MILP-GNN with random features. MILP-GNN with random features is proposed by Chen et al. (2023) to alleviate the limitations of the original GNN by appending random features to the MILP graphs. As shown in Fig. 6, the error rate of MILP-GNN is highest regardless of the embed- ding size, as it cannot distinguish GNN-intractable MILPs. Although MILP-GNI with random features can improve performance, it achieves the best when the embedding size 32, which will cost 30, 565 parameters. Moreover, adding random features may cause additional issues, i.e., changing the feasibility or solution of the original problem, resulting in the change of ground truth of the dataset. In contrast, GQGLA can capture the edge connectivity of GNN- intractable MILPs, so it can achieve accurate test results with just 4 blocks, i.e., 48 parameters. The results show that GQGLA has better discriminative power than GNNs with fewer parameters.
Embedking GNN
16
0.5
GNN (trin & best)
Rond. (train)
of Fror
GNN RRnd Feel Desi)
O (train)
Ours (lest)
0.01
Block Number of Ours
Figure 6: Comparison on GNN-intractable MILPs. GNN refers to MILP-GNN (Chen et al., 2023), and GNN + Rand. feat. indicates the MILP- GNN with random features.
Experiments on GNN-tractable MILP Dataset. We further compare our GQGLA and MILP-GNN on the GNN-tractable MILPs that GNNs can distinguish. We randomly generate 8, 290 GrN-tractable MILPs with four variables and four constraints. with feasible and infeasible MILPs each accounting for half. The experiments evaluate the rate of error in predicting the feasibility and the mean squared error (MSE) of predicting optimal values and optimal solutions of MILPs. As reported in Table 2, as the embedding size increases, the training error of MILP--NN decreases, but its generalization error on the test set increases. The reason is that GNN-tractable datasets are challenging, with diverse training and test sets, making it difficult for P-NN to generalize well on the test set. In contrast, our GQGLA benefits from quantum mechanisms, leading to better generalization performance.
Comparison with Advanced GNNs We utilize the PyG (PyTorch Geometric) library to extend more GNN models into frameworks suitable for MILP graphs. We modify each GNN to update
8

---

Published as a conference paper at ICLR 2025
Table 4: Comparison between different quantum models predicting the fcasibility of MILPs.
Table 5: Performance changes as the num- ber of auxiliary qubits increases on predict- ing optimal solution.
HEA
QGCN
GQGLA (ours)
(Kandala al., 2017)
(Zheng ol., 2021)
Aux. qubits
2
3
Train Test
0,4613+ 0004
0.3419: 0.155
0,1066: 0.008
Train Test
0.6580
0.6166
0.5694
0.6099
0.4665 0.200
0,3475 0.018
0.1127:: 0.012
0,6853
0.6410
0.5993
0.6354
variable nodes and constraint nodes using different weights. Table 3 compares our methods with GAT (Graph Attention Network) (Veličković et al., 2018), GATv2 (Brody et al., 2022), and Graph Transformer (Shi et al., 2021), w.r. the accuracy of feasibility prediction on GNN-intractable and GNN-tractable datasets. As we can see, in the GNN-tractable dataset, our method remains competitive with advanced GNNs, achieving nearly the best results, and advanced GNNs still struggle with GNN- intractable datasets, whereas our model is more effective.
5.2 COMPARISON WITH OTHER QUANTUM ALGORITHMS
Recall in Table that most quantum GNNs have not considered edge features, which yet are vital for solving MILP. Therefore, we only compare QGNNs that consider edge features, e.g. the quan- tum graph CNN (QGCN) (Zheng et al., 2021). We also compare problem-agnostic, hardware- efficient ansatz (HEA) (Kandala et al., 2017). The circuit structure of HEA is typically fixed, mak- ing it unable to encode the edge information of a graph. yet can encode the node feature informa- tion of the graph. Table reports the error rates on MILP dataset with three vari- ables and three constraints. In this MILP dataset, QGCN requires more qubits to compute than GQGLA. Moreover, we set the number of parameters for all quantum models to 96. The results show that the problem-agnostic ansatz cannot effectively learn from graph data. Although QGCN is a mroblem-inspiree ansatz and designs an equivariant graph convolution layer, their pooling layers violate permutation invariance, leading to performance degradation in predicting MILP feasibility. By contrast, GQGLA ensures permutation invariance with better performance.
Table 3: Comparison of GQGLA and other GNNs on dataset.
the GNN-intractade and
Emhedding Size!
Blocks
GAT
0.856
0.926
GNN-tractable dataset
GATV2
0.914
0.927
0.96
0.943
Graph Transformer
0.875
0.914
0,920
0,930
MILP-GNN
0.872
0.910
GQGLA
0.933
0.936
0.912
0.916
GAT
0,500
0.500
0.500
0,500
..N-inttaccuble
GATv2
0,500
0.500
0.500
0,500
Graph Transformer
0.500
0.500
the
dataset
MILP-GNN
0.500
0,500
0.500
0.500
GQGLA
0.987
0.998 1.000 1.000
5.3 ABLATION STUDY
Table 5 investigates the contribution of auxiliary layers to GQGLA, which shows the perfor- mance of GQGLA in predicting the optimal solution with an increasing number of auxiliary qubits. The results indicate that increasing the number of auxiliary qubits can enhance per- formance, yet there may exist an optimal threshold for a specific problem scale. We can select appropriate auxiliary qubits to enhance performance for tasks of different complexity. Furthermore, we delve into the individual compo- nents that shape GQGLA's design, as shown Ta- ble 6. Repeated encoding refers to encoding features at every block. Synchronous encoding and learning refers to adding features and learnable parameters as new learnable parameters. Double interaction refers using a constraint and variable layer in the graph message interaction layer. All configurations employ the same number of parameters. Results indicate that these three components are useful.
Table 6: Ablation study w.n. our components.
Repeated Encoding
Syn. Encoding Learning
Double Interaction
Train
Test
x
X
x
0.0924
0.0953
X
0.0876
0.0898
X
0.0708
0.0726
0.0738
0.0765
V
0.0623
0.0659
0.0557
0.0574
5.4 COMPARISON WITH HIGHER ORDER GNNS
We conducted experiments on BREC (Wang & Zhang, 2024) to evaluate expressiveness, com- pared to higher order GNNs, including subgraph- based methods NGNN (Zhang & Li, 2021), DS-GNN (Bevilacqua et al., 2022) and KP-GNN (Feng et al., 2022), k-WL hierarchy- models å-k-LGNN (Morris et al., 2020) and PPGN (Maron et al., 2019), random model DropGNN (Papp et al., 2021), Transformer-based model Graphormer (Ying et al., 2021), and substructure- based model GSN (Bouritsas et al., 2022). The Basic dataset in BREC consists of

---

Published as a conference paper at ICLR 2025
1- WWL-indistinguishall graphs generated through exhaustive search and is designed to be non-regular. The Regular dataset con- tains regular graphs, further divided into simple regular graphs and strongly regular graphs, where 1-WL and 3-WL test fail, respectively. Including 4-vertex condition graphs and distance-regular graphs further increases the dataset's complexity. The Ex- lension graphs bridge the gap between 1-WL and 3-WL., offering more granular comparison for evaluating models beyond I-WL. We employ Reliable Paired Comparison (RPC) (Wang & Zhang, 2024) to verify if GNNs can produce distinet outputs for a pair of graphs. Table 7 shows that the proposed GQGLA not only achieves good performance on the Basic and Extension datasets but also outperforms other classical methods on the challenging Regular dataset.
Table 7: Performance comparison of GNNs on BREC.
Method
Basic
Regular
Extension
NGNN (Zhang & Li, 2021)
0.983
0.343
0.59
DS-GNN (Bevilaqqua al., 2022)
0.967
0.343
1.0
KP-GNN (Fong et ol,, 2022)
1.0
0.757
0,98
6-K-LGNN (Momis et al, 2020)
1.0
0.357
1.0
PPON (Maron al.,, 2019)
0.357
1.0
DropCINN (Papp et al., 2021>
0.867
0.293
0,820
Graphormer (Ying, al., 2021)
0,267
0.086
GSN (Bounitsas et al, 2022)
1.0
0.207
0.95
Ours
1.0
0.964
1.0
6 THE COMPLEXITY AND SCALABILITY OF GQGLA
For graph with N nodes and E edges, the node feature encoding layer involves O(N) qubits and O(N) single-qubit gates, while the graph message interaction layer introduces (EE) two-qubit gates. For a circuit with T blocks, the total number of gates scales as O + E)). However, in the current. NISQ era, both real quantum devices and classical simulators have limited number of qubits. Therefore, inspired by how classical GNN algorithms handle large graph computations with limited resources, we have presented S- S-GQGLA to process large graphs with limited qubits. Specifically, we first employ the graph sampling technique GraphSAINT (Zeng et al., 2020) to extract appropriately connected subgraphs, then apply our GQGLA model these subgraphs and combine the obtained information of these subgraphs together so that the training process overall learns information of the full graph. In this way, for graph with N nodes, we can sample subgraphs for training, with each subgraph using at most & qubits.
Table shows the performance of GQGLAA on three commonly used graph classification datasets, PRO- TEINS and PTC. Among them, the number of nodes is up to 620 at most. We extract appropriately connected subgraphs with at most 14 nodes, which can be pro- cessed using qu-qubit GQGLA with 6 blocks. All subgraphs are input as a batch into the GQGLA, and we combine their results to predict the classification of the full graph. We compare S S-GQGLA with message- passing based GNNs GraphSAGE (Hamilton et al., 2017), GIN (Xu et al., 2018), and GAT (Veličković al., 2018), subgraph-base based methods PPGN (Maron et all,, 2019), QS-CNN (Zhang et al., 2019) and Deep- WL-SGN (Xuan et al., 2019), and Transformer-basee methods SEG-BERT (Zhang, 2020) and U2GNN (Nguyen et al., 2022a). S-GQGLA can achieve the best performance on PROTEINS, and slightly worse than U2GNN and SEG-BERT on PTC.
Table 8: Accuracy comparison of S-GQGLA on three graph classification datasets.
Methods
PROTEINS
PTC
GraphSAGE
25,9
7.7
GIN
76.20 2
64.6
GAT
74.70
6.1
PPGN
7.666
6.66
QS-CNN
4.6
66.0 4.4
Deep-WL-SGA
2.4
65.88 5.1
U2GNN
78.53
69.63 3,6
SEG-BERT
77.20 3.1
68.86 4.2
S-GQGLA (Ours)
91.64 3.1
68.57
2.9
7 CONCLUSION
This paper introduces an expressive quantum graph learning framework aimed at addressing complex graph structural data, such as learning the MILP graph representation. Our proposed framework. GQGLA, uses the synchronous encoding and learning module to handle node and edge features, and presents a parameter-sharee
mechanism and a carefully designed graph information interaction layer. We theoretically prove that GQGLA possesses permutation equivariance and invariance for nodes and edges. Moreover, the proposed graph information interaction layer leverages quantum entanglement to model the edges, enabling the capture of graph patterns that are challenging for classical methods. Numerical experiments demonstrate that our approach can overcome the fundamental limitations of traditional GNNs, achieving superior performance on MILP tasks that include GNN-intractall graphs. GQGLA also offers flexibility in configuration for general graphs, and the results of the BREC dataset highlight the generality and separating power of GQGLA.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Xing Ai, Zhihong Zhang, Luzhe Sun, Junchi Yan, and Edwin Hancock. Towards quantum graph neural networks:an ego-graph learning approach. arXiv preprint arXiv:2201.08 100020000055,,,.. 15, 2022.
Hooman Askari-Nasab, Y Pourrahimian, E Ben-Awuah, and S Kalantari. Mixed integer linear programming formulations for open pit production scheduling. Journal of Mining Science, 47:
2011.
Tinyyi Bao, Qitian Wu, Zetian Jiang, Yiting Chen, Jiawei Sun, and Junchi Yan. Graph out-of- distribution detection goes neighborhood shaping. In Forty-first International Conference Machine Learning, 2024.
Tianyi Bao, Xinyu Ye, Hang Ruan, Chang Liu, Wenjie Wu, and Junchi Yan. Beyond circuit connections: A non-message passing graph transformer approach for quantum error mitigation. In The Thirteenth International Conference on Learning Representations, 2025.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representutions, 2022.
Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning, Nature, (:: 2017.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Pattern Analysis and Machine Intelligence, 45( 45(1):657-668, 2022.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Proceedings of the International Conference on Learning Representations, 2022.
Ziang Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. On representing mixed-integer linear programs by graph neural networks. In Proceedings of the International Conference on Learning Representations, 2023.
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. Advances Neural Information Processing Systems, 35: 4776-4790, 2022.
Christodoulos A. Floudas and Xiaoxia Lin. Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Annals of Operations Research, 139(1):131162,, Oct 2005a. ISSN 1572-9338.
Christodoulos A Floudas and Xiaoxia Lin. Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Annals of Operations Research, 139:131-162, 2005b.
Bernard Fortz and Michael Poss. An improved benders decomposition applied to a multi-layer network design problem. Operations research letters, 37(5)3359-364, 2009.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi, Exact combi- natorial optimization with graph convolutional neural networks. Proceedings of the Advances in Neural Information Processing Systems, 32, 2019.
Xueshi Guo, Casper R Breum, Johannes Borregaard, Shuro Izumi, Mikkel V Larsen, Tobias Gehring, Matthias Christandl, Jonas S Neergaard-Nielsse and Ulrik L Andersen. Distributed quantum sensing in continuous-variin variable entangled network. Nature Physics, (6(3):281-284 2020.
Prateck Gupta, Elias B Khalil, Didier Chetélat, Maxime Gasse, Yoshua Bengio, Andrea Lodi, and M Pawan Kumar. Lookback for learning to branch. arXiv preprint arXiv:2206. 14966,1447..... 2022.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs.
Advances in neural information processing systems, 30, 2017.

---

Published as a conference paper at ICLR 2025
Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D Nation, Lev Bishop, Andrew W Cross, et al. Quantum computing 2024.
with qiskit. arXiv preprint arXiv:2405.0888
Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549(7671):242-2444 sep 2017.
Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 10219-10227, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Martin Larocca, Frédéric Sauvage, Faris M Sbahi, Guillaume Verdon, Patrick Coles, and Marco
Cerezo. Group-invariant quantum machine learning. PRX Quantum, 3(3):030341, 2022.
Junde Li and Swaroop Ghosh. Scalable variational quantum circuits for autoencoder-basel drug discovery. In 2022 design, automation & test in europe conference & exhibition, pp. 340-345. IEEE, 2022.
Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and strong SIGKDD Conference on Knowledge Discovery and Data Mining, 2023a.
baseline. In Proceedings of the 29th ACM
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023b.
From distribution learning in training
Yang Li, Jinpei Guo, Runzhong Wang. Hongyuan Zha, and Junchi Yan. Fast 12t: Optimization consistency speeds up diffusion- based training-to-testie to-tesiingg solving for combinatorial optimization. Advances in Neural Information Processing Systems, 2024.
Yang Li, Jiale Ma, Wenzheng Pan, Runzhong Wang. Haoyu Geng, Nianzu Yang, and Junchi Yan. M14tspbench: Drawing methodological principles for tsp and beyond from streamlined design space of learning and search. International Conference on Learning Representations, 2025.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Jarrod R McClean, Sergio Boixo, Vadim Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature communications, 91)::8812, 2018.
Péter Memyei, Konstantinos Meichanetzidis, and Ismail Ilkan Ceylan. Equivariant quantum graph circuits. In Proceedings of the International Conference on Machine Learning, pp. 15401-15420.
PMLR, 2022.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33: 21824-21840, 2020.
Dai Quoc Nguyen, Tu Dinh Nguyen, and Dinh Phung. Universal graph transformer self-attention networks. In Companion Proceedings of the Web Conference 2022, pp. 193-196, 2022a.
Quynh T Nguyen, Louis Schatzki, Paolo Braccia, Michael Ragone, Patrick J Coles, Frederic Sauvage, Martin Larocca, and M Cerezo. Theory for equivariant quantum neural networks. arXiv preprint arXiv:2210.08566. 2022b.
Joaquín Ossorio, Castillo and F Pena, Brage. Optimization of a refinery scheduling process with column generation and a quantum annealer. Optimization and Engineering, 23(3):1471-1488 2022.
12

---

Published as a conference paper at ICLR 2025
Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 34:21997-22009 2021.
Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man- Hun-Hong Yung, Xiao- Qi Zhou, Peter Love, Alán Aspuru-Guzik, and Jeremy I. O'brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1 (11):4213, 2014.
Michael Ragone, Paolo Braccia, Quynh T Nguyen, Louis Schatzki, Patrick J Coles, Frederic Sauvage, Martin Larocca, and M Cerezo. Representation theory for geometric quantum machine learning. arXiv preprint orXiv:2210.07980, 2022.
A. Richards and J.P. How. Aircraft trajectory planning with collision avoidance using mixed integer linear programming, In Proceedings of the American Control Conference, volume 3, pp. 1936-1941 vol.3, 2002.
Louis Schatzki, Martin Larocca, Frederic Sauvage, and Marco Cerezo. Theoretical guarantees for permutation-equiiarian quantum neural networks. arXiv preprint wwXiv:2210.0999) 2022.
Tom Schouwenaars, Bart De Moor, Eric Feron, and Jonathan How. Mixed integer programming for multi-vehicle path planning. In 2001 European control conference (ECC), pp. 2603-2608. IEEE, 2001.
Yunsheng Shi, Zhengjie Huang. Shikun Feng. Hui Zhong, Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. In Proceedings of the International Joint Conference Artificial Intelligence, 2021.
Kristan Temme, Sergey Bravyi, and Jay M Gambetta. Error mitigation for short-depth quantum circuits. Physical review letters, 1 (19(18): 18:5809 2017.
Ewout Van Den Berg, Zlatko Minev, and Kristan Temme. Model-free readout-error mitigation for quantum expectation values. Physical Review A, 105(3):032620, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua
Bengio. Graph attention networks. In Proceedings of the International Conference on Learning Representations, 2018.
Guillaume Verdon, Trevor McCourt, Enxhell Luzhnica, Vikash Singh, Stefan Leichenauer, and Jack Hidary. Quantum graph neural networks. arXiv preprint 1rXiv:1909..2220 2019.
Hanrui Wang, Yongshan Ding, Jiaqi Gu, Yujun Lin, David Z Pan, Frederic T Chong, and Song Han. Quantumnas: doise-adaptive search for robust quantum circuits. In Herfo-Pefoorancc Computer Architecture, pp. 692-708. 2022a.
Hao Wang, Yu Pan, and Wei Cui. Quantum-inspired solvers on mixed-intege linear programming problem. Proceedings of the Chinese Control Conference, pp. 5693-5698. IEEE, 2022b.
Rui Wang, Zhiming Zhou, Tao Zhang, Ling Wang. Xin Xu, Xiangke Liao, and Kaiwen Li. Learning to branch in combinatorial optimization with graph pointer networks, 2023.
Yanbo Wang and Muhan Zhang- An empirical study of realized gnn expressiveness. In Forty-first International Conference on Machine Learning, 2024.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein.
Informatsia, 2(9):12-16, 1968.
Huaijin Wu, Xinyu Ye, and Junchi Yan. Qvae-mole: The quantum vae with spherical latent vari- able learning for 3-d molecule generation. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024a.
Yadong Wu, Juan Yao, Pengfei Zhang, and Hui Zhai. Expressivity of quantum neural networks. Physical Review Research, 3(3):1033209, 2021.
13

---

Published as a conference paper at ICLR 2025
Yongliang Wu, Xinting Hu, Yuyang Sun, Yizhou Zhou, Wenbo Zhu, Fengyun Rao, Bernt Schicle, and Xu Yang. Number it: Temporal grounding videos like flipping manga. arXiv preprint arXiv:2411.10332, 2024b.
Yongliang Wu, Shiji Zhou, Mingzhuo Yang, Lianzhe Wang. Wenbo Zhu, Heng Chang, Xiao Zhou, and Xu Yang. Unlearning concepts in diffusion model via concept domain correction and concept preserving gradient. In AAAI Conference on Artificial Intelligence, 2025a.
Yongliang Wu, Wenbo Zhu, Jiawang Cao, Yi Lu, Bozheng Li, Weiheng Chi, Zihan Qiu, Lirian Su, Haolin Zheng, Jay Wu, et al. Video repurposing from user generated content: A large-scale dataset and benchmark. AAAI Conference on Artificial Intelligence, 2025b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? Proceedings of the International Conference on Learning Representations, 2018.
Qi Xuan, Jinhuan Wang, Minghao Zhao, Junkun Yuan, Chenbo Fu, Zhongyuan Ruan, and Guanrong Chen. Subgraph networks with application to structural feature space expansion. IEEE Transactions on Knowledge and Data Engineering, 33(6):2776-778) -7899, 2019.
Ge Yan, Huaijin Wu, and Junchi Yan. Quantum 3d graph learning with applications to molecule embedding. In International Conference Machine Learning, pp. 39126-33137) PMLR, 2023.
Xu Yang. Yongliang Wu, Mingzhuo Yang, Haokun Chen, and Xin Geng. Exploring diverse in-context configurations for image captioning. In Advances in Neural Information Processing Systems, 2025.
Xinyu Ye, Ge Yan, and Junchi Yan. Towards quantum machine learning for constrained combinatorial optimization: quantum qap solver. In Proceedings of the International Conference on Machine Learning), 2023a.
Xinyu Ye, Ge Yan, and Junchi Yan. Vqne: Variational quantum network embedding with application to network alignment. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.
2023b.
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888. 2021.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020.
Jiawei Zhang. Segmented graph-bert bert for graph instance modeling. arXiv preprint arXiv:2002.03283. 2020.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34:15744-15747, 2021.
Zhihong Zhang, Dongdong Chen, Jianjia Wang, Lu Bai, and Edwin R Hancock. Quantum- -ased subgraph convolutional neural networks. Pattern Recognition, 88:38-49, 2019.
Zhongqi Zhao, Lei Fan, and Zhu Han. Hybrid quantum benders' decomposition for mixed-integer linear programming, In IEEE Wireless Communications and Networking Conference (WCNC), pp. 2536-2540. IEEE, 2022.
Jin Zheng, Qing Gao, and Yanxuan Lüi Quantum graph convolutional neural networks, In Proceedings of the Chinese Control Conference, pp. 6335-6340. IEEE, 2021.
14

---

Published as a conference paper at ICLR 2025
A RELATED WORK
Quantum Graph Neural Networks Various quantum graph neural networks have been proposed, with applications in fields such as social networks (Ye et al., 2023b) and molecular generation (Li & Ghosh, 2022; Wu et al., 2024a; Yang et al., 2025). Verdon et al. (2019) proposed a class of graph neural networks by defining operations in terms of Hamiltonians based on the graph structure. However, their models are restricted to Hamiltonians of specific forms, thereby cannot flexibly and efficiently encode classical high-dimensional node or edge features of the graphs to solve some classical tasks. Zheng et al. (2021) designed a specific quantum graph convolutional neural network (QGCN), which uses an amplitude encoding method to encode node and edge features and employs qubits representing edges as control qubits to apply unitaries to the two qubits representing nodes connected by that edge. Nevertheless, the usage of edge qubits will lead the number of qubits of the model scales quadratically with the number of nodes. Moreover, the pooling layer and measurement operator of QGCN will indeed result in the loss of permutation invariance of the entire model. Ai et al. (2022) presented an ego-graph based Quantum Graph Neural Network (egoQGNN), which decomposes the input graph into smaller-scale subgraphs and feeds them into the circuit. However, due to the use of entanglement layers within the model, it still does not possess permutation invariance.
Equivariant Quantum Neural Networks Recently, a nascent field named geometric quantum machine learning (GQML) (Larocca et al., 2022; Nguyen et al., 2022b) has been developed, which leverages the machinery of group and representation theory (Ragone et al., 2022) to build quantum architectures that encode symmetry information about the problem. Schatzki et al. (2022) provide an analytical study of Sn -qqiivariant QNNs and prove that they do not suffer from barren plateaus, quickly reach overparametrization, and can generalize well from small amounts of data. The equivariant QNNs can used to learn various problems with permutation symmetries abound, such as molecular systems, condensed matter systems, and distributed quantum sensors (Peruzzo et al., 2014; Guo al., 2020; Wu et al., 2024b), namely, they are also not specifically designed to solve classical graph tasks. Mernyei et al. (2022) first proposed a theoretical recipe for building permutation equivariant quantum graph circuits (EQGC) and aggregated the output of the quantum circuit by classical functions to ensure permutation invariance of the model. Nevertheless, the EQGC does not provide the specific circuit implementation and does not consider the case of weighted graphs in their model. In addition. another QNN with permutation equivariance Ye et al. (2023a) is proposed, which specially designed for solving quadratic assignment problems, but their model only encodes the graph information and then employs the shared problem-agnostic ansatz to learn the representation of each node. Thus, their model does not contain the learnable graph message interaction layer.
Quantum Algorithms for MILP Mixed-Intege Linear Programming (MILP) is mathematical optimization approach that aims to find the best solution to a linear objective function while imposing constraints on some all of the variables to be integers. MILP is widely used in various practical applications such as process scheduling (Floudas & Lin, 2005a; Li et al., 2023b; 2024; Wu et al., 2025b), transportation (Richards& & How, 2002; Wu et al., 2025a; Bao et al., 2024; 2025), and network design (Fortz&& & Poss, 2009; Li et al., 2023a). Recently, researchers have endeavored to employ quantum computing to assist in solving the MILP. Zhao et al. (2022) proposed hybrid quantum- classical Benders' decomposition algorithm, which decomposes an MILP problem into a Quadratic unconstrained binary optimization (QUBO) problem solved by quantum computer and a subproblem easily tackled by classical computers. Ossorio & Pena (2022) described an algorithm based on Dantzig- Wolfe decomposition. Different from Zhao et al. (2022). the algorithm then solves several either continuous or binary subproblems instead of a mixed one. Wang et al. (2022b) pointed out that quantum-inspired Ising machines can be used to solve MILPs by reducing them into Ising models. However, the above algorithms are based unconstrained Ising models, while MILPs are subject to complex constraints. Their common solution is to introduce a penalty to the algorithm. A proper penalty is of great importance because extremely large penalty may cause the quantum annealer to malfunction since will explode the coefficients, while a soft penalty may make the quantum annealer ignore the corresponding constraints (Zhao al., 2022). However, there is no instruction on how to tune the penalty, and it may even be different for various MILP problems. In contrast, our approach leverages QML to represent MILP problems, thereby pioneering a novel direction for harnessing quantum computing in aiding MILP solutions, there is promising for witnessing the emergence of new paradigms that combine quantum and classical methods for MILP solving.
15

---

Published as a conference paper at ICLR 2025
B THE BASICS OF QUANTUM COMPUTING
Single-qubit Quantum State. In quantum computing, the fundamental building blocks of compu- tation are qubits (short for quantum bits), which are the quantum analog of classical bits. Unlike classical bits, which can only take on one of two possible values (0 or 1), a qubit can exist in superposition of the two states, represented by the vector:
[v) = =1]0) + [1]]),,
(7)
where [0] and [1]represent the two basis states of one qubit, and aj and ag are complex numbers that satisfy the normalization condition |a1|² |az 12 1. When (e) is measured, it will collapse to either the (0) or (1) state with a probability |a,|² or |a2|
Mathematically, the quantum state of one qubit can be denoted as a complex 2-dimensional vector, e.g.. (0) = [1, 0)", [1) = [0. 1)", and (ıš) [01, 02)"" The Bloch sphere is sphere of radius 1, which is a useful tool for visualizing the state
single qubit. Any other state of one qubit can be represented by point the surface of the sphere, and you can see them through this online tool ?
Multi-qubit Quantum State. Multi-qubit quantum states are an extension of single-qubit quantum states, and a N --qubit quantum state can be represented as complex 2% -dimensional vector in Hilbert space. This is why quantum systems are often described as living in a 2 -dimensional Hilbert space. More specifically, two-qubit system can be represented as (Φ) .i (00) +az + 10) + +as (11),
where E a =
1 and (00) represent the tensor product (0) @ (0).
Quantum Circuits. Quantum circuits are constructed using quantum gates, which are analogous to classical logic gates. Some commonly used single-qubit gates include the Pauli-X gate, the Pauli-Y gate, and the Pauli-Z gate. They can be represented by the unitary matrix:
0 - . ....0-()).--
00 Tx (1
.o (=))
0 0 .
(8)
The Controlled-NoL (CNOT) gate a two-qubit gate that flips the second qubit (target) if the first qubit (control) is in the [1) state. We provide the matrix forms of common quantum gates in Table 9. When quantum gate acts on a quantum state (15), transforms this state to another quantum state Iv/"), according to the mathematical operation (eb") Ul+),, where U represents the unitary matrix associated with the quantum gate.
Parameterized Quantum Circuits. Parameterized quantum circuits (PQCs) consist of parameterized gates and offer a concrete way to implement quantum machine learning algorithms. Specifically, the common parameterized quantum gates are listed Table The parameters (e.g.. 0) the quantum gate can be either learnable parameters for optimizers or classical information that we want to encode.
Quantum Machine Learning. A quantum machine learning model can be constructed using a sequence of parameterized quantum gates. The initial quantum states can be transformed into the output quantum states. By measuring the output the quantum circuit, we can convert quantum information into classical information, which can be used to calculate the cost function of the optimization task. We can use classical optimizers to minimize the cost function by adjusting the parameters of quantum gates.
C FORMULAS OF EACH LAYER IN GQGLA
In GQGLA, the single-qubit gate can be written as the unitary matrix from. For example, k(0) exp( -i - pk ), where pk E {o., oz). Similarly, (0)) exp (ep,,, D(0) exp(-ig PD), G()) exp(-iž exp(-igpG). pG).
Based on this, the unitary matrix of the node feature layer of Fig. 4 contains: Uw,c,u,b, az) exp( ii
aa, +(u + a
(b, + ac,5) PMW
Up(l,c,o,0t) = exp(-
((4 + 04.3) 2 PX + + P2
2 -
(o) + 04,6 PD p2pt
where PW 8 X
tt 2
16

---

Published as a conference paper at ICLR 2025
Table Common quantum gates.
Operator
Gate(s)
Matrix
0
1
Pauli-X 0z)
1
0
0
Pauli-Y (Y,
1 0
(2,
Z
0
-1
Rotation-Z -Z (Rz(0))
RZ
e
COs
sin
Rotation-Y Y (Rty (0))
RY
sin
cos
cos
isin
Rotation-X (Rx (f))
RX
isin(
2
cos(
0
Controlled Not (CNOT, CX)
0
0
0
1
0
0
0
0
Controlled RZ (Cnz(0)
RZ
0
0
0
0
Controlled RY (#)
RY
0
cOs sin
sin
cos
0
Controlled RX (CRx (0))
RX
0
cos
cos(2)
8
sin
-i ssn )
cos
The graph message interaction layer of Fig. 5 contains:
cxp(-ii Σ
(Ar.s + -
(FJEEE
UK B1,2) = exp(-ii( Σ
(Ar, + B1,2) 0z) 02)2241155 p
(+,))E
(8(,)))) exp( (pp--il) Be,((I 0z 02)2441
(10)
(A, Be.a) exp(-i( Σ (Ais BL.)(I oz)22t} PK )),
(K.))EE
U (A, (c,5) = -exp(-it Σ
(Aiss + 3r,)(( 02)2045 PK
(KJ)EE
(8,,6))) exp(-i() 3r.6
17

---

Published as a conference paper at ICLR 2025
(a) Equivariant model
Invariant model
Yey
Invariant model
Change the order Ø,
Irget
Equivariant model
outpptt
Change the onder of isput
quppu
16
Equivariant model
outppt
Ingue
Invariant model
Chazge the coder of output nealts
Prodict fousibility and optimal values
Y
Figure 7: Diagram of the properties of equivariant (a) and invariant (b) models. For equivariant models, when the input node has a permutation a, the output is equivalent to the original one with the same permutation For invariant models, the permutation of input nodes will not affect output Y.
D THEOREMS AND PROOFS OF THE EQUIVARIANCE
D.1 THE DETAILS OF DEFINITION 1
Ag Boxq and Ap E B2xp are permutation matrices representing a permutation Ty Sa and Tp E SP, respectively. S and S are the groups containing all permutations the variable nodes and p constraint nodes, respectively. After the MILP graph undergoes permutation Ty and TT, the feature set of the variable nodes and the feature set of the constraint nodes become A₂H and A A, respectively. Then, the adjacency matrix between variable nodes and constraint nodes of the MILP graph A E 1RX2 is transformed to Ap. We define permutation Ty+p on the (q + p) elements to indicate the overall permutation all nodes of the MILP graph. To+p consists of distinct parts: the first & elements follow the permutation Ty, and the subsequent p elements follow Tp- A is the unitary representation of kgtz. which indicates the permutation of qubits representing nodes. A can be implemented by applying a series of SWAS AP gates to the quantum circuit. The detailed proof and formulation
follows.
is known that any permutation can be expressed as a product of transpositions. The transposition refers simple permutation that just swaps elements. Suppose that the permutation "g+ con- tains z transpositions, i.e., Tgtp = (611, 612)...(511 (521 822). Given that a n-qubit quantum circuit and suppose that one qubit represents one node, i.e., p + q, a transposition (821 d.2) can be represented by a SW AP 6.2) gate to exchange the -21 qubit and 622-th qubit of the quantum circuit. Hence, the corresponding unitary Ä Ås, As..... is equal to
SW AP (o SW. AP S.P....SPPPPPPPPa..aa.. (6..66)....WWW AWAPPOL (
(11)
That is, we decompose complex permutation into series of transposition, so that we can get:
Defintion D.I. If the quantum circuit U equivariant for any transpositions (da, 8.2), i.e. U(Aps, ANgs, Aa5, H", H θ) = Nr -U(A H" H$ () No;
the circuit is equivariant for the permutation Tgtp. where Aps, and Ago, are the permutation matrices corresponding the permutation (ō,1, 0z2).
18

---

Published as a conference paper at ICLR 2025
Based on Definition D.I, derive Definition by using Eq. 11.
UUAAH' H H2,0), ....).
SW SWAP((8 ..2) S.. AP(8n (12) UAA,H' H)- SWAP (ôn SWW)...WAA.. AP (P (6.1)
SW AP (6.1 (.2)....SWWWW AP (821 S22) (Ap6, AAgo, A26, HV, AAp,, H 0)SW (P( SW AP (8.1.622)
UAAps...... 9Ago..... A96
HV Poi H)
= UAA,AA H, A,H*,
(12)
By the associative law of matrix multiplication, we can combine the middle three terms of the formula until the last transpositions. In the final, Aps Ap and Agó,.... 6. A, reprsent the permutation matrices corresponding to the permutation xqtp = (Ón, 812)...(011 0.2) 8.2). Thereby, we can obtain Definition
D.2 THE DETAILS OF THEOREM
We can decompose Theorem into the following theorems and corollary for clearer proof.
Theorem D.1. (Uggt is Equivariant). The circuit Uagt (A, H H ④) of the proposed GQGLA is permutation equivariant circuit.
Theorem D.2. (D(A, H. θ) is an Equivariant Mapping). After Pauli-Z measurement, the output of the GQGLA permutation equivariant.
Corollary D.1. (A,,, H) an Invariant Mapping). The mapping of GQGLA to predict
the feasibility of instance of (AA, fea is permutation invariant.
D.2.1 THE PROOF OF THEOREM D.
These two circuits in the quantum circuit are permutation-dependeee and permutation-indeeendeer circuits. germutation-dependent circuit refers to the quantum circuit composed of gates related to input node features or edge features. Permutation independent circuit is defined as:
Defintion D.2. (Permutation Independent Circuit). A parameterized quantum circuit Unna) is permutation independent for MILP graphs (A, H² If') if Unnna((A A, AyH θ) (O), and
XtUnaa (e) = Unaal θ = (O).
(13)
We can derive the permutation equivariance of the circuit that only contain permutation equivariant circuit and permutation indepentent circuit.
Corollary D.2. EEquivariant x Independent = Equivariant). If quantum circuit U = UegUinds where Ueg represents the permutation equivariant circuit and Unn represents the permutation independent circuit, then U is the permutation equivariant circuit.
Proof. It is known that
U (A HS) = A U (A A AAHS) -t,
XtUnnd (P) = Uinel (0)At Um))(O).
Therefore, we can obtain
U(A, H$, +) HY, H JUnde A. Ung (Ag A.HY ApH²)) Ät Unn
= - UeU A.H A,H²) - A Uma((9) At
A U. AH' A₂H²) (+))()) Ät
Å A-UUAAAAAp.. AH A ( 9) Ät,
which indicates the circuit satisfies the definition of permutation equivariance.
On the other hand, GQGLA contains many layers, and we can demonstrate the permutation equivari- ance GQGLA by proving permutation equivariance of each layer in GQGLA.
19

---

Published as a conference paper at ICLR 2025
Node Feature Layer
Graph Message Interaction Layer (w = 1)
WiG + Mg37
PG1 662)
W(u, + dra)
KGAu A.
Constrrintt Update Layer
x
Wics + (,a)
PC2 613?
W(ws 1ia))
D(P2 m6a)
Rok-)
W(h, + +,a)
D(s
Wib;
+8aa)
Variable update loyer
Figure 8: The framework of GQGLA with one qubit represents one node (i.e., W 1).
Theorem D.3. (Equivariance of T-layered circuit). A I-layered quantum circuil U (A, H" HP, () IT U' H (i) is permutation equivariant iff every layer U is permutation equivariant.
Proof. U is permutation equivariant means that
UA H2, 6.) A U (' ArH ApH², O.) At.
Therefore,
U(A,H, H3, 0) [ H H,, II A U (A,AA AnH ApHi, Xt,
where Ā and Ät I. Hence,
F U(A.H, HS, 9) = I U A AA A, ARH θJ)T = AU A, A.H O)
Each layer of GQGLA has the UHH",, H$, a,)U, (,,,UU((71)) Moreover, U2(T) is permutation independent circuit. Therefore, by Corollary D.2 and Corollary D.1, only need to prove that U~(H', HS au) and (A, B,) are permutation equivariant for any transpositions (6:1. 6:2).
circuit structure and be decomposed into
Equivariance of the Node Feature Layer
Take Fig. 8 as example, i.e., one qubit represents one node, U.( HS or) can be written as Us &U,, @U,, &U.,. where Up, = W(a+tar,)D((44a. (u,+a,, 2(E,; tar,,,) (I..... 4} and Unj W (b; + D(o; + ac,6), = p}. When the node permutation changes, UA, a,) U, @ Ue,_(a> US UU U,,,,ey As we can see, the node permutation transformed into the permutation of the order of tensor products of unitary matrices on individual qubits. Suppose there is n-qubit arbitrary quantum state
w Σ Cdi..dd...dd. ......)..)d... dj (0,
where Cd...d,...d, dn is the amplitude of the basic state Id1... Take (b) as input U U1 @ ...U,... 3 Un. For transposition (ōa, 6:2).
SW SWAPPt,, (22) 1 10) > Cdp Odiaila me di de
USW AP (o (p 10) Σ Od Anp Uilds) ... @ Uni (d5Ø)) @ Us. Ids,,? @ Un.ddd))
SW SWAPP Ug USW AR 122) 10) = Σ Cap das 4b.2 da Unldi) @ ... & Uni ) & ... (doia) @ U....dd.)))
U1 Uni
Vsn & Unlv).
(14)
Therefore,
obtain SW AP 6:2) U1 2 @ Us. @ & Us 2 SW AP ( (1))
Uj @ ... X Us.2 @ ... & Us, 8 ... & Un. which indicates the unitary satisfies the definition of the equivariance.
Equivariance of the Graph Interaction Layer
As shown in Fig. 8, the variable update layer has similar structure the constraint update layer. Moreover, the layer that consists of G(3)) the permutation independent circuit. Therefore, ac- cording Corollary D.2, only need to prove that the layer that consists of controlled- K gates is
20

---

Published as a conference paper at ICLR 2025
permutation equivariant. It is known that CK(0)2,, I 2 [0) K(0) & [1) where the first qubit is the target qubit and the second qubit the control qubit. Moreover,
SW AP (2.1) SW) (P22, 0) & + [1) & K(0) CK( (15)
For ( circuit,
+
1 @ @
& + (
10X.1_111111___..1.1 Ins
where the index of the matrix represents the index of qubit that the matrix acted on. For brevity, set 8yk AAs + 8t 0 [0) (0), 1 = [1), and the edge set of the graph is E. As we can see, the double-qubit quantum gate only related the permutation of the qubit (q + j) or qubit k. Assume that there are two transpositions (q j. 4 + 8 8*)) and (k:, to exchange the place of the qubits, and SW AP denot Considering a n-qubit arbitrary quantum state
(0b = - Cd (d ............ ...d (1)(())).)))).)))))))) (K)...
{0,11]
SWAP (6) = Cdg..deend (x) de do+5 dyt.........
CK(B)))th..SWW SP w) E Cdr..de..... dn (((d)) 8 ... 0d
(d+p) ... @ ld (n)))
+ (Idi) @ ... & (00;s) 8.... @ (da) @ @ 1 dd @ dg+s) @ (n)),
SWAP CK (0 1P/ = Σ Cd (((d)) 0 d 0
. (d. (n))) (ld1) (de) @ ((0))))lds<ss)
(dp+)) 1 ()) ... |d, (n)).
C.((A, (1)
(16)
Therefore, we can obtain
SW AP CK(A,M SW)+
SP (b) CK(AA + (0048113 CK(As = + Be)g
(17)
where j = (J') and l: = (k'). It is known that (% = IIGAAJEE CK(Ajt + Be)atsk
UN = II
SW CK(P + Be) AP
USEEE
II (K(A51(915000) Be (JA)EE
CK(A))))))) + Bi) ('Aeeee
II
(18)
= -U B.) (Ns, A.),,
where As, and As, are the permutation matrices the permutation 5, and 5y- The equation indicates the equivariance of the graph message interaction layer.
D.2.2 PROOF OF THEOREM D.2
As mentioned earlier,
( θ) = $(A, HV HS, θ) [(01U pegg (A O)O,UUpeg (A,H", HS, ()
(19)
and we have proven that Upeng is permutation equivariant. i.e.,
A Upegy (A, HV HS, θ) Ā = Upegg AAp AgH., AAHS 9).
(20)
Therefore, AAA.AAp A H A,HS, +)
= -(OlUt pegy pegg (A AA A,H AgHS, ,0O,, pegg (ApAAg. AHH A,H e
-[OOAATT pegg (A,H*, H$ θ)) pago (A, H$ 11)
(21)
-(OoAAtt pogg (A, H Q)) (1) pegg HA, H. +))
-A,+, ( HV H$ O),
which indicates ((A, Hy Hs. θ) is permutation equivariant mapping.
D.2.3 PROOF OF COROLLARY D.
21

---

Published as a conference paper at ICLR 2025
Corollary D.3. (From Equivariance to Invariance). If mapping O H², H*) E RR+P is permutation equivariant, Σ(o(A, , is permutatiin invariant.
Assume that ((A,H, ,H)) = [y1..... Botpl TT, According to Definition 2, 6(ApAAq: Ay AAH²) = (1r++)(1) u. Mo (ra+ Therefore, we can obtain (,H))
Proof.
E(O(A, H)) E Us ExE (). I(o(ApAA
By Theorem D.2 and Corollary D.3, we can obtain diea (A, H) = EiS $(A, H, fea): is permutation invariant. Similarly, the mapping of predicting objective value Pobjl (A, H)
En (A, H, Oeb)); also holds.
D.2.4 AN INTUITIVE EXAMPLE OF GRAPH MESSAGE INTERACTION LAYERS
In graph message interaction layers, each edge is mapped into a two-qubit quantum gate acted on qubits representing two nodes. For example, here is graph G with three nodes a, b, c. After the first feature encoding layer, the quantum state (0)) = (ea) @ (bb) @ k&e).. If there is an edge connecting nodes and b, the model will apply two-qubit quantum gate between qubit qa and qubit Tb- Suppose the used two-qubit gate is Rzz (0) = exp(- - i & 2) gate, then it is equivalent to multiplying the quantum state by a matrix U Rzz @ L. Thus, the quantum state is changed as (eX) ) U|p)
(exp(-i0Z @ Z) @ (1v)) words, the two-qubit gate alters the quantum states corresponding to nodes a and b, thereby achieving the goal of information exchange.
) @ (bb) & (e)) (Rzz (0) @ Z) ([ @ ((b)) = (w%b)) ) @ (e)). In other
E GQGLA CAN DISTINGUISH MILP GRAPHS THAT GNN CANNOT DISTINGUISH
E. WHY GNN FAILS ON THE GNN-INTR MILPs
The discriminative power of GNN is defined whether it can distinguish two non-isomorphic graphs. The representation power of GNN refers to its ability to approximate mappings with permutation cquivariant/invariant properties. Moreover, Xu al. (2018) have shown that GNNs are at most as powerful as the Weisfeiler-Lehme structures. The WL test a well-known algorithm to identify whether two graphs are isomorphic or not, i.e., whether two graphs are topologically identical. However, there are numerous WL test indistinguishable graphs, and the most well-known class is regular graphs, where every vertex has the same number of neighbors, i.e., the same degree. According to the above, if pair of graphs is indistinguishable by the WL test, GNN will also fail to distinguish them. In fact, the MILP graph dataset just contains numerous WL- WL-indistinguishabe graphs, directly using GNN to represent general MILP graphs will lead to poor performance. Chen et al. (2023) extracted this subset of WL-indistinguishable graphs from the entire MILP dataset and named it the "GNN-intractabb MILP". A variant of the WL test specially modified for MIIP is provided in Algorithm 1. Based on the algorithm, it can intuitively show why the WI test cannot distinguish some non-isomorphic graphs, thereby showing why GNN cannot discriminate GNN-intractable MILPs
(WL) test Weisfeiler & Leman (1968) in distinguishing graph
Algorithm WL test for MILP-Graphs
Input: A graph instance (A, H) E Ggp x HY HsS and iteration limit I. > 0. Initialize with cy hash(s for all V. hSsh(sS) for all s e S. for 1 = to L do d hash(c E Ar,hash (c,,)),, for all veve
and
hash(d E Ar,hash (ct; 1), for all s S.
end for
Output: The multisets contain all colors ((c. : V.
In the algorithm, hash(-) (-) is a function that maps its input feature to a color in C. The algorithm flow be seen follows. First, all nodes in V U S are assigned to initial color ee and di according to their node features. Then, for each U; E V, the hash function maps the previous color d-1 and aggregates the color of the neighbors of (d) 1-1)), (N)))) Similarly, the hash function maps
22

---

Published as a conference paper at ICLR 2025
the previous color d and aggregates the color of the neighbors of (c.''ree Io,e)(ss)-- This process is repeated until L reaches the maximum iteration number. Finally, histogram hG of the node colors can be obtained according to {( : v E V.C. : S S}}, which can be used as a canonical graph representation. The notation ({-}) denotes multiset, which is generalisation of the concept of a set in which elements may appear multiple times. That is, the WWL test transforms a graph into canonical representation. If the canonical representation of two graphs is equal, the WL test will
consider them isomorphic.
Assume that there node has n neighbors in both graphs. And we set A1 * A2 and H1 = Hg. i.e., they have the same features but different topology structures (the connectivity of edges). For clarity, we set {J) y is the same, and U
n-regular MILP graphs Gi (A1, H1) and G2 (A2, H2), where each
) 1 the same. Fig. is an example of this type of graph. Initially, in the
WL-test, (c))g1 = g2 and (c.)21 = (c)) Then, the representation of each vertex is updated iteratively based on itself and information from its neighbors. In both graphs, each variable node has the same number constraint nodes, and all constraint features are the same, so all c,, are identical at this step. Similarly, each constraint node has the same number of variable nodes, so all de are identical. Until the maximum number of iterations is reached, the algorithm will output the same representation for these two graphs. Therefore, the WL-test or GNNs cannot distinguish them.
E.2 PROOF OF THE DISCRIMINATIVE POWER OF GQGLA BETTER THAN GNNS
Theorem F.1. GQGIA can capture the difference edge connectivity between two MILP graphs.
Proof. Suppose that G1 = (A1, H1) and G2 = (A2, H2), and the two graphs have only different edge connectivity or edge weights, i.e,, A, F A2. In GQGLA, the layer related A is the graph message interaction layer. As shown in Eq. 10, the sublayers related to A are UK layers. All UK layers have similar structures. For clarity, consider the following a simplified UK layer (where one qubit represents one node) to showcase how GQGLA captures the topological structure. ie..
UK(A) = exp(-ii Σ A15(T oz))
(N,))E
V.. 8(1 oz) ? Note that (1,..., Φ) and j {1,... p), and (I o2); is equal 18...
I. Similarly, pk 9tj 10 @...0
pk 8... 8.. Therefore, (1 oz):Pp
J-1
σ.) 8...
pk c...
PK o= appears in one of the first q positions, and PK acted in one As we can see, for (I (I-o2),PA 9+3s of the last positions. For different edges, (T - oz); PK is different. More importantly, for different is also different due to the properties of tensor products. Therefore, if A1 # A2, resulting in UK (Ai) * U. (A2). which indicates the GQGLA can capture the difference in edge connectivity between two MILP graphs. Although two non-isomorphie regular graphs have the same degree, the edge connectivity is different. That is, GQGLA can distinguish GNN-intractable MILP graphs that GNN fails to distinguish.
edge sets, (i.j)e Ai,ū PK P
F THE PERFORMANCE OF ALL POSSIBLE TYPES OF GQGLAS
Table 10 lists all possible selections of the quantum gate in GQGLA, The type represents (P"r pD) pk pC). For example, when the type equal to (az,, a2, Bys o2), it indicates (() (0), D(0) (0) CK((0) C'yy (f), and G(0) different settings, we test them on the task of predicting the feasibility of the GNN-tractable MILP dataset. In the experiment, rate to 0, and the batch size to 16. Table shows GQGLA with (oay os, oo, σ2) can achieve the best result, adopt this scheme in our all experiments.
(f). To compare the performance of
set the block of GQGLA is 8, the number of epochs to 15, the learning
23

---

Published as a conference paper at ICLR 2025
Table 10: All possible selections of GQGLA and their performance results on predicting the feasibility of GNN-tractable MILP datasets. Results demonstrated that (Øz, oz By σz) can achieve the best performance.
Types
(ox, Vy.00.00.:00 (2. (1
(11.02102100,) (0,.02,02.00))
(0 (2,,02,0y Gy:0))
(A2. Wa..y. (ay [g)
Train
0.0598
0,0557 0.0574
0.0724 0.0741
0.0623
0.0635
0,0615
Test 0.0606
0.0625
0.0647
0.0635
G MILP DATASET GENERATION
For GNN-tractable MILPs, we first set the number of variables and constraints to m and n.
For each variable, Cý NO( 0.01), 1,. ", U(0, 2r). If > uy, then switch 1 and uj- The probability that 2, is an integer variable is 0.5.
For each constraint, o; ~ U(S,= and b; ~ (-11,1).
After randomly generating all the MIIP samples, we use the WT. test algorithm to calculate their graph representation for each instance, ensuring that there are no duplicate graph representations in the dataset, so that we can determine that this dataset does not contain WL-test indistinguishable pairs of MILP instances.
The GNN-intractable dataset is constructed by many pairs of WL indistinguishable graphs, and Fig. 1 in our paper is GNN-intractable example, which a pair of non-isomorphic graphs that cannot be distinguished by the WL-test or by GNNs. The GNN-intractable dataset randomly generates 2000 GNN-intractable MILPs with 12 variables and 6 constraints, and there 1000 feasible MILPs with feasible optimal solutions while the others are infeasible. We construct the (2k 1)-th and 2k-th problems via the following approach, where (1 < k < 500).
ja) as random subset of 2,,2,... ..., 12) with 6 elements. 1) For j E J, 2, E {0, 13. i.c. Iy is a binary integer variable. 2) For & J, J, is a continuous variable with bounds 1y ~ ((, TT) uj ~ U(0 T). If > u.j then switch ly and uz.
Sample J
= = C12 0.01.
The constraints for the (2k- 1)-th problem (feasible) 2n + Øyz = 1, 1, + I3 = 1.
ZJs tæ 1, tıソ 1, J.. t Jo +2,, 1. For example, x 00,1,0,1,00
is a feasible solution.
The constraints for the 2k-th problem (infeasible) is Iy + 2zz Tjs + Tjj = 1, 2z4 + Jij = 1, Ija Ije = 1, Fje 3j = 1.
Dtz + 2js
(a) o% layer for mult-dimensional edge features
(b)
Ug layer for m>11
KrAh
K04
609
122
&aA +a
B006, +55
KtAg, Mil
1//4,
i
0I(A
0g (A.Paa))
(PE()
Figure 9: (a) The controlled K layer for multi diltiiidmmesional edge features. (b) The controlled G' layer for m > 1, where m is the number of qubits representing one node By or 8;.
H THE CAPACITY OF GQGLA
The proposed framework can also be used for situations where the edge dimension is more than one. As shown in Fig. 9 (a), the controlled K gates be repeatedly applied with different edge dimensions. In addition, Fig. 9 (b) illustrates the detailed circuit when the number of qubits representing one node is more than one. Moreover, although GQGLA is designed for MILP graphs, i.e., bipartite graphs, it can be easily extended to arbitrary graphs. Specifically, in the quantum graph message interaction layer, we can apply symmetric two-qubit gates, such as Rzz gate, between two nodes, representing edges in an arbitrary graph and preserving the edge permutation invariance. The remaining structure can remain completely unchanged when applied an arbitrary graph.
24

---

Published as a conference paper at ICLR 2025
Figure 10: Variance v.s qubits (log- linear scale).
It has been shown that general QNNs may suf- fer from barren plateau (McClean et al., 2018), i.., the loss gradients vanish exponentially with the system size, causing the trainability of QNNs becomes important issue. However, Fig. 10 shows the variance of our cost function par- tial derivatives for a parameter in the middle of
Exponential Decay
le-3
Polynomial Decay (0urs)
Vartunze Greaberats
Ee-4
20-4
GQGLA. The variance only decreases polyno-
mially with the system size, which shows that GQGLA has good trainability.
le:4
6
8
10
16
18
Number Qubits
I THE DETAILS OF UK LAYER
In the training process, the types (e.g., (0), (0), RZ(0)) and positions of gates are fixed, but their internal parameters are not fixed in the quantum machine learning. Therefore, should be noted that when implementing the proposed graph message interaction layer, there is actually a controlled K gate between each variable node and each constraint node (like a fully connected bipartite graph). However, if there is no edge between the two nodes, will set the parameters of the corresponding controlled gate to O. CO(()) is an identity matrix that will not affect the overall circuit. Specifically, in code engineering, we first obtain the binary adjacency matrix T of the bipartite graph. Tij = 1 indicates that there is an edge connecting constraint node 8; and variable node vy. while Túj 0 indicates that there is no edge connecting them. Then, CK acted on the two qubits representing constraint node and variable node vy. As we can see, when there is an edge between the two qubits. CK (A,g + 3) is acted on the two qubits, while when there is no edge between the two qubits, CK((0) is acted on the two qubits. In this way, we can achieve the modeling of the graph message interaction layer under the premise of fixed gate types and positions.
+ 9)) is
THE IMPLEMENTATION ON REAL QUANTUM DEVICES
Our proposed GQGLA quantum circuit consists of only simple single-qubit and two-qubit gates, making it easy to deploy on existing NISQ devices. To verify this, we use the Qiskit package and the IBM Quantum platform to directly execute our circuits on real IBM quantum hardware. The circuits are first compiled and optimized, then mapped to the real quantum hardware's 's topology using the generate, prreset pass manager function. Subsequently. the expectation values of the quantum circuits are estimated using the Estimator V2 primitive. The Estimator primitive supports three resilience levels: Resilience Level 0 represents no error mitigation techniques are applied. Resilience Level applies readout error mitigation and measurement twirling using model-free technique known as Twirled Readout Error eXtinction (TREX) (Van Den Berg et al., 2022). Resilience Level includes the eтror mitigation techniques from Level and further applies gate twirling and the Zero Noise Extrapolation (ZNE) (Temme et al., 2017).
We conducted experiments using 10 minutes of free usage the 127-qubit IBM Brisbane quantum computer, and evaluate the mean square error (MSE) compared to ground truth on MILP dataset with three different scales, as shown in the table below. The results demonstrate that employing error mitigation strategies can improve performance. Higher resilience levels produce more accurate results, but the cost of increased processing time, which is a trade-off between cost and accuracy.
18 qubit
26 qubit 36 qubit
Noise (ibm brishane) 0.2627
0.2850
0.3461
resilience_level = 0.2107
0.2428
0.3336
resilience. = 0.2077
0.2174
0.3176
Table 11: Performance comparison across different qubit numbers and resilience levels.
In addition, we studied the parameter transferability and the impact of noise on performance. We train on the 20-qubit GNN-imtractalle MILPs and transfer their parameters into problems with 30, 40, and 50 qubits to test. n qubit represents MILP graph dataset containing 200 different graphs with a nodes.
25

---

Published as a conference paper at ICLR 2025
Specifically, use Qiskit's (Javadi-Abhari et al., 2024) matrix product state simulator, as well as IBM's noise model Fake Washington with the backends built to mimic the behaviors of IBM Quan- tum systems. As shown in Table 12, the model param- eters trained on the 20-qubit remain effective for the 50-qubit data, benefiting from GQGLA's parameter- sharing mechanism. This means that the parameters trained on small qubit datasets can provide a good initialization for larger qubit datasets, speeding up the training. Moreover, while noise does have impact on performance, the effect is not big.
Table 12: Parameter transferability across qubits
under noiseless and noisy conditions.
Qubit
(base)
30
50
Noiseless Nosiy
1.0
0.967
0.908
0.862
0.995
0.928
0.864
0.825
26


Reviews:
[{"review_id": "iqWLrjEzb8", "reviewer": "Reviewer_xDyW", "summary": "This paper proposes a new quantum-driven graph learning model called VQGLA, which aims to overcome the limitations of classical Graph Neural Networks (GNNs) in representing mixed-integer linear programming (MILP) problems. VQGLA leverages quantum computing to provide superior discriminative capabilities for complex optimization tasks like MILP representation. The proposed model introduces a node feature layer, a graph message interaction layer, and an auxiliary layer, ensuring permutation equivariance and flexible circuit configurations. Experimental results demonstrate VQGLA's effectiveness compared to classical GNNs on both GNN-tractable and GNN-intractable datasets.", "questions": "1. Can the authors provide more insights into the scalability of VQGLA, especially concerning the number of quantum gates required for larger graph instances?\n2. How does the presence of quantum noise impact the performance of VQGLA? Are there any error mitigation strategies that could be employed?\n3. Could the authors include a comparison with more advanced classical GNN models, such as Graph Transformers, to highlight the specific advantages of the quantum-driven approach?\n4. Is there any practical guidance on implementing VQGLA on near-term quantum hardware? A discussion on the hardware requirements would be very helpful for future work.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper clearly articulates the limitations of classical GNNs in representing MILP problems and makes a strong case for the introduction of a quantum-driven solution. The use of quantum machine learning (QML) is well-motivated, especially in scenarios where classical methods are fundamentally limited, such as GNN-intractable graph representations.\n\n2. The design of VQGLA, including the node feature layer, graph message interaction layer, and auxiliary layer, is well-thought-out and comprehensive. The incorporation of quantum entanglement to enhance discriminative power is innovative, and the theoretical proof of permutation equivariance strengthens the rigor of the work.\n\n3. The experimental results are compelling. VQGLA's superior performance over classical GNNs is demonstrated through multiple benchmarks, including both GNN-tractable and GNN-intractable MILP datasets. The comparison to other quantum and classical methods is thorough, and the reported results support the claims made in the paper.\n\n4. The paper demonstrates the versatility of VQGLA by applying it to various graph tasks, including graph classification, graph regression, and node property prediction. The adaptability of the model to different levels of graph tasks, as well as its ability to handle edge features, is a significant advantage.", "weaknesses": "1. While the paper emphasizes the benefits of using quantum methods, it lacks a detailed discussion on the computational complexity and scalability of VQGLA. The use of fully quantum circuits for large graph instances might introduce significant resource requirements, and this limitation is not addressed sufficiently. It would be helpful if the authors provided more insights into the scalability of VQGLA with respect to graph size and the number of quantum gates required.\n\n2. The explanation of the quantum operations, especially in the auxiliary and graph message interaction layers, could be clearer. The use of quantum gates and entanglement is discussed at a high level, but more detailed explanations and diagrams would make it easier for readers without extensive quantum computing backgrounds to understand the exact role of each component in the quantum circuit.\n\n3. Although VQGLA is compared to classical GNNs and a few quantum models, it would be beneficial to include more comparisons with state-of-the-art classical GNN architectures that have shown effectiveness in handling complex graph tasks, such as Graph Transformers or other hybrid models. This would provide a more comprehensive understanding of how VQGLA stands relative to the best classical methods.\n\n4. The implementation of VQGLA on near-term quantum devices is briefly mentioned, but the impact of quantum noise on the model's performance is not explored in depth. Quantum hardware is prone to noise, and the absence of a discussion on error mitigation strategies or the robustness of VQGLA under noisy conditions weakens the paper's practical relevance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B897cUxwsi", "reviewer": "Reviewer_x2kb", "summary": "The authors present a versatile quantum graph learning architecture (VQGLA) method for solving GNN-intractable mixed-integer linear programming (MILP). The VQGLA encodes features of nodes and edges in quantum circuits, which maintain node permutation equivariance. The new method combine the power of quantum computing and GNN, exhibiting superior discriminative power over classical GNNs.", "questions": "The authors show a good parameter transferability. I wonder if these graphs have the same structures? \nThe authors compare the VQGLA and the HEA in their numerical results. Did they encode the graph information in the HEA?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The authors present a well established method for MILPs. By introducing quantum computing, this new method is able to solve GNN-intractable MILPs. Numerical results can fully support this conclusion. I believe that this work exhibits an interesting application of quantum computing for solving real-world optimization problems.", "weaknesses": "The quantum circuits that are used to encode the constraint node are not straightforward. Could the authors explain how to map mathematical operators onto quantum circuits?\nThis work exhibits excellent performance of VQGLA in solving some MILPs. It is interesting to discuss the scalability and quantum circuit complexity of this method for general graph structures.\nSince quantum neural network is an interdiscipline, the authors would better clarify how to turn a real-world problem into a quantum computing problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PkFHqYPSxu", "reviewer": "Reviewer_9Vep", "summary": "The authors proposed a quantum machine learning method to solve mixed integer programming via graph learning.", "questions": "Is the proposed method still superior comparing to higher order GNNs? Examples include subgraph GNNs that can distinguish the graphs in figure 1.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The proposed method is able to encode MILP graphs that are known to be intractable by message passing GNNs. The authors show that this method is able to surpass GNN baselines, especially on GNN-intractable problems.", "weaknesses": "The examples of GNN-intractable MILP problems are specific to message passing GNNs. Various works on higher-order GNNs have been proposed to overcome this issue in classical GNN architectures. Indeed, the authors provided experimental comparison to graph transformers; but basing the main motivation on a weak GNN lacks persuasiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)