Presentation
dyGRASS: Dynamic Spectral Graph Sparsification via Localized Random Walks on GPUs
DescriptionThis work introduces dyGRASS, an efficient dynamic algorithm designed for spectral sparsification of large undirected graphs that undergo streaming edge insertions and deletions. The core of dyGRASS is a random-walk-based method to efficiently estimate node-to-node distances in both the original graph and its sparsifier. This approach helps identify the most crucial edges from the updating edges, which are necessary to maintain distance relationships. It also aids in the recovery of essential edges from the original graph back into the sparsifier when edge deletions occur. To improve computational efficiency, we developed a GPU-based random walk kernel to allow multiple walkers to operate simultaneously across different targets. This parallelization significantly enhances the performance and effectiveness of the dyGRASS framework. Our comprehensive experimental evaluations demonstrate that dyGRASS achieves approximately a twofold speedup while eliminating setup overhead and improving solution quality compared to inGRASS in incremental spectral sparsification. Furthermore, dyGRASS achieves high efficiency and solution quality for fully dynamic graph sparsification involving both edge insertions and deletion operations for various graph instances derived from circuit simulations, finite element analysis, and social networks.
Event Type
Networking
Work-in-Progress Poster
TimeMonday, June 236:00pm - 7:00pm PDT
LocationLevel 2 Lobby