Neural Topological Ordering for Computation Graphs
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 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.
Code (0)
등록된 구현이 없습니다.
Tasks
2kBIG-bench Machine LearningCombinatorial OptimizationDecoderGraph Neural NetworkMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Diffusion Models for Causal Discovery via Topological Ordering
Discovering causal relations from observational data becomes possible with additional assumptions such as considering the functional relations to be constrained as nonlinear with additive noise (ANM). Even with strong as…
Causal DiscoverySequentially learning the topological ordering of causal directed acyclic graphs with likelihood ratio scores
Causal discovery, the learning of causality in a data mining scenario, has been of strong scientific and theoretical interest as a starting point to identify "what causes what?" Contingent on assumptions and a proper lea…
Causal DiscoveryFormulating Neural Sentence Ordering as the Asymmetric Traveling Salesman Problem
The task of Sentence Ordering refers to rearranging a set of given sentences in a coherent ordering. Prior work (Prabhumoye et al., 2020) models this as an optimal graph traversal (with sentences as nodes, and edges as l…
Combinatorial OptimizationSentenceSentence OrderingTraveling Salesman ProblemDifferentiable Bayesian Structure Learning with Acyclicity Assurance
Score-based approaches in the structure learning task are thriving because of their scalability. Continuous relaxation has been the key reason for this advancement. Despite achieving promising outcomes, most of these met…
Score-informed Neural Operator for Enhancing Ordering-based Causal Discovery
Ordering-based approaches to causal discovery identify topological orders of causal graphs, providing scalable alternatives to combinatorial search methods. Under the Additive Noise Model (ANM) assumption, recent causal …
Prompt Engineering