Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Linear programs (LPs) are a special case of constraint satisfaction problems (CSPs).
This work claims that GNN's may approximate the properties of LPs: if it is feasible, unbounded and its optimal solution if bounded.
namely: feasibility, optimal objective value, and optimal solution.
The work shows (in theorems 4.1 and 4.2 ) that the limitations of GNNs are not a problem for demonstrating these properties.
The work validates using numerical results (in section 5) that GNNs may approximate the optimal objective value and solution (in theorem 3.4).
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.

It would be interesting to see results and comparisons between the following special cases of CSPs:
1. Linear programming in which the variables are real, and the factors are linear inequalities.
2. Integer linear programming in which the variables are integers and the factors are linear inequalities.
3. Mixed integer programming in which the variables are reals and integers and the factors are linear inequalities.
clarity,_quality,_novelty_and_reproducibility: The exposition is clear.
The paper consists of minor grammar and spelling mistakes.
summary_of_the_review: The presentation of the relationship to previous work on theoretical guarantees of optimality is lacking in the related work section.
The contribution is marginally significant and novel compared with previous work.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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 &
Lelarge 2021—this paper shows that GNNs can separate and represent LP properties.

strength_and_weaknesses: Strengths:
The 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.

Weaknesses:
The 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.
clarity,_quality,_novelty_and_reproducibility: The paper is well written and easy to follow. The examples given, such as the LP-Graph in Figure 1 on page 3 and the LP-Graphs indistinguishable by WL test in Figure 2 on page 8, are very illustrative.

In general, both the big picture and the technical details are explained well, complete with experimental validation.

In terms of novelty, the idea of connecting LP graph or properties with GNN or WL test appears to be new, and mathematically natural in hindsight.

The paper presented sufficient details so the experimental results should be reproducible.
summary_of_the_review: This paper could be an interesting, if slightly incremental, contribution to the mathematical theory of GNN or WL tests.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
strength_and_weaknesses: Strengths: what looks like a general and solid foundational theorem is clearly presented, with a conceptually simple argument.

Weaknesses: the results do not bound the size of the networks required and do not cover generalization, so are of only theoretical interest.
clarity,_quality,_novelty_and_reproducibility: The authors claim that "we established the first complete proof that GNN can universally represent a broad class of LPs".
I am not expert enough to be confident about this, but if so then this looks like a valuable foundational result.
Furthermore the argument based on the WL test is conceptually very simple and relates to much previous work on GNNs.

summary_of_the_review: A very interesting theoretical contribution to study of GNN.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: In recent years there has been an emerging line of work on using graph neural networks (GNNs) to help with solving linear programs. One may wonder about the representational power of how well-suited GNNs to this task, and as the authors nicely summarize in the author response to XXXE, there are a series of questions that one could ask:

"""
(Existence). Do there exist GNNs that can represent key characters of LPs? This question is also named as the representation power of GNNs. If the answer was no, GNNs would confuse an LP instance with another extremely distinct LP instance, and one could not expect GNN as a good tool for LP and even an ambitious goal, MILP. Thus, this is actually a fundamental question.

(Trainability). If such GNNs exist, can we find them? The process of finding such GNNs is also named as training.

(Generalization). Does the trained GNN work well on unseen instances? This is also named as the generalization performance of GNNs.
"""

This paper addresses the first question by bringing together results linking GNN representational power to the Weisfeiler–Lehman (WL) isomorphism test and results linking WL to properties of LPs. The paper is well-scoped and high quality. The main weakness that I see (raised by ubzC) is that "the results do not bound the size of the networks required and do not cover generalization, so are of only theoretical interest." However, this seems appropriate to leave as a challenge for future work.


justification_for_why_not_higher_score: Not clear that the paper has the broad applicability and interest to justify an oral presentation. 
justification_for_why_not_lower_score: Paper is high quality and seems like a foundational result for the area of GNNs for LPs.
Decision: Accept: notable-top-25%