Maximum Independent Set: Self-Training through Dynamic Programming

Summary

Maximum Independent Set: A Dynamic programming approach (DP) to GNNs. The idea is to solve a Combinatorial Optimization problem, in particular the Maximum Independent Set (MIS): max set of nodes so that no two nodes are neighbors (set of nodes not linked by edges). The problem is NP-Hard but a GNN can generate an approximation. DP partitions the graph in subgraphs. The main idea is to avoid the exponential space. Theorem 1 enables the recursive search. The idea is to remove nodes recursively or their neighbors. Basically, if a vertex is in the MIS, its neighbors cannot be! GNNs for MIS. The approach is incremental. A) Build comparator CMP based on theorem 1, for determining whether to graphs have approximately MIS size. B) Implement CMP using GNNs. Initially, we have neighbors and anti-neighbors (as the degree of freedom). However, the initial embedding is ZERO for ALL of them. The new embedding for a node comes by concatenating that of its neighbors with that of the anti-neighbors. Later on, when this information is pooled to form a global embedding and fed to an MLP, its decision will be sent backward. This is explained in section 5. Self-Learning using CMP. Since the problem is NP-Hard it is reasonable to use the randomized CMP as a provider of examples. In this regard, Theorem 2 guarantees that any consistent graph comparing function CMP (the expectation of the randomized CMP is greater for the graph it has to be) induces an optimal algorithm ACMP for MIS. The basic idea is to choose to parameterize CMP_theta in such a way that it is consistent. This is exactly the GOAL OF TRAINING. Experiments. Compare the proposal with greedy methods. Usually greedy methods works very well but in some graphs. The method seems to generalize a bit. I agree with the conclusions: “We firmly believe that a thorough investigation into the interplay between Dynamic Programming and self-training techniques can pave the way for new deep-learning-oriented approaches for demanding CO problems”.

Strengths

A nice paper for illustrating the use of GNNs in CO problems through self learning, specially in NP-Hard Problems. Nice time complexity for a fixed budget.

Weaknesses

Despite the framework is nice, there is no insight in terms of verifying whether the resulting embeddings of the nodes verify the decision taken. A probable approach is to hash the compatible nodes to one code and the incompatible one to another code. In this way the method will be more explanatory and will enlarge the consistency of the response.

Questions

How do the parameters of the CMP_theta evolve? How far/close are them of resturning consistent/inconsistent responses? In other words, use the analysis of these parameters to diagnose how hard is the problem for different graphs.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Maybe better GNNs could improve the results. Agree with the authors the lack of convergence analysis. In this regard, it seems to me that making the CMP_theta more explainable will help.

Summary

This paper studies the combination optimization problem, maximum independent set, via self-training. By training a consistent graph comparator function to determine the larger MIS of two different graphs, the MIS of original graph can be obtained recursively efficiently.

Strengths

1. The notations and presentation are clear. 2. The idea of using the intermediate results during algorithm execution to supervise the model itself is novel.

Weaknesses

1. The most important component in the proposed method is the consistent graph comparator. It would be better to include more detailed explanation on why the learned graph comparator will be consistent. 2. As the algorithm $A$ depends on $CMP_\theta$, and the whole training pipeline relies on $A$, what will happen if $CMP_\theta$ makes a lot of mistakes initially? This should be discussed. 3. The computational complexity/overhead should be discussed.

Questions

See in weaknesses.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Limitations are mentioned. Negative societal impact is not applicable.

Summary

This work uses a dynamic programming framework for approximately solving the maximum independent set (MIS) and minimum vertex cover (MVC) problems. A graph neural network (GNN) is used to replace a heuristic step in the randomized version of the DP algorithm. Essentially, MIS (and MVC) can be broken down into (2^n) recursive decisions about whether to include a vertex in the output set or not. The randomized version doesn’t go through all of these, but decides for a random vertex whether or not to include it. This setup ensures that the output will be a valid independent set regardless of the decisions. In this paper, the decisions are made by a trained GNN (heuristic). The GNN is trained by comparing the output IS with random independent sets formed by performing rollouts starting with the alternative choice. E.g., if the GNN decides to include vertex v in the IS, then the rollouts are performed on the graph without v. The greedy rollout is included in the mixed version, to potentially improve this training signal. The GNN architecture used is referred to as GEM, but as far as I can tell, the GNN is exchangeable for any other GNN architecture.

Strengths

1. This is a neat setup for DP problems on graphs. The framework ensures that the outputs are valid, and using a GNN as a heuristic can make sense. It's a nice idea to replace a heuristic step in an algorithm with a GNN (but this is not the first work to do so). 2. The approach is clearly laid out and easy to follow. 3. Some of the results are promising. The GNN also clearly outperforms the random CMP, indicating that the GNN is learning something useful and contributing positively to the algorithm.

Weaknesses

1. It is not clear how much impact this paper might have. I’m sure the framework can be used for some other CO problems where the output is a subset of the input, but it is not clear how widely applicable it might be, especially given its runtime complexity. 2. The main novelty seems to be the use of a GNN for the decision step in the algorithm. 3. GEM is given a new name, but it is essentially fully-connected message passing, where neighbours and non-neighbours are aggregated separately. This is not a novel contribution, so I don’t think it deserves a new name. 4. The proposed model is not scalable to larger graphs. Already the GNN used (GEM) is n^2 per layer (n being the number of nodes), which simply doesn’t scale to large graphs. Moreover it is applied n times at inference, giving n^3 runtime. What are the largest graphs you can run on? How does the complexity compare with the complexity of the other approaches? 5. Greedy baseline outperforms the proposed approach on 2/4 datasets. 6. The results are not very convincing for MVC.

Questions

1. Have you tried using any other GNN architectures (GIN, GAT, Erdos, Graph Transformer, ...) for the heuristic step? 2. Are the anti-neighbors needed? How is the performance without (this would help in lowering the overall complexity)? 3. How many rollouts are needed for the results? 4. Why not use a GNN to decide on the next vertex to consider rather than doing it randomly? There might be some vertices that are easier to decide whether to include at a given time. 5. Why is SPECIAL missing from Table 2? 6. Is RB or TWITTER really out-of-distribution for COLLAB? Maybe those datasets are very similar in distribution. 7. What about using only the greedy rollout? 8. Some symmetry breaking is probably needed for the greedy approach (e.g. if there are (neighboring) nodes with the lowest degree in the graph), so multiple rollouts could be done here and the max taken. Do you consider only a single (random) rollout? Or do you run greedy multiple times? 9. The random CMP could be replaced by a degree-weighted random CMP, i.e. selecting lower degree nodes with a higher probability, but not necessarily taking a lowest degree node. This would essentially make the greedy approach a little more robust to “special” graphs, maybe providing a better baseline. 10. Do you have any insights into the GNN decisions?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

yes

Summary

This paper proposes a method to solve the maximum independent set (MIS) problem using self-trained dynamic programming and carefully-designed GNNs. The MIS problem is decomposed into dynamic programs and solved by comparing two reduced graphs.

Strengths

It is interesting and innovative to address the MIS problem using GNNs in a self-training manner. The proposed method is effective and efficient for solving the MIS problem.

Weaknesses

The following improvements could enhance the experiments: 1. Baseline comparisons: In Line 74, several recent baselines are mentioned. It would be beneficial to include comparisons with these methods in the experiments to demonstrate the superiority of the proposed approach. 2. Evaluations on large-scale graphs: Existing methods [Schuetz et al., 2022b, Wang and Li, 2023] have demonstrated their effectiveness on larger-scale graphs with more than $10^4$ nodes. It would be valuable to showcase the results of the proposed method on such graphs. 3. Comparisons on model training: Since the proposed method employs self-training, it would be informative to compare the training cost of the proposed method with that of the baselines. Including such comparisons would provide insights into the efficiency of the proposed approach.

Questions

None

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Please check the weaknesses.

Summary

The paper proposes a GNN based method to approximate the largest independent set for a graph. The algorithm proposes to train a GNN layer to decide at each iteration whether a randomly selected node should be a part of the independent set, the resulting graph (either losing the neighbours of the chosen node or only the node the itself) is then the input at the next iteration. For graph distribution datasets are used for empirical evaluation.

