Effective-Resistance Preserving Spectral Reduction of Graphs
Effective-Resistance Preserving Spectral Reduction of Graphs
复制标题
DOI：
10.1145/3316781.3317809
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Zhiqiang Zhao;Zhuo Feng
中科院分区：
文献类型：
--
作者：
Zhiqiang Zhao;Zhuo Feng
本文提出了一种可扩展的算法框架，用于大型无向图的有效电阻保持谱约简。所提出的方法允许计算更小的图，同时保留原始图的关键谱（结构）属性。我们的框架建立在以下三个关键组件之上：频谱保留节点聚合和缩减方案、具有迭代边缘权重缩放的频谱图稀疏框架，以及有效电阻保留后缩放和迭代解决方案细化方案。通过利用最近的相似性感知谱稀疏化方法和图论代数多重网格（AMG）拉普拉斯求解器，提出了一种新颖的约束随机梯度下降（SGD）优化方法，用于实现谱图缩减的真正可扩展性能（接近线性复杂度）。我们表明，所得的谱简化图可以稳健地保留原始图拉普拉斯的前几个非平凡特征值和特征向量，从而允许开发高度可扩展的谱图划分和电路仿真算法。ACM 参考格式：Zhiqiang Zhao 和 Zhuo Feng。 2019.有效电阻保持图谱缩减。 2019 年第 56 届年度设计自动化会议 (DAC '19)，2019 年 6 月 2-6 日，美国内华达州拉斯维加斯。 ACM，美国纽约州纽约市，6 页。 https://doi.org/10.1145/3316781.3317809
This paper proposes a scalable algorithmic framework for effective-resistance preserving spectral reduction of large undirected graphs. The proposed method allows computing much smaller graphs while preserving the key spectral (structural) properties of the original graph. Our framework is built upon the following three key components: a spectrum-preserving node aggregation and reduction scheme, a spectral graph sparsification framework with iterative edge weight scaling, as well as effective-resistance preserving post-scaling and iterative solution refinement schemes. By leveraging recent similarity-aware spectral sparsification method and graph-theoretic algebraic multigrid (AMG) Laplacian solver, a novel constrained stochastic gradient descent (SGD) optimization approach has been proposed for achieving truly scalable performance (nearly-linear complexity) for spectral graph reduction. We show that the resultant spectrally-reduced graphs can robustly preserve the first few nontrivial eigenvalues and eigenvectors of the original graph Laplacian and thus allow for developing highly-scalable spectral graph partitioning and circuit simulation algorithms.ACM Reference Format:Zhiqiang Zhao and Zhuo Feng. 2019. Effective-Resistance Preserving Spectral Reduction of Graphs. In The 56th Annual Design Automation Conference 2019 (DAC '19), June 2–6, 2019, Las Vegas, NV, USA. ACM, New York, NY, USA, 6 pages. https://doi.org/10.1145/3316781.3317809