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 accuracy of results. 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, which assigns pairs of nodes with the same j to the same thread for computation, thus ensuring a conflict-free graph layout solution based on SGD. Secondly, the parallel efficiency is further improved by shuffling only the samples within each thread and reducing the number of iterations. 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. The experimental results show that the proposed method achieves no loss in solution accuracy and increases the solution speed by more than tenfold, demonstrating the efficiency and usability of the proposed method in terms of layout quality and runtime efficiency.