Timezone: »
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.
Author Information
Mukul Gagrani (QualComm)
Corrado Rainone (Qualcomm Inc, QualComm)
Yang Yang (Qualcomm Inc.)
Harris Teague (Qualcomm)
Wonseok Jeon (Qualcomm AI Research)
Roberto Bondesan (Imperial College London)
Herke van Hoof (University of Amsterdam)
Christopher Lott (Qualcomm AI Research)
Weiliang Zeng (QualComm)
Piero Zappi (Qualcomm Tech. Inc.)
Piero Zappi is a Sr. Staff research Engineer at Qualcomm. His current work focus on applying ML to combinatorial optimization problems.
More from the Same Authors
-
2022 Poster: Learning Expressive Meta-Representations with Mixture of Expert Neural Processes »
Qi Wang · Herke van Hoof -
2022 : Neural DAG Scheduling via One-Shot Priority Sampling »
Wonseok Jeon · Mukul Gagrani · Burak Bartan · Weiliang Zeng · Harris Teague · Piero Zappi · Christopher Lott -
2022 : Robust Scheduling with GFlowNets »
David Zhang · Corrado Rainone · Markus Peschl · Roberto Bondesan -
2022 : Training graph neural networks with policy gradients to perform tree search »
Matthew Macfarlane · Diederik Roijers · Herke van Hoof -
2022 Poster: Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel »
Changyong Oh · Roberto Bondesan · Efstratios Gavves · Max Welling -
2022 Poster: Local Metric Learning for Off-Policy Evaluation in Contextual Bandits with Continuous Actions »
Haanvid Lee · Jongmin Lee · Yunseon Choi · Wonseok Jeon · Byung-Jun Lee · Yung-Kyun Noh · Kee-Eung Kim -
2020 Poster: Experimental design for MRI by greedy policy search »
Tim Bakker · Herke van Hoof · Max Welling -
2020 Spotlight: Experimental design for MRI by greedy policy search »
Tim Bakker · Herke van Hoof · Max Welling -
2020 Poster: MDP Homomorphic Networks: Group Symmetries in Reinforcement Learning »
Elise van der Pol · Daniel E Worrall · Herke van Hoof · Frans Oliehoek · Max Welling