  Graph representation learning has achieved a remarkable success in many
graph-based applications, such as node classification, link prediction, and
community detection. These models are usually designed to preserve the vertex
information at different granularity and reduce the problems in discrete space
to some machine learning tasks in continuous space. However, regardless of the
fruitful progress, for some kind of graph applications, such as graph
compression and edge partition, it is very hard to reduce them to some graph
representation learning tasks. Moreover, these problems are closely related to
reformulating a global layout for a specific graph, which is an important
NP-hard combinatorial optimization problem: graph ordering. In this paper, we
propose to attack the graph ordering problem behind such applications by a
novel learning approach. Distinguished from greedy algorithms based on
predefined heuristics, we propose a neural network model: Deep Order Network
(DON) to capture the hidden locality structure from partial vertex order sets.
Supervised by sampled partial order, DON has the ability to infer unseen
combinations. Furthermore, to alleviate the combinatorial explosion in the
training space of DON and make the efficient partial vertex order sampling , we
employ a reinforcement learning model: the Policy Network, to adjust the
partial order sampling probabilities during the training phase of DON
automatically. To this end, the Policy Network can improve the training
efficiency and guide DON to evolve towards a more effective model
automatically. Comprehensive experiments on both synthetic and real data
validate that DON-RL outperforms the current state-of-the-art heuristic
algorithm consistently. Two case studies on graph compression and edge
partitioning demonstrate the potential power of DON-RL in real applications.
