Learning Combinatorial Node Labeling Algorithms
Authors: Lukas Gianinazzi
Maximilian Fries
Nikoli Dryden
Tal Ben-Nun
Maciej Besta
Torsten Hoefler
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph learning
reinforcement learning
combinatorial optimization

Abstract: We present the combinatorial node labeling framework, which generalizes many prior approaches to solving hard graph optimization problems by supporting problems where solutions consist of arbitrarily many node labels, such as graph coloring. We then introduce a neural network architecture to implement this framework. Our architecture builds on a graph attention network with several inductive biases to improve solution quality and is trained using policy gradient reinforcement learning. We demonstrate our approach on both graph coloring and minimum vertex cover. Our learned heuristics match or outperform classical hand-crafted greedy heuristics and machine learning approaches while taking only seconds on large graphs. We conduct a detailed analysis of the learned heuristics and architecture choices and show that they successfully adapt to different graph structures.

Under review as a conference paper at ICLR 2023
LEARNING COMBINATORIAL NODE LABELING ALGORITHMS
Anonymous authors Paper under double-blind review
ABSTRACT
We present the combinatorial node labeling framework, which generalizes many prior approaches solving hard graph optimization problems by supporting prob- lems where solutions consist of arbitrarily many node labels, such as graph coloring. We then introduce neural network architecture implement this framework. Our architecture builds on a graph attention network with several inductive biases to improve solution quality and is trained using policy gradient reinforcement learning. We demonstrate our approach on both graph coloring and minimum vertex cover. Our learned heuristics match or outperform classical hand-crafted greedy heuristics and machine learning approaches while taking only seconds on large graphs. We conduct a detailed analysis of the learned heuristics and architecture choices and show that they successfully adapt to different graph structures.
INTRODUCTION
Graph problems have numerous real-world applications, ranging from scheduling problems (Marx, 2004) and register allocation (Chaitin, 1982; Smith al., 2004), to computational biology (Abu- khzam et al., 2004). However, many useful graph optimizations problems are NP-hard to solve (Karp, 1972). This has spurred a variety of approaches, from greedy heuristics (Brélaz, 1979; Papadimitriou & Steiglitz, 1982; Matula & Beck, 1983; Avis & Imamura, 2007; Delbot & Laforest, 2008) to integer linear programming (Graver, 1975). More recently, machine learning approaches have shown increasing promise (Dai et al., 2017; Kool et al., 2019; Li et al., 2018; Karalias & Loukas, 2020).
From a structural point of view, many graph problems fall into one of three classes depending on the type of their solution: Problems that ask for (1) subsets of vertices, (2) permutations of vertices, or (3) partitions of vertices into two or more sets. Most work has focussed on either the first two (Dai et al., 2017), or just one of the three (Bello et al., 2017: Li et al., 2018; 18; Kool et al., 2019; Karalias Loukas, 2020; Manchanda et al., 2020; Cappart et al., 2020; Drori et al., 2020; Ma et al., 2020). Existing machine learning methods for the first two types of problems, such as S2V-DQN (Dai et al., 2017), do not casily generalize to cases where the number labels is not known in advance. Many important and challenging problems, such graph coloring (Marx, 2004; Myszkowski, 2008; Bandh et al., 2009), require that vertices be partitioned into an unkown number of sets.
To address this, we present the combinatorial node labeling framework ($2), which generalizes prior approaches (Fig. 1), and supports many problems, including minimum vertex cover (Onak et al., 2012: Bhattacharya al., 2017: Ghaffari al., 2020), traveling salesman (Dantzig et al., 1954; Garey& & Johnson, 1990), maximum cut (Karp, 1972), and list coloring (Jensen et al., 1995). These and many other ($D). problems can all be framed as iteratively assigning a label to nodes, in some order. We then introduce a neural architecture, GAT-CNL, to learn greedy-inspired heuristics for such problems ($3). We use policy gradient reinforcement learning (Sutton & Barto, 2018: Kool et al., 2019) to learn a node ordering and combine this with a fixed label rule to label each node according to the ordering. We show that for the chosen label rules, there still exists an order that guarantees an optimal solution. By using policy gradients, we can construct both deterministic greedy policy, as well as a probabilistic policy where sampling boosts the solution quality. To improve performance, we incorporate two inductive biases: spatial locality, where labeling node only impacts the weights of its neighbors; and temporal locality, where node selection is conditioned only on the previously labeled node, summary of prior labelings, and global graph context (Figs. 2 and 3).

---

Under review as a conference paper at ICLR 2023
Node Labeling
in edges vertices
Graph
S2V-DQN
edges
Graph
Ours: GAT-CNL
n vertices
Example looke
Average Time
Giggn coloring (64.3)
our
S2V
GAT
Encoder
Encoder
Learnable
Set
(D6 seaeea 2857 aoaiacals
Vertex embedding
Vertex embedding
Exumple taska:
Next vertex
Next vertex
State Embedding
State Embedding
Next label
No labels
Permutation
m/n
feits at ane stal ane
times
times
Cap aesaritt al wass eivaietc doo,,
Next
Exampli kasks:
TSP Longestputt
Decoder
Greedy
Probobilistic
Decoder
vertex
Label Assignment
m/n
m/n
Figure I: Left: Venn diagram of tasks solvable with the set, permutation, and node labeling frameworks. Node labeling generalizes existing frameworks and allows solving additional tasks. Center & right: Comparison of our architecture with S2V-DQN (Dai et al., 2017). We add label assignment step, allowing us to solve new problems. Further, the average time for picking the next vertex is significantly reduced, such that the total number of arithmetic operations is now linear in the size of the graph.
We evaluate our approach ($4) and demonstrate significantly improved performance for neural graph coloring (GC) and find near-optimal solutions for minimum vertex cover (MVC). We additionally study the runtime of our models, conduct comprehensive ablation studies, and provide qualitative analyses of the learned heuristics, showing they adapt to the properties of the input graph.
Related work. We now review key related works. Figure (left) provides comparison of node labeling with other frameworks.
Supervised learning. The fundamental downsides of supervised learning for combinatorial opti- mization are twofold: First, it can be difficult to formulate problem in supervised manner, since it might have many optimal solutions (e.g., GC). Second, even if the problem admits direct supervised formulation, we still need labeled data for training, which can be hard to generate and relies on an existing solver. In particular, supervised learning cannot easily be used for problems that have not been studied before. Advantages of supervised learning are its sample efficiency and that it can lead to overall better results. Recent approaches like Joshi et al. (2019) and Manchanda et al. (2020) obtain good results for influence maximization (IM) and the traveling salesman problem (TSP), respectively. Both approaches use supervised learning. For IM, the approach of Manchanda et al. (2020) shows promising results on graphs much larger than those seen in training. For TSP, the approach of Joshi et al. (2019) is very efficient but does not generalize well to graphs larger than those seen in training. Li al. (2018) also use supervised learning and produce good results on minimum vertex cover (MVC), maximum independent set, and maximal clique.
Unsupervised Learning. To apply unsupervised learning, is necessary to formulate a differen- tiable surrogate loss. There have been approaches for several specific combinatorial optimization problems (Nazi et al., 2019; Amizadeh et al., 2019; Tönshoff et al., 2019; Yao et al., 2019) and there has been progress to create framework for the derivation of trainable losses (Karalias & Loukas, 2020). Still, significant insight into a problem is required to design suitable loss functions.
Reinforcement learning (RL). Using RI. only requires a way to represent partial solutions and way to score the cost of a (partial or final) solution. Dai et al. (2017) provide S2V-DQN, a general framework for learning problems like MVC and TSP that is trained with RL. It shows good results across different graph sizes for the covered problems, but is not fast enough to replace existing approaches nor does it handle arbitrary node labels (see Fig. 1). Kool et al. (2019) focus routing problems like TSP and the vehicle routing problem. They outperform Dai et al. on TSP instances of the training size. Unfortunately, their approach does not seem generalize to graph sizes that very different from those used for training. Several other RI. approaches have been proposed and evaluated for TSP (Bello al., 2017; Cappart et al., 2020; Drori et al., 2020; Ma et al., 2020). Barrett et al. (2020) consider the maximum cut (MaxCut) problem. Huang et al. (2019) present a Monte Carlo search tree approach specialized only for graph coloring. These methods do not address the general node labeling framework, but instead model the solution as permutation of vertices (e.g.. TSP, vehicle routing) or a set of nodes or edges (e.g., MVC, MaxCut). Instead, we can represent
2

---

Under review as a conference paper at ICLR 2023
solutions where vertices assigned to unknown and unbounded number of partitions, which is crucial for solving tasks such as graph coloring.
2 COMBINATORIAL NODE LABELING
Many graph heuristics can be phrased as greedy process, where vertices get assigned problem- dependent label one after the other. For example, this label could indicate if the vertex is part of the solution set, its position in a permutation, or its membership in one of many sets. We introduce combinatorial node labeling, which frames many hard graph optimization problems, such as graph coloring (see $D for list), greedy process. This generalizes previous work (Kool al., 2019; Dai et al., 2017; Ma et al., 2020; Drori et al., 2020), to encompass problems where the number of labels is not known in advance and is unbounded (see Fig. 1).
Every node labeling problem can be formulated as a (finite) Markov decision process (MDP), during which nodes successively added so-called partial node labeling until termination criterion is met. In $3, we will present graph learning approach to optimizing such node labeling MDPs.
2.1 PRELIMINARIES
We consider an undirected, unweighted, and simple graph G = (V, b)) with n nodes in V and m edges in E. We denote the neighbors of node v by Nvv). We assume w.l.o.g. that the graph is connected and hence m = f2(n).
node labeling is a function function d' V - L' for subset of nodes V" C V and labels L' C L. A node labeling problem is subject to a feasibility condition and a real-valued cost function f. The cost function maps node labeling to a real-valued cost fc). We require that the feasibility condition be expressed in terms of an efficient (polynomial-tima computable) extensibility test T P(V L) x V x L - {0, 1}. where P denotes the powerset. We say the extensibility test passes when returns 1.
V where S (O.....m). A partial node labeling is a
Intuitively, given a partial node labeling é', a node É V', and label É, the extensibility test passes if and only if c' can be extended by labeling node with é such that c' can be extended into node labeling. Formally, the extensibility test characterizes the set of feasible solutions:
Definition 2.1. A node labeling e is feasible if and only if there exists a sequence of node- label pairs (V1, ...,... (Un, en) such that for all 2 0 the extensibility test T satisfies T([(11. E....., (U,, 4,),, U1+1. (++1 1.
The goal of the node labeling problem is to minimize the value of the cost function among the feasible node labelings. For consistency, an infeasible node labeling has infinite cost. Next, we present the two node labeling problems on which we focus in our evaluation.
Definition 2.2. A k-coloring of graph = (V, E') is a node labeling e: V - f1,2.... ...2....,k)......... such that no two neighbors have the same label, i..., V(u, v) E c(() # c(u).
The cost function for GC is the number of distinct labels (or colors) k. Given partial node labeling d' : V {1.....k} .) and any vertex-label pair (u, f). the extensibility test passes for (c', v, E) if and only if the extended partial node labeling c' J (v. E) is a k- or (k + 1)-coloring of the induced subgraph G [v]). In particular, the test does not pass when > k 1. The smallest for which there is a k-coloring of G is the chromatic number xG) of G.
Definition 2.3. A vertex cover of a graph G = (V, E) is a node labeling e V + 1) such that every edge is incident to at least one node with label 1, i.c., V(u, v) E E c(u) = 1 VV = 1.
The cost function for MVC is the number of nodes with label 1. Given a partial node labeling : V' + {0, 1} the extensibility test passes for (c', v, E) if and only if the extended partial node labeling d' U (v. E) is vertex cover of the induced subgraph G[V' U {u}].
2.2 NODE LABELING MDP
We show how to construct MDP that models a given combinatorial node labeling problem. Minimizing the cost of the combinatorial node labeling problem is equivalent to maximizing the return of this MDP. In the vast majority of reinforcement learning approaches to solve combinatorial
3

---

Under review as a conference paper at ICLR 2023
graph optimization problems (Kool et al., 2019; Dai et al., 2017; Ma et al., 2020; Drori et al., 2020), a state corresponds to a set or sequence of nodes that are already added to a solution set. Instead, in our setting the state represents partial node labeling. This is why in addition to problems like MVC and TSP, we can also model problems with more than two labels (even when the number of labels is not known in advance). Graph coloring is such problem.
Lemma 2.4. For any node labeling problem, there is an MDP whose terminal states correspond to the feasible solutions with cost equal to the negative return.
We embed the cost function/ f and the extensibility test into the MDP. Note that we do not require a way to measure the cost of partial node labelings. Here, we formulate the state space, action space, transition function, and reward. In $C.1, we finish the proof of Lemma 2.4.
State space. A state S represents partial node labeling. It is set of pairs S = V" x L for a subset =V= Hence, the set of states is the powerset P(V x {0. ..... n)) ) of the Cartesian product of the vertices and labels. Action space. In state S. the set of legal actions are the pairs (v, E) for nodes v and labels & which pass the extensibility test of the problem for the partial node labeling given by S (i.c., T(S, v. () 1). Transition function. In our case, the transition function 'T is deterministic. That is, given the current state S₁ and an action (u, e). (S,,, (v. ()) yields the next state S2+1 S.U U {(v, {)}. Reward. For a terminal state S representing the node labeling c, the reward is - f(c). For all other states, the reward is O.
of nodes V' C V and a subset of labels L C {O..... n.. A state is terminal
A policy is a mapping from states to probabilities for each action. Note that we can turn a probabilistic policy into a deterministic greedy policy by choosing the action with largest probability. Next, we present how to train such a policy end-to-end using policy gradients.
GRAPH LEARNING APPROACH
We present graph learning approach to node labeling, which is inspired by greedy algorithms. Greedy approaches generally trade optimality for improved runtime. A greedy node labeling algorithm assigns a label in (O.....n) n1 to one node after another based on a problem-specific heuristic. Hence, it can be seen as providing (I) an order on the nodes and (2) a rule to label the next selected node.
We focus on learning an order on the nodes and pick label that passes the extensibility test according fixed rule. The following two lemmas show there exists a label assignment rule that ensures the optimal solution can be found for GC and MVC (see $C.2 for the proofs):
Lemma 3.1. For every graph G, there exists an ordering of vertices for which choosing the smallest color that passes the extensibility test colors optimally.
Lemma 3.2. For every graph G, there exists an ordering of vertices for which choosing the label 1 until every edge in G has one of its endpoints labeled with 1 produces minimum vertex cover of G.
We expect similar results can be obtained for most other node labeling problems.
Instead of a handcrafted ordering heuristic, we learn to assign weights to each node and choose the nodes according to their weights. To compute these weights, we introduce a novel spatial locality inductive bias inspired by the greedy heuristics: labeling a node should only affect the weights of its neighbors. As we will show in $4.3, this leads to better test scores compared to the alternatives of updating all or none of the weights when node is labeled. This spatial locality bias is inspired by successful greedy heuristics: The ListRight heuristic for MVC (Delbot & Laforest, 2008) assigns node to the vertex cover based on the assignment of its neighbors. For GC, the DSATUR strategy selects nodes according to their saturation degree (Brélaz, 1979). If new node is selected, only the saturation degree of its neighborhood can change; the others remain unchanged.
3.1 POLICY OPTIMIZATION
We train our node labeling model by policy gradients, specifically REINFORCE (Bello et al., 2017) with greedy rollout baseline (Kool et al., 2019). The advantage of policy gradients over Q-learning is that is has stronger convergence guarantees (Sutton & Barto, 2018). At high level, the algorithm works as follows. We begin by initializing two models, the current model and the baseline model. For each graph in the batch, the algorithm performs probabilistic rollout of the policy. The baseline
4

---

Under review as a conference paper at ICLR 2023
ambadding
Gugh onbedding kgg ne?
Made
Lue sheled node erbokding Jyio lig
Hyght
Lated untoesll 1g Myyes Haae A.
THE Altentonn Weights Change Figure 2: Spatial locality of the decoding. We show how graph is 2-colored using node order c, e, b, d. After labeling node, only neighbors' attention weights change; e-g., when colored, only its neigh- bors b and e receive new attention weights. (We omit the last step where d is colored.)
84 Figure 3: Temporal locality of the state embedding. We show how the state embedding is updated as nodes are colored. The state embedding focuses on the last labeled node, and contains the graph embedding, and embeddings of the last labeled node and its label, which pools the embeddings of nodes with the same label.
Sh.
model performs a greedy rollout. The difference between the two costs determines the policy gradient update. After every epoch, we perform a (one-sided) paired f-test over the cost on challenge dataset check if the baseline model should be replaced with the current model. See $A.2 for more details.
3.2 GAT-CNL ARCHITECTURE
Our architecture, GAT-CNL, consists of an encoder and decoder learn policy specific to the node labeling problem. The encoder learns the local structural information that is important for the problem in the form of node embedding.
The state embedding encapsulates information about the graph itself (enabling the network to adapt its actions the graph), the last node that was labeled and its label, and summary of prior actions (with pooling). This enables the state embedding to have constant size; adding additional nodes provided no benefit (see $4.3). This also serves as temporal locality bias; however, note that the decoder is not Markovian, as it depends on more than just the previous decision.
The decoder uses the node embeddings and the state embedding to select the next node based on attention weights between the node embeddings and the state embedding. After the decoder picks the next node v, the label rule (see Lemmas 3.1 and 3.2) assigns the label & for the node. The policy then takes the action (v, f). Then, the state embedding is updated and the decoder is invoked again until all nodes are labeled. Figure (right) overviews our architecture.
Node features. Each node is associated with input feature vector x.. Our input features consist of a combination of sine and cosine functions of the node degree, similar to positional embeddings (Vaswani et al., 2017). This representation ensures that input features are bounded in magnitude even for larger graphs. We subtract the mean node degree from the degrees on the synthetic dense graph instances.
GAT encoder. We use a hidden dimension of size (unless stated otherwise, d = 64). The input features are first linearly transformed and then fed into a GNN, which produces, for each node v, node embedding h, E Rdd We use a three-layer Graph Attention Network (GAT) (Vaswani et al., 2017: Velickovic et al., 2018: Lee et al., 2019), additive multi- head attention with four heads, batch normalization (loffe& & Szegedy, 2015) with skip connection (He et al., 2016) at each encoder layer, and leaky ReLU activations (Maas et al., 2013).
State embedding. The state embedding allows the decoder to condition its choice based on the graph instance and the partial node labeling. For computational reasons, we ensure it is of constant size. Denote the node labeled in step by (4) and its label by g(t), Then the state embedding consists of three components concatenated together: (1) The graph embedding hG, max- max-pooling over all node embeddings. (2) The node embedding h1 of the last labeled node yf (((-1), (3) The label embedding hgg of the last labeled node's label g(t-1), a max-pooling over the embeddings of all nodes with that label. In the first iteration, we use a learned parameter (0) for (2) and (3). We considered including more than just the last labeled node, but found that this led to worse performance
($4.3). Hence, this induces a temporal bias by focusing on the prior node and nodes with the same label as the last labeled node. See Figure 3 for illustration of the state embedding.
5

---

Under review as a conference paper at ICLR 2023
Local attention decoder. The decoder takes imput the node embeddings generated by the encoder and the state embedding and outputs the next node to label. In each time step t, an attention mechanism between the state embedding 9t and each node embedding h, produces attention weights aL") Here, we introduce a spatial locality bias: labeling a node can only affect the attention scores of its neighbors in the next time step. Let V be the set of nodes already labeled. The attention weight ar for node time step is given by the local decoding. For node e V
C tanh (01 (@ahv) ((xhh)) vi
E (N(((--)) or t
V É ((((t-))
If U E V", then the attention weight is a. = Do. In the first iteration of the decoder, we calculate the coefficients for each node in the graph. As in Bello et al. (2017), we clip the attention coefficients within a constant range [-C, C7. our experiments we set = 10. The learnable parameter matrices are θ RRdx3d and O Raxd We scaled dot-product attention (Vaswani et al., 2017) (instead of additive attention) to speed up the decoding. Finally, for each node v we apply a softmax over all attention weights to obtain the probability pv that node is labeled next. See Figure 2 for visualization of the attention weight computation during decoding.
During inference, our greedy policy selects the vertices with maximum probability. Our sampling policy (for k samples) runs the greedy policy once, then evaluates the learned probabilistic policy k times (selecting node with the learned probability p.), returning the best result.
3.3 NUMBER OF OPERATIONS
We express the number of operations (arithmetic operations and comparisons) of the model during inference parameterized by the embedding dimension d, the number of nodes n and the number of edges m. The encoder uses O(dm + d'n) arithmetic operations and the decoder uses (d arithmetic operations, resulting in (dm + n + d'm) arithmetic operations, which is linear in the size of the graph. To select the action of maximum probability (or sample node), the decoder additionally needs (n²) comparison operations (although this could be reduced to Om m log n) with appropriate data structure). We empirically study the runtime in $$4.1 and 4.2; in practice, the d'm term dominates the runtime for the evaluated graphs until 5000 vertices. In contrast, updating all attention weights after every labeling scales O(n²) (see $B.5).
4 EXPERIMENTS
We evaluate approach established benchmarks for graph coloring and minimum vertex cover, including greedy baselines and machine learning approaches. We focus on other heuristic approaches that return an approximation in polynomial time.
Training. We use three different synthetic graph distributions to generate instances for training and validation (Albert & Barabási, 2002; Erdös & Rényi, 1960; Watts & Strogatz, 1998). We generate 20,000 graphs for training. The graphs have between 20 and 100 nodes. We use Adam with learning rate a 10- (Kingma & Ba, 2015). The effective batch size is B 320, which comes from using batches of 64 graphs for each node count and accumulating their gradients. We clip the L2 norm of the gradient to 1, as done in Bello al. (2017). We selected these hyperparameters after initial experiments on the validation set. Each model took 15-20 CPU compute node hours to train cluster with Intel Xeon E5-2695 and GB memory per node. The overall time spent training was
Table I: Graph coloring results on the Lemos et al. (2019) subset of the COLOR challenge graphs.
Table 2:
Comparison of MVC approaches on dense ER graphs with edge-probability 0.15.
Method
Cost
Wins
Optimal
Method
Cost Approx. Ratio
Classic
Largest First
10.65
50%
45%
Maximal Matching List Right
232.00
1.2486
DSATUR
9.85
65%
50%
225.35
1.1120
Smallest Last
10.8
50%
45%
Li et al. (2018)
212.296
1.0594
Lemos et al. (2019)
N/A
45%
25%
S2V-DQN
N/A
1.1208
ML
Ours Greedy
10.36-0.01
55%
50%
Ours Greedy
221.52
1.0510
Ours Sampling
9.65
70% %
50%
Ours 10 samples
220.27
1.0443

---

Under review as a conference paper at ICLR 2023
(c) Barahisi Albert graph. Figure 4: Example colorings produced by our learned heuristic. Node borders indicate the colors. Numbers on the nodes indicate the order in which the heuristic labels them.
(a) Erdls Rényi gruph.
(b) Walls Strogaiz graph.
was less than 2500 CPU node hours and the time spent on validation and testing was less than 300 CPU node hours. We train each model for 200 epochs with five random seeds and report the standard deviation a of cost w.r.t. the random seeds as too See $A for more details.
Test Scores. In addition to mean cost, we report the ratio of the solution cost to the optimal solution cost (approximation ratio). For large graphs, this cannot computed exactly in a timely manner. In this case, use the best solution found by an ILP solver within compute time of one hour. To compare with baselines which return infeasible solutions (and hence have ill-defined cost), we report the percentage of wins (ties for first place count wins) and the percentage of instances solved optimally. We refer to these metrics as "Wins" and "Optimal", respectively. We use the model with the lowest cost compute these percentages.
Runtime, We benchmark on c2d-standard-4 Google Cloud instance with vCPUs and 16 GB RAM.
4.1 GRAPH COLORING
Greedy baselines. Largest-Fing First greedily colors nodes in decreasing order of degree. Smallest- Last (Matula & Beck, 1983) colors the nodes in reverse degeneracy order, which guarantees that when a node is colored, it will have the smallest possible number of neighbors that have been already colored. Smallest-Last guantees a constant number of colors for certain families of graphs, such as Barabási-Albert graphs (Albert & Barabási, 2002) and planar graphs (Matula & Beck, 1983). DSATUR (Brélaz, 1979) selects nodes based on the largest number of distinct colors in its neighborhood. DSATUR exact on certain families of graphs, e.g., bipartite graphs (Brélaz, 1979). We the implementations from NetworkX (Hagberg et al., 2008).
Machine learning baseline. We compare our approach with the chromatic number estimator of Lemos et al. (2019). It does guarantee that the solution is feasible, meaning that both under- and overestimate the chromatic number. We use the values reported by the original paper. Note that S2V-DQN (Dai al., 2017) cannot solve GC because of the way it embeds the state.
COLOR benchmark (Table 1). We evaluate on the same subset of the COLORO2/03 benchmark (Col, 2002) Lemos et al. (2019), consisting 20 instances size between 25 and 561 nodes. Our greedy policy outperforms both Largest-Firgs and Smallest-Last and is tied with DSATUR for the most graphs solved optimally. When sampling (100 samples) evaluate the policy, our model outperforms all baselines in both mean cost and win percentage and is tied for the most graphs solved optimally. The approximation ratio 1.25 and 1.13 for our greedy and sampling policies, resp.
Results on classic graphs. We also trained our model four families of sparse graphs: cycles, wheels, random trees, and stars. We trained on graphs up to 400 nodes and evaluated on graphs up to 10,000 nodes. The produced colorings optimal extremely close to optimal for all four families (Table 3). As our model works perfectly on cycles and wheels we conclude that the model leams to leverage local graph structure and works completely symmetrical. Table 4 shows the validation cost for varying instance size on Patts-Strooatt. graphs, which grows only slowly with instance size. See $B.2 for additional results.
when all nodes have the same degree and
Qualitative results. Figure 4 presents typical examples of the learned coloring heuristic on the training distribution graphs. See $E.1 for more examples. We can observe that the heuristic generally
7

---

Under review as a conference paper at ICLR 2023
Table 3: Our approach colors simple
families of graphs (near- Joptimalll
Graph Family
Optimal X
Ours
Stars
2
Random trees
2 2 2
Even cycles
2
2
Odd cycles
3
3
Odd wheels bx
3
3
3+0.00
Even wheels
4
4
(a) Erdös Rényi graph.
(b) Burabisi-Alber graph.
Figure 5: Example covers from learned hcuristic. Nodes with a bold border in the cover found, the order is irrelevant.
Numbers indicate the labeling order. Once
picks higher degree, centrally located nodes first. However, if several nodes have the same degree, it favors coloring neighboring nodes subsequently. This happens in the WS graphs, see Figure 4b. The learned heuristic can consistently color the WS graphs with 4 colors, which matches the Smallest- heuristic. We conclude that the learned heuristic captures complex aspects of the graph extending beyond simple segree-based decisions and considers the graph's 's local neighborhood structure.
We compare the runtime of our approach with the classical baselines. As we did not have access to the code of Lemos et al. (2019), we could not compare the runtime directly. Our approach is faster than DSATUR for graphs larger than 640 nodes and scales much better. As expected from $3.3, the runtime of our algorithm grows linearly with the size of the graph, similar to the simpler baselines such as Largest First and Smallest Last, which have better constant factors.
Runtime (Figure 6).
4.2 MINIMUM VERTEX COVER
Classic baselines. We compare with two classic algorithms. First, we use the endpoints of a maximal matching, which produces a 2-approximation Papadimitriou & Steiglitz (1982). Second, we compare with list-right Delbot & Laforest (2008), a V 3 approximation algorithm for maximum degree A.
Machine learning baselines. S2V-DQN is Q-learning based approach (Dai et al., 2017). We use the values reported in the original paper. Li al. (2018) present a tree-search based approach trained in supervised way. In contrast to S2V-DQN, it samples multiple solutions, then verifies if they are feasible. The time to construct feasible solution varies depending on the instance. We use the publicly available code and pretrained model from the authors. We run Li et al.' code until it finds feasible solution, and sample more solutions it is below the time budget 30 seconds per graph.
Results on in-distribution graphs. We evaluate and compare our approach for MVC with S2V- DQN (Dai et al., 2017) and et al. (2018) on the same dataset of generated graphs as Dai al. (2017). It consists of 16,000 graphs from two distributions, Erdös-Rén Ménés-Rééyi (ER) (Erdös & Rényi, 1960) and Barabási-Albert (BA) (Albert & Barabási, 2002), of sizes varying from 20 to 600 nodes. We the results reported by Dai al. (2017) their model trained 40-50 nodes, except for the graphs with less than 40 nodes, for which no data is available for this model. Hence we use their model trained on 20-40 nodes on these smaller graphs. See Table for the results on ER graphs and $B.3 for results on additional graphs. On ER graphs, our model achieves the closest average approximation ratio, followed by Li et al. (2018). Li et al. (2018) has the lowest average cost. Note that the lowest approximation ratio and lowest cost need not coincide because the cost grows quickly with graph size, whereas the approximation ratio does not. Our model and Li al. (2018) outperform the greedy baseline, while S2V-DQN is slightly outperformed by List Right. In Table 4, we show how the approximation ratio and cost depend on the instance size. As shown $B.3, on the BA graphs, model is about 2.3% away from optimal. The two machine learning baselines slightly less than 1% away from optimal. The greedy basclines are 9% 45% away from optimal.
Qualitative Results. Figure shows typical results of our learned MVC heuristics. See $E.2 for more examples. On the ER graphs, we can see that the heuristic does not always start with the highest degree node. In contrast, highest degree node. Unlike the classic greedy heuristics (and our learned graph coloring heuristic), the learned MVC heuristics seldomly pick neighboring nodes subsequently.
the BA graphs, the heuristic has strong preference to start with the
8

---

Under review as a conference paper at ICLR 2023
Table 4: Mean validation cost of approach for graph coloring on WS graphs and cost and approximation ratio for minimum vertex cover on ER graphs (10 samples). Shaded columns are for graphs larger than during training.
25
Larpud kirt
2.
Seauiial land
Nodes
20
50
100
200
400
600
Cost
3,92
4.00
4.02
4.01
4.04
4.05
0.5
Nodes
15-20
40-100
100-300
300-500
500-600
0.
MVC
Cost
8
43.8
178.4
384.9
540
12:0
2000
9128
Number nocine
Approx.
1.012
1.042
1.048
1.055
1.054
Figure 6: Distribution of graph coloring in- ference runtime on WS graphs.
Runtime. As shown in $B.5, our approach takes around 0.5 second to find a cover on the test graphs with 1,000 nodes on CPU per sample, and around 5 seconds for 10 samples. This is comparable to what Dai et al. (2017) reported on a GPU on a similar graph (11 seconds). Note that the time budget for Li et al. (2018) was 30 seconds and the time budget for the combinatorial solver was hour.
4.3 ABLATION STUDIES
Spatial locality. We test the inductive biases we made regarding locality of the decoder by comparing against a decoder variant that never updates the attention weights (static decoding) and variant that always updates all of the attention weights (global decoding).
Static decoding never recomputes the attention weights. For node a node that not yet labeled, its weight is: a C' tanh ((.,o) Static decoding O + + n²) operations, which are fewer than those of local update decoding when > d.n. With static decoding, the model is essentially a GNN with a special node-readout function.
vil
Global decoding recomputes the attention weights in each time step For node i that is not yet labeled, its weight is: a;
Global decoding uses (dPn)) operations, which is at least d² factor more than local update decoding for not too dense graphs (m < n² /d)).
(t) = C .tanh (()I))"
Vi
When there are only two labels (as for MVC), global decoding is very similar to the Kool al. (2019) model. The difference to Kool et al. (2019) is that they use additional attention layer to compute new state embedding each step.
We train graph coloring models with both static and global decoding on the Lemos et al. (2019) subset of the COLOR challenge graphs (following $4.1). Static and global decoding achieve a mean cost of 10.74#0.12 and 10.71 =0.05 respectively, both worse than when using inductive bias (Table 1).
Architecture Parameters. We varied the size of the context embedding (i.e., the number of nodes and their labels that contribute to it). Increasing the context size does not significantly improve the test score on graph coloring. For graph coloring, a context of size two and three results in a mean cost of 10.49=0.12 2 and 10.42=t0.12 respectively, for the greedy policy. We varied the number of attention heads (among 1, 2, 4) with a per-head dimension of 16. For graph coloring, this results in a mean validation cost of 5.29=0000 4.981 and 4.95+ respectively. We therefore use 4 attention heads (hidden dimension 64). In $B.4, we provide additional ablation studies for the encoder.
5 CONCLUSION
We introduced combinatorial node labeling, framework that generalizes existing approaches to many hard graph problems, and presented neural network architecture for it, which demonstrates excellent results on both graph coloring and minimum vertex cover problems. This serves as an important step toward replacing hand-crafted heuristics in graph algorithms with learned heuristics tailored to a particular problem and graph structure.
There are many avenues for future research. While the nodel labeling framework is very general, other graph problems may require adjustments to the neural architecture or inductive biases for good performance. In particular, handling weighted graphs and edge labeling problems would be valuable.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
The combinatorial node labeling framework and our neural network architecture target a broad class of graph problems, and hence are very purppss. Downstream tasks of such problems range from compiler passes to logistics optimization to graph data mining. Hence, it is hard to identify specific cases of benefit harm from our work, it depends the specific application of the downstream tasks. We nevertheless urge careful consideration of the implications of improving performance on tasks using our methods, especially ones with privacy implications (e.g., data mining).
REPRODUCIBILITY STATEMENT
We detail the combinatorial node labeling framework in $2, and describe the neural network architec- ture and training process we use in $3. We note that the node labeling framework is very general and alternative architectures could be used to solve it. Proofs of our theoretical claims are provided in &C and we give details of our training setup in $4 and $A. We additionally include our source code in the supplementary material to aid reproducibility.
REFERENCES
Computational symposium on graph coloring and generalizations (COLORO2), Ithaca, NY, 7-8 September 2002, 2002. URL https: /mat. tepper. cmu. Co100/O0..///
Faisal Abu-khzam, Rebecca Collins, Michael Fellows, Michael Langston, W. Suters, and Christopher Symons. Kemelization algorithms for the vertex cover problem: Theory and experiments. pp. 62-69, 01 2004.
Réka Albert and Albert-Lászit Barabási. Statistical mechanies of complex networks. Reviews of Modern Physics, 74(1):47-B (1-97,7777778 Jan 2002. ISSN 1539-0756. doi: 10.1103/evmoodhyy.74..3 URL http: //cx
doi.orge /000001.0001 1103/ 10111033evvtt /Rw/ModPMMsss.ee//// .7.47.
Saeed Amizadeh. Sergiy Matusevych, and Markus Weimer. Learning solve circuit-sat: An unsupervised differentiable approach. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https: http://////peeeeee.eeeeeeee net/ forum? /
1d-BJxg22R9t7.
Sanjecv Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, embeddiigg and graph partitioning. J. ACM, 56(2):5:1-5:37 2009. doi: 10. (..11445150279315027799 URL https::s://// 100 1145/ 1502793. 1502794.
David Avis and Tomokazu Imamura. A list heuristic for vertex cover. Oper. Res, Leu.. 35(2):201-22)) 204, March 2007. ISSN 0167-6377. doi: 10.10166..01.200660..144 URL https::/ccoi.zzg// 1016//111..... orl.. 2006.0 03 014.
Tobias Bandh, Georg Carle, and Henning Sanneck. Graph coloring based physical-cell-id assignment for
LTE networks. In Proceedings the International Conference on Wireless Communications and Mobile Computing: Connecting the World Wirelessly, IWCMC 2009, Leipzig, Germany, June 21-24, 2009, pp. 116- 120, 2009. doi: 10. 10.1145/1582379.1555 1582440.. URL https::/ //cp: www.orggg//.oooo /0gg/10..00 httg:/..111//1111 111//1582773 1582406.
Thomas D. Barrett, William R. Clements, Jakob N. Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In The Thirty- Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 3243-3250, 2020. URL https: /aaai.aa.......a .rgg ojs/ wwwiinnexx..... pwtdee..ppp/Aaee AAAT/
article/view/511 /5733.
Irwan Bello, Hieu Pham, Quoc V. Lc, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforeement learning. 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings, 2017. URL net/ / forum? ? d- 9mx1SFx.
Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. Fully dynamic approximate maximum
matching and minimum vertex cover in O(log n) worst case update time. In Proceedings of the Twenty-Eight SIAM Symposium on Discrete Algoritlums, SODA 2017, Barcelona, Spain, Hotel Porta Fira. January 16- 19, pp. 470-489, 2017. doi: 10. 103711 1111111119991161 717778811197777.70 URL https: : /twp///oooooo///ooooooooo .ooooiorg/// / 1137/1 07777/1971166 9787661777778....3
Annual ACM-SIAM
10

---

Under review as a conference paper at ICLR 2023
Hans L. Bodlaender. Discovering treewidth. In SOFSEM 2005: Theory and Practice of Compuder Science, 31 Conference on Current Trends in Theory and Practice of Computer Science, Liptovský Ján, Slovakia, January 22-28, 2005, Proceedings, pp. 1-16, 2005. doi: 0-507777788-50033577---4-3 URL https: //doi. org 10. 1000111007----00---00000
Daniel Brélaz. New methods to color vertices of graph. Commun. ACM, 22(4):251-256, 1979. doi: 10.1145339994.3591000 URL https://dbi....... wttgg/...00 1tt.:///////////1/1111/.1
359101.
Quentin Cappart. Thierry Moisan, Louis-Martin Rousseau, Isabeau
and André Augusto Ciré. Combining reinforcement learning and constraint programming for combinatorial optimization. CoRR, abs/2006.01610, 2020. URL http::tpp////oc www.wwwwww...........oao 2006. 01610.
Gregory J. Chaitin. Register allocation & spilling via graph coloring. In Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Massachusetts, USA, June 23-25, 1982, pp. 98-105, 1982. doi: 10. 145//000230 806984, URL https: doi. . www.o//////// 1145/ 800230.0... 806984.
Lenore J. Cowen, Robert Cowen, and Douglas Woodall. Defective colorings graphs surfaces: Partitions into subgraphs of bounded valency. J. Graph Theory, 10(2):87-1155, 1986. doi: 10.1002/gt.3199000077.
URL http:::: / /dci .rrg 10. /00///gt..3 901 00207.
Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optp:aiiiiiiiioiiiiiiiiiiiiioo optimization algorithms over graphs. CoRR, 70s/1704.01665, 2017. URL http: htttp:/aaxxiv.org/ aww/aa//000 066.
George B. Dantzig, D. Ray Fulkerson, and Selmer M. Johnson. Solution of a large-scale tracedinn--gggllllem problem. Oper. Res., 2(4):393-410, 1954, doi: 10. 2...2283/ URL https: htttppa:/dbi.orgg///
1287/opre. 4.33..
François Delbot and Christian Laforest. A better list heuristic for vertex Inf. Process. Lett. 107(3-4): 125 127, 2008 doi: 00.10166..p..2008.000 20.0.02.004. URL putpps///cee 1pp 024004.
Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma. Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on real-world graphs in lincar time. In 19th IEEE International Conference on Machine Learning and Applications, ICMLA 2020, Miami, FL, USA, December 14-17, 2020, pp. 19 24, 2020, doi: 10.1109/ (CMLAS5134.2220.00013 URL https: /ol. org/ 10. 1109/ ICMLA5 1294 24 2020 00013.
Paul Erdös and Alfréd Rényi On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5(1):17-60. 1960.
Michael R. Garey and David Johnson. Computers and Intractability; A Guide to the Theory of NP- Completeness. W. H. Freeman & Co., USA, 1990. ISBN 0716710455.
Mohsen Ghaffari, Ce Jin, and Daan Nilis. massively parallel algorithm minimum weight vertex cover. In SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, 259-268, 2020, doi: 10.1145/3350755.3m 3400060. URL https://dda //oii..///o/// http::///ooooo////// 1145/ 3350755 3400260.
Jack E. Graver. On the foundations of linear and integer linear programming I. Math. Program. 91):207-226, 1975. doi: 10.1007/BF11681344 URL ht /ww.i org/ wttp://11..11///1111 100//BF0168144..
Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman (eds.), Proceedings of the 7th Python in Science Conference, pp. 15, Pasadena, CA USA, 2008
Frank Harary and Robert A. Melter. On the metric dimension of graph. Ars Combinatorio, 2(191- 1976.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 770-77 778, 2016. doi: 10.11099CVPR.2016.999 URL https: /doi org/10 1109/ CVPR. 2016.90.
Stephen T. Hedetniemi and Reau C. Laskar: Bibliography on domination in graphs and some basic definitions of domination parameters. Discret. Math. 86(1-3):257-277, 1990. doi: 00.101660012-355000)0903 URL https:: //tp::/dcii////ooo www.erggl1l. 10161116/// 10066000000 00/0001111222 365X (9C) 90365-0.
Jiayi Huang, Md. Mostofa Ali Patwary, and Gregory F. Diamos. Coloring hig graphs with alphagozero. CoRR, abx/1900. 10162, 2019. URL htttp://axxiv.rrrtt/
902. 10162.

---

Under review as a conference paper at ICLR 2023
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference on Machine Learning. ICML 2015, Lille, France, 6-11 July 2015, pp. 448-456, 456, 2015. URL http::hpprooocediinnnnn/// mlr, press/
v37/loffe15 htmm.
T.R. Jensen. T.R. Jensen, B. Toft. Graph Coloring Problems. Wiley interscience publication. Wiley, 1995. ISBN 9780471028659. URL https::////.. bbookbo...o....o/ /ttp//oooooooi....... google ch/bocks boockssid-YEER 2oockkss?d-VY22AAAMM..
Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. CoRR, ahs/1906.011277, 2019. URI, http::t///axxi..rrg////////// 1906. 01227.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Sys- tems 33: Annul Conference on Neural Information Processing Systems 2020, NeurIPS 2020, Decem- ber 6-12, 2020, virtual, 2020. URL https: htap:pp:/ppppeeeee http////ooocooocccecooooocoocccc .ew.eeurnnnnnurrniniee. newr meurips... wwtpppppp//aaaecccccccc hww.0//a220////h/// 49485a9e e 90b2 Celb2uBBeedBbara 923c6691 -bw.teettbbtrttt..eeeeeeeaaaaaee htm..
David R. Karger and Clifford Stein. A approach the minimum eut problem. J. ACM, 43(4))6001-44 6400 1996. doi: 445//33533.2345544 URL https: /doi /t/////..115/224533323 233533333.4.
David R. Karger. Rajeev Motwani, and G. D. S. Ramkumar, On approximating the longest path in a graph.
Algorithmica, 18(1):82-98, 1997. doi: (0.1007/BR02522669) URL http:ps://ai..ggg//ee 1007/ BF 8802523689.
R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher (eds.), Complexity of Computer Computations, pp. 85-103. Plenum Press, 1972.
Brian W. Keriighan and Shen Lin. An efficient heuristic procedure for partitioning graphs Bell Syst. Tech. J. URL
49(2):291-300 307, 1970. doi: 10. 10.1002/j. 7.1538-7305. 1970. tb117700 x.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http: /ttp/v.aiiiv/////////eeeeeaaaa.a crg/ abs /1412.///2..... 6980.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, Iearn solve routing problems! In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
John Boaz Lee. Ryan A. Rossi, Sungchul Kim, Nesreen K. Ahmed, and Eunyee Koh. Attention models in graphs: A survey. ACM Trans. Knowl. Discow. Data, 336):62:1-62:25. 2019. doi: 10.1145/3363574. URL hetps://dci..e
Henrique Lemos, Marcelo O. R. Prates, Pedro H. C. Avelar, and Luís C. Lamb. Graph colouring meets deep 2019.
learning: Effecttive graph neural network models for combinatorial problems. CoRR,
URL http::tttaaiiiiii org/ abs/1903 04598.
Zhuwen Li, Qifeng Chen, and Vladien Koltun. Combinatorial optimization with graph convolutional net- works and guided tree search. In Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 537-546, 2018. URL https: : ppwceedeoieeggeeoooooo//eo www.riiissp... ez/ paper/200 8 8/hash/ 8d3pba /4252/222ccc
Abstract html.
Qiang Ma, Suwen Ge, Danyang Hc, Darshan Thaker, and Iddo Drori. Combinatorial optimization by graph pointer networks and hicrarchical reinforcement learning. In AAAI Workshop on Deep Learning on Graphs: Methodologies and Applications, 2020.
Andrew L Maas, Awni Hannun, and Andrew Y Ng. Rectifier nonlinearities improve neural network acoustic models. In Proc. ieml, volume 30, pp. 3. Citeseer, 2013.
Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. GCOMB:
learning budget-constrained combinatorial algorithms over billion-sized graphs. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12. 2020, virtual, 2020. URL https: pttp///roceens...e/ee/e//c www.eeiinnnnnnnnnn...eee cc/ paper/20200 htt.///asheee///
.neurips... Abstract html.
D. Marx. Graph colouring problems and their applications in scheduling. Periodica Polytechnica Electrical Engineering, 18-11-16, 2004.
12

---

Under review as a conference paper at ICLR 2023
David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. ACM, 30(3):17-427, 1983, doi: 10.1145/2402.322355. URL https:tttt...ooooc 322385.
Pawel Myszkowski. Solving scheduling problems by evolutionary algorithms for graph coloring problem.
In Metaheuristics for Scheduling in Industrial and Manufacturing Applications, pp. 145-167. 2008, doi: 10.
--000779778-----78888--3---8---- URL https: : coi -
Azade Nazi, Will Hang. Anna Goldie, Sujith Ravi, and Azalia Mirhoseini. GAP: generalizable approx graph partitioning framework. CoRR, abs/1903 11001900300114.... 2019. URL http: aaw.v.xxvvvv..co ozg / abs 19tp. 00614.
Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the Twenty-Third Anmual ACM-SIAM Symposium on Discrete Afgoritims,, SODA 2012, Kyoto, Japan, January 17-19, 2012, pp. 1123-1131, 2012. doi: 10.1 9tt/:/19786611 1973099.88. URL https: http://cciiccoo http://ccc.ccgg///
88.
Christos Papadimitriou and Kenneth Steiglitz. Combinatorial Optimizaaiion Algorithms and Complexity, volume 32. 01 1982. ISBN 0-13-152462-3. doi: 10. 10.1109/AASSP..98..11000
J. M. Robson, Algorithms for maximum independent sets. J. Algoritlums, 7(3):25- 440, 1986. doi: 10.1016/ 1196-6774436)90032-55 URL bttttps://bb..rrgg// 1.0 6/01 96- 6774 (86) 90032-5.
Michael D. Smith, Norman Ramsey, and Glenn H. Holloway. A generalized algorithm for graph-coloring register allocation. In Proceedings of the ACM SIGPLAN 2004 Conference Programming Language Design and Implementation 2004, Washington, DC, USA, June 9-11, 2004, pp. 277-288, 2004, doi: 10.1144/996841. 996875. URL wwtpt:ttp:... / ht/./iioooooo org. 11w.111119998/ 9964419.997755 996875
Richard S. Sutton and Andrew Barto. Reinforcement Learning: An Introduction. Bradford Book, Cambridge, MA, USA, 2018. ISBN 0262039249.
Robert Endre Tarjan and Anthony E. Trojanowski. Finding a maximum independent set, SIAM J. Comput. 6(3): 537-546, 1977. doi: 10. 03/160700
Etsuji Tomita and Tomokazu Scki. An efficient branch-and mannch-and-bee bound algorithm for finding a maximum clique. In Discrete Mathematics and Theoretical Computer Science, 4th International Conference, DMTCS 2003, Dijon, France, July 7-12, 2003. Proceedings, pp. 278-289, 2003. doi: 10. 00.10077/-540-4566-111 22. URL https:/ /ttp://cciii/// etg/ 1007 5400333-000--------0 12.
Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. RUN-CSP: unsupervised learning of message passing networks for binary constraint satisfaction problems. CoRR, ahs/1909.08887,, 2019. URL http:
// //arxiv.. .org/ abs /0ss//900 1909, 08387.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is you need. Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA. pp. 5998 6008, 2017. URL ht https: httpppss//pooceeiieeeee wwt.ooeeeings.neur....e www.rnnuss........ wwtppppppppppppeeeeeeeaaeee..aat 2017 2017/hash// /hash/ 315ee243547 / wbw.b3eleeaaaaeoomce.eeeeeee -bbaaaatttaabattattttt......a... html.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 2018, Conference Track Proceedings, 2018. URL https: //apenrevicw net rum? 1
Duncan Watts and Steven H. Strogatz. Collective dynamics of wsoldd-world' networks. Noture 3936684)::40--- 442, June 1998. ISSN 0028-0836. doi: 10. 1038//388918 URL http: /olp::////xxdo.....///oo////..// http://...diioo////////// 1111//1111111100011 30916.
Weichi Yao, Afonso S. Bandeira, and Soledad Villar. Experimental performance graph neural networks on random instances max-cut. CoRR, abs/1908.05767, 2019. URI. http:://axxiv...////aaatta 05767.
13

---

Under review as a conference paper at ICLR 2023
A TRAINING
A. DATA GENERATION
We use four different synthetic graph distributions to generate instances for training and validation. All graphs are generated via the Python NETWORKX library (Hagberg et al., 2008).
Barabási-Alberd Model (Albert & Barabási, 2002) The Barabási-Albert (BA) Model generates random scale-free networks. Similar to real-world networks BA graphs grow by preferential attach- ment, i.e., new node is more likely link more connected nodes. The model is parameterized by one parameter 8, which dictates the average degree.
Erdós-Rény: Model (Erdós & Rényi, 1960) An Erdōs-Rényí (ER) graph G(n.p) p) has nodes and each edge exists independently with probability The expected number of edges is (2)p.
Watts-Strogatz Model (Watts & Strogatz, 1998) Watts-Strogatz (WS) graphs were developed to overcome the shortcomings of ER graphs when modeling real world graphs. In real networks we see the formation of local clusters. i.e., the neighbors of node are more likely to be neighbors. For parameters & and q, a WS graph is built as follows: build ring of n nodes. Next, connect each node to its k nearest neighbors. Finally, replace each edge (u, v} by new edge {u, w) (chosen uniformly at random) with probability q-
A.1.1 TRAINING SET PARAMETERS
See Table 5 for the parameters of the graph distributions used during training. Note that for BA and ER graphs, the parameters match those used in the Dai et al. (2017) test set (see Table 2 and Table 10). We also consider sparse ER graphs (S-ER), for we set the edge probability such that graphs have expected average degree close A 7.5 when is small but remain connected with high probability when n is large. This means that
A (
Inn n
Pa-er min
1, max
(1+
(1)
n
for small which we set to 0.2 in our experiments. The formula is derived from the connectivity threshold of ER graphs (Erdös Rényi, 1960).
For graph coloring, we train on hybrid dataset consisting of an equal proportion of BA, S-ER, and WS graphs. For minimum vertex cut, we train on a datasct consisting of BA graphs, a dataset consisting of ER graphs, and hybrid dataset consisting proportion). We use the in-distribution models for the evaluation on the synthetic test instances and the hybrid model for the memet racker graph. During training, graphs with n E {20, 40, 50, 70, 100) nodes.
combination of the two (in equal
equal proportion of
For the results (10....,51. 51, 60, 61, 70, 70,80, 81,90, 90, 91, 99, 100, 200, 201, 300, 301, 400, 401} and validate on 1000 or 1001 nodes.
simple graphs in Table 3,
graphs with sizes
A.2 POLICY OPTIMIZATION
We train model with REINFORCE with greedy rollout baseline Kool al. (2019). The details follow. We denote the cost of labeling the graph G; in the order given by the sequence of nodes π by C(T,, G.). A model M is parameterized by parameters 0. On graph G, the model returns sequence of nodes and an associated probability Pa- The probability po is the product of all action probabilities that led to the sequence of nodes л. We write po. evaluated deterministically and pa, Ma(G.) when the policy is evaluated probabilistically.
Mo, when the policy is
Table The graph parameters for training and validation.
BA
ER
S-ER
WS
8 = 4
p
0.15
== Pa-er
k = 5,
q 0.1
14

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Policy Training with Reinforce+Bassline
1: Input: number of epochs E, batch size B, datasets Dirain
2: Initialize model Ma and baseline model M BL
3: Dehallenge f- sample new challenge dataset
4: for epoch = 1..... ...,.. E do
5: for batch in Drrain do
6:
Po,i, Tú ~ Mo(G;) for G2 in batch ]
Sample from policy
7:
Pa.i !
BL BL f- Masa (G;) for G, in batch ]
B Greedy baseline
8:
VoJ(O) B D ( [[(ms) G.) -Lm Gi) Vo log(po.))
Policy Gradient
9:
ADAM (())
10:
end for
11: if OneSiieePPiredTTTessMMMMM MBL Dehallenge) < 0.05 then
Challenge the baseline
12: (BL. + 0
13:
Dehallenge f sample new challenge dataset
14:
end if
15:
end for
The complete training procedure is given in Algorithm 1. Algorithm follows from the textbook REINFORCE with a baseline (Sutton Barto, 2018) by factoring the probability of reaching terminal state and using that the rewards are 0 in our MDP except when reaching terminal state. Unlike Kool al. (2019), we not use warmup epochs where training starts out with an exponential moving average baseline.
B ADDITIONAL RESULTS
B. VALIDATION RESULTS
We compare the of the learned heuristic for different parameters of the training. The validation set consists of 600 graphs with n nodes for {20, 50, 100, 200, 400, 600).
B.1.1 GRAPH COLORING
Table 6 shows the validation cost on the three training distribution for all evaluated configurations.
With a larger learning rate 10-3, the mean validation cost for graph coloring significantly worse, namely 5.22 5.22=0.002, A smaller learning rate of 10-5 leads to mean validation cost of 5.02+0.001 which slightly worse than the cost of 4.95+0.02 for a 10-4
B.1.2 MINIMUM VERTEX COVER
Table 7 shows the validation results for training on either only one distribution and evaluating on ER and BA graphs. Training mixture ER and BA graphs leads to worse validation cost on BA graphs compared to training only on BA graphs. Training on ER graphs exclusively without BA graphs leads slight cost improvement ER graphs.
B.2 RESULTS BY SIZE
Table 8 shows how the cost and approximation ratio of our MVC approach varies with the instance size (on the ER test graphs). Although the approximation ratio grows slightly with instance size, remains within ca 5.5% of optimal for graphs with 500-600 nodes.
Table 9 shows how the cost GC varies on two synthetic distributions of graphs, S-ER and BA, For BA and ER graphs, the grows by about one color on the larger graphs.
B.3 ADDITIONAL RESULTS MVC
Results on BA graphs See Table 10 for the MVC results on BA graphs.
15

---

Under review as a conference paper at ICLR 2023
Table
Ablation studies for graph coloring. I, S, and short for local, static, and global decoders, respectively. Prev, denotes number of previously labeled nodes in state embed- ding, Norm. indicates if batch-normalizaioon is used, and Short. indicates if shortcuts are used.
Encoder Norm.
Decoder
Validation cost on distribution
Layers
Short.
Type
Prev.
Heads
S-ER
WS
BA
All
L.
5.32
4.01
5.50=0.01
4.95=0002
2
V
L
4
5.34
=0.01
5,57=0.02
4.98=00.02
1
V
L
4
5.4=0.05
4.09#t001
5.55=0.05
5.02#0.08
3
X
X
L
4
5.56
4.29+
6.09=0.04
5.32
V
X
L
4
5.56 10.05
4.12
5.92
5,22 5,22 0.004
3
V
S
4
5.59
4. 4.14=t0.00
5.52=0.06
5.09
3
V
G
4
5.58
4.15:b0.01
5.54
5. 10.03
3
V
L
4
5.37#0.03
4.02#t0.01
5.49=0.01
4.97=0.08
L
5.36
4.02
5.48=0007
4,96 4,96 0.00
3
L
2
5.38
4.02#t0001
5.54=0.03
4.98=0.01
3
V
L
1
5.58
4.01
6.26
5,28
Table 7:
MVC Validation Cost for vary-
Table 8: Cost and approximation ratio of our approach
ing
training
and
validation distributions.
for MVC on BA graphs by instance size. Shaded
columns are for test instances larger than the train- ing graphs. Approx. denotes the approximation ratio.
Train Graphs
Cost ER
Cost BA
ER
223.56.10.11
218.074:.36
Nodes 15-20 40-100
100-300
300-500
500-600
BA
223.76
#12.02
Cost 10.53
35.08
113.56
225.16
309.02
ER+BA
223.98 10..26
208. 208.18 16.24
Approx.
1.009
1.016
1.022
1.025
1.027
Table Mean validation cost our greedy approach GC on S-ER and BA graphs by instance size. Shaded columns are for instances larger than those seen during training. S-ER Graphs
BA Graphs
Nodes 20
50
100
200
400
600
Nodes
20
50
100
200
400
600
Cost 5.30
5.18
5.18
5.28
5.39
5.96
Cost 4.83
5.08
5.34
5.61
5.96
6.18
Table 10: Comparison of MVC approaches on BA graphs with average degree 4.
Name
Cost
Approx. Ratio
Class.
Maximal Matching
190.84
1.4516
List Right
143.50
1.0984
Li al. (2018)
131.62
1.0084
ML
S2V-DQN
N/A
1.0099
Ours Greedy
133.78=0007
1.0234
Ours 10 Samples
133.39.10.05
1.0202
16

---

Under review as a conference paper at ICLR 2023
Hartan
Purdmn
1.3
10000 12500
1030
5000
(a) GC on S-ER graphs:
(b) GC on WS graphs:
122
95.2%, 8
1.12 10 10-
96. 06.0% S 1.67 10 %s
2.5
25
1.5
1.5
Runtho
Murame
1.0
1.0
0.3
2000
3002
5000
1002
2000
5000
Number nondde
Namber rackes
(C) MVC on S-ER graphs:
(d) MVC on BA graphs:
112 94.4%. S 3.4 10 9s.
n12
94.4%.
1.68 10
Figure 7: Inference runtime with local decoding. The solid line indicates lincar least squares fit, the dashed orange line the mean. We report the coefficient of determination Ii2 and standard erroor S.
B.4 ABLATION STUDIES FOR THE ENCODER
We varied the number of layers in the encoder, removed the shorteut connections, and removed the normalization. The results are summarized in Table 6. We can see that removing the shortcut connections has very strong detrimental effect the validation cost. Removing both shorteuts and normalization deteriorates the cost further. Using layers results in a small, but noticeable increase in cost, whereas single layer has significantly worse cost.
B.5 RUNTIME SCALABILITY
We evaluated the inference runtime on 42ghhighmem-4 (4 vCPUs, 32 GB RAM) Google Cloud machine (Environment M94 with PyTorch 1.11). Figure show the runtime scaling of our approach on GC and MVC together with linear least squares fit. In Figure 7b, we see that for graphs up to around 5000 vertices the runtime of GC inference very closely follows linear trend. For larger graphs, the runtime grows slightly faster than linear, shown in Figure 7a. Similar results hold for MVC: takes less than 0.5 seconds to compute a vertex cover for a graph with 1,000 nodes. Figure 7d and Figure 7c show the distribution of MVC runtimes of up 5120 nodes.
B.6 DISCUSSION.
is not surprising that our machine learning approach performs best on in-distribution graphs. Whilst it is desirable to have an approach that generalizes well, if representative sample of graphs is available for target applications, this does not pose an issue. Moreover, we have shown that the quality degrades gradually when the test distribution differs from the training distribution.
17

---

Under review as a conference paper at ICLR 2023
C ADDITIONAL PROOFS
C.I THE NODE LABELING MDP
Proof of Lemma 2.4. Consider sequence of actions (uI, (i),.., , (n) ending in a terminal state. For all i, the prefix (v1, (1),,...... (ve, Ee) of this sequence corresponds partial node labeling d' (by viewing the sequence of node-label pairs as describing function from nodes to labels). By construction of the MDP, labeling node U++1 with l441 passes the extensibility test for c'. Hence the node labeling represented by (v1, fi),-..: (Un, fn) is feasible. By construction, the return of the episode is f(c), where f(c is the cost of node labeling c.
Conversely, consider feasible solution with cost f(c). Then, by definition of feasibility ($4.3), there is sequence (v), (I),................... (Va, en) of node-label pairs such that for all t 2 the partial node labeling given by (vi, (I),..,, (ve, &x) passes the extensibility test for node Ur+1 and label l(+1. Hence, the sequence of node-label pairs is also sequence of actions the MDP leading to terminal state. The return for this episode is -(()).
Note that since our tasks are episodic. the return equals the sum of the rewards (specifically the reward received in the terminal state). In particular, we do not use discounting.
C.2 OPTIMALITY OF THE LABELING RULE
Proof of Lemma 3.1. Let G be some graph with chromatic number X(G) = k and e" be mapping that colors G optimally. We partition V into color classes C, = {vl c² (v) = i such that all nodes with color i are in C, Now, we build an ordering by consecutively taking all nodes from C1, then all nodes from C2 and so on. Choosing the smallest color that passes the extensibility test will produce an optimal coloring for such an order of nodes: The proof is by strong induction on the index of the color class i. The induction hypothesis (i) is that for all nodes u in C, for j < i, v is colored with color in {1. .......j... Assume the induction hypothesis (i) holds. Now, consider a node in C,, The color must be a valid color for v: First, assigning color i does not produce any conflicts with any node in C, for j < i because by induction hypothesis node u has color strietly less than i. Second, assigning color i to e does not produce a conflict with another node w in C; because then C; would not be valid class of colors (nodes in a color class cannot be neighbors.). As we choose the smallest valid color and is valid, get color in [1....
.}. Thus, (i + 1) holds.
Note that this coloring might be different from the one of c* This is, because a node in C. might have no conflicts with some color j < i and therefore this node will be assigned color j.
Proof of Lemma 3.2. Let be the set over nodes with label 1 in a minimum vertex cover of G. Order these nodes first (in an arbitrary relative order), then order the remaining nodes in V V S nodes (in an arbitrary relative order). Now, label the nodes with in this order until every edge has an endpoint with label 1. After [S] steps, every node in S has label meaning that the nodes with label 1 form minimum vertex cover: If the nodes formed a vertex cover after less than |S] steps, we would find a smaller vertex cover, contradicting the minimality of S.
after these
D LIST OF COMBINATORIAL NODE LABELING PROBLEMS
We provide an extensive list of classic graph optimization problems framed as node labeling problems. Note that there can be multiple equivalent formulations. For some problems, we consider a weighed graph G with weight function w: E + Rt, write w(u, v) the weight of an edge {u, v}. For set of nodes S, we denote the subgraph of G induced by S with G[S).
The problems in Table 11 require partition of the nodes their solution. These can be represented as node labeling problems by giving each partition its unique label. For many of the problems, the number of used labels determines the cost function.
The problems in Table 12 require a path (or a sequences of nodes) as their solution, which we represent as node labeling problems by having the label indicate the position in the path (or sequence).
18

---

Under review as a conference paper at ICLR 2023
Table 11: Node labeling problems which partition the nodes into sets.
Problem
Extensibility Test T(V' x v,
Cost function f
Balanced k-partition (Kernighan Lin, 1970)
There are more than [%] nodes with the same label and at most k labels.
Σ ((L))EE. w(u,
Balanced k. + vpartition (Kernighan Lin, 1970)
There are more than [ nodes with the same label and most l labels.
EAumERRAAO) a(u,, v)
Minimum k-cut (Karger & Stein, 1996)
k 1
E(Ln)ERROO)) m(u,))
and (u) Every label induces clique
Clique cover (Karp, 1972)
Number of labels
Domatic number (Hedetniemi & Laskar, 1990)
Every label induces dominating set of G(V' U [w)]
Negative number of labels
Graph coloring (Jensen al., 1995)
No neighbor of v has label
Number of labels
Graph co-coloring (Jensen al., 1995)
The nodes with label / induce independent set in G' or the complement of
Number of labels
k-defective coloring (Cowen et al., 1986)
No node has more than neighbors with label
Number of labels
Table 12: Node labeling problems where the labels encode permutation of nodes.
Problem
Extensibility Test T(V' x 1, Cost function f
Traveling salesman problem
I max (C) and is a neighbor of the node
E(.n)EE ((,,v)
(Dantzig al., 1954)
in L with label max(C)
Tree decomposition (Bodlaender, 2005)
I max(C) (C)
For a node v; with label i, add edges to G until forms clique with its higher-labeled neighbors. The cost is the largest number of higher- neighbors in the augmented graph (Bodlaender, 2005).
Longest path (Karger et al., 1997)
1 1 max(C) +1
Maximum number of nodes with consecutive labels that induce path
The problems in Table 13 require a set of nodes as their solution. These can be represented as node labeling problems giving the nodes in the solution set the label and the nodes not in the solution set the label 0. The cost function is closely related to the number of nodes with label 1 for most of these problems.
19

---

Under review as a conference paper at ICLR 2023
Table Node labeling problems with binary labels. these problems, the extensibility test passes only the label is or (and the additional requirements listed below are satisfied).
Problem
Extensibility Test T(V' C, v,
Cost function
Maximum cut (Karp, 1972)
At least one node has label
-[(u.,) e E. & M())
Sparsest cut (Arora al., 2009)
At least one node has label
[(w.)E. Mo) 1 [[]]1)]]
Maximum independent (Tarjan & Trojanowski, 1977) (Robson, 1986)
The subgraph induced by the nodes with label is an independent
-K V,((u) 1H
Minimum vertex cover (node cover) (Karp, 1972)
The subgraph induced by the nodes with label is vertex cover of G[V" U {v)
Ho v,((u) = =1H
Maximum clique (Tomita & Seki, 2003)
The subgraph induced by the nodes with label is a clique
-1(v E V,((u) = 13
Minimum feedback node set (Karp. 1972)
Gl(u E V'U ("U, 0H is forest
Ho V,((u) 1H
Metric dimension (Harary & Melter, 1976)
The nodes in V U {w) are uniquely identified by their distances to nodes
He = 1H
with label
Minimum dominating set (Hedetniemi & Laskar, 1990)
The nodes with label form a dominating set of G(V" U (u}]
HoE HoEV, V,((u) = IH
Minimum connected dominating set (Hedetniemi & Laskar, 1990)
The nodes with label form connected dominating set of G(V" U (v))
(EEV, 1H
20

---

Under review as a conference paper at ICLR 2023
(a) Erdis Rényi graph, 16.
(b) Erdlis Rényi graph, n 16.
(c) Erdlis Rényi gruph, n 16.
14
Erdök--Rónyi graph,
Erdós-Rényi graph,
(f) Erdds--énní graph,
Strts-Strogatz graph, 16.
(h) Watts-Srrogatr graph, 16.
(i) Warts Strogatz graph, 16.
Watts-Srogatz graph, 16.
(k) Warts-Strogatz graph, ni (I) Warts-Strogatz graph,
Figure 8: Example colorings produced by our learned heuristic. Node borders indicate the colors. Numbers on the nodes indicate the order which the heuristic labels them.
E ADDITIONAL EXAMPLES
E GRAPH COLORING
Figure 8 and Figure show additional results of our learned coloring heuristic on in-distribution graphs. For the Erdös-Rényi graphs and Watts-Strogatz, provide some examples in circular layout and some with the graph, but for these two graph classes leads many crossing edges. See Figure 10 and Figure 11 for results on cycles, wheels, and trees. Interestingly, the heuristic picks the highest degree node in star wheel sometimes first and sometimes last.
layout. The force-directed layout emphasizes the structure of
21

---

Under review as a conference paper at ICLR 2023
(a) Rarahási-Alhert graph, v. 16.
(b) Aalhh graph, 16.
(c) Barahisi-Alher graph, 16.
15
10
(d) Barabisi Albert graph, n 16.
(e) Barahási Aerah graph, n 16.
(i) Barahisi Albert graph, n. 16.
Erdös-Rénn' graph,
(h) Strts-Strogatz graph,
Barabdsi-Albert graph, 20.
( Erdds Erdis-Rééni graph, 20.
(k) Watrs Strtsttt gmphh, 20.
(1) Rarablsi-Alhert graph, 20.
Figure 9: Example colorings produced by our learned heuristic. Node borders indicate the colors. Numbers on the nodes indicate the order in which the heuristic labels them.
22

---

Under review as a conference paper at ICLR 2023
(a) Cycle graph, 12.
(b) Cycle graph, 16.
(c) Cycle graph, 28.
(d) Cycle graph, 13.
(e) Cycle graph, 17.
(i) Cycle graph, v
Wheel graph.
Wheel graph, 1...
Wheel graph,
( Wheel graph, 13.
(e) Wheel gmph, 17.
Wheel gmah, 29.
Figure 10: Example colorings produced by our learned heuristic on cycles and wheels. The learned coloring heuristic visits nodes on the cycles in-order. For the wheels, the center of the wheel is either visited first or last.
23

---

Under review as a conference paper at ICLR 2023
(a) Star graph, 12.
28. 10
(b) Star grapht 7a 16.
(c) Star graph,
graph,
(e) gruph,
(i) graph,
Tree graph, 12.
Tree graph, 16.
Tree graph, 28.
i Tree graph, n 13.
(k) Tree graph, n. 17.
() Tree graph, 29.
Figure 11: Example colorings produced by our learned heuristic on stars random trees. For stars, heuristic either labels the center first or last. The tree heuristic prefers to start coloring at one of the leaves of the tree and then colors nodes in search pattern from there, coloring nodes that are neighbors of already colored nodes. It often labels the remaining leaves very late into the coloring.
24

---

Under review as a conference paper at ICLR 2023
70
04
10
(3) Endls Rényi graph, 16.
(b) Erdōs Rényi graph, n 17.
(c) Erdiis Rényi gruph, nv
Fodds-Rénn graph,
Erdós-Rényi graph,
(f) Erdös-Rénní graph,
(g) Ahrabisi-AAhhrt graph, 16.
(h) Rarahási-Alhert graph, 17.
(i) Rarahisi-Alle Alben graph, 18.
(i) Barabisi-Albert graph, 20.
(k) Barablsi-Albert graph. x (l) Barabdsi-Albet graph. n
Figure 12: Example covers produced by our learned heuristic on Erdös Ménlis--enii--- and Barabási-Alles graphs. Black-bordered nodes are in cover.
E.2 MINIMUM VERTEX COVER
Figure shows additional example covers of our learned heuristic on in-distribution graphs
25


Reviews:
[{"review_id": "q4Jum-NS5n", "reviewer": "Reviewer_isah", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors present a graph attention network trained using policy gradient reinforcement learning that can label nodes in an efficient way to (try to) solve hard combinatorial optimization problems. They test their method on the graph coloring and minimum vertex cover problem on different kinds of graphs , comparing the performances with greedy algorithms and different neural networks approaches proposed in the past.", "summary_of_the_review": "Summarizing while the idea of finding an efficient way for node labeling in hard combinatorial problems is new and interesting, the results obtained in the draft are not good enough: the proposed method cannot reach the performances of standard algorithms, it does not generalize well and its performances degrade going to larger sizes of the problems.", "strength_and_weaknesses": "\nThe idea to create an efficient way for node labeling in combinatorial optimization problems is new and promising. Indeed, in greedy algorithms (GA) one decides the rules to choose the next node to label. In GA these rules are chosen a-priori, and different choices are possible: taking inspiration from GA, the authors try to infer which is the best order using a Graph attention network: the resulting order for node labeling is different from the standard GA ones.\n\nThe main weakness of the paper is that the performances of the method are not extensively investigated and the comparison with existent methods to solve combinatorial optimization problems is not completely fair and exhaustive. Moreover, the weaknesses of the results are only shown in the Appendix and not in the main text.\n\nFor the graph coloring (GC), the authors compare their results with GAs and with the machine learning (ML) approach of Lemos et al (2019) (GNN-GCP). GNN-GCP is not very good for GC. In fact it acts as a classifier, with the only output being the predicted chromatic number and not a possible configuration of nodes labels. For this reason GNN-GCP can find a number of colors smaller than the correct one, that is a highly undesirable feature. I suggest to compare the results of the method proposed by the authors with other better ML approaches to GC, such as the one in Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Frontiers in artificial intelligence, 3:98, 2021 (the arXiv reference in the draft should be updated with the published one) or the recent Schuetz, Martin JA, et al. \"Graph Coloring with Physics-Inspired Graph Neural Networks.\" arXiv preprint arXiv:2202.01606 (2022).\n\nFor GC on simple family of graphs, like wheels, trees, even/odd cycles, after a training on graphs up to 400 nodes, the proposed method finds the good chromatic number on graphs up to 1000. The author could test the performances on larger instances in this very basic examples to check if performances degrade going to larger sizes.\n\nThe runtime is shown in Fig. 6-7 for GC and Fig. 8 for MVC. In this last case, the scaling seems to be exponential with the size of the problem and not linear. However in both cases a fit should be performed to show if the scaling is linear or not. (In Fig. 6 the scaling of DSATUR seems to be not-linear too; however DSATUR is a simple greedy method that should perform in linear time, thus I have some doubt on the good implementation of it).\n\nWhen tested on sparse Erdos-Renyi graphs of average connectivity c=7.5, the method proposed by the authors finds a chromatic number of almost 5 for instances with 100 nodes, and a chromatic number of almost 6 for instances with 600 nodes. However a standard message passing algorithm, or a stochastic walk-sat algorithm can find a good coloring with 4 colors up to connectivity larger than 8 for much larger graphs in linear time (see for example L Zdeborova and F Krzakala. Phase transitions in the coloring of random graphs. Physical Review E, 76(3):031131, 2007). Thus the performances of the proposed method are really poor in this case and degrade fast with growing sizes.\n\nFor MVC, following table 10 the proposed method cannot reach results obtained by other existing ML methods. Moreover no comparisons with standard algorithms is performed.\n\nIn Table 7 one notices that performances of the proposed method quite strongly depend on the training set: if trained on ER graphs, the performances on BA graphs reduce and vice-versa: the method cannot generalize well.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VWLHhnaAwFq", "reviewer": "Reviewer_wJkv", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes a framework for learning combinatorial problems over graphs in which the solution can be expressed in terms of an ordered labeling of the nodes. Then, the authors propose GAT-CNL, a neural architecture leveraging the framework to learn to solve such class of problems in a greedy fashion. Empirically, the method presents better results when solving graph coloring and minimum vertex cover.", "summary_of_the_review": "In my opinion the paper needs a little bit more of work, since the weaknesses currently outweigh the contributions. If the authors are able to test the solution on larger graphs and make the proofs more rigorous, I'm willing to raise my score.", "strength_and_weaknesses": "--- Strength ---\na) The node labeling framework is a clear formulation of a wide class of problems and will help guide future contributions.\nb) The graph coloring problem indeed never had, to the best of my knowledge, a more general ML solution.\nc) Their MDP formulation allows for more than two labels and, more importantly, unknown number of labels. This is because a state is not a partial solution, but a partial labeling, which is fundamentally different.\nd) Lemma 2.4 guarantees a solution in the MDP space, which is not a common result in previous literature.\ne) Empirical results, especially for GC, are very promising.\n\n--- Weaknesses ---\na) Throughout the text, the authors argue that node labeling and greedy strategies are intimately related (due to the ordering of labels). I understand that it's a natural relationship when we design heuristics, but we know that relationship does not necessarily exist in optimal solutions. I think it would be good to make this distinction more clear.\nb) I find the proofs not rigorous enough (although the statements seem to be true to me). The authors try to present constructive arguments, which can result incur easily in this (without enough care). From what I see the proofs can be rewritten to use contradiction instead. A good example of this is Lemma 3.2's proof: The authors construct a solution and immediately conclude \" Labeling the nodes in this order produces a minimum vertex cover of G.\". I understand the lemma stands, but it reads sloppy.\nc) I expected to see larger graphs in the dataset. Also, for ML in combinatorial opt, it is vital to test your solution on graphs that are larger at test time (shift in distribution).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MmLNosq4s39", "reviewer": "Reviewer_aTgv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper extends S2V-DQN and enables it to cover more node-labeling-related problems. In terms of the neural network model, S2V embedding is replaced by more recent GAT embedding. Experiments are conducted on graph coloring and minimum vertex cover.", "summary_of_the_review": "The idea of \"learning node labeling\" for CO is novel and interesting, however, the technical contributions of this paper seem trivial and incremental. I am suggesting a rejection in consideration of the lack of technical novelty.", "strength_and_weaknesses": "**Strength**\n1. This paper extends the classic S2V-DQN approach, with the purpose to fit into more general problems.\n2. Learning node labels is an interesting characteristic of learning CO, which may inspire future papers.\n\n**Weakness**\n1. The overall pipeline of this proposed approach is very similar to S2V-DQN, and such a reinforcement learning pipeline is actually followed by many other papers to tackle different problems since the S2V-DQN paper was published in 2017. For example, the following papers also study graph coloring:\n    * Enhancing column generation by a machine-learning-based pricing heuristic for graph coloring. AAAI 2022. \n    * Approximation ratios of graph neural networks for combinatorial problems. NeurIPS 2019.\n\n   Considering these existing papers, the node-assignment step, which is the main technical contribution of this paper, seems incremental.\n\n2. Adopting attention models for CO is either a new idea, for example, the highly cited paper:\n    * Attention, learn to solve routing problems! ICLR 2018.\n\n   So in this paper, replacing S2V with GAT in the model does not seem novel either.\n2. Since the proposed scheme also covers \"set\" and \"permutation\" problems, it will be interesting to see the performance of the proposed method on well-studied problems such as TSP. It will be easier to position the effectiveness of this approach w.r.t. existing papers with the results on problems like TSP.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "C2cGs3nRRaS", "reviewer": "Reviewer_j1zE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a combinatorial node labeling framework, which solves CO problems by labeling the nodes. The model is based on graph attention networks and trained by reinforcement learning. Graph coloring and minimum vertex cover are studied. Experiments prove the performance of the proposed framework.", "summary_of_the_review": "This paper unifies a lot of CO problems into the node labeling framework. Experiments on graph coloring and MVC show the significance. The problem is that the significance of dealing CO problems as node labeling might be overclaimed. More experiments on MVC compare with stronger baselines or experiments on other tasks are recommended.", "strength_and_weaknesses": "Strength\n- The perspective of unifying CO problems in the framework of node labeling is novel and makes sense. \n- Writing is good and the paper is easy to follow.\n- Experiments are sufficient. Experimental settings (baselines, datasets, paremeter settings, etc.) are presented clearly, and results are convincing.\nWeakness \n- One of the biggest concerns is whether the framework really works on the task MVC, which is usually not processed as  the node labeling problem in the main stream of literature. And in this sense, baselines are too old. To make the results more convincing, more recent baselines, e.g. [1][2], and traditional solvers should be compared. Only by comparing the sota methods and traditional ones on both running time and the results on the MVC problem, can the paper prove that node labeling works in tasks beyond graph coloring. Whether it `really' works well on MVC is the key point to judge whether the significance of unifying the CO problems into the node labeling framework is over-claimed.\n-The other concern is the technical novelty of the paper, it seems to me an increment extension from binary classification to the multi-class case based on existing S2V-DQN framework.\n\n[1] Local Search with Efficient Automatic Configuration for Minimum Vertex Cover\n[2] Efficient Minimum Weight Vertex Cover Heuristics Using Graph Neural Networks", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject