Graph-based Deterministic Policy Gradient for Repetitive Combinatorial Optimization Problems
Authors: Zhongyuan Zhao
Ananthram Swami
Santiago Segarra
Venue: ICLR 2023 poster (2023)

Abstract: We propose an actor-critic framework for graph-based machine learning pipelines with non-differentiable blocks, and apply it to repetitive combinatorial optimization problems (COPs) under hard constraints. Repetitive COP refers to problems to be solved repeatedly on graphs of the same or slowly changing topology but rapidly changing node or edge weights. Compared to one-shot COPs, repetitive COPs often rely on fast heuristics to solve one instance of the problem before the next one arrives, at the cost of a relatively large optimality gap. Through numerical experiments on several discrete optimization problems, we show that our approach can learn reusable node or edge representations to reduce the optimality gap of fast heuristics for independent repetitive COPs, and can optimize the long-term objectives for repetitive COPs embedded in graph-based Markov decision processes. Source code at https://github.com/XzrTGMu/twin-nphard 

Published as a conference paper at ICLR 2023
GRAPH-BASED DETERMINISTIC POLICY GRADIENT FOR REPETITIVE COMBINATORIAL OPTIMIZATION PROBLEMS
Zhongyuan Zhao Rice University zhongyuan. zhao@ rice. .ddu
Ananthram Swami
Santiago Segarra Rice University segarra@rice.cm
DEVCOM Army Research Laboratory ananthram. swami. ci cive army mii
ABSTRACT
We propose an actor-critic framework for graph-based machine learning pipelines with oon-differentiable blocks, and apply it to repetitive combinatorial optimization problems (COPs) under hard constraints. Repetitive COP refers to problems to be solved repeatedly on graphs of the same slowly changing topology but rapidly changing node or edge weights. Compared to one-shot COPs, repetitive COPs often rely on fast (distributed) heuristics to solve one instance of the problem before the next one arrives, at the cost of relatively large optimality gap. Through numerical experiments on several discrete optimization problems, we show that our approach can learn reusable policies to reduce the optimality gap of fast (distributed) heuris- ties for independent repetitive COPs, and can optimize the long-term objectives for repetitive COPs embedded in graph-based Markov decision processes. Source code at /ultttps://gttaeia
com wtt.:uu.tooo//tttMMMt/cc.co
-nhaard
INTRODUCTION
In general network setting, the network state is captured by graph G EV, that comprises vertex set V, an edge set ε, and matrix S capturing the node features. A vector o E R/ captures the outcomes on individual nodes of non-differentiable network process, fnct as:
(9)
We aim to optimize the sestem-level objective fotj where fobj RRool - is known linear combination, by improving parts of the network process f.er(.). In particular, we are interested in network processes that involve graph-based repetitive combinatorial optimization problems (R-COPs) (Kraay & Harker 1996) COPs that need to be solved repeatedly
graphs of the same slowly changing topology (V or E) but rapidly changing node features (S), under hard constraints that must be satisfied at all times (Kendall 1975). which often make COPs NP-hard. R-COPs have many real-world applications, such as task scheduling (Pinedo] 2012). route planning (Vogiatzis & Pardalos 2013). link scheduling (Joo & Shroff [0022] Paschalidis et al.. 2015 Eisen et 2019 (Zhao et al. 2022a b) and routing (Oliveira et al., 2011) in communication networks, and energy management in smart grids (Chau 2018), where node edge weight captures varying cost or utility.
In practice, solvers for R-COPs are often subject to restricted runtime and/or distributed execution. For example, in scheduling, network routing, and multi-object tracking in computer vision, COPs need to be solved within tens of milliseconds to few seconds. Although memory- based approaches can avoid solving each instance from seratch for some applications (Kraay Harker, 1996. Wang 2021), in general, R-COPs rely on fast heuristics to meet the strict time constraints, at the cost of relatively large optimality gaps. Moreover, real-time networked systems, such as communication networks, smart grids, and robot swarms (Tolstaya al.) 2020), centralized solvers often suffer from the large communication overhead of gathering the full network state, high computational complexity, and risk of single point of failure. Therefore, distributed solutions (Moser & Tardos 2010) preferred for better scalability and robustness, in which nodes across the network work in parallel to collect and process the information of only their local neighborhoods for decision making.
Depending on the definition of fatj. R-COPs can be categorized as. 1) independent R-COPs. i... S(11) and S(12) considered as independent if / + 12, and R-COPs embedded in graph-

---

Published as a conference paper at ICLR 2023
Markov decision process (MDP). For example, in link scheduling for wireless multiple networks (Zhao et al. 2022a b), the network state (tt = (V. E, S())). where S(t captures the packet backlogs the schedule of t 1 found by solving maximum weight
of all the links at time t, depends independent set (MWIS) problem defined on g - 1). Scheduling for maximum throughput (numher of data packets transmitted on the schedule) is equivalent to optimize each MWIS instance individually (Zhao et al. 2022a), which is formulated as an independent R-COP. However, to minimize the average backlog (packets left in the queues by the schedule) across links and over time, the transition of network states must be considered and the scheduling is formulated as R-COP in a graph-based MDP (Zhao et al. 2022b). Similar MDP formulations can also be found in wireless scheduling for battery lifetime (Sikandar et al. 2020), vehicle routing for waste collection (Wu et al.) 2020). and inventory control distribution networks (Celebi 2015). However, the 2nd type of R- R-COPs have rarely been addressed, except in an ad-hoc manner for link scheduling (Zhao et al. 20226.. Therefore, general approach to R-COPs in graph-basee MDPs would be of high interest.
1.1 EXISTING APPROACHES TO COPs
Centralized solvers: The general approach for exactly solving a COP is to formulate as a mixed- integer program, and solve it by branch-and-bound (Land & Doig 1960) dynamic programming. Commercial Gurobi solvers (LLC 2020) can exactly solve COPs on graphs of hundreds of nodes in reasonable time. Although large real-world graphs with certain structural properties can be reduced (Lamm et al. 2019) to find exact solutions, problems of large scale and/or stringent time limits often rely on efficient heuristics to approximate the solutions; common strategies include greedy algorithms, local search ( (Wang et al. 2018), tabu search, ant colony (Jovanovic et al. 2010). and simulated beaning-based 202T) are trained to guide an algorithmic framework, which guarantees the constraints being always followed; common frameworks include branching (Khalil et al.) 2016]Gaass et al., 2 Nair et al.
annealing. In recent machine learning- based COP solvers, graph neural networks (GNNs) (Wu et al.)
2020; Zarpellon et al., 2022), tree search (Li et al. 2018), greedy algorithms (Khalil et al. [201]] Zhao et al., 2022a)). and local search (Hudson et al. 2022). In these approaches, a COP instance is formulated a fimite episode of an MDP, with the residual graph of each intermediate step defined as a state, based on which an action of adding one vertex in the residual graph to the partial solution is
generated by GNN, and solution is built from a sequence of such scalar actions. This formulation has a time complexity of at least (())))), since a GNN of time complexity of ((E)) (Wu et al. 202T is called in each intermediate step. (Drori et al. 2020 Hottung et al.) (022) lowered the time complexity of vehicle routing problems to O(EE)) (typically, [&|> [V) > by encoding the graph by GNN only once per COP instance. However, for R-COPs, this formulation limited by centralized execution and the complexity of a GNN, and does not apply to R-COPs in graph-based MDPs.
Distributed solvers: Popular distributed approaches to COPs include Moser- Moser-Tardos algorithm (Moser & Tardos 2010) and dynamic programming. The complexity of distributed algorithms is typically measured by local communication complexity, which refers to the rounds of message exchanges between a node and its neighbors (Joo & Shrofi 2012 Zhao et al. 2022a). For example, on MWIS, Moser-Tardos algorithm (Joo & Shrofi] [012] Moser & Tardos 2010) can converge in Olog" [V]) rounds, whereas distributed dynamic programming (Paschalidis et al. 2015) in ((VV) rounds. Distributed algorithms may have larger optimality gaps due to the lack of global information, but topological metrics, such edge betweenness for the Steiner tree problem(Fujite et al., 2016), can help reduce the gap. Learning-baat to their centralized counterparts. GCN-LGS (Zhao et al. (022a) is an architecture proposed for repetitive MWIS problem, in which an L-layer graph convolutional neural network (GCNN) generates vector for topology (V,8), and a greedy heuristic solves modified instances (V, E, c(t) O z). rather than the original ones (V, E, c(t)), for the next N time slots E {1...., N), assuming the N. GCN-LGS can reduce the optimality gap of greedy solvers [Joo & Shroff, 2012) by 1/3 to 1/2, with time complexity of (LLET/N + [V')), or can converge in OLL/N + log VI iterations in a distributed setting. For large reusing factor N, the overhead of GCNN is negligible. However, the training methods in (Zhao al..
distributed COP solvers have received less attention compared
topology would not change by
2022a b) are ad hoc and specific to MWIS problems, and may not be directly applicable to other types of R-COPs.
In this work, we generalize the GCN-LGS architecture in (Zhao et al. 2022a b) to a wider range of R-COPs, through a unified framework of problem formulation and actor-critic architecture. Unlike previous works that solve COP instance through sequence of scalar actions, generates a digh-dimensional intermediate action to parameterize a given classical heuristic, ht' (-). which produces vectorized decisions by solving one or multiple instances of an R-COP. This formula-
actor network
2

---

