On Representing Mixed-Integer Linear Programs by Graph Neural Networks
Authors: Ziang Chen
Jialin Liu
Xinshang Wang
Wotao Yin
Venue: ICLR 2023 poster (2023)

Abstract: While Mixed-integer linear programming (MILP) is NP-hard in general, practical MILP has received roughly 100--fold speedup in the past twenty years. Still, many classes of MILPs quickly become unsolvable as their sizes increase, motivating researchers to seek new acceleration techniques for MILPs. With deep learning, they have obtained strong empirical results, and many results were obtained by applying graph neural networks (GNNs) to making decisions in various stages of MILP solution processes. This work discovers a fundamental limitation: there exist feasible and infeasible MILPs that all GNNs will, however, treat equally, indicating GNN's lacking power to express general MILPs. Then, we show that, by restricting the MILPs to unfoldable ones or by adding random features, there exist GNNs that can reliably predict MILP feasibility, optimal objective values, and optimal solutions up to prescribed precision.  We conducted small-scale numerical experiments to validate our theoretical findings.

Published as a conference paper at ICLR 2023
ON REPRESENTING MIXED-INTEGER LINEAR PRO- GRAMS BY GRAPH NEURAL NETWORKS
Ziang Chen
Jialin Liu
Department of Mathematics, Duke University Durham, NC 27708 z ziangemath, duke. edu
Damo Academy, Alibaba US Bellevue, WA 98004
jialin. 11 uual ibaba inc. com
Xinshang Wang
Damo Academy, Alibaba US
Antai College of Economics and Management, Shanghai Jiao Tong University Bellevue, WA 98004
xinshang.
com
Jianfeng Lu
Wotao Yin
Departments of Mathematics, Physics, and Chemistry, Duke University Durham, NC 27708 jianfengemath. duke. edu
Damo Academy, Alibaba US Bellevue, WA 98004
wotao.yin@e i'aaba - i inc. com
ABSTRACT
While Mixed-integer linear programming (MILP) is NP-hard in general, practical MILP has received roughly 100-fold speedup in the past twenty years. Still, many classes of MILPs quickly become unsolvable their sizes increase, motivating researchers to seek new acceleration techniques for MILPs. With deep learning, they have obtained strong empirical results, and many results were obtained by applying graph neural networks (GNNs) to making decisions in various stages MILP solution processes. This work discovers a fundamental limitation: there exist feasible and infeasible MILPs that all GNNs will, however, treat equally, in- dicating GNN's lacking power to express general MILPs. Then, we show that, by restricting the MILPs to unfoldable ones or by adding random features, there ex- GNNs that can reliably predict MILP feasibility, optimal objective values, and optimal solutions up to prescribed precision. We conducted small-scale numerical experiments to validate our thcoretical findings.
INTRODUCTION
Mixed-integer linear programming (MILP) is a type of optimization problems that minimize a lin- ear objective function subject linear constraints, where some or all variables must take inte- ger values. MILP has a wide type of applications, such as transportation (Schouwenaars et al.) 2001), control (Richards & How 2005). scheduling (Floudas & Lim 2005). etc. Branch and Bound (B&B) (Land & Doig 1960), an algorithm widely adopted in modern solvers that exactly solves general MILP' to global optimality, unfortunately, has an exponential time complexity the worst- case sense. To make MILP more practical, researchers have to analyze the features of each instance of interest based on their domain knowledge, and use such features to adaptively warm-start B&B or design the heuristics in B&B.
To automate such laborious process, researchers turn attention to Machine learning (ML) techniques in recent years (Bengio et al. 2021). The literature has reported some encouraging findings that proper chosen ML model is able to learn some useful knowledge of MILP from data and generalize well to some similar but unseen instances. For example, one can learn fast approximations of Strong
A major part of the work Z. Chen was completed during his internship at Alibaba US DAMO Academy. Corresponding author.

---

Published as a conference paper at ICLR 2023
Branching, an effective but time-consuming branching strategy usually used in B&B (Alvrrez et al.,
2014 Khalil et al., 2016; Zarpellon et al. [2021] Lin et al., (022). One may also learn cutting strate-
gies Tang al. 2020; Berthold et al.] 2022 Huang al., 2022). node selection/pruning strate-
gies (He et al. 2014; Yilmaz& & Yorke-Smith] 2020), or decompasition strategies (Song et al. 2020) with MI. models. The role of MI. models in those approaches can be summarized as: approximal- ing useful mappings or parameterizing key strategies in MILP solvers, and these mappings/strategies usually take an MILP instance as input and output its key peroperties.
The graph neural network (GNN), due to its nice properties, say permutation invariance, is consid- ered a suitable model represent such mappings/strategies for MILP. More specifically, permuta- tions on variables or constraints of an MILP do not essentially change the problem itself, reliable ML models such as GNNs should satisfy such properties, otherwise the model may overfit to the vari- able/constraint orders in the training data. Gasse et al. (2019) proposed that an MILP can be encoded into a bipartite graph on which one can use a GNN to approximate Strong Branching. Ding et al. (020)) proposed to represent MILP with tripartite graph. Since then, GNNs have been adopted to represent mappings/strategies for MILP, for example, approximating Strong Branching (Gupta et al.
2020 Nair et al., 2020; Shen et al. 2021 Gupta et al., 2022), approximating optimal solu- tion Nair et al. 2020; Khalil et al. 20222. parameterizing cutting strategies (Paulus et al. 2022).
and parameterizing branching strategies (Qu al. 2022 Scavuzzo al. 2022).
However, theoretical foundations in this direction still remain unclear. A key problem is the ability of GNN to approximate important mappings related with MILP. We ask the following questions:
Is GNN able to predict whether an MILP is feasible?
(Q1)
Is GNN able to approximate the optimal objective value of an MILP?
(Q2)
Is GNN able to approximate an optimal solution of an MILP?
(Q3)
To answer questions Q1 Q3,, one needs theories of separation power and representation power of GNN. The separation power of GNN is measured by whether it can distinguish two non-isomorphic graphs. Given two graphs G1 G2, we say mapping F (e.g. GNN) has strong separation power if F(G,) + F(G2) as long as G1. G2 that are not the isomorphic. In our settings, since MILPs are represented by graphs, the separation power actually indicates the ability of GNN to distinguish two different MILP instances. The represeniation power of GNN refers to how well it can approximate mappings with permutation invariant properties. our settings, we study whether GNN can map an MILP to its feasiblity, optimal objective value and an optimal solution. The separation power and representation power of GNNs are closely related to the Weisfeiler-Lchme & &Leman 1968) classical algorithm to identify whether two graphs are isomorphic or not. It has been shown that GNN has the same separation power with the WL test (Xu et al., 2019), and, based on this result, GNNs can universally approximate continuous graph-input mappings with separation power no stronger than the WL test (Azizian & Lelarge 2021
(WL) test (Weisfeiler
Geerts & Reutter 2022).
With the above tools in hand, one still cannot directly answer questions (Q Q3 since the relationship between characteristics of general MILPs and properties of graphs are not clear yet. Although there are some works studying the representation power of GNN on some graph- related optimization problems (Sao et al. [201 Loukas 2020) and linear programming (Chen et al., 2022], representing general MILPs with GNNs are still not theoretically studied, to the best of our knowledge. Our contributions are listed below:
Our contributions
(Limitation of GNNs for MILP) We show with example that GNNs do not have strong enough separation power to distinguish any two different MILP instances. There exist two MILPs such that one of them is feasible while the other one is not, but, unfortunately, all GNNs treat them equally without detecting the essential difference between them. In fact, there are infinitely many pairs of MILP instances that can puzzle GNN.
(Foldable and unfoldable MILP) We provide a precise mathematical description on what type of MILPs makes GNNs fail. These hard MILP instances are named as foldable MILPs. We prove that, for unfoldable MILPs, GNN has strong enough separation power and representation power to approximate the feasibility, optimal objective value and an optimal solution.
(MILP with random features) To handle those foldable MILPs, we propose to append random features to the MILP-induced graphs. We prove that, with the random feature technique, the answers to questions (Q1 Q3) are affirmative.
2

---

Published as a conference paper at ICLR 2023
The answers to QQI serve as foundations of a more practical question: whether GNNs are able to predict branching strategies or primal heuristics for MILP? Although the answers to QQ and (Q2) do not directly answer that practical question, they illustrate the possibilityy that GNNs can capture some key information of a MILP instance and have the capacity to suggest an adaptive branching strategy for each instance. To obtain a GNN-based strategy, practitioners should consider more factors: feature spaces, action spaces, training methods, generalization performance, etc., and some recent empirical studies show encouraging results on learning such a strategy (Gasse et al. 2019
Gupta et al.
2020 2022; Nair et al. 2020 Shen et al. [021] Qu et al., 2022 Scavuzzo et al. 2022
Khalil al., 2022). The answer to (Q3) directly shows the possibility of learning primal heuristics.
With proper model design and training methods, one could obtain competitive GNN-based primal
heuristics (Nair et al. 2020 Ding et al. 2020).
The rest of this paper is organized as follows. We state some preliminaries in Section 2
The
limitation of GNN for MIL is presented in Section[Jand we provide the descriptions of foldable and unfoldable MILPs in Section 4 The random feature technique is introduced in Section 5 Section 6
contains some numerical results and the whole paper is concluded in Section 7
2 PRELIMINARIES
In this section, we introduce some preliminaries that will be used throughout this paper. Our no- tations, definitions, and examples follow Chen al. 2022)). Consider a general MILP problem defined with:
min c x, S.L. Ar br Is 2j EE VJET. #ER"
(2.1)
where A E R CE C. , IE (-U(- u (R U (+oo))", and O (1.,,
The index set I c (1, n includes those indices j where zj are constrained to be an integer. The feasible set is defined with Xfeasible == fr |r b. I I u, Ij Z j E T), and we say an MILP is infeasible if iisusible = and feasible otherwise. For feasible MILPs, inf(c x: : x E { is named as the optimal objective value. If there exists x E X with e Ix" < c. V x E Xfeusible. then we say that x² is an optimal solution. It is possible that the objective value is arbitrarily good, i.e., for any >> 0, c T < < holds for some & E Xfessible. In this case, we say the MILP is unbounded or its optimal objective value is -00.
2.1 MILP AS A WEIGHTED BIPARTITE GRAPH WITH VERTEX FEATURES
Inspired by Gasse et al. 2019)) and following Chen et al. (2022), we represent MILP by weighted bipartite gruphs. The vertex set of such graph is V U W. where V = (U1, U2, .2,..., "mm) } with w representing the i-th constraint, and W {wi, W2,-... Wm) with w, representing the j-th variable. To fully represent all information in 22. we associate each vertex with features: The vertex E V is equipped with a feature vector h
(b,, o.) that is chosen from H. = R x (s, =, }}. The vertex W/ E W is equipped with a feature vector h. = (c,, Ug. T,). where T, = 1 if j E I and
T, = 0 otherwise. The feature i. W is in the space HW = x (RU( x (TR U (+x))) x 1). The edge E E E connects v, E V and wi E W, and its value is defined with E Ai.-- Note that there is no edge connecting vertices in the same vertex group (V or W) and Eig = 0 if there is no connection between U; and wy. Thus, the whole graph denoted as G = (V U W, E). and we denote Gm. as the collection of all such weighted bipartite graphs whose two vertex groups have size m and n, respectively. Finally. we define H. == (HV ym and H. = (HW)) yr, and stack all the vertex features together as H (hy by ..... by h. hW ...., hw H. x H.W. Then a weighted bipartite graph with vertex features (G, H) E Gm, x HY x H.W contains all information in the MILP problem (2.1). and we name such a graph as an MILP-induced graph or MILP- MILP-graph.
I If I = 0, the feature тj can be dropped and the graphs reduce to LP-graphs in Chen et al. 2022
We provide an example of MILP-grap in Figure
2.2 GRAPH NEURAL NETWORKS WITH MESSAGE PASSING FOR MILP-
To represent properties of the whole graph, one needs to build GNN that maps (G, H) to real number: Gm., x HY. x HWW > I; to represent properties of each vertex in W (or represent properties
for each variable), one needs to build a GNN that maps (G, ) to a vector: 9m, x HV x HWW + R". The GNNs used in this paper can be constructed with the following three steps:
In Gasse et al. (2119) and other related empirical studies, the feature spaces HV HHW are more complicated than those defined in this paper. We only keep the most basie features here for simplicity of analysis.
3

---

Published as a conference paper at ICLR 2023
min + 32, =e2?
MY = (1,2)
w1
1 = (1,-0,3,)
+ 3r2 2,
51 33, 22 5,
22 E2.
by = (1.2)
W2
hw = -1,-00,5,11
Figure An example of MILP--gaphh
(1) Initial mapping at level I 0. Let pd and qº be learnable embedding mappings, then the em- bedded features are sf. = (h. and F = -0 ((())) for i = 1, ........ and 1....... Given learnable mappings s',g'
.......... (2) dassage-passing layers for 2,....., It. update vertex features by the following formulas for all i 1, ..,..,, and 1,2,... ................................ n
".g', ,p', .q', one can
= Σ BasT())) 4= ( D
Eegs' ( (s:-1)
(3a) Last layer for graph-level output. Define a learnable mapping TG and the output is scalar YG = TG(33,, ). where 3 Ex= of and 8 = Σラ= t/.
(3b) Last layer for node-level output. Define a learnable mapping Tw and the output is a vector with entries being yj = rw (5 8 (15) for j 1.2....,,?
y E RR
Throughout this paper, we require all learnable mappings to be continuous following the same set- tings as Chen al. (2022); Aziziin Lelarge (202T). practice, one may parameterize those mappings with multi-layer perceptions (MLPs). Define FaNN as the set of all GNN mappings con- necting layers (1), (2), and (3a). JONN defined similarly by replacing (3a) with (3b).
2.3 MAPPINGS TO REPRESENT MILP CHARACTERISTICS
Now we introduce the mappings that are what we aim to approximate by GNNs. With the definitions, we will revisit questions (QQQ3) and describe them in mathematically precise way.
Feasibility mapping
We first define the following mapping that indicates the feasibility of MILP:
4 teas Gm,n x H. x H. + {0,1),
where Preas (G, HI) i (G, H) corresponds feasible MILP and Prens H) otherwise.
Optimal objective value mapping We then define the following mapping that maps an MILP to its optimal objective value:
Pabj
Pm, x H. x H.W RU (x0, - -00),
where (G, H) = oo implies infeasibility and o H) - oc implies unboundedness. Note that the optimal objective value for MILP may be an infimum that can never be achieved. An
example would be min 21 + TT2 s.t. I1 + πΣZ 2 V2. The optimal objective value is v2, since for any > 0, there exists feasible x with + πT2 < 2 + However, there is no x E 2 such that 2 + 22. Thus, the preimage & 2.7 (R) cannot precisely describe all MILP instances with an optimal solution, it describes MILP problems with a finite optimal objective.
Optimal solution mapping To give a well-defined optimal solution mapping much more com- plicated since the optimal objective value, we discussed before, may never be achieved in some cases. To handle this issue, we only consider the case that any component in / or u must be finite, which implies that optimal solution exists as long as the MILP problem is feasible. More specif- ically, the vertex feature space is limited to H.W (R R x R x (0, C H.W and we consider MILP problems taken from Dastn = (9m,, x HV H.W) the set of all feasible MILPs. Consequently, any MILP instance in Daota admits at least one optimal solution. We can further define the following mapping which maps an MILP to exactly one of its optimal solutions:
feas (1). Note that (+=2(1) describes
2solu D Doolu Droldable + R",
where Dioldable is a subset of Gm,, HV x H.W that will be introduced in Section 4 The full definition of & solu is placed Appendix [ due to its tediousness.
'If we remove the integer constraints / 0 and let MILP reduces to linear programming (LP), the solution mapping will be easier to define. In this case, as long as the optimal objective value is finite, there must exist an optimal solution, and the optimal solution with the smallest norm is unique (Chen et al. (202). Therefore, mapping & salu which maps an I.P to its optimal solution with the smallest fo-nrmm, is well defined on t 65 (R).
4

---

Published as a conference paper at ICLR 2023
Invariance and equivariance Now we discuss some properties of the three defined mappings. Mappings Preas and Pooj are permutation invariant because the feasibility and optimal objective of an MILP would not change if the variables constraints is permutation equivariant because the solution of an MILP should be reordered consistently with the permutation on the variables. Now define Sn the group contains all permutations on the constraints of MILP and Sn, as the group contains all permutations on the variables. For any av S.m and ow E Sn. (w) * (G, H)) denotes the reordered MILP-graph with permutations ov,ow. It is clear that both Pless and Potj are permutation invariant in the following sense: * (G, H)) Poty(G, H)),
reordered. We say the mapping s
Pieus ((ov, ow) * (G, H)) PJeas (G, H), & Ponj [aaj(ov,ov
for all øv E Sm. Ow E Sn, and (G, H) E 9m, x H H In addition, & is permutation equivariant: @solu Bov ow) (G, (G) = ow ( soso (G, H)), for all Øv E Sm. ow E S,y and (G,H) E Daolu' Droldable. This will be discussed in Section C Furthermore, one may check that any F E FGNN is invariant and any Fw E JahN is equivariant.
Revisiting questions (QT,, Q2) and (Q3) With the definitions above, questions { and (33 actually ask: Given any finite set DD C 9m,n Hy HWW is there F E FaNN such that F well approximates teus or Puby on set D? Given any finite set DD C "Duotu (Poodablee is there Fw E GNN
such that Fw is close to Poou on set DD?
3 DIRECTLY APPLYING GNNS MAY FAIL ON GENERAL DATASETS
In this section, we show a limitation of GNN to represent MILP. To well approximate the map- ping & Preas, FUNN should have stronger separation power than Peass: for any two MILP instances (G, H), (G, H)) E Im. X HY HW"
Peeas H) * 4 teeas (G, H) implies F(G, H) + F(G. H) for some F FONN-
In another word, as long as two MILP instances have different feasibility, there should be some GNNs that can detect that and give different outputs. Otherwise, we way that the whole GNN family FONN cannot distinguish two MILPs with different feasibility, hence, GNN cannot well approximate Preas This motivate us to study the separation power of GNN for MILP
In the literature, the separation power of GNN is usually measured by so-called Weisteiler-Lehman (WL) test /Weisfeiler & Leman 1968). We present a variant of WL test specially modified for MILP in Algorithm that follows the same lines as in Chen et al. (2022) Algorithm 1), where each vertex is labeled with a color. For example, vij E V is initially labeled with CO.V based on its feature hy by hash function HASHo,y that is assumed to be powerful enough such that it labels the vertices that have distinet information with distinct colors. After that, each vertex iteratively updates its color, based on its own color and information from its neighbors. Roughly speaking, as long as two vertices in a graph are essentially different, they will get distinct colors finally. The output of Algorithm 1 contains all vertex colors ((C.-.) ) [1C). }) where (0) refers to a multiset in which the multiplicity of an element can be greater than onc. Such approach is also named as
color refinement (Berkholz et al. 2017 Arvind et al. 2015|2017)
Algorithm 1 WL test for MILP-Grapha denoted by WLMIL)
Require: A graph instance (G, H) E 9mm x HY x HW and iteration limit O.
1: Initialize with C. HASHo, (nY), C. = HHSHo, (n))).
2: for 1 = 1, 2, ... L do
3: C.V. HASH, (C.-LV Σド= E.,, HASH, (cl->))
4: C/ = HASH,
(C-- ETh E. HASH' (c.-.)).
5: end for
6: return The multisets containing all colors (1C.- D.m (IC, "
'In Algorithm I the hash functions ( HASH w Him can be any injective mappings defined on given domains, their output spaces consist of all possible vertex colors. The other hash functions (HASH,, v. HASH",w) are required injectively map vertex colors to linear space because we need define sum and scalar multiplication on their outputs. Actually, Lemma 3.2 also applies on the WL test with more general update scheme: C..V HASH, (C.- 1, LC, ({HASHH w (C-_L.W (E.)))).....
HASH, (C (C (P.)).
5

---

Published as a conference paper at ICLR 2023
Unfortunately, there exist some non non-isomorphic graph pairs that WL test fail to distinguish (Douglas 2011]. Throughout this paper, use H)) ~ (G, H) to denote that (G, H) and (G, H) cannot be distinguished by the WL test, i.e. WLMMLP((G, H), WLaAL H),, L) holds for any L E N and any hash functions. The following theorem indicates that FONN actually has the same separation power with the WL test.
Theorem 3.1 (Theorem 4.2 in Chen et al. 2022).. For any (G, H), (G) E Im. x H. x H.W it holds that (G, H) ~ (G. H) if and only if F(G, H) - F(G, H), V E FaNN-
Theorem B.I is stated and proved in Chen et al. (2022) for LP-graphs, but it actually also applies for MILP-graphs. The intuition for Theorem 3.1 is straightforward since the color refinement in WL test and the message-passing layer in GNNs have similar structure. The proof of Chen et al. (2022 Theorem 4.2) basically uses the fact that given finitely many inputs, there always exist hash functions or continuous functions that are injective and can generate linearly independent outputs, i.c., without collision. We also remark that the equivalence between the separation powers of GNNs and WL test has been investigated in some earlier literature (Xu et al. 2019 Azizian & Lelarge 2021; Geerts & Reutter 2022). Unfortunately, the following lemma reveals that the separation power of WI. test weaker than Peess and, consequently, GNN has weaker separation power than feass on some specific MILP datasets.
Lemma 3.2. There exist two MILP problems (G, H) and (G,H) with one being feasible and the other one being infeasible, such that (G, H) ~ (G, H).
Proof of Lemma 3.2 Consider two MILP problems and their induced graphs:
21 + 2/222212 + mg + 14 + 25 + 46 IERS
min
W/y
s.t. 21 21 = 1, 22 23 = 1, 23 -4
1/2
M22
24+ = x 26 1, 0 $1, Yj 11, ... 6).
F3
F3
min
21 21
ZER6
S.l. 21 1,
23 1,
45G
24 1,
26
2
1/B
M/
0 11 1, 2₁ E2 Aj 6)..
Figure 2: Two non-isomorphic MILP graphs that cannot be distinguished by WL test
The two MII.-grrahss in Fugure 2 can not be distinguished by WI. test, which can be proved by induction. First we consider the initial step in Algorithm [ Based on the definitions in Section 2.2 we can explicitly write down the vertex features for each vertex here: h. (1,=), S i S
and h/ 1,, S j S 6. Since all the vertices in V share the same information, they are labeled with an uniform color C..V = Co ... = Co. (We use blue in Figure 2). whatever the C..W
hash functions we choose. With the same argument, and label all vertices in W with red. Both of the two graphs will be initialized in such an approach.
would obtain C C..
Assuming (C/." 16 are all blue and {C,, (.. 1 are all red, one will obtain for both of the graphs in Figure 2 that C C/+IVV = C.+I.V....
I based on the update rule in Algorithm because each blue vertex has two red neighbors and each red vertex has two blue neighbors, and each edge connecting a blue vertex with a red one has weight 1. This concludes that, one cannot distinguish the two graphs by checking the outputs of the WL test.
G and C = C. -.+..
However, the first MILP problem is feasible, since x = 1, 1, O, 1) is a feasible solution, while the second MILP problem is infeasible, since the constraints imply = 2(x1 + x2 + xz) which is a contradiction.
27,
For those instances in Figure 2 GNNs may struggle to predict a meaningful neural diving or branch- ing strategy. In neural diving (Nair et al. 2020 , one usually trains GNN to predict estimated solution; in neural branching (Gasse et al. 2019). one usually trains a GNN to predict a ranking score for each variable and uses that score decide which variable is selected to branch first. How- ever, the analysis above illustrates that the WL test or GNNs cannot distinguish the 6 variables, and one cannot get a meaningful ranking score or estimated solution.

---

Published as a conference paper at ICLR 2023
4 UNFOLDABLE MILP PROBLEMS
We prove with example in Section 3 that one may not expect good performance of GNN to approx- imate Pres on general dataset of MILP problems. It's worth ask: is it possible to describe the common characters of those hard examples? If so, one may restrict the dataset by removing such instances, and establish a strong separation/reprreeetttion power of GNN on that restricted dataset. The following definition provides rigorous description of such MILP instances.
Definition 4,1 (Foldable MILP). Given any MILP instance, one would obtain vertex colors AC,.Y, C.,"" Jas by running Algorithm 1/ S m or 1 S J.J S such that + " for any I E N and any hush finctions. In another word, at least one color in the multisets generated by the WL test always has a multiplicity greater than 1. Furthermore, we denote Dinddube C 9mm. X Hy, x H. as the collection of all (G, H) E 99m.. Hy HW that can be folded.
We say that an MILP instance can be folded, is
foldable, if there exist 1 S i,
=
or "/ i
For example, the MILP Figure i not foldable, while the two MILP instances in Figure are both foldable. The foldable examples in Figure 2 have been analyzed in the proof of Lemma 3.2
and now we provide some analysis of the example in Figure here. Since the vertex features are distinct h # ht one would obtain C * C... as long as the hash function HASHo,w w is injective. Although hy = hy and hence C. = - the neighborhood information of U1 and 02 different due to the difference of the edge weights. One could obtain C..V o C2.V by properly choosing HASHo, w. HASH 1.w HASHI, which concludes the unfoldability.
We prove that, long those foldable MILPs removed, GNN is able accurately predict the feasibility of all MILP instances in dataset with finite samples. We use (F(G, H) 1/2) as the criteria, and the indicator IF(G,))>1/2 1 if F(G, H) 1/2: (F(.IF(G.)))1) 0 otherwise.
Theorem 4.2. For any finile datasel D C 9m,, x H% x H, (Djaldable. there exists E FaNN such that
1//2 = Jean H), A H),
Similar results also hold for the optimal objective value mapping Paby and the optimal solution mapping soolu and we list the results below. All the proofs of theorems are deferred to the appendix.
Theorem 4.3. Let D C Im, Hy H.W DDondable be finite dataset. For any 5 > 0, there exists Fi E FONN such that
TF((G.))>1/2 = TD,,,G,HEER A (G,H)EED
and there exists some F2 E FONN such that [F2(G,
(G,
A H) E DD
obi (R).
Theorem 4.4. Let D C Dasii'D C Sm.n x Hy x H.W (Dolduble be a finite dataset. For any 8 > 0, there exists Fw E F.W GNN such that
[[ H)
1 sotu (G, H) < 8, V(G
Actually, conclusions in Theorems 4.2 and 4.4 can be strengthened. The dataset DD in the three theorems can be replaced with measurable set with finite measure, which may contains infinitely many instances. Those strengthened theorems and their proofss can be found in Appendix
Let us also mention that the foldability of an MILP instance may depend on the feature spaces HV and HW If more features are appended (see Gasse et al. 2019)). i.e., by and hy have more entries, and then a foldable MILP problem may become unfoldable. In addition, all the analysis here works for any topological linear spaces H. and H., long as Prcass Pobj. and o can be verified as measurable and
mappings.
5 SYMMETRY BREAKING TECHNIQUES VIA RANDOM FEATURES
Although we prove that GNN is able to approximate P Pabj, & to any given precision for those unfoldable MILP instances, practitioners cannot benefit from that if there are foldable MILPs in their set of interest. For example, for around 1/4 of the problems in MIPLIB 2017 GGeixnnr al. 2021 the number of colors generated by WL test is smaller than one half of the number of vertices, respect to the H and H used in this paper. To resolve this issue, we introduce technique inspired by
7

---

Published as a conference paper at ICLR 2023
Abboud et al. 22200; Sato al. (2021). More specifically, append the vertex features with an additional random feature w and define a type of random GNNs as follows.
Let Ω [0, 1 x |0, 1 and let (R, IP) be the probability space corresponding to the uni- form distribution ( The class of random graph neural network JOHN with scalar output is the collection of functions
FR Imm x H HW x Q - (G, HW
R,
+ FR(G,H,,),
which is defined in the same way as FANN with input space being 9m, X Hy x H.th x Ω Sm, x (H. x [0, 11) x (HW x [0, 1))" and w being sampled from U(?). The class of random graph neural network GNN with vector output is the collection of functions
Fw,R 9mm x Hy x HW x Ω (G, H,))
R"
Fw,n(G,H,w),
which defined in the same way as FONN with input space being 9m., x H. HW x Ω Im, x (H [0, 1))m (HW [0, 1))" and w being sampled from U(2).
By the definition of graph neural networks, Fn is permutation invariant and Fw.n is permutation equivariant, where the permutations σy and ow act on (HL x [0, 1))" and (7t x [0, 1])".. We also write FR(G, H) = (R.G. H.w) and FW, H) Fw.n(G, H.w) as random variables. The theorem below states that, by adding random features, GNNs have sufficient power to represent MILP feasibilityy, even including those foldable MILPs. The intuition is that by appending additional random features, with probability one, each vertex will have distinct features and the resulting MILP- graph is hence unfoldable, even if is foldable originally.
Theorem 5.1. Let D C gm, XHY x x be a finite dataset. For any > there exists Fn FR such that
IP (Inn(a,M))1122 + Deear @ (G,H) <e, (G, e D. Similar results also hold for the optimal objective value and the optimal solution.
Theorem 5.2. Let D gm, Hy H. be a finite dataset. For any e, > O, there exists FR,1 F GNN such that
P (L # Lo (G.,HE)) <e, ()
and there exists FR,2 FR GNNY such that
IP ([ H) Doty(G H)] 8)< H( (R).
Theorem 5.3. Let D C 2 C Gm, x HV H.W be finite dataset. For any e, 8 > 0, there
R exists FW.RR E F- GNN such that
F(] H) 2
8) <e, <E, (G,
The idea behind those theorems is that GNNs can distinguish H,W) and (G, H. () with high probability, even they cannot distinguish (G, H)) and (G, il). How to choose the random feature in training is significant. In practice, one may generate one random feature vector w E [0, 1] [0. 1 for all MILP instances. This setting leads to efficiency in training GNN models, but the trained GNNs cannot be applied datasets with MILP problems of different sizes. Another practice is sampling several independent random features for each MILP instance, but one may suffer from difficulty in training. Such a trade-off also occurs in other GNN tasks (Loukas) 2019 Balcilar al.) 2021). In this paper, we generate one random vector for all instances (both training and testing instances) to directly validate theorems. How to balance the trade-off in practice will be an interesting future topic.
6 NUMERICAL EXPERIMENTS
In this section, we experimentally validate our theories on some small-scale examples with 6 and n = 20. We first randomly generate two datasets D2 and D2. Set D2 consists of 1000 randomly generate MILPss that are all unfoldable, and there are 460 feasible MILPs whose optimal solutions are attachable while the others are all infeasible. Set D: consists of 1000 randomly generate MILPs that all foldable and similar to the example provided in Figure 2 and there 500 feasible
8

---

those unfoldable Published as a conference paper at ICLR 2023
MILPss with attachable optimal solution while the others infeasible. We call SCIP (Bestuzheval et al. 202 la b). a state-of-the-ar non-commercial MILP solver, to obtain the feasibility and optimal layers as L = 2 and parameterize all the learnable functions fi yW Son: fo { I si g6 }(=0 as multilayer perceptrons (MLPs). Our codes modified from Gasse al. (2019) and released https: 7/github. com/ won/iiujjilgiiii Miliii//tNNNNN CENN-MILP git, All the results reported in this section are obtained on the training sets, not an separate testing set. Generalization tests and details of the numerical experiments can be found in the appendix.
solution for each instance. In GNNs, set the number of m
Feasibility We first test whether GNN can rep- resent the feasibility of an MILP and report our results in Figure 3 The orange curve with tag "Foldable MILPs presents the training result of GNN on set D2. It's clear that GNN fails to dis- tinguish the feasible and infeasible MILP pairs that are foldable, whatever the GNN size we take. However, if we train GNNs MILPs in set D1 it's clear that the rate of errors goes zero, as long as the size of GNN is large enough (the number of GNN parameters is large enough). This result validates Theorem 4.2 and the first conclusion in Theorem 4.3 the existence of GNNs that can accurately predict whether an
0.5
Rate of error
0.4
Unfoldable MILPs
Foldable MILPs
0.2
Foldable Rand Feat.
0.1
0.0
10a
10a
10a
Num. of GNN parameters
Figure 3: Feasibility
MILP is feasible (or whether MILP has finite optimal objective value). Finally, we append additional random features to the vertex features in GNN. As the green curve with tag "Foldable + Rand Feat." shown, GNN can perfectly fit the foldable data D2, which validates Theorem 5.1 and the first conclusion in Theorem
Optimal value and solution Then we take the feasible instances from sets Dj and D2 and form new datasets Dfcasible and Dfcassibee respectively. On Dicassible and Dicusiibe, we validate that GNN able to approximate the optimal objective value and one optimal solution. Figure 4a shows that, by restricting datasets to unfoldable instances, or by appending random features to the graph, one can train a GNN that has arbitrarily small approximation error for the optimal objective value. Such conclusions validates Theorems 4.3 and 5.2 Figure 4b shows that GNNs can even approximate an optimal solution of MII.P, though it requires a much larger size than the case of approximating optimal objective. Theorems 4.4 and 5.3 validated.
Unfoldable MILPs
10a
Mean squared error
Mean squared error
Foldable + Rand Feat.
0.10
10
0.05
10-3
Unfo ldabe MILPs
Foldable Rand Feat.
0.00
10a
10
10
10*
10
10
107
Num. GNN parameters
Num. of GNN parameters
(a) Optimal objective value
(h) Optimal solution
Figure 4: GNN can approximate Pobj. and o solu
7 CONCLUSION
This work investigates the expressive power of graph neural networks for representing mixed-integer linear programming problems. It is found that the separation power of GNNs bounded by that of WL test is not sufficient for foldable MILP problems, and in contrast, approximate characteristics unfoldable MILP problems with arbitrarily small error. To get rid of the requirement random feature is discuss with theoretical guarantee. We conduct numerical experiments for all the theory. This paper will contribute the recently active field of applying GNNs for MIL .P solvers.
show that GNNs can
unfoldability which may not be true in practice, technique of appending

---

Published as a conference paper at ICLR 2023
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01179, 2020.
Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. A supervised machine learning approach to variable branching in branch-and sothh-and-booudd In In ecml. Citeseer, 2014.
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. On the power of color refinement. In International Symposium on Fundamentals of Computation Theory, pp. 339-350.
Springer, 2015.
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky, Graph isomorphism, color refinement, and compactness. computational complexity, 2673):627-685, 2017.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural net- works. In International Conference on Learning Representations, 2021.
Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Con- ference on Machine Learning, pp. 599-608 PMLR, 2021.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: a methodological tour d d'horizon. European Journal of Operational Research, 290(2): 405-421 2021.
Christoph Berkholz, Paul Bonsma, and Martin Grohe. Tight lower and upper bounds for the com- plexity of canonical colour refinement. Theory of Computing Systems, 60(4):581-614, 2017.
Timo Berthold, Matteo Francobaldi, and Gregor Hendel. Learning to use local cuts. arXiv preprint arXiv:2206. 11618, 2022.
Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Mare E. Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Well- ner, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 8.0. Technical report, Op- timization Online, December 2021a. URL httpthttp/////t opt zat on-on on ine .nn.org// org/ html
DB
Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Fifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Mare E. Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Well- ner, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 8.0. ZIB-Report 21-41, vi ng de durunnn:.. nnoo:
Zuse Institute Berlin, December 2021b. URL http:://bnnnntt
de: 0a:0299-22 - 85309
Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing linear pro- grams by graph neural networks. arXiv preprint arXiv:2209. 12288, 2022.
Jian- Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang. Yinghui Xu, and Le Song. Ac- celerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 1452-1459, 2020.
Brendan L Douglas. The weisfeille-lehmman method and graph isomorphism testing. arXiv preprint a /01.5/11, 2011.
10

---

Published as a conference paper at ICLR 2023
Lawrence C Evans and Ronald F Garzepy. Measure theory and fine properties of functions. Rout- ledge, 2018.
Christodoulos A Floudas and Xiaoxia Lin. Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Annals of Operations Research, 139(1)1111112, 2005.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Floris Geerts and Juan L Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations, 2022.
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp M. Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, and Yuji Shinano. MIPLIB 2017: Driven Compilation of the 6th Mixed Integer Programming Library. Math ematical Programming Computatioon, 2021. doi: 10.1007/s 12512-0202-2222222 020-00094-3.. hRthets:: ordoi.org/ 10. http:////....101/122222-00000000 020-2099-0-00000-000000000
Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neural information processing systems, 33:
18087-18097, 2020.
Prateek 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.1490 2022.
He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27,201 2014.
Zeren Huang, Kerong Wang, Furui Liu, Hui-Ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning to select cuts for efficient mixed-integer programming. Pattern Recognition, 123: 123:108353, 2022.
Elias Khalil, Pierre Le Bodic, Le Song. George Nemhauser, and Bistra Dilkina. Learning branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guid- ing combinatorial solvers. Update, 2:x3, 2022.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 11Xiv:1412.6980, 2014.
AH Land and AG Doig. An automatic method of solving discrete programming problems. Econo- metrica: Journal of the Econometric Society, pp. 497-520, 1960.
Jiacheng Lin, Jialin Zhu, Huangang Wang, and Tao Zhang. Learning branch with tree-aware branching transformers. Knowledge-Baud Based Systems, 252:109455, 2022.
Andreas Loukas. What graph neural networks cannot learn: depth width. In International Con- ference on Learning Representations, 2019.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Con-
ference on Learning Representations, 2020.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349 2020.
Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International Conference Machine Learning, pp. 17584-17600. PMLR, 2022.

---

Published as a conference paper at ICLR 2023
Qingyu Qu, Xijun Li, Yunfan Zhou, Jia Zeng, Mingxuan Yuan, Jie Wang, Jinhu Lv, Kexin Liu, and Kun Mao. An improved reinforcement learning algorithm for learning to branch. arXiv preprint arXiv:2201.06213, 2022.
Arthur Richards and Jonathan How. Mixed-integer programming for control. In Proceedings of the 2005, American Control Conference, 2005., pp. 2676-2683, IEEE, 2005.
Walter Rudin. Functional Analysis. International series in pure and applied mathematics. McGraw- Hill, 2nd edition, 1991. ISBN 9780070542365.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. Advances in Neural Information Processing Systems, 32, 2019.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333-341. SIAM, 2021.
Lara Scavuzzo, Feng Yang Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. Learning to branch with tree mdps. arXiv preprint urXiv:2205. 11707, 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. 6603-2608. IEEE, 2001.
Yunzhuang Shen, Yuan Sun, Andrew Eberhard, and Xiaodong Li. Learning primal heuristics for mixed integer programs, In 2021 International Joint Conference on Neural Networks (IJCNN), pp. 8-8. IEEE, 2021.
Jialin Song, Yisong Yue, Bistra Dilkina, et al. general large neighborhood search framework for solving integer linear programs. Advances in Neural Information Processing Systems, 33; 20012-20023, 2020.
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning cut. In International conference on machine learning, pp. 9367-9376. PMLR, 2020.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Kaan Yilmaz and Neil Yorke- Learning efficient search approximation in mixed integer branch and bound. arXiv preprint arXiv:2007.03940 2020.
Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and-bound search trees to learn branching policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3931-3939, 2021.
12

---

Published as a conference paper at ICLR 2023
A PROOFS FOR SECTION
In this section, we prove the results in Section i.c., graph neural networks can approximate Preas Pabj. and 4 solus on finite datasets of unfoldable MILPs with arbitrarily small error. We would con- sider more general results on fmite-measure subset of Im.n Hy H which may involve infinite elements.
In our settings, foldability is actually a concept only depending on the MILP instance. In the main text, we utilize the tool of the WL test to define foldability here for readability. Here we present more complex but equivalent definition merely with the language of MILP.
Definition A.1 (Foldable MILP). We say that the MILP problem (2.I) can be folded, or is foldable, if there exist I = {I1, .2, Is} and J = J,...., Jt) } that are partitions of {1, (1.,...., m) and (1.2..... n., respectively, such that least one of and J is nontrivial, i.e., < m that the followings hold for any .1. .5 and E (1,2.....l) ,,: vertices in {vs : i Ip) share the same feature in HV, vertices in {w, : Jq} share the same feature in HW and all column sums (and row sums) of the submatrix (A.))EET,. are the same.
< n, and
According to Chen al. (2022 Appendix A), the color refinement procedure of the WL con- verges to the coarsest partitions I and J satisfying the conditions in Definition A. assuming no collision happens. Therefore, one can see that Definition 4.1 and Definition A. are equivalent.
Before processing to establish the approximation theorems for GNNs on 9m.n x H x HW (D Pooldables let us define the topology and the measure on gm, X HY x H.W.
Topology and measure The space 9m. x Hy x H.W can be equipped with some natural topology and measure. In the construction of Im,n x H. H.W. let all Euclidean spaces be equipped with standard topology and the Lebesgue measure; let all discrete spaces equipped with the discrete topology and the discrete measure with each elements being of measure 1. Then let all unions be disjoint unions and let all products induce the product topology and the product measure. Thus, the topology and the measure 9m, H. x H. defined. We use the notation Meas(.) for the measure Gm,n H. H.W.
Now we can state the following three theorems that can be viewed as generalized version Theo- rem and 4.4
Theorem A.2. Let X C Gm, Hy HW Dirtdable be measurable with finite measure. For any 6 > 0, there exists some F FaNN, such that
Meas HH E IF(G, # Jeas (G, H))) <G, where I. is the indicator function, iee, TF(G, = if H) > 1/2 and FFGG.H)21/2 = otherwise.
Theorem A.3. Let X Im,n HY HW (Djotdbble be measurable with finite measure. For any e, 8 > 0, the followings hold:
(i) There exists some Fi E FGNN such that
Meas (L(G, H) E x :TT, (G,, <e.
(ii) There exists some F2 E FONN such that
Meas (((G,)) oby (B) (F2(G, - (G) 68) <c.
Theorem A.4. Let X C DDotu PooturP Diuudable Im. x HY x HW (Djoddbble be measurable with finite measure. For any 5 > 0, there exists Fw E GNN such that
Meas (L(G, E X (G, 2 (G,tt(G,Au H)|l 83) <.
The proof framework similar to those in Chen et al. (2022). and consists two steps: i) show that measurability of the target mapping and apply Lusin's theorem to obtain continuous mapping
13

---

Published as a conference paper at ICLR 2023
compact domain; ii) use Stone- Weierstrass-type theorem to show the uniform approximation result of graph neural networks.
We first prove that Ptaas and Lobj are both measurable in the following two lemmas. The optimal solution mapping ssolu will be defined rigorously and proved as measurable in Section
Lemma A.S. The feasibility mapping feas 9m. H H {0.1] is measurable.
Proof. It suffices to prove that leus (1) is measurable, and the proof is almost the same as the that Chen et al. 2022 Lemma F.I). The difference is that should consider any fixed T E {0, 1)" Assuming 7 (0, .0........ 0, 1, .......,] where 0 and 1 appear for and n & times respectively without
loss of generality, we replace I= and Q" in the proof of Chen et al. 2022 Lemma F.1) by
R x zn and @ x zn-k to get the proof in the MILP setting.
Lemma A.6. The optimal objective value mapping Poby 9m HY H. R [00, -00) is measurable.
Proof. Consider any Φ E I. Doy < o if and only if for the MILP problem associated to
(G, H), there exists a feasible solution x and some r E N such that c x S 1/r. The rest of the proof can be done using the same techniques as in the proofs of Chen al. (0022 Lemma F.1 and Lemma F.2). with the difference pointed in the proof of Lemma A.5
The Lusin's 's theorem, stated follows, guarantees that any measurable function can be constricted on compact such that only a small portion of domain is excluded and that the resulting function is continuous. The Lusin's theorem also applies for mappings defined on domains in 9m,n x XHY x H.W This is because that 9m. H% H.W isomorphic the disjoint union of finitely many Euclidean spaces.
Theorem A.7 (Lusin's ' theorem (Evans& & Garzepy 2018 Theorem 1.14)). Let μ be a Borel regular measure Tn and let f R Rddh be p-measurable. Then for any j-measurable X C B with (XX)= < co and any > 0, there exists a compact set C C with EEX(E) < c, such that flg g is continuous.
The main tool in the proof of Theorem A.2 and Theorem A.3 is the universal approximation property of FUNN stated below. Notice that the separation power of GNNs is the same as that of WL test. Theorem A.8 guarantees that GNNs can approximate any continuous function on a compact set whose separation power less than or equal to that of the WL test, which can proved using the Stone Weierstasss theorem (Rudin) 1991. Section 5.7).
Theorem A.8 (Theorem 4.3 in Chen et al. (2022)). Let C &mmn x HV x H. be a compact set. For any & C(X, I) satisfying
(G, (G, (G,
(A.1)
and any e > O, there exists F E FUNN such that
sup (G,H)eX
[ - H) <t.
(A.2)
Let us remark that the proof of Chen et al. 2002 Theorem 4.3) does not depend on the specific choice of the feature spaces H and H which only requires that HV and H are both topological linear spaces. Therefore, Theorem A.8 works for MIl.P-graphs with additional vertices features.
For the sake of completeness, Gm,n x H. x HW W + Gm. x H. x H / ~ be the quotient. Then for any continuous func- tion F: "mm. x HY HW + IR, there exists unique E. 9m. H. x HW / /~ R such that F Fon. Note that FANN := (F F E FGNN) separates points in Gm, x HV x xHW by Theo- rem 3.1 By the Stone-Weieree Weierstrass theorem, there exists F FANN with EiG [TTTG, (TGHH)) < c, which then implies A.2).
outline the proof of Chen al. (022) Theorem 4.3): Let
Similar universal approximation results for GNNs and invariant target mappings also be found in earlier literature; see e.g. Aziziann & Lelarge (202T); Geerts Reutter (2022). With all the preparation above, we can then proceed present the proof of Theorem A.2
14

---

Published as a conference paper at ICLR 2023
For applying Theorem A.8 one need verify that the separation power of Preas and Potj bounded by that of WL test for unfoldable MILP instances, i.c., the condition (A.I). For any (G, H), (G, H) E 9m.n x Hy x H
A (iislaable since they are unfoldable, WL test should gen- erate discrete coloring for them if there is collision. If we further assume that they cannot be distinguished by WL test, then their stable discrete coloring must be identical (up to some permu- tation probably), which implies that they must be isomorphic. Therefore, we have the following lemma:
Fny Lemma A.9. For any (G, H), (G, it) Im. HYy H.W Djoldable holds that (G, (G) (G, it)
if and only if (G, H) and (G, H) are isomorphic, i.e. (wv * (G, = (G; H) for some Ov Sm and ow E Sn-
Let us remark that Lemma A.9 true for any vertex feature spaces because the following proof does not assume the structure of the feature spaces.
Proof. It's trivial that the isomorphism of (G, H) and (G, implies (G, (G, H), and it suffices show (G, H1) (G, implies the isomorphism.
Applying Algorithm on (G, H) and (G, f) with a common set of hash functions, we define the outcomes respectively:
[[0] L. (CC// Dam UC,, Dy= WL (GG,
"Cr"")m HC }) :LWMM. WLL.mP((C (G,,H),,
H), L).
Then (G, H) ~ (G. H) can be written as [1C. }1 {(c. Jo and (1C DD (10 W }
(A.3)
for all L E N and all hash functions. We define hash functions used in this proof.
We take hash functions HASHo, v, HASHo, w such that they are injective on the following domain: {h/ ky RY Ay :1s m, S S n).
Note that {-} means a set, but not a multiset. The above set collects all possible values of the vertex features in the given two graphs (G, H) and (G. H). Such hash functions exist because the number of vertices in the graphs must be finite.
Forl (,,2, ,L, define a that collects all possible vertex colors at the /- 1-th iteration,
C--1 == :- B00-LVcc--- C .C C1-1. : :13 i m, S S n).
Note that |C--1 is finite. The two sets (HASH), : C Ct-1) and (HASH( w (C) Ct-1} can be linearly independent for some hash functions HASH',,.AAHH,W. This is because that one can take the output spaces of HASH/ v. HASH(,w as linear spaces of dimension greater than [C Given such functions HASH, v. HASH' we consider the following set
Fr. HASH (cI-LW)
isism m
Gl
I.V. Σ
B.,HASH (CH-IW)
asis
j=1
c
1.- Σ
E. HASH, (CI-LP)
issiSn
1=1
O AL-LW
B BASHA
(CI-V))
:15j5n
which is finite set given any two graphs (G, H) and (G, fi. Thus, one can pick hash functions HASH.v HASH that are injective on the above set.
15

---

Published as a conference paper at ICLR 2023
Due to the statement assumption that (G, H) and (G, H) are both unfoldable and the definition of the above hash functions, one can obtain that
C... + CV. Viti, G * Cj Vi C... + CV., Viti' Cf + C... vi+s'
(A.4)
for some L E N. In another word, in either (G, H) or (G, H), each vertex has an unique color. Combining A.3 and (A.4). we have that there exists unique ov Sm and dw Sn such that
C... C "v(()) C. = c =i=
m.j ...
In addition, the vertices with the same colors much have the same neighbour information, in- cluding the colors of the nerighbourhood and weights of the associated edges. Rigorously, since H HASHL, are both injective, one will obtain that
C CL-1V CoTt) C GL-1.W CL-1W ow(i)>
HASH', (OT-LIM)=
Σ Bor(), (cH-1.M).
Σ HASHAL (o--LV) Σ (A (c.-L.)).
Now let us consider the second line of the above equations,
E HASH,, (CH-L.))
Boy (1. HASH,,, (cH-1,))
E () (Chwlit
(o HASH (C)-1.))
Therefore, holds that
Σ
[is Eor(h) HASH',, (0C-1.8) =0.
This implies that E..y For because (HASHL,w( C CL-13 are linearly indepen- dent. Then one can conclude that (av, (G, H) = (G, (G,H). M.
Now we can proceed to present the proof of Theorem A.2
Proof of Theorem 4.2 According to Lemma A.5 the mapping T Pless Im,, x HVV x H -> {0,1) measurable. By Lusin's theorem, there exists compact E X C 9m, HV x HW W (Piolable such that ieas E: is continuous and that Mcas E) < e. For any H), (G, H E E, if (G, H) ~ (G, Hf), Lemma A.9 guarantees that ie (eensG,, H) Dress(G fl). Then using Theorem A.8 one can conclude that there exists F FUNN with
sup IF(G, Press (G, H) < 1 (G.H)EE
This implies that
Meas (((G,H) X II(G,))21/2 # 4rems (G) Meas(X)B) e.
Similar techniques be used prove sequence of results:
16

---

Published as a conference paper at ICLR 2023
Proof of Theorem 4.2 D is finite and compact and Pras p is continuous. The rest of the proof
follows the same argument as in the proof Theorem A.2 using Lemma A.9 and Theorem A.8
Proof of Theorem A.3 Pobj is measurable by Lemma A.6 which implies that
(aj Im. x H. H. + {0,1),
also measurable. Then (i) and (ii) can be proved using the same argument in the proof of Theorem A.2 for and (.(()))) as well as n db
101 (IR and Pooj. respectively.
Proof of Theorem 4.3 D is compact and (e) restricted on D is continuous. In addition, as (R]) nonempty, it is compact and Patj restricted on D n o o (R) continuous.
long D n @ obj
Then use Lemma A.9]and and Theorem A.8 to obtain the desired results.
Now we consider the optimal solution mapping ssolu and Theorem A.4 for proving which one needs universal approximation result of JGNN for equivariant functions. For stating the theorem
rigorously, we define another equivalence relationship on Im, H H.W (G, H) W (G, H) (G (G, H) and in addition, C. = - Vjj E (1.2...., n), for any L E N and any hash functions.
The universal approximation result of GNN is stated as follows, which guarantees that FGNN can ap- proximate any continuous equivariant function compact whose separation power less than or equal to that of the WL test, and is based on generalized
theorem established
in Azizian & Lelarge 202I).
Theorem A.10 (Theorem E.1 in Chen al. (2022)) Let X C. Gm,xXHY xHW be compact subset that closed under the action of Sm x S.. Suppose that & E C(X, satisfies the followings:
For any ov Sms ow Sn, and (G, I1) X, it holds that ① ((ov,ow) (G, H)) = =
(ii) G H) -G H) holds for all (G, H), (G, M) x with (G, H) W. (G. A.)
(iii) Given any (G, H) X and any i.j E ( if C = C.W holds for any e N and any choices of hash functions, then & (G, H); = ( H)j-
Then for any > 0, there exists Fw E FNN such that
sup (G,8)eX
[[ Fw H) <e.
Similar to Theorem A.8 Theorem A. 10 is also true for all topological linear spaces HV and H" We refer to Azizian & Lelarge (2021); Geerts Reutter (2022) for other results on the closure of equivariant GNNs. Now
prove Theorem|A.4 and Corollary 4.4
Proof of Theorem A.4 We can assume that X C D DTollable C Gm, x HV x HW (Dioldblee is close under the action of Sm x Sn, since otherwise one can replace X with Ulov lee..a xs. (ov,ow) ow) X. The solution mapping Psolu Daolu Proldable is measurable by Lemma C.5 According to Lusin's theorem, there exists a compact E' C X C Daotu D Dioldable with
Meas X E < S/ Snl such that @ ler is continuous. Let set
n
(ov,ow) * F CX,
(ov (ov JESM S..
which is compact and is closed under the action of S. Sn. Furthermore, it holds that
Meas(A X EE = Meas
X
n
(av,ow) E
(ov.ow)ESm.e XSS
17

---

Published as a conference paper at ICLR 2023
E
Meas(X)(ove) E*)
(o JES xS. Smm x Snl Meas X (E))
c.
For any (G, (G, H), (G, E Ef, H) W (G, H), similar Lemma A.9 know that there exists
OV Sm such that Id) HG H) H). Then by the construction of $ solu Section C
one has that so (G, H) s G. it) E R". Condition (i) in Theorem A. is satisfied by
the definition of Ssoiu (see Section G and Condition (iii) in Theorem AA.1 follows from the fact
that WL test yields discrete coloring for any graph in Gm. x Hy x Hen (Dioldble-- Then applying
Theorem A.10 one can conclude that for any > O, there exists Fw E FW with
sup |FW(G: H) solu H) < 6. (G,H)EE
Therefore, holds that
Meas (I(G, E X: [GW Psolu sso H)|l 83) - MMass <
which completes the proof.
assume that the finite dataset DD Doolu' Droldablo is closed under the action of Sm x Sn- Otherwise, we can replace 'D by U(ov JES s., (ov,ow) D.
Proof of Theorem 4.4 Without loss of generality,
Note that D compact and Pssiu/ continuous. The rest the proof can done by using similar techniques in the proof of Theorem A.4 with Theorem A.10
B PROOFS FOR SECTION
We collect the proof of Theorem 5.1 Theorem 5.2 and Theorem 5.3 in this section. Before we proceed, remark that the following concepts are modified as follows in this section due to the random feature technique:
The space of MILP-graph. Each vertex in the MILP-graph is equipped with an additional feature and the entire random vector sampled from w E Q == [0, 1 x [0, 1]a. More specifically, we write:
= (w> w) (WY, ... w. w
w
Equipped with random feature, the new vertex features are defined with:
h // (h. wY), hy. (hy ) v1 m, n. The corresponding vertex feature spaces are defined with:
H.V.R. : = H. 1 (H x 1),
H W.R. = H. x (0, 10. n WH 10. 1))..
The corresponding graph space is Gm, x HV.R x WWR and is isomorphic to the space defined in the main text:
Im,, HV HW Ω Gm, H.V.R H.W.R
(B.1)
Note that the two spaces are actually the same, merely defined in different way. In the main text, we adopt the former due to its simplicity. In the proof, we may either use the former the latter according to the context.
Topology and measure. We equip Ω with the standard topology and the Lebesgue measure. Then the overall space Gm. x H. x HW Ω can be naturally equipped with the product topology and the product measure.
18

---

Published as a conference paper at ICLR 2023
Key mappings. On the space (with random features) Imn Hm x H 22 the three key mappings can be defined with
Peas (G, H,w) : 1 feas (G, H);
Ponj (G, H w) Day G, H):
4 sol (G, H, - (G, H),
for all E 22 This is due the fact that the feasibillity, objective and optimal solution only depend on the MILP instance and they are independent of the random features appended.
Invariance and equivariance. For any permutations ov E Sm and ow E Sn, (av, (ev,,w)sr denotes the reordered MILP-graph (equipped with random features). We say function FR is permutation invariant if
x (G, H. w)
Fa((ov, ow) (G, H,) "FR(G,H,u)
for all ov Sm. ow Sn, and (G, W. E Gm, H. x H... And we say function Fw.R is permutation equivariant if
Fw,n(lov, (G, H,w)) = ow (Fw,w H,w)),
for all σy E Sm, ow E Su. and (G, H, E 9m., x Hy. x H.R.R It's clear that iteus and Pabj are permutation invariant, and soln is permutation equivariant. Furthermore, it holds that any FR E FONN is invariant and any FW.R FONN is equivariant.
The WL test. In the WL test, vertex features ny Ai replaced with h.. and the corresponding vertex colors are denoted by C.V.R.CC..W.B
R .h .y.. respectively, R in the 1-th iteration.
Initialization:
C.O.V.R HASHo, (h R,
C. CO.W.R HASH W (h (.W.)..
For / = 1,2, ... ,, C. C.V.V. HASHEV 1.2,...,
C CL-VVR
E BASHASH W (C.-
For 1 = 1,2, L C. HASH,
C Cl-1...R
Eag BASHASH (c.-
(B.2)
Note that the update form of (B22) is equal to that of Algorithm ! and the only difference is the initial vertex features.
The equivalence relationship. Now let us define the eguivalence relationships ~ and W the space equipped with random features gm,n Hy x HW Ω2. Given two MILP- graphs with random features (G, H,)) and (G, H,W), the outcomes of the WL. test are W. pm (10 115-0 respectively. We say ((C....111 H.C.....).. and (1OL.V 1 H,W) (.)
[[C..W.R (10 (. 1 (( and [[c, 137 = (10 11
for all for any L N and any hash functions. We say (G, H w) W. (G, H. () if (G, H,w) ~ (G. H, @) and in addition, C.R. &.R.RR V e .l, for any L E N and any hash functions.
Foldability. Suppose the vertex colors corresponding to (G, are C. C C. Then say (G, H,) is foldable if there exist 1 S i, m j.j S such that
C. C.V.V. V.V.R. i i f, or C.W.R. C j
for all | N and any hash functions.
By merely replacing hy h. with h. V.R. h W. we define all the required preliminaries. According to the remarks following Theorem [A8] Lemma A.9 and Theorem A. we are able to directly apply these theorems and lemmas the space Gm. x HV.R H.W where HV.R corresponds to HY and H. corresponds to HW
19

---

Published as a conference paper at ICLR 2023
Proof of Theorem 5.7
Define
Up = (1, (1,2....., 8.1. wp = w
(B.3)
or or E (1,
n), s.t. w/ = w }.
Given any (G, H) E 9m, x Hm x H as long w & Sp, different vertices in V W are equipped with different vertex features:
V.R
V.R. Vi Vi + h
h W. + ,yy W.R. Vj
and consequently, each of the vertices possesses unique initial color:
C. C.V.RR
* CV
C.V. Vi C...R * Cj. R.W.R. Vj
for some HASHO, and HASHo, w. In another word, although (G, H) may be foldable, (G, H, must be unfoldable as long as Qpp.
Therefore, for any (G, W), (G, ()) Im, XHY H x (AARp)) it holds that both (G, H, and (G, H. ()) are unfoldable. Applying Lemma A.9 we have (G, H.w) ~ (G, H, ()) if and only (ov, ow) * (G, H) (G, H,)) for some ov E Sm and ow E Sn. The invariance property of less implies that
T leas (G, H, teas H,H, A (G, (G, H. Gm,a Hy H. x (S)Sp)-
In addition, the probability of w E Op is zero due to the uniform distribution o P(L2)) For any > 0, there exists a compact subset Ω C 12p such that
P()))) IP ((9)
Note that X Q2 is also compact and that ieas is continuous on X Ω2 The continuity of Press DxQ. follows from the condition that D is finite dataset and that the fact that any mapping with discrete finite domain is continuous (note that Piegs (G, H.W), w) is independent of w Ωt)) Ap- plying T.. for Diess and D Ue C gm,n H.V.t. H.W.t, one can conclude the existence of F F with GNN
W.Rt
1
sup (
FR( Preas (G, H, W)] <
Since Piess is independent of the random features w, the above equation can be rewritten as
sup (G,H,)eDxL,
[R H. Pieas (G, H)]
thus holds for any (G, H) e D that
IP (TFR # Prem (G, < P(1)).).) <c
Proof of Theorem 5.2 The results be obtained by applying similar techniques as in the proof of Theorem 5.1 for (..))) eR and Pat--
Proof Theorem 5.3 Without loss of generality, we can assume that D is closed under the action
of Sm x Sn; otherwise, we can use {(ār,aw) * (G. H) (G, H) E D.ov E Sm. ow E S,} instead of 'D. Let 22 Ω be the set defined (B.3) which clearly closed under the action of Sm x Sn. There exists compact D2 C F8Pp with ((2))))) P(( < e//Sm. x Sal- Define
Ω
n
(ov,ow) Ω C 990F
(av.ow J.S. xS. which is compact and closed under the action of Sm Sn, One has that
P())))) P [2)
(ov,ow) * S2
(eV. xS.
20

---

Published as a conference paper at ICLR 2023
Σ
P(N)(or, * 92))
( xS.,
= 15m Sn1. ((S)))))
<.
In addition, D x S2 is compact in Im, x (HV x 10, R x (HW W x 10, 1)) and is closed under the action of Sm x Sn.
We then verify the three conditions in Theorem A. 10 for ssolu and D x Ωg Condition (i) holds automatically by the definition of the optimal solution mapping. For Condition (ii), given any (G, H))) and (G, H. @)) in D Qg with (G, H.w) W (G. H.,.,, since graphs with vertex fea- tures in D x Qh C Im. x Hy x HW X (2)pp) cannot be folded, similar to Lemma A.9 one can conclude that H,))
(G,H,w) for some E Sn, which leads to Psolu H) solu (G, H). Condition (iii) also follows from the fact that any graph in D S2 cannot be folded and WL test yields discrete coloring. Therefore, Theorem A.10 applies and there exists FW.R& E FW. such that
(ov,
[Fw,n H,w) soou (G, H)ll < ().H,
sup
which implies that
P F(I - ssolu ( (G, > 8) ((()))) <e, ((,
more deeper observation that, Theorem 5.1 Theorem 5.2 and Theorem A.3 are actually true even if we only allow one passsage-passingg layer in the GNN structure. This is because that the separation power of GNNs with one message-passing layer the same as the WL test with one iteration (see Chen el al. (2022 Appendix C)), and that one iteration in WL test suffices to yield a discrete coloring for MIL.P -allpps gm. X Hy x HW x (1))
Remark B.1.
C THE OPTIMAL SOLUTION MAPPING PSOLU
In this section, we define the equivariant optimal solution mapping & and prove the measurabil- ity. The definition consists of several steps.
C.1 THE SORTING MAPPING
We first define a sorting mapping:
Poot : Gm. x H.Y. x H:t DDroldable - Sn.
that returns a permutation on {W1, W2.... W Dioldable is the collection of all foldable MILP problem in Definition 4..1 This can be done via order refinement procedure, similar the WL test. The initial order as well as the order refinement are defined in the following several definitions.
Definition C.1. We define total order on H. and H. using lexicographic order:
For any (b,, ot), (b),,v) ov) HV RR =1 we say (b,, o.) (bv,oz) if one of the followings holds:
b; < by.
b, by and ((o;) < ((or), where -5,)=1,((-)) and = =
(ii) For any (cy, 1g: Uj Tú ) (Cyr 1j, uy Ty) E HW =R (TU x (0, 1),
we say (cj, 1,. Uj T3) < (Crr Ly, T3) if one of the followings holds:
Cj < Cji.
Cj cj' and I, < ljr.
G = Cy. 1 1,,, and ūj < uzr
21

---

Published as a conference paper at ICLR 2023
Cj -= cy.
uy u,, وy and Tj < Tz.
Definition C.2. Let [, .......,..................... x*8) and X' 22. ........ z }} be two multisets whose elements are taken from the same lotally-onlered set. Then we say X S X if (o))) ". "'Io((k) S "''( '''Z'''(0) in the sense of lexicographical order, where a E S₁ and E Sk are per- mutations such that Ea(1) S La(2) S .... S [k) and x' "1)'(1) S 5 S ... ...... S... dar(ey
Definition C.3. Suppose that V = fu1,u2,... v,,...,, vn and W = {wi, W2...., wa) are already or- dered, and that E E 1mxx" The order refinement is defined lexicographicaly;
(i) For any i, E (1,2..... m). we say that
(Us, ([(E,,, wy) Eug + 0}}) (cv, (((E,, w,) Evs # 0}1),
if one of the followings holds:
U/ < vp.
U; vy and [(a.j. Big + 0} < {( wyy (yy)) Er 0} in the sense of Definition C.2 where (Paj, wz) < (Be.g, if and only if Fig < E or Fii.
Ee wj Wy.
(i)) For any j.3 E (1,2..... .n] nJ, we say that
(wj, (l(Ea,j uz): Big + 0}}) < (((,,,,( Eig + 0}}),
one of the followings holds:
W < Wy--
w/ wy and {EEg, u.) Ei # #0 < (E En # 0} in the sense of Definition C.2 where (Ei,, v1) (E ve) ) if and only if Eus < Ees or Eig
E 1/ Ug.
With the preparations above, we can now define son in Algorithm
Algorithm 2 The sorting mapping & sonrt
Require: A weighted bipartite graph G (V W,W,W E Gm,n. with vertex features H
(hy hy ...... Jy bW 1 ...., AW E HV x HW such that (G, H) & Droldable- Order and W according to Definition
2: for --=1 1
+ n do
3: Refine the ordering on V and W according to Definition
4: end for
5: Return ow E S, such that (1) < Wow (2) < ... Waw (n)
Remark C.4. The output of Algorithm is well-defined and is unique. This is because that use unfoldable (G, H1) as input. Note that the order refinement in Definition C.3 is more strict than the color refinement in WL test. Therefore, after m + iterations, there is + E .1.,....... n with wy = Wy' since the WL test returns discrete coloring if no collisions for (G, H) & Djoldable
The sorting mapping o san has some straightforward properties:
Pen is equivariant:
( (G, H)) = ow) & sG, ow D H),
for any σV Sm. ow S,, and (G, II) E Im, HV H. DFoldable This is due to the fact that Definition C.3 defines the total order and its refinement solely depending on the vertex features that are independent the input order.
son is measurable, where the range S, equipped with the discrete measure. This is because that T smn is defined via finitely many comparisons.
22

---

Published as a conference paper at ICLR 2023
C.2 THE OPTIMAL SOLUTION MAPPING
We then define the optimal solution mapping
solu soll (D roldable
based on sort: where
solu
(9m. Hy H
n $ ( (1):
with H x x (0, 13)a C 7 is the collection of all feasible MILP problems in which every component in and u is finite.
We have mentioned before that any MILP problem in Doolu admits at least one optimal solution. For any (G,H) E Dsotu' X (Diodabbee. we denote XooinG H) E R= as the set of optimal solutions to the MILP problem associated to (G, H). One can see that X (G, H) is compact since for every (G,H) E soluu Diotaable both 1 and are finite, which leads to the boundedness (and hence the compactness) of Ssalu(G. H).
Given any permutation E Sn, let us define total order on R": = x' if and only if ((()) ... (n) < Fo(1) " 0(2) ".aa(() in the sense of lexicographic order. For any (G, H) E Dootu' (Poldaboo Im. Hy is well-defined. Then we define Psotu(G H) is the smallest element in X H) with respect to
Drooddable as in Section C.I. the permutation Pson (G, H) S,
the order 2, where a = Don (G, H). The existence and the uniqueness are true since X H) compact. More explicitly, the components of & sottu (G, H) can be determined recursively:
sotu (G, H)(()) inf {Io(1) x X (G, (G, H)}
and
T solu (G, H),H) = inf {Io(T) : E X (G, H), Fo(i) s (G, H)()), 3' 1,2,..... ... n. follows from the equivariance of 4 so () and X (G, H) that s (G, H) is also equivariant, i.e.,
for
solu ((ov, ow) * (G, H)) = (w (G, H)), Vov Sm, ow E Sny (G, Doolu Droldable-
We then show the measurability of & soln-
Lemma C.5. The optimal solution mapping Bxoiu D / Djotdubble + Ra is measurable.
Proof. It suffices to show that for any fixed o E (S,=, TE 10, and a E Sn, the mapping 1 : (D (Droldable) ) n (#son (1)-1(0) (A,b,c,L,
R
H soou (1 (A,,,,,,,,
measurable for all j E {1, ...., n), where
1 m Rmm R" R" Rd Gm,n x H. x H.W
is the embedding map when o and T are fixed. Without loss of generality, we assume that S. 2, ......... 2) where S. =, and 2 appear for K1, k2 ky and m K2 times, respectively, and that = (0... 0, 1, ......1) where 0 and appear for 1 and n h times, respectively. Note that the domain of $j. i.e., i - (Daota (Dialdable) (Pamn o i)-1 is measurable
due to the measurability of &
Define
n Σ
m
Viens A,,.b,,l,u, = max
max Isiski
Aig - bi
-b1)
max
Ai. bi
ks
<iSk2
5' ='=1
+
max <
bi -
Σ
Ai.
max (1y: xxy) + Is''n"
max (x. uz)) ) 15''Sn
j'=1
23

---

Published as a conference paper at ICLR 2023
and
Sol (A, b,,,,,,,,,,,,,, u, max {(eT= Pob)(((A, c, +))) Vieus (A, b, C,,, u,
for (A, (A,b,c,1,u) E Rmx x R x R" R" x R" and E R x zn- It is clear that Vieas is continuous and that E E2 x zー is an optimal solution to the problem (A, c, L.,,)) and only if Vunia (A, b, c, 1, u, x) = O. In addition, Viola is measurable with respect to (A, b, l, u) for any x, by the measurability of Pabj (see Lemma A.6 and continuity Views and is continuous with respect to I.
Then we proceed to prove that ; is measurable by induction. We first consider case that j = 1. For any (A, b, c,l, E (D (Piolable) (Psont o (o) and any & E. the followings are equivalent:
Psotu e, (,, (1)) <Φ.
inf (Io(1) x E X (1( (A, c,,, u))} <.
There exist r E 4 and X ( b, e, L, u)), such that To(1) S Φ 1/r.
There exists r E N4, for any r' E N+. zo(1) I 1-1/r holds for some Q zn-h satisfying Vinla (A, b, e,,,,,,, u) 1/r'.
Therefore, holds that
(-'(0) L = Dronauble) n so o))
U
U
rEN r'eN se x2n-N Se(1)50-1/-
EA Rm x 1mM R" R R" Vo, (A,,,,,,,, <
{ (A,
measurable, which implies the measurability of Φ Then we assume that $1...., Φ ( 2) are all measurable and show that 4, is also measurable. Define
VJJ solu (A, b, u, = max Vanta b. u,,,u,)), max (oo T - (A 153'
for (A,b,c, E (Dsota D Pioldable) 7 (4b sort oz) and r R x - Similar to Vuauu solu also measurable respect to (A, b, c, u) for any x and continuous with respect to x. For any u,,,, E (D (Dioddable)
( o (l the followings equivalent:
Panta b, ())o(() < <.
inf (5o()) : x E X (AA, b, e, u)), ro(y) (A,b,, J .,,, <
There exist r E N4 and x R$ x kn such that V (A, b, c, u. u, = and that To(()) S Φ --1r.
There exists r E N4, for any r' e N4, Ro(i) 60- 1/r holds for some æ e Q x zn satisfying V (A,,bc,, 1/r'.
Therefore, 0 (--0, Φ) can be expressed in similar format as (-o0, Φ). and is hence measur- able.
D DETAILS OF THE NUMERICAL EXPERIMENTS AND EXTRA EXPERIMENTS
MILP instance generation
Each instance in D has 20 variables, constraints and is generated
with:
24

---

Published as a conference paper at ICLR 2023
For each variable, Cj ~ (N 0.01), 4, u, ~ (V(,, 10). 1f uy. then switch i, and uy. The probability that zj is an integer variable is 0.5.
For each constraint, o, ~ U[{,, =, 2)) and by ~ 00 1).
has 60 nonzero elements with each nonzero element distributing (O 1).
Each instance in D2 has 20 variables, 6 equality constraints, and we construct the (2k 1)-th and 2k-th problems via following approach (1 S & 500)
Sample J fJ...e......3 Iy {0, 1). For j & J, 24 is a continuous variable with bounds (j. uj ~ NNO0, 10). If L3 > uj. then switch 1j and u.-
as random subset of {1,2.... ......... 20} with elements. For j E J,
< c00 0.
The constraints for the (2k-1) -th problem (feasible) is 2n +., 1, 1, +.ys 1, +2 1,
Ti + +IJ = 1, Jy + 15 = 1, 3/ + 2,, =
The constraints for the 2k-th problem (infeasible) vy +Wzz 1, tija + + 1, Jis + Fij 1, Jj Jo = 1, Jjs J3 = 1, jijo 2.j4 = 1.
MLP architectures As we mentioned in the main text, all the learnable functions in GNN taken as MLPs. All the learnable functions f. J. fow; fon (f) f1 .g"" .9 " M
are parameterized with multilayer perceptrons (MLPs) and have two hidden lay- The embedding size do. dr. are uniformly taken d that is chosen from (2,4,8, 16, 32, 64, 128, 256, 512, 1024, 2048). All the activation functions are ReLU.
Training settings We use Adam (Kingma Ba 2014 as our training optimizer with learning rate of 0.0001. The loss function is taken as mean squared error. All the experiments are conducted on Linux server with an Intel Xeon Platinum 8163 GPU and eight NVIDIA Tesla V100 GPUs.
Extra experiments on generalization We conduct for the andom-feature approach. The GNN/MLP architecture is the same as what we describe be- fore with the embedding size being dl The size of the training set is chosen from {10, 100, 1000) and the size of the testing set is 1000, where all instances are generated in the same way as D2, with the only difference that we set C1
numerical experiments on generalization
C20 = 0.01 instead of C1 is that, C1 = ... C20 = 0 makes every feasible solution as optimal and thus the labels depend on the solver's choice. By setting c
C20 = The reason
C2p 0.01, one can make the label depend only on the MIIP problem itself, which fits our purpose, i.e., representing characteristies of MILP problems, better. In addition, our datasets for feasibility consists of 50% feasible instances and 50% infeasible ones, while other datasets are obtained by removing infeasible samples.
We report the error on training set and the testing set Table [ The generalization performance
is good in our setting when the training size is relatively large. Although our experiments are still small-scale, these results indicate the potential of the random-featur approach in solving MILP problems in practice.
Number of Training Samples
10
100
1000
Feasibility
Training Error Testing Error
0
0.02
0.289
0.104
0.022
Objective
Training Error Testing Error
1.2e- 15
1.1e-06
1.
5,9c-03
5.4e-06
1.le-06
Solution
Training Error
1.7c-03
7.2e-02
7.2c-02
Testing Error
2e
7.5e-02
7.3e-02
Table 1: Generalization for feasibility
25


Reviews:
[{"review_id": "_YLIcrsGbT5", "reviewer": "Reviewer_mtYU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors try to answer an interesting yet challenging question：\nIs GNN a good representation model for MILP and whether it can predict important properties, eg., feasibility, for MILP problems?\nThey construct a simple example showing that there exist two MILPs such that one of them is feasible while the other one is not, but no GNN can distinguish them.\nThis example illustrates the limitation of the representability of GNN for MILP problems.  \nThey further divide MILPs into two classes: foldable and unfoldable and show that GNN has strong enough representation power on unfoldable MILPS. \nFinally, they show that by appending random features, GNN can also have strong enough representation power on foldable MILPS. \n", "summary_of_the_review": "Overall, this is a good paper that tries to answer important questions on the topic of \"learning to optimize\".", "strength_and_weaknesses": "Strong points:\n1. Studying the representability of GNN for MILPs is a fundamental problem in this area， and this topic fits well with the conference's scope. \n2. The construction of the counterexample is neat, and this example clearly shows the limitation of the representability of GNN for MILP problems.  \n3. Proving GNN has strong enough representation power by appending random features provides some theoretical explanations for this widely known trick. \n\n\nWeak points:\n1. Since the definition of foldable MILP depends on Algorithm 1, which is used to measure the separation power of GNN, the resulting theorems (Thm 4.2 ~ Thm 4.4) seem to be straightforward.\n2. For the experiments, reporting training loss is not very meaningful from a practitioner's point of view. As you claim that adding random features is a good practical solution, can you also report the corresponding test loss?\n3. Although the three questions raised in the paper are important, they are not quite practical. It will be better if the authors can link the results of this paper to answer whether GNN is able to predict the branching strategy which has been empirically studied recently. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ZG0ydwIq7Mj", "reviewer": "Reviewer_wHAc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper study the representation power of GNN for mixed integer linear programming (MILP) problems. ", "summary_of_the_review": "This paper studies the representation power of GNN for mixed integer linear programming (MILP) problems.  The problem is important and fundamental. The analysis justifies the advantage of the random feature technique when solving MILP problems. The overall presentation is quite clear.  The proof combines the Stone-Weierstrass theorem (including its generalized version in Azizian and Lelarge’21) with domain knowledge of MILP.  The anaylsis is mostly sound and solid. However, I have the following questions. \n\n**Major questions:** several important proof steps are shown in a hand-waving style without rigorous derivation. For instance: \n\n1. Lemma A.8 is a very strong claim. I think it only holds for some specific graphs like bipartite graphs. Please write down the proof rigorously. The same suggestion also applies to the proof of Thm 5.1, page 16, the claim in the sentence \"Therefore, similar to Lemma A.8, one can see for any....\". Please write down the proof rigorously. \n\n2. For the proof of Thm 5.1, page 16,  please verify that for any function f in the function class of  GNN, f(G1) = f(G2) if G1 and G2 (which are both equibed with random features) are isomorphic.  Please write down the proof rigorously (if this claim is correct.)\n\n3.  Why is phi_feas continuous?\n\n4. phi_solu( ) is an one-to-many mapping. It is not a function. I don't understand how to approximate this mapping using Lusin' & Stone-Weisterass Theorem, which only apply to measureable & continuous functions. Please explain more. \n\nA follow-up question related to the above comments 1 and 2:\n\nRegarding the proof of Thm 5.1, page 16, the authors apply Thm A.7 after verifying  \"phi_feas(G, H ) =  phi_feas(Ghat, Hhat), for all (G, H,w )~ (Ghat,Hhat,what)\". However, I dont think we can apply  Thm A.7 like this because (G,H) and (G, H, w) lie in different spaces.  From my understanding, by applying Thm A.7 correctly, we can only get \"random-featured GNN\" can approximate \"phi_feas defined on random-featured  graphs\".  But it seems unclear what is the relation between \"phi_feas defined on random-featured  graphs\" and \"phi_feas defined on original  graphs\". Please verify.\n\nTo briefly summarize, the proof of Thm 5.1, page 16 is quite dense and hand-waving. **The rigorous proof is missing and I doubt the correctness of the results about random features.  I would like to raise the score if authors address these concerns.**\n\n\n\n**Other comments:**\n1. The paper steps forwards an important first step to establish the feasibility of learning MILP by GNNs. However, the problem is far from being concluded. For MILP problems, another equally important (if not more important) application of GNN is to learn the algorithmic configuration such as the branching strategy, which is not covered in the script. Please add more relevant discussions.  \n\n2. Correct me if wrong: from my understanding,  the original WL test paint all the nodes in a single graph with the same initial color.  Why do we allow different initial colors (across nodes) in the script? \n\n2. typo: page 6 lemma 3-2: Consider two MILP provlems ==> problems.\n\n3. I would suggest the authors double-check all the \\citep and \\citet properly. \n\n4. When encoding the MILP into a graph, how do you implement \"<=, >=\" and \"\\infty\" in the node feature of the graph?\n\n\n+++++++++++++++++++++**POST REBUTTAL** ++++++++++++++++++++++\n\nMany thanks for the detailed reply from the authors. Most of my concern is addressed.  I am also convinced that the script has many differences with  the LP paper  so the ethic concern is also addressed. I briefly summarize the contribution of the script as follows:\n\n1. Negative results on GNN for representing MILP\n2. A candidate solution called “random-featured GNN“ is provided.\n\nFor me, 1 is not surprising because it is well known that GNN has limited distinguishing power, so it is possible that GNN might fail to capture certain info on MILP graph. However, it is good to see a counter-example to explicitly point out the limitation of GNN for representing MILP.  In summary, although the result is not surprising, I think this part is still worth sharing with the community. \n\nAs for 2, I think the contribution is limited due to the following reasons.\n\n[R1] The analysis requires infinite-width random-featured GNN.  It seems unclear what is the advantage of random-featured GNN over MLP. Since infinite width MLP has universal approximation power, MLP can solve isomorphism problems and also it can represent MILP as well. Then the random-feature strategy seems not that important since you also require infinite width anyways.  \n\n[R2] The practical impact is unclear due to the toy experiments. Further, random-feature technique is not invented by the script, either. \n\n\nBy balancing the pros and cons, I raise my score to 6.\n\n\n\n", "strength_and_weaknesses": "See my comments below. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MzXEDrXuXb", "reviewer": "Reviewer_ekKz", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper presents a Graphical Neural Network (GNN) based method for the solution of Mixed-integer linear programming (MILP) optimization problem. The proposed method adds random features to the MILP based GNNs and prove is provided that this will provide a optimal solution for MILP. Details, from a reference,  are provided for the representation of an MILP into a weighted graph. GNN is built to represent the properties of the whole graph. Feasibility, Optimal objective value and Optimal solution mappings are provided along with the invariance and equivariance properties. A lot of theoretical description of mathematics is provided for the GNN based MILP solution. Feasibility through numerical experiments is  described. \n", "summary_of_the_review": "\t1. The paper seems sound mathematically and theoretically.\n\t2. Mostly the paper is about MILP and Graphs theory\n\t3. Other than GNN, no machine learning\n\t4. More suitable for graph or applied mathematics conference\n\t5. Not suitable for a machine learning conference\n", "strength_and_weaknesses": "Strength:\n\t1. The proposed technique of addition of random features\n\t2. Mathematics and details of the MILP representation into GNN\n\t3. Reapplication of theorem 3.1. for MILP - graphs\n\t4. Theorems of section 4 & 5\n\t5. Numerical experiments to validate proposed theories\nWeaknesses:\n\t1. Typos e.g. \"Fugure 2\" on page 6\n\t2. It is not clear what is the contribution to the mathematics and theory and what is reapplication of existing work.\n\t3. Mainly the paper is about graph theory\n\t4. Although GNN is used in machine learning, the paper does seems to be doing machine learning\n\t5. No real world MILP scenarios are implemented or solved\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "FeiGsKdKH1", "reviewer": "Reviewer_LV4F", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "Authors identify cases which a particular method of graph representations of mixed integer linear programming (MILP) problems shall not distinguish feasible problems from infeasible problems using Weisfeiler-Lehman (WL) test. Authors characterize a subset of indistinguishable MILP problems as \"foldable\", which means there are nodes with the same color from WL test. As a treatment, authors suggest to add a random features to make all nodes distinguishable. Synthetic data experiments demonstrate that random features do provide representation power to separate feasible MILPs from infeasible ones.", "summary_of_the_review": "Being clear about limitations of the analysis, and bridging the gap between the analysis & actual practice will strengthen the paper.", "strength_and_weaknesses": "While GNNs have become a popular method of encoding MILP problems, there has been lack of clarity on whether these GNNs are actually representative enough for their successful applications to downstream tasks such as neural diving or branching. This paper provides a clear example which this method might fail, and provides an insightful characterization. I believe such a finding will help practitioners understand limitations of current approaches in applying GNNs to MILPs.\n\nAuthors also build upon well-established approaches from the literature: The suggested remedy of adding random features is simple, but well supported by recent literature on GNNs. \n\nThe contribution of the paper is mostly theoretical rather than empirical, and unfortunately the paper is not very clear about the limitation of the analysis. Most importantly, authors fail to mention that the particular bipartite graph representation they introduce is a simplification of what was actually introduced in Gasse et al. (2019). The paper almost reads like this representation is exactly what Gasse et al and follow-up papers like Nair et al are using, whereas in reality these papers have a number of engineered features and therefore the suggested \"unfoldability\" is much less likely to happen. I still find authors' analysis to be insightful- good analysis requires simplification. However, authors should've clarified they are making simplifications.\n\nI am also not sure adding random features is the right remedy to the problem. For sure, making every node color unique will allow WL test to always separate two graph instances. But on the other hand, when there are two equivalent MILP problems, WL test will now fail to recognize they are equivalent? Hence we seem to be losing statistical power from this \"remedy\", but this loss of statistical power is not characterized, not giving readers the sense of trade-off being made.\n\nAuthors could've provided much more insight on the practical usefulness of foldability if they used MILP problems from existing benchmarks. How many of MILP problems in the literature are actually foldable; is there any? If there are, how does that impact the performance of GNN-based feasibility classifiers and/or neural diving/branching models?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster