Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

**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.
strengths_and_weaknesses: ### Strengths

The 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.

Many performance considerations are made, then challenges mitigated. Using a well-crafted non-autoregressive approach significantly speeds up inference for large graphs.

The 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.

### Weaknesses

The 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?

Details 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.

The 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.

The 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.

Finally, 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?).

Several other works related to optimization of ML workloads and ML for CO are not cited:
- [Neural Combinatorial Optimization with Reinforcement Learning](https://research.google/pubs/pub45821/)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://arxiv.org/abs/1704.01665)
- [Value Learning for Throughput Optimization of Deep Learning Workloads](https://proceedings.mlsys.org/paper/2021/hash/73278a4a86960eeb576a8fd4c9ec6997-Abstract.html)
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?

Is 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.

Beam 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?

Have 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.

Per 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
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths: 
1. The problem is quite novel and can be a notable contribution to the field of GNNs, CO problems and compilers. 
2. Experiments show improved results. 
3. Paper is mostly explained well, sometimes difficult to follow. 
4. Some of the results are interesting. 
5. Problem is well placed in the literature and impactful. 
6. To the best of my knowledge, this is the first work based on GNN+topological ordering in DAG. 

Weaknesses: 
1. Paper is sometimes difficult to follow. 
2. Example figures should have been included. 
3. Some more analyses and explanations could be performed to show the significance of the attention mechanism or Transformer network. 
4. I don’t see any comparison with SOTA. 
questions: 1. What about graphs with more than 2k nodes? 
2. Can we show comparison wrt recent algorithms for the same problem? 
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths: 
- The paper is well-written, and the results are compelling.
- 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.
- 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.

Weaknesses: 
- 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.
- 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.
- 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.
questions: No questions at present. 
limitations: Limitations: See final bullet in "Weaknesses" section above.

Societal Impact: Not applicable
review_title: null

Meta-review: metareview: The reviewers unanimously considered that this paper should be accepted for publication.  Among the strengths noted are is the novelty and relevance of the method, the experimental results and finally it was considered to be well-written.

confidence: Certain
Decision: Accept