Published as a conference paper at ICLR 2023
tion allows to pick fast and/or distributed classical heuristic h-)-) that adheres to various practical restrictions, while guaranteeing the decisions always follow the hard constraints. For independent R-COPs, an intermediate action encodes the underlying topology shared by N instances to improve the average quality of their solutions, reducing the GNN overhead from ((EE)) (Drori et al., 2020 Hottung et al. 2022) to ((E)/N), which is arbitrarily small for large N. In R-COPs embedded in a graph-based MDP, an intermediate action for the optimal expected long-term objective is generated based on the network state in each time step, serving as the cost vector of the corresponding COP instance, which is later translated into a decision vector by N'(-). The challenge, however, is that our policy network contains a -n-diffeerentaale block, e.g., h'(-).
1.2 LEARNING IN NON- DI-FFERENNIIBBLE PIPELINES
Training with supervised or unsupervised learning methods is challenging in the presence of non- differentiable blocks. Reinforcement learning (RL) (Sutton & Barto, 2018) addresses this problem by treating the non-differentiable block as (part of) the environment (Silver et al. 2014 Khalil et al.) 2017, Zhao et al. 2022a). Compared to Q-learning (Watkins & Dayan 1992) that is sequential, policy gradient (Silver al. 2014) is better suited for the high-dimensional action spaces in networks of parallel and dynamic nature. A major issue in RL for networks is how to assign credit to individual
elements based on the system-level reward. Zeroth-order optimization (ZOO) (Liu et al. (0200 is the
last resort for non-differentiable pipelines, as it requires numerous evaluations of fnee(? (-), which can
be computationally prohibitive. In some scenarios, soft constraints (Kendall [975] can avoid the
use of non-differene diteentiffee pipeline, allowing a fully differentiable policy network being trained by primal-dual optimization (Fisen al., 2019) or imitation learning (Ross et al.
201T).
To address the aforementioned shortcomings, we propose GDPG-Twin, a graph- deterministic policy gradient method based on the actor-critic framework (Sutton & Barto [018 ch. 13). GDPG- Twin trains a differentiable twin of the non-differentiable policy block in (ner(-), e.g., h'(-), as part of the critic network to facilitate the training of the actor network. A similar differentiable approximation bridges (DAB) (Ramapuram & Webb (020) can approximate the immediate behavior of -iffeefeerett block in standalone systems. We improve DAB from three aspects: we use a twin network to predict the element-wise expected outcomes of the non-differentiable policy network, use a GNN to account for the permutation equivariance in network settings, and use random policy sampling for static policy parameters Z in fixed topology. In addition, GDPG- -win is more efficient than ZOO, Although we focus on node-related problems, GDPG-Twin also applies to edge-related problems, e.g.. by using simplicial neural networks (Roddenberry et al. 2021.
1.3 CONTRIBUTIONS
In summary, our proposed framework: 1) can generalize to learning for different COPs without handcrafting the credit assignment strategies as in other schemes of network- based RL (Eisen et al., 2019 Zhho et al. 2022a b). 2) works for R-COPs with hard constraints, 3) requires fewer evaluations of (.) than 700 (Liu et al. 2020), and 4) has the advantage of RL schemes in not relying on expensive data labeling as in supervised learning or a computationally intensive supervising algorithm as in imitation learning (Ross al. 2011). Our contribution contains the following three aspects:
We propose general approach to R-COPs under hard constraints and practical restrictions. Our approach can reduce the optimality gap of fast and/or distributed heuristics for inde- pendent R-COPs, the cost of only an upfront computation and communication overhead. Moreover, it can optimize the long-term objectives for R-COPs in a graph-based MDP by embedding the future reward into the cost vector of COP instance at each time step.
We propose GDPG-Twin, an actor-critic architecture for network settings. By using a twin network that learns the element-wisg wise expected outcomes o of a non-differentiabbe policy network in (.). the critic can leverage the knowledge of the linear combination of the system-level objective for, (o) to address the challenge of credit assignment across the network, which is a major roadblock for discrete or mixed-integer network processes.
We adopt a random policy sampling strategy in the training of the twin network, which enables optimizing static policy for R-COPs defined on fixed topologies. Moreover, our approach requires significantly fewer evaluations of the network process fnee()) than ZOO.
Notation.
Upright bold (ower(upper)-casse symbols are used to denote column vectors, e.g., X (matrices, e.g., X). x; denotes the ith element of vector x, X., denotes the element at row and
3

---

Published as a conference paper at ICLR 2023
column j of matrix X, xxx (or X,)) denotes row i (or column j) of matrix X. Unless otherwise specified, calligraphic upper-case symbols (c.g., V) are used to denote sets. (+) and O denote transpose and element-wing product, respectively.
PROBLEM FORMULATION
Many binary discrete COPs have the following formulation,
x min c x
(2a)
s.t. x, E (..) (...).
(2b)
other mroblem-specifee constraints,
(2c)
where x and с are respectively the vectors of decisions and weights on nodes, and constraints in (2c)
often defined on the graph, e.g., X; x, I V(E, E. Without loss of generality, (2b) can be of other arities and (2c) can be on hypergraph or simplicial complex. Since many problems in (2) NP-hard, we seek to develop efficient heuristies to approximate x". Furthermore, we define the function space F of valid heuristics, meaning that x = f(V,E, c) satisfies the constraints in (2) for all F. We also define the space P of practical functions, i.e., functions that satisfy pre-specified practical restrictions, e.g., limited runtime and/or distributed execution.
2.1 INDEPENDENT REPETITIVE COPS
For independent R-COPs, the weight of an instance is considered to be random vector drawn from its target sampling distribution S?- We formulate independent R-COPs as finding a valid heuristic
(policy) that optimizes the expectation of the objective function in (2a under practical restrictions
h min
Eaosie (c x)
(3a)
BE(FNP)
s.t. x = h(V,E.c).
(3b)
2.2 REPETITIVE COPS IN A GRAPH-BASE MARKOV DECISION PROCESS
Given network state (t) = (V(I), ((),, S())., where S(t) captures features on nodes at time (, our objective is to find valid heuristic h for COP in 2 and cost function V which together form policy that subject to the practical restrictions maps (t) into x(t) and maximizes the expected system-level value over time horizon T, as follows:
h",
max VEP
Egayae [ao (o(1))
(4a)
T-
8.l. (1) = E
Σ
xrr(1 xr((++ b) E>t((++)((
(4b)
r(t) =
(4c)
x(t) c())
(4d)
c(I) = V(V()),(0))
(4e)
S(t + -
(4f)
In 4 ot is the value vector of current state (t) under policy {h, } 0 y S is the discount factor, (4a) states that the system objective is the expectation of known linear combination, fokj Riol + R. of o(1) over the initial state distribution Ω capturing both average reward and start-state formulations (Sutton et al. 1999). (4c) states that decision vector x(1) is generated by a valid heuristic h e of COP based on the network topology (V(t), E()) and cost vector c(t), which is function of the network state (t) as stated by (4c). and 4c) and (41 define the MDP by respectively stating that the reward vector r(t) and the next state Stt + depend on the current state S(t) and the decisions x(t). In general, f-(-) and fa(.) in 4 are stochastic functions, capturing some stationary random processes in the environment. The formulation in (4) can capture R-COPs with accumulative objectives, such as latency and battery lifetime in wireless scheduling, waste level in vehicle routing for waste collection, and inventory in distribution networks. Notice that if T = f, y = 1, S(t) = c(t) (I is bypassed), r(t) c(t) x(t), (o) 1 and we set fa in 4f as drawing random vector from ? then 4 boils down to (3). Thus, (4) is generalized form of all R-COPs. Appendix A further illustrate and (4) via exemplary formulations of two wireless scheduling problems.
4

---

Published as a conference paper at ICLR 2023
3 GRAPH-BASED DETERMINISTIC POLICY GRADIENT
Our downstream pipeline follows the existing methodology of using neural network to guide discrete operation, which guarantees the hard constraints, but keeps the neural network outside the iterations of the algorithmic framework for lower complexity (Zhao et al. 2022a). In this section, we provide the main solution, whereas the full procedures of optimization for Sections 3.1 and 3.2 are given by Algorithms D and 2 in Appendix Since (3) and (4) are functional optimization problems, seek to approximately solve them by parameterizing the policy (h or {h, V and reformulating (3) and (4) as finding the optimal set of parameters. To meet the practical restrictions, we rely on manual selections (or design) of baseline heuristic h F and the parameterizations.
3.1 LEARNING FOR INDEPENDENT REPETITIVE COP
For independent R-COPs, we reformulate
3 as
Z min o
(5a)
Z
8.1. o = Ee (c ( x)
(5b)
x = E((VE,w)
(5c)
w; floc(c,; Z..) Vi (1....,/c]}
(5d)
The objectives in (3a) and 5ap are equal due to the linearity of expectation, i.e. Ec-tre (c
x)
Ee-n= (E/g C, parameterized policy in (3b). h(: 2), into a baseline heuristic N'(-) E (F PP) given in advance and
Ee (c,x,) 1 _oo Constraints (5c) and (5d) further break the
a parameterized local function (: Z;.), where Zi E 1x captures the local parameters for
node i E V. The local function [too(;; Z;-) can be chosen as, e.g., multiplier, single neuron, or even a small neural network, and depends on node-specific parameters Zi..
To solve the problem formulated in (5). employ deterministic policy gradient reinforcement learning, where the policy parameters are Z. However, the gradient Vz1 o is not available since h' is non-differentiable. To address this problem, introduce trainable and differentiable twin network (:: +.) to learn the element-wise expected outcome of h:; Z). In contrast to the critic in typical standalone setting, which directly predicts the system-level objective, the twin network works for network settings, where the policy parameters and outcome are supported on graphs. The twin can be implemented by graph simplicial neural network, depending on the specific COP. The expected behavior of the twin can be described by
ftwin (V, E, c, Z; @;), where (Ep(cc)
Based on 5ap and (6). we can estimate the system objective as 1 Ö Based on (6) and the chain rule 81 T
06 the policy gradient estimated as (Silver al. 2014)
OZ
V R Vz1 Vz.twin (,, Ege (c), Z; 0.)1
Given policy learning rate 0 ap For applications on static topologies, we can optimize Z directly with stochastic gradient descent.
can update the policy parameters as, Z Z 0 V ò.
For R-COPs on dynamic networks, we want the policy parameters be function of the topology,
implemented as an actor, Z = VVVVE ē; Op). In this case, we can estimate the gradient Ve,1
Ve, (V, c; O 7z1" 6, and update the actor parameters perspective of the actor Vp (:; @p), its input is (V,E, c) instead of the instantaneous network state (V,E, c), and its output is intermediate action Z, which is used as the policy parameters.
θ f θ a,, 1 1 From the
Given learning rate S ag < 1, the twin network can be updated by the following gradient descent,
θ θ a. Ve, Emse (ò, o)
where the loss function emse (, o) is the mean- suuu--quar--errorr (MSE) between ô and o. Since o is an expectation over sampling space Ω can implement the following stochastic gradient descent
+ ー O a. Ve.
L m (ò, x), Emse (o,
1
Σ (o. cxx,)² CE si
x
by minimizing the MSE loss in with an off-the-shelf optimizer. Notice that we need to evaluate
h((+) and [toc(;; Z) to get in 9 A detailed derivation of is given in Appendix B
5

---

Published as a conference paper at ICLR 2023
3.1.1 RANDOM SAMPLING AROUND CURRENT POLICY
For applications based static topologies, i... (V,E, é) are constant, we longer need actor to generate Z. In this case, the twin is likely to be overfitted if we only feed it with a static Z during training. To address this problem, we feed the twin [twin (-) and h(;; Z) with random samples
around the current policy parameters Z = Z + NO), No E ((),cc) where e is the sampling radius. The loss in (9 then becomes ( c @ x This random sampling strategy enables the critie, comprising the twin ftwin (:: . and system-level objective function foty (ô), to learn the loss landscape around the current Z, thus improve the quality of gradient in 7
In ZOO, policy gradient is estimated from at least two random samples around the current Z (including Z itself) (Liu et al. 2020). While fewer policy samples requires fewer evaluations of hc: Z). which could be computationally expensive in many applications, it could degrade the convergence by raising the noise floor of the gradient estimate. Compared to ZOO, our twin- based critic can continuously learn, refine, and memorize the loss landscape around the current policy as new samples coming in, leading to better gradient estimate in backpropagation (improved convergence as shown in Figure. D. and higher policy sampling efficiency, as shown in Sections and 4.3
3.2 LEARNING FOR REPETITIVE COP A GRAPH-BASED MARKOV DECISION PROCESS
For R-COP in a graph-based MDP, we parameterize the policy in 4 {h, V. with given baseline heuristic h E F, and parameterized cost function (:; Op). We then reformulate
θ
max θ G
EG(1)= [Sab] (o(1))
(10a)
T-
s.t. (t) = E
Σ
r rr ( g(t)
(10b)
r(t) = (()) ((t)))))
(10c)
x(1) = N'(V()),
(10d)
c(t) = ((V((),
(10e)
S(t + 1) = (())
(10f)
By fixing in the policy (h, v to a given baseline heuristic h' in (Od), we only need to optimize
the actor network (-; p) that generates the intermediate action c(t) based on ((t) in (Te)). Similar
to (7). we estimate the gradient Ve(t) (G (1) [foby (o(1)) through a twin network that predicts the value vector in (T0b) o(t) o() Stwii (())))(()))(())cc)))))
O.). Based on linearity of
expectation and the policy gradient theorem-the policy gradient does not depend on the gradient of the state distribution (Sutton et al.) [199).. the policy gradient estimate is (Silvrr et al. 2014)
Ve, E E [foks (o(1)) z E [Vo, (t) Vort)
(11)
Then, we can update the policy network as @p + θ + ap Ve, sampled from Ω² According to the derivation in Appendix C. the twin network can be trained via stochastic gradient descent, i.c., by minimizing the following loss with an off-the-shelf optimizer:
with (())
Emse (ó(t), r(t) + rō(t + 1)), where oft + 1) = 0, Vt
(12)
NUMERICAL RESULTS 4.1 INDEPENDENT R-COPS
We demonstrate the effectiveness of GDPG-Twin on four types of independent R-COPs by showing that it can improve the quality of solutions of fast and/or distributed heuristics with minimal overhead. These problems are maximum weighted independent set (MWIS), minimum weighted dominating set (MWDS), node weighted Steiner tree (NWST), and minimum weighted connected dominating set (MWCDS). They are all NP-hard, and need to be solved repetitively in a wide range of applications. For example, the MWIS problem appears in various schedulers (Pinedo) 2012] Joo & Shrofi 2012
Zhao et al., 2022a) and multi-on object tracking in computer vision (Brendel et al. 2011). The MWDS problem is encountered in wireless network clustering (Shahraki al. 2020). Multicast routing in
communication networks involves the NWST problem (Sun et al. 2020). The MWCDS problem can establish virtual backbone network in wireless multihop networks, that covers all the nodes with

---

Published as a conference paper at ICLR 2023
GCNN.3)
Approx. Ratio wrt.. Greedy-MWDS Meedy--WDD
1.000
Rotio Optimal
0.98
GCNN Twin
GONN33)- G5-200
0.96
MP Peschalidis15)
0.950
LGS [Joo12]
0.925
0.92
0.90
0.275
0.88
0.850
ER.
GRP
0.86
W5
100
150
200
250
300
100
300 350
Graph Size
Graph Size
Figure 1: Approximation ratios (Larger is better) of the vanilla and GCNN distributed heuristics MWIS problem (max), w.r.t. the optimal solver.
Figure 2: Approximation ratio (Smaller is better) of the GCNN-enhanced w.r.t the vanilla Greedy- WeWS for MWDS problem (min) on sets of random graphs.
Communi cation Complexisy
GCNN(3)+LGS
Graph
Reusing
Vanilla LGS
0.07
BA
N
lentralized Runtime
ER
N
GRP
2.05
WS
2.03
3.01
150
150
200
250
300
100
150
200
250
300
350
400
450
500
Graph Size
Graph Size
Figure 3: Average rounds of local message exchange for GCNN-enhance and vanilla LGS-MWIS solvers solve instance, excluding GCNN (N 00).
Figure 4: Average runtime of GCNN-enhanced Greedy- MWDS per instance graph size, in seconds, no reusing and infinity reusing N of Z.
the lowest cost in energy consumption security vulnerability (Oliveira et al. 2011). We refer the readers to Appendix for more detailed descriptions of the aforementioned applications.
We develop four similar ML pipelines respectively for the four R-COPs, in which the actor and twin networks are implemented by L-layer and 5-layer GCNNs, respectively, the baseline heuristics f(()) in (cc) selected as centralized distributed greedy solvers. The details of the four ML pipelines are Appendix
E for the equations of GCNN, Appendix for the detailed training configurations, H for the hyperparameters of GCNNs and brief descriptions of the chosen baseline heuristics. We aim to demonstrate the effectiveness of our proposed learning framework in closing the optimality gaps of some widely used fast heuristics for R-COPs, the cost of negligible overhead. e.g., an additional computational complexity of OL E|/N) or local communication complexity of (LLNN per instance on sparse graphs. We do not claim smaller optimality gaps than the state-of-the- art (slower and centralized) heuristics, nor that GCNN is the best candidate graph neural architecture for these problems. An appealing characteristic of our framework is its modularity, which allows the GCNNs being replaced by any other (non-convolutiona)) GNN while our approach is still valid.
and Appendix
The four COPs are widely applied in various wireless networks, involving graphs up to hundreds of nodes, and restricted runtimes from tens of milliseconds to a few seconds. Due to the dynamic nature and the lack real-world datasets wireless network topologies, we follow the norm wireless research by running experiments four sets of synthetic random graphs: Erdōs Erdōs-Rényi (ER) (Erdos & Rényi 1959), Barabási-Allas (BA) (Albert & Barabási] 2002). Gaussian Random Partition (GRP), and connected Watts- Strogatz small-world (WS) graphs. Each test dataset contains 2000 random graphs generated by graph model with parameters detailed Appendix F The optimality of a heuristic is evaluated by the average approximation ratio, Eạ (c (c)x())/ c x x)),, on test set Ω/ where (*) and (+) are respectively the solutions from the heuristic of interests and a reference algorithm. Only in MWIS, the optimal solutions from ZZhao al. 2022a) used as reference, in other COPs, greedy heuristics are the references.
MWIS: An independent (vertex) set for graph is subset of vertices not connected by any edges. The MWIS problem is to find an independent set on a vertex weighted graph that maximizes the total weight. The baseline heuristic is distributed local greedy solver (WIS)- (Joo & Shroff 2012)
7

---

Published as a conference paper at ICLR 2023
1.00
Approx. Rato w.r.. Central Greedy
Approx. Ratio wrrt. 5PH-NWVST
0.5
Grach
0:96
BA
3.0
ER
0.54
GRP
2.5
WS
Graph
Solver
2.0
G Greedy
ER
Greedy
1.5
GRP
0.50
1.0
WS
100
200
250
100
200
250
350
Graph Size
Graph Size
Figure 5: Approximation ratio (Smaller is better) of the
Figure 6: Approximation ratios (Smaller is better) of vanilla and GCNN -ehhnneede distributed heuristics w.r.t. a centralized heuristic for MWCDS problem on sets of random graphs. MWCDS is a min. problem.
w.r.t vanilla K-SPH-NWST NWST problem on 4 sets of random graphs. NWST is a minimization (min) problem.
with a local communication complexity of (log VI). We test multiple distributed MWIS solvers, including the GCNN-enhanced and vanilla LGS-MWIS, and a message passing (MP) algorithm
(Paschalidis et al. 2015) on set of 500 random ER graphs from (Zhao et al. 2022a). . 3 GCNNs are respectively trained by ad hoc RL (Zhao et al. 2022a GDPG-Twin, and ZOO set of 6000 ER graphs. The approximation ratios of the tested solvers w.r.t. the optimal solver are shown in Figure T GDPG-Twin (93.1 %) works equally well as the ad hoc RI. (93.2%). and slightly outperforms ZOO (92.7%) with only 1/2 to 1/2 evaluations of (: Z) (see Section 4.3) The GCNN can reduce the optimality gap of LGS-MWIS (89.77 7%) by 1/3, beating the MP algorithm (90.7%). Figure 3 shows that GCNN-enbanced and vanilla LGS-MWIS converge in 3 ~ 4 rounds in this test (MP algorithm converges in 2|V| rounds), where the former is slightly faster for a large N.
(iu al. 2020), on
MWDS: A dominating set for graph G (V. E) is subset D of V such that every vertex not in D is adjacent to at least one member of D. In the MWDS problem, every node is associated with non-negative weight, and the objective is to find dominating set of minimum total weight. The baseline heuristic a centralized greedy algorithm, Greedy-MWDSS as detailed in Appendix [H] The approximation ratio of the GCNN-enhanced Greedy-MWDS w.r.t. the vanilla Greedy-MWDS on the 4 sets of random graphs described earlier, are shown in Figure 2 On average, GCNN improves the performance of Greedy-MWDS by 11.42% on BA graphs, 6.8% on ER graphs, 3.0% on GRP graphs, and 2.6% on WS graphs. The improvement is more pronounced on larger graphs. As shown Greedy-MWDD on laptop of 4 CPUs no
in Figure 4 the average runtime of the CCNN-enhancer GPU (detailed in Appendix MT ranges from 32 to 78 milliseconds per instance, and is linear to the graph size, which can be further cut to 2-17 milliseconds for large reusing factor N.
In the NWST problem, we are given undirected graph G with node cost nion-neeee weight) and a subset of nodes called terminals. The goal is to find a minimum cost subgraph of & that connects the terminals. In the test, the terminals are selected by randomly removing 10% 50% nodes from a maximal independent set (MIS) on the graph. The baseline heuristic is a distributed greedy algorithm, Kruskal's shortest path heuristic (K-SPH-NWST) (Matsuyama) 1980; Bauer & Varmal 1996). The approximation ratio of the GCNN-enhanced K-SPH-NWST w.r.t. the vanilla K-SPH-NWST the 4 sets of random graphs, are shown in Figure 5 GCNN can improve K-SPH- NWST by 6.8% on BA graphs, 1.2% on GRP graphs. 1.4% on ER graphs 0.9% on WS graphs, and 0.9% on a real-world dataset of Internet backbone topology (Knight et al.) 2011) with | = 31.23 on average. The noticeable gain on BA graphs is meaningful to large real- world networks, such as the Internet, World Wide Web, and social networks (Posfai & Barabasi 2016 Ch. 5).
NWST:
MWCDS: In MWCDS problem, we are given an undirected and connected graph, and our goal is to find a minimum weighted dominating set that is connected. Our baseline heuristic is a distributed greedy algorithm (Dist. Grist..reedy.. whereas the reference algorithm is centralized greedy heuristic. Both MWCDS heuristies are implemented two steps (Sun et al., 2019): 1) find a MWDS, 2) connect the MWDS by solving NWST problem where the terminals are the solution of step 1. The approximation ratios of the vanilla and GCNN-enhancee distributed heuristics w.r.t. the centralized greedy heuristic on 4 sets of random graphs, each with 2000 graphs, shown in Figure Despite the large gap between distributed and centralized greedy algorithms, GCNN can improve the distributed greedy by 17.8% GRP graphs, 16.0% on ER graphs, 6.6% on WS graphs, and 4.0% BA graphs.
The average centralized runtimes of GCNN- distributed solvers for the MWIS, NWST, MWCDS problems respectively 0.017 0.05, 0.07 1.5, 0.08 2.0 seconds per instance, as
8

---

Published as a conference paper at ICLR 2023
Approx. Rabio to Vanilla 1SS.WIS
1.07
Median Backiog
1.0
1.08
0.5-
1.04
0.5
1.03
Mcan Backog
1.02
1.0
train
type
1.01
GDPG-Wiin-1 point Z00-2 points
Train Training
Vran
1.00
Validation
LockahsadRL [2hoo22]
GDMG-Wie
0.99
Z0O-11 points
ER
BA-mix BA Star10
Tree
BA
Star2o
Star30 15.5 10.5
10000
15000
20000 25000 50000
35300
2.056
4.848
5.307 5.5 5.669
0.004
Evaluations of h(-)
Figure 7: GDPG-Twin achieves similar sework-wwide mean and medium backlogs (smaller better) looka- head RL (Zhao et al., (202bb) training a distributed link scheduler, using only V/ evaluations of h(-) of it.
Figure 8: Performance trajectories of GCNN-enhanced LGS-MWIK trained by GDPG-Twin and ZOOs with 2-point and 11-point gradient estimations. Larger is better. GDPG-Twin needs fewer evaluations of h(-).
reported in Appendix I along with their estimated computational time (not the execution time) in distributed execution, as less than 0.18, 5.1, and 5.8 milliseconds, respectively.
4.2 REPETITIVE MWIS IN A GRAPH-BASED MARKOV DECISION PROCESS
Next, we compare GDPG-Twin an ad-hoc training method (Zhao al. 2022b) in the context of delay-oriented distributed wireless link scheduling, demonstrating its effectiveness and efficiency in long-term goal-seeking for R-COPs in a graph-based MDP. The distributed scheduler contains 1 1-layer GCNN and LGS in both methods, and a 5-layer GCNN is used as the twin in GDPG- EDPG-Twin. The node feature matrix, (t))
(t);; I(t)), encloses the packet backlogs q(t) and stochastic data rates I(() on all links (nodes in conflict graph). The state transition in 4f) is based on q(t + 1)
q()) + a() min(q((), 1(1) @ x(x) (4)). where a()) captures random packets arrivals, and x(1) captures binary scheduling decisions. The objective is to minimize the average backlog, EEEV, (t)]. see Appendix
A for detailed formulation. As shown in Figure 7 two distributed schedulers respectively trained by 5-step lookahead RL (Zhao al. 2022b) and GDPG-Twin achieve similar performance in terms of the mean and median backlogs on conflict graphs with different levels of centralization, as indicated by the number the x-axis. However, GPDG-Twin is 5 times faster than lookahead RL, as the former needs only 2 evaluations of h(-) per I, whereas the latter needs 10.
4.3 COMPARISON WITH ZEROTH-ORDER OPTIMIZATION IN TRAINING
The trajectories of relative performances of GCNN-enhanced LGS-MWIS (as detailed in Section 4. w.r.t. vanilla LGS-MWIS, under different training methods, are illustrated in Figure g where x-axis the number of evaluations of the con-differentiable h(-) (LGS-MWIS), Each point on the curve is the average value of 100 instances. During training, random weights are generated on on-the-fly fly for a training graph, whereas the weights on a validation graph are unchanged. GDPG-Twin and Z00 are configured with the same sampling radius and learning rate. In training, GDPG-Twin converges within only 1/3 to evaluations of h(.)) required by the fastest 700 based on 2-point gradient estimation, showing a better sampling efficiency than ZOO, by a factor of 2 to
CONCLUSION
We address repetitive combinatorial optimization problems under practical restrictions in run- time and/or distributed execution, by introducing non-differentiable policy network based on a hand-picked, fast and/or distributed heuristic, which is parameterized by continuous-val -vauue high- dimensional intermediate action from an actor GNN, The actor GNN optimized by graph- deterministic policy gradient with the help of a critic based on twin network that can predict the node- wise expected outcomes of the policy network. Through examples, we demonstrate that our approach can: 1) leverage the shared underlying topology of independent R-COPs, to reduce the average optimality gap of the fast and/or distributed heuristics, and 2) optimize the long-term objectives for R-COPs in graph-based Markov decision process. In terms of limitations, our work has not addressed the variance and worst-case of the optimality gap, which are important for many real-world applications. Our evaluation is based on synthetic rather than real-worke graphs. Moreover, the actor and critic networks in our framework would need further design for broader tasks, e.g., edge related R-COPs, In addition, we do not expect our work have any impact on social equality.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This research was sponsored by the Army Research Office and was accomplished under Cooperative Agreement Number W91 INF-19-2--26,. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
REFERENCES
R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Rev. Mod. Phys., 74:47-97, Jan 2002. doi: 10. 2..100//eMoodP
Fred Bauer and Anujan Varma. Distributed algorithms for multicast path setup in data networks. IEEE/ACM Transactions on networking, 4(2):181-191 1996.
William Brendel, Mohamed Amer, and Sinisa Todorovic. Multiobject tracking as maximum weight independent set. In CVPR 201 pp. 1273-1280. IEEE, 2011.
Sid Chi-Kin Chau, Khaled Elbassioni, Majid Khonji, et al. Combinatorial optimization of alternating current electric power systems. Now Publishing Incorporated, 2018.
Denis Cornaz, Fabio Furini, and Enrico Malaguti. Solving vertex coloring problems as maximum weight stable set problems. Discrete Applied Mathematics, 217:151-162, 2017.
Edsger W Dijkstra et al. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959.
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 linear time. In 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 19-24. IEEE, 2020.
Mark Eisen, Clark Zhang. Luiz F. O. Chamon, Daniel D. Lee, and Alejandro Ribeiro. Learning optimal resource allocations in wireless systems. IEEE Transactions on Signal Processing, 67(10); 2775-2790, 2019, doi: 10.1109/TSP.2219. 2908990..
Erdös and A. Rényi On random graphs Publ. Math. Debrecen 6, pp. 290-297, 1959.
Misa Fujita, Takayuki Kimura, and Kenya Jin' no. An effective construction algorithm for the steiner tree problem based edge betweenness. Journal of Signal Processing. 20(4):145-148 2016.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32: 1-13, 2019.
André Hottung, Yeong-Dac Dae Kwon, and Kevin Tiemney Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022. URL
net htt.aa/rrreee..eeeeooooooooooooo
Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network
guided local search for the traveling salesperson problem. In International Conference on Learning Representations, 2022. URL
Joo and N. B. Shroff. Local greedy approximation for scheduling in multihop wireless networks. IEEE Trans. on Mobile Computing, 11(3):414442, 2012.
Raka Jovanovic, Milan Tuba, and Dana Simian. Ant colony optimization applied to minimum weight dominating set problem. Proceedings the /2th WSEAS International Conference on Automatic Control, Modelling & Simulation, Catania, Italy, pp. 29-31, 2010.
JW Kendall. Hard and soft constraints in linear programming. Omega, 3():7709-755, 1975.
10

---

Published as a conference paper at ICLR 2023
E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song. Learning combinatorial optimization algorithms over graphs. In Advances Neural Info. Process. Systems, pp. 3348-6358, 2017.
Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings the AAAI Conference on Artificial Intelligence, volume 30, 2016.
S. Knight, H.X. Nguyen, N. Falkner, R. Bowden, and M. Roughan. The internet topology zoo. Selected Areas in Communications, IEEE Journal on, 29(9): -1775, october 2011. ISSN 0733-8716. doi: 10.1009/S44:2201111000.
David R Kraay and Patrick T Harker. Case-based reasoning for repetitive combinatorial optimization problems, part i: Framework. Journal of Heuristics, 2(1):55-85, 1996.
Sebastian Lamm, Christian Schulz, Darren Strash, Robert Williger, and Huashuo Zhang. Exactly solving the maximum weight independent set problem on large real-world graphs. In Proc. of the 21st Workshop on Algo. Engr. and Exper. (ALENEX), pp. 144-158. SIAM, 2019.
Ailsa H. Land and Alison G. Doig. An automatic method for solving discrete programming problems. Econometrica, 28(3):005-133 105-13,, 1960. doi:
Z. Li, Q. Chen, and V. Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Info. Process. Systems, pp. 539-548, 2018.
Sijia Liu, Pin-Ye Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred O Hero III, and Pramod Varshney. A primer zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Process. Mag., 37(5):43-54, 2020.
Gurobi Optimization LLC. Gurobi refeenceeeeeeencce reference manual, 2020.
com
Matsuyama. An approximate solution for the steiner problem in graphs. Math. Japonica, 24: 573-577, 1980.
Robin A Moser and Gábor Tardos. A constructive proof of the general lovász local lemma. Journal of the ACM (JACM), 57(2):1-15, 2010.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020.
Carlos AS Oliveira, Panos M Pardalos, et al. Mathematical aspects of network routing optimizution. Springer, 2011.
I. C. Paschalidis, F. Huang, and W. Lai. A message-passingg algorithm for wireless network scheduling. IEEE/ACM Trans. Netw, 23(5):1528-1541 October 2015. ISSN 1063-6692. doi: 10. 109.TT.T.. 2014.2338277.
Michael L Pinedo. Scheduling, volume 29. Springer, 2012.
Marton Posfai and Albert-Laszlo Barabasi. Network science. Cambridge University Press, 2016.
Jason Ramapuram and Russ Webb. Improving discrete latent representations with differentiable approximation bridges. In 2020 International Joint Conference on Neural Networks (IJCNN), pp. 1- 2020. doi: 10.1 1..1100NNNNN4000....0 000.040600050000227777555
T Mitchell Roddenberry, Nicholas Glaze, and Santiago Segarra. Principled simplicial neural networks for trajectory prediction. In International Conference on Machine Learning, pp. 9020-9029 PMLR, 2021.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 627-635 JMLR Workshop and Conference Proceedings, 2011.
11

---

Published as a conference paper at ICLR 2023
Amin Shahraki, Amir Taherkordi, Øystein Haugen, and Frank Eliassen. Clustering objectives in wireless sensor networks: A survey and research direction analysis. Computer Networks, 180: 107376, 2020.
Ajay Sikandar, Rajeev Agrawal, Manoj Kumar Tyagi, AL Rao, Mukesh Prasad, and Muhammad Binsawad. Toward green computing in wireless sensor networks: prediction-orientedd distributed clustering for non-uniform node distribution. EURASIP Journal Wireless Communications and Networking, (0200(1)1-11) 2020.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning (ICML), pp. 387-395, PMLR, 2014.
Xuemei Sun, Yongxin Yang, and Maode Ma. Minimum connected dominating set algorithms for ad hoc sensor networks. Sensors, 19(8):199, 2019.
Yahui Sun, Daniel Rehfeldt, Marcus Brazil, Doreen Thomas, and Saman Halgamuge. A physarum- inspired algorithm for minimum-coom relay node placement in wireless sensor networks. JEEE/ACM Transactions on Networking, 28(2):681 1-694, 2020. doi: 10. 10.1100 1091109TTT220002297777
Richard S Sutton and Andrew Barto. Reinforcement learning: An introduction. MIT press,
Cambridge, MA, 2018.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances Neural Information Processing Systems, 12:1057-1063, 1999.
Ekaterina Tolstaya, Fernando Gama, James Paulos, George Pappas, Vijay Kumar, and Alejandro Ribeiro. Learning decentralized controllers for robot swarms with graph neural networks. In Conference on robol learning, pp. 67 1-22.. PMLR, 2020.
Chrysafis Vogiatzis and Panos Pardalos. Combinatorial optimization in transportation and logistics networks. In Handbook combinatorial optimization, pp. 673-722. Springer New York, 2013.
Qing Wang. Knowledge-based approach for dimensionality reduction solving repetitive combinatorial optimization problems. Expert Systems with Applications, 184: 15502, 2021. ISSN 0957-4174. doi: https://doi.org// 10.
Yiyuan Wang, Shaowei Cai, Jiejiang Chen, and Minghao Yin. A fast local search algorithm for mini- mum weight dominating set problem on massive graphs. In Proceedings of the 27th International Joint Conference on Artifiiaal Intelligence, IJCAI-18, pp. 1514-1522. IJCAI Organization, 7 2018.
URL htt.t:tt//////t org/ 10. 24963/1 jeai 2018/210
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):279-292, 1992.
Hailin Wu, Fengming Tao, and Bo Yang. Optimization of vehicle routing for waste collection and transportation. International Journal of Environmental Research and Public Health, 17(14):4963, 2020.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24, 2021. doi: 10. 1..1099/NNLS 1.19TNNNLS.2220.2278833
Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing fanch-and--ound search trees learn branching policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3931-3939, 2021.
Zhongyuan Zhao, Gunjan Verma, Chirag Rao, Ananthram Swami, and Santiago Segarra. Link scheduling using graph neural networks. In arXiv preprint arXiv:2109.05530 2022a. URL
Zhongyuan Zhao, Gunjan Verma, Ananthram Swami, and Santiago Segarra. Delay-oriented dis- tributed scheduling using graph neural networks. In ICASSP 2022 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 9902-8906 2022b. doi: 10.1 NQ.10099CCASSSP492222222.9999999
12

---

Published as a conference paper at ICLR 2023
Dilay Çelebi. Inventory control in centralized distribution network using genetic algorithms: A case study. Computers & Industrial Engineering, $7:532-539 2015. ISSN 0360-8352. doi:
A APPENDIX: TWO EXEMPLARY FORMULATIONS OF REPETITIVE COPS
For link scheduling in wireless multiple networks (Joo & Shroff 2012 Zhao et al. 2022a b). the network state (())= = (V()), ((), where (V(1), {()) is the underlying topology of the conflict graph, in which a vertex i E V(() represents wireless link, and an undirected edge {i,j} E E(t captures the conflicting relationship between two links and j. The underlying topology of the conflict graph is supposed to change slowly compared to node features S(t).
The node feature matrix S(t) = (q(t); I(t)] encloses vectors of packet backlogs (queue lengths), q(t). and predicted link rates 1(t) all the links at time t. The backlog vector (t) evolves according to the scheduling decisions xt), and the state transition function (-) in (41) is
q(t + 1) = q()) + a(t) - min(q((), ((t) @ x()),
where a(t) captures random packets arrivals, and 1(t) follows a stationary random distribution.
The scheduling decision is subjective to a binary constraint, x; E {0, 1), Vi E V. and a constraint of independent set as, x; + x; I 1, vii.j} E E, corresponding to (2b) and (2) respectively.
In link scheduling for throughput maximization (Joo & Shroff 2012 Z Zhao et al. 2022a). 4e is
defined as utility function c(t) (t) @ I(t) prioritize wireless links with large backlogs and high
link rates. The heuristic h(-) in 4d is a distributed MWIS solver, e.g., LGS in (Joo & Shroff 2012)
and GCN-LGS in (Zhao et al. 2022a). The reward vector in (4c) defined as r(t) = c(t) O x(t).
and the expected return o(t) E.ST [r((]] for 4b). Since throughput maximization is equivalent
to optimize MWIS instances individually without considering their inter-dependencies, 4e) and
(41) together can be simplified as sampling process ~ Ω Therefore, t can be dropped, and the expected return becomes o(t) = Ee-r [c @ x]. and the objective function in (4a) becomes foty(((t)) = 1 = Ee-or (c xx) The formulation is then simplified as (3) with c = -q O
For delay-oriented link scheduling (Zhao et al. 2022b), the objective is to minimize the average back- log across the network and time, Eiv, [t). and the inter-dependencies between network states cannot be ignored. This objective can be formulated as average reward objective, implemented by setting the discount factor as = 1 and defining Soty (o(l)) =
= Eiyy [o:( The heuristic solver 1(()) in (4d) is LGS, and the reward vector in 44ch is r(t)= = q((1) q()), where q' (1) is the backlog vector under LGS with a baseline cost vector c c((l -((1-)
q(--1) 1(t I(t- 1). The objective function
Eev. (f)), which the first component is a constant. The cost vector in (4c) is obtained by GCN as c(t) = y (V(t), q(t) O 1(t); Op). which is trained to maximize the objective function.
in 44a) can then be transformed to BiEV.sS [q
These two examples show that independent R-COP is special case of R-COP in graph- MDP, and problems under similar settings can be formulated differently based on their objectives.
B APPENDIX: SGD FOR TWIN NETWORK IN INDEPENDENT REPETITIVE COPs
Give MSE loss,
1 |o| Σ 66, -o)3
Emse (6,
(13)
0
the partial derivative of Ease (ô. 0) w.r.t. the parameters of the twin network is
Olmse (ò)
Hemse do
(14a)
0
dó 00
2
dó
j E Epiol
(c @ x
(14b)
00,
2
d6
Eqjel
) ① x
(14c)
00.
13

---

Published as a conference paper at ICLR 2023
where from (1bb to (14c) based on the linearity of expectation. Based (1c)). by drawing C ~ 52", we have the following unbiased stochastic gradient estimation:
mse (ó, o)
Ol (Ö o)
Ep
(15)
d0.
d0.
where
msse (6.0)
2
d6
66
(16a)
00
ae
dL mee (Ó, (
(16b)
de
Therefore, the stochastic gradient estimation for the parameters of the twin network is
Veeeme (Ó, o) Ve, (o, C x).
(17)
C APPENDIX: SGD FOR TWIN NETWORK IN R-COPs IN GRAPH-BASED MDP
We define a return vector supported on the nodes the graph as
T-t
g(()
Kr( k)
(18)
k=
which can be expressed in a recursive form
g(t = r(t) + (g 1). where g(t) = 0, V>
(19)
The outcome (value) vector of state ((t) is the expected return vector under policy Op.
(t) = Ee, [())
(20)
The gradient Ve, Emse (ô(t), ot)) can be found by the following partial derivative
ds ((t),,(() mse ( o(t) 0ō(t)
(21a)
00:
0ō(t)
de.
2 (6(1) Ee, [B()))(()) TT((()
(21b)
[t)
00
2
(o(t) g()) 06(1)
Ee, [o(t)]
(21c)
00
where from 21b to (1ch based on the linearity of expectation, and that ó(f) a function of G
generated by the twin network, defined in (12). Based on I9 we have the following unbiased
estimation of the partial derivative (2la)
mm (o(t). o(t)) Eo, mmse o(t)
(22)
00.
d
where
Ol @m o())
2
(ô(t) ((t) 06(()
(23a)
00
[o(t]]
2
[6(() r(t) 7g(( + 1)(G(() 0o(t)
(23b)
[o(1]
(23b), r(f) is the reward vector collected under current state G(t), as defined in 10c)). and
g)(+)) is the return of the next state G 1), evolved from the current state G(t) according to
(IOF.. The return of the next state G(t + 1) is estimated as g(t + 1) = o(t + 1) by the twin network,
as defined in 12). As result, we have the following approximation
rtt) + 7g(t + 1))g(t)= zs r(t) + 7ō(t + 1).
(24)
Plugging to 23b we have
me (o(1), (())
@mmse (o r(t) + nō( + 1))
(25)
a0
ae.
Therefore, the stochastic gradient estimation for the parameters of the twin network is
V Emse (o(1), Ve, (m)))))(((()))((( 70(1 1)))
(26)
14

---

Published as a conference paper at ICLR 2023
D APPENDIX: ALGORITHMIC PROCEDURES OF GDPG-TWIN
Algorithm Twin for R-COPs with Independent Instances
Input: 52 22 h(-),,)))))) (h-)),p,p000 Oc: E, B,
Output: Z or @ θ
1: Initialize Z or p,, O randomly
pretrained models, E5 (c)
2: for e (1.2.....,
do
3: 2₂ = Ø, Q. Ø /* Clear gradient buffers */
4: for b E (1..... B} do
5:
Draw G(V,8) 22 E Ω 1s Draw data from training dalaset target distribution */ if Actor network is used then
6:
7:
Z = (VVV ē; pp
8:
end if
9:
Z + NO), N U(-C,c) / Random policy sampling */
ftwin (V,E, c, Z(); O")
x= (ne &, c; Z based on h(.)) in 5cb and ftoo(:) 5d
12:
Estimate gradient Ve. ( c @ x) for critic
Q. Q. (Ve. (ô, 1 x)}
Estimate policy gradient Vz1 â based on if Actor network is used then
15:
Estimate gradient Ve, _ Ve, ,, for actor
17:
2 - 1
else
19:
Q + Op U
20:
end if
21:
end for
22:
O < O a 2. V Emc Ox
23: + a Eq. Vz1 or O t θ - a,, (Ve,1
24:
end for
25: Output Z or θ p. O
For the four demonstrated R- R-POss with independent instances, we set the hyperparameters of training procedure in Algorithm as follows: 0pp a, 0.0001, F 25, B 100, 0.15.
15

---

Published as a conference paper at ICLR 2023
Algorithm 2 GDPG-Twin for R-COPs in a graph-based MDP
Input: , ./.,,(((,),,))) ap, Oce, T" E
Output: p. O
1: Initialize pp. + randomly or as pretrained models
2: for E .1....... E) do
3: 2. 0, Op = Ø, Q. = Ø 1 Clear experience & gradient buffers
4: Initialize state G(1) = (V(1),(11))())) Q2t (or 29 for ergodic MDP)
5:
fort (1.....TT T) do
6:
c(t) =
7:
6(t) Stwin (V"))n (()) c(t); )
8:
Obtain decision vector x(t) based on (10d)
9:
Observe reward vector r(t) according to (1cc)
10:
Update state feature S(t + according to T
Estimate stochastic policy gradient Ve, (o())) based on [1]
12:
Op + 2p U { Ve,fobb (o(t))
Q. + 2. U (()()))) >}
14:
end for
for (I....,?) do do
16:
Fetch r(f), ö(t), ö(t + 1) from Q.
17:
Estimate stochastic gradient Vo. loce (ô(t), + 70(t + 1)) for critic
18:
Qc Q. UVV., emse (ó(t), r(t) jō(t 1)))
19: end for
20: O. O Eg Ve. mse (o(t), r(t) + r0(t + 1))1
21: θ - θ + Op V Ve, Sarj (o(1) / Objective maximization */
22:
end for
23:
Output O.
For the demonstrated delay-oriented link scheduling (Zhao al. 2022b), we use the following
hyperparameters in training described in Algorithm Opp 02 0.0001, 7 64, E 200. The
types and mixture of the training graphs, random processes, etc., are identical to (Zhao et al. 2022b).
E APPENDIX: GRAPH CONVOLUTIONAL NEURAL NETWORKS
An L-layer GCNN is implemented as follows: Given the input feature (0) = S supported on graph G, the output is Z (t,)) fGcN (g, S; O), where an intermediate Ith layer of the GCNN is
-'=at at (s' (s + -
(I......)
(27)
In C is the normalized Laplacian of graph G, @,, O E R9-11 are the trainable parameters, g and gi are the dimensions of the output features of layers 1 and I, respectively, and ar(.) is an element-wite activation function.
In distributed system, 27 can be implemented by the following local operation on node v E V,
S
St.. oi S/-10'
S/-1
Σ
0
(28)
d(v)d(u)
NEN((t)
where St., E Rlxa is the uth row of matrix S', which captures the features on node v d(v) is the degree of node and (v)) is the set of neighboring nodes of node
F APPENDIX: CONFIGURATIONS RANDOM GRAPHS FOR TRAINING AND TESTING
p E U(0.15, 0.35). E [U(10, 30) Training graph size [ E (100, 150, 200, 250, 300}. Testing graph size [V] (100, 150, 200, 250, 300, 350, 400, 450, 500) (varies by problem).
16

---

Published as a conference paper at ICLR 2023
ER: size [V], edge probability 1./e. BA: size [,. number of edges to attach from new node to existing nodes m = pk WS: size [Vi, each node is joined with its k nearest neighbors in a ring topology, p. the probability of rewiring each edge. GRP: size [V], mean cluster size k. shape parameter min(7, k),, prohability of intra-cluster connection p. probability of inter cluster connection max p/3). For MWIS problem in Section 4.1 the test set of 500 ER graphs and the corresponding
optimal solutions are from httpp:://gli 2022ap.
con./zhorgyuanzhao//licse
(Zhao et al.
G APPENDIX: APPLICATIONS OF THE FOUR EXEMPLARY R-COPs
G.1 MWIS IN SCHEDULING AND COMPUTER VISION
Definition: An independent (vertex) set for graph is a subset of vertices not connected by any edges. The MWIS problem is to find an independent set vertex weighted graph that maximizes the total weight.
MWIS for wireless scheduling: MWIS can be applied link scheduling in wireless multihop networks with orthogonal multiple access (Joo & Shroff) 2012 Zhao et al. 2022a). In a wireless multihop network, wireless link refers to a pair of nearby wireless transceivers that can directly talk to each other. In orthogonal multiple access, two links would conflict with each other if they share the same transceiver (which can only be tuned to one link at time), or they would block out each other if activated simultaneously (e.g., any transceiver(s) of a link are located too close to any transceiver(s) of the other link interfere the reception of wireless signal). each time slot, a link scheduler -eiiht scheduler) would determine a set of non-interfering links to be activated, so that it would maximize the total utility of the wireless network. Mei-ht scheduling is essentially finding MWIS on the conflict graph of the wireless network. which is defined as follows: each vertex in the conflict graph is a link in the wireless network, and an edge captures the conflict relationship between two links. For example, with a per-link utility function based on the length of backlogged data packets of each link, Weight scheduling can achieve the maximum throughput (the amount of data packets transmitted in a time slot) of the wireless network. The typical length of time slot in various wireless communication protocols ranges from 1 ~ 100 milliseconds, which means that a Max- fax-Weight scheduler needs solve an MWIS instance every 1 ~ 100 milliseconds. Meanwhile, the topology of the conflict graph in wireless scheduling (determined by the topology of the wireless networks and physical locations of transceivers) evolves at much lower pace, such as seconds to minutes for mobile wireless networks, or remain the same if all the transceivers (such as microwave towers and wireless sensors) are static.
Graph coloring problems are also applied to wireless scheduling, especially, multi-channel wireless scheduling. The conflict graph is formulated similarly in the previous single-channel scheduling, but instead of finding MWIS, each node in the conflict graph (link in the wireless network) is assigned a color representing a particular channel, so that neighboring nodes (conflicting links) will never have the same color (channel). In Cornaz et al. (2017), the four types of graph coloring problems: Vertex coloring problem (VCP), equitable vertex coloring problem (ECP), Max-coloring (Max-Col) which can be seen the weighted version of VCP, and Bin Packing Problem with Conflict (BPPC), can be converted to solving MWIS on an associated graph.
MWIS for multiobject tracking in computer vision: In multiobject tracking (Brendel al. 2011). a detector first identifies a set of objects in a video frame, records the following properties of the corresponding bounding box of each object: location, size, the histograms of color, intensity gradients, and optical flow. Next, the detected objects across different video frames needs to be linked according their properties to maintain their unique identities. The second step formulated as finding a MWIS on graph, in which nodes represent candidate matches (of two objects) from every two consecutive frames, referred as tracklets; node weights encode the similarity of the corresponding matches; and edges connect nodes whose corresponding tracklets violate the hard constraints that no two matches share the same object. If there are 10 objects in each of the two consecutive frames, there would be 100 tracklets. The MWIS on such graph is a set of matches that maximize the total similarities of tracklets, resulting in the most plausible tracking of multiple objects. In this formulation, MWIS instance needs to be solved every video frame (24, 30 frames per second), while the topology of the graphs of consecutive MWIS instances would be similar since consecutive frames in a typical video stream would remain similar.
17

---

Published as a conference paper at ICLR 2023
G.2 MWDS IN WIRELESS SENSOR NETWORKS AND COVERING CODES
Definition: A dominating set for a graph 9 = (V, is a subset D of V such that every vertex not in D is adjacent to at least one member of D. In the MWDS problem, every node is associated with non-negative weight, and the objective is to find a dominating set of minimum total weight.
MWDS for clustering in wireless sensor networks: Wireless sensor networks are type of ad-hoc network for monitoring purpose.. It usually include a large number of sensor nodes, which are resource-constrained (such as battery power), but can connect to other nodes of the network for transmitting sensed data. Each node can also forward data from neighbors to the sink (or gateway, base station, server, etc.) (Shahraki et al., (020). Clustering is one of the most popular techniques for the topology management of wireless sensor networks. It organizes sensor nodes into set of groups called clusters, each cluster has one or more cluster heads which gathers data from other members of the cluster and send the (fused) data to the sink directly or indirectly. Using clustering techniques, resource-constraing sensor nodes do not need to send their data to the sink directly, which can cause energy deplction, resource consumption inefficiency and interference. Clustering as MWDS problem, where the cluster heads form a dominating set so that the rest of the sensor nodes can directly reach at least one cluster head. By defining the node weight as the cost of being cluster head, MWDS can minimize the total cost of wireless sensor networks, such as energy consumption or quality of service. To maximize the lifetime of the wireless sensor network, it may need to select different set of cluster heads once in a while to avoid draining the battery of cluster heads. The node weight would change based on the battery levels of the sensor nodes.
be formulated
G.3 NWST FOR MULTICAST ROUTING WIRELESS NETWORKS
Definition: In the NWST problem, we are given an undirected graph G with node cost (non-negative weight) and a subset of nodes called terminals. The goal is to find a minimum cost subgraph of G that connects the terminals.
NWST in multicast routing: A multicast route a network route that connects more than two nodes at the same time (Oliveira et al. (01T). Multicast routing is applicable to networking scenarios where data needs to be shared by a group of users, such as a software company sends out a security patch to the computers across the Internet installed with its software, or a company pushes notification to the smart phones installed with its mobile app. In these example, the Internet would be the graph, the server and the recipients are defined as the terminals in the Steiner tree problem, and the non-terminal nodes are the routers, gateways, and other computers on the Internet.
Multicast routing in wireless multihop networks can be formulated as node weighted Steiner tree (NWST) problem (Sun et al. 2020). The graph models the network, c.g., a node represents a wireless device and an edge represents a link between two wireless devices. The terminals in the NWST are the subset of wireless devices that need to connected with each other, and the non-terminal nodes are the rest of the wireless devices in the network. The node weight captures the cost of non-terminal node relaying packets, such as the consumption of energy, bandwidth, and/or CPU load, By formulating the multicast routing as NWST, we can connect all the terminals at minimal total cost. Whenever there is request to establish a multicast route, a NWST problem in the network needs to be solved. In medium to large-scale wireless networks, distributed algorithms are always preferred since it does not require a centralized coordinator to collect the real-time network state and compute the solution.
G.4 MWCDS IN MOBILE AD-HOC NETWORKS
Definition: In MWCDS problem, we are given an undirected connected graph, and our goal is find minimum weighted dominating set that is connected.
MWCDS for virtual backbone computation: In mobile ad-hoc networks, a virtual backbone is set of nodes that can be used to take routing decisions and that act as proxies for routing packets OOlieeira et al. 201 It can reduce the amount of routing information shared among nodes of the system, by requiring only subset of nodes to be actively involved in routing decisions. Formally, we would define the mobile ad-hoc network as a undirected graph, in which each node represents mobile device, and each edge represents a link between two mobile devices. A virtual backbone needs to a connected subgraph so that packets from one node can always reach to another node in the virtual backbone. A node in the network needs to be either member of the virtual backbone
18

---

Published as a conference paper at ICLR 2023
or adjacent to at least one member of the virtual backbone, that it can reach to the rest of the network. Therefore, a virtual backbone needs to be a dominating set of the graph. Moreover, since members of the virtual backbone take the responsibility of routing, which comes with extra cost in battery power consumption and routing packets, we want to minimize the total cost of implementing a virtual backbone. Therefore, the computation of a virtual backbone is to find the minimum weighted connected dominating set of the network. The virtual backbone in mobile ad-hoc networks needs to be re-established after a while, in order adapt to the changing traffic conditions, network topology, as well as the battery levels of the mobile devices. The network topology may change slowly, whereas the battery levels of mobile devices and traffic conditions may change more frequently. Re-establishing the virtual backbone once while could avoid draining the batteries of the members of the virtual backbone. Moreover, virtual backbone computation requires distributed algorithm to find the MWCDS, since there is no server or base-station in mobile ad-hoc network to perform such computation.
H APPENDIX: ML PIPELINES AND BASELINE HEURISTICS
H.1 MWIS PIPELINE
We adopt the GCN-LGS pipeline in Zhao et al. 2022a) as the actor network, which comprises a 3-layer GCNN followed by distributed local greedy solver (LGS-MWIS) (Joo & Shroff 2012).
The actor GCNN is configured as follows: the dimensions of GCNN layers are 9i = 32,7 1, 2,
and 90 0s = 1, the hidden layers employ leaky ReLU activation, while the output layer ReLU activation. The GCNN outputs vector
B The local funetion in (5d) is instantiated
multiplier, fco Z:) = C, The twin network is implemented by a 5-layer GCNN, in which the hidden layers have dimensions of gt = 64, 1 .....: 4 and leaky ReLU activation, and the output layer has a dimension of gs = 2 and Softmax activation. The training takes about an hour on a server with 16 GB memory, 8 CPUs and GPU (Nvidia 1080 Ti).
The basic greedy heuristic first sorts the nodes by their weight in decreasing order, then iteratively adds a node the solution and removes the node and its neighbors from the sorted list, until the list is empty.
The distributed heuristic LGS-MWIS (Joo & Shroff 2012) iteratively builds a solution as follows: in an iteration, each node compares its weight with its neighbors: if node has the maximal weight in the neighborhood, it marks itself as and broadcasts a control message to its neighbors, who then mark themselves as -1; the unmarked nodes enter the next iteration. When all nodes are marked, the solution the set of nodes marked as LGS-MWIS has an average local communication complexity of Olog V/ on general graphs. The centralized greedy algorithm and LGS-MWIS are detailed in (Zhao et al. 2022a Algo and Appendix Algo 1).
For MWIS problem in Section 4.1 the test set of 500 ER graphs and the corresponding optimal solutions are from https: / thub. caub.ccmm/ htt.://///ooooounauaaaaoiiaaaaaa diittga (Zhao et al. 2022a).
H.2 MWDS PIPELINE AND GREEDY-MWIDS
We augment Greedy-MWDS with 5-layer actor GCNN and the same local function in the MWIS pipeline in Appendix H.T The actor GCNN is configured as follows: the input and hidden layers have dimensions of 9i 32,7 7 = 1...., and leaky ReLU activations, the input and output dimensions are 90 = 9s = 1. and the output layer employs ReLU activation. The twin is also implemented by 5-layer GCNN configured the same as the twin GCNN in the MWIS pipeline in Appendix H.. except that gr = 32, I = 1,...,4. 4. The GCNN is trained on randomly generated ER graphs of 100 to 300 nodes. The training takes about an hour on a server with 16 GB memory, 8 CPUs and 1 GPU (Nvidia 1080 Ti)
The greedy algorithm, Greedy-MWDS, iteratively builds solution by adding to the solution the most cost-effective node from the vertices not yet in the solution, marking its neighbors as covered, until all nodes are either in the solution or covered. A good metric for the cost-effectiveness of node v E V is (Jovanovic et al. 2010)::
c(v)
((b) 1 EweN(wnw c(u)
W' = (ili e (D' A (D'UN(D)))
(29)
19

---

Published as a conference paper at ICLR 2023
where smaller (t) means better cost-effictivenness, c(u) is the weight of node e, D' is the partial solution (initialized as Ø), (.)) refers to the neighbors a node or a vertex set, W is the set of uncovered nodes.
An alternative greedy algorithm Streedy-MWIDS selects the most cost-effective node only from the uncovered vertices in each iteration, which builds an independent dominating set (IDS). Greedy- MWIDS can be implemented by the distributed LGS-MWIS (Joo & Shroff 2012). and is used as part of the distributed heuristic for the MWCDS problem in Appendix H.4
H.3 NWST PIPELINE AND BASELINE HEURISTICS
The actor, twin, and local function are configured the same as in the MWDS pipeline in Appendix H.2 The input node feature for the actor and twin GCNNs is one-hot encoded indicator of whether node is a terminal. The GCNNs are trained on randomly generated GRP graphs with 100 to 300 nodes. The training takes 5 hours on server with 16 GB memory, CPUs and GPU (Nvidia 1080 Ti).
Shortest path heuristic (SPH) [Matsuyama 1980) initializes the terminals as a set of subtrees; starting from an arbitrary subtree, it iteratively merges with its nearest subtree through the shortest path. The distance of path is the total cost of nodes on it, where terminals have zero cost. The algorithm terminates when only one tree is left. The shortest path found by Dijkstra's algorithm (Dijkstra et al., 1959). Kruskal's s SPH (Bauer & Varmal 1996) (K-SPP) (KSPH) is distributed variation of SPH. in which every subtree merges with its nearest subtree until only one tree is left. SPH has an approximation ratio of 2 (Matsuyama 1980).
H.4 MWCDS PIPELINE, BASELINE AND REFERENCE HEURISTICS
low complexity heuristic for MWCDS problem (Sun et al. 2019) can be implemented in two steps: 1) find MWDS, 2) connect the MWDS by solving NWST problem where the terminals are the solution of step 1.
In our baseline heuristic, choose Greedy-MWIDS MWIDD in Appendix H.2 for step 1, and K-SPH-NWSH in Appendix H.3 for step 2, and treat them as a single distributed greedy heuristic (Dist.Greddy)
Our reference algorithm is centralized greedy heuristic, composed of Greedy-MWDS in Ap- pendix H.2 for step 1 and SPH-NWST in Appendix H.3 for step 2.
The actor GCNN is configured as follows: the dimensions of input and hidden layers are gI 32, I 1.....4 4 and leaky ReLU activations, the input and output dimensions are gu = 1, 1.9s = 2, and the output layer employs linear activation. The actor outputs Z E IR M|x2 and the local function is single neuron, (C,, Zz+) Re (Z,,,c; + Z. The twin network is a 5-layer GCNN configured identically as the twin in Appendices H.2 and H..3 except that its input dimension fits the output dimension of its own actor GCNN. The GCNN is trained on GRP graphs of 100 to 300 nodes. The training takes 8 hours on server with 16 GB memory, CPUs and GPU (Nvidia 1080 Ti).
I APPENDIX: CENTRALIZED RUNTIME IN SECONDS
We report the actual runtime of GCNN-enhanced COP solvers demonstrated in Section 4 measured on a laptop computer (Macbook Pro. 16GB memory, 2 GHz Quad-Core Intel Core i5, CPU only). It should be noted that these runtimes based on our Python code, of which the implementation could be further optimized for running speed.
For the examples demonstrated by distributed COP solvers, the centralized runtime does not represent their distributed runtime. Therefore, we report both the total centralized runtime and the per-node centralized runtime for each distributed solver. The latter represents the estimated computational time in distributed execution. However, the major component of distributed runtime for distributed solvers the communication time rather than the computational time, which could not be measured in our setting. In general, the GCNN no longer dominate the total runtime for these distributed COP solvers. For MWIS in Figure (a) and 9b). the centralized runtime distributed COP solvers are still linear to the graph size. For NW ST (Figures and IO(b))))) and MWCDS (Figures [[(a] and [ind[110 ((b)), the major component of the centralized runtime is Dijkstra's 's algorithm for the shortest path, which has a time complexity of O(I)22 O((V) + +|8) log VV).
20

---

Published as a conference paper at ICLR 2023
0.06
0.00018
GCNN(3)+LGS
Centralizen liziddddd runtime per hade (4)
0.00036
0.05
LGS
Centralized runtime
0.04
0.00032
0.00030
0.03
GCNN(3)
0.02
100
250
130
150
200
250
300
Graph Size
Graph
(a)
(h)
Figure 9: Average centralized runtime GCNN-enhanced LGS-MWIS per instance, with reusing factor
N 1. The total runtime broken down to GCNN(3), as a one time overhead, and LGS, as the runtime for N = co. (a) Total centralized runtime by graph size, (b) Per node centralized runtime by graph size, representing the estimated computational time distributed execution. Notice that the major component of distributed runtime is the communication time.
Centralized runtime per node (8]
0.005
BA
Centralized runtime (6)
ER
1.2
b.004
GRP
Graph
WS
0.003
0.8
GRP
WS
100
150
200
250
300
100
150
200
250
300
Graph Size
Graph Size
(a)
(b)
Figure 10: Average centralized runtime of GCNN-enhanced K-SPH-NWST solver per instance, with reusing factor 1. (a) centralized runtime by graph size, (b) node centralized runtime by graph size, representing the estimated computational time in distributed execution. Notice that the major component of distributed runtime is the communication time.
2.00
0.006
Centralized runtime per node
Centralized runtime (s)
0.005
1.50
0.004
1.25
BA
0.003
ER
GRP
GRP
0.75
WS
0.002
WS
0.50
0.001
0.25
3,000
Graph Size
Graph Size
(a)
MWCDS instance, with reusing factor N = 1. (a) Total centralized runtime by graph size, (b) Per node centralized runtime by graph size, representing the estimated computational time in distributed execution. Notice that the major component of distributed runtime communication time.
Figure 11: Average centralized runtime of
21


Reviews:
[{"review_id": "xillbSOUDn", "reviewer": "Reviewer_XHWP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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 novel GNN and RL-based approach to R-COPs with hard constraints and without supervised labels. The proposed approach has several advantages compared to existing methods and show clear improvements emperically. ", "summary_of_the_review": "The paper is well-written and the proposed method is novel and has clear improvements.", "strength_and_weaknesses": "Strength:\nThe proposed method is novel and gives clear improvements compared to existing methods. The introduction and literature review gives a good context of the problem. The experiment results are strong.\n\nWeakness:\nCould improve the citation style.", "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": {}}, {"review_id": "joryHPXRPW", "reviewer": "Reviewer_fA3E", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 introduces a novel formulation for repetitive combinatorial optimization problems (R-COPs) over graphs that is particularized to both independent R-COPs (i.e., problems where the graph data is independent at different time steps) and graph MDPs. It also introduces a novel actor-critic framework to solve these problems---GDPG-Twin---where the critic consists of a differentiable twin model that is trained to represents the states resulting from the application of a policy to a non-differentiable network process (typically based on a greedy heuristic). ", "summary_of_the_review": "The contributions of the paper are novel significant, but the presentation is poor. I recommend acceptance conditional on improving notation and presentation in the rebuttal.", "strength_and_weaknesses": "Strengths:\n\n- The proposed learning framework is novel and broadly applicable.\n- The numerical results are convincing:\n    - On synthetic graphs, GDPG-Twin either improves upon or achieves faster computations than the conventional heuristics in four independent R-COPs, and optimizes the long-term objective in a graph MDP.\n    - GDPG-Twin with random sampling around the current policy converges faster and has better sampling efficiency than the comparable method (ZOO).\n\nWeaknesses:\n\n- While the proposed framework is pretty general and is tested on four examples of COPs, many of the examples are very similar. It would have been interesting to see how the framework fares in different types of COPs, such as graph coloring (which also has applications in scheduling).\n- The graph machine learning models used to parametrize GDPG-Twin are not described in detail. Moreover, the effect of the choice of parametrization is neither discussed nor illustrated with numerical experiments. \n- Very little intuition is given as to the real-world applications of MWIS, MWIDS, NWST, and MWCDS and the differences among them. It is understandable that there is no real-world data for these problems, but a better description of their application to real-world problems would help ground the paper and strengthen its contribution. \n- The paper is very hard to understand in its current form. See below.\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": {}}, {"review_id": "fXRaTuBoiS", "reviewer": "Reviewer_gr9w", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 paper proposes an RL approach to address two families of CO problems: (i) independent repetitive COPs and (ii) COPs embedded in graph-based MDPs. It claims to learn reusable node and edge information to improve existing heuristics to these problem. The proposed approach is illustrated on graph CO problems.\n", "summary_of_the_review": "I would vote for reject because the paper is not clear and lacks mathematical correctness. \n\n\n******* **After Rebuttal** ******\n\nI thank the authors for their replies. After reading the revised manuscript and the extensive rebuttal, I think the paper is more clear and many of my questions were answered. I still have a few minor doubts/remarks:\n\n* The first statement of the abstract: “We propose an actor-critic framework for graph-based machine learning pipelines with non-differentiable blocks, and apply it to repetitive combinatorial optimization problems (COPs) under hard constraints” but the paper really focuses on repetitive COPs and the framework is only defined for repetitive COPs.\n* In Eq (4), should the sets of vertices $\\mathcal{V}(t)$ and edges $\\mathcal{E}(t)$ depend on $t$? They don’t seem to be updated for different $t$s. Only $S(t+1)$ is defined in Eq (4f).\n* In (4b), since the expectation is taken with respect to the heuristic $h$ and cost $\\psi$, are these functions stochastic? \n* This expectation in (4b) should also depend on $f_r$ and $f_s$ which are defined as stochastic.\n* In (3a), $h$ does not appear in the expectation — is it deterministic there?\n* The paper says that the local function in (5d) “…can be chosen as, e.g., a multiplier, a single neuron, or even a small neural network,..”  If it is a neural model then it is not clear how it can be learned within the framework. I see in the Appendix that in the experiments the local function is “a multiplier”: $f_{loc}(c_i, z_i) = c_i z_i$ — therefore no learning needed. I think the paper should explain how $f_{loc} $ can be trained or remove the statement that it can be a neuron/neural network.\n\nDetails:\n* In Eq (7) $\\bar{c}$ could be used for readability.\n* Sec 2.2: “$0 \\leq \\gamma \\leq 1$”: the discount factor should be strictly positive \n* Sec 3.1 “$0 \\leq \\alpha_p \\leq 1$\": similarly the learning rates $\\alpha_p$ and $\\alpha_c$ should be strictly positive, and I’m not sure about why the paper uses 1 as an upper bound. Of course in practice the learning rate is much smaller than 1 but I don’t think it **has** to be smaller than 1.  \n\nOverall I think the paper presents an interesting approach to improve the performance of heuristics for repetitive COPs over graphs. The proposed framework is successfully demonstrated on 5 problems. Therefore I am happy to increase my score and confidence level.\n", "strength_and_weaknesses": "**Strengths**\n1. The paper cites and explains a lot of related works\n1. The approach is tested on 4 problems\n\n**Weaknesses**\n1. Important issues with the formalization of the problem or the notations, that make understanding the primal goal/setting of the paper difficult:\n    * The initial problem Eq (1) optimize f_{obj}(o) where o = f_net(G) but G is the network state that looks like the input. So I don’t see what is the decision variable here\n    * Sec 2: “We define a function space F as a set of functions that will output solutions satisfying all the constraints of the COP in (2).” What is the input of these functions? \n1. Some mathematical statements lack rigor or are wrong in my opinion :\n    * Sec 2.1: We relax the objective function in (2a) to its expectation over Ωc. How is this a relaxation (in the mathematical optimization sense)? Problem (3a-b) is another optimization problem, where the decision variable is F_net\n    * Sec 2.1 “optimal solution for (3), x^∗ = f_net^*(V, E, c), is still an exact solver for (2) for every given c”.  f_net^* is by definition the optimal solution when minimizing the expected objective over c. Therefore for a given c, there is no guarantee that it is optimal. \n    * Sec 3.1. The fct h in eq (5) is presented as a valid heuristic, but it looks like a constraint in (5c). Is it an input ? (in which case h \\in F should not appear as a constraint);  Or a variable ? (in this case how is it linked to the decision variable Z?)\n1. The paper is very dense and was not easy to read for me — although I have a strong background in CO and ML but admittedly not so much in network problems specifically.\n    * E,g. Sec 1.1 could use some more structure like paragraphs \n    * I don’t understand: Sec 1.2: “Imitation learning …. However, it requires a good guiding algorithm, which set the upper limit of the system and could be costly” \n    * Even after reading the paper carefully, the first sentence of the conclusion  is still hard to get \"...address repetitive combinatorial optimization problems by parameterizing the input node weights of a non-differentiable, fast and/or distributed heuristic, fnet(·), through a continuous-valued high-dimensional action generated by an actor GNN\"\n\n", "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: Accept: poster