标题： dyGRASS：基于局部随机游走的动态谱图稀疏化技术在GPU上的实现 显示英文标题

标题： dyGRASS: Dynamic Spectral Graph Sparsification via Localized Random Walks on GPUs

摘要： 本文介绍了一种高效的动态算法dyGRASS，用于大规模无向图的谱稀疏化，这些图经历了流式边插入和删除。 该算法的核心采用基于随机游走的方法，高效估计原始图（用于减量更新）及其稀疏表示图（用于增量更新）中的节点到节点距离。 对于增量更新，dyGRASS能够识别更新中的谱临界边以捕捉最新的结构变化。 对于减量更新，dyGRASS有助于从原始图恢复重要边回到稀疏表示图。 为了进一步提高计算效率，dyGRASS采用基于GPU的非回溯随机游走方案，允许多个行走者同时在各种目标更新上操作。 这种并行化显著提高了所提出的dyGRASS框架的性能和可扩展性。 我们的综合实验评估显示，与最先进的增量稀疏化（inGRASS）算法相比，dyGRASS实现了大约10倍的速度提升，同时消除了设置开销并在增量谱稀疏化任务中提高了解的质量。 此外，dyGRASS在完全动态图稀疏化中提供了高效率和优越的解质量，适用于来自集成电路模拟、有限元分析和社会网络的各种图实例中的边插入和删除。 显示英文摘要

摘要： This work presents dyGRASS, an efficient dynamic algorithm for spectral sparsification of large undirected graphs that undergo streaming edge insertions and deletions. At its core, dyGRASS employs a random-walk-based method to efficiently estimate node-to-node distances in both the original graph (for decremental update) and its sparsifier (for incremental update). For incremental updates, dyGRASS enables the identification of spectrally critical edges among the updates to capture the latest structural changes. For decremental updates, dyGRASS facilitates the recovery of important edges from the original graph back into the sparsifier. To further enhance computational efficiency, dyGRASS employs a GPU-based non-backtracking random walk scheme that allows multiple walkers to operate simultaneously across various target updates. This parallelization significantly improves both the performance and scalability of the proposed dyGRASS framework. Our comprehensive experimental evaluations reveal that dyGRASS achieves approximately a 10x speedup compared to the state-of-the-art incremental sparsification (inGRASS) algorithm while eliminating the setup overhead and improving solution quality in incremental spectral sparsification tasks. Moreover, dyGRASS delivers high efficiency and superior solution quality for fully dynamic graph sparsification, accommodating both edge insertions and deletions across a diverse range of graph instances originating from integrated circuit simulations, finite element analysis, and social networks.