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
Primary area: learning on graphs and other geometries & topologies
Keywords: Learning to optimize, shallow graph neural network, linear programming, distributed algorithm, 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.

Decision: accept (poster)
Reviewer scores: 5, 3, 6, 8

Reviews and discussion:
<thread>
creation date:
1730639635526

thread_type:
official_review

<thread_object>
creator: reviewer_94wt

<content>
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).

strengths:
- originality: to my knowledge and google scholar skills, the first such proof => original
- 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. 
- 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.
- additionally, I think the question of learnability with standard algorithms would have been interesting to study in the specific setting studied

both of these could be addressed with some small scale numerics given the constructive arguments used

additionally, 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.

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
</content>
</thread_object>

</thread>
<thread>
creation date:
1730680001915

thread_type:
official_review

<thread_object>
creator: reviewer_dnan

<content>
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.

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.

2. 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?

questions:
refer to "weakness"
</content>
</thread_object>

</thread>
<thread>
creation date:
1730696813999

thread_type:
official_review

<thread_object>
creator: reviewer_ncqz

<content>
summary:
This paper analyzes the depth and width of graph neural networks for linear programs, based on existing results for distributed algorithms.

strengths:
1. This paper is in general clearly written and is easy to follow.

2. 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.

2. 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.

3. There are no numerical experiments.

(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.

questions:
None
</content>
</thread_object>

</thread>
<thread>
creation date:
1730717956632

thread_type:
official_review

<thread_object>
creator: reviewer_d7xg

<content>
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.

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.

2. 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.

3. 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.

4. 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.

questions:
See weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732676068056

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Responses

comment:
We sincerely thank the reviewers for their valuable comments and constructive feedback. We provide detailed responses individually to each reviewer. 



**1. Clarification of Novelty**

More than one reviewers have expressed concerns about the novelty, suggesting that this paper merely translates known results from LP algorithms. Here, we would like to clarify our approach and findings:

- This paper considers a **chain of reduction in generality**: from "general LPs" to "packing/covering LPs" (a.k.a. non-negative LP), then to "sparse binary LPs", and finally to "row-sparse column-sparse binary LPs".
- Both of our key observations--(i) the connection between distributed LP algorithms and GNN-for-LPs and (ii) that the performance of GNNs is measured based on the average-case instance--apply to **general LPs**. For instance, the average-case analysis offers a potential explanation for the impressive empirical success of PDHG-net on PageRank [ICML24].
- For **row-sparse column-sparse binary LPs**, by unrolling a known distributed algorithm, we show that a constant-depth GNN can solve such LPs even in the worst case.
- For **sparse binary LPs**, by leveraging known impossibility results from distributed LP algorithms, we prove that no constant-depth GNN can solve such LPs in the worst case. However, by designing and unrolling a **new distributed LP algorithm** (Algorithm 2), we prove that $\exists$ constant-depth GNN can solve such LPs in the average case. This highlights the necessity of average-case analysis, and is formalized in Theorem 3, which is the main technical part of our work.

- Besides, we've designed a GNN by unrolling Algorithm 2, and conducted numerical experiments to validate Theorem 3. Besides, we've also conducted experiments to compare our GNN with GCN, and the results show that **Our GNN achieves much better performance while using significantly fewer parameters**. Please see **2. Experiments** for details.

*Remark*: In this paper, the round complexity of distributed algorithms and the depth complexity of GNNs are analyzed in terms of the problem size $(m,n)$, and the approximation ratio $\epsilon$. A GNN depth is said to be constant if it does not grow with the problem size $(m,n)$.

[ICML24] Li et al. PDHG-unrolled learning-to-optimize method for large-scale linear programming. ICML 2024.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The manuscript studies the connection of parallel algorithms for linear programming with graphical neural network representation for LP problems, which gives bounds for depth and width of the neural networks based on results from distributed algorithms. Overall, this provides a new angle to analyze GNN representation for linear programs. While the reviewers pointed out some shortcomings of the paper, most of those were addressed during the discussion. Therefore, the metareviewer recommends acceptance of the paper.