Graph Drawing by Conflict-Free Parallel Stochastic Gradient Descent

The stress model is one of the most commonly used methods for graph layout. The stochastic gradient descent (SGD) algorithm is often used to solve the stress model due to its ease of convergence, but it is difficult to implement effective parallelization. Although the lock-free SGD method can greatly improve parallel efficiency, there are often thread conflicts during the solution process, leading to low result accuracy. To improve the efficiency and accuracy of parallel graph layout, this paper proposes a conflict-free parallel SGD solution method. Firstly, a thread allocation algorithm for the stress model is designed to ensure a conflict-free graph layout solution based on SGD. Secondly, by shuffling only the samples within each thread and reducing the number of iterations, the parallel efficiency is further improved. To test the efficiency of this method, comparative experiments were conducted on 16 real datasets of different scales, and the proposed method was applied to solve the sparse stress model, demonstrating the efficiency and usability of the proposed method in terms of layout quality and runtime efficiency.