Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper study the representation power of GNN for mixed integer linear programming (MILP) problems. 
strength_and_weaknesses: See my comments below. 
clarity,_quality,_novelty_and_reproducibility: See my comments below. 
summary_of_the_review: This paper studies the representation power of GNN for mixed integer linear programming (MILP) problems.  The problem is important and fundamental. The analysis justifies the advantage of the random feature technique when solving MILP problems. The overall presentation is quite clear.  The proof combines the Stone-Weierstrass theorem (including its generalized version in Azizian and Lelarge’21) with domain knowledge of MILP.  The anaylsis is mostly sound and solid. However, I have the following questions. 

**Major questions:** several important proof steps are shown in a hand-waving style without rigorous derivation. For instance: 

1. Lemma A.8 is a very strong claim. I think it only holds for some specific graphs like bipartite graphs. Please write down the proof rigorously. The same suggestion also applies to the proof of Thm 5.1, page 16, the claim in the sentence "Therefore, similar to Lemma A.8, one can see for any....". Please write down the proof rigorously. 

2. For the proof of Thm 5.1, page 16,  please verify that for any function f in the function class of  GNN, f(G1) = f(G2) if G1 and G2 (which are both equibed with random features) are isomorphic.  Please write down the proof rigorously (if this claim is correct.)

3.  Why is phi_feas continuous?

4. phi_solu( ) is an one-to-many mapping. It is not a function. I don't understand how to approximate this mapping using Lusin' & Stone-Weisterass Theorem, which only apply to measureable & continuous functions. Please explain more. 

A follow-up question related to the above comments 1 and 2:

Regarding the proof of Thm 5.1, page 16, the authors apply Thm A.7 after verifying  "phi_feas(G, H ) =  phi_feas(Ghat, Hhat), for all (G, H,w )~ (Ghat,Hhat,what)". However, I dont think we can apply  Thm A.7 like this because (G,H) and (G, H, w) lie in different spaces.  From my understanding, by applying Thm A.7 correctly, we can only get "random-featured GNN" can approximate "phi_feas defined on random-featured  graphs".  But it seems unclear what is the relation between "phi_feas defined on random-featured  graphs" and "phi_feas defined on original  graphs". Please verify.

To briefly summarize, the proof of Thm 5.1, page 16 is quite dense and hand-waving. **The rigorous proof is missing and I doubt the correctness of the results about random features.  I would like to raise the score if authors address these concerns.**



**Other comments:**
1. The paper steps forwards an important first step to establish the feasibility of learning MILP by GNNs. However, the problem is far from being concluded. For MILP problems, another equally important (if not more important) application of GNN is to learn the algorithmic configuration such as the branching strategy, which is not covered in the script. Please add more relevant discussions.  

2. Correct me if wrong: from my understanding,  the original WL test paint all the nodes in a single graph with the same initial color.  Why do we allow different initial colors (across nodes) in the script? 

2. typo: page 6 lemma 3-2: Consider two MILP provlems ==> problems.

3. I would suggest the authors double-check all the \citep and \citet properly. 

4. When encoding the MILP into a graph, how do you implement "<=, >=" and "\infty" in the node feature of the graph?


+++++++++++++++++++++**POST REBUTTAL** ++++++++++++++++++++++

Many thanks for the detailed reply from the authors. Most of my concern is addressed.  I am also convinced that the script has many differences with  the LP paper  so the ethic concern is also addressed. I briefly summarize the contribution of the script as follows:

1. Negative results on GNN for representing MILP
2. A candidate solution called “random-featured GNN“ is provided.

For me, 1 is not surprising because it is well known that GNN has limited distinguishing power, so it is possible that GNN might fail to capture certain info on MILP graph. However, it is good to see a counter-example to explicitly point out the limitation of GNN for representing MILP.  In summary, although the result is not surprising, I think this part is still worth sharing with the community. 

As for 2, I think the contribution is limited due to the following reasons.

[R1] The analysis requires infinite-width random-featured GNN.  It seems unclear what is the advantage of random-featured GNN over MLP. Since infinite width MLP has universal approximation power, MLP can solve isomorphism problems and also it can represent MILP as well. Then the random-feature strategy seems not that important since you also require infinite width anyways.  

