Using Reinforcement Learning to Optimize the Global and Local Crossing Number

In reinforcement learning (RL), an agent receives a description of its environment, based on which it chooses an action changing the environment The agent receives a reward, which is positive for a “good” change or negative otherwise. The agent tries to maximize its reward. RL programs like Alpha(Go)Zero [8, 9] were able to master games like Go, chess, and Shogi by just being taught the rules and objectives of the game. They were not given any strategy. We investigate the following question: Can we use reinforcement learning to optimize graph drawings with respect to a given graph drawing aesthetics measure? We present an RL framework for graph drawings to optimize local and global crossings.¹¹1With local crossings we refer to the maximum number of crossings an edge has in a straight-line graph drawing. With global crossings we refer to the total number of crossings in a straight-line graph drawing. We perform a quantitative analysis on two graph data sets comparing our models against other methods.

To obtain a size-invariant algorithm, we follow an idea of Safarli, Zhou, and Wang [7], who let an agent “sit” on a vertex and use as possible actions moving the vertex one step octagonally.

We provide the agent an observation vector describing the local neighborhood of a vertex $v$ with respect to the eight octants defined by the eight octagonal rays around $v$. The first eight entries in the observation vector of $v$ count the number of neighboring vertices in each octant, then eight entries count the total number of vertices. The next eight entries describe the distance to the closest neighbor, while the next eight entries describe the distance to the closest vertex. Finally, eight entries describe the amount of crossings that occur on edges incident to $v$ in the respective octants and eight entries their local crossing number.

In each step, the agent has eight actions to choose from, which correspond to moving the vertex in one of the 16 main direction 22.5 degrees apart. The reward function is, for the global crossing number, the number of removed crossings. For the local crossing number, it is a combination of local and global crossing number. The choice of the vertex for the next step depends on a probability distribution weighted by crossings and vertex degree.

We compare our approach on the rome graphs [1] (relatively sparse; 10–100 vertices, 9–158 edges) and extended Barabási-Albert (BA ​​) graphs [3] (random graphs; 50–150 vertices). An initial drawing used as input to the algorithms is obtained with the Kamada-Kawai algorithm [4]. We use 6,602 rome (1,000 BA ​​) graphs for training and 1,650 (500) for testing. We record the global and local crossing number and the running time and use a time limit of 900 s; see Figure 1. The experiments ran on a server with a single CPU. The code is written in Python 3.12. The custom environment is implemented on top of the Gymnasium library, and we train an (artificial neural network) PPO agent using the stable-baselines3 library.

We compare our RL method trained for the global (RL(GC)) and local crossing number (RL(LC)) with a range of different methods: the stress-minimization approach Kamada-Kawai (KK) and the spring embedder Fruchterman-Reingold (FR), implemented in networkx, which do not directly optimize for (local) crossing number but generally achieve good results. We also compare with the machine-learning model SmartGD [10]; the authors released a model trained to minimize the crossing number, which we use. Regarding previous heuristic solutions, we compare to the stochastic gradient descent method (SGD)² [2], to two geometric local-optimization approaches presented by Radermacher et al. [6], namely, Vertex Movement (VM) and Edge Insertion (EI), and to the probabilistic hill-climbing method Tübingen-Bus (TB). Note that while the latter approach was originally designed for minimizing the number of crossings in upward drawings, we could easily adjust it to drop the upward constraint [5].

We have presented a post-processing procedure to optimize quantifiable objectives like the global and local crossing number. For the global crossing number, some state-of-the-art approaches achieve better results. This may depend on our current RL implementation. We made some ad-hoc design choices for the observation vector and the action space based on octants; also we chose a specific vertex-selection procedure and reward function. For the local crossing number, our algorithm is among the best-performing methods. Note, however, that we are among the first to explicitly optimize the local crossing number. In the future, we will try to apply more and better-suited RL approaches to graph drawing problems.