On Representing Linear Programs by Graph Neural Networks
Authors: Ziang Chen
Jialin Liu
Xinshang Wang
Wotao Yin
Venue: ICLR 2023 notable top 25% (2023)

Abstract: Learning to optimize is a rapidly growing area that aims to solve optimization problems or improve existing optimization algorithms using machine learning (ML). In particular, the graph neural network (GNN) is considered a suitable ML model for optimization problems whose variables and constraints are permutation--invariant, for example, the linear program (LP). While the literature has reported encouraging numerical results, this paper establishes the theoretical foundation of applying GNNs to solving LPs. Given any size limit of LPs, we construct a GNN that maps different LPs to different outputs. We show that properly built GNNs can reliably predict feasibility, boundedness, and an optimal solution for each LP in a broad class. Our proofs are based upon the recently--discovered connections between the Weisfeiler--Lehman isomorphism test and the GNN. To validate our results, we train a simple GNN and present its accuracy in mapping LPs to their feasibilities and solutions.

Published as a conference paper at ICLR 2023
ON REPRESENTING LINEAR PROGRAMS BY GRAPH NEURAL NETWORKS
Ziang Chen
Jialin Liu
Department of Mathematics, Duke University Durham, NC 27708 zi miang@math, duke. edu
Damo Academy, Alibaba US Bellevue, WA 98004
jialin. 11 u@al al ibaba inc. com
Xinshang Wang
Damo Academy, Alibaba US
Antai College of Economics and Management, Shanghai Jiao Tong University Bellevue, WA 98004 xinshang. w@alibaba-ing 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 ibaaba - i inc. com
ABSTRACT
Learning to optimize is rapidly growing area that aims to solve optimiza- tion problems improve existing optimization algorithms using machine learn- ing (ML). In particular, the graph neural network (GNN) is considered a suit- able ML model for optimization problems whose variables and constraints permutation-invarian
for example, the linear program (LP). While the literature has reported encouraging numerical results, this paper establishes the theoretical foundation of applying GNNs to solving LPs. Given any size limit of LPs, we con- struct GNN that maps different LPs different outputs. We show that properly built GNNs can reliably predict feasibility, boundedness, and an optimal solution for each LP broad class. Our proofs are based upon the grently-discovered connections between the Weisfeiler-Lehman isomorphism test and the GNN. To validate our results, we train simple GNN and present its accuracy mapping LPs to their feasibilities and solutions.
INTRODUCTION
Applying machine learning (ML) techniques to accelerate optimization, also known as Learning
to Optimize (I.20), is attracting increasing attention. It has been reported that L.20 shows great
potentials on both continuous optimization (Monga et al. 2021 Chen et al., 2021 Amos 2022 and combinatorial optimization (Bengio al. Mazyavknn et al.) (021). Many of the 120 works train a parameterized model that takes the optimization problem as input and outputs information useful to classic algorithms, such as good initial solution and branching decisions (Nair et al. 2020), and some directly generate approximate optimal solution (Gregor & LeCun 2010).
In these works, one is building an ML model to approximate the mapping from an explicit optimiza- tion instance either its key properties directly to its solution. The ability to achieve accurate approximation is called the representation power or expressive power of the model. When the ap- proximation is accurate, the model solve the problem provide useful information guide an optimization algorithm. This paper tries to address a fundamental but open theoretical problem for
A major part of the work of Z. Chen was completed during his internship at Alibaba US DAMO Academy.
Corresponding author.

---

Published as a conference paper at ICLR 2023
linear programming (LPy:
Which neural network can represent LP and predict its key properties and solution?
(PO)
To clarify, by solution we mean the optimal solution. Let us also remark that this question is not only of theoretical interest. Although currently neural network models may not be powerful enough to replace those mathemattial--goondee LP solvers and obtain an exact LP solution, they are still useful in helping LP solvers from several perspectives, including warm-start and configuration. It requires that neural networks have sufficient power to recognize key characteristics of LPs. Some very recent papers (Deka & Misra 2019 Pan et al., 2020; Chen et al. (022) on DC optimal power flow (DC-OPF), an important type of LP, experimentally show the possibility of fast approximating LP solutions with deep neural networks. Practitioners may initialize an LP solver with those ap- proximated solutions. We hope the answer to (PO) paves the way toward answering this question for other optimization types.
Linear Programming (LP). LP is an important type of optimization problem with wide range of applications, such as scheduling (Hanssmann & Hess 1960), signal processing (Candes & Tao 2005). machine learning (Dedieu et al. 2002)), etc. A general LP problem is defined as:
min c c'x, S.t. Ar 1 1s =ER"
(1.1)
where A E R E R", b E R I E (IR (RU(-x))) u E (TR (+00))) and o E (S,=,2)
Any LP problems must follow one of the following three cases (Bertsimas & Tsitsiklis):
Infeasible. The feasible set X == far E RR: Ax o b, 1 1 u} is empty. In another word, there is no point in R" that satisfies the constraints in LP [.I).
Unbounded. The feasible set is non-empty, but the objective value can be arbitrarily good, i.e., unbounded from below. For any R > 0, there exists an Xp such that c x -R. Feasible and bounded. There exists x" E Xp such that c=x² I Txx for all x E Np. Such x" is named as an optimal solution, and c x= is the optimal objective value.
Thus, considering (PO), an ideal ML model is expected to be able to predict the three key charac- teristics of LP: feasibillity, boundedness. and one of its optimal solutions (if exists), by taking the LP features (A, b, c, I, o, as input. Actually, such input has a strong mathematical structure. swap the positions of the i, variable in (1.1), elements in vectors b, c, I, u, and columns of matrix A will be reordered. The reordered features (A, b, é, i, â, 6) actually represent an exactly equivalent LP problem with the original one (A, b, c, I, u, o). Such property is named as permulation invariance. If we do not explicitly restrict ML models with a permutation invariant structure, the models may overfit to the variable/constraint orders of instances in the training set. Motivated by this point, we adopt Graph Neural Networks (GNNs) that are permutation invariant naturally.
GNN in L20. GNN is type of neural networks defined on graphs and widely applied in many areas, for example, recommender systems, traffic, chemistry, etc (Wu et al. 20200] Zhou et al.. 2020). Accelerating optimization solvers with GNNs attracts rising interest recently (Peng et al. 202 Cap-
part et al. 2021). Many graph-related optimization problems, like minimum vertex cover, traveling
salesman, vehicle routing, can be represented and solved approximately with GNNs due to their
problem structures (Khalil et al. 2017 Kool et al. 2019 Joshi et al., 2019 Drori et al. 2020). Be- sides that, one may solve general LP or mixed-integer linear programming (MILP) with the help of GNNs. Gasse et al. (2019) proposed to represent an MILP with bipartite graph and apply GNN on this graph to guide an MILP solver. [Digg et al. (2020) proposed a tripartite graph to represent
MILP. Since that, many approaches have been proposed to guide MILP LP solvers with GNNs (Nair et al. 2020; Gupta et al.) 2020) 2022 Shen et al. 2021 Khalil et al. 2022; Liu et al., 2022, Paulus et al. [2022] Qu et al. 2022 et al. 2022). Although encouraging empirical results have been observed, theoretical foundations are still lack for this approach. Specifying (PO), we ask:
Are there GNNs that can predict the feasibility, boundedness and an optimal solution of LP? (P1)
Related works and contributions. To answer PI one needs the theory of separation power and representation power. Separation power of neural network (NN) means its ability to distinguish two different inputs. In our settings, a NN with strong separation power means that it can outputs different results when it is applied on any two different LPs. Representation power of NN means its ability to approximate functions of interest. The theory of representation power is established upon the separation power. Only functions with strong enough separation power may possess strong
2

---

Published as a conference paper at ICLR 2023
representation power. The power of GNN has been studied in the literature (see Saao (see|Sato
(2020) Jegelka
(202)); Li & Leskovec (2022) for comprehensive surveys), and some theoretical efforts have been
made represent some graph-related optimization problems with GNN (Sato et al.. 2019 Loukas
2020). However, there are still gaps to answer question (PT) since the relationships hetween charac-
teristics of L. and properties of graphs not well established. Our contributions are listed below:
(Separation Power). In the literature, it has been shown that the separation power of GNN is equal to the West (Xu et al. 2019; Azzizian & Lelarge| 2021 Geerts & Reutter 2022). However, there exist many pairs of LPs that cannot be distinguished by the WL test. We show that those puzzling LP pairs share the same feasibility, boundedness, and even an optimal solution if exists. Thus,
GNN has strong enough separation power.
(Representation Power). To the best of our knowledge, we established the first complete proof that GNN can universally represent a broad class LPs. More precisely, we prove that, there exist GNNs that can be arbitrarily close to the following three mappings: LP - feasibility, LP optimal objective value (-o0 if unbounded and oo if infeasible), and LP + an optimal solution (if exists), although they are not continuous functions and cannot be covered by the literature (Keriven
& Peyré 2019; Chen et al. 2019 Maron et al. 20 2019a b
Keriven et al. 2021).
(Experimental Validation). We design and conduct experiments that demonstrate the power of
GNN on representing LP.
The rest of this paper is organized follows. In Section 2
provide preliminaries, including related notions, definitions and concepts. In Section 3 we present our main theoretical results. The sketches of proofs are provided in Section[4] We validate our results with numerical experiments in Section 5 and we conclude this paper with Section 6
2 PRELIMINARIES
In this section, we present concepts and definitions that will be used throughout this paper. We first describe how to represent an LP with a weighted bipartite graph, then we define GNN on those LP-induced graphs, and finally we further clarify question (P) with strict mathematical definitions.
2.1 LP REPRESENTED AS WEIGHTED BIPARTITE GRAPH
Before representing LPs with graphs, we first define the graph that we will adopt in this paper: weighted bipartite graph. A weighted bipartite graph G = -V U W, E) consists of a vertex set VUW that are divided into two groups and W with V i' W 0, and a collection E of weighted edges, where each edge connects exactly one vertex in V and one vertex in W. Note that there is no edge connecting vertices in the same vertex group. E can also be viewed as a function E V W + R. We use Gm,, to denote the collection of all weighted bipartite graphs G UVUW, E)) with V = m and W = n. We always write V = {U1, U2,.... ,m.) ). W = {wi, W2,.... w.), and Egj- = E(U;, w,),, for E (1,2...... m), j 2.,......
One can equip each vertex with feature vector. Throughout this paper, denote h/ E H.V the feature vector of vertex v; E V and denote h/ E HW as the feature vector of vertex wy E W, where HV HW are feature spaces. Then we define H. (HV H. the vertex features together as H = (hy h1 weighted bipartite graph with vertex features is defined
(H( )r and concatenate all W.W E H. x HW Finally, a
y. W. .i tuple (G, H) Gm, H. H.W.
With the concepts described above, one can represent an LP L.. as a bipartite graph (Gasse et al. 2019; Each vertex in W represents a variable in LP and each vertex in V represents a constraint. The graph topology is defined with the matrix A in the linear constraint. More specifically, let us set
Vertex 8ú represents the i-th constraint in Az b, and vertex wy represents the j-th variable xy.
Information of constraints is involved in the feature of o;: hy (bi, o;).
The space of constraint features is defined HV = IR x { {s-- -,
Information of variables is involved in the feature of wi: hw
(c,,,,,,)).
The space of variable features is defined as W = R x (R U (-oo)) x (RUffoo)))
The edge connecting Us and wy has weight E,, = A.j.
Then I. is represented as graph (G. H) Im,, x HVV H.. In the rest of this paper, we coin such graphs as I.P-induced Graphs or I.P-Graphs for simplicity. We present an LP instance and its corresponding LP-graph in Figure
3

---

Published as a conference paper at ICLR 2023
min x
T1 + 2022,
NY (1,2)
11
w1
h 11,00+00)
s.t. 21 + 20 2 1,
201 + T2 2,
1 (2, =)
12
W2
hy (2, -00
31 2 0, 12 -1
Figure 1: An example of L.P-graph
2.2
GRAPH NEURAL NETWORKS FOR I.P
The GNNs in this paper always take an LP-Grat LP-Graph as input and the output has two cases:
The output is a single real number. this case, GNN is a function 9m,, x H% x HW -> R and usually used to predict the properties of the whole graph.
Each vertex in W has an output. Consequently, GNN is function Gm.n x Hy x H + R". Since W represents variables in LP, GNN is used predict properties of each variable in this case.
Now we define the GNN structure precisely. First we encode the input features into the embedding space with learnable functions J HV + Rdo and fiWl HWW + Rdo:
h O.V (h!), &) = f (n]"), i = 1,2. m. j 1,,2....
(2.1)
where n. 1g E Rdd0 are initial embedded vertex features and do their dimension. Then we choose learnable functions f. S.W Rdd-1 + Rd and of . 12de- x Rdd - Rdd and update the hidden states with
1 g6
1/ 1.V
Σ
Baght ( (1)-1.1)) i= 1=1,2 1,2,
(2.2)
n/w gb [n
Σ E (ng )) j .,,. (1))
(2.3)
where V. .nj.W E Rd are vertex features at layer (1 S S L) and their dimensions are di....,, dg respectively, The output layer of the single-output GNN is defined with learnable function fou IRda. x IRd + R:
yout = Sout Σ
L.W
(2.4)
The output of the vertex-output GNN is defined with for Rdde x Rdde Rd + R:
Yout (W,)
-for Σ L.V
Σ L.W
) j 1,2 ........ n2
(2.5)
We denote collections of single-output GNNs and vertex-output GNNs with FANN and JW spectively:
GNN' re-
FUNN =(F Gm,n H. x H.W - R F yields 2.1 2.2
2.4
(2.6)
FUNN =(F Gm. x HY x H.
-> R. F yields 2.1
In practice, all the learnable functions in GNN - fouts fW {f J .9 96 L usually parameterized with multi-linear perceptrons (MLPs). In our theoretical analysis, we assume for simplicity that those functions may take all continuous functions settings in Azizzin & Lelarge 2022 Section C. Thanks to the universal approximation properties of MLP (Hornik al. 1989 Cybenko 1989), can extend our theoretical results by taking those
given domains, following the
learnable functions as large enough MLPs.
2.3 REVISITING QUESTION [TT
With the definitions of LP-Graph and GNN above, we revisit the question (I)) and provide its precise mathematical description here. First define three mappings that respectively describe the feasibility, optimal objective value and an optimal solution of an LP (if exists).
Note that the update rules in (2.2 and 2.. follow a pressage-passing way, where each vertex only collects information from its neighhors. Since F 0 if there is no connection between vertices i and u.,, the sum operator in 2.2 can be rewritten Σ, EyEN(E where (v:))) denotes the set of neighbors of vertex 24.
4

---

Published as a conference paper at ICLR 2023
Feasibility mapping The feasibility mapping is classification function
& feas gm,n X Hm x H, + {0,1),
(2.7)
where Preas If) = 1 if the LP associated with (G, H) is feasible and Preas fec H) otherwise.
Optimal objective value mapping Denote
Pabj: 9m., Hy H, - +RU -BU
(2.8)
as the optimal objective value mapping, i.e., for any (G, H) 9m. H% x H PGij(, H) is the optimal objective value of the LP problem associated with (G,
Remark 2.1. The optimal objective value of a LP problem can a real number or 0c/ - cc. The
"co" case corresponds to infeasible problems, while the "-oo" "0 case consists LP problems whose objective function is unbounded from below in the feasible region. The preimage of all finite real numbers under 4 abij. (6) (R), actually describes all LPS with finite optimal objective value.
Remark 2.2. In the case that a LP problem has finite optimal objective value, it is possible that the problem admits multiple optimal solutions. However, the optimal solution with the smallest -ormorm must be unique.
fact, if + x' are two different solutions with ||>||| = ||x'),, 1. where ll || denotes the E2-norm throughout this paper. Then 2 2(x + +x') is also an optimal solution due
the convexity of LPs, and it holds that 11 + 22)l? < 2||==|1 + 11221112 ||||2
|| i.e.
(l + z')l < ||>|| | where the inequality is strict since x + x'. Therefore, and x! cannot be optimal solutions with the smallest Ez-norm.
Optimal solution mapping For any (G, H) E D2) we have remarked before that the LP problem associated with (G, H) has unique optimal solution with the smallest mo-mmm Let
Pool + (R) R."
(2.9)
be the mapping that maps H) E TJ) (R) to the optimal solution with the smallest normm
Invariance and Equivariance We denote Sn, Sn as the group consisting of all permutations on vertex groups W respectively. another word, Sn, involves all permutations on the constraints of LP and Sn involves all permutations on the variables. In this paper, we say function F Gm, X HV x HW + R is invariant if satisfies
F(G, H) F ((ov, ow) (G, H)), Vav E Sm, ow E Sn,
and a function Fw: : .m,n x H. X H - RR" is equivariant if it satisfies ow (Fw (G, H)) Fw ((ov,ow)+ * (G,
Yav E Sw Sn. where (av,ow) (w) (G, H) is the permuted graph obtained from reordering indices in (G, H) using (ov, J.), which the group action of Sm x Sn on Im,n X HV x H.W One can check that Press Dobj. and any F E FGNN are invariant, and that & and any Fw GNN are equivariant.
Question (PI) actually asks: Does there exist F E FONN that well approximates P or 4 Dajj And does there exist Fw E FW that well approximates sslu?
MAIN RESULTS
This section presents main theorems that answer question (11).
As state in the introduction, representation power is built upon separation power in our paper. We first present with the following theorem that GNN has strong enough separation power represent LP.
Theorem 3.1. Given any two LP instances (G, H). (G. Ht) E Gm. x H. HW, F(G, =
F(G, H) for all F E Fows then they share some common characteristics:
(i) Both LP problems are feasible or both are infeasible, i.e., & Beea(G,,r H) De (G, H).
(ii) The two LP problems have the same optimal objective value, i.e. Dang(G H) @ f)).
(ii) bott problems are feusible and bounded, they have the same optimal solution with the small- est to-norm up to a permutation, i.e., T sofu (G, H) = ow ( so G. H)) for some ow Sn- Furthermore, if Fw (G, H) = Fw (G, Hf), 4 Fw GNN then (iil) holds without taking permuta- tions, Le., 1 L (G, H) (G.ttu f).
5

---

Published as a conference paper at ICLR 2023
This theorem demonstrates that the function spaces FGNN and F GNN rich enough to distinguish the characteristics of LP. Given two LP instances (G, H), (G, H), as long as their feasibility or boundedness are different, there must exist F E FGNN that can distinguish them: F(G, H) * F(G, H)). Moreover, long their optimal solutions with the smallest Eg Eg-norm different, there must exist Fw E F that can distinguish them: Fw H) + FG, H). With Theorem 3.1 served as a foundation, we can prove that GNN can approximate the three mappings Piens. Ponj and Psolu to arbitrary precision. Before presenting those results, we first define some concepts of the space Imn x Hm x H,
Topology and measure Throughout this paper, we consider gm.n H x H where H R x ( and HW" R x (R U {- x (R U [+oo}), topology space with product topology and a measurable space with product measure. It's enough to define the topology and measure of each part separately. Since each graph in this paper (without vertex features) can be represented with matrix A E Rm the graph space Gm. is isomorphic to the Euclidean space |=*x;; Gm. _ _mxxn and we equip Gm. with the standard Euclidean topology and the standard Lebesgue measure. The real spaces IR in HW and HV are also equipped with the standard Euclidean topology and Lebesgue measure. All the discrete spaces {S.=.2h. {-oo]. and {+oo} have the discrete topology. and all unions are disjoint unions. We equip those spaces with discrete measure ((S)= = JS|. where (S] is the number of elements in finite set S. This finishes the whole definition and we denote Meas(-) as the measure on gmn. Hy H.W
Theorem 3.2. Given any measurable X C. Gm. x H. x H with finite measure, for any > 0, there exists some F FoNN, such that
Meas (I(G, H) E X [I((,,))22/2+ + De (G, <,, where I. is the indicator function, i.e. IF(G, = 1 Ff ([G., H) > 1/2 and IFGG, otherwise.
This theorem shows that GNN is a good classifier for LP instances in X long as X has finite measure. If we use F(G, ((G,H) H) > 1/2 as the criteria to predict the feasibility, the classification error rate is controlled by e/ e/Meas(X), where e can be arbitrarily small. Furthermore, we show that GNN can perfectly fit any dataset with finite samples, which is presented in the following corollary.
Corollary 3.3. For any D C Gm,n X H. x H. with fimite instances, there exists F E FoNN that
IF(G,H)>1/2 = D (G,H), Y (G,
Besides the feasibility, GNN can also approximate Oobj and @solu-
Theorem 3.4. Given any measurable X Gmnn HY H. with finite measure, for any O, there exists F1 E FONN such that
Meas (((G, H) E X I + Ims,(.,EERR) <e,
(3.1)
and any e, >>0 0, there exists Fg E FaNN such that
Meas (((C, ((G.H)exnce xx (x (R) F2 - (G, H)] HT) 6)) <
(3.2)
Recall the definition of Pabi in (28) that it can take { as its value. Thus, Pohj H) R means the LP corresponding to (G. H) feasible and bounded with a finite optimal objective value, and inequality (3.1) illustrates that GNN can identify those feasible and bounded LPs among the whole set X, up to given precision Inequality (3.2) shows that GNN can also approximate the optimal value. The measure of the set of LP instances of which the optimal value cannot be approximated with 5-precision is controlled by c. The following corollary gives the results on dataset with finite instances.
Corollary 3.5. For any D C Im, HY HW with finite instances, there exists F1 E FONN such that
TF((G.))>1/2 = (G, A (G,H) D,
fnr any 8 > 0, there exists F2 E FGNN, such that [2, H) 2 (G, H)| < 8, (GG H) E D (R).
Finally, we show that GNN is able to represent the optimal solution mapping T wolu-

---

Published as a conference paper at ICLR 2023
Theorem 3.6. Given any measurable X C $ (R) C Imm x Hy x H. with finite measure. for any e, > O, there exists some Fw E G such that
Meas (1(G, H) X EI:
2oon (G, H)Il > 83) <E.
Corollary 3.7. Given any D C Payy (R) 9m. Hy H. with finite instances, for any 8 > 0, there exists Fw E F such that
[[F(G, solu (G, H) < (G, E D.
SKETCH OF PROOF
In this section, we will present sketch of our proof lines and provide examples show the intu- itions. The full proof lines are presented in the appendix.
Separation power The separation power measures a neural network with whether it generates different outcomes given different inputs, which serves foundation of the representation power. The separation power of GNNs is closely related to the Weisfeiler-Lehmat (WL) test (Weisfeiler & Leman 1968). classical algorithm to identify whether two given graphs are isomorphic. To which is slightly
apply the WL test on LP-graphs, we describe a modified WL test in Algorithm [ different from the standard WL test.
Algorithm The WL test for LP-Graphy denoted by WLLP)
Require: A graph instance (G, H) E 9m. Hy x HW and iteration limit L 0.
1: Initialize with CO. = HASHo, (1t)) G.. = HASSo, (h)).
2: for 1, do
3: C.. HASH,v (c.- Σラ= E HASH,, (c)-LW)
4: C HASH,W (C)-L,, EE Pay (C- (G!-V.))
5: end for
6: return The multisets containing all colors
((C D {[)) })5=0
We denote Algorithm by (LLP('), and we say that two LP-graphs (G, H), (G. H) can be distinguished by Algorithm 7 if and only if there exist positive integer L and injective hash functions (HASH, HASH,, H U (HASH,, v HASH w 1 such that WLLP ((, H), L) + WL. WLG,((G, H. L). Unfortunately, there exist infinitely many pairs of non-isomorphic LP-graphs that cannot be distinguished by Algorithm | Figure provide such an example.
Since the separation power of GNNs is actually equal to the WL test (Xu al. 2019), one would expect that the limitation of the WL test might restrict GNNs from universally representing LP. However, any two LP- LP-graphs that cannot be distinguished by the WL test must share some common characteristics even if they are not isomorphic. For example, let us consider the six LP instances in Figure In each of the three columns, the two non-isomorphic LP instances cannot be distinguished by the WL test. It can be checked that the two instances in the same column share some common characteristics. More specifically, both instances in the first column are infeasible; both instances in the second column are feasible but unbounded; both instances in the third column are feasible and bounded with (1/2, 1/2, 1/2, 1/2) being the optimal solution with the smallest fo-norm. Actually, this phenomenon does not only happen the instances in Figure 2 but also serves universal principle for all LP instances. We summarize the results in the following theorem:
Theorem 4.1. If (G. H), H), E Gm. x HV x HW are not distinguishable by Algorithm then
Dfeas (G, H) Dea (G, and (G, H) 2
In Algorithm ! multisets, denoted by {O). are collections of elements that allow multiple appearance of the same element. Hash functions (HASH;,v HASH,,) injectively map vertex information to vertex colors, while the others [HASH[ HASH(, w Hi, injectively map vertex colors to a linear space so that one can define sum and scalar multiplications on their outputs. In addition. such an algorithm is usually named as the 1-WL. test in the literature since it only considers the neighborhood with distance for each vertex. In this paper, we abbreviate Algorithm I the 1-WL. test to the WT. test for simplicity.

---

Published as a conference paper at ICLR 2023
min 21 + 22 + 33 + 24,
min 1i + + 23 + 14,
min #1 + 12 + 23 + 24:
s.t. 21 + 2/2 4,
s.t. I1 + 1
s.t.
12 1,
P2
W2
22 +
2 1
22 F3
33 34 1
44+ 1
33 +
24 + 21 = 1,
+ 1
24 #
1/4
W14
2j 2,21, 1, 1 1 4
1, 1 15154
2j E, 1 - j S 4.
min 21 + x2 24,
min क + 23 J4,
min ω1 + 32 + x3 + 3s.
s.t. 2
s 1
s.t. =
1/2
1/2
22 =
at
23 +4
+ x4 # 3,
-+
24 + 24 =
2 Tj 1 15 5
1/4
W14
Ij 2 1, 15j54.
Figure 2: LP-graphs that cannot be distinguished by the WL test. Since the features and neighbor information of {w;} and {w;} the two graphs are equal, holds for both graphs that C ... C... and C -... Ca for all 2 O, whatever the hash functions are chosen. Based on this graph pair, we construct three pairs of LPs that are both infeasible, both unbounded, both feasible bounded with the same optimal solution, respectively.
Furthermore, (G, H), (G, fr) E T (R), then it holds that T sotu H) = OW (Denti H)) for some ow E S.-
In other words, the above theorem guarantees the sufficient power of the WI. test for separating L.P problems with different characteristics, including feasibility, optimal objective value, and optimal solution with smallest fn-norm (up to permutation). This combined with the following theorem, which states the equivalence of the separation powers of the WL test and GNNs, yields that GNNs also have sufficient separation power for LP-graphs in the above sense.
Theorem 4.2. For any (G, (G, E Gm,n HY x H.W the followins are equivalent:
(i) (G, H) and (G, H) are not distinguishable by Algoritim
(ii) F(G, H) = F(G, H), F E FeNN.
(ii) For any Fw E F.W. there exists ow E Sn such that Fw Fw H) = ow (Fw (G, M)).
Theorem 4.2 extends the results in Xu et al. (2019;; Azizian & Lelarge (2021) 2022 to the with the modified WL test (Algorithm I and LP .rapphhss....
Geerts & Reutter
Representation power Based on the separation power of GNNs, one is able to investigate the rep- resentation/aprroiimtiion power of GNNs. To prove Theorems 3.2 3.4, 3.6 we first determine the closure of FANN or GNN in the space of invariant/equivariant continuous functions with respect to the sup-norm, which is also named as the universal approximation. The result of FaNN is stated follows, where C(X, IR) is the collection/algebra of all real-valued continuous function X. The result of JWW can be found in the appendix.
Theorem 4.3. Let X Gm, H. H.W be a compact set. For any & C(X, R) that satisfies (G, H) (GG, H) for all (G, H), (G. H) X that are not distinguishable by Algorithm | and any > 0, there exists F E FaNN such that
sup (G,H)XX
- <E
Theorem 4.3 can be viewed as an LP-graph version of results in Azizian & Lelarge (202)): Geerts & Reutter (0022). Roughly speaking, graph neural networks can approximate any invariant continuous function whose separation power is upper bounded by that of WL test on compact domain with arbi- trarily small error. Although target mappings Peess Looj. P not continuous, we prove (in appendix) that they are measurable. Applying Lusin't 's theorem (Evans & Garzepy] 2018 Theorem 1. 1.14), show that GNN be arbitrarily close to the target mappings except for small domain.
8

---

Published as a conference paper at ICLR 2023
5 NUMERICAL EXPERIMENTS
We present the numerical results that validate our theoretical results in this section. We generate LP instances with m 10 and n 50 that are possibly infeasible or feasible and bounded. To check whether GNN can predict feasibility, we generate three data sets with 100, 500, 2500 inde- pendent LP instances respectively, and call the solver wrapped in scipy. optimi ze linprog to get the feasibility, optimal objective value and an optimal solution for each generated LP. To generate enough feasible and bounded LPs to check whether GNN can approximate the opti- mal objective value and optimal solution, we follow the same approach randomly and discard those infeasible IPss until the number of LPs reach our requirement. We train GNNs fit the three IPP characteristics by minimizing the distance between GNN-output and those solver-generated labels. The building and the training of the GNNs are implemented using TensorFlow, The codes are modified from Gasse et al. 2019) and can be found in /etps://giihhe com/ http:/uujlllggg learnable functions fin Jin fout: Jom (f ft" oi 91 T/v are all parameterized with MLPs. De-
before to generate LP
GNN LP, gitt] We set L -= 2 for all GNNs and those
tails can be found in the appendix. Our results are reported in Figure 3
0.4
Num of Samp: 100
Num of Samp: 100
Num Samp: 100
Rate of errors
0.3
Num of Samp:
Num of Samp: 2500
Mean squared error
1.00
0.75
Num Samp: 2500
Samp:
Mean squared
3
Num Samp: 2500
Num Samp: 500
0.2
0.50
2
0.1
0.0
0.00
10a
10
10
10a
10
10
10*
10
10s
10'
Num. of GNN parameters
Num. of GNN parameters
Num. of GNN parameters
(a) Feasibility
(h) Optimal objective value
(c) Optimal solution
Figure 3: GNN can approximate Prenss Pobj. and P
All the errors reported in Figure 3 are training errors since generalization is out of the scope of this paper. In Figure Bal the "rate of errors" means the proportion of instances with [F * (G, H). This metric exactly equals to zeros as long as the number of parameters in GNN is large enough, which directly validates Corollary [33] the existence of GNNs that can accru- ately predict the feasibility of LP instances. With the three curves in Figure combined together, we conclude that such principle does not violate as the number of samples increases. This con- sists with Theorem 3.2 Mean squared errors in Figures 3bb and 3c are respectively defined as B m [F,G, H)- T teas (G, 12 and E,G, |I H) Preas (G, Thereforee Figures 3b
and 3c validates Theorems 3.4 and 3.6 respectively. Note that all the instances used in Figure 3b
feasible and bounded. Thus, Figure 3b actually only validates (3.2) in Theorem 3.4 However, due to the fact that feasibility of an IP is equal to the boundedness of its dual problem, one may
dualize each LP and use the conclusion of Figure Ba to validate (3.1) in Thcorem 3.4 Some extra
experimental results on generalization, i.c., the performance of the trained models on the test set, are presented in Appendix G
CONCLUSIONS
In this work, we show that graph neural networks, as well as the WL test, have sufficient separation power to distinguish linear programming problems with different characteristics. In addition, GNNs can approximate LP feasibility, optimal objective value, and optimal solution with arbitrarily small errors compact domains finite datasets. These results guarantee that GNN is a proper class of machine learning models to represent linear programs, and hence contribute to the theoretical community. Future directions include the size/complexity of
foundation in the GNNs and the generalization, that are not covered in our current theory but are of great importance. Another future topic is investing the representation power of graph neural networks for mixed- integer linear programming (MILP), which has been observed with promising experimental results in the literature.

---

Published as a conference paper at ICLR 2023
REFERENCES
Brandon Amos. Tutorial on amortized optimization for learning to optimize over continuous do- mains. arXiv preprint arXiv:2202. 00065, 2022.
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. 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, 26(3):677-655, 2017.
Waiss Azizian and Marc Lelarge. Expressive power of invariant equivariant graph neural net- works. In International Conference on Learning Representations, 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-611 2017.
Dimitris Bertsimas and John N Tsitsiklis. Introduction to linear optimization, volume 6.
Emmanuel J Candes and Terence Tao. Decoding by linear programming. IEEE Iransactions on information theory, (112))4203-42155 2005.
Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. In Pro- ceedings of the Thirtieth International Joint Conference Artificial Intelligence, IJCAI-21, pp- 1348-4355, 2021.
Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to optimize: primer and a benchmark. arXiv preprint arXiv:2103. 12828, 2021.
Yize Chen, Ling Zhang, and Baosen Zhang. Learning to solve dcopf: A duality approach. Electric Power Systems Research, 213:108595, 2022.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns, Advances in neural information processing systems, 32, 2019.
George Cybenko.
Approximation by superpositions of sigmoidal function. Mathematics control, signals and systems, 204):303-314, 1989.
Antoine Dedieu, Rahul Mazumder, and Haoyue Wang. Solving I1-regularized svms and related linear programs: Revisiting the effectiveness of column and constraint generation. Journal of Machine Learning Research, 23(164):1-41, 2022.
Deepiyoti Deka and Sidhant Misra. Learning for dc-opf: Classifying active sets using neural nets. In 2019 IEEE Milan PowerTech, pp. 1-6. IEEE, 2019.
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 on Artificial Intelligence, volume 34, pp. 1452-1459, 2020.
Iddo Drori, Anant Kharkar, William R Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on real-world graphs in linear time. In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMIA), pp. 19 19-24. IEFE, 2020.
Lawrence C Evans and Ronald Garzepy. Measure theory and fine properties of functions. Rout- ledge, 2018.
10

---

Published as a conference paper at ICLR 2023
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.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th international conference on international conference on machine learning. pp. 399 406, 2010.
Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning 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. 2022.
Fred Hanssmann and Sidney W Hess. A linear programming approach to production and employ- ment scheduling. Management science, (1):46-51, 1960.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural networks, 2(5):359-366, 1989.
Stefanie Jegelka. Theory of graph neural networks: Representation and learning. arXiv preprint arXiv:2204.077 07697, 2022.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.00 01227, 2019.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. On the universality of graph neural networks on large random graphs. Advances in Neural Information Processing Systems, 34:6960-6971 2021.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
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 arXiv:1412.6980 2014.
Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Pan Li and Jure Leskovec. The Expressive Power of Graph Neural Networks, pp. 63-98. Springer
Nature Singapore, Singapore, 2022.
Xijun Li, Qingyu Qu, Fangzhou Zhu, Jia Zeng, Mingxuan Yuan, Kun Mao, and Jie Wang. Learning to reformulate for linear programming. arXiv preprint arXiv:2201.06216, 2022.
Defeng Liu, Matteo Fischetti, and Andrea Lodi. Learning to search in local branching. In Proceed- 2022.
ings of the AAAI Conference on Artificial Intelligence, volume 36, pp.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Con- ference Learning Representations, 2020.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019a.
Haggai Maron, Ethan Fetaya Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International conference on machine learning, pp. 4363 4371- PMLR, 2019b.

---

Published as a conference paper at ICLR 2023
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021.
Vishal Monga, Yuelong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, 38(2):18-44, 2021.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O' D'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012. 13349, 2020.
Xiang Pan, Tianyu Zhao, Minghua Chen, and Shengyu Zhang. Deepopf: deep neural network approach for censtry-const de optimal power flow. IEEE Transactions Power Systems, 36(3) 2020.
Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to by looking ahead: Cutting plane selection via imitation learning. In International Conference on Machine Learning, pp. 17584-17600, PMLR, 2022.
Yun Peng, Byron Choi, and Jianliang Xu. Graph learning for combinatorial optimization: survey of ofate-of-the-art. Data Science and Engineering, 6(2):19-141, 2021.
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.062 2022.
Walter Rudin. Functional Analysis. International series in pure and applied mathematics. McGraw- Hill, 2nd edition, 1991. ISBN 9780070542365.
Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint wwXiv:2003.04078, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. Advances in Neural Information Processing Systems, 32, 2019.
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. 1-8. IEEE, 2021.
Vlad Timofte. Stone-weierstrass theorems revisited. Journal of Approximation Theory, 136(1): 45-59, 2005.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. AI Open, 1:57-81, 2020.
12

---

Published as a conference paper at ICLR 2023
A WEISFEILER-LEMMAL (WL) TEST AND COLOR REFINEMENT
The WL test can be viewed as a coloring refinement procedure if there are no collisions of hash functions and their weighted averages. More specifically, each vertex colored initially accord- ing to the group it belongs to and its feature two vertices have the same color if and only if they are the same vertex group and have the same feature. The initial colors are denoted as C C2
CO.V. C C... C2 C..W ..... C.WW Then at iteration l, the set of vertices with the
m
same color iteration I - 1 are further partitioned into several subsets according to the colors of their neighbours Iwo vertices v, and by are in the same subset if and only if C.-I. Cl-VV and for any C E {C] [C/-LW 11 S n).
Σ O- =C
Eng=
Σ
E
C.-,W=C
and it is similar for vertices w, and Wyr. After such partition/refinementt vertices are associated with the same color and only if they are in the same subset, which is the coloring at iteration 1. This procedure terminated if the refinement is trivial, meaning that
with the same color partitioned into at least two subsets, i.e., the coloring is stable. For more information about color
refinement, we refer Berkholz al. (2017) Arvind al. (2015) 2017).
We then discuss the stable coloring that Algorithm [ will converge to, for which we made the following definition, where S S and S; n Sy 0, A1 S <.
(2,,S2..... 8.} is called a partition of set if UUS
Definition A.1 (Stable Partition Pair of Vertices). Let G = (V U E) be a weighted bi- partite graph with V (Uz, U2...., )m W (wi, W2, wnt, and vertex features
(hY h22 ...., h h .h hww!... ......... ), and let I = II.. Io} and J (J..J2...... Jt} be and {1, ..2.....,. n., respectively, We say that (I, J] is a stable partition
purtitions of {1,2,... (1,2,...,,) ,,) pair of vertices for the graph G if the followings are sutisfied:
(i) hY = h holds if i E Ip for some E {1,2......
(ii) hy = ny holds j.j j' E for some q E {1,2..... t).
(iii) For any p E {1, $) q {1,2, f and i Lp. Eies, Eis Ejes, Ev
(iv) For any p E 21, E (1,2, j.j' E Jq. Ever, Fig = Esel, Ea.y-
We denote (I',J) as the partition pair corresponding the coloring iteration 1 of Algorithm Suppose that there are no collisions. Then it is clear that (I'+I_(++) is finer than (I². Jo). denoted as (I J(+1) I (I'TT), which means that for any E T'+1 and any J Jl41 there exist
I' I' and J' E Jt such that I C I' and J C J'. In addition, (I++),](+)) ) (I) J if and only
(I', Jt) is a stable partition pair of vertices. Note that there is at most O[V] + [WD iterations
leading to strictly finer partition pair, i.e, We can immediately obtain the following result:
= (I.TT)) but (I++) I
(I)T))
Theorem A.2. If there are no collision of hash functions and their weighted averages, then Algo- rithm 1 terminates stable partition pair of vertices in O(IVI + Wl) iterations.
Furthermore, for every (G, H) Gm, H. x H.W the coarsest stable partition pair of vertices exists and is unique, which can be proved using techniques similar to the proof of Berkholz et al. the unique coarsest stable partition pair. This is because that the coloring gin each iteration of Algorithm [ always coarser than the unique coarsest stable partition pair (see Berkholz et al. (017) Proposition 2)).
(2017) Proposition 3). Algorithm | terminates
B SEPARATION POWER OF THE WL TEST
This section gives the proof and some corollaries of Theorem 4.1 First we present some definitions and lemmas, from which the proof of Theorem 4.1 can be immediately derived.
13

---

Published as a conference paper at ICLR 2023
Definition B.1. Given (G,H), (G, H) 9m. Hm H. we say that (G, H) and (G. H) can be distinguished by the WL test if there exists some L E N and some choices of hash functions, H. HASHo,w. H, HASHL, HASH v. and HASHL.w for lorl= 1,2..... ..... L, such that the multisets of colors at the L-th iteration of the WL test are different for (G, H) and (G, H). Let ~ be an equivalence relationship on Im. x Hm x Hy defined via: (G, H) ~ (G, H) if and only if they can not be distinguished by the WL test.
is clear that (G, (G, Hf) if they are isometric, i.e., there exist two permutations, ov m) + (1, mm and ow E.g, hV (a) R.. and h (5) = h, for any 2.. m} and j E {1,2...., ever, not every pair of Wi-indistinguishable graphs consists of isometric ones; see Figure example. However, for LP problems that cannot be distinguished by the WL test will share some common properties, even if their associated graphs are not isomorphic.
m + 21,2..... n). such that (i)
.2....,77 n). How-
2 for an
Lemma B.2. If two weighted bipartite graphs with vertex features corresponding to two LP prob- lems are indistinguishable by the WL test, then either both problems are feasible or both are infea- sible. In other words, the WL test can distinguish two LP problems if one of them is feasible while the other one is infeasible.
Proof of Lemma B.2
Let consider two LP problems:
min cJx,
#ER"
(B.1)
s.t. Ar b.lsssu
and
min #ER
(B.2)
s.t. 6 i i
Let (G, H) and (G. H), where G (V W W. F. and (V F), be the weighted bipartite graphs with vertex features corresponding
and B.2 respectively.
Since (G, H) (G, ff), for some choice of hash functions with no collision during Algorithm
for (G, H) and (G, H), Theorem A.2 guarantees that Algorithm outputs the same stable color- ing for (G, H) and (G, H) up to permutation. More specifically, after doing some permutation, J2...2..... J1. that are partitions of {1.2..... m) and (1.2....,n)) respectively, such that the followings hold:
there exist [2,, .2..... } and
(b,, o.) (bi, 63) and is independent of E Ip. for any p E (1,
(1),1)) = (I, úg) and is independent of E Jn for any E
1). Ejer, Ai, Ejer, Aig and independent of For any p {1, ,. and q E (1,2,... 1}. EiEr, Ar, Eier, Ar, and is independent of
For any 21.,,...,a.) and y E i E Lp.
jE Jq.
Suppose that the problem B.1 is feasible with R be some point in the feasible region. Define y RD via B4 [J,] EjE,, 2j and E R via ă yq. j E Jg. Fix any p E f1,2...... and
some in E Ip. It holds for any E I that
Σ =1
Acyz, oz bi, i.e., Σ Σ q JEJg
Aijj Oio bios
which implies that
ALJ=, [pp jElj
Ais By oso bio
RE g=1
14

---

Published as a conference paper at ICLR 2023
Notice that LiEr, At, is constant for j J4p 4q E f1.,,..., Let us denote ag =EiEI, Aig Eier, Ang for any E Jq- Then it holds that
Σ FELP
And
Bo too bio
Ip q=1jEJ,
pT
[
g=ljEJo
q=1 jEJ,
Note that
Σ Ass
1
Σ
Ans
Ug.
q=1 1eJ,
HET
IET q=1
and that Ejes, Aij is constant for i Lp. So one can conclude that
Σ Aijăz
Anjá Σ
Σ
Ais
yo oz bi.
Vie 1p
JEJ,
JEds
which leads to Aë b. It can also be seen that = 1 S a u us ú. Therefore, is feasible for B.2
We have shown above that the feasibility of (B.1) implies the feasibility of B.2) The inverse is also true by the same reasoning. Hence, we complete the proof.
Lemma B.3. If two weighted bipartite graphs with vertex features corresponding to two LP prob- lems are indistinguishable by the WL test, then these two problems share the same optimal objective value (could be oo or -o)).
If both problems infeasible, then their optimal objective values are both We then consider the case that both problems are feasible. We use the same setting and notations as in Lemma B.2. and in addition we have that Cj = êj. which is part of 1y h. is independent of j E Jg for any E (1,). Suppose that x is an feasible solution to the problem (B.T) and let E IR" be defined via â; = [.a Eyee, Ty', j E Jg- It is guaranteed by the proof of Lemma B.2 that & is a feasible solution (..2). One can also see that cT = ē f. Since this holds for any feasible solution to (B.I). the optimal value of the objective function for (B.2) is smaller than or equal to that for B.I. The inverse is also true and the proof is completed.
Proof of Lemma B.3
Lemma B.4. Suppose that two weighted hipartite graphs with vertex features corresponding to two LP problems are indistinguishable by the WL test and the their optimal objective values are both finite. Then these two problems have the same optimal solution with the smallest (--norm, up to permutation.
Proof of Lemma B.4 We work with the same setting as in Lemma B.3 where permutations have already been applied. Let æ and x' be the optimal solution to (.. and (B.2) with the smallest 2z- 22-norm, respectively. (Recall that the optimal solution to a LP problem with the smallest norm unique, see Remark 2.2) Let & E Ra be defined via à
J4l Lj,e, Iy for j E Jy. =
1, 2, t. According to the arguments in the proof of Lemma B.2 and Lemma B.3 a is an optimal solution to (.2). The minimality of x' yields that
| < |1113
1
Σ JEJ
2
||011
Iz
[gg]
Jg]
jEJn
JEJ
(B.3)
which implies | < |a||| The converse | < ||'||| || is also true. Therefore, we must have ||ж||| = ||~'|| and hence, the inequalities in (B.3) must hold as equalities. Then one can conclude that 2, Zy for any j.j' E Jg and 1, 2, ..... which leads to x f. Furthermore, it follows from [|a||| = ||ق|| and the uniqueness z' (see Remark 2.2 that I' = 2 = æ, which completes the
proof.
15

---

Published as a conference paper at ICLR 2023
One corollary can from the proof of Lemma [.4 is that the components of the optimal solution with the smallest f--norm must be the same if the two corresponding vertices have the same color in the WL test.
Corollary B.5. Let (G, H) be a weighted bipartite graph with vertex features and let x be the optimal solution to the corresponding LP problem with the smallest En-norm. Suppose that for some ....,,,,,,..
j.j' 11,2....,,A n). J.j = xz-
one has Ch,. = - for any E N and any choices of hash functions, then
Let us also define another equivalence relationship on Gmn Hy HW where colors of W1, ,2,,..., w, with ordering (not just multisets) are considered:
Definition B.6. Given If) (G, it) E 9m. x Hy x HWw (G, and (I) are not in the same equivalence class of W. ~ if and only if there exist some L E N and some hash func- tions HASHo,v. HASHo,w, HA HASH,, HASH and HASH I 1.2,... L,, such that (1C ..C.V. ...... ,t..,Oth.] * (10T CO..V. ..... ....,Ch.Vy) CL,V3 C. * C.WW for some j E (I......,n..
is clear that (G. H) W. (G, H) implies (G, H) ~ (G, H). One can actually obtain a stronger version of Lemma B.4 given (G, H) W (G.
Corollary B.7. Suppose that two weighted bipartite graphs with vertex features corresponding to two LP problems, (G, H) and (G, Ht,, satisfies that H) W. (G, ff). Then these two problems have the same optimal solution with the smallest Ez-norm.
Proof of Corollary B.7 permutation
The proof of Lemma B.4 still applies with the difference that there is no
[w), u2....,,n
Proof of Theorem
4.1 The proof of Theorem
follows immediately from Lemmas B.2
B.3 and
B.4
C SEPARATION POWER OF GRAPH NEURAL NETWORKS
i.e., the separation power of GNNs is equivalent to that of the WI. test. Similar results can be found in previous literature, see e.g. Xu et al. (2019); Azizian & Lelarge| (202T); Geerts & Reutter (2022). We first introduce some lemmas that can directly imply Theorem 4.2 The lemma below, similar to Xu et al. (2019 Lemma 2), states that the separation power of GNNs is at most that of the WL test.
This section aims to prove Theorem 4.2
Lemma C.1. Let (G, H), (G. fr) E 9m, x HY x H.W If H) ~ (G, M) then for any Fw GNN there exists a permutation ow E Sn such that Fw H) = ow (Fw(G, if).
Proof of Lemma C.1 First we describe the sketch of our proof. The assumption (G, ~ (G. H) implies that, we apply the WL test on (G, H) and (G, H). the test results should be exactly the same whatever the hash functions the WL test we choose. In the first step, we define functions that are injective on all possible inputs. Second, we show that, if we apply an arbitrarily chosen GNN: Fw E GNN on (G, H)) and (G, H). the vertex features of the two graphs are exactly the same up to permutation, given the fact that the WI. test results are the same. Finally, it concludes that Fw (G, H) should be the same with Fw Fw(G, (G, H) up to permutation.
of hash
FW
Let us first define hash functions. We choose HASHo, and HASHo, w that are injective on the following sets (not multisets) respectively:
(hY y. bY ...., KX and {h ,...,,,, A. "...,....,,. A.W.
Let (C.-- L I (C/-L 1 and (c, (CL-LV
pm Jim: (C, (d.-1, py be the vertex colors in the (1-1)- th iteration (1 < 1 < L) in the WL test for HG and (G, H) respectively. Define two sets (not
1,
multisets) that collect different colors:
CK = (C--LV
1.-1V G A1
CL-L.
On
16

---

Published as a conference paper at ICLR 2023
and
C = (C- ,...., C...,,CC-L Ch-1. . C4-1.W ,.... ,...,,,,.II, C.
The hash function HASH, and HASH', are chosen such that the outputs are located in some linear spaces and that (HASH), C E CV-,) and (HASH), w (C) C C both lin- early independent. Finally, we choose hash functions HASH,, and WASH,, such that H injective the (not multiset)
{
C dL-V
Σ j=1
E. HASH W
(C/-IM)
i1sism
61-1,
Σ
Beg HASH (c/-.M)
:1 pisismy m
and that HASH,, is injective on the set (not multiset)
{
c L. Σ
HASHI (c.-
:.SiS"
mm
61-1. Σ
H., (c.-.V) :isisn
Those hash functions give the vertex colors at the next iteration (I-th layer): {C, im (C,
in 1j=1
and (CA.V) 1m (0, in 1j=1-
Consider any Fw E FWh and let (1/ 1.V 1 REE:: (n Yー and ( 1.1 1,V
i==: {7;
1,1 In j==1 be
the vertex features in the 1-th layer (0 < 1 < L) of the graph neural network Fw. (Update rule refers We aim to prove by induction that for any {0, 1. ...,, L), the
equations 2.1 2.2
(2.5))
followings hold:
(i C.Y. C/7 implies h." h/ for S i S m;
(ii) CI. C implies
R L.V h for < i, S m;
(ii) C.V 6 implies h R for S i, S m;
(iv) CfW = o implies h = n for S j.j' S m
(v) GrW G.WW implies h. i.W.W for 1 S j,j' S m
J.W (vi) Ch = C implies h = h2 for < j.J < n.
The above claims (i)-(vi) are clearly true for due the injectivity of HASHo, and HASHo,W. Now we assume that (i)-(vi) are true for some I E 1........ I 1-1). i.e,
Suppose that C.. = C
C. L.- Σ E. HASH', (CH-I.
HASH,V
j=1
Fv FagHAN HASH (c.
= =HASHL
C.-LVV
1=1
for some 1 i, S m. It follows from the injectivity of HASH, that
-.-.V
C.V.V
(C.1)
17

---

Published as a conference paper at ICLR 2023
and
a HA,HHAHH (c--..)
Σ
Ee HASHi (c--L.).
==1
==1
According to the linearly independent property of HASH w. the above equation implies that
Ed O--LW=C
Σ
Σ
Er
ICECK
(C.2)
Note that the induction assumption guarantees that h n 1- as long C, -.-1. -d--.
So one can assign for each C' E C some h(C) E RRd such that h2 -, = h(C) as long as C. for any j S n. Therefore, it follows from (C22 that
Σ El (hl (
Σ
Σ
Easli (M(C))
CEC C C/-LW=G
Σ
Σ
Beght (M(C))
Σ
CEC
C
j=1
Note also that (C.I and the induction assumption lead to h that
1-1V =
h2
Then one can conclude
A. of
L. Σ
Bashi (nl (11-1.)) oe
1 Σ Es JS (hl (1)-1.1))
j=1
This proves the claim (i) for I. The other five claims can be proved using similar arguments. Therefore, we obtain from (G, (G, H) that
(14. L.V. L.V ...., h
L. }}
RRL. BLV
BLV1
and that
{ h h2 h.w.
L.W.
mn ([ ..W.
R.W. { }]
By the definition of the output layer, the above conclusion guarantees that Fw (G, H) ow (F (Fw(G. H)) for some ow E Sn.
(1,,,,GG, Lemma C.2. Let (G, II, (G, it) E Gm,n Hy. H. Suppose that for any Fw FW there exists a permutation ow E Sn such that Fw (G, H) = ow (Fw (G, H)). Then F(G,H) = F(G, H) holds for any F E FoNN-
F
Proof of Lemma C.2 Pick an arbitrary F FaNN. We choose Fw J.y such that
(G' H1') = (F(G', H!)...., F(G', E RR, (G', , Ht') E Gm,n x H. x W
Note that every entry in the output of Fw is equal to the output of F. Thus, it follows from (G, = ow (Fw (G, fr) that F(G, H) F(G,
The next lemma is similar to Xu al. 2019 Theorem 3) and states that the separation power of GNNs is at least that of the WL test.
Lemma C.3. Let (G, H). (G. ff E Im, x HY x HW. F(G, H) F(G. H) holds for any F E FeNu, then (G, H) (G, M
18

---

Published as a conference paper at ICLR 2023
Proof of Lemma C.3 It suffices to prove that, if (G, H) can be distinguished from (G. H) by the WL test, then there exists F E FGNN, such that F(G, H) F(G, H). The distinguish-ability of the WL test implies that there exists L E N and hash functions, HASHo,y, HASHo,w, HASH,V w. HAS v. and HASH, w for I = .,,,....4. L, such that
(f CZ.Y
C.. }] ff .O,. ....,,CLV) OLV)) C...
(C.3)
H C...
}}
+ Hf CCr ...., C..W 11
(C.4)
We aim to construct some GNNs such that the followings hold for any I = 0, ,,.., L:
(i) h k implies C.V. C/ for i S m:
(ii) B.Y ky implies C... = C for < i S m.;
(iii) b. k. implies C.V. = C for S S m.
(iv) new 1
L.W implies C. c.W for 1 S j.j' Sm;
(v) h.W hLw implies C W C.y C..WW for S j.j' S n
(vi) n.w h2 implies C. = &.. for S j.j' S n.
It is clear that the above conditions (i)-(vi) hold for l = 0 as long as we choose f. and SW that are injective on the following two sets (not multisets) respectively:
(hY...., No ,Y,...,
3 and {/1 ..... A WW WW.
We then assume that (i)-vvi) hold for some 1 < L. and show that these conditions are also satisfied for / if we choose fL f.W oh g properly. Let us consider the set (not multiset):
a21.aa....,,a.) Rd--
that collects all different values in M/ 1. 11 1 ..... " 11-1, W.-1. R/- M/-1. ..... 1 Let di 2 and let edi = (O.....0, 0, other entries being 0, for S p 1,.,,...,00 0) be the vector in Te with the p-th entry being and all Choose f." R1 + Rd as a continuous function satisfying JW (ap) = ed p 1, ,. and choose n) Rdd Rd Rdi that is continuous and is injective when restricted on the set (not multiset)
h 1-IV
E S (hl 1,
1siss
1/- 1--1VV 7
Eig
W (i)
:isis m m
Noticing that
n
Eas St W 1-
(h
Fig
di
1=1
and that {e di ........ edi is linearly independent, one can conclude that N. 1.V if and only and Σj Fagslh (n) (nW ΣØ= Fe (h (,-,1,W) where the second
- b1 -
condition equivalent
Σ
Eij
Σ
En Vp (1......8).
R 1-1.W may
h/- =op
19

---

Published as a conference paper at ICLR 2023
This, as well as the condition (iv) for 1 1, implies that
Σ Bag BASHAS W (c--1.m))=
Σ 1=1
Ee HASHiSH w (c.-l.m).
and hence that C.Y C/ by using hi-L.V - and condition (i) for ( - 1. Therefore, know that (i) is satisfied for 1, and one can show (ii) and (iti) for using similar arguments by taking di large enough. In addition, f!' and 9tth can also be chosen in similar way such that (iv)-(vi) are satisfied for
Combining
and condition (i)-(iv) for L, obtain that
{{ L.V. ....
km
L.V
JJ
+
L.V 1 15
(C.5)
or
{
h/. 122
L.W
k..
}}
W... J.W.
L.W. }
1]
Without loss of generality, we can assume that (C.5) holds. Consider the (not multiset)
02..........8 3t} C TRd
kLV. Let be that collects all different values in N. L.V. ..... ,..., LLV N.V N.V ...., m
positive integer that is greater than the maximal multiplicity of an element in the multisets L.V
[(h h22 ..... hLV1) and (( A...V ..... 1.41). }). There exists continuous function P Rdd. - R such that ((5g) = k7 for q 1.2..... and due C..5 and the fact that the way of writing an integer as k--ry expression unique, hence holds that
m
Σ
c
p(h V.
Set the dimension of (L + 1)-th layer as 1: dr+1 = 1, and set f141Y O, fL+1. O, IL+1, (h, 0) = (h)), and 9L+1.W = O. Then we have h, I+,V (hh, L.V }, h L,,IV = =p(h, V.
and h2 hLW h W for ...,... and Sow h²) h. Then it follows that
1,2,...,,. Define fou. R x R R via
n.
12
m
four Σ
h4
L+IV
Σ
hg
1+1.W
Σ (
1=1
p((t..v) four
L+1.
Σ
R
which guarantees the existence of F FaNN that has L layers and satisfies F(G, H) * H).
Proof of Theorem 4.2
The equivalence of the three conditions follow immediately from
Lemma C.I C.2 and C.3
Corollary C.A. For any weighted bipartite graphs with vertex features (G, H), H) Im x HV x H. the followings are equivalent:
(i) (G W. (G
(ii) For any Fw Fi it holds that Fw (G) FW ft).
Proof of Corollary C.4 The proof follows similar lines as in the proof of Theorem 4.2 with the difference that there is permutation on (Wi, W2,-.. W.).
20

---

Published as a conference paper at ICLR 2023
In addition the separation power of GNNs for two weighted bipartite graphs with vertex features, one can also obtain results on separating different vertices in one weighted bipartite graph with vertex features.
Corollary C.5. For any weighted bipartite graph with vertex features (G, H) and any j.j E f1,2,... n., the followings are equivalent:
(i) Cj = C. holds for any E N and any choice of hash functions.
(ii) Fw GW, H)j Fw (G, H)y. V Fw FW
GNN
Proof of Corollary C.5 "(i)
(ii) and "(ii) = (i)" can be proved using similar arguments in
the proof of Lemma and Lemma respectively.
D UNIVERSAL APPROXIMATION OF FGNN
This section provides the proof of Theorem 4.3 The main mathematical tool used in the proof is the Weiersssssss theorem:
Theorem D.1 Soinne--eessstrss theorem (Rudin 1991, Section 5.7)). Let X be a compact Haus- dorff space and let F C C(X, IR) subulgebra. If J separates points on X, iee.for any x, x' X with x F x', there exists F E F such that F(x) + F(x'), and E F, then F is dense in C(X, IR) with the topology of uniform convergence.
Proof of Theorem 4.3 Let X + X/ ~ be the quotient map, where (XX X/ is equipped
with the quotient topology. For any F E FGNN, since F : X + IR is continuous and by Theorem F(G, H) = F(G,H), A (G, ~ (G, H), there exists a unique continuous F x(X) + IR such that F = F a æ. Set
FONN [ F FANN] c((m(X),B)
In addition, the assumption on 4, i.c.
(G, H) = (GG
(G. ~ (G, M.)
leads to the existence of unique & C(T((),.) with +b $
Since X is compact, then (XX) is also compact due to the continuity of According to Lemma D.2 below, FaNN is a subalgebra of C(= (X), R). By Theorem 4.2. FANN separates points on ((X). This can further imply that T(X) ) is Hausdorff. In fact, for any x; x' E ((X). there exists f E FONN with F(x) * F(x'). Without loss of generality, we assume that F(x)) < F(x') and choose some E I with F(x) < < ((x'). By continuity of F. we know that F--(((-0, c)) n (X)) and F- ((c, n (X) are disjoint open subsets of (X) with
F ((-o( c)) n (X)) and x' E F- +2)) n xX)), which leads to the Hausdorff property of (X). Note also that 1 E FANN. Using Theorem D.I can conclude the denseness of FANN in C(T (X), IR). Therefore, for any e > 0, there exists F FGNN, such that
sup (G.H)EX
|& H)) F(G, sup =EF(X)
(e(x) - - <E.
which completes the proof.
Lemma D.2. FONN is subalgebra of C(Gm, x HV x H.W RR), and as a corollary, FoNn is subalgebra of (( x HV x HW ~ ~R RR)
Proof of Lemma D.2 It suffices show that FONN is closed under addition and multiplication. Con-
sider any F, f FANN. Thanks to Lemma D.3 we can assume that both F and f have L layers. Suppose that F is constructed by
f HV Rd
JW W do
NY. WW -d + RRd,
gi gt de dR - Rd ISLLL
for : Rd, x dR + R,
21

---

Published as a conference paper at ICLR 2023
and that F is constructed by
Pn HV Redo Aw HW Rd. fL fiW R. 1 Rd, of .l" IR
R +R. 131sL.
fou: :Rd x Rd + R.
One can then construct two new GNNs computing F and F F as follows: The input layer
The update rule of the input layer is defined by
f HV Rd x Rdo, P. h + (A) (h))
eW H R x Edd
h (IW (n). f (h))
Then the vertex features after the computation of the input layer h. and h.. are given by: h.v Ch (1/) (L PM (14 F. RRdo Rd h.w tH (h))) (FI (hW) AW (h))) (h) h..h) 12 R m, and j = 1, .n.
for i = -12...,,,,
The 1-th layer (1 < L) We set
F/ Rdd x Rddi- IR: x Rdd,
hh, + (f ( (h)).
W Rd
x Rd Rdt Rd.
(h. + (1 (h), (( (i))
gY RR- x Rdi
x Rd ad. + Rd x IR
(h, h 11', in')
(gt" (h, 10, ot (h, (i,
+
and
gi W
R
R x R
Rd Rdd x Rd
(h, h')
(g) (h, h'), oy (h. R').
Then the vertex features after the computation of the 1-th layer h and h W are given by:
h
VV
v
h
1-
Fas G. (a (h.-1.m0
==1
gi
h
1-1.V Σ
Ea (
.6 h
b Σ j=1
Ex aw (h) (11-1117)))
1=1
V R.V.V E Rd Rd.
and
h.W
h = w
1-1 Σ
Eg, ry (h) (n--11/))
i=l
22

---

Published as a conference paper at ICLR 2023
gi M1 1, Σ
m
Fight (n4
h
Σ i=1
m
F f (h- (1/-115)
(nw hi:w) Rd Rd
for 1,2..., m, and j 1.2: ..... !1.
The output layer
To obtain F + F, we set
rodd Rd Ed x Rd Rdd +
R ((h, h), (h', RD) + Sour (h, N¹) + Soun (hr N.)
Then it holds that
padd out
L.V
L.W
fout
Σ
L.V
L.W
+ four
Σ
h4
L.V
n.
i=1
i=1
3=1
i=1
j=1
=F(G, F(G, H).
To obtain F FF, we set
enultiply
out
Rd x Rede x Rdd x Red -
R
((h, h), (h', h() + Sou(h, h') Soul (h, N!)-
Then it holds that
m
n
m
n
m
72
emultiply out
L.V.
L.W
= fout
h
L.V
h
L.W
foul
h
L.V
L.
j=1
5=1
H) F(G, H).
The constructed GNNs satisfy F(G, H) + P(G. H) E FaNN and F(G, H) F(G H) E FaNN. which finishes the proof.
O
Lemma D.3. If E FANN has L, layers, then there exists F E FaNN with I + 1 layers such that F F=F.
Proof of Lemma D.3 Suppose that F is constructed by f. fw fouss i&l' S.W .y .9t Nl=o- We
W L
choose fY. O. JWy 0, (h, h') h, W. (h, h²) h. Let F be constructed by fy. Jin Sow: {V ft .g .g 1 Then F has + layers with f= F.
E UNIVERSAL APPROXIMATION OF GNN
This section provides universal approximation result of FW
Theorem E.1. Let X C Gm.n X HV x H. be a compact subset that is closed under the action of Sm x Sn Suppose that & E C(X, IR") satisfies the followings:
(i) For any ov E Sm. ow E Sn. and (G, H) E X, it holds that
$ ((ay,ow) * (G, H)) =ow(#(C. ())
(E.1)
(i) @ H) (G. ff) holds for all (G. H), (G, A) X with (G, H) E. (G,
(ii) Given any (G, H) E X and any j.j E {1, 2, n), if C.. C.W (the vertex colors obtained in the 1-th iteration in WL test) holds for any E N and any choices of hash functions,, then (G, H), GGG, H)y-
23

---

Published as a conference paper at ICLR 2023
Then for any 0, there exists F E F such that
F(G <. (G,I)ex
sup
is LP-graph version of results the closure of equivariant GNN class in Azizian & Lelarge 202 Geerts & Reutter (2022). The main tool in the proof of Theorem E. is the following theorem for equivariant functions established in Azizian & Lelarge
Theorem
generalized 2021
Theorem E.2 (Generalized Stone- Seie-Weeissstrss theorem Azizzan & Lelarge, 2021 Theorem 22)). Let X be compact topology space and let G be a finite group that acts continuously on X and IR". Define the collection of all equivariant continuous functions from X to R² as follows:
Cg(X, 12)) {F C(X, F(g * x) = F(x), VIE E X,
Consider any F CE R²) and any & E Cx(X, IR Suppose the following conditions hold:
(i) F a subalgebra of
and 1 FEF.
(ū) For any n, E X, if f(x) f(a') holds for any f E C(). with f1 E F, then for any
F there exists E G such that F(x) =g* F(x').
(iii) For any x, x' X, Ff F(x') holds for any F E F, then 4(x) = 42x²).
(iv) For any I ((1,2...., ,,)" F(x); = =((rs, FF.
X, holds that ((x), D A (,1') E J(x), where [xx
Then for any > O, there exists F E such that
[1((x) - F(x)] <e. zeX
sup
We refer to Timofte (2005) for different versions of Stone- Weierstrass theorem, that is also used in Azizian & Lelarge 2021). In the proof of Theorem E. we also need the following lemma whose proof almost the same as the proof of Lemma D.2 and is hence omitted.
Lemma E.3. FON is a subalgebra C(gm, H. HW ).).
Proof of Theorem E. Let Sm x S act on IR" via
(av,ow) y ow (v), Vav E Sm.ow E Sn, R".
Then it follows from E. that Φ is equivariant. In addition, the definition of graph neural networks directly guarantees the equivariance of functions in F. Therefore, one only needs to verify the conditions with F as Fll and G as S, in Theorem E.2
Condition (i) in Theorem E.2
follows from Lemma
E.3
and the definition of GNN-
Condition (ii) in Theorem
E.2
follows from Theorem 4.2
and FaNN C FFW GNN
Condition (iii) in Theorem
E.2
follows from Corollary C.4
and Condition (ii) in Theorem E.
Condition (iv) in Theorem follows from Corollary C.5
and Condition (iii) in Theorem
finishes the proof.
F PROOF OF MAIN THEOREMS
We collect the proofs of main theorems stated in Section 3 in this section.
24

---

Published as a conference paper at ICLR 2023
Proof of Theorem
3.1 If FfG, = F(G holds for any F E FUNN, then Theorem 4.2 guar-
antees that (G, H) (G, H). Thus, Condition (i), (ii), and (iii) follow directly from Lemmas B.2
B.3 and B.4 respectively.
Furthermore, if FG, H) = (W, A Fw E F then follows from Corollary C.4 and
Corollary B.7 that the two LP problems associated to (G, and (G, ff) share the same optimal solution with the smallest nonmm.
Then we head into the proof of three main approximation theorems, say Theorem 3.2 3.4 and
3.6 that state that GNNs can approximate the feasibility mapping tcass the optimal objective value mapping Pobj. and the optimal solution mapping & solu with arbitrarily small error, respectively. We have established in Sections D and E several theorems for graph neural networks to approximate continuous mappings. Therefore, the proof of Theorem 3.2 and 3.6 basically consists of two steps:
Show that the mappings Preas Payj. and ssolu are measurable.
(ii) Use continuous mappings to approximate the target measurable mappings, and then apply the universal approximation results established in Sections D and
Let us first prove the feasibility of Pleus Pobj. and o solu in the following three lemmas.
Lemma F.1. The feasibiliyy mapping Decas defined (2.7 is measurable, i.e., the preimages feas and Tb Jeas (1) are both measurable subsets of 9m, Hy HW.
8-1 (0)
Proof of Lemma F.T. suffices to prove that for any E (5.=2) m and any Ni, No c 21,2.... ................................ nn. the set
X = {(A, b. E IR M x R" x R MI x RNN
E R s.t. Ar b, F, 24 VjEN, xy S Mj, Vj E Na),
measurable subset in Rmxn x Rm Nil x IN Without loss of generality, we assume
that o (S...., _.....,, 2, ..... 2) where "S", "=", and "2" appear for k1, K2 An and
m 11 K2 times, respectively, S k1 S 22 S m.
Let us define function Vieas RR mx RT RINd RINN R
Rzo that measures to what
extend point in IR" violates the constraints:
Viens (4,,,1,u,
max IsiSki
Σ
Aijoy
bi
max ko <isk2
Σ
Aijar be
/=1
+
n
max Ac 4
by
Asyar
JEN. max (1) -xy)+: max (2rg 11)+ JEN,
j=1
where y/ max 0}. can seen that Vieas continuous and Viens b, u, x) only if Ax b, 2z 2 1j. A E Nr. and x; új, Vj E N,. Therefore, for any (A, b, 1, pmxa x 1 Rl glval the followings are equivalent:
if and
(A, uA E Xtess-
There exists R E N4 and x BR : {x' IR" : ||''l| S RJ. such that Viens (A, b, 4, u. = O.
There exists E N4 such that for any r E N4. View (A, u, x)) S 1/r holds for some æ e Bn B".
This implies that Xteas can be described via
U REN, rEN, #EBAnQ"
U
(AA.b,l.)) g x T R MM IR Vicas(A,
(, b, u. x. s
25

---

Published as a conference paper at ICLR 2023
Since Q is countable and V is continuous, we immediately obtain from the above expression that tees is measurable.
Lemma F.2. The optimal objective value mapping & Paij defined 2.8 measurable.
Proof of Lemma F.2 It suffices to prove that for any E {s.=2) th any Nr (1,2.....,1) and any o E R, the set
Xobj == ((A,,,,,,,)) E guxx x RT x R x [Nil x R N.I.
E s.t. c x Φ, oz b, zj 2 L,, VjEN, 2j ug Vje N.).
a measurable subset in Rmxx x Rm Rd R Nil R N. Then the proof follows the same lines
as in the proof of Lemma F.I with different violation function
Vang (,,, = max (c 2) Viens (A, 1.b,l.u. u, x)
Lemma F33 The optimal solution mapping s defined in 2.9 is measurable.
Proof of Lemma
F33 It suffices to show that for every ju {1,2, ................... the mapping
n).
Jjo solu T (R) TR,
measurable, where jo :Ra R maps vector x E R" to its ju-th component. Similar as before,
one can consider any {S. =2= mm any Nr, C (1,2...., and any ø E R, and prove that the set
solu ((A,6,c,l,u) mm R R
R Ni
R No.
The LP problem, min cTa xx s.t. Ar b, zj 11. Vje No, uy S VjE No.
ZER*
has a finite optimal objective value, and its optimal solution with the smallest & - norm, Topts satisfies (Zopt) Φ),
is measurable.
Note that we have fixed E (5,=>)) = jm and N1, Nu C (1, Let
4: mxxn x Rm x x | x R |.. + Im. x HV x H
be the embedding map. Define another violation function
Violu
(Poty ( R" R.
via
Vasua (A,b, max {(e (L c, (,,,,,))). u))) 4 Viens (A,,,,,,,,,u
which is measurable with respect to c, for any fixed x E R", due to the measurability of Pby and the continuity of Viess Moreover, Valu continuous with respect to æ. Therefore, the followings are equivalent for (A,b,c,l,u) (Poo) (R):
(,,,, u) E Xsolu-
There exists E R" with Fjjo < o, such that V (A, b, (,l,,,,,)) = 0 and Vsatu (A, b, c, 1,,,,,,),,,)) 0, V v BB 11/0 Φ
There exists R Q N.. and E BR with Ijo S 50-1/r- such that Visia (A, b, c,,, u, =
and Vaolu (A, e, 1 u, x') > 0, V BR. n',, 2 Φ.
There exists R Q+ and N.. such that for all r' E N.. 3x BR 13p < 1/r,
s.t. Vanu A, b, c, I v, x) < 1/7' and that 3 rd E N4. s.t., Vanta b, 1/1" 4
BR O Q", 2//, 2 Φ
26

---

Published as a conference paper at ICLR 2023
Therefore, one has that
X U U
REQ+ rEN
(.0)
U
(A,b,c,l,,) (Pers (R)) V..(AA.b.cu..)))))
(EN DEBnnQ", 330 SØ-+
1 (A...c. (Pary (R) (A r" 1)
P"EN+ x' EBBRQ" 4/ 20
which is measurable.
With the measurability of ieuss Pabj. and ssol established, the next step to approximate Pjeas Patj. and sotu using continuous mappings, and hence graph neural networks. Before proceeding, let us mention that Sm,, x H. x H, is essentially the disjoint union of finitely many product spaces of Euclidean spaces and discrete spaces that have finitely many points and are equipped with discrete measures. More specifically,
9m, x Hy H.W = R
R x
[
( (RU{->o)) x (RU (RU(++o))))
pmxn
x
R
R x Rn-k x I p-
x 2} 1m x f-oo {
Therefore, many results in real analysis for Euclidean spaces still apply for gm,a HY. HW and (.. including the following Lusin's 's theorem.
Theorem F.4 (Lusin's 's theorem (Evans & Garzepy 2018 Theorem 1.14)). Let μ be Borel regular measure R" and let f R" - Tddh be p-measurable. Then for any μ-measurable X R" with (xX) < oo and any > 0, there exists a compact set C X with p(X)F) F)) < 6, such that f( is continuous.
Since X C Gm. x V x xH is measurable with finite measure, according to Lusin's 's theorem, there is compact set C such that Preas E is continuous with Meas (X))) < By Lemma B.2 and Theorem 4.3 there exists F FONN such that
Proof of Theorem 3.2
sup (G,H)EE
|F(G, H) Peas (G, H)| <
which implies that
IP(, = Preas (G, H), (G,
Therefore, one obtains
Meas (H( X IF(G.))>1/2 + Prens (G, Meas(X)BB <
and the proof is completed.
Proof of Corollary 3.3 As finite set, is compact and P is continuous. The rest of the proof
similar that Theorem
3.2
using Lemma B.2 and Theorem 4.3
ii) The proof follows the same lines in the proof of Theorem 3.2 with the difference that we approximate
Proof of Theorem 3.4
11 if Do R.
GG, () 0. otherwise,
instead of & iees and use Lemma B.3 instead of Lemma B.2
27

---

Published as a conference paper at ICLR 2023
(ii) The proof is still similar to that of Theorem 3.2 By Lusin's theorem, there is a compact set
E' C X 2 (IR) such that Ponjl E is continuous with Meas ( < Using
Lemma B.3 and Theorem there exists F2 E FONN with
sup (G,H)EE
[F(GG H) - Dobj (G, <ó
which implies that
Meas (((G, H.EHEEE E:: F H) Oooj (G, 5)) s Meas (x <c
Proof of Corollary 3.5
The results can be proved using similar techniques as in Theorem 3.2 and
Theorem 3.4 by noticing that any finite dataset is compact which any real-valued function is continuous.
Proof of Theorem 3.6 Without loss of generality, we can assume that X C
abj (R) C
9mn Hy HW is closed under the action of Sm x Sn; otherwise, we can replace X by xS., (ov X. By Lusin's theorem, there exists compact subset F. X such that Meas( X) < <e/lSm x S.. and that s ry is continuous. Define another compact set:
E
n (ov,ow) E' C CX,
(oviow)ESmx5,
which is closed under the action of Sm Sn and satisfies
Meas( X (E) s
Σ
Meas(X) ((av))(( E*)
(ov.ow)ESS JES xS
Σ
Meas((av, X (ov,, * F')
Jev. xS.
Σ
u((ov,ow) (X(E')
(ov,ow)ESm. xS.
Σ
1 EXX{E')
(ES SS,
Σ
Sm x S
(dv.owlESm, x8,
Note that the three conditions in Theorem E. are satisfied by the definition of & Psolu Corollary B.7 and Corollary B.6 respectively. Using Theorem E.1 there exists Fw GNN such that
sup [[W(G: H!) 4sotu H. < 6. (G.H)EE
Therefore, it holds that
Meas (((G, H) E X: [[[WWG (G, H|] 8)) MMas(X (E\E) <e,
which completes the proof.
Proof of Corollary 3.7 One can assume that D is closed under the action of Sm Sn otherwise,
larger but still finite dataset, U (rryvow)ess Jes.. xss (av, aw) DD can be considered instead of D. The rest of the proof is similar that of Theorem 3.6 since D is compact and & lo is continuous. n
28

---

Published as a conference paper at ICLR 2023
G DETAILS OF THE NUMERICAL EXPERIMENTS AND EXTRA EXPERIMENTS
LP instance generation We generate each LP with the following way. We set m = 10 and 50. Each matrix A is sparse with 100 nonzero elements whose positions are sampled uni- formly and values are sampled normally. Each element in b, c are sampled i.id and uniformly from [-1. 1]. Additionally, each element i scaled by 0.01. The variable bounds u are sampled with W(,, 10). If > Uj, then we swap 1 and uj for all 1 S & n. Furthermore, we sample o; i.i.d ") 0.3. With the generation approach above, the
) 0.7 and P(o, probability that each LP to be feasible is around 0.53.
with P(o;
MLP architectures As we mentions in the main text, all the learnable functions GNN taken MLPs. The imput functions f fin have one hidden layer and other functions fout, four (f fI go .9lh H= have two hidden layers. The embedding size do. dp are uni- formly taken as d that is chosen from {2, 4, 8, 16, 32, 64, 128, 256, 512]. All the activation functions are ReLU.
Training settings We use Adam (Kingma & Ba 2014) as our training optimizer with learning rate of 0.0003. The loss function is taken as mean squared error. All the experiments are conducted on Linux server with an Intel Xcon Platinum 8163 GPU and eight NVIDIA Tesla V100 GPUs.
Extra experiments on generalization We generate the testing set consisting of 1000 LP problems using the same distribution that of the training set. The performance of the trained GNNs on training set and testing set presented in Table 2 and 3 for feasibility, optimal objective value, and optimal solution, respectively. The metric in Table is the rate of classification errors; the metric
i is relative error defined as FF /otil/( Pbjj + 1); the metric in Table 3 defined with
Fw sollu //(]lll(([]] 9/]l] + 1).
Number of Training Samples
100
500
2500
The Error on the training set
0
0
0,067
The Error on the testing set
0.454
0.339
0.175
Table 1: Generalization for feasibility (Num. GNN parameters: 1254)
Number of Training Samples
100
500
2500
The Error on the training set
1.9c-6
0.080
0.128
The Error on the testing set
0.790
0.591
0.173
Table 2: Generalization for optimal objective value (Num. GNN parameters: 1254)
Number of Training Samples
100
500
2500
The Error on the training set
1.1
0.193
0.205
The Error on the testing set
0.550
0.351
0.274
Table 3: Generalization for optimal solution (Num. GNN parameters: 7888)
One can observe that, for a GNN with fixed size, its generalization performance, i.c., the perfor- mance the testing is increasing if trained with more training samples. Given these nu- merical results, we believe that understanding the generalization quantitatively and theoretically deserves future research.
29


Reviews:
[{"review_id": "fHDlSv3xBu", "reviewer": "Reviewer_ubzC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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 studies the ability of GNNs to solve linear programming problems.  It is quite systematic and proves that within a well defined class of GNNs, and given a set of LPs, there exist networks (with specified weights) which can distinguish pairs of LP problems within the set with different feasibility and objective values, and which can approximate the objective value.  The argument is that the Weisfeiler-Lehman test, which it is known that GNNs can perform, suffices for these tasks.  A simple experimental check is made.", "summary_of_the_review": "A very interesting theoretical contribution to study of GNN.", "strength_and_weaknesses": "Strengths: what looks like a general and solid foundational theorem is clearly presented, with a conceptually simple argument.\n\nWeaknesses: the results do not bound the size of the networks required and do not cover generalization, so are of only theoretical interest.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "Q2vUh70i8U", "reviewer": "Reviewer_AwvS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 studies the problem of learning Linear Program (LP) properties—feasibility, optimal value, and shortest optimal solution—by Graph Neural Networks (GNNs). By extending existing results on GNNs—namely the paper by Xu et al. 2019 which equates the separation power of GNNs with Weisfeiler–Lehman isomorphism test (WL test), and the Generalized Stone-Weierstrass Theorem as in Azizian &\nLelarge 2021—this paper shows that GNNs can separate and represent LP properties.\n", "summary_of_the_review": "This paper could be an interesting, if slightly incremental, contribution to the mathematical theory of GNN or WL tests.", "strength_and_weaknesses": "Strengths:\nThe solution given to the problem is natural in hindsight, and the connection between LP graphs/properties and GNN/WL-test appear to be new. And GNN and LP are both important on their own.\n\nWeaknesses:\nThe task of learning different LP properties (feasibility, optimal value, and shortest optimal solution) by neural networks appears somewhat artificial, because there are much better tools out there (various LP solvers, including those used by this paper in the numerical experiments section) than neural networks for this task, and likely neural networks will never be remotely competitive (both in theory or in practice) for learning LP related properties, where a deep mathematical theory trumps neural networks and vast training data.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "1CfK71sX62a", "reviewer": "Reviewer_XXXE", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Linear programs (LPs) are a special case of constraint satisfaction problems (CSPs).\nThis work claims that GNN's may approximate the properties of LPs: if it is feasible, unbounded and its optimal solution if bounded.\nnamely: feasibility, optimal objective value, and optimal solution.\nThe work shows (in theorems 4.1 and 4.2 ) that the limitations of GNNs are not a problem for demonstrating these properties.\nThe work validates using numerical results (in section 5) that GNNs may approximate the optimal objective value and solution (in theorem 3.4).", "summary_of_the_review": "The presentation of the relationship to previous work on theoretical guarantees of optimality is lacking in the related work section.\nThe contribution is marginally significant and novel compared with previous work.\n", "strength_and_weaknesses": "The work is missing a clear explanation of why the WL test limit is related to the task of representing an LP's optimality.\n\nIt would be interesting to see results and comparisons between the following special cases of CSPs:\n1. Linear programming in which the variables are real, and the factors are linear inequalities.\n2. Integer linear programming in which the variables are integers and the factors are linear inequalities.\n3. Mixed integer programming in which the variables are reals and integers and the factors are linear inequalities.", "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": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%