Presentation
inGRASS: Incremental Graph Spectral Sparsification via Low-Resistance-Diameter Decomposition
DescriptionThis work presents inGRASS, a novel algorithm designed for incremental spectral sparsification of large undirected graphs. The proposed inGRASS algorithm is highly scalable and parallel-friendly, having a nearly linear time complexity for the setup phase and the ability to update the spectral sparsifier in $O(\log N)$ time for each incremental change made to the original graph with $N$ nodes. A key component in the setup phase of inGRASS is a multilevel resistance embedding step for efficiently identifying spectrally critical edges and effectively pruning spectrally similar ones, which is achieved by decomposing the initial sparsifier into node clusters with bounded effective-resistance diameters achieved through a low-resistance-diameter decomposition (LRD) scheme. The update phase of inGRASS exploits low-dimensional node embedding vectors for efficiently estimating the importance and uniqueness of each newly added edge. As demonstrated through extensive experiments, inGRASS achieves state-of-the-art results in incremental spectral sparsification of graphs obtained from various tasks, such as circuit simulations, finite element analysis, and social networks.
Event Type
Research Manuscript
TimeWednesday, June 2610:45am - 11:00am PDT
Location3010, 3rd Floor
EDA
Analog CAD, Simulation, Verification and Test