Towards Explaining the Power of Constant-depth Graph Neural Networks for Structured Linear Programming
Authors: Qian Li
Minghui Ouyang
Tian Ding
Yuyi Wang
Qingjiang Shi
Ruoyu Sun
Venue: ICLR 2025 Poster (2025)
Keywords: Learning to optimize
shallow graph neural network
linear programming
distributed algorithm
average-case analysis
Primary area: learning on graphs and other geometries & topologies
TL;DR: We prove that constant-depth, constant-width GNNs can solve sparse binary LPs, through the lens of distributed computing and average-case analysis.

Abstract: Graph neural networks (GNNs) have recently emerged as powerful tools for solving complex optimization problems, often being employed to approximate solution mappings. Empirical evidence shows that even shallow GNNs (with fewer than ten layers) can achieve strong performance in predicting optimal solutions to linear programming (LP) problems. This finding is somewhat counter-intuitive, as LPs are global optimization problems, while shallow GNNs predict based on local information. Although previous theoretical results suggest that GNNs have the expressive power to solve LPs, they require deep architectures whose depth grows at least polynomially with the problem size, and thus leave the underlying principle of this empirical phenomenon still unclear. In this paper, we examine this phenomenon through the lens of distributed computing and average-case analysis. We establish that the expressive power of GNNs for LPs is closely related to well-studied distributed algorithms for LPs. Specifically, we show that any $d$-round distributed LP algorithm can be simulated by a $d$-depth GNN, and vice versa. In particular, by designing a new distributed LP algorithm and then unrolling it, we prove that constant-depth, constant-width GNNs suffice to solve sparse binary LPs effectively. Here, in contrast with previous analyses focusing on worst-case scenarios, in which we show that GNN depth must increase with problem size by leveraging an impossibility result about distributed LP algorithms, our analysis shifts the focus to the average-case performance, and shows that constant GNN depth then becomes sufficient no matter how large the problem size is. Our theory is validated by numerical results.

Published as a conference paper at ICLR 2025
TOWARDS EXPLAINING THE POWER OF CONSTANT DEPTH GRAPH NEURAL NETWORKS FOR STRUC- TURED LINEAR PROGRAMMING
Qian Li!, Minghui Ouyang?, Tian Ding'. Yuyi Wang", Qingjiang Shi and Ruoyu Sun
Shenzhen International Center for Industrial and Applied Mathematics, Shenzhen Research
Institute Big Data. ligian. ict aect@gmaall.... com, di iingtiansrrbbe cn Pekkngg University. ouyangmi nghui 9980gma com
CCRC Zhuzhou Institute Tengen Intelligence Institute. yuyiwagg920 *Tongji University. shiqi@tongji edu..
com
School of Data Science, The Chinese University of Hong Kong, Shenzhen. sunruoyul cuhk edu.
ABSTRACT
Graph neural networks (GNNs) have recently emerged as powerful tools for solv- ing complex optimization problems, often being employed to approximate solu- tion mappings. Empirical evidence shows that even shallow GNNs (with fewer than ten layers) can achieve strong performance in predicting optimal solutions linear programming (LP) problems. This finding is somewhat counter-intuitive, as LPs are global optimization problems, while shallow GNNs predict based lo- cal information. Although previous theoretical results suggest that GNNs have the expressive power to solve LPs, they require deep architectures whose depth grows at least polynomially with the problem size, and thus leave the underlying prin- ciple of this empirical phenomenon still unclear. this paper, we examine this phenomenon through the lens of distributed computing and average-cast analysis. We establish that the expressive power GNNs for I.Ps is closely related to well- studied distributed algorithms for LPs. Specifically, we show that any d-round distributed LP algorithm can be simulated by a d-depth GNN, and vice versa. In particular, by designing new distributed LP algorithm and then unrolling it, we prove that constant-depth, constant- width GNNs suffice to solve sparse binary LPs effectively. Here, in contrast with previous analyses focusing worst case scenarios, in which we show that GNN depth must increase with problem size by leveraging impossibility result about distributed IP algorithms, shifts the focus to the average-case performance, and shows that constant GNN depth then becomes sufficient no matter how large the problem size is. Our theory is validated by numerical results.
analysis
INTRODUCTION
Learning to Optimize (L20) has recently gained considerable attention promising framework that leverages machine learning techniques discover efficient optimization strategies. Compared to traditional rule-based methods, 1.20 methods adaptively learn optimization strategies tailored to specific problem classes, offering greater flexibility and efficiency. The 1.20 framework has shown its potential in handling both continuous optimization (Monga et al., 2222)) and combinatorial opti- mization (Bengio et al. [202] Mazyavkina et al. 2021). and opens up new possibilities for automat- ing and improving the efficiency of various real-world applications.
Graph Neural Networks (GNNs) have emerged as a powerful tool within the L20 framework (Cap- part al. 2023 Peng al. 2021). GNNs dedicated to capturing dependencies and relational structures among variables, thus well-suited for representing and solving optimization problems with graph-structured data, e.g., cut (Schuetz al. 2022). traveling salesman problem (Hud-

---

Published as a conference paper at ICLR 2025
son et al. 2021), and minimum vertex covering (Sato et al. 2019), where the relationships between variables are key to finding efficient solutions.
In particular, there is line of research (Li et al. 2022
Chen ct al. 2023 Kuang al. 2023 Fan
ct al. 2023 Liu et al. 2024; Qian et al. 2024;1 Li ct al.
2024a) exploring the power of GNNs to ac-
celerate the solving process of linear programming (LP). These studies are based the observation that a general LP instance max(c" x A. < b, x 2 0} can be naturally represented as a labeled bipartite graph. Specifically, variable æ corresponds a left node u; labeled with cj. a constraint A.,: @ S. b; (or a dual variable y;) corresponds to a right node v; labeled with b; and a left node új and a right node F; are connected by an edge labeled with Ay A. * O. Empirical results show that even very shallow (with fewer than ten layers) GNNs often perform well in predicting optimal solutions to LPs.. Remarkably, [i et al. (202a)) demonstrated that by employing 4-layer GNN as a warm-start, the PDLP solver can achieve a 3x speedup on the PageRank problem with millions of nodes compared the vanilla version.
We note that this empirical phenomenon is somewhat counter-intuitivy In a shallow GNN, no matter how wide is, each node has to base its output on local information from its d-hop neighborhood (d denotes the number of layers of GNN, a.k.a. the depth of GNN), making the GNN inherently limited in capturing long-range dependencies. In contrast, LP is a global optimization problem, where the optimal value of one variable usually depends the global information and long-range dependen- cies between variables often exist (see (Trevisan & Xhafa, 1998) for an example). Thus besides the potential guidance to L,20 practitioners, also has its own theoretical interest understand the principles behind the empirical phenomenon.
Previous theoretical works (Chen et al. 2023 Qian al. 2024 Li et al. 2024a) have proven that anonymous GNNs possess enough expressive power to solve LPs. Here, we say GNN anonymous the nodes are not equipped with (unique) identifiers. In particular, Li al. (2024a) showed that the popular Primal-Dune Hybrid Gradient (PDHG) algorithm can be naturally aligned with GNNs, where the right node v the bipartite graph represents a dual variable instead of a constraint. This alignment explains why GNNs are often used as the basic network architecture in L.20 from a primal-dual perspective. Unfortunately, all these theoretical results require deep GNNs whose depth grows at least polynomially with the instance size. The reason behind the empirical success of shallow GNNs for LPs remains poorly understood.
1.1 OUR CONTRIBUTIONS
In this paper, we examine this phenomenon through the lens of distributed computing and average- case analysis; and prove that constant-depth, constant-width GNNs suffice to solve sparse binary LPs (Theorem 3), where the depth and the width of GNN remain the same as the problem size grows.
Sparse Binary LPs. An instance of binary LP has all the entries of the constraint matrix A as binary, and b and both as all-ones vectors. A binary LP instance, therefore, takes the following form:
max
(Primal binary LP)
min
(Dual binary LP)
m
s.t.
Ayaz S 1, Vi [m]
s.t.
Σ
Auyy
2
11,j [n]
x 2 0
2
where each A. E 1). Here, A has dimensions m X and we use [n] to denote (1,2.... n.. An LP instance is called spurse has at most O(m - n) non-zero entries. This paper particularly focuses on LP instances where = @(n). We note that such sparse binary LPs can model the fractional versions of many basic combinatorial optimization problems, such as minimum vertex cover, maximum matching, and minimum dominating set sparse graphs.
Our Ideas. Our result builds the following two observations.
2

---

Published as a conference paper at ICLR 2025
Observation 1: The of GNNs for LPs is closely related to the well-studied distributed algo- rithms for LPs. Specifically, we find that any d-round distributed LP algorithm can be simulated by d-depth GNN, and vice versa.
Observation 2: In the aforementioned empirical phenomenon, the performance of GNNs is mea- sured based on the average instance rather than the worst instance. In other words, GNNs are required to work for "most" instances (i.e., they are allowed to fail in a few exceptional cases), rather than for every possible instance.
Remark 1. We note that Observation 2 is general in L20 scenarios, for the following reasons: (i) most L2O methods target NP-hard problems, such as mixed integer linear programs or traveling salesman problems, where it is unrealistic to expect the L2O method works for every possible in- stance; (ii) the general objection of L20 methods is solve instances that arise "in practice", ", where the worst instance may never be encountered, and people are usually satisfied if 1.20 methods work for "many" or "most" instances.
Remark 2. This paper will consider a chain of reduction in generality: from general LPs to pack- ing/covering LPs (a..a. non-negative L.P), then to sparse binary LPs, and finally to row-sparse column-span sparse binary LPs. While the focus is primarily on structured LPs, the two observations mentioned above are applicable to general LPs as well.
A central topic distributed computing is to determine what global goals can or cannot be achieved based on local information. Based on Observation 1, we can leverage the known principles of distributed LP algorithms to study the power of GNNs. First, by unrolling a distributed LP algorithm proposed by [i et al. 2024b), show that there exists constant-depth, constant- constant-width GNN that can approximately solve row-sparse, column-sparse binary LPs (Theorem[) 2 A row-sparse, column- sparse binary I.P is special kind of sparse binary LP where the number non-zero entries in each row and each column of A is upper bounded by a constant. Moreover, by leveraging an impossibility result about distributed LP algorithms (Kuhn et al. 2016), we conclude that there exist no constant- depth GNNs that can solve every possible instance of sparse binary LP (Lemma [ However, if we shift the focus to the average-case performance. by designing and unrolling new distributed algorithm, we prove that constant GNN depth then becomes sufficient for almost all instances of sparse binary LP (Theorem 3), which the main technical part of this paper. Finally, we conduct experiments that directly validate the theoretical result.
DISTRIBUTED LP ALGORIHTM AND THEIR CONNECTIONS WITH GNNS
In this section, we first briefly review known results about distributed LP algorithms, where we will provide the description of distributed algorithm that will be used. Then we demonstrate the connections with GNNs.
2.1 DISTRIBUTED ALGORITHMS FOR L.SS
The Distributed Computational Model. In the distributed computational model, there is net- work G = E)) where (i) each node represents processor and (ii) each edge (u, e) represents bidirectional communication channel connecting processors and v. The computation proceeds in rounds. In one round, each processor first executes local computations and then sends messages to its neighbors. Each of the messages is allowed to be arbitrarily long (so we are talking about the so-called LOCAL model). The algorithm complexity is measured in the number of rounds it performs. Note that in a d-round distributed algorithm, each node has to base its output on local information from its dohop neighborhood. A central topic in distributed computing is to determine what global goals can or cannot be achieved based on local information (Peleg 2000).
For LP problems, most of the related works (see e.g. (Kuhn et al. 2006)) considered the following distributed setting. Given an LP instance max c" x
b. 20,
The network is bound to a bipartite graph G = (U, V, E): each primal variable zy is associated with left node uy; each dual variable y, is associated with right node iù and edge (u,, vx) exists if and only if Ar > O. Note that this bipartite graph is exactly the one used by GNNs to encode I.ss. Besides, we will use N₂ to denote the set of neighbors of ut-
3

---

Published as a conference paper at ICLR 2025
At the beginning of an algorithm, each left node uy only knows çj and the j-th column A.. A.g. and each right node 2 only knows by and the i-th row A,; (An A2,... At the end of an algorithm, each left node uj is required to output 2, and each right node v; to output a Ds, which together are supposed to form an approximate solution to the primal LP max(c² x A.r < b, x: 2 0} and the dual LP min ( (b"
A 2 y 2 0) respectively. Here, we say a: a (1 + -approxiiatee solution (i) is feasible solution and (ii) the ratio between its objective value and optimum lies in [1/(1 e), +
Distributed Algorithms for LPs. An important class of distributed LP algorithms are based on first-order methods (FOM) (Lul 2024), which only utilize gradient information update their it- erates and thus avoid matrix factorization. The main FOM-based LP algorithms include PDHG Chambolle & Pock (2016), PDLP (Applegate
al., 2021), ABIP (Lin et al. 2021, Deng et al. 2022), ECLIPSE [Basu et al. 2020), and SCS (O' do'oong et al., 2016 O Donoghue, 2021). Ap- plegate al. (2023) showed that the Restarted PDHG can find solution that is e-close to the optimal
solution with O( 2 a log(1/A (1/)) iterations, and matches with the complexity lower bound of span-respecting FOMs. Here, is the Hoffman's 's constant of the KKT system.
There is another line of research (Papadimitriou & Yannakakis 1993;
Bartal et al. 1997 Kuhn &
Wattenhofer 2005 Kuhn et al.
2006
Awerbuch & Khandekar 2009 Floréen al., 2008 2011
Kuhn et al.. 2016 Ahhaad et al.
2018
Li et al. 2024b) studying distributed algorithms for solving LPs. packing LP and its dual covering LP are non-negative A < b, 2 0} and min(b"
packing LPs and the dual covering
LPs of the canonical form: m
A c, y 2 0} where A, and c have only non-negative entries. Packing/covering LPs can be normalized into the
following forms (Awerbuch & Khandekar 2009 Li et al. 2024b):
1"x
(Normalized packing LP)
min V/
1 y
(Normalized covering LP)
s.t.
Aæ 1
s.t.
A y 2 1
x 20 0
y 2 0
where Aij is either 2 o.
Let n and mn denote the number of primal variables and dual variables respectively, i.e., has dimensions n, and let Amax denote maxi,j Aij. Define
r max Aij. and Ta max
Aij.
J=1
Bartal et al. (199)) proposed the first constant-factor approximation algorithm running in polylog(n) m + n) rounds for packing/covering LPs. This algorithm was further im- proved by Kuhn et al. (2006): they developed an (1 + apprrooxiittioon algorithm run- ning in O (log Tp log Ta rounds. In particular, for row-sparse, column-sparse in- stances, their algorithm runs in (log² Amax/E") rounds. Later, Awerbuch & Khandekar (2099) proposed another (1 appprooximttioon algorithm for packing/covering LPs running in O (Log" (m.maa log" (mmAAaa)/ mee) rounds, which has slightly worse bound than Kuhn et al. 2006 but enjoys the features of simplicity and statelessness. Recently, Li et al. (024b) proposed a distributed algorithm (Algorithm D that returns (1 + e)-approximate solution for row-sparse, column-sparse instances in O (Amax log Amax/c2) rounds. We remark that all the aforementioned distributed algorithms are anonymous, where the nodes in the network are not equipped with identi- fiers.
On the lower bound side, Kuhn et al. (016)) proved that: every constant-factor approximation dis- tributed algorithm for the fractional maximum matching problem, a special kind of sparse binary LP, requires at least Ω( (lo(lommm + n log log(m + n)) rounds.
Description of a Distributed Algorithm. The algorithm proposed by Li et al. (2024b), which will be used later, is depicted in Algorithm[] The three parameters a, J, and are defined as
2 and f e In InI and L [log p fl.
1 c. I.
4

---

Published as a conference paper at ICLR 2025
Input: a c)appproximation distributed algorithm for packing/covering LPs Li
Algorithm 1: An (1
et al. 2024b)
n matrix where each Aú either or I. and real number 0; Parameters: a E R20 and L E IN defined as in equation| |
Initialize 2; := 0 and r == for any j E [n]] and y/s = for any E [m]]
for L = 1 to L do
for each right node v in parallel do
if pi 2 nnN Po then Ay 1;
else Ay := 0:
:= + Ay:
send Ay; and p; all of its neighbors;
for each left node ú in parallel do
Jj Ij + +r- Σ, Aij Aui/p; and vy =- A
rf S a-= then r, := 0;
13
send ry to all of its neighbors;
14 Return: x/(f (1 e)) and f as a (1 + appprooxeea solution to the normalized packing LP and the normalized covering I.P respectively.
where è is sufficiently large constant, say = 1000. Each left node u, maintains two variables Iy and ry. and each right node v, maintains variable yı- Every 2y and y initially 0 and the value can only increase throughout the algorithm; every rj is initially 1 and the value can only decrease, Besides, each right node v; also maintains variable P: := E, Arjz Recall that the set of neighbors of u, denoted by N,.
Theorem 1 (Li et al. (2024b)). Given any c O, Algorithm computes (1 + appproxxieate solutions to the normalized packing LP and the normalized covering LP the same time, running in < 10 Pa log p//²² rounds. Particularly, for row-sparse, column-spare binary LP instances,
Algorithm 7 runs constant rounds.
For the intuition behind Algorithm[ the analysis, we refer interested readers to (Li et al. 2024b
2.2 CONNECTION WITH GRAPH NEURON NETWORKS FOR LPs
The connection builds on the observation that distributed LP algorithms and GNNs employ the same bipartite graph represent an LP instance. On one hand, it is obvious that d-depth GNN can be computed by d-round distributed algorithm; so by the lower bound obtained by Kuhn et al. (0166), have the following lemma:
Lemma 1. There exists no olylog(m + n)/ log log(m + n)) GNN that output constant-factor approximate solution for every sparse binary LP instance.
On the other hand, by utilizing the universal approximation property of MLPs, any d-round (anony- mous) distributed LP algorithm can be simulated by a d-depth (anonymous) GNN. In particular, by unrolling Algorithm[] [ have the following theorem. The proof can be found in the appendix.
Theorem 2. Given any > O, there exists a constant-depth, constant-width GNN such that: for any row-sp column-sparse binary LP instance, it outputs + (e+++)-upp -)-pprooximate solutions the primal LP and the dual LP at the same time.
3 MAIN RESULT
By Lemma 1 is impossible that a constant-depth GNN can approximately solve sparse binary LPs in the worst case. Despite this, if we care about the average-case performance, then such GNN exists:
Theorem 3. Given any 0 and n < there exists constant-depth. constant-widh GNN such that: for (1 - πι) fraction of all possible sparse binary LP instances, it outputs a (1 c)- approximate solution the primal L.P and the dual L. the time.
5

---

Published as a conference paper at ICLR 2025
Remark 3. To be more specific, in Theorem 3 the GNN depth is upper bounded by 10y/ log("ra;3)ee where a = m/n. 3 = nnz(A) m m. and 7 is defined as in equation For exam- ple, if the GNN is required output 2-approximate solution for 99% fraction of LP instances where m = n and nnz(A) = 20m, then the upper bound is 54079.
While the theoretical constants may be large, we will empirically demonstrate that 5-layer GNN designed by unrolling Algorithm Searrtthmcann can solve sparse binary LPs.. See Section D for details.
In the rest of this section, will prove Theorem 3 algorithm that works for almost all sparse binary LPs, and can be naturally converted to a constant- depth, wontt GNN.
We will propose constant-round distributed
3.1 NOTATIONS AND PROPERTIES ABOUT AVERAGE INSTANCES
Recall that the constraint matrix A has dimensions m X n. Let a denote the ratio m/n. Since we have assumed m (n)), a bounded away from 0 and also upper bounded by a constant. Let Am.n.s denote the set consisting of all binary matrix A E {0, 1)mxn having exactly 3 m non-zero entries. For A Am, each row contains 3 non-zero entries average, and we say a row 7-denee if it contains at least 7/3 non-zero entries; similarly, each column contains 033 non-zero entries in average, and we say a column y-dense if it contains at least ya. non-zero entries. Let R., C [m] (and C. [n] respectively) denote the set of y-dense rows (and columns respectively). Let Cint := Ui 3i R, s.t. Aij # 0} C [n] denote the set consisting of all columns which intersect with some 7-dense row. We define (pl(AA A) to be the optimal objective value of the binary LP instance with constraint matrix A, i.e.
opt () == max E E
min Σ yi AT. y 2 221,92 1 0
{
The following property about an "average" A will used,
Lemma 2. Let 7 2 8. For at least fraction of A in Amn. have |Ra, <
6m
1- 213
|C,,
5
6n 1-2 2jm and |ciul|
6a(13+10 ljm
In particular, by setting 7 a sufficiently large constant,
7-2 210
say
48a/3
1
48,
7 2 log²
log²
3
n7c
ag
ncc
we have |Rab
en and |C 8n
+ +Ca1 S
a for at least
17 fraction of A in Am.n.
Proof. Let A denote uniformly sampled matrix from Amnra random. We use Z to denote the event that the i-th row of A contains exactly ls 1-entries. For any E [m] and 2 83, we have
Pr[Za + // |r A
nt
3m (k + 1))
(m 1)m2
n
(m - 1)m)
=
k: + 1
k
Bm k
n k.
Bm k
71 43
3
h: + 1
(m - 1) 1)n - 3m + 1: +
8, +1
B
n - 43
1
< 8 n/2 3
<
2'
which implies that
Priza k 2 2 (k-29) Pr|Z2ol < 2-
(3)
Furthermore, we have
Pr i-th row is y-dense]
Σ
Pr|Za] < Σ
2 (k6-2))) 2- 20-
Rmyg
k k=7B 78
Then, by linearity of expectation,
EA R = Σ Pr i-th row is y-densel < 22- m.
A

---

Published as a conference paper at ICLR 2025
Algorithm 2: A distributed algorithm that works for almost all instances of sparse binary LP
Input: A matrix A E {0, 1 j with 3m 1-entries, and two real numbers > 0,0 < 1) < 1;
Parameters: 7 defined in equation 2
for each right node in parallel do
A, y-dense then
vl :;
send "sleep" all of neighbors; set itself to the sleep mode;
for each left node uj in parallel do
recieves "sleep", or A..j is "y-desse then
send ("sleep"..1 , E; Aij) to all of its neighbors;
11
set itself to the sleep mode;
12 Run Algorithm with parameter c/4 on the awake nodes, and obtain a' and g':
for each left node uj in parallel do
14
if uy is in sleep mode then return R; = O;
15
else return 3;- 4/i
16 for each right node in parallel do
17
return Uú- = 8 + Esleep jeN, Ee Avz
By applying Markov's inequality,
3
Pr A
R2
2 2 27- 17
m
- 3
(4)
Similarly, we can also show that
Pr
C.
2 (77--2)0841
3
11
(5)
3
In the rest of the proof, will show that
Pr
3 77
(13++)-2-07) 27-2))) 2)8+1
S
(6)
3
which, together with equation 4 and equation imply the conclusion by the union bound.
Note that |Cint| is upper bounded by the total number 1-entries in 7-dense rows. So by linearity of expectation, we have
E8
cintt
<E [# l-entries contained in the y-dense rows]
E
(1i-th row is y-dense) (# (#11cmm 1-entries contained in i-th row)
to0 2 (k-28)
Pr[Zi]
k
6m
k=
=m + 2 27-2)8
By applying Markov's inequality, we obtain equation 6
3.2 CONSTRUCTION OF THE CONSTANT-DEPTH, CONSTANT-WIDIH GNN
In the following, will y in equation 2 which is constant. To prove Theorem 3 will propose a constant-rowe round distributed algorithm that works for almost all sparse binary LP instances. Then, will see, it be naturally converted to constant-depth, constant-width GNN. The

---

Published as a conference paper at ICLR 2025
distributed algorithm builds on Algorithm 1 The idea is depieted follows: given A Am.n.3, we first obtain a reduced matrix A' from A by deleting all rows in R and all columns in C, U. Note that A' is row-sparse, column-sparse binary matrix. Then we run Algorithm the reduced LP instance with constraint matrix A', where the reduced primal LP is
| with e/4 on
max
24 A' < 1. 0
A'x
uc
and the reduced dual LP is
min
Σ
A y 2 1,
dE[mJ).R R.,
to obtain (1 + apprrxxmaee solutions #' E RR and D' E Rlm]yR, of the reduced
instance. Finally,
Let & E IR" obtained from ø' by setting each zÿ in C. U Cutt to O. Return as an (1 + +)-- approximate solution to the original primal LP.
Let D be obtained from ğ' by first setting each in R2 to 1, and then adding the vector Ejec, A. A.j. Return ý as an (1 (1+ -pppprommmmatte solution to the original dual LP.
The formal description of the distributed algorithm is presented in Algorithm 2 It is easy to that this algorithm runs in constant rounds and can be naturally converted to constant-depth, constant- width GNN. What remains is to show the correctness.
3.3 CORRECTNESS
By Lemma
2 it suffices to show that for every A E Am,n. where [R,1,1C,1 S en 87, and |Cint +
[c,l S n/2,& d and ÿ returned by Algorithm 2 are + -)appooxiim solutions to the original primal LP max Ax 1, 2 0} and the dual LP min A 1, 0} respectively. We first present some helpful observations.
Claim 1. opt(A)
en I opt(A) - R - 1C,| & opt(A') S opt(A).
47,
Proof. We first show that opt( ppt(A')= < opt(A) Suppose that x' E R Ri,,(", is an optimal solution to the reduced primal I.P. Let a: E [R(n] be obtained from x²" by setting each vy in C, C, O. It is easy to check that æ feasible solution to the original primal L.P. So
(A' Σ
Σ x S opt(A).
x
Now, we show that (At(A) < opt(A') + |Ryl + +,,,l. Suppose that y E R[m]{R, an optimal solution to the reduced dual LP. Let y be obtained from y" by (i) first setting each yi in R. to 1, and (ii) then adding Σjec, Σ, A. A.j. We claim that y is feasible solution to the original dual LP. i.e., AJv >iT AijMi 2 1 for any j E [n]. The feasibility can be checked case by case:
If [m] (C,, U Cint), then have AJ y ATT v" 21. 1.
If E C.,, then A 2 Af Σ, A.j 1.
i Crint, then there a R., such that Ai 1. Note that yi 2 for any i Ry. We have A, y 2 Aij yi 2 1.
Finally, since is feasible solution to the original dual LP, it has
(A) = Σv5 y1 S Σ 1 R + Σ Σ
Ars opt(AA) R2, + +,C.l.
Ar
jEC,
8

---

Published as a conference paper at ICLR 2025
Claim 2. opt(A') 2 24/8"
Proof. Note that A' contains no y-dense rows, i.e., each row of A' contains no more than 7/8 1- entries. Thus 533 7B. ... 73 a feasible solution to the reduced primal LP, and the objective (n - |Camt CCl z
value 1 73
a 2n5
provides a lower bound on opt(A').
In the following, we show that is (1 + aaapppooximate solution the original primal LP. The feasibility is obvious, and the optimality can be verified as follows:
(1+ Σ 2j e1 jE(m)
Σ
1+e
opt(A')
1 e/4
JE(N|RR
2(1
c
opt AA) (At
2 oAt(
2 (Ap
en
2 (A')
e
(Claim
4
(A)t(A)
en
6
(Claim 2
4
2 2
(A).
What remains is to show that y is a (1 + -)-approximate solution to the original dual I.P. The feasibility can be checked similarly as in the proof of Claim The optimality can be verified as follows:
Ed, S
Σ 8/ + 1
+Σ JEC.
1 A,
Ag =E Ryy +111
< 1 opt(AA'+ en
4yB
< (1 + 9)
4)
-opt(A) + opt (1)
(Claim 2
1 3f
opt((A
(Claim
Now, we finish the proof the correctness.
NUMERICAL EXPERIMENTS
We conduct numerical experiments to validate our main theoretical results, namely Theorem 3 By unrolling Algorithm 2 we propose GNN architecture, depicted Appendix B We make our code publicly available at ht / wwt.uu..om//eeeee http:///eessssstttttttttttttteee
Experimental Setup. To validate the performance of our method across different sizes Normal- ized packing LP problems and ensure consistency with theoretical results, we randomly generated LP problems of varying sizes using Ortools. Specifically, the LP instances generated were of the form M = N, with each instance containing 10 (M + N) non-zero entries. Four different problem sizes were considered: 100, 500, 1,000, and 1,500. After generation, we employed Ortools solve these problems, collecting both the primal and dual solutions for training and testing.
For each problem size, we used 100 independent, randomly generated training samples and 100 independent, randomly generated testing samples. Our model was implemented using the PyTorch framework, and the training process was conducted on GPUs. The Adam optimizer was used with learning rate of 1e-3 and a batch size of 1. Fixed parameters included L = 5, and K 16, along with a learnable parameter f initialized to 1. In the comparison experiments, we use GCNs with the same L-llayer cut each with 64-dimensional feature dimensions.

---

Published as a conference paper at ICLR 2025
Evaluation Metrics. To assess the representational power of method, report the training loss after the model has converged. Additionally, we evaluate the relative gap. Using feasibility restoration (see Appendix C) the final values zfinal and féinal returned by our GNN are used to compute x' and y' The relative gaps are then calculated as follows: the relative gap of the primal is denoted R. abj(z')-op) and the relative gap of the dual is denoted R.D obi()"))opi ope
opt In order to explore the difference in the representational power of the two methods, we report the converged training loss, which is the training loss in the table. The lower the RP and RD the better the performance.
Experimental Results. The results of the numerical experiments directly illustrate the effective- ness of our method. Table [ demonstrates that our GNN achieves much better performance while using significantly fewer parameters, where our model uses at most 2K parameters, which is almost 0.8% of the number of parameters in GCN (=250K).
Table I: Performance comparison of our method with GCN for training loss, Training RP, Training RD, Test RP, and Test RD.
LP size
Training Loss
Training RP
Training RD
Test RP
Test RD
GCN
Ours
GCN
Ours
GCN
Ours
GCN
Ours
GCN
Ours
100
0.0087
0.0086
1.0
0.20
18.64
0.43
1.0
0.20
18.62
0.45
500
0.0086
0.0084
0.96
0.20
18.37
0.48
0.94
0.20
18.35
0.47
1000
0.0079
0.0085
1.0
0.20
18.33
0.47
1.0
0.20
18.35
0.46
1500
0.0083
0.0085
1.0
0.20
18.33
0.45
1.0
0.20
18.38
0.46
We also conduct small-scale numerical experiments to illustrate that method TRAINING LOSS can converge to O. In the experiments, the size of the LP problem is 1000 and the training samples 10. We report the relationship (see Fig. [ of converged training loss with the number of layers L. Even for very small L, the training loss for convergence can already be close to 0.
0.000
trernng kos
0.025
0.000
0.05
0D10
Figure 1: Convergence trends due changes in the number of layers during training.
5 CONCLUSION
Towardd understanding the empirical success achieved by shallow GNNs for solving LPs, we prove that constant-depth, constant-width GNNs suffice to solve sparse binary LPs effectively, by leverag- ing the principles of distributed LP algorithms. Besides, our analysis shifts the focus from worst-case performance to average-cast performance, as empirical studies usually measure GNNs based on av- erage performance across instances. We believe ideas can help in further explorations of the power of GNNs in L20. For future directions, it is interesting to investigate whether our result can be extended to general I.P classes, such non-negative I.Ps.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors would like to thank Qingyu Han for conducting the numerical experiments.
This paper supported by the National Key Research and Development Project under grant 2022YFA 1003900; Hetao Shenzhen-Hong Kong Science and Technology Innovation Cooperation W77QSWS-KCCYB-2222
Zone Project
University Development Fund UDF01001491, the Chinese University of Hong Kong, Shenzhen; Guangdong Provincial Key Laboratory of Mathemat- ical Foundations for Artificial Intelligence (2023B12120 122000000000 the Guangdong Major Project of Basic and Applied Basic Research (2023B0303000001) Qian Li and Minghui Ouyang's work was additionally supported by the National Natural Science Foundation of China Grants No.62002229.
Tian Ding's s work was additionally supported by the Internal Project of Shenzhen Research Insti- tute of Big Data under Grant J00220240005. Yuyi Wang's work was additionally supported by the Natural Science Foundation of Hunan Province, China (Grant No. N0.2024115128).
REFERENCES
Mohamad Ahmadi. Fabian Kuhn, and Rotem Oshman. Distributed approximate maximum match- ing the CONGEST model. In Ulrich Schmid and Josef Widder (eds.), 32nd International Sym- posium on Distributed Computing. DISC 2018, New Orleans, LA, USA, October 15-19, 2018, volume 121 of LIPIcs, pp. 6:1-6:17. Schloss Dagstuhl Seiibiiz-Zentum für Informatik, 2018.
David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O'Donoghue, and Warren Schudy. Practical large-scale linear programming using primal-dual hybrid gradient. Ad- vances Neural Information Processing Systems, 14:20243-20033 2021.
David Applegate, Oliver Hinder, Haihao Lu, and Miles Lubin. Faster first-order primal-dual methods for linear programming using restarts and sharpness. Mathematical Programming, 201(1): 184. 2023.
Baruch Awerbuch and Rohit Khandekar. Stateless distributed gradient descent for positive linear programs. SIAM J. Comput., 38(6):2468-2444 2282666666686,, 2009.
Yair Bartal, John W. Byers, and Danny Raz. Global optimization using local information with applications to flow control. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997, pp. 303-312. IEEE Computer Society, 1997.
Kinjal Basu, Amol Ghoting, Rahul Mazumder, and Yao Pan. Eclipse: An extreme-scale linear program solver for web-applications. In International Conference on Machine Learning, pp- 704-714. PMLR, 2020.
Yoshua Bengio. Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: methodological tour d d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Velickovic. Combinatorial optimization and reasoning with graph neural networks. J. Mach. Learn. Res., 11:10011,,, 2023.
Antonin Chambolle and Thomas Pock. On the ergodic convergence rates of a first-order primal-dual algorithm. Mathematical Programming, 159(1)253-2887, 2016.
Ziang Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. On representing linear programs graph neural networks. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net 2023.
Qi Deng, Qing Feng, Wenzhi Gao, Dongdong Ge, Bo Jiang, Yuntian Jiang, Jingsong Liu, Tianhao Liu, Chenyu Xue, Yinyu Ye, et al. New developments of admm- based interior point methods for linear programming and conic programming. arXiv preprint arXiv:2209.01793 2022.
11

---

Published as a conference paper at ICLR 2025
Zhenan Fan, Xinglu Wang. Oleksandr Yakovenko, Abdullah Ali Sivas, Owen Ren, Yong Zhang, and Zirui Zhou. Smart initial basis selection for linear programs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Conference on Machine Learning, ICMI.2023. 23-29 July 2023, Honoluuu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 1650-96664 PMLR, 2023.
Patrik Floréen, Marja Hassinen, Petteri Kaski, and Jukka Suomela. Tight local approximation results for max-min linear programs. In Sándor P. Fekete (ed.), Algorithmic Aspects of Wireless Sen- sor Networks, Fourth International Workshop, ALGOSENSORS 2008, Reykjavik, Iceland, July 2008. Revised Selected Papers, volume 5389 of Lecture Notes in Computer Science, pp. 2-17. Springer, 2008, doi: 10. 00.1007/978-3-54--228666 1, URL 978 3 540 92862 2
Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, and Jukka Suomela. Local approximability of max-min and min-max linear programs. Theory Comput. Syst. 49(4); 672-697, 2011. doi: 10.1077/000224-009900--- URL cattps://aci.org/1/
s00224 010- 9303-6 6
Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. In International Conference on Learn- ing Representations, 2021.
Yufei Kuang. Xijun Li, Jie Wang, Fangzhou Zhu, Meng Lu, Zhihai Wang, Jia Zeng, Houqiang Li, Yongdong Zhang, and Feng Wu. Accelerate presolve large-scale linear programming via reinforcement learning. CoRR, abs/2310.1 1145, 2023.
Fabian Kuhn and Roger Wattenhofer. Constant-time distributed dominating set approximation. Distributed Comput.. 17(4):303-310, 2005, doi: 10. 10.1007/500446-000011133 URL https: 7/doi. //doi.org/10: 100700000440000000000000
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. The price of being near-sighted. In
Proceedings of the Seventeenth Anmual ACM-SIAM Symposium Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pp. 980-989. ACM Press, 2006.
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. J. ACM, 63(2)11:1-11::44, 2016.
Bingheng Li, Linxin Yang. Yupeng Chen, Senmiao Wang, Haitao Mao, Qian Chen, Yao Ma, Akang Wang, Tian Ding, Jiliang Tang, and Ruoyu Sun. Pdlg--unollee learning-to-optmiize method for large-scale linear programming. In Forty-first International Conference on Ma- chine Leurning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024a. URL net/ http:/oommmm-d2x22-eeee
atttps://openzevaae
Qian Li, Minghui Ouyang, and Yuyi Wang. A simple distributed algorithm for sparse fractional covering and packing problems. arXiv preprint arXiv:2409. 16168, 2024b.
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.062/6 2022.
Tianyi Lin, Shiqian Ma, Yinyu Ye, and Shuzhong Zhang. An admm-based interior-poin method for large-scale linear programming. Optimization Methods and Software, (6(2-3):8994244 2021.
Tianhao Liu, Shanwen Pu, Dongdong Ge, and Yinyu Ye. Learning to pivot as a smart expert. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan (eds.), Thirtt-Fighth AAAI Con- ference on Artificial Intelligence, AAAÍ 2024. Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances Artifi- cial Intelligence, EAAI 2014, February 20-27, 2024, Vancouver, Canada, pp. Press, 2024.
AAAI
Haihao Lu. First-order methods for linear programming. arXiv preprint arXiv:2403.14553 2024.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400 2021.
12

---

Published as a conference paper at ICLR 2025
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.
Brendan O' O'Donoghue. Operator splitting for a homogeneous embedding of the linear complemen- tarity problem. SIAM Journal Optimization, 313))1999-2023, 2021.
Brendan O' d'donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applica- tions, 169:1042- 1068, 2016.
Christos H. Papadimitriou and Mihalis Yannakakis. Linear programming without the matrix. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal (eds.), Proceedings of the Twenty-Fifth Anmual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pp- 121-129. ACM, 1993.
David Peleg. Distributed computing: a locality-sensitivv approach. SIAM, 2000.
Yun Peng, Byron Choi, and Jianliang Xu. Graph learning for combinatorial optimization: a survey of state-of-the-art. Data Science and Engineering, 6(2):119-14, 2021.
Chendi Qian, Didier Chételat, and Christopher Morris. Exploring the power of graph neural net- works in solving linear optimization problems. In International Conference on Artificial Intelii gence and Statistics, pp.
PMLR, 2024.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. Advances in Neural Information Processing Systems, 32, 2019.
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.
Luca Trevisan and Fatos Xhafa. The parallel complexity of positive linear programming. Parallel Process. Lett 8(4)5577-333, 1998. doi: 10. 00.1142/501122264980000 1, URL htttpa:/ddo
13

---

Published as a conference paper at ICLR 2025
A PROOF OF THEOREM 2
We will explicitly describe such GNN. The idea is to simulate Algorithm on binary LP instances. Given matrix M IRmx* and a vector p R", we define the mmxx-roduuct" q M Xmax p to be the m-dimensional column vector such that qi max Myjpj
We design GNN as follows: each left node in the bipartite graph maintains a 4-dimension feature vector (z J, by. Pj), and each right node also maintains 4-dimension feature vector (y:, Ma,i Pis Pmax.i). Here.
ry represents loga Fý + f. In other words, = a's-1.
by is defined to be ry (or equivalently a² a²:-f)if > a- and 0 otherwise.
P: represents A, b Σ3 Aszby-
Pj represents Ma Pt, or equivalently A Xmax P.
Pmax,i represents max Py maxjeN; Pj. or equivalently A..: x Xmax P.
Va, represents the increment of y:-
The architecture of the GNN is depicted below.
-Iiitialize .0 := f 1 1x b = nxi: and pa x both to be Onx1-
Initialize all of " 22, pO, p to be 0mx1-
For é = 2,
p r A bt:
rez2 A x max p +1;
P Pmax = A max p² 141 == g - Pittk/aa) and n = y² -3a p+1
AT
V s+1 s+1 == x² +b AT
(vs s+1 o p ] and be+ by bo (1(+1).
Here, denotes entry-wise multiplication (a.k.a. Hadamard product), and the parameterized func- tions ge, R RR are applied entry-wise on the vectors p²+1 Piiak/a and pe+1 respectively. If we set (=) == 1.20 and (z)z) := 1.20 a²-1, then it is straightforward to check that this GNN exactly simulates Algorithm By Theorem L we finish the proof.
B GRAPH NEURAL NETWORK DESIGN BY UNROLLING ALGORITHM 2
Each left node in the bipartite graph maintains a 5-dimension feature vector (I., Pg. by, Pj, mask)) E R3, and each right node also maintains a 5-dimension feature vec- tor (yi, V4.i. Pi. Pmaxx m R Here,
The feature mask indicates whether the node is in the sleep mode. For example, mask." is supposed to be if the left node uy is in sleep mode, and if not.
Recall that right node v; is set be sleep if has 2 73 edges. In the neural network, we will let mask = 90" (A.1, 1xx1), where d0 (z) = Σi= (00.5 s -2 0g.9) a learnable function and applied entry-wise. Here, 0(2) = 1/(1 + exp(-2) is the sigmoid function. Recall that left node uj right node. In the neural network, we will let mask + max max (AT T, 1mx1), AT Xmax mask where 9p Di= (0 + 0x.11) .1) is a learnable function and applied entry-wise.
be sleep if has 2 7a3 edges or connects to a sleep
The intuition behind the other features is the same as in Theorem 2
The architecture of the GNN is depicted below.
Initialize 70
1, 50 1 and 0o 00 0 =mask* 00,x1-
14

---

Published as a conference paper at ICLR 2025
Initialize yd y pd Pinax mask 00mx1
maak = 000 (A 1xx1).
.mask* - max 0 (AT. mxx1), A Xmax mask
For é = 0, 2 ... , 1-11
p (A b²) (1 mask ))
g+z = (AT Xmax p 12+ o (1 mask );
P max = (A X max p= o o mask 7), y f+1
= go(pttt - -Pmax/a) mask and
y ++1 (y² + Us o
mask
pl+1 = (Fl AT y (+1) o (1 mask xet1 = (x + AT ( p )])
(1 - -mask" ), and b = ba ( o mask
return x finall x and y f = yn mask + + (hJ mask"
Here, denotes entry-wise multiplication (a.k.. Hadamard product), the nn-dimensional matrix
A is defined as Aij = Aij/ Ei= Aij. and the parameterized functions g bng R -> IR are applied entry-wise to the vectors p -P / /a and p(+1 respectively where
(b(=) 0h. (0k.2-00022--- 2 ++0x2)) and (²(=) Σ 1 (0k.s 2 02,6) -2 ReLL(((
The learnable parameter is + := {h R", fI U 1e0 The number of parameter is 11LK + n +
One check that the above GNN can exactly simulate Algorithm
Network training. The training data set a set I = {(A,,", yy)} } of binary LP instances. More specifically, the input of instance is identified by the constraint matrix A; the label xx and y rep- resent the corresponding optimal solutions to primal LP and dual LP respectively. Let æ /mol ( A) and y final (O, A) denote the output our GNN parameterized by θ running on the input A. The goal of the training process is to find a parameter O minimizing MSE loss defined as:
((I:
final (O, 3
23
Σ iE[M]
y Linal (O,
y 19. A)
I
N
(A,=*)EZ JEI
JE[N]
C OTHER DETAILED INFORMATION ABOUT THE EXPERIMENTS
Evaluation Configurations. All experiments were performed the same hardware environment. The evaluation machine is equipped with two Intel(R) Xeon(R) Gold 5117 CPUs @ 2.00GHz, 256GB of RAM, and single Nvidia V100 GPU. Ortools version 9.11 and PyTorch version 1.10.2 were utilized in our experiments. The maximum number of training epochs was set to 1,000.
Feasibility restoration for the primal LP. Note that the /inal returned by our GNN may be infeasible. To restore feasibility, we implement the following post-processing procedure:
First, for each j E (n]. update xy = max(0, min(1,
Then, for i = 1 to m do
I A, 1, then update Ty A.m.
Ty for each with Ag 0.
Feasibility restoration for the dual LP. Since the y final returned by our GNN may be infeasible, implement the following post-processing procedure restore feasibility:
- First, for each & [m.) update := m5 min(1,,)))
Then, for j 1 to do
15

---

Published as a conference paper at ICLR 2025
If A3 y 1, then update yi == A 2 for each with Aiy # 0.
16


Reviews:
[{"review_id": "jtp8NQI9HR", "reviewer": "Reviewer_d7xG", "summary": "This paper proposes a connection between GNNs and existing distributed LP algorithms, suggesting that the iterations of distributed LP algorithms correspond to message-passing steps in GNNs. Additionally, the authors use existing results on iteration bounds in distributed LP algorithms to infer bounds on the number of GNN layers.", "questions": "See weakness.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Existing theoretical results on the representational power of GNNs for optimization problems often rely on strong assumptions about problem size, leaving the complexity of GNN size for these problems largely unexplored. This paper advances this area by drawing connections to existing results from LP algorithms for specific types of LPs.", "weaknesses": "1. The title may overstate the contributions by referring to GNNs for \"linear programming,\" as the authors actually draw on results specific to packing and covering LPs. While these capture certain classes of combinatorial optimization problems, they do not encompass general LPs.\n\n2. The connection between GNN message passing and factorization-free LP algorithms is straightforward. GNN message passing involves matrix-vector multiplications, allowing any convergence results from first-order LP algorithms that consist of matrix-vector multiplications to be applied here. The results presented in this paper represent only a subset of these. In this respect, the theoretical contribution of this paper appears limited.\n\n3. The authors emphasize throughout the paper that shallow GNNs are practically effective. However, the specific value of \"constant number of layers\" suggested remains unclear. My understanding is that for the theories to hold, this constant would likely be very large, rendering it impractical. If so, the theory borrowed from existing distributed LP algorithms may not fully explain the practical utility of shallow GNNs.\n\n4. The absence of experimental results, even with toy examples, to validate this proposed number of GNN layers is unusual for a machine learning paper. This raises further questions about the practical applicability of the proposed result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "doo7Y1n8f7", "reviewer": "Reviewer_nCqZ", "summary": "This paper analyzes the depth and width of graph neural networks for linear programs, based on existing results for distributed algorithms.", "questions": "None", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "1. This paper is in general clearly written and is easy to follow.\n\n2. This paper connects GNNs with distributed algorithms for solving LPs.", "weaknesses": "1. I do not see much novelty in the theory. In particular, I feel that this paper is just translating known results for distributed algorithms to GNN language.\n\n2. If you fix $\\epsilon$ and $\\eta$, then Theorem 2 and Theorem 3 are direct corollaries of Chen et al. (2023). The results have to be more quantitative if you want to have something new.\n\n3. There are no numerical experiments.\n\n(Chen et al., 2023) Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin, On representing linear programs by graph neural networks, ICLR 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "v6rlhENx5p", "reviewer": "Reviewer_DnAN", "summary": "This paper investigates the expressive power of GNNs in representing LPs. The gap between theoretical and practical insights in this area is notable: theoretically, there are no tight upper bounds on the required GNN size (in terms of depth or width) for representing LPs, with upper bounds typically depending on the problem size. However, in practice, GNNs with minimal depth are often sufficient. This study aims to bridge this gap. Focusing on a specific class of LPs (sparse binary LP), it connects GNNs with a distributed algorithm. For this type of LP, the distributed algorithm’s iteration achieves constant steps, suggesting that a GNN with constant depth can reach a certain accuracy level.", "questions": "refer to \"weakness\"", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The theoretical exposition is clear and rigorous. In the constant-depth analysis, the authors employ the big-O notation O(xxx) with actual constants rather than constants implicitly tied to the LP size. This precision in presentation is commendable, as many similar papers tend to obscure critical constants within the big-O notation, which can be misleading. This paper avoids that pitfall.\n\n2. The analysis focuses specifically on sparse, binary-coefficient LPs. This approach is sensible, as constructing a constant-size GNN for all LPs would be overly ambitious. Additionally, their analysis highlights the conditions and assumptions required for a constant-size solution—namely, sparsity and boundedness of the maximum values in A. This adds valuable insights for the field.", "weaknesses": "My primary concern with this paper is the applicability of its theoretical findings to practical GNNs. Specifically, if one were to train a GNN to solve packing/covering LPs, would the trained model align with the theoretical framework presented here? Do the theoretical observations in this paper truly correspond with practical outcomes?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TcffKcICu3", "reviewer": "Reviewer_94WT", "summary": "The paper studies the expressive power of constant-depth GNNs for approximatively solving sparse, binary linear programs (LPs), specifically packing/covering LPs. Specifically, the paper embeds a [recent distributed LP algorithm](https://arxiv.org/abs/2409.16168) into a GNN such that $d$ layers amount to running  $d$ rounds of the algorithm. They then show that while the lower bound of [Kuhn 2016](https://dl.acm.org/doi/abs/10.1145/2742012?casa_token=axoJjWtNII0AAAAA:GRCjUb2MDG1nvsEH5FOwiboPhll-JbEfJaN2ObfeanJbgQvDy7WAW1s4UD4Orown_Alaw0RvTMbBifAA) rules out these constant depth GNNs performing well in the worst case on all LPs, the _average_ case can be achieved with a probabilistic bound (which is the meat of the contribution).", "questions": "my main question is: have you implemented an run your LP? i think numerical issues like precision could play an additional role. additionally, are you aware of an explicit counter example? this + a randomized average case numerical evaluation could really round of this paper in my eyes", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- originality: to my knowledge and google scholar skills, the first such proof => original\n- quality+ clarity:  very crisp presentation, while I do not feel 100% solid in my verification, i feel I could at least follow the proof,and it appears correct to me. \n- important result if correct, as it gives _an_ upper bound (it remains to be evaluated how tight) on the depth required for a given LP-heuristic GNN", "weaknesses": "- I think some basic numeric would have rounded off the results and helped readers and practitioners judge the tightness of the bound.\n- additionally, I think the question of learnability with standard algorithms would have been interesting to study in the specific setting studied\n\nboth of these could be addressed with some small scale numerics given the constructive arguments used\n\nadditionally, I think making the chain of reduction in generality from \"generic LP => sparse LP= > sparse binary LP\" + the generality of packing coverage vs other types of LP clearer would additional help non-experts judge the relevance of the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)