  We present a novel method for graph partitioning, based on reinforcement
learning and graph convolutional neural networks. The new reinforcement
learning based approach is used to refine a given partitioning obtained on a
coarser representation of the graph, and the algorithm is applied recursively.
The neural network is implemented using graph attention layers, and trained
using an advantage actor critic (A2C) agent. We present two variants, one for
finding an edge separator that minimizes the normalized cut or quotient cut,
and one that finds a small vertex separator. The vertex separators are then
used to construct a nested dissection ordering for permuting a sparse matrix so
that its triangular factorization will incur less fill-in. The partitioning
quality is compared with partitions obtained using METIS and Scotch, and the
nested dissection ordering is evaluated in the sparse solver SuperLU. Our
results show that the proposed method achieves similar partitioning quality
than METIS and Scotch. Furthermore, the method generalizes from one class of
graphs to another, and works well on a variety of graphs from the SuiteSparse
sparse matrix collection.
