Neural Topological Ordering for Computation Graphs
Authors: Mukul Gagrani
Corrado Rainone
Yang Yang
Harris Teague
Wonseok Jeon
Roberto Bondesan
Herke van Hoof
Christopher Lott
Weiliang Will Zeng
Piero Zappi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Combinatorial Optimization
Graph Neural Network
Directed Acyclic Graph

Abstract: Recent works on machine learning for combinatorial optimization have shown that learning based approaches can outperform heuristic methods in terms of speed and performance. In this paper, we consider the problem of finding an optimal topological order on a directed acyclic graph (DAG) with focus on the memory minimization problem which arises in compilers. We propose an end-to-end machine learning based approach for topological ordering using an encoder-decoder framework. Our encoder is a novel attention based graph neural network architecture called \emph{Topoformer} which uses different topological transforms of a DAG for message passing. The node embeddings produced by the encoder are converted into node priorities which are used by the decoder to generate a probability distribution over topological orders. We train our model on a dataset of synthetically generated graphs called layered graphs. We show that our model outperforms, or is on-par, with several topological ordering baselines while being significantly faster on synthetic graphs with up to 2k nodes. We also train and test our model on a set of real-world computation graphs, showing performance improvements. 

Neural Topological Ordering for Computation Graphs
Mukul Gagrani" Qualcomm Al Research
Corrado Rainone" Qualcomm Research Prainone@@ti.uuallcom. qua..uall.cmmmmoo com
Yang Yang Google LLC
mgagrani&qtil tuwlliii..lalloooooaaaaaaao gomm.com.........m..mmmmmmmm.... com
Harris Teague
Wonseok Jeon
Herke Van Hoof
Qualcomm Al Research
Qualcomm AI Research
University of Amsterdam, Netherlands
Weiliang Will Zeng Qualcomm Research
Piero Zappi Qualcomm Al Research
Christopher Lott Qualcomm AI Research
Roberto Bondesan Qualcomm AI Research
Abstract
Recent works machine learning for combinatorial optimization have shown that learning based approaches can outperform heuristic methods in terms of speed and performance. In this paper, consider the problem of finding optimal topo- logical order on a directed acyelic graph with focus on the memory minimization problem which arises in compilers. We propose an end-to-end machine learning based approach for topological ordering using an encoder-decoder framework. Our encoder is novel attention based graph neural network architecture called Topoformer which uses different topological transforms of DAG for message passing. The node embeddings produced by the encoder are converted into node priorities which are used by the decoder to generate probability distribution over topological orders. We train our model on dataset of synthetically generated graphs called layered graphs. We show that our model outperforms, or is on-par, with several topological ordering baselines while being significantly faster on syn- thetic graphs with to 2k nodes. We also train and test our model on set of world computation graphs, showing performance improvements.
1 Introduction
Many problems in computer science amount to finding the best sequence of objects consistent with some precedence constraints. An intuitive example comes from routing problems. where we would like to find the shortest route between cities but we have requirements (i.e. for example to pick up and subsequently deliver a package) on the order in which the cities should be visited []] Another case is found in compiler pipelines, wherein the "cities" become operations to be executed and the constraints come from the data dependencies between these operations, such as when the result of an operation is an operand in a subsequent one. In this case, the metric to be optimized can be the run time of the compiled program, or the memory required to execute the program [2]. Common across this class of problems is their formulation in term of finding the optimal topological order
"Equal contribution
"Qualcomm Al Research an initiative of Qualcomm Technologies, Inc. Work completed during employment at Qualcomm Technologies, Inc.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of the Directed Acyelic Graph (DAG) that encodes the precedence constraints, which induces a Combinatorial Optimization (CO) problem which is in general computationally hard A.
Already from the two examples above, one can immediately grasp the relevance of such problems for industrial Operations Research, which has prompted various actors invest in the development of efficient CO solvers; these solvers usually encapsulate heuristic methods whose design typically requires extensive use of domain-specific and problem-specific knowledge, across decades of de- velopment. In recent years, considerable interest has emerged in the possibility of replacing such handcrafted heuristics with ones learned by deep neural nets [5] (machine learning for combinatorial optimization, MLCO). As a matter of fact. both of our two examples of DAG- CO problems have indirectly been object of study in the Machine Learning literature. References 66 7 g take into consideration Routing Problems, especially the Traveling Salesperson Problem (TSP) which, on account of its richness, complexity and long history of mathematical study [10, has attained the status of a standard benchmark for MI.C [8. Conversely, less attention has been devoted to operations sequencing likely due to the proprietary and sensitive nature of compiler workflows, which hampers the definition of public benchmarks. References [1]22] both consider the task of optimizing the run time of a neural network's forward pass by optimizing the ordering and device assignment of its required operations. However, in this last case the sequencing stage is only one part of larger compiler pipeline, and as a result of this both the performance metrics and the datasets employed cannot be made available for reproduction by third parties. This makes it both hard to assess the results therein, and to draw general conclusions and guidelines for the advancement of MLCO, which still suffers from lack of commonly accepted and standard datasets and benchmarks.
In this work, we address the problem of finding optimal topological orders in a DAG using deep learning, focusing on the compiler task of optimizing the peak local memory usage during execution. We make the following contributions:
We present a neural framework to optimize sequences on directed acyclic graphs. Mindful of the need for scalability, we consider a non-auto-regressive (NAR) scheme for parametrizing the probability distribution of topological orders. This allows our method to attain an extremely favorable performance vs. run time tradeoff:: it always outperforms fast baselines, and is only matched or outperformed by those requiring a much longer (in one case 4000x more) run time. We address the problem of how to perform meaningful message-passing on DAGs, a graph type which has received comparatively less attention in the literature on Graph Neural Networks. We introduce Topoformer, a flexible, attention- based architecture wherein messages can be passed between each and every pair of nodes, with different set of learnable parameters depending on the topological relation between the nodes.
To test our method, we introduce Net-like computation graphs, allowing any researcher to generate a dataset of as many as desired graphs of any desired size. These graphs are more faithful model of real NN workflows, and allow us to prove our method on a much larger and varied dataset, than previous efforts [.]. To knowledge, this is the first public algorithm of this kind. Nevertheless, also test our method on proprietary graphs to illustrate its relevance to realistic compiler workflows.
algorithm for the generation of synthetic, layered, Neural
2 Related work
Machine Learning for Combinatorial Optimization: Combinatorial optimization as a use case for deep learning poses interesting technical challenges. First, the combinatorial nature of the problem conflicts with the differentiable structure of modern deep neural networks; and second, the models need to be run at large scale to solve real world instances, exacerbating the challenges in training deep learning models. Given the discrete nature of CO problems, natural approach is to pose them as reinforcement learning (RL) problems [13]. The aim is then to learn a policy that selects the best actions to maximize reward directly related to the optimization objective. Algorithms then differ in the way the policy is parameterized: either in an end-to-end manner where the actions directly . or in a hybrid manner, where the policy augments parts of a traditional solver, e.g. by replacing heuristics used in setting parameters of
correspond to solutions of the optimization problem [12 6 g 14,
an algorithm, see e.g. [T 9 7 2 Our approach follows an end-to-end design philosophy, which, not having to rely on an external algorithm, affords better control of post-compile run time and facilitates application on edge devices (2). Furthermore, RL has the advantage of being useful as a black box optimizer, when no handcrafted heuristics can be designed.

---

Sequence Optimization via ML; Within MLCO, much effort has been devoted to the task of predicting optimal sequences [ 6 16 18. The end-to-end nature of our method places it close to the one proposed in [6. although to the best of our knowledge, our work is the first to tackle the challenge of enforeing precedence constraints in the network predictions. As we shall see more detail below, this generalization is non-trivial: already counting the number of topological orders belongs to the hardest class of computational problems [4]. This has to be contrasted with the fact that the number of sequences without topological constraints is simply n! for objects. Besides, as pointed out in [8] no MLCO method has so far been able to convincingly tackle TSPs of sizes above few hundred nodes, when it comes to zero-shot generalization to unseen problem instances, Le. when no fine tuning on the test set is done. is also therein pointed out how an auto regresssee parametrization of the sequence (which was the method used in ref. [6] appears to be necessary to achieve acceptable performance even at those small sizes. Conversely, in the present work we show compelling zero-shot performance on DAGS of sizes up to thousands of nodes, while nonetheless generating our sequences in a fully non-auto-regreesiyy (NAR) way and maintaining a strong run time advantage over classical sequencing algorithms. Our results can then also be interpreted as cautioning against the idea of using the TSP as the sole, paradigmatic test-bed for MLCO research, as [8) remarks.
The DAG sequencing task we consider is an omnipresent stage in compiler workflows, which usually also include such tasks as device assignment and operations fusion [1].. In such a setting, jointly optimizing these tasks to reduce the run time of a certain workflow (such as the forward pass of Neural Net) is a common objective, which in refs [T] [9] is tackled with MI. methods. In this work we focus on the task of minimizing the peak local memory usage during execution, which does not require performance model or simulator as well as being relevant to applications on edge devices (2). In [1], the ML solution leans on an existing genetic algorithm, whilst our solution is end-to-end, much like that proposed in 12] Another characteristic of the solution proposed in [12] is the idea of interpolating between AR and NAR via an iterative refinement scheme, in which sequences are generated one pass but subsequently refined during an user-defined number of subsequent passes; conversely, we generate all our sequences in single pass. While in [1] the run time optimization is studied on both real- world and synthetic random graphs - the latter being relatively small (up to about 200 nodes), the peak memory optimization is studied only on a proprictary dataset augmented via perturbation of the node attributes. In [1] the authors train relatively small set of six proprietary workflows which are not disclosed to
ML for Compiler Optimization:
and test their method the reader, and out of those six, only the size of the largest instance is mentioned.
Deep Graph Neural Networks: Given that to parametrize our sequence sequence-generation policy with a Graph Neural Network architecture [20]. The basic idea of every GNN architecture is to update graph and edge representations by passing messages between the graph nodes along the graph edges (21). However, this can be too restrictive when it comes to sequence generation
problem is specified as DAG, it is logical choice
DAGs. For example, nodes that come after each other in the sequence might not be linked by an edge in the graph, and therefore are unable to directly influence each other's representation. Notice how this difficulty is another consequence of the presence of precedence constraints in our problem, which conversely was not an issue in c.g. 66 where the graph
fully connected and no constraints are present. Relatively few efforts (see e.g. 22 23 24 have been devoted to devise way to perform meaningful message passing on DAGs. As matter of fact, the quest for expressive GNN architectures is at the center of intense theoretical investigation [25 26
3 Background
3.1 Topological Orders and DAGs
We here introduce the mathematical background, starting with a few definitions. A partial order is an irreflexive transitive relation < between certain pairs of set V. We call a pair (z, y) E V V that is related by < comparable, and incomparable otherwise. A Directed Acyclic Graph (DAG) G = (V, E) a directed graph with no directed loops. We can map a DAG = (V, E)) to a partially ordered set (V. <) where r < if there is directed path from node x to node y. Multiple DAGs map to the same partial order. For example, the DAGS with vertex set (a. y, }} and edge sets E = {ar + y,y + =} and E' = {x - y.y 2, x + 2}. where s - denotes directed edge from s to 1, correspond to the same partial order x < y < z. We define the transitive closure (TC) of a DAG as the graph with most edges that has the same underlying partial order, so that there exists directed edge (x, v)
3

---

whenever < y. Conversely, the transitive reduction (TR) is the graph with least edges that results in the same partial order. We denote the order induced by a DAG by <G-
topological order or sorting of DAG G is a bijection a : V + (1,...,,,VV] IV]] such that (a) < (v) whenever <G y- The set To of topological orders of G is a subset of the permutation group of the vertices and coincides with total orders on V that respect <g. called linear extensions of the partial order. While there are several well-known algorithms to compute a topological order of DAG, e.g. breadth first search and depth first search, counting the number of topological orders is one of the hardest computational problems, being #P complete [4. In this work we develop a general machine learning method to find topological order that minimizes given cost function on DAG, which we define in the next section.
3.2 Peak Memory Minimization
Deciding the best way to schedule operations in computational graph representing a neural network central problem in compilers [1]] 12 2). We can associate DAG computational graph in such a way that nodes represent operations ("ops"), and incoming/outgoing edges represent operands/results of these operations. Every time one executes an op, the input to that op need to be in memory, and memory for the outputs needs to be allocated. Therefore, each node of the DAG carries label m V + specifying the memory required to store the output of that op. typical first step in scheduling a DAG is to identify topological orders to execute operations. Compilers for edge devices, which have limited memory, aim at choosing the optimal topological order that minimizes the peak memory footprint [2]. We focus therefore on the peak local memory usage minimization task, which can be formulated as the following combinatorial optimization problem on labeled DAG G (V, m):
min C(a), oTTa
C(a) = max(M (
(1)
with the definitions
M, -6-1 m(ar):
(2)
= Me Σ m,,
St S.=
iiid
U St and Vi.j) E, E on 1=
sES.
i.e. the memory usage time is given by the memory usage 4,1 of the outputs which have not yet been consumed, at time t - 1, by downstream operations, plus the memory requirement of the output of operation (f). L is in turn obtained by subtracting from M, the memory costs nodes whose outgoing edges only connect to already scheduled nodes, i.e. nodes whose output was only required by already scheduled operations. Naturally, Iu = 0, Su = Φ.
4 Method
We use an encoder-decoder architecture whose schematic is shown in figure 1 Topoformer, novel GNN architecture, which derives an embedding for each node of the graph. The embeddings are used by the decoder which generates a distribution in the sequence space and finally the distribution can be converted to sequence via different inference methods like sampling, greedy inference or beam search. Next, we describe each of the component in detail.
Our encoder is
4.1 Topoformer: Topologically Masked Attention
A Graph Neural Network (GNN) is a natural choice to encode our scheduling problem via embedding of the DAG nodes. All canonical GNN architectures operate by updating these embeddings via the aggregation of "messages" sent from the other nodes, usually in the form of some function of their own embedding 20). Architectures mainly differ in how the set of sender nodes is constructed and the aggregation function is chosen. In Graph Convolutional Network [27). the senders are the first neighbors of node and the aggregation function is a weighted average, whilst in a vanilla Graph Attention Network 28 the senders are all the other nodes, but their contributions are aggregated
We use "inputs" and "operands" interchangeably throughout the paper.

---

Topoformer encoder
[R((]
G Emara)
TC
Incomp. pains
MHA
MHA
MHA MHA
MHA
MHA
MHA
LL
MLP
h
Topoformer layer
h (4))
Non-auto- Regressive decoder
Non-auto-Regressive
[o]
y/
Figure 1: Our complete architecture for neural topological ordering. The shades of gray in the MHA boxes are highlight how attentions heads operate separately on the forward and backward version of the first three graphs. The priorities (wr)_1 are represented by the red bars on the original DAG and decoded into a sequence with its associated probability.
via averaging with learned weights so as to account for their degree of relevance. When trying to apply such mechanisms DAGS, common point of contention whether, and how in practice, the partial ordering encoded by should reflect in the direction of travel of the messages [29] 24 22). While disregarding the DAG structure entirely (as one would do in a vanilla GAT), does not appear wise, it might be too restrictive when it comes to our task. For example, nodes that are next to each other in the sequence might well be incomparable, and thus lack path for messages between them. The combinatorial nature of the task also poses requirements; it is known 225 5) that reasoning about CO problems on a graph requires the capacity to reason about the global structure of whilst architectures such as those proposed in [29] 24 (2 limit the set of sender nodes to a local neighborhood of the receiver node. summary, our architecture must strike compromise between accounting for global structure and local partial ordering information.
Our Topoformer architecture meets these requirements. vector æ; of input features (see the appendix for details about its definition and dimensionality) is first turned into an initial node embedding h (0) via node-wis wise linear transformation. h W + b. Subsequently, succession of L attention layers, each of them consisting of a Multi-Head Attention (MHA) (88 sub-layer followed by one more node-wise MLP, updates these embeddings, similar to vanilla Transformer (30]; however, confer topological inductive bias to these updates by having a separate group of attention heads masked by each of the following graphs induced by the original DAG:
Its transitive reduction (TR).
The directed graph obtained by removing the TR edges from the DAG: G\ ETR(G)-
The directed graph obtained by removing the edges of the DAG from its TC: TC(G))..
The backwards versions (i.e. with flipped edges) of each of the three above.
The undirected graph obtained by joining all incomparable node pairs.
5

---

By adding together these graphs, one would obtain the fully connected graph relative to the node set V. whereupon all nodes would attend to all nodes. Then effectively, the propagation rules of Topoformer are same as those of a vanilla transformer encoder,
hg =h (f-1)
(E)
+ concat, [HA (N(-"),.. ..... h "VT :M)]]
(4)
(0) h1 h + MLP(1) (n.)
(5)
save for the presence of the mask MM, which ensures that head j only attends to its assigned graph among the seven listed above. Following BII, we also apply layer normalization [32 to the MHA and MLP inputs. The number of heads assigned to each graph can be chosen independently (setting it to zero means to not message-pan pass along the edges of the respective graph), or parameters can be tied among different MHAs. One should also remark how the MLP sub-layer allows the flow of information between different attention heads. All nodes are then able to influence each other's s representation, while anyway injecting strong inductive bias based on the DAG structure. Information about the Topoformer configurations used in our experiments is provided in the appendix.
4.2 Decoder
Once the embeddings of the nodes are generated, the decoder's task to derive a stochastic policy G(o(G) over the valid topological orders of the graph. The most straightforward way is to take advantage of the chain rule of conditional probability to decompose the policy as a product
IV G(o|G) = II po G) x po(a h, G),
(6)
We could then sample a complete sequence by autoregressively choosing new node at each step as done c.g. in [6). This scheme the most principled and expressive; however, when a NN is used as a function approximator for pg. it also requires that [V] calls to this NN be performed, which limits its feasibility to relatively small graphs due to the amount of computation required.
Non-Auto-Regressivv (NAR) scheme which decouples In order to scale to large graphs, we employ Non-Auto- Regressive the number of NN calls from the graph size. Similar the approach of [[2), we assign scheduling priorities y/ E R to the nodes, rather than scheduling probabilities. The priority for node i is derived by passing its final embedding through an MLP:
h (1)
Vi MLP
These priorities are assigned with single NN inference. The sequence itself is subsequently constructed by adding a new node at each step. Given the partial sequence di the next node can only be selected from subset S(0 G) of schedulable nodes, due to both the graph topology and choices made earlier in the sequence. Then, the distribution of the next node to be added at step i given follows:
exp(yor)
if o E S(o)a-1,G),
1, E Ejes(ouenn.)) exp(y;)'
(8)
otherwise.
Decoding Methods: We use the following three methods to obtain the next node in the partial sequence from the distribution p(a:|or:t-1,,,, h, G):
1. Greedy: At each step 6, select the node with the highest probability i.e. ot = arg max,, p(ā h.
2. Sampling: At each step f, sample from the next node distribution i.e. or ~ p(-1o1--11 h, G)
3. Beam search with state-collapsing: We can also expand the partial sequences by using beam search method where the score function is total probability of the partial sequence. We improve our beam search routine by making the following observation: suppose there are two partial sequences in consideration, di: and 013, such that both have scheduled the same set of nodes so far (but different order), and C(a1:e) C(²1:)) Then, can ignore the partial sequence 01: and only keep 11t in the beam search. This is because both partial sequences must schedule the same of remaining nodes, and hence the set of future memory costs are identical for both o and T1a. but the current peak memory cost is higher for T Thus, dir dominates ō la in terms of achievable minimal peak memory usage.

