Graph Ordering: Towards the Optimal by Learning

Graph ordering concentrates on optimizing graph layouts, which has a wide range of real applications. As an NP-hard problem, traditional approaches solve it via greedy algorithms. To overcome the shortsightedness and inflexibility of the hand-crafted heuristics, we propose a learning-based framework: Deep Ordering Network with Reinforcement Learning (DON-RL) to capture the hidden structure from partial vertex order sets over a specific large graph. In DON-RL, we propose a permutation invariant neural network DON to encode the information from partial vertex order. Furthermore, to alleviate the combinatorial explosion for partial vertex order sets and make the efficient training data sampling, we propose RL-Sampler, a reinforcement learning-based sampler to tune the vertex sampling probabilities adaptively during the training phase of DON. Comprehensive experiments on both synthetic and real graphs validate that our approach outperforms the state-of-the-art heuristic algorithm consistently. The case study on graph compression demonstrates the potentials of DON-RL in real applications.