[R2] The practical impact is unclear due to the toy experiments. Further, random-feature technique is not invented by the script, either. 


By balancing the pros and cons, I raise my score to 6.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The paper presents a Graphical Neural Network (GNN) based method for the solution of Mixed-integer linear programming (MILP) optimization problem. The proposed method adds random features to the MILP based GNNs and prove is provided that this will provide a optimal solution for MILP. Details, from a reference,  are provided for the representation of an MILP into a weighted graph. GNN is built to represent the properties of the whole graph. Feasibility, Optimal objective value and Optimal solution mappings are provided along with the invariance and equivariance properties. A lot of theoretical description of mathematics is provided for the GNN based MILP solution. Feasibility through numerical experiments is  described. 

strength_and_weaknesses: Strength:
	1. The proposed technique of addition of random features
	2. Mathematics and details of the MILP representation into GNN
	3. Reapplication of theorem 3.1. for MILP - graphs
	4. Theorems of section 4 & 5
	5. Numerical experiments to validate proposed theories
Weaknesses:
	1. Typos e.g. "Fugure 2" on page 6
	2. It is not clear what is the contribution to the mathematics and theory and what is reapplication of existing work.
	3. Mainly the paper is about graph theory
	4. Although GNN is used in machine learning, the paper does seems to be doing machine learning
	5. No real world MILP scenarios are implemented or solved

clarity,_quality,_novelty_and_reproducibility: Clarity:
	Most of the paper is clearly written but in some descriptions, contribution and reusing of others work is not clear. eg. Do the theorems of section 4 and 5 are contributions or reapplications?
Quality and Novelty:
	This paper is mostly about Graph theory and MILP and these are not in my area of expertise. Therefore, I am not able to judge the quality or the novelty of this paper. In my opinion this paper is not suitable for a machine learning conference. This paper should be submitted to a applied mathematics or graph conference.
Reproducibility: Seems reproducible as theorems proofs and details are provided in the appendix

summary_of_the_review: 	1. The paper seems sound mathematically and theoretically.
	2. Mostly the paper is about MILP and Graphs theory
	3. Other than GNN, no machine learning
	4. More suitable for graph or applied mathematics conference
	5. Not suitable for a machine learning conference
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors try to answer an interesting yet challenging question：
Is GNN a good representation model for MILP and whether it can predict important properties, eg., feasibility, for MILP problems?
They construct a simple example showing that there exist two MILPs such that one of them is feasible while the other one is not, but no GNN can distinguish them.
This example illustrates the limitation of the representability of GNN for MILP problems.  
They further divide MILPs into two classes: foldable and unfoldable and show that GNN has strong enough representation power on unfoldable MILPS. 
Finally, they show that by appending random features, GNN can also have strong enough representation power on foldable MILPS. 

strength_and_weaknesses: Strong points:
1. Studying the representability of GNN for MILPs is a fundamental problem in this area， and this topic fits well with the conference's scope. 
2. The construction of the counterexample is neat, and this example clearly shows the limitation of the representability of GNN for MILP problems.  
3. Proving GNN has strong enough representation power by appending random features provides some theoretical explanations for this widely known trick. 


Weak points:
1. Since the definition of foldable MILP depends on Algorithm 1, which is used to measure the separation power of GNN, the resulting theorems (Thm 4.2 ~ Thm 4.4) seem to be straightforward.
2. For the experiments, reporting training loss is not very meaningful from a practitioner's point of view. As you claim that adding random features is a good practical solution, can you also report the corresponding test loss?
3. Although the three questions raised in the paper are important, they are not quite practical. It will be better if the authors can link the results of this paper to answer whether GNN is able to predict the branching strategy which has been empirically studied recently. 
clarity,_quality,_novelty_and_reproducibility: This is a well-organized paper and easy to follow.
summary_of_the_review: Overall, this is a good paper that tries to answer important questions on the topic of "learning to optimize".
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Authors identify cases which a particular method of graph representations of mixed integer linear programming (MILP) problems shall not distinguish feasible problems from infeasible problems using Weisfeiler-Lehman (WL) test. Authors characterize a subset of indistinguishable MILP problems as "foldable", which means there are nodes with the same color from WL test. As a treatment, authors suggest to add a random features to make all nodes distinguishable. Synthetic data experiments demonstrate that random features do provide representation power to separate feasible MILPs from infeasible ones.
strength_and_weaknesses: While GNNs have become a popular method of encoding MILP problems, there has been lack of clarity on whether these GNNs are actually representative enough for their successful applications to downstream tasks such as neural diving or branching. This paper provides a clear example which this method might fail, and provides an insightful characterization. I believe such a finding will help practitioners understand limitations of current approaches in applying GNNs to MILPs.

Authors also build upon well-established approaches from the literature: The suggested remedy of adding random features is simple, but well supported by recent literature on GNNs. 

The contribution of the paper is mostly theoretical rather than empirical, and unfortunately the paper is not very clear about the limitation of the analysis. Most importantly, authors fail to mention that the particular bipartite graph representation they introduce is a simplification of what was actually introduced in Gasse et al. (2019). The paper almost reads like this representation is exactly what Gasse et al and follow-up papers like Nair et al are using, whereas in reality these papers have a number of engineered features and therefore the suggested "unfoldability" is much less likely to happen. I still find authors' analysis to be insightful- good analysis requires simplification. However, authors should've clarified they are making simplifications.

I am also not sure adding random features is the right remedy to the problem. For sure, making every node color unique will allow WL test to always separate two graph instances. But on the other hand, when there are two equivalent MILP problems, WL test will now fail to recognize they are equivalent? Hence we seem to be losing statistical power from this "remedy", but this loss of statistical power is not characterized, not giving readers the sense of trade-off being made.

Authors could've provided much more insight on the practical usefulness of foldability if they used MILP problems from existing benchmarks. How many of MILP problems in the literature are actually foldable; is there any? If there are, how does that impact the performance of GNN-based feasibility classifiers and/or neural diving/branching models?
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. Mathematical notations are consistent throughout the paper, and follow well-established conventions, which make it easy to follow the discussion without much effort.

The identification of the negative example which current graph representation fails is clever and insightful. Given GNNs have been quite popular for MILP applications, I am surprised such a negative result did not already exist. Hence I highly value the novelty of this work. Authors also built upon standard tools for understanding GNN representative power, which makes the method principled. Beyond the identification of the negative example & characterization with foldability, however, the rest of the analysis seems standard.

The paper is mostly theoretic, so reproducibility is not a big concern. I wasn't able to find code, but replicating results is likely low effort given the simplicity of experiments.


summary_of_the_review: Being clear about limitations of the analysis, and bridging the gap between the analysis & actual practice will strengthen the paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the representation power of GNN on mixed integer linear programming (MILP) problems. The paper shows that vanilla GNNs are not powerful enough to represent MILP problems. They further prove that the random feature strategy can overcome this issue. Most reviewers agreed that this paper made a good contribution to the L2O community. The major issue lies in the random-feature trick. I explain as follows. 
1.In theory:  The analysis of the random feature technique requires infinite-width GNNs, which is  not practical. A better analysis should work on GNN with finite number of parameters. 
2.In practice: The practical value of the random feature trick remains unclear. As mentioned in the script, the random feature technique requires that the testing MILP has the same structure as the training MILP. This condition rarely holds in real-world tasks. I think a better theoretical paper should provide an analysis of a more practical trick. 
Even if this work has some limitations, its contribution outweighs its disadvantages. For this reason, I recommend accepting this paper.

justification_for_why_not_higher_score: The major issue lies in the random-feature trick. I explain as follows. 
1.In theory:  The analysis of the random feature technique requires infinite-width GNNs, which is  not practical. A better analysis should work on GNN with finite number of parameters. 
2.In practice: The practical value of the random feature trick remains unclear. As mentioned in the script, the random feature technique requires that the testing MILP has the same structure as the training MILP. This condition rarely holds in real-world tasks. I think a better theoretical paper should provide an analysis of a more practical trick. 
justification_for_why_not_lower_score: The paper shows that vanilla GNNs are not powerful enough to represent MILP problems. They further prove that the random feature strategy can overcome this issue. Most reviewers agreed that this paper made a good contribution to the L2O community. Even if this work has some limitations, its contribution outweighs its disadvantages.
Decision: Accept: poster