---

4.3 Training
Our a given DAG G. The expected cost incurred is given by J[Ø[G) (c) [C)) We minimize
architecture induces distribution (G) on the set of topological orders for
the cost (() = EG [][]] via gradient descent using the REINFORCE gradient estimator [33
as follows
((( EG (o(())
[CC(a) b(G)) V log po(a)))),
where (G) a baseline meant to reduce the variance of the estimator. We follow 6 in setting equal to the cost of greedy rollout of a baseline policy on the graph G
b(G) = (arg max pa (G)
(10)
5
Experiments
We conduct experiments on a synthetic dataset of graphs which we refer to as "layered graphs", as well as a set of real-world computation graphs. We compare our approach with the following classic topologiaal ordering baselines:
Depth/Breadth first sequencing: Find the topological order by traversing the graph in depth/breadth first manner according to the layout of the graph generated using pygraphviz.
Depth-first dynamic programming (DP): Depth-first DP is global depth-firs, method for searching the optimal sequence, with automatic backtracking when equivalent partial sequences are found; it retains the full sequence with minimum cost so far, and returns search does not complete before the prescribed timeout.
Approximate DP: In approximate DP, a beam of partial sequences are considered at each step. For each beam in the subsequent step. the top-K partial sequences with the lowest costs are retained. This DP is also able to find the optimal sequence given enough memory and compute resources (with unlimited beam size K), but only consider an approximate version with K = 10 in this work. Note that approximate DP uses the state-collapsing and parallelism to improve its efficiency. Random order: We generate 100 random topological orders, and pick the one with smallest cost.
Please see the appendix for more detailed description of the baselines. Therein, we also report some ablation studies on various neural baselines including ablation studies on decoder by considering other neural architectures, as well as comparison with an end to end baseline adapted from ref. [6]. Neural topo order greedy, sample and BS denote the performance of our model in greedy, sampling and beam search inference mode respectively. We use a sample size and beam size of 16 sequences, of which the best one is subsequently picked, for all our experiments. Next, we describe in detail the results of the two experiments.
5.1 Layered Graphs
In order to generate large corpus of training data come up with way to synthetically generate graphs of a given size which have similar structure to the computation graphs of feed-forward neural networks. We call our synthetic graph family layered graphs, as these graphs comprise of well-defined layers of nodes. The nodes in a layer have connections to the nodes in the subsequent layer and can also have skip connections with nodes in layers farther down. The number of layers, number of node per layer, number of edges between subsequent layers, number of skip connections and memory utilization of the nodes are all generated randomly, and can be controlled by setting appropriate parameters. We refer the reader to the appendix for more details on layered graphs, including their generation algorithm and some visual examples.
We train our model on 500-node layered graphs for 325 epochs, where in each epoch we generate a training set of 1000 new graphs. We test the performance of our model set of 300 unseen graphs of the same size, generated with the same method. We also evaluate the cross-size size generalization performance of our trained model by testing it on graphs of size 1000 and 2000. We refer the reader to the appendix for a comprehensive description of the training algorithm and model configuration.
Figure 2 shows the performance vs. run time plot on layered graphs of size [V] = 500, 1000, and 2000. We report the performance in terms of the % gap of peak memory utilization from the peak memory obtained via approximate DP, which we consistently observed to be the best-performing
7

---

baseline. Note that the run time is plotted on log-scale. We can observe that for 500-node graphs, our model beats all the baselines except approximate DP in terms of both the memory usage and run time. Our model is slightly worse than approximate DP from the memory usage perspective, but it runs 100x faster. We also observe that our model generalizes well to larger sized graphs. For the case of 2000-node graphs our model performs better than approximate DP in terms of peak memory usage, while being 4000x times faster. This shows that while approximate DP performs more poorly as graph size increases, our model is able to generalize larger graphs by learning meaningful embeddings of the topological structure thanks to Topoformer, and to be extremely fast thanks to our NAR decoding scheme.
500 node graphs
1000 node graphs
2000 node graphs
20
5-
10.0
15
7.5
Average
10
5.0
5
2.5
*
0
*
10
10
10"
10a
10
10
10a
10a
10a
10"
10c
10a
10a
10a
10*
Average run time (S)
Average run time (8)
Average run time (4)
Neural topo order Greedy Neural tapo order Sample
Neural topo order
Approx.
seq.
Dapth first DP
DF sec.
Random order
Figure 2: Average % gap from approximate DP vs average run time comparison on the test set of 300 layered graphs. Lower better for both % gap and run time.
Table I: Comparison of methods on the synthetic layered graph test set.
500- node graphs
1000-node graphs
2000-node graphs
Algorithm
gap from run time [s]
% gap from run time
% gap from approx. DP
run time [s]
approx. DP
approx. DP
[s]
Approximated DP
264.88
0
1561.17
0
8828.86
Depth-First DP
5.76
3600
3.84
3600
2.40
3600
(max. run time=1H) Random order Depth-first seq. Breadth- first seq.
6.86
1.38
2.62
7.13
0.31
36.87
12.9
2.45
7.1
10.91
3.57
51.32
20.94
2.43
11.31
10.87
6.42
51.52
Neural Topo Order
v Greedy
4.32
0.6
0.48
1.19
-1.47
2.44
/ Sample
3,49
0.72
0.03
1.41
-1.68
2.87
/ Beam search
3.21
2.68
0.08
5.92
-1.66
14.74
5.2
Graphs
While our synthetic layered graphs convenient for experimentation, we value in also presenting results obtained from neural computation graphs used for commercial development of our artificial intelligence hardware and software products. Here sample 115 representative graphs that have diverse architectures (classifiers, language processors, denoisers, etc.) and size (from few dozen to Ik nodes). We split this dataset into training set and test set via random 80 20 split. We train our model for 500 epochs and report the performance on the unseen test set at the end of training in table[2] In order to ensure fair comparison of run times, we stratify the test set into 3 categories based on the graph size. Figure shows the performance vs run time plot on the test set of real graphs. We observe that for real graphs the performance gap between the best baseline (approximate DP) and our model is remarkable. We can obtain sequences which are 50% better than approximate DP on average while also being almost 1000x faster on average. This proves the capability of our model to generalize and perform well on real-world computation workflows.

---

Real graphs test set (23 graphs)
350
Neural topo order Greedy
Neural order Semple
*
Neural topo order BS
Depth-first DP
250
Approx DP
BFS
DFS
Random order
150
Average
100
0-
-50
109
10a
10a
10a
Average run time (s)
Figure 3: Performance vs rum time comparison for different approaches on test set of real computation graphs. Performance is measured in average % gap from approximate DP.
Table 2: Comparison of methods on the real graph test set. Smaller gap is better
200 500-node graphs
500 500-700-nee 700-node graphs
700 1000-node graphs
Algorithm
gap from approx. DP
run time [s]
% gap from run time
% gap from
run time [s]
approx. DP
[s]
approx. DP
Approximated DP
113.54
0
517.60
1131.61
Depth-First DP
62.18
3600
102.76
3600
50.57
3600
(max. run time=1H)
Random order Depth-first seq.
469.34
0.25
376.16
1.24
116.24
2.40
506.21
0.70
394.93
2.26
123.21
4.49
Breadth- first seq.
348.77
0.75
149.81
2.31
-35.55
4.86
Neural Topo Order
/ Greedy
-17.57
0.42
-51.23
0.6
-68.97
0.83
/ Sample
-21.53
0.44
-40.51
0.68
-61.46
0.97
/ Beam search
-19.5
1.22
-57.34
2.58
-73.45
3.86
5.3 Encoder Ablation Study
We conduct experiments by using an MLP, fully connected transformer and GAT as an encoder architecture quantify the effectiveness of our topoformer architecture. We test vanilla version of GAT (referred as GAT forward only) which does message passing only on the edges of the DAG. We also consider GAT encoder which does message passing the augmented graph having reverse edges corresponding to all the edges of the DAG and refer to this setting as GAT forward+backward.
We train each model on the layered graph dataset of 500 node graphs. We evaluate the performance of the trained model on the test set (300 graphs) of 500 node and 1000 node graphs. We use sample size and beam width of 16 for evaluation transformer use the same number of layers and hidden dimension as the topoformer specified in appendix ??. We run the inference on our test set of 300 graphs 10 times for each model to be more precise our run time calculations. We report the mean % gap from approximate DP and the mean time across all the graphs and trials along with their 95% confidence interval.
both 500 and 1000 node graphs. The MLP and
Table shows the performance of different encoder architectures. can be observed that both versions of our topoformer architecture and GAT have superior performance than MLP and fully connected transformer for both graph sizes. Moreover, full topoformer (message passing on all the seven graphs listed in section 4. has better performance than GAT and topoformer with message

---

Table 3: Comparison of different encoder architectures. Topoformer with MP (message passing) on DAG corresponds to forward and backward message passing only on the input DAG using topoformer.
500-node graphs
1000-node graphs
Algorithm
% gap from approx. DP
run time [s]
% gap from approx. DP
run time [s]
MLP
v Greedy
8.31 = 0.76
0.58 + 0.0
2.95 + 0.48
1.52 = 0.01
V Sample
4.41 0.50
0.67 0.0
0.68 + 0.35
1.84 = 0.02
/ Beam search
6.5 0.69
2.47 + 0.01
2,43 + 0.49
7.62 + 0.07
Fully Connected Transformer
/ Greedy
8.46 + 0.72
0.69 = 0.01
3.09 + 0.46
1.3 + 0.01
Sample
4.72 0.52
0.8 0.01
0.85 + 0.37
1.55 0.02
/ Beam search
6.52 + 0.72
2.98 = 0.03
2.09 + 0.47
6.49 + 0.07
GAT (forward only)
/ Greedy
5,94 0.61
0.49 = 0.01
1.33 + 0.38
1.24 0.01
/ Sample
4.19 0.56
0.64 + 0.01
0.48 + 0.36
1.54 + 0.02
/ Beam search
4.22 0.60
2.22 + 0.02
0.60 + 0.38
5.94 + 0.04
GAT (forward-backward)
/ Greedy
4.84 0.55
0.63 0.01
0.90 + 0.37
1.37 0.02
/ Sample
3.55 + 0.53
0.80 = 0.01
0.23 + 0.36
1.67 + 0.02
v Beam search
3,55 0.54
2.89 = 0.01
0.39 + 0.36
6.50 0.05
Topoformer (forward-backward) (Ours)
/ Greedy
4.82 0.55
0.73 + 0.01
0.76 + 0.36
1.62 + 0.02
/ Sample
3.67 + 0.52
0.85 + 0.01
0.21 + 0.36
1.99 + 0.02
v Beam search
3.68 0.57
3.03 + 0.03
0.35 + 0.37
8.1 0.08
Full Topoformer (Ours)
/ Greedy
4.31 + 0.56
1.04 + 0.01
0.47 + 0.36
1.51 + 0.01
/ Sample
3.35 0.52
1,21 0.01
-0.01 + 0.35
1,8 0.02
/ Beam search
3.08 + 0.51
4.15 = 0.02
0.05 + 0.36
7.4 : 0.07
passing only the forward and backward edges of the DAG. This shows the benefit of global message passing between all the nodes which is enabled by the full topoformer.
6 Conclusion
In this work we propose an end-to-end machine learning method for the task of optimizing topological orders directed acyelic graph. Two key elements our design are: (1) an attention-based GNN architecture named Topoformer that employs message passing that is both global and topologically- aware directed acyclic graphs, (2) a autrrerreerresvvee parametrization of the distribution on topological orders that enables fast inference. We demonstrated, for both synthetic and real-world graphs, the effectiveness of the method tackling the problem of minimizing peak local memory usage for compute graph canonical task in compiler pipelines. Said pipelines also include other tasks [12), chief amongst them the one of assigning operations to devices for execution. At the present stage, method and dataset cannot be leveraged for solving these, for end-to-end optimization of whole pipeline. Extending our method to this more challenging setting is therefore natural direction for future research.
References
[1] P. Toth and D. Vigo, Vehicle routing: problems, methods, and applications.
SIAM, 2014.
10

---

[2] B. H. Ahn, J. Lee, J. M. Lin, H.-P. Cheng, J. Hou, and H. Esmaeilzadeh, "Ordering chaos: Memory-aware scheduling of irregularly wired neural networks for edge devices," Proceedings of Machine Learning and Systems, vol. 2, pp. 44-57, 2020.
[3] C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algoritims and complexity. Courier Corporation, 1998.
[4] G. Brightwell and P. Winkler, "Counting linear extensions is #p-complete," in Proceedings Anmual ACM Symposium on Theory of Computing, 1991, 175-181. [Online]. Available: http://doii.rr// 1tttg//00111111111111111310
[5] Y. Bengio, A. Lodi, and A. Prouvost, "Machine learning for combinatorial optimization: methodological tour d' horizon,,"" European Journal of Operational Research, vol. 290, no. 2, pp. 405-421, 2021.
[6] W. Kool, H. Hoof, and M. Welling, "Attention, learn to solve routing problems!" in International Conference on Learning Representations, 2019. [Online]. Available: http://opeeeeeeisweeeee/uuuiliad
[7] L. Xin, W. Song, Z. Cao, and J. Zhang, "NeuroLKH: Combining deep learning model with on-kernigghan-hesgaaun heuristic for solving the traveling salesman problem." in Advances in Neural Information Processing Systems, 2021. [Online]. Available: http:pppaneiiiiee.eeefrromnnnn/e
[8] C. K. Joshi, Q Cappart, L.-M. Rousseau, and T. Laurent, "Learning TSP requires rethinking gen- eralization," in International Conference Principles and Practice of Constraint Programming, 2021.
[9] A. Correia, D. E. Worrall, and R. Bondesan, "Neural simulated anncaling," " 2022. [Online]. Available: http://ppwnoiiii...///oommm/mmaa
[10] W. J. Cook, In pursuit of the traveling salesman. Princeton University Press, 2011.
[11] A. Paliwal, F. Gimeno, V. Nair, Y. Li, M. Lubin, P. Kohli, and O. Vinyals, "Reinforced genetic algorithm learning for optimizing computation graphs," in International Conference on Learning Representations, 2020. [Online]. Available: http:://ppnreeve..eefffmmmmmm Bid.
[12] Y. Zhou, S. Roy, A. Abdolrashidi, D. Wong, P. Ma, Q. Xu, H. Liu, P. Phothilimtha, S. Wang, A. Goldie et al., "Transferable graph optimizers for ML compilers," Advances in Neural Information Processing Systems, vol. 33, pp. 13 844-13 855, 2020.
[13] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction. MIT press, 2018.
[14] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song, "Learning combinatorial optimization algorithms over graphs," " Advances in neural information processing systems, vol. 30, 2017.
[15] I. Bello*, H. Pham* Q. V. Le, M. Norouzi, and S. Bengio, "Neural combinatorial optimization with reinforcement learning," 2017. [Online]. Available: https://openeeviee.eeefffmmm Pid= YY3399eg
[16] G. Mena, D. Belanger, S. Linderman, and J. Snoek, "Learning latent permutations with gumbel- sinkhorn networks," in International Conference on Learning Representations, 2018.
[17] S. Linderman, G. Mena, H. Cooper, L. Paninski, and J. Cunningham, "Reparameterizing the Birkhoff polytope for variational permutation inference," in Proceedings of the International Conference on Artificial Intelligence and Statistics, vol. 84, 09-11 1 Apr 2018, pp. 1618-1627. [Online]. Available: https://proceedings..u www.eeeewnnn.mmmrre////////eeeee wtt.pres///84//iddmmaann wtw.eerrmannnaahinnn. ht..html
[18] A. Gadetsky, K. Struminsky, C. Robinson, N. Quadrianto, and D. Vetrov, "Low-variance black- box gradient estimates for the plackett-luce distribution," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 06, 2020, pp. 10 126-10 135.
[19] B. Steiner, C. Cummins, H. He, and H. Leather, "Value learning for throughput optimization of deep learning workloads," " Proceedings of Machine Learning and Systems, vol. 3, pp. 323-334, 2021.
11

---

[20] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, "A comprehensive survey on graph neural networks," IEEE transactions on neural networks and learning systems, vol. 32, no. pp. 4-24, 2020.
[21] P. W. Battaglia, B. Hamrick, V. Bapst, A. Sanchez-Gonzale V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner et al., "Relational inductive biases, deep learning, and graph networks," arXiv preprint arXiv:1806.00 01211, 2018.
[22] V. Thost and J. Chen, "Directed acyclic graph neural networks," in International Conference on Learning Representations, 2020.
[23] M. Zhang, S. Jiang, Z. Cui, R. Garnett, and Y. Chen, "D-VAE: A variational autoencoder for directed acyelic graphs," Advances in Neural Information Processing Systems, vol. 32, 2019.
[24] M. Bianchini, M. Gori, and F. Scarselli, "Recursive processing of directed acyclic graphs," in Neural Nets WIRN Vietri-01, 2002, pp. 96-101.
[25] C. Ying, T. Cai, S. Luo, S. Zheng. G. Ke, He, Shen, and T.-Y. Liu, "Do transformers really perform badly for graph representation?" Advances in Neural Information Processing Systems, vol. 34, 2021.
[26] R. Sato, "A survey on the expressive power of graph neural networks," " 2020. [Online]. Available: https:/aarxx..og//a////0.......0
[27] N. Kipf and M. Welling, "Sperisupe classification with graph convolutional networks." in International Conference on Learning Representations, 2017.
[28] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, "Graph attention networks," " in International Conference on Learning Representations, 2018. [Online]. Available:
[29] R. Wang, Z. Hua, G. Liu, J. Zhang, J. Yan, Qi. Yang. J. ZHOU, and X. Yang. "A bi-level framework for learning to solve combinatorial optimization on graphs," in Advances in Neural Information Processing Systems, 2021.
[30] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, "Attention is all you need," Advances in neural information processing systems, vol. 30, 2017.
[31] R. Xiong, Y. Yang, D. He, K. Zheng, S. Zheng, C. Xing, H. Zhang, Y. Lan, L. Wang, and T. Liu, "On layer normalization in the transformer architecture," International Conference on Machine Learning. PMLR, 2020, pp. 10 524-10333.
[32] J. L. Ba, J. R. Kiros, and G. E. Hinton, "Layer normalization."" in NIPS Deep Learning Symposium, 2016. [Online]. Available: https://arxiv.org/dddi 607 (07.6667.666000 00445001..ppp
[33] J. Williams, "Simple statistical gradient-following algorithms for connectionist reinforcement learning," Machine learning, vol. 8, no. 3, pp. 229-256, 1992.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See section 5
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] We cannot foresee any possible negative impacts, due to the highly technical nature of the task under consideration.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results... (a) Did you state the full set of assumptions of all theoretical results? [N/A]
12

---

(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL.)? [No] The code and the data are proprietary. We do include clear instructions on how our synthetic graph dataset is generated in the appendix.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] Please see the appendix for training details (c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We report the standard deviation of the % gap from approximate DP and the run time for each method in the appendix
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] Please the appendix for details on compute resources
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing
conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "zUUQZ4-VBbi", "reviewer": "Reviewer_hyRi", "summary": "The authors introduce an architecture called Topoformer. It employs message passing that is both global and topologically- aware in directed acyclic graphs. It is an end-to-end framework of encoder and decoder for topological ordering focusing on the compiler task of optimizing the peak local memory usage during execution. Experiments are conducted on both real and synthetic graphs of varied sizes.", "questions": "1. What about graphs with more than 2k nodes? \n2. Can we show comparison wrt recent algorithms for the same problem? ", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The problem is quite novel and can be a notable contribution to the field of GNNs, CO problems and compilers. \n2. Experiments show improved results. \n3. Paper is mostly explained well, sometimes difficult to follow. \n4. Some of the results are interesting. \n5. Problem is well placed in the literature and impactful. \n6. To the best of my knowledge, this is the first work based on GNN+topological ordering in DAG. \n\nWeaknesses: \n1. Paper is sometimes difficult to follow. \n2. Example figures should have been included. \n3. Some more analyses and explanations could be performed to show the significance of the attention mechanism or Transformer network. \n4. I don’t see any comparison with SOTA. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RrDUEk-xTcr", "reviewer": "Reviewer_BLAK", "summary": "This paper addresses topological ordering over computational graphs, and proposes a neural model, the Topoformer, to compute an optimal topological ordering (in terms of peak memory usage) when compiling a directed acyclic graph of compute operations, e.g., in neural networks. At a high level, the Topoformer builds on graph neural network (GNN) architectures, and applies these models simultaneously to multiple graph structures (e.g., the transitive reduction of the input DAG) using separate multi-head attention mechanisms, and then combines the attention outputs using MLPs. The Topoformer uses a simple (albeit less powerful) decoder, based on computing node priorities using an MLP layer on the final node embeddings, rather than an auto-regressive approach, so as to efficiently compute node sequences in one model pass. Finally, the paper evaluates the Topoformer (with sampling, greedy and beam search decoding), and against multiple baselines (random orderings, dynamic programming, etc.) on both synthetically generated neural network baselines, as well as real-world baselines. In all experiments, the Topoformer model achieves comparable performance to the best baseline (Approximate DP), and eventually outperforms it on larger instances, even with a fraction of the computational resources. ", "questions": "No questions at present. ", "limitations": "Limitations: See final bullet in \"Weaknesses\" section above.\n\nSocietal Impact: Not applicable", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- The paper is well-written, and the results are compelling.\n- The model is highly scalable and easy to understand. Furthermore, its fundamental idea of using multiple graph representation is an interesting direction for graph data augmentation in general.\n- The dataset generation procedure is potentially valuable for the MLCO community, and can serve as a strong baseline aside from the more traditional baselines such as TSP.\n\nWeaknesses: \n- The comparison against baselines is rather limited: It would be good to validate the strengths of this approach against different GNN choices, such as DAGNN, or even standard GNNs such as GCN, GAT. Currently, the baselines are all non-neural. It would therefore be insightful to include other GNN results to demonstrate the value of the Topoformer architecture.\n- The analysis of the model could be improved: For instance, it would be nice to see how the different attention components combine, e.g., a case study on a representative test instance, or to conduct an ablation study of the different graph structures included as input to the Topoformer.\n- The limitations of the one-shot decoder are not sufficiently discussed. The paper states that expressiveness is sacrificed, but does not thoroughly discuss the potential drawbacks, namely loss of potential ordering outputs. Ideally, one should highlight scenarios in which this choice could be harmful, e.g., some DAG where the optimal sequence cannot be obtained, or, alternatively, whether this limitation is not impactful in practice.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "857id__AVmP", "reviewer": "Reviewer_bMHc", "summary": "The authors introduce a new approach for solving the problem of topological orderings on DAGs with additional ordering constraints. They do so using a novel neural architecture based on a GNN with attention. The authors focus on peak memory minimization as a setting for application — specifically, computation graphs generated by neural network computation. They present a simple but effective method of generating layered graphs which serve as synthetic data for their benchmarks, pointing out several challenges with real-world benchmarks, then benchmarking their approach on both, which shows significant improvements in runtime over other approximate methods.\n\n**NB:** I am reviewing this paper as an emergency substitute; please let me know if you have questions about my review or anything I can clarify.", "questions": "The decision to add constituent graphs as other attention heads is sensible, but there is no speculation or study as to why that inductive bias is effective. What other approaches did the authors explore, and why were they successful or not?\n\nIs it possible this approach could be used to solve other problems in P# or related complexity classes that have reductions to or from this particular constrained topological ordering problem? Additional discussion of this might be compelling.\n\nBeam search significantly increases the cost of inference for the model; results, however, don’t seem much better. Are there any insights as to why beam search doesn’t yield much improvement?\n\nHave the authors verified that the orderings produced by the model work in practice? A real experiment using the constructed computation graphs would be very compelling.\n\nPer the above: what is the model size, and how long does it take to train on what scale of hardware? Is training sensitive to ay configurations or parameters?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nThe proposed method is novel. In particular, the introduction of additional attention heads of component graphs of the fully-connected graph is a unique way to inject inductive bias into the model.\n\nMany performance considerations are made, then challenges mitigated. Using a well-crafted non-autoregressive approach significantly speeds up inference for large graphs.\n\nThe paper is very well-written and pleasant to read. Its premises are compellingly argued. The motivation and problem setting are clear and the utility simple.\n\n### Weaknesses\n\nThe paper lacks ablations on some of the architectural contributions – some decisions seem somewhat arbitrary as a result. As an example: why is an additional node-wise MLP layer added to follow MHA sub-layers in the model? Is this layer a prerequisite to training, or is it simply a change which empirically improved performance?\n\nDetails on the generation of the real-world graphs are lacking. Further, the authors do not discuss releasing the set of graphs you used to evaluate your model, which would greatly enhance reproducibility and would further the paper’s contribution.\n\nThe discussion of the approaches for generating and the origins of the real-world graphs can be significantly improved to better-understand the differences between the real-world and generated graphs.\n\nThe authors can do a better job of broadening the treatment of the benefits of the proposed approach to other types of problems in topological ordering. The problem setup and study, while useful, is rather narrow.\n\nFinally, significant details about the model and experimentation process are missing (how large is it? How long does it take to train and what are the training dynamics?).\n\nSeveral other works related to optimization of ML workloads and ML for CO are not cited:\n- [Neural Combinatorial Optimization with Reinforcement Learning](https://research.google/pubs/pub45821/)\n- [Learning Combinatorial Optimization Algorithms over Graphs](https://arxiv.org/abs/1704.01665)\n- [Value Learning for Throughput Optimization of Deep Learning Workloads](https://proceedings.mlsys.org/paper/2021/hash/73278a4a86960eeb576a8fd4c9ec6997-Abstract.html)", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept