Maximum Independent Set: Self-Training through Dynamic Programming
Authors: Lorenzo Brusca
Lars C.P.M. Quaedvlieg
Stratis Skoulakis
Grigorios Chrysos
Volkan Cevher
Venue: NeurIPS 2023 poster (2023)
Keywords: Maximum Independent Set
Combinatorial Optimization
Graph Neural Networks
Dynamic Programming
TL;DR: We propose a neural approach that is inspired by dynamic programming to tackle the Maximum Independent Set problem

Abstract: This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly constructs two smaller sub-graphs, predicts the one with the larger MIS, and then uses it in the next recursive call. To train our algorithm, we require annotated comparisons of different graphs concerning their MIS size. Annotating the comparisons with the output of our algorithm leads to a self-training process that results in more accurate self-annotation of the comparisons and vice versa. We provide numerical evidence showing the superiority of our method vs prior methods in multiple synthetic and real-world datasets.

Maximum Independent Set: Self-Training through Dynamic Programming
Lorenzo Brusca"
Lars C.P.M. Quaedvlieg' Stratis Skoulakis' Grigorios G Chrysos Volkan Cevher
École Polytechnique Fédérale de Lausanne, Switzerland [[first name]. [last hame]]Gepth ch
Abstract
This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose DP-like recursive algorithm based GNNs that firstly constructs larger MIS, and then uses it in the next recursive call. To train our algorithm, require annotated comparisons of different graphs concerning their MIS size. Annotating the comparisons with the output of our algorithm leads to a self-training process that results in more accurate self-annotation of the comparisons and vice versa. We provide numerical evidence showing the superiority of our method vs prior methods in multiple synthetic and real-worke datasets.
smaller sub-graphs, predicts the one with the
Introduction
Deep neural networks (DNNs) have achieved unprecedented success in extracting intricate patterns directly from data without the need for handcrafted rules, while still generalizing well to new and previously unseen instances [He et al.] 2016 Vaswani et al. 2017). Among other applications, this success has led to the development of frameworks that utilize DNNs to solve combinatorial optimization (CO) problems, such as the Traveling Salesman Problem [Xing and Tu 2020 Hu et al. 2020 Prates et al., 2019], the Job-Shop Scheduling Problem [Zhang et al. 2020 Park et al. 2021 and the Quadratic Assignment Problem [Nowak et al. 2017].
core challenge for deep learning approaches on CO is the lack of training data. Annotating such data requires the solution of huge number of instances of the CO, hence such supervised learning approaches are computationally infeasible for NP-hard problems [Yehuda et al., 2020).
Circumventing this difficulty is key to unlocking the full potential of otherwise broadly applicable DNNs for CO.
Our work demonstrates how classical ideas in CO together with DNNs can lead to a scalable self- supervised learning approach, mitigating the lack of training data. Concretely, we focus on the Maximum Independent Set (MIS) problem: Given a graph GVV E), MIS asks for a set of nodes of maximum cardinality such that no two nodes in the selected set are connected with an edge. MIS is an NP-hard problem with several hand-crafted heuristics (e.g.. greedy heuristic, local search). More recently, several deep learning approaches have been proposed [Karalias and Loukas 2020
Toenshoff et al.) 2019 Schuetz et al. 2022a
Our approach involves the following steps determine MIS in graph. We graph neural networks (GNNs) [Wu et al. 22020] to enable model to generate approximate maximum independent sets after training on data that was annotated by the model itself. For this purpose, draw inspiration
"These authors contributed equally to this work.
Work done while at EPFL. Currently at University of Wisconsin-Madison; [surname] wisc.edu.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

from dynamic programming (DP) and employ DP-like recursive algorithm. Initially, we are given a graph. At each recursive step, we select a random vertex from that graph and create two sub-graphs: one by removing the selected vertex and another by removing all its neighboring vertices. We then make a comparison between these sub-graphs to determine which sub-graph is likely to have larger independent set, and we use the sub-graph with the highest estimated independent set for the next recursive call. We repeat this process until we reach a graph consisting only of isolated vertices, which signifies the discovery of independent set for the original graph.
Dynamic programming guarantees that if our predictions are accurate (i.e., we select the sub- -gaah with the largest MIS value), our recursive algorithm will always result in maximum independent set. To make accurate predictions, we introduce "graph comparing functions," " which take two graphs as input and output a winner. We implement such graph comph-inn functions with GNNs.
We adopt a self-training approach to train our graph-comparing function and optimize the parameters of the GNN. In each epoch, we update the graph-comparing function parameters to ensure it accurately fits the data has seen so far. The data comprises pairs of graphs (G, G') along with a label Label(G, G") E {0, 1]. For annotating the labels, we utilize the output of the recursive algorithm that leverages the graph-comparing function. Supported by theoretical and experimental evidence, we demonstrate how the self-annotation process improves parameter selection.
We conduct thorough validation of our self-training approach in three real-world graph distribution datasets. Our algorithm surpasses the performance of previous deep learning methods [Karalias and Loukas 2020 Toenshoff et al. 2019 Ahn et al. 2020] in the context of the MIS problem. To further validate the efficacy of our method, we explore its robustness on out-of-distribution data. Notably, results demonstrate that the induced algorithm achieves competitive performance, showcasing the generalization capability of the learned comparator across different graph structures and distributions. In addition, we extend the evaluation of our DP-based self-training approach tackle the Minimum Vertex Cover (MVC) problem in Appendix D Encouragingly, similar to the MIS case, our induced GNN-based algorithms for MVC admit competitive performance with respect other deep-learning approaches.
The code for the experiments and models discussed in this paper is available at: https://githu:
2
Related Work
Our work lies in the intersection of various domains, i.e., combinatorial optimization, Dynamic Programming, and (graph) neural networks. We review the most critical ideas in each domain here and defer a more detailed discussion in Appendix A
Graph Neural Networks (GNNs) have gained widespread popularity due to their ability to learn representations of grapb-structured data (Xiao et al. [2222] Zhang and Chen 2018 Zhuu et al. 2021
Errica al.) [019] invariant to the size of the graph. More complex architectural blocks. such as the Graph Convolutional Network (GCN) Kipp and Welling 2017 Zhang et al. 2019]. the Graph Attention Network (GAT) (Veličković et al. 2017]. and the Graph Isomorphism Network [Xu et al., 2018) have become influential instances of GNNs. In our work, we utilize a simple GNN architecture to showcase the effectiveness of our proposed framework. While our choice of architecture is intentionally simple, we emphasize its modular nature, which enables us to incorporate more complex GNNs with ease.
Combinatorial Optimization: Supervised learning approaches have been used for tackling CO tasks, such as the Traveling Salesman Problem (TSP) [Vinyals et al., 2015). the Vehicle Routing Problem (VRP) (Shalaby et al. [022]] and Graph Coloring [Lemos et al. 2019]. Due to the graph structure of the problems, GNNs are often used for tackling those tasks [Prates et al. 2019 Nazari al.) 2018 Schuetz et al. 2022b). However, owing to the computational overhead of obtaining supervised labels, such supervised approaches often do not scale well. Instead, unsupervised approaches have been deployed recently [Wang and Li] 2023). A popular approach relies on a continuous relaxation of the loss function [Karalias and Loukas) 2020 Wang et al. 2022, Wang and Li 2023 In contrast to the previous unsupervised works, we adopt Dynamic Programming techniques to diminish the overall time complexity of the algorithm. Another approach uses reinforcement learning (RL.) methods to
address CO tasks, such as in Covering Salesman Problem [Li ct al. 2021], the TSP (Zhang et al.

---

2022], the VRP James et al. 2019], and the Minimum Vertex Cover (MVC) Tia and Li 2021] However, applying RL to CO problems can be challenging because of the long learning time required and the non-differentiable nature of the loss function.
Dynamic Programming has been a powerful problem-solving technique since at least the 50s [Bell man 1954]. In recent years, researchers have explored the use of deep neural networks (DNNs) to replace the function responsible for dividing problem into subproblems and estimating the optimal decision at each step (Yang et al. 2018). Despite the progress, implementing CO tasks with Dynamic Programming suffers from significant computational overheads, since the size of the search space grows exponentially with the problem size [Xu et al., 2020]. Our approach overcomes this issue by utilizing model that approximates the standard lookup table from Dynamic Programming, meaning that we avoid the exponential search space typically associated with DP.
3 An Optimal Solution to Maximum Independent Set (MIS)
Firstly, let us introduce MIS and its relationship with Dynamic Programming.
Notation: G(V, E) denotes an undirected graph where V stands for vertices and E for the edges. (u)) denotes the neighbors of vertex v E (v)) = {u E V (u, v) E E}. The degree of vertex V is d(v)= == IA [v)]. Given a set of vertices S C V. G/S denotes the remaining graph of G after removing all nodes E S.
Definition (Maximum Independent Set). Given an undirected graph G(V, E), find a maximum set of nodes S C V such that (u, v) $ E for all vertices u, E S. We denote with (MIS(G) the size of the maximum independent set of graph G.
Dynamic Programming is a powerful technique for algorithmic design in which the optimal solution of the instance of interest is constructed by combining the optimal solution of smaller sub-instances. The combination step is governed by local optimality conditions which, in the context of MIS, take the form of Theorem [ Theorem 1 establishes that the decision to remove node E V or its neighbors (()) during the recursive process depends on whether |MTS (G/N(w)) Z [MT)(G This decision continues until graph with no edges is reached. According to Theorem I if at each step of the recursion, the choice is made based on whether [MSS (G/N(v)) Z IMIS (GFe) or not, then the resulting empty graph is guaranteed to be an optimal solution. The proof is this theorem can be found in Appendix !|
Theorem 1. Let a graph G(V, E) E G. Then for any vertex v E V with d(v) 2 1,
MTS(G)) = max (IMTS (G/N())) [MIS(G/(e)) 4
4 Graph Neural Network-Based Algorithm for MIS
In this section, we present our approach for developing algorithms for MIS parameterized by parameters 0 θ. Initially in Sec. 4.1 we present how any graph-comparing function taking as input two different graphs and outputting a {0, 1} value can be used in the construction of an algorithm computing
independent set (not necessarily optimal). In Sec. 4.2 we present how Graph Neural Networks can be used in the construction of such graph
functions. Finally, in we present our inference algorithm that computes independent set of any graph G' E G.
Sec. 4.3
4.1
MIS Algorithms induced by Graph Comparing Functions
Consider a function CMP: G x G + {0, 1} that compares two graphs G, G' based on the size of their MIS. Namely, if [MIS(G) Z [MI((G") then CMP(G,
and CMP G') = otherwise.
Theorem I ensures that if we have access in such a graph-comparti function then we can compute an independent set of maximum size for any graph G. From starting node v. with an initial graph from G, and by recursively selecting either G/(u} or Gv)(v) based on [MIS(G/(u)) Z [MTS(G/N(())) (v)),, we are ensured to end in independent set of maximum size. The decision of
Note: In the trivial case where G is an empty graph (i.e., it has no edges), the size of the maximum independent set is [V].
3

---

Algorithm Randomized Comparator-Inducee Algorithm
1: function ACMP (G(V, F))
Algorithm ACMP (G) takes graph G as input
2: if [E] = then return V
3: end if
4: pick vertex v E V with d(v) > uniformly at random.
5: Go - G) {o} and G1 +- G (v))
6:
if CMPPGG, Gi) = 0 then
7:
G
Remove vertex
8:
else
9:
G
Remove the neighbors of
10:
end if
return ACMP(() (G)
12:
end function
whether MIS(G//u)) 2 (IS(G//(()) each recursive call can be made according to the output of (CCCGG//,G//OO
The cornerstone idea of approach is that any graph-comparing function CMP induces such a recursive algorithm for a MIS. Recursively selecting G/(u} or G/N(v) based on the output of a graph generating function independent set of the original graph. In case CMP G') + ([MMIC) < [MIS("")]) where Il is the indicator function, is not guaranteed that the computed independent set of the maximum size. However, there might exist reasonable graph comparing functions that i) are efficiently computable ii lead to near-optimal solutions.
G/N)((())G/N(())
E [0,1) always guarantees reach
In Definition 2 and Algorithm [ we formalize the idea above.
Definition 2. A comparator CMP g -> {0, 1) is function taking imput two graphs G, G' and outputing a {0, 1] value.
Proposition Any comparator CMP G + {0, 13 induces a randomized algorithm ACT (Algorithm 7
Remark 1. Given a graph-comparing function CMP x -- {0, 10, the induced algorithm randomized, since at Step 4 of Algorithm ! vertex is randomly selected. Notice that Algorithml 7 recursively proceeds until a subgraph with 0 edges reached (see Step 2).
Remark 2. Two different comparators CMP and CMP' induce two different algorithms ACPP and A CMP' for estimating the maximum independent set.
4.2 Comparators through Graph Neural Networks
In this section, discuss the architecture of model Mo parameterized by 0 θ, that is used for the construction comparator function
CMPa(G,G)) = [[M < Mo(G'))
In order to embed graph-level information, we introduce a new GNN module, which we refer to as the Graph Embedding Module (GEM). Unlike standard GNN modules, this module captures different semantic meanings of differing embeddings of a node, its neighbors, and anti-neighbors.
Graph Embedding Module (GEM):
The GEM operates using the following recursive formula:
))
4+1 1
LN
GELU
gh
Σ
0h
Σ
(I)
wEN(e)
NgN(( (v)
Initially, all nodes in this graph have zeros embeddings 14 Ôe 3p Here, n denotes the initial
embedding vector of node v. In Eq. (T) for all iterations K E 10,.... K 1), the embeddings of

---

Fully Connected Layers
GEM for K Berations
Average Pooling Tr Die
Graph Logit
jaG
Ps
Figure I: Architecture of model (G). From left to right: initially, an input graph G is passed into the model with zeros as node embeddings, which are displayed white in the figure. The striped green edges connect the anti-neighbors, which are also used in the GEM. After K iterations of the GEM module, the final node embeddings are obtained. These then averaged obtain graph embedding μao Finally, the graph embedding is put through multiple fully-connected layers to obtain final logit value for the input graph.
node denoted by p SR its neighbors, and its anti-neighbors are put through their own linear layers, denoted by 0% 0f, 0 RRx33, which are the parameters of the module. The bias term is omitted in the equation for readability purposes. We incorporate anti-neighbors in the GEM to capture complementary relationships between nodes. By using separate linear layers for different features, we emphasize the contrasting semantic meaning between neighbors and anti-neighbors, representing negative and positive relationships the graph. Then, the individual feature embeddings are concatenated, which is denoted by [I.. followed by a GELU activation function (Hendrycks) and Gimpel| 2016] and layer normalization [Ba et al. 2016a] We note that the computational complexity of this module is ((VV)))
The complete model architecture depicted in Fig. [ At high level, the architecture Embedding Module to extract a global graph embedding from the input graph, which then passed through set of fully connected layers output a logit for that graph. During the training process of the comparator function, we utilize CMPs G") softmax Mo which forms differentiable loss function for classification.
Graph
4.3 Inference Algorithm
In the previous section, we discussed how parameterization O defines the graph-comparing function CMP G*) [Ma(G) < Ma (G')). As result, the same parameterization E e defines an algorithm ACMP, where at Step of Algorithm | the comparing function CMPs used. Since the number of graph comparisons is upper-bounded by VV. the inference algorithm admits to computational complexity of ((V))).
5 Self-Supervised Training through the Consistency Property
In this section, we present our methodology for selecting the parameters 0 E θ so that the resulting inference algorithm 4CMPa (-) computes independent sets with (close to) the maximum value.
The most straightforward approach is to select the parameters E such that CMP G') = II [[M[S(()) < [MTS(G")] using labeled data. The problem with this approach is that huge amount of annotated data of the form {[(G, G'), [[MI((G) < [MIS(G"[[]) are required. Since finding the MIS is Ha-Hard problem, annotating such data comes with an insurmountable computational burden.
The key idea to overcome the latter limitation is to annotate the data of the form {(G G')} by using the algorithm ACMPs (-) that runs in polynomial time with respect to the size of the graph. Intuitively, our proposed framework entails the optimization of the parameterized comparator function CMP, on data generated using algorithm CCMP, better comparator function leads to a better algorithm, which leads to better data, and vice versa. This mutually reinforcing relationship between the two components of our framework is theoretically indicated by Theorem that we present in Section 5.1 The exact steps are detailed below.
5

---

5.1 Consistent Graph Comparing Functions
In this section, we introduce the notion of consistent graph-comparing function (Definition B that plays a critical role in our self-supervised learning approach. Kindly take note that A utilizes the unparameterized variant of comparator function, whereas ACMP, utilizes its parameterized counterpart.
Definition 3 (Consistency). graph- ceaiph--omarringgiii if and only if for any pair of graphs G,G' G' E G.
CMP: G x g + {0,1} } is called consistent
CMP(G, G*) =0 if and only if [] [ 2 E [[ACMI(G')) (G"]]-
Remark 3. In Definition 3 we use E [[ACMM((G]] E [|A ( since, as we have already
discussed, comparator CMP induces a randomized algorithm ACMP, where the expectation is over the nodes in the graphs.
In Theorem 2 we formally establish that any consistent graph-comparing functtion CMP induces an optimal algorithm for the MIS.
Theorem 2. Consider consistent comparator CMP GxG (0, Then, the algorithm ACMP (-) always computes a Maximum Independent Set, E | CMMP (G) |MIS(G)) for all G g.
Theorem 2 guarantees that any consistent graph comparing function CMP induces an optimal algorithm A CMP for MIS. The proof for this theorem can be found in Appendix | Hence, the selection of parameters 6* E e should be selected such that CMP3- is consistent. More precisely:
Goal of Training: Find parameters 0 E ④ such that for all G, G" E EG:
CMP a- (G, G') = 0 if and only if EE [[A CMP (G)l] 2 B [| CMP [G)))]
5.2 Training a Consistent Comparator
The cornerstone idea of our self-supervised learning approach is to make the comparator more and more consistent over time. Namely, the idea is to update the parameters as follows:
CMP g++1_ == argminneeBB..cr [ (CMP G*), [[AM [G]]] E AMMP (G'III) (2)
where -(. is a binary classification loss. In Eq. ( are the fixed parameters of the previous epoch. Thus, in the next few paragraphs, we only use the notation ACMPs, to denote the fixed parameters. Gradient updates are only computed over
Remark 4. We remark that neither solving the non-convex minimization problem of Eq. 2 the existence of parameters 8 E ④ such that CMP can be guaranteed. However, using a first-order method for Eq. (2) and large enough parameterization can lead to an approximately consistent comparator with approximately optimal performance.
In Algorithm 2 we present the basic pipeline of the self-training approach that selects the parameters 0 E θ such that the inference algorithm A CCM,, admits a competitive performance given as input graphs G following graph distribution D C G. We further improve this basic pipeline with several tweaks that we incorporate into our training process:
Creating graph buffer B: We are given shuffled dataset of graphs D, which represents the training data for the model. The core difference between the pipeline and the training process comes from the graph buffer B. In Algorithm this buffer stores any graph G that is found during the recursive call of A CMPs, (Ginit) on Ginit ~ D (Step of Algorithm 2}. However, in the implementation the graph buffer, it stores pairs of graphs (G, G") that were generated by ACMPs, (Gmaa). alongside binary label that indicates which the two graphs has a larger estimated MIS size. How this estimate is generated, will be explained further down this section.
The training process: Prior to starting training, we first set two hyperparameters: one that specifies the number of graphs used to populate the buffer before training the model, and another that determines the number of graph pairs generated from A ACMP, (G) per graph G D. Then, a dataset created by generating these pairs for the set number of graphs. The dataset is then added to the graph buffer,

---

Algorithm 2 Basic Pipeline of our Training Approach
1: Input: A distribution D over graphs.
2: Initialize parameters On E O
3: Initialize a graph-buffer B <- 23.
4: for each epoch = 0,... ........ T do
5: Sample a graph Ginit ~ D.
6: Run ACMP (Ginit) and store in B all graphs produced during each recursive call of Algo-
r
7: Update the parameters oc+1 ① such that
g++
argninggg B(G, [e (CMPo(G, G"), IIA CMPP. (G) < [|A CMP (G)
8:
end for
Computing A [SIP ((Gua) and populating
Step Creating detsnet samples
Gus
[G Gb,, Co., Go)
CMP G2) mL
Computing 130 (6] (alloal
G2
CMM CMP Gi)
(MP)) A CMMP (G ChEP (Cio)
G2
G2
Constructing dataset with painiiee samples
CMPA(CG,GG))
Gs
GG. G.).
a (G.) < (G2)
G5
[c Gol.
(G < (Ca)
B+ BU (G., Ga...., G., Go]
(lG (1 (G.))
Figure 2: An example of data generation for the training. (Left) At the beginning of each training epoch (Step 5). Algorithm 2 samples Ginit ~ 'D and computes an independent set by using the comparator CMP,, o, and by tollowing the branches in the recursion tree that marked red, with the doubly circled one being the produced independent set. The generated graphs from this procedure are added to the buffer B. (Right) Then, a dataset created by sampling graphs from the buffer and then computing an estimate of their MIS size (based on ACMPs, ). Based on this estimate, a dataset is created with graph pairs (G, G") and their corresponding binary labels denoting which MIS estimates are larger.
replacing steps 5 and in Algorithm 2 which only does this with one graph per epoch. Next, training starts, and after completing set number of epochs, a new dataset is created using the updated model, and the process is repeated iteratively.
Estimating the MIS: Finally, the loss function in Step 7 of Algorithm 2 also operates slightly differently. The main difference arises from 1 [E [[A CMPs (G)l] < ACMP', (G') since the estimates JMIS(G) z E [[ACMPM, (G)]] and IMIS(G") ~ E
[[ [[ CMPP, (M)) are not directly utilized. Instead, we propose two other approaches, which are better approximations than the expectations used in Algorithm [ since they use a maximizing operator.
The first approach involves performing so-called "roll-outs" on the graph pairs generated G and G' by ACMP', in order to estimate their MIS sizes. To perform the roll-outs, we simply run AMMss graphs G and G' m times and use the maximum size of the found independent sets as an estimate of their MIS. Formally, in a roll-out on a graph G, we sample the inde- pendent sets ISS,, ISS, .... ISS,. A CMPs, (G). Then, the estimate of the MIS size of G is max ( [ISS I)
An example of the entire process of generating the dataset using roll-outs can be found in Fig. 2 In practice, we observe an increasing consistency of the model during training, as can be seen in Appendix
7

---

Mixed roll-out variant: We introduce a variant of the aforementioned method, which utilizes the deterministic greedy algorithm. This greedy algorithm iteratively creates an independent set by removing the node with the lowest degree and adding it to the independent set. This algorithm is often an efficient approximation to the optimum solution. Our variant is constructed as follows: we compute the maximum between the roll-outs of the model and the result of the greedy algorithm, which creates a dataset with more accurate self-supervised approximations of the MIS values. This, in turn, generates binary targets for the buffer that are more likely to be accurate. Thus, for this second variant, the estimate of the MIS size of graph G would be max (|Greedy (G)), [ISS1], [ISS2]..... [ISSm.)).
Experiments
In this section, we conduct evaluation of the proposed method for the MIS problem. Let us first describe the training setup, the baselines, and the datasets. Additional details and experiments on Our method also generalizes well in MVC, as the
MIS are displayed in the Appendices C and D
results in Appendix illustrate.
6.1 Training Setup
Our model: We implement two comparator models: one using just roll-outs with the model, and another using the roll-outs together with greedy, called "mixed roll-out". We train each model using a graph embedding module with K = 3 iterations, which takes in 32-dimensional initial node embeddings.
Baselines: We compare against the neural approaches Erdox GNN (Krralias and Loukas 2020], RUN- CSP from Toenshoff et al. (2019), and a method specifically for the MIS problem: LwDMIS [Ahn ct al. 2020]. Since we observe unexpected poor performances from RUN-CSP on the COLLAB and RB datasets, we have omitted those results from the table. We train every model for 300 epochs. Each experiment is performed on single GPU with 6GB RAM.
Besides neural approaches, we use traditional baselines, such as the Greedy MIS [Wormald 1995] Simple Local Search [Feo et al.) 1994] and Random Comparator as a sanity check. Furthermore, we implement two mixed-integer linear programming solvers: SCIP 8.0.3 and the highly optimized commercial solver Gurobi 10.0.
Datasets: We evaluate model three standard datasets, following Karalias and Loukas [2020] COLLAB (Yanardag and Vishwanathan 2015). TWITTER [Leskovec and Krevl][2044 and RB [Xu al. 2007, Toenshoff et al. [019]. In addition, we introduce the SPECIAL dataset that includes challenging graphs for handcrafted approaches as we detail in Appendix C
6.2 Results
Table I reports the average approximation ratios the test instances of the various datasets. The approximation ratio is computed by dividing solution's 's independent set size by the optimum solution, which is computed using the Gurobi solver with time limit of 1 hour per graph.
The results indicate that the greedy algorithm performs strongly in three the four datasets, which is consistent with the observation of Angelini and Tersenhhrs 2022]. However, notice that our pro- posed approach outperforms the greedy in both the Twitter and the SPECIAL datasets, which validates that the greedy heuristic is not optimal in every case and is prone to failing in few cases. Importantly, among the neural approaches that are the main compared methods, our proposed method performs favorably in all datasets. The performance of our method indicates that the proposed self trf-iiran scheme is able to learn from diverse data distributions and generalize reasonably well in the test sets of the respective dataset. In addition, the proposed method is faster than the rest neural approaches.
The mixed roll-out model in Table T outperforms the normal roll-out model in almost all datasets, indicating the effectiveness of the greedy heuristic in roll-outs. This is particularly evident in the RB dataset. However. for SPECIAL instances, the normal model performs marginally better, possibly due to the unsuitability of the greedy guiding heuristic baseline for this dataset.
Out of distribution: We examine the performance of the learned comparator through its general- ization to new graph distributions. Coneretely, we conduct out-of-distribution analysis as follows:
8

---

Table Test set approximation ratios (higher is better; best performance in bold) on four datasets for MIS. We report the average approximation ratios, along with std and duration in seconds per graph (s/g). Notice that the proposed method outperforms all the deep-learning-baseee -aaedd approaches across
datasets. Classical methods have a gray color, whilst neural approaches are in black.
Method ()) Dataset (-))
RB
COLLAB
TWITTER
SPECIAL
0.770 + 0.107
0.990 0.051
0.967 = 0.083
0.996 0.029
CMP (Normal Roll-outs)
(0.43 s/g)
(0.17 s/g)
(0.35 s/g)
(0.04 s/g)
0.836 + 0.083
0.990 + 0.049
0.977 = 0.031
0.994 + 0.035
CMP (Mixed Roll-outs)
(0.36 s/g)
(0.21 s/g)
(0.21 s/g)
(0.05 s/g)
0.813 = 0.107
0.952 0.142
0.935 = 0.078
0.921 + 0.218
Erdos' GNN
(1.39 s/g)
(0.60 s/g)
(1.37 s/g)
(1.03 s/g)
0.804 + 0.089
0.978 0.031
0.972 + 0.032
0.828 0.304
LwDMIS
(0.42 s/g)
(0.17 s/g)
(0.19 s/g)
(0.32 s/g)
0.875 + 0.053
0.946 0.059
RUN-CSP (Accurate)
(0.57 s/g)
(0.51 s/g)
0.925 + 0.053
0.998 + 0.023
0.964 0.048
0.131 + 0.055
Greedy MIS
(0.01 s/g)
(0.02 s/g)
(0.04 s/g)
(0.03 s/g)
0.615 +: 0.155
0.817 +: 0.211
0.634 0.182
0.225 + 0.279
Random CMP
(0.42 s/g)
(0.30 s/g)
(0.36 s/g)
(0.41 s/g)
Simple Local Search (IOs)
0.565 = 0.237
0.860 = 0.213
0.644
0.188 E 0.340
SCIP 8.0.3 (1s)
0.741 +: 0.351
0.999 + 0.016
0.959 + 0.024
1.000
SCIP 8.0.3 (5s)
0.937 + 0.118
1.000
0.999 + 0.024
1.000
Gurobi 10.0 (0.5s)
0.969 = 0.070
0.068 0.981
0.985 + 0.085
0.940 + 0.237
Gurobi 10.0 (Is)
0.983 = 0.051
1.000
1.000
1.000
Gurobi 10.0 (5s)
0.999 + 0.008
1.000
1.000
1.000
Table 2: Out-of-distribution approximation ratios during inference (higher better). Every row denotes a model trained on specific dataset. Every column considers different test dataset. The CMP is trained using mixed roll-outs. Notice that the proposed method generalizes well in out-of- distribution structures. This is indicative of the learned comparator extracting robust patterns.
Model (J) Dataset (-)
RB
COLLAB
TWITTER
CMP RB CMP COLLAB
0.903 = 0.186
0.668 0.187
0.856 + 0.080 0.773 0.101
0.906 + 0.094
CMP TWITTER
0.927 = 0.148
Erdos' GNN RB
0.361 = 0.334
0.752 + 0.188
Erdos' GNN COLLAB
0.680 0.071
0.592 + 0.186
Erdos' GNN TWITTER
0.746 + 0.092
0.666 = 0.385
each model is trained in one graph distribution, indicated by the rows of Table Then, the model is evaluated on different graph distributions, indicated by the columns of Table 2 The analysis is conducted on both our model and the approach of Erdos GNN [Karalias and Loukas 2020].
Surprisingly, our model trained over COLLAB displays good generalization skills across different datasets, even outperforming the RB ar-trained model on the RB dataset. Conversely, Erdos GNN trained over RB performs poorly over the COLLAB dataset. Both models trained over the RB dataset perform more poorly in general, likely due the highly specific graph distribution of the RB dataset. Moreover, our model, on the whole, exhibits good generalization skills over different graph distributions.
7 Conclusion
Motivated by the principles of Dynamic Programming, we develop self-training approach for important CO problems, such as the Maximum Independent Set and the Minimum Vertex Cover. Our approach embraces the power of self self-training, offering the dual benefits of data ceff-annotation and data generation. These inherent attributes are instrumental in providing an unlimited source of data indicating that the performance of the induced algorithms can be significantly improved with sufficient scaling on the computational resources. We firmly believe that thorough investigation into the interplay between Dynamic Programming and self-training techniques can pave the way for new deep-learning orieetee approaches for demanding CO problems.

---

Limitations: Our current empirical approach lacks theoretical guarantees on the convergence or the approximate optimality of the obtained algorithm. Additionally, the implemented GNN using simple modules, while more complex modules could result in further empirical improvements, which can be the next step this direction. Furthermore, randomly selecting vertex could he sub-optimal. One interesting future direction would be to explore predicting the next vertex to select.
Acknowledgements
This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021 200021_205011, by Hasler Foundation Program: Hasler Responsible Al (project number 21043) and Innovation project supported by Innosuisse (contract agreement 100.960 IP-ICT). We further thank Elias Abad Rocamora and Nikolaos Karalias for the useful feedback on the paper draft as well as Planny for the helpful discussions.
References
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what defer for maximum independent sets. International Conference on Machine Learning (ICML), 2020.
Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Maria Chiara Angelini and Federico Ricci-Tersenghi. Cracking nuts with sledgehammer: when modern graph neural networks do worse than classical greedy algorithms. arXiv preprint arXiv:2206. 13211, 2022.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization, 2016a.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.064550 2016b.
Richard Bellman. The theory of dynamic programming. BULL, 60(6):03333111111 1954.
Richard Bellman. Dynamic programming treatment of the travelling salesman problem. JACM, 9(1): 61-63, 1962.
Paul Erdós, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 571): 1960.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. arXiv preprint arXiv: 02.9999, 2019.
Thomas A Feo, Mauricio GC Resende, and Stuart H Smith. A greedy randomized adaptive search procedure for maximum independent set. Journal of Global Optimization, 42(5):860-8)) 1994.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. NIPS, 32, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Conference Computer Vision and Pattern Recognition (CVPR), pages 770-778. 2016.
Dan Hendrycks and Kevin Gimpel. Gaussian enror linear units 1606v:1606.0844 2016.
(gelus).
arXiv preprint
Yujiao Hu, Yuan Yao, and Wee Sun Lee. A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowledge-Brl Based Systems, 204:106244 2020.
JQ James, Wen Yu, and Jiatao Gu. Online vehicle routing with neural combinatorial optimization and deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 20 (18):3806-3817, 2019.
10

---

Steven James, George Konidaris, and Benjamin Rosman. An analysis of monte carlo tree search. AAAI Conference on Artificial Intelligence, 31(1), Feb. 2017. URL https::/ojs.... aaaii org/ index. http:///wAA//aatttcca///////////
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. Advances in neural information processing systems (NeurIPS), 33:6659-6672, 2020.
Maryam Marimi-Mamaghant Mehrdad Mohammadi, Patrick Meyer, Amir Mohammad Karimi- Mamaghan, and El-Ghazali Talbi. Machine learning the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art. EJOR, 296(2):393-42, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: pet....42...... 26800, 2014.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference Learning Representations (ICIR), 2017.
Henrique Lemos, Marcelo Prates, Pedro Avelar, and Luis Lamb. Graph colouring meets deep learning: Effective graph neural network models for combinatorial problems. International Conference on Tools for Artificial Intelligence (ICTAI), pages 879-885. IEEE, 2019.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: // //snap. stanford. edu/datat June 2014.
Kaiwen Li, Tao Zhang, Rui Wang, Yuheng Wang, Han, and Ling Wang. Deep reinforcement learning for combinatorial optimization: Covering salesman problems. IEEE Transactions on Cybernetics, 52(12): 2021.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems (NeurIPS), 31, 2018.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. COR, 134: 105400, 2021.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In International Conference Machine Learning (ICML), 2020. URL www www.hgaaraaaanggg.... io
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems (NeurIPS), 31, 2018.
Alex W. Nowak, Soledad Villar, Afonso S. Bandeira, and Joan Bruna. A note on learning algorithms for quadratic assignment with graph neural networks. ArXiv, abs//100.07450. 2017.
Junyoung Park, Sanjar Bakhtiyar, and Jinkyoo Park. Schedulenet: Learn to solve multi-agent
scheduling problems with reinforcement learning, 2021.
Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi. Learning to solve up-complete problems: A graph neural network for decision tsp. In AAAI Conference on Artificial Intelligence, volume 33, pages 4731-4733 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, 2022a.
Martin JA Schuetz, Kyle Brubaker, Zhihuai Zhu, and Helmut G Katzgraber. Graph coloring with physics-inspired graph neural networks. Physical Review Research, 4(4):043131, 2022b.
UIrich Schwalbe and Paul Walker. Zermelo and the early history of game theory. Games and economic behavior, 34(1):123-137, 2001.
Mohamed A Wahby Shalaby, Ayman R Mohammed, and Sally Kassem. Supervised fuzzy e-means techniques to solve the capacitated vehicle routing problem. IAJIT, 18(3A):552463,, 2021.
11

---

Hong Tian and Dazi Li. Graph convolutional neural networks with am am-actor-critee for minimum vertex cover problem. In 2021 33rd Chinese Control and Decision Conference (CCDC), pages 3841-3846. IEEE, 2021.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Run-csp: unsupervised learning of message passing networks for binary constraint satisfaction problems. CoRR, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems (NeurIPS), pages 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. NewrIPS, 28, 2015.
Haoyu Wang and Pan Li. Unsupervised learning for combinatorial optimization needs meta-lcarning. arXiv preprint arXiv:2301.03116 2023.
Haoyu Peter Wang, Nan Wu, Hang Yang, Cong Hao, and Pan Li. Unsupervised learning for combinatorial optimization with principled objective relaxation. NIPS, 2022.
Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small- (6684))440-444 442. 1998.
networks. newworss nature, 393
Nicholas C Wormald. Differential equations for random processes and random graphs AAP, pages 1217-1235, 1995.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Iransactions on neural networks and learning systems, (21)):424,, 2020.
Shunxin Xiao, Shiping Wang, Yuanfei Dai, and Wenzhong Guo. Graph neural networks in node classification: survey and evaluation. Mach. Vis. Appl., 33:1-19, 2022.
Zhihao Xing and Shikui Tu. A graph neural network assisted monte carlo tree search approach to traveling salesman problem. IEEE Access, 8:108418-108423 2020.
Zhihao Xing, Shikui Tu, and Lei Xu. Solve traveling salesman problem by monte carlo tree search and deep neural network. arXiv preprint arXiv:2005.06879, 2020.
Ke Xu, Frédéric Boussemart, Fred Hemery, and Christophe Lecoutre. Random constraint satisfaction: Easy generation of hard (satisfiable) instances. Artificial intelligence, 171(8-9):514-534 2007.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? arXiv preprint arXiv: 1188.0000.20. 2018.
Ruiyang Xu and Karl Lieberherr. Learning self-play agents for combinatorial optimization problems. KER, 35:e11. 1, 2020.
Shenghe Xu, Shivendra S Panwar, Murali Kodialam, and TV Lakshman. Deep neural network approximated dynamic programming for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1684-1691, 2020.
Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. SIGKDD, 2015.
Feidiao Yang, Tiancheng Jin, Tie- Yan Liu, Xiaoming Sun, and Jialin Zhang. Boosting dynamic programming with neural networks for solving np-hard problems. In ACML, pages 726-739.
PMLR, 2018.
Gal Yehuda, Moshe Gabel, and Assaf Schuster. It's not what machines can learn, it's what we cannot teach. In ICML, pages 10831-10841. PMLR, 2020.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances neural information processing systems (NeurIPS), 33:1621-1632, 2020.
12

---

Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. NeurlPS, 31, 2018.
Rongkai Zhang, Cong Zhang, Zhiguang Cao, Wen Song, Puay Siew Tan, Jie Zhang, Bihan Wen, and Justin Dauwels. Learning to solve multiple-tsp with time window and rejections via deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 2022.
Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. Graph convolutional networks: comprehensive review. Computational Social Networks, 6(1):1-23, 2019.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. NeurIPS, 34:29476- 29490, 2021.
13

---

Contents of the Appendix
We describe the contents of the supplementary material below:
Appendix A we provide further information on the prior work and related research,
including additional references and links to relevant papers.
In Appendix B we explore applications of our method beyond the MIS problem. Specifically, discuss how our method be applied to the Minimum Vertex Cover (MVC) problem.
In Appendix C
we provide detailed experimental details used in our experiments.
In Appendix we present additional experiments conducted specifically on the MIS problem.
In Appendix we extend our investigations to the MVC problem. We present experimental results benchmarks and discuss the performance and insights gained from the experiments. Appendix provides additional background information on relevant concepts related to the MIS and MVC problems.
In Appendix G present ablation study where systematically analyze the impact of different architecture configurations in our method.
Appendix[H]]dlveee into the broader impact of our work, discussing the potential implications of using our self-supervised approach for CO problems.
Appendix[] [ we provide the omitted proofs of theorems mentioned in the main paper.
Finally, in Appendix []] gain some insight into the decisions of the comparator through the consistency property.
A Additional Links to Prior Work
In Appendix A. we delve into an analysis of multiple deep learning techniques for solving CO
(Combinatorial Optimization) problems, including how different works have addressed the non- continuity of the loss function. Additionally, in Appendix A.2 we provide brief explanation of Dynamic Programming and Monte Carlo Tree Search.
A.1 Deep Learning Approaches for CO
The growing interest in employing machine learning techniques to tackle combinatorial optimization problems has led addressing the task using different neural approaches [Karimi-Manin Mamaghan et al.) 2022, Ma2g2,aaykkinn et al., [021]] Moreover, some works combine elements from classic heuristics with deep learning techniques, like branch-and bound [Gasse al. 2019] and local search [Li et al.) 2018
As mention in Sec. 2 several works continuous relaxation of the loss function. Following the settings of Wang and Li (2023). CO problems consist of assigning values to discrete optimization
variables X- (x:, isiiin (0, 13" i such that an energy (or loss) function FGG, X) minimized or
maximized in X. Since F(G, X) is not continuous, Karalias and Loukas 2020 employs relaxed
probabilistic loss function, which is later refined by Wang al. 2022 by assuming continuous values
and taking the values of F(G,X' X) at the discrete points X. Since some CO problems require instance- wise good solutions, Wang and Li 2023] focuses more on obtaining good initialization instances. Given that certain CO issues necessitate the acquisition of individual-level optimal solutions, Wang and 2023) places greater emphasis on attaining favorable initializations for subsequent instances rather than providing immediate solutions.
A.2 Dynamic Programming
Dynamic Programming is especially effective for solving problems that demonstrate the principle of optimality. This principle states that an optimal solution to a problem can be achieved by recursively finding the optimal solutions smaller subproblems.
Xu al. 2020 utilize DNNs to replace the function responsible for dividing a problem into sub- problems and estimating the optimal decision at each step. Their results demonstrate significant
14

---

reductions in computation time for classical combinatorial optimization problems such as the 'TSP',
compared to the Bellman- Held-Karp algorithm [Bellman 1962].
The work of Yang et al. [0188] addresses the problem of the size of the lookup table, which may require exponential space, used to store solutions of sub-problems in Dynamic Programming. In their work, Yang et al. 2018 argue that it is possible to approximate Dynamic Programming function with much smaller neural network.
The Dynamic Programming Tree (DPT) often employed for solving CO tasks. Each node of the tree represents problem, and its child nodes represent two sub-prue tob-rrobles derived from it. The DPT designed to explore the solution space of a problem similar to Dynamic Programming. but it only considers subset of the possible solutions due to the large size of the solution space. To construct the DPT, a Monte Carlo Tree Search (MCTS) technique (James et al. 2017] is utilized. The MCTS algorithm begins at the root node and navigates the tree add new nodes to the structure. Upon reaching a new leaf node, MCTS employs a simulation to estimate the value of the node. The results of these simulations are subsequently backpropagated up through the tree, updating the node values accordingly.
Due to the reasons stated above, Monte Carlo Tree Search (MCTS) and other tree search methods have been utilized in the context of CO problems as a replacement for pure Dynamic Programming. MCTS is capable of significantly reducing computational complexity as it operates search space. In Xing et al. (2020], MCTS is employed to solve the TSP problem on graphs with maximum of 100 nodes. Additionally, Xu and Lieberherr [2020] employs MCTS to convert CO problems into Zermelo games (Schwalbe and Walker 2001]. and maps the winning strategy of the Zermelo games provide solutions for CO problems.
a smaller
B Beyond Maximum Independent Set
Our proposed method for solving CO problems using DP and GNNs with self-supervised training extends beyond the realm of the MIS problem. While our focus has primarily been on MIS, the underlying framework and techniques can be applied to various other CO settings. In this section, we explore the potential application and adaptation of our approach to address a different problem domain. We will focus on another problem, called the Minimum Vertex Cover (MVC) problem. We will benchmark against various neural approaches. The goal of the MVC problem is the following:
Definition 4. Given a graph G(V, F) find a set of nodes S C V with minimum size such that for each edge (v, u) E E either v E S or u E
Minimum Vertex Cover asks for the smallest set of vertices S such that all edges of G are "covered" by at least one vertex in the set. Dynamic Programming provides similar optimality guarantees as that of Maximum Independent Set described in Theorem The respective optimality guarantees for Minimum Vertex Cover are formally stated in Corollary
Corollary 1. Let a graph G(V, E) E g. Then for any vertex v E V with d(v) 2 1,
[MC((G) = min (G))
where
:= GVV G(V Elu),,(((ub (u, E (ANNNNoeeEE N())) G' is created by removing e from G as well as all the edges incident to neighbors v.
Go : G (ud E No))), ( u)lu E N()))), Go is created from G' by adding the copy nodes ul d'uu E Nww) and the edges (u', u) for all u E NN)) (each vertex u is connected with its copy u'). Go represents the situation where vertex u is not selected in the MVC, but its neighbors are.
G G(V U (o'), E' ((u,e) v)lu E N(e) Uf ,))),, G is created from G by removing all edges incident and adding a copy node o' that is then connected to v. G represents the situation where v is selected to be part of the MVC.
In the trivial case where G is graph with only connected components of two vertices (d(v) < for all E V). the size of the minimum vertex cover is [G] = [E(G)).
15

---

Corollary iis based on the fact that for any node v E V either v or all of its neighbors (u)) lie in the optimal solution. The first case is captured through G₁. Notice that G is constructed by G by removing all the incident edges to E V since they are already covered by c. The new copy node o' added and connected to so as encode that either node v or its copy v' should be selected in the minimum vertex cover of G1- Symmetrically, the graph Go is constructed by repeating the latter process for each u E (V))..
As in Algorithm | graph comparing function CMP (G, G') induces the following recursive algorithm for computing vertex cover. The latter formally described in Algorithm By Corollary in case CMP Mvc G') [MVVC()) > [MVC(G"II then Algorithm always computes minimum vertex cover.
Algorithm 3 Compaaator-IIduuee Algorithm for the MVC problem
1: function A ACMPsve (G(V, E))
Algorithm ACMPwe)(G) takes graph as input
2:
if E d(t) < 1 then
G' is composed of isolated nodes and isolated edges
3:
S+ for each edge (u,v') E E do Su
4:
5: end for return end if
b Select one of the endpoints of each isolated edge
6:
7:
8:
9:
pick a vertex U E V with d(v) 2 uniformly at random.
10:
G' G(V \ {v}, EY ((u, E) u N(v) ALE (())))
11:
Go == UV f ((o) fuf(",
e()) G, G(V [uu, e) ((e',
12:
13:
if CMPMyc(GG, G1) = 0 then
14:
G+ Go
Remove vertex and put it's neighbors in the MVC
15:
else
16:
G+
Put vertex e in the MVC and remove the edges to its neighbors
17:
end if
18:
return A CCMPsve (G)
19:
end function
By adjusting the notion of consistency (see Definition 3) in the context of minimum vertex cover as CMP G*) = 0 and only if E [[A [CMMMP (G) S E [MM wvc (G')]] one can establish that, if CMP MyC is a consistent comparator, A 4CMPPvve (-) always outputs a minimum vertex cover. In Appendix E present experimental results produced after the self-training of consistent in the context of Minimum Vertex Cover.
C Experimental Details
Additional information related the hyper-parameters. baselines, and datasets are depicted in this section.
C.1 Training Setup and Baselines
follows: 96 32, 96 32, and 96 x 32. After this module, 4 linear layers follow, with the following sizes: 96 x 32, 32 x 32, 32 32, and 64 1. Furthermore, the output of the last GEM iteration has skip connection into the last dense layer of the model, which is also why the final layer has 64 input neurons. Every linear layer in the entire network is followed by layer normalization [Ba al.) 2016b). Each model is trained for 300 epochs total with batch size 32 using Adam optimizer [Kingma and Ba 2014] and learning rate of 0.001. We split the graph datasets into 80% for training and 20% for testing, except
Training setup: The sizes of the linear layers each iteration
"Notice that for the MVC, we have a > sign in the function instead of < sign like the MIS. This comes from the fact that the recursive algorithm for the MVC in corollary [ Jimm to find minimum sized set, instead of the maximum like in Theorem
16

---

for COLLAB and RB datasets where the number of test graphs is much bigger than the number of train graphs. From the training data, validation set is constructed by dedicating 20% of the data in the buffer to it. Considering the baseline methods, we trained them for 300 epochs, and in the case of reinforcement learning, for 300 episodes. A precise description of the Hyper-parameten values is reported in T
Baselines: Besides the methods specified in Sec. 6 in Appendix D we employ the IMDB dataset
Morris et al., 2020 and graphs coming from the Erdos-Rent Renyi [Erdós et al. 1960], Barabasi-Aller
Albert and Barabási 2002] and Watts-Strogert [Watts and Strogatz [998] distributions. Moreover, in Appendix E we use two datasets (RB200 and RB500) that resemble the RB dataset employed
in Sec. but the two datasets have different numbers of nodes. As mentioned in Sec. [ and in Appendix we use traditional baselines, such as the Greedy MIS employed in Sec. 2 Greedy MVC employed in Appendix E Greedy MIS iteratively chooses the node with the minimum degree to be part of the independent set and removes its neighbors from the graph, while Greedy MVC considers the node with the highest degree as part of the vertex cover set, still removing the neighbors of the node. We also implement Simple Local Search, which, given time limit, randomly adds node to the independent set and removes conflicting nodes. The largest set in the time period is used as the solution of the algorithm.
Hardware: Any experiment with a reported execution time has been performed on a laptop with Windows 10 and Python 3.10. The device uses Max-Q GPU with 6GB VRAM, and an Intel(R) Core(TM) 17-7700HQ CPU with 2.80GHz clock speed, and 16GB of RAM. Our method is implemented in PyTorch.
NVIDIA GeForee GTX 1060
C.2 Datasets
Two important parameters are considered for the analysis of the datasets: the size and the density of the graphs. The first parameter measured in terms of total number of nodes. The second one reflects how sparse a graph is and it is measured the ratio between the total number of edges of the graph and the total number of edges if the graph would have been complete.
Real-world datasets and RB: Our work utilizes real-worid datasets that simulate social network scenarios, like IMDB, COLLAB and TWITTER. The RB dataset that we employ consists of the same graphs utilized in the research conducted by Karalaaia and Loukas| [202)] whereas the RB200 and RB500 datasets align with those employed in the work by Wang and Li [2033] Notably, RB200 and RB500 were generated by configuring small hyper-parameter p 0.25, making the instances within these datasets challenging, as specified by Waan and Li 2023).
Graph distribution: In Appendix D we conduct testing on well-known graph distributions, specifi- cally the Erdos-Renyi, Renyi, Barabasi-Alber and Watts- Strogatz distributions [Erdös et al. 1960 Albert and Barabási] 2002 Watts and Strogatz 1998]. abbreviated as ER, BA, and WS in Table 4 The objective is to evaluate the performance our model on datasets where the instance densities differ from those of real-world datasets.
The Special dataset has two nodes, and u. which are connected to set of nodes I. The size of set is denoted as n. Moreover, the nodes within are all independent of each other, since there are no connections between any pair of nodes and j within 1. Additionally, all nodes in I are connected to every node in a clique of nodes called C, which has a total of n + a nodes. When employing the Greedy MIS heuristie, nodes u, U, and one node from C are selected as part of the MIS (Maximum Independent Set), while the MIS itself in reality corresponds to I, which has a dimensionality of n. Notice that the Greedy MIS heuristic performs poorly in these instances.
Special dataset:
Table 3: Experimental setting employed in the training process.
Name
Value
Learning rate
0.001
Optimizer
Adam
Output layer size (D)
32
Number of GEM layers (K)
3
Number of fully connected layers (L)
4
Batch size
32
Training epochs
300
17

---

Table Statistics of the employed datasets. For each dataset, reported the average number of nodes and density of the graphs, and the total number of graphs employed for both training and testing (denoted as "Train' and "Test' respectively).
IMDB COLLAB TWITTER
RB
SPECIAL
RB200
RB500 ER/BA/WS
Nodes
19.77
74.49
131.76
216.67
106.89
197.28
540.79
158.10
Density
0.51
0.52
0.205
0.218
0.530
0.205
0.179
0.105
Train
800
600
777
200
160
400
400
400
Test
200
1000
196
400
40
100
100
100
D
Additional Experiments on MIS
Besides the datasets of Table [] we also performed experiments in the IMDB dataset and three known graph distributions: Erdos Renyi, Barabasi Albert and Watts Strogatz. Table Shoos that all methods, except for the random comparator, always achieve optimal results for the MMDB dataset, since the size of the IMDB instances is extremely small, depicted by Table 4 Moreover, is worth noticing that, on the ER dataset, our method outperforms the greedy heuristic in the mixed roll-outs case.
shows
Table 5: Test set approximation ratios (higher is better) on one dataset made with real-world instances (IMDB) and three datasets made by three known graph distributions (ER/BA/WS). We report average approximation ratio along with the standard deviation.
IMDB
ER
BA
WS
Comparator (Normal Roll-outs)
1,000
0.930 + 0.068
0.922 0.089
0.823 + 0.119
Comparator (Mixed Roll-outs)
1.000
0.954 + 0.058
0.942 + 0.055
0.831 + 0.116
Greedy MIS
1.000
0.950 + 0.045
0.959
0.045
0.937 0.058
Random Comparator
0.874 + 0.261
0.584 +: 0.250
0.490 +: 0.251
0.610 + 0.185
Simple Local Search (1Os)
1.000
0.670 +: 0.184
0.533 4 0.189
0.707 + 0.141
SCIP 8.0.3 (1s)
1.000
0.908 + 0.147
0.919 + 0.193
0.926 0.155
SCIP 8.0.3 (5s)
1.000
0.944 + 0.067
01.699 + 0.044
0.977 0.054
Gurobi 10.0 (0.5s)
1.000
0.945 + 0.074
0.916 + 0.128
0.990 1..900=000 0.030
Gurobi 10.0 (1s)
1.000
0.960 + 0.061
0.956
+ 0.101
0.997 #.014
Gurobi 10.0 (5s)
1.000
0.988 + 0.026
0.998 0.014
0.999 + 0.004
E
Experiments on Minimum Vertex Cover
Experiments for the MVC problem are performed over the RB200 and RB500 Xu et al. [2007].
which were specifically designed to generate hard instances. In addition, we evaluate results by comparing them with the methodologies proposed in Erdos' GNN Karalias and Loukas 2020))
RUN-CSP Toenshoff et al. 2019], and Meta-EGN Wang and Li 2023 Specifically, the results presented in Table are sourced from Wang and Li (0033 with the exception of the comparator and Greedy MVC, and all experiments were conducted using the same datasets as in their study. [Wang and 2023].
Among the neural approaches, o similar results for the two datasets, and our model achieves the best result for the RB500 dataset. Moreover, as depicted by the last rows of Table 6 optimal solvers do not always reach the optimal value over the graphs of the datasets, since, as mentioned before, RB instances are known to hard.
Our model, benefiting from dynamic programming techniques, possesses the ability to decompose complex instances into more manageable sub-instances. result, shows good skills in addressing the inherent complexity of the RB200 and RB500 datasets, surpassing other methods in this regard.
18

---

Table Test set approximation ratio (lower better) for different methods on real-world datasets. We present the performance of different algorithms on the minimum vertex cover problem (MVC). For each cell in the table, the average approximation ratio reported together with the standard deviation. The time limit of solvers is reported next to the name. If the standard deviation is not reported, then the algorithm achieves always the optimal solution over all graphs of the dataset. The best performances reported in bold.
Method (L) Dataset (-)
RB200
RB500
CMP
1.031 0.006
1.015 + 0.004
Erdos' GNN
1.031 = 0.004
1.021 = 0.002
Meta-EGN
1.028 = 0.005
1.016 0.002
RUN-CSP
1.124 0.001
1.062 0.005
Greedy MVC
1.027 = 0.007
1.014 0.003
Random CMP
1.063 = 0.027
1.031 = 0.015
8.0.3 (Is)
1.017 = 0.104
1.025 = 0.018
SCIP 8.0.3 (5s)
1.016 0.007
1.011 = 0.003
Gurobi 10.0 (0.5s)
1.009 = 0.006
1.013 + 0.004
Gurobi 10.0 (Is)
1.002 0.003
1.012 0.003
Gurobi 10.0 (5s)
1.000 = 0.001
1.004 0.003
Additional Background Information
In our work, we use Gurobi as matter of comparison for our results. Since Gurobi is an Integer Linear Programming (ILP) solver, we believe it is useful to briefly revise the ILP formulations of the MIS and MVC problems. In particular, given a graph GVV, E) with n = [V], we use binary decision variables X (zi)ision {0, 1)" for each vertex E V such that I; if vertex i is considered as part of the solution and z; = otherwise. In ILP, the goal is to assign values to every æ; variable such that function F(G, X), called energy function, is either maximized minimized under set of constraints.
F1 Integer Linear Programming for the Maximum Independent Set
In MIS, the energy function defined the of every binary decision variable: F(G, X) Σigy Tj. Since every edge (i.j) can have at most one of its nodes in the independent set (otherwise the independent condition is violated), the sum of decision variables of i and is most one:
maximize
Σ xz
iEV
(3)
subject to and
I; + xz S V(i,j) E E {0,1} ViEV.
F22 Integer Linear Programming for the Minimum Vertex Cover
Differently from MIS, the ILP formulation for the MVC consists in minimizing the objective function F(G, X) Σiev I;- Since every edge of the graph has to have at least one of the two nodes in the vertex cover set (otherwise the edge wouldn't 't be covered), the sum of the decision variables of the two nodes defining the edge has to be greater (or equal) to one:
minimize
Σ 3i
SEV
(4)
subject to and
24 Iz 21 V(i EE
24 E {0,1) V.E..
19

---

G
Ablation Study
In this section, we perform an ablation study on several parameters of the comparator function (without using mixed roll-outs) the COLLAB dataset. The following parameters will be tweaked:
D: The dimensionality of the initial node embeddings, and the output size of the layers in the network.
K: The number of iterations in the Graph Embedding Module.
L: The number of fully connected layers in the network.
We experiment linearly with the following parameters: D E [8, 16,36,2444 48, 64), K E [1, 5,,
and I. E [2,3, 4, 5). with base configuration of D 32, K 3, and I, 4. This means that when testing with D 48, the model configuration will be D 48, K 3, and L 4. The meaning of these parameters can found in greater detail Sec. 4.2
All models were trained for 200 epochs, with the experiments performed on a single GPU with 6GB RAM.
Table Model Performance for a different value of D. The best performance highlighted in bold.
Parameter (D)
8
16
32
48
64
Model Performance 0.976 + 0.053 0.972 + 0.050 0.990 + 0.049
0.980
0.055
0.984
0.048
Table 8: Model Performance for a different value of K. The best performance is highlighted in bold.
Parameter (K)
1
2
3
Model Performance 0.912 - 0.097
0.944 + 0.068
0.990 = 0.049
0.992 + 0.037
0.960 + 0.059
Table 9: Model Performance for different value of L. The best performance is highlighted in bold.
Parameter (L.
2
3
4
Model Performance 0.922 + 0.084 0.987 + 0.057 0.990 + 0.049 0.993 + 0.046
From Tables we can see that value of D = 32, K = 3, and L = 4 is reasonable choice for the model architecture, also taking into account runtimes during inference for model with smaller parameters. Interestingly, the model performance starts to degrade for K = 5, possibly due over-smoo..ing.
H Broader Impact
Designing neural networks for combinatorial optimization (CO) problems is still in its infancy, and as such there are lot exciting questions. Nonetheless, delving even more in this direction might potentially impact our society. Important fields like medicine biology require the solution of CO problems in a short time since the execution time can be critical for the health of a patient. Therefore, tackling CO problems with deep learning techniques can bring important benefits society, but also be used for malicious purposes. Therefore, we do encourage the community to consider those challenges and perspectives.
I
Omitted Proofs
Theorem Let a graph G(V, E) E G. Then any vertex E with d(v) 2 1,
MIS(G)) max (MSS (G/N(+))) (MIS(G/(U))
20

---

Proof. Let G(V, E) be graph and MIS(G) be its maximum independent set. We want to show that for any vertex V with d(v) 2 the size of MIS(G) can be obtained by either removing v or removing its neighbors. ( (wv).
Consider cases:
V E MIS(G)
In this case, if remove M(v) from G, the resulting graph is denoted G' G (o)) Since the neighbors of v cannot be in the maximum independent set, removing it does not affect the size of MIS(G). Therefore, MIS(G) MIS(G").
& MIS(G)
In this case, we can remove from G to obtain the graph G' G \ {v}. Since is not in the maximum independent set, removing it does not affect the size of MIS(G). Therefore, MIS(G) = GT.
By considering these two cases, we have shown that for any vertex v E V, the maximum independent set MIS(G) can be obtained by either removing v or removing its neighbors N(v). Thus, we can express the size of the maximum independent set as follows:
MIS(G)) = max (MSS (G/N(e))), MIS(CG/))))
Theorem Let consistent comparator CMP G G 1). Then the algorithm ACMI' (-) always computes a Maximum Independent Ser, E [ ACM (G) = |MTS(G)) for all G e g.
Proof. Let us consider consistent comparator CMP. We will establish Theorem on the number of edges i.
2
with an induction
Induction Basis (i 0): Let G(V, E G[0] then CMP (G)= =V MIS(G).
Induction Hypothesis: ||| [|ACMM] (G) = [MS(G)) for all G GDD with j s i.
Induction Step: Let G Gli + 1] and consider a node v with degree d(e) > 1. Con- sider also the graphs Go == G/(u} and G1 == (o)) Both Go and G1 admit less than edges and thus by the inductive hypothesis, E [MMP [[.))P((Go]]]]
[MTS(Go) and E [[ACMP (G1)] = [MS((G)). Hence CMP(G,, G₁) if and only if |MIS(Go) MTS(( As result, |ACMP(() max (IM)S(Go)) [MIS(G,)]) and Theorem implies that (ACMP()). = [MI(GG)
J Additional Experiments on Consistency
In an attempt to gain insight into the decisions of the comparator, we measure something that we refer the consistency value of a comparator. The consistency of comparator is the proportion of graph pairs in which the equation of consistency from definition is fulfilled.
Fig.Assoww shows the consistency values as the training progresses for three different benchmark datasets. Overall, the consistency curves have an increasing behavior, indicating an increase in the consistency of the decision that comparator makes as training progresses.
21

---

Consistency of the comparator for three datasets
0.975
0.950
0.925
consistancy
0.875
0.850
0.825
COLLAB
0.800
TWITTER
RB
0.775
10
20
40
iteration
Figure 3: The figure highlights the behavior of the consistency of the comparator for the three datasets: COLLAB, TWITTER, and RB. The consistency (y-axis) represents the confidence of the comparator during the generation of the recursive tree. A consistency value close to 1 indicates high confidence the comparator, Moreover, the consistency is calculated during the training process at the end of every iteration (x-axis), where iteration corresponds to total of 10 epochs. The consistency value associated with iteration 0 is obtained at the beginning of iteration and indicates the consistency of the random comparator.
22


Reviews:
[{"review_id": "ISyIbgaUhJ", "reviewer": "Reviewer_rVy4", "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.", "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?\n- Q2: Line 22-23: How do you circumvent this difficulty? Please be explicit in the introduction.\n- Q3: Algorithm 1: Please emphasize this is a randomized algorithm.\n- 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.\n- Q5: Algorithm 2 Line 5: Where is $G_{init}$ used?\n- 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”.\n- 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”.\n- Q8: Line 316-317: What do you mean by “core modules”?\n\n[1] Yehuda et al. It’s not what machines can learn, it’s what we cannot teach. ICML 2020.", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n- 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.\n- 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.\n- 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.\n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer rVy4 for their thoughtful feedback. We address their concerns below:\n\n\n> W1: Is dynamic programming appropriate for this paper?\n\nMIS is a problem with overlapping subproblems - given the maximum independent set of the sub-graphs $G/\\{u\\}$ and $G/\\{N(u)\\}$, one can directly find the maximum independent set of G. Notice that the computing MIS on $G/\\{u\\}$ and $G/\\{N(u)\\}$ are overlapping subproblems since $G/\\{u\\}$ and $G/\\{N(u)\\}$ share both edges and nodes. That is the reason we used the term Dynamic Programming. That being said, we are open to suggestions for improving the clarity of our work.\n\n____\n\n\n> W2: Randomized nature of the inference algorithm\n\n\nThank you for the remark. The randomized version of our inference comes from the fact that at each level of the recursion, the under examination node is sampled uniformly at random. In our revision we will further emphasize the randomized nature of our approach as well as its importance.\n\n____\n\n> 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  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.”\t\n\nThe reviewer is right, the time complexity of our algorithm is $O(n^3)$ in the worst case. In the revised version of our work we discuss the time-complexity of our method in detail. In the experimental evaluations we used the exact same datasets of the previous DNN approaches for MIS at which our method performs similar or even better performance with respect to the running time (see s/g in Table 1). The main scope of this work is how to blend ideas from theoretical computer science with neural network approaches. Concretely, we aim to investigate how to couple classical algorithmic design techniques with deep learning models. Scaling our method as well as the previous DNN approaches to graphs of millions of nodes is an interesting and important future research direction. We will discuss this in the final version. \n____\n> W4:  Is it possible to avoid  dense propagation in the GNN?\n\nWe appreciate the recommendation from the reviewer. Inspired by this, we conducted the related experiment and verified that the complexity without the anti-neighbors is lower, but the performance deteriorates. The results in Table 1 (in the 1-page pdf) indicate how the performance without the anti-neighbors (AN) deteriorates. We will include the experiment in the revised version.\n____\n\n\n### Questions\n\nQ1: We first remark that using data sampled from a distribution of “easier instances” with respect to the worst-case instances of the CO setting of interest, is not necessarily futile. In fact the key motivation of the learning to optimize literature is that in many cases, the instances of interest admit an easier combinatorial structure. Secondly, our approach does not lie in the considered setting of [1] since it uses a polynomial-time sampler that is not static but evolves over time as the weights of the GNN model evolve (notice that our dataset is augmented according to the choices of the model at each epoch).\n\nQ2: We circumvent the difficulty of annotating such data with our DP/bootstrapping approach of self-annotation through our GNN-induced algorithm. In the revised version of our work we will further elaborate on this part.\n\nQ3-Q4: We will fix those, thank you for the suggestion.\n\nQ5: $G_init$ is just a randomly sampled graph from the distribution $\\mathcal{D}$.\n\nQ6-Q7: Thanks for the suggestion, we will update to “Better MIS estimation” and “Mixed roll-out estimator”.\n\nQ8: We appreciate the attentive reading of the reviewer; we meant that we used only basic modules and not more advanced architectures, e.g. GAT, etc. We will rephrase it to `basic components’ to avoid any confusion. \n\nWe are happy to address any other concerns the reviewer rVy4 might have.\n"}, {"review_id": "FLlsiigf8F", "reviewer": "Reviewer_qbTV", "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.", "questions": "None.", "limitations": "No the limitations are not adressed, see the weaknesses.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "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. \n\n1. I retract the first point in the bullet list below, it is indeed incorrect as the authors point out in the rebuttal. \n2. 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. \n3. 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. \n4. I also retract W4. \n5. It is a weakness that the paper doesn't discuss this in it's current form.\n6. 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.\n7. Units should still be explained. One prior work doesn't make it standard enough to not mention it.\n8. 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.\n9. 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.\n\nThe paper has substantial weaknesses that prevent acceptance at this time in my view:\n\n1. 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. \n2. 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).\n3. 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.\n4. 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)|.\n5. 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.\n6. 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.\n7. Table 1 uses an unexplained unit of s/g.\n8. 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.\n9. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer qbTV for their feedback. We address their concerns below:\n\n> Q1: MIS cannot be classified as NP-hard or anywhere in that complexity hierarchy\n\nWe respectfully disagree with the reviewer. Maximum independent Set (MIS) is an NP-hard problem (e.g. see [D] published in ICML’20).\n\nIndeed MIS does not belong in NP since it is not a decision problem. However, contrary to NP-complete problems, NP-hard problems do not necessarily lie in NP. Up next we quote [A], that is the standard textbook on approximation algorithms.\n\nP-459: “We conclude this section by defining the term NP-hard, which can be applied to either decision or optimization problems. Roughly speaking, it means as hard as the hardest problem in NP ”\n\nP-459: Definition B.9 (NP-hard): A problem A is NP-hard if there exists a polynomial-time algorithm for an NP-complete problem B when the algorithm has oracle access to A (notice that is A not required to belong in NP.)\n\nMaximum Independent Set is not only NP-hard but in fact it is highly inapproximable. More precisely, For any $\\epsilon>0$ there is no $1/n^{1-\\epsilon}$−approximation polynomial-time algorithm for Maximum Independent Set unless P=NP [A-C]. As a result, solving MIS (even approximating it) is a computationally intractable task. Under this perspective, we do not understand why the following lines are plain incorrect.\n\nLine 181 -> “Since  MIS is an NP-Hard problem, annotating such data comes with an insurmountable computational burden”.\n\nLine 21 -> “Annotating 20 such data requires the solution of a huge number of instances of the CO, hence such supervised learning approaches are computationally infeasible for NP-hard problems”.\n\n[A] The Design of Approximation algorithms, Williamson et al. 2009\n\n[B] Linear degree extractors and the inapproximability of max clique and chromatic number, Zuckerman et al. 2007\n\n[C] https://webdocs.cs.ualberta.ca/~zacharyf/courses/approx_2014/notes/nov26-675.pdf \n\n[D] Learning What to Defer for Maximum Independent Sets, Ahn et al. 2020\n____\n> Q2: Various statements are imprecise or plain wrong\n\nThere could be a misunderstanding here, so please let us paste the actual line 136: \n\n“However, there might exist a reasonable graph comparing functions that i) are efficiently computable ii) lead to near-optimal solutions”. \n\nThus, we do not claim/prove that such a graph comparing function exists. The goal of this paper is to derive such a GNN-based graph comparing function that performs well (producing large independent sets) in graphs of interest.\n\nIn Remark~4 we write that the non-convex problem of Eq 2 can be treated with a first-order method such as SGD that in practice performs well in the non-convex optimization settings arising in the context of ML. The latter is verified by our experimental evaluations indicating that the self-supervised approach improves over training. Beyond the aforementioned clarifications, we are open to suggestions from the reviewer to improve the clarity of our writing.\n____\n> Q3: Computational complexity\n\nIn the revised version we will explicitly write the worst-case computational complexity of our inference algorithm that is indeed O(n^3). In Table~1 we compare the running time of our method with respect to previous deep learning approaches as well as Gurobi and SCIOPT. Note that s/g stands for seconds/graph and was used in previous works as well, e.g. [1, 2]. We also remark that the worst-case complexity of Gurobi and SCIOPT is exponential in n since otherwise $P = NP$.\n____\n> Q4: Missing a +1 in Theorem 1\n\nLet us first emphasize that Theorem 1 is correct (a +1 is **not** missing).\n\nNotice that |MIS(G/{v})| refers to removing the node from G and thus $v$ will not be contained in the produced solution (that is a subgraph with isolated nodes). The case where $v$ is part of the produced solution is captured in |MIS (G/N(v))| at which all neighbors of $v$ are removed and thus $v$ will become an isolated node that will never be removed in the recursive calls.\n____\n> Q5:  Variance in estimating the experimentation\n\nThe variance of the process is at most $n$ since the random variable can take value at most $n$. In our experimental evaluations we used 5 roll-outs which is enough to sufficiently reduce the variance of the process.\n____\n> Q6: Not acceptable practice to remove the RUN-CSP baseline\n\nWe respectfully disagree with the reviewer. We use the open-source code (of the authors) for RUN-CSP model. When this code is trained on RB and COLLAB datasets, it obtains a poor performance. Therefore, instead of misleading the readers with a low performance, we prefer to indicate that we obtain an unexpected performance, such that other researchers can validate or refute our claim. If the reviewer has any recommendation on the topic, we will gladly change the phrasing to better reflect our case. \n____\n> Q7: Table 1 uses an unexplained unit of s/g\n \nSeconds/graph; we will clarify this. This is standard notation in deep learning papers, such as [1].\n____\n> Q8: Justification for benchmark datasets\n\nIn our experimental evaluations we used the benchmarks used in the previous DNN approaches, e.g. [1], so as to provide a fair comparison. \n____\n> Q9: Comparison with classical optimization solvers\n\nWe remark that our method achieves the best performance across previous DNN approaches for MIS that have already been published in top-tier conferences as NeurIPS. We agree with the reviewer that learning to optimize is at an infantry level and in most CO settings of interest is outperformed with standard solvers and algorithms that have been tough developed for decades. We believe that the latter does not lower either the value of our work or the value of learning to optimize line of research.\n\nWe are happy to address any other concerns the reviewer qbTV might have.\n\n[1] Karalias, Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. NeurIPS, 2020\n"}, {"review_id": "QMF7CfqDCi", "reviewer": "Reviewer_YVwa", "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.", "questions": "None", "limitations": "Please check the weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "\nIt is interesting and innovative to address the MIS problem using GNNs in a self-training manner.\nThe proposed method is effective and efficient for solving the MIS problem.", "weaknesses": "\nThe following improvements could enhance the experiments:\n\n1. 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.\n\n2. 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.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer YVwa for their feedback. We address their concerns below:\n\n\n> Q1: Baseline comparisons\n\nIn Line 74, we present the various DNN approaches for various CO settings and adapting those to MIS might not be trivial. In our experimental evaluations we compare with the existing approaches for MIS. If the reviewer believes there is a relevant baseline that we should include in the comparisons, we are happy to consider it. \n____\n\n> Q2: Evaluations on large-scale graphs\n\n\nWe are thankful to the reviewer for the remark and the references. Let us clarify why the presented methods are not directly comparable with ours and the other deep-learning approaches that we compare against.\n\nFirstly, we remark that [Schuetz et al., 2022; Wang and Li, 2023] present only results for $d$-regular graphs for some small values of $d$ (3 and 5). Despite the fact that these graphs admit a large number of nodes, the number of edges scales only linearly with $n$ which is the reason why their methods can scale. This is a different setting to ours, where we do not make such assumptions about the graph distribution. Furthermore, notice that both [Schuetz et al., 2022; Wang and Li, 2023] use GNNs meaning that the inference algorithm admits at least $O(n^2)$ complexity for dense graphs. \n\nWhat is more, let us clarify why the learning of these approaches also differs from the aforementioned deep-learning approaches. [Schuetz et al., 2022] optimize the parameters of the GNN providing a fractional MIS-solution and then use a standard randomized rounding to convert to an integral one.  However, they *train* the GNN for each new graph separately during inference (or in other words, the parameter optimization of the GNN is part of the inference algorithm). The latter pipeline is very similar to the classical *relax and round* approach that has been used in the approximation algorithms for years (see section 4,5 and 6 in [1]). On the other hand [Wang and Li, 2023] do not derive a new learning algorithm but rather use their approach to tune the classical *greedy algorithm* whose practical favorable performance has been identified over the years.\n\n[1] The Design of Approximation Algorithms, Williamson 2009\n\n____\n\n> Q3: Model training timing\n\nWe are thankful for the recommendation by the reviewer. We ran the training process on the TWITTER dataset for 1000 iterations. Concretely, given the constructed dataset, we measured the time it required for forward + backward passes with our model and the EGN model from [1]. The results in the table below showcase that our method is quicker for this dataset. \n\n| Model | Twitter (seconds/graph) |\n|-------|-------------------------|\n| Ours | 0.45 |\n| EGN | 1.62 |\n\nAlthough the TWITTER dataset does not contain graphs with thousands of nodes, our method should scale with a similar rate to that of prior deep learning approaches for dense graphs.\n\n\nWe are happy to address any other concerns the reviewer YVwa might have.\n"}, {"review_id": "WyBCT9W3Vv", "reviewer": "Reviewer_b8RC", "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.", "questions": "1. Have you tried using any other GNN architectures (GIN, GAT, Erdos, Graph Transformer, ...) for the heuristic step?\n2. Are the anti-neighbors needed? How is the performance without (this would help in lowering the overall complexity)? \n3. How many rollouts are needed for the results?\n4. 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.\n5. Why is SPECIAL missing from Table 2?\n6. Is RB or TWITTER really out-of-distribution for COLLAB? Maybe those datasets are very similar in distribution.\n7. What about using only the greedy rollout? \n8. 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?\n9. 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.\n10. Do you have any insights into the GNN decisions?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "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).\n2. The approach is clearly laid out and easy to follow.\n3. 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.\n2. The main novelty seems to be the use of a GNN for the decision step in the algorithm.\n3. 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.\n4. 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?\n5. Greedy baseline outperforms the proposed approach on 2/4 datasets.\n6. The results are not very convincing for MVC.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer b8RC for their feedback. We address their concerns below:\n\n> W1: Unclear impact of the paper and applicability to other CO problems\n\nWe agree with the reviewer that extending to other CO problems is not trivial, but we respectfully disagree on the significance of our work. The main motivation of our work is to investigate Dynamic Programming, a well-established technique, in combination with deep learning models. We believe that our results clearly indicate how fertile this coupling is and is of interest for the ‘learning to optimize’ audience of NeurIPS. This is also clearly identified by R. v2kw.\n____\n\n> W2: No novelty on GEM \n\nWe are not aware of any previous work using the latter aggregation mechanism. In case the reviewer can provide us with the specific reference we are happy to provide the due credits.\n____\n> W3: Scalability to larger graphs\n\nThe time complexity of our algorithm is $O(n^3)$ which indeed poses limitations on applying it to very large graphs . However we remark that it requires similar (or even better) running time of previous DNN approaches (see Table 1 and 2 where s/g stands for seconds per graph). We emphasize that this runtime is even obtained with code written on PyTorch modules and we firmly hold that further implementing our model with low-level libraries could further boost the runtime performance. For example, at each step, the adjacency matrix of the graph must be modified by removing either the selected node or its neighbors. This is an expensive operation when using NetworkX (which is a standard library). Furthermore, by batching graphs in order to allow for GPU-based parallelization, which is not currently done, we expect to significantly improve training and inference results of the model.\t\n____\n> W4: Performance when compared to the greedy baseline\n\nBeating the greedy heuristic for MIS with deep learning methods that do not use any domain knowledge on the problem is a challenging task. We remark that the latter holds for all previous learning approaches out of which our method presents the best performance. We believe that the latter does neither lower the value of our work nor the value of the learning to optimize line of research, that it is a way more recent research direction with respect to the human-design heuristics.\n____\n\n> W5: Performance on MVC\n\nThe focus of this work is on MIS (which is already declared in the title of the paper). Nevertheless, we make an effort to demonstrate the extension of our work to other CO tasks, such as MVC. We do believe that with an improved architecture (e.g. as in the next question), we could further improve improvements in the MVC, but even our approach from MIS readily achieves a decent performance in MVC.\n____\n\n> Q1: Can you use other GNN architectures?\n\nYes, but we have not tried in detail, since the focus of this work is not the GNN architecture per se. We believe this is a future direction for our work, which we will explicitly mention in the final version.\n____\n\n> Q2: Role of anti-neighbors\n\nWe appreciate the recommendation from the reviewer and agree about the comment regarding the computational complexity. Inspired by this, we conducted the related experiment and verified that the complexity without the anti-neighbors is lower, but the performance deteriorates. The results in Table 1 (in the pdf) indicate how the performance without the anti-neighbors (AN) deteriorates. We will include the experiment in the revised version.\n____\n\n> Q3: How many rollouts are needed for the results? \nTable 3 (in the pdf) reports the approximation ratio for different rollout values. Notice that the optimal rollouts for both COLLAB and TWITTER belong in the range of 5 or 10.  \n____\n\n> Q4: 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.\n\nIndeed, it is a reasonable tweak that we have not considered since we wanted to investigate the performance of the vanilla version of the DP-based learning approach. We will explicitly mention this in the final version as a future step.\n____\n\n> Q5: Why is SPECIAL missing from Table 2? \n\nWe notice that RB and SPECIAL distributions share common patterns. For instance, they have big clusters of fully-connected nodes, but clusters are almost independent. Therefore, this is adding redundant information.\n____\n> Q6: Is RB or TWITTER really out-of-distribution for COLLAB?\n\nThe graph distributions between the three datasets are quite different. Please check Table 2 in the pdf. \n____\n> Q7: What about using only the greedy rollout? \n\nIt achieves similar performance.\n____\n> Q8: Do you run greedy multiple times or a single rollout?\n\nWe run greedy multiple times exactly as the reviewer suggests.\n____\n\n> Q9: Degree-weighted random CMP baseline  \n\nWe tried the recommendation of the reviewer, but, unfortunately, it did not produce a good result. The result of the pure random CMP over the SPECIAL graphs is 0.225 +- 0.279 while the result of the degree-weighted random CMP is 0.172 +- 0.192. Even if the chosen node is not the lowest degree one, the comparator has to make a choice. This choice is wrong 50% of the times, since the comparator is random, producing a low approximation ratio.\n____\n> Q10: Insights into the GNN decisions\n\nWe analyze the GNN decisions by calculating the consistency value which is the percentage of the graphs pairs at which the equation of Definiton 3 holds (consistency). Fig. 1 in the pdf shows the consistency values as training proceeds. Overall, the **consistency curves have an increasing behavior, indicating an increase in the comparator consistency as training goes on**.\n\nWe are happy to address any other concerns the reviewer b8RC might have.\n"}, {"review_id": "I6SwfVQVZV", "reviewer": "Reviewer_T1ds", "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.", "questions": "See in weaknesses.", "limitations": "Limitations are mentioned. Negative societal impact is not applicable.", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The notations and presentation are clear.\n2. 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.\n2. 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.\n3. The computational complexity/overhead should be discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer T1ds for their feedback. We address their concerns below:\n\n> Q: Include a more detailed explanation on why the learned graph comparator will be consistent.\n\tNotice that the optimization problem of Eq. 2 effectively asks for more and more consistent comparators. \n\nNevertheless, to provide an empirical demonstration, we opted to conduct the following experiment. We are thankful to the reviewer for the suggestion. We analyze the GNN decisions by calculating the consistency value which is the percentage of the graphs pairs at which the equation of Definiton 3 holds (consistency). Fig. 1 in the pdf shows the consistency values as training proceeds. Overall, the **consistency curves have an increasing behavior, indicating an increase in the comparator consistency as training goes on**.\n\n\nWe are happy to address any other concerns the reviewer T1ds might have.\n"}, {"review_id": "M5sygHgYyO", "reviewer": "Reviewer_v2kw", "summary": "Maximum Independent Set:\nA 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. \n\nTheorem 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! \n\nGNNs for MIS. The approach is incremental. \nA) Build comparator CMP based on theorem 1, for determining whether to graphs have approximately MIS size.\nB)  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. \n\nSelf-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. \n\nExperiments. Compare the proposal with greedy methods. Usually greedy methods works very well but in some graphs. The method seems to generalize a bit. \n\nI 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\nnew deep-learning-oriented approaches for demanding CO problems”.", "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. ", "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. ", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A nice paper for illustrating the use of GNNs in CO problems through self learning, specially in NP-Hard Problems. \nNice 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. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer v2kw for their feedback. We address their concerns below:\n\n> Q: “How do the parameters of the $CMP_{\\theta}$ evolve? How far/close are they returning consistent/inconsistent responses? In other words, use the analysis of these parameters to diagnose how hard the problem is for different graphs.”\n\nWe are thankful to the reviewer for the suggestion. We analyze the GNN decisions by calculating the consistency value which is the percentage of the graphs pairs at which the equation of Definiton 3 holds (consistency). Fig. 1 in the pdf shows the consistency values as training proceeds. Overall, the **consistency curves have an increasing behavior, indicating an increase in the comparator consistency as training goes on**.\n\n\nWe are happy to address any other concerns the reviewer v2kw might have.\n"}]

Author rebuttal:
Dear reviewers, 

We are thankful for your time and effort to handle the paper. Please find enclosed the single-page pdf. We respond to each question of the reviewers below. 

Meta-review: The paper has received reviews (after rebuttal) that consensually vote for acceptance. Reviewers state that the presented approach is nice and novel with solid experimental results. The AC follows this recommendation.
Decision: Accept (poster)