Strengths

The paper employs a DNN module at an appropriate place, i.e. as the graph comparator function, which is sensible. This would be a reasonable contribution if the weaknesses would be addressed.

Weaknesses

EDIT: Summary: Some of the weaknesses mentioned were incorrect (W1,W2,W4) (apologies to the authors). Some of the weaknesses simply need to be discussed in the paper (W3,W5,W6,W7,W9). In my opinion the deciding factor should be W8, does the AC think that simply using benchmarks with no real-world connection to the problem we are trying solve are good empirical evaluation (only used because prior work did and nobody checked that) is good enough. If Yes, the paper should clearly be accepted (score of 7), else it should be rejected as the accepted benchmark should be updated. Thus, I have updated my score to a 5, 7 if the authors decide to add a benchmark with a real world connection or explain why one of the current benchmarks has a real-world connection and thus represents the distribution of graphs one might find in practice. 1. I retract the first point in the bullet list below, it is indeed incorrect as the authors point out in the rebuttal. 2. In the second bullet point, I also did forget a word ("might") that does matter, however, I regarding remark 4 I maintain my criticism, while the interpretation that the authors provide in the rebuttal makes sense what is written in the paper is much more broad. I suggest they reword for the camera ready. 3. Regarding point 3, I thank the authors for addressing the computational complexity more directly, but the comparison in run-time to Gurobi seems unfair as that tries to find the optimal solution as far as I understood, which is naturally exponential in the worst case, so this seems to be an apple to oranges comparison, the greedy heuristic may be a better comparison point. 4. I also retract W4. 5. It is a weakness that the paper doesn't discuss this in it's current form. 6. I stand by W6 given the current phrasing in the paper which is "Since we observe unexpected performance from RUN-CSP on the COLLAB and RB269 datasets, we have omitted those results from the table." This doesn't explain why it has been removed, which is necesary. 7. Units should still be explained. One prior work doesn't make it standard enough to not mention it. 8. Prior work having used the benchmarks is in my opinion a weak argument without any other benchmarks. But I understand that this is a contentious issue within the ML community. I leave this up the AC, but as far as I can tell from the response of the authors, there is no particular use in the real-world to compute the MIS on something like the Twitter dataset. 9. I agree that such work is still valuable, but it's an obvious limitation that needs to be discussed and wasn't in the paper. The paper has substantial weaknesses that prevent acceptance at this time in my view: 1. The authors demonstrated knowledge of what NP-hard means is poor, frequently mis-using the term and similarly the context of approximation algorithms is missing completely. In more detail: NP is a class of BINARY decision problems, i.e. the problem asks a yes or no question. Maximum Independent Set (Defintion 1) as defined in the problem is not such a problem and thus cannot be classified as NP-hard or anywhere in that complexity hierarchy. Leading to several incorrect claims in the paper (e.g. line 181). Furthermore, problems that are NP-hard are considered computationally infeasible for anything but the smallest instance sizes, so a sentence like "computationally infeasible for NP-hard problems" (line 21) does not make sense. If we want to discuss the optimisation problems associated with an NP-hard problem, e.g. finding the optimal route of the travelling salesman problem or finding the maximum independent set, this is a different computational complexity class with it's own hierarchy. This is especially important once we care about approximations, doubly so when we want to considered the randomized approximation algorithms, however, any such discussion is missing. 2. Various statements about the quality of the solutions of the algorithm are imprecise or plain wrong. For instance, in line 136 the claim is made "there exist a reasonable graph comparing functions that i) are efficiently computable ii) lead to near optimal solutions" with no reference to any proof or evidence. These baseless claims decrease the authors credibility significantly. (another example can be found in remark 4 the second sentence). 3. The computational computational complexity of the algorithm is never discussed, which is particularly relevant given we are approximating solutions and thus there is a fundamental trade-off between time and the quality of the solution found. The algorithm proposed is of high-computational complexity, a single GEM module layer as proposed in equation 1. is already of complexity O(n^2) where n is the number of nodes. This would quickly be infeasible for problems of an interesting size and also raises the question why a GraphTransformer architecture wasn't considered. Furthermore, the GEM layers need to be applied O(n) time in the worst case, as the recursion depth of algorithm 1 is O(n) in the worst case. Thus giving us at least O(n^3) at inference time, neglecting the training time here, making the algorithm expensive to run. This is not compared against any other method either, e.g. the computational complexity of traditional solvers like Gurobi or other baseline methods is also not given. 4. Theorem 1 seems to be missing a +1, presumably when we remove a node v from the graph and add it to the independen set this should lead to a +1 appearing somewhere in the equation of |MIS(G)|. 5. The computational complexity of computing the expectation in the loss function given in equation 2 seems prohibitively high and there is no discussion about the variance in estimating the expectation by using only samples. In practice, this seems to be replaced with roll-outs another form of probabilistic estimation, whose complexity or variance remain unmentioned. Again, a claim is made that these roll-outs are better than the original expectation without any empirical or theoretical evidence. 6. The empirical evaluation removes the results from the RUN-CSP baseline with the words "unexpected performance" without any further justification, this is highly unusual and not acceptable practice. 7. Table 1 uses an unexplained unit of s/g. 8. The benchmark datasets aren't justified, why is it interesting to compute the MIS of a twitter graph? Given that the graph distribution will be highly relevant to performance this is important. While it is understandable to re-use benchmark datasets that prior work has used, it doesn't help the paper if the benchmark datasets aren't specfic to any real world problem people care about. At least one dataset needs to be of relevance to a real world problem, e.g. MIS is used in compiler optimisations. 9. There is no adequate discussion of running time or discussion of any benefits of the proposed method or DNN methods in general over classical optimisation solvers for the problem studied. Indeed, from Table 1. I cannot discern why a practioner would use the method proposed over Gurobi over SCIP.

Questions

None.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

No the limitations are not adressed, see the weaknesses.

Summary

This paper proposes a novel graph neural network (GNN) framework for solving the maximum independent set (MIS) problem. The idea is to use a randomized divide-and-conquer algorithm (which is termed as dynamic programming in the paper though) to pick a random node or its neighborhood and divide the problem into two subproblems recursively. In order to choose one of two actions at each step, the authors propose to parameterize the comparator with a GNN over the current graph structure. The advantage of this method is that it can bootstrap training data generation with a trained GNN, and then improve the GNN with the new training data. This reduces the cost of training data generation for MIS, which is an NP-hard problem. Experiments on 4 datasets show that the proposed CMP method achieves the best results among all deep-learning-based methods under similar time budgets.

Strengths

- S1: This paper proposes a novel solution for the MIS problem. It induces a random MIS inference algorithm from a comparator function, where the comparator function is parameterized by a GNN model. - S2: One of the challenge for NP-hard problems is the cost for generating annotated data. The authors employ a smart way to bootstrap data generation from a learned GNN comparator and use the generated data to further train the model. - S3: Experiments on 4 datasets show that the proposed CMP method achieves the best result among all deep-learning-based methods under similar time budgets.

Weaknesses

- W1: The paper mistakes recursive algorithms for dynamic programming. This makes the paper somehow hard to understand. Dynamic programming is for problems with overlapping sub-problems. If the sub-problems are non-overlapping, then it is called divide-and-conquer algorithms. If every action only results in a single sub-problem, then it is merely a normal recursive algorithm. According to Alg. 1, the proposed model is a recursive algorithm. - W2: The writing of this paper can be improved. The authors don’t emphasize the randomized nature of their inference algorithm very much, so it’s hard to understand what an expectation over the inference algorithm is at first glance. As the randomized inference algorithm is the key technique to achieve the goal of self-training, the authors may emphasize it more in the abstract and the introduction. - W3: There are some concerns regarding the time complexity of the proposed CMP model. According to Alg. 1 and Eqn. 1, the time complexity of this paper is $O(n^2|MIS(G)|)$ in the worst case. The datasets used in this paper mostly contain around a hundred nodes, which can’t reveal the disadvantage in the time complexity. It’s recommended that the authors analyze this in the paper. Also is it possible to avoid $O(n^2)$ dense propagation in the GNN?

Questions

- Q1: Line 20-21: According to [1], any polynomial-time sampler generates an easier sub-problem of an NP-hard problem. It looks to me that the CMP model can’t avoid this problem, either. Can you explain that? - Q2: Line 22-23: How do you circumvent this difficulty? Please be explicit in the introduction. - Q3: Algorithm 1: Please emphasize this is a randomized algorithm. - Q4: Line 183-184: This sentence requires more clarification. From my understanding, a model can’t learn anything from what it infers, unless it is a randomized algorithm or some planning algorithms as in this paper. - Q5: Algorithm 2 Line 5: Where is $G_{init}$ used? - Q6: Line 240-241: It’s a little bit confusing that you replace the basic pipeline, which is something you proposed, with two other approaches. You may say “improve the basic pipeline by …”. The title of the paragraph may be changed to “Better MIS estimation”. - Q7: Line 249: Mixed roll-out variant should be parallel with the first approach, not with “Estimating the MIS”. It may be renamed to “Mixed roll-out estimator”. - Q8: Line 316-317: What do you mean by “core modules”? [1] Yehuda et al. It’s not what machines can learn, it’s what we cannot teach. ICML 2020.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors discuss the limitations but not the societal impact in the paper. It seems that the proposed method will not cause obvious negative societal impact, but the authors are encouraged to discuss it.

Are there any remaining questions from reviewer b8RC?

Dear reviewer b8RC, We appreciate your constructive feedback and questions. We are wondering whether there are any additional questions that we might be able to answer for the reviewer. The key questions so far concern both the *methodology*, e.g., requirement for the anti-neighbors, and the *experimental setup and results*, e.g., the the difference between the datasets (please check Table 2 in the provided single-page pdf for a detailed answer), or the insights for the GNN decisions. Please let us know if you have any remaining questions. We are happy to answer them. If you are satisfied with our responses, we would be grateful if you could re-evaluate your score. Best regards, Authors

Are there additional comments from Reviewer v2kw?

Dear reviewer v2kw, we hope that our response covers the key questions of consistency from the original review. We are **open to your suggestions**, since the summary indicates a clear understanding of our work. If you have any additional comments or questions, we are happy to address them. Best regards, Authors

Are there any remaining concerns?

Dear reviewer qbTV, we are thankful for your time and effort to review our work. Based on your original review, our responses clarify that MIS is an NP-hard problem (correctly stated in the manuscript) and the validity of our theorem. We also elaborate on the statements flagged by the reviewer. We are wondering whether the reviewer has any other concerns regarding our work. Best regards, Authors

Are the concerns of the reviewer rVy4 addressed?

Dear reviewer rVy4, we are thankful for the constructive questioning and the overall appreciation of our work. Our responses clarify the why dynamic programming is appropriate, the randomised nature of the inference as well as the questions raised by the reviewer. We are wondering whether the reviewer has any remaining questions. We are happy to elaborate further, since we consider this work introduces novel elements, e.g., with respect to data annotation in MIS. Best regards, Authors

Are there any last concerns from Reviewer T1ds?

We are happy to address any last concerns the reviewer T1ds might have. Beyond the consistency, let us further clarify some of the points raised by the reviewer: 2. Naturally, the untrained comparator makes a lot of mistakes in the beginning. These mistakes are also indicated in the poor performance of the untrained comparator presented in Table 1 (in the paper). However, through additional roll-outs in the produced sub-graphs during the execution of Algorithm~1, the comparator is able to realize its past mistakes and update the weights that lead to fewer and fewer mistakes. We believe that the latter is nicely depicted in the additional plots that we have provided depicting the increasing behavior of the comparator (see Figure in the pdf). *We remark that being more consistent implies fewer mistakes*. In the revised version of our work we will incorporate the above valuable discussion. 3. We are thankful to the reviewer for raising this point. The complexity of our inference algorithm is in the worst case $O(n^3)$. In the revised version of our work we will explicitly mention the above (see also our response [b8RC](https://openreview.net/forum?id=igE3Zbxvws&noteId=zIK0d3OVCR) and the response to [qbTV](https://openreview.net/forum?id=igE3Zbxvws&noteId=LaaSZFxI4a)). If the reviewer has any remaining concerns, we would be happy to address them.