摘要
应力模型是计算节点连接图布局时最常用的方法之一.随机梯度下降法由于具有很好的收敛性,常被用于求解应力模型,但该方法难以实现有效并行.虽然无锁随机梯度下降方法能大幅提高并行效率,但其求解过程中常存在线程冲突,导致结果准确性低.为了提高并行图布局的效率和准确性,提出一种无冲突的随机梯度下降的并行求解方法.首先提出一种面向应力模型的线程分配算法,将与节点j相同的点对分配到同一线程内计算,保证基于随机梯度下降方法的图布局无冲突化求解;然后仅对线程内的样本随机洗牌并减少次数,进一步提升并行效率.在16个不同规模的真实数据集上进行实验,并将所提方法应用在稀疏化应力模型的求解上,实验结果显示所提方法在求解精度上无损失且求解速度提高10倍以上,从布局质量和运行效率2个方面证明了该方法的高效性和可用性.
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.
作者
王智
薛明亮
王一凡
钟发海
汪云海
Wang Zhi;Xue Mingliang;Wang Yifan;Zhong Fahai;Wang Yunhai(School of Computer Science and Technology,Shandong University,Qingdao 266237;School of Software and Technology,Shandong University,Jinan 250101;School of Information,Renmin University of China,Beijing 100872)
出处
《计算机辅助设计与图形学学报》
北大核心
2025年第6期1063-1072,共10页
Journal of Computer-Aided Design & Computer Graphics
基金
科技创新2030—“新一代人工智能”重大项目(2022ZD0160805)
国家自然科学基金(62132017,62141217)
山东省自然科学基金(ZQ2022JQ32)。
关键词
图布局
随机梯度下降
并行计算
图可视化
graph layout
stochastic gradient descent
parallel computing
graph visualization
