SHF: Small: Spectral Reduction of Large Graphs and Circuit Networks

SHF：小：大型图和电路网络的频谱缩减

• 批准号: 1909105
• 负责人: Zhuo Feng
• 金额: $ 50万
• 依托单位: Michigan Technological University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2020-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909105&HistoricalAwards=false
• 关键词: SHF; Small; Spectral; Reduction; Large

Spectral methods are playing increasingly important roles in many graph and numerical applications. This research plan will investigate a truly-scalable yet unified spectral graph reduction approach that allows reducing large-scale, real-world directed and undirected graphs with guaranteed preservation of the original graph spectra. The success of the proposed research will significantly advance the state of the arts in spectral graph theory, electronic design automation (EDA), data mining, machine learning, as well as scientific computing, leading to the development of much faster numerical and graph-based algorithms. The algorithms and methodologies to be developed will be disseminated to leading technology companies such as EDA software and network companies for potential industrial adoptions. Spectral graph reduction algorithms/software packages will also be made available to other researchers through collaborations.The project will investigate a truly-scalable yet unified spectral graph reduction approach by exploiting a scalable (nearly-linear complexity) spectral matrix perturbation analysis framework for constructing nearly-linear sized subgraphs that can well preserve the key eigenvalues and eigenvectors of the original graph Laplacians. Unlike prior methods that are only suitable for handling specific types of graphs (e.g. undirected or strongly-connected graphs), this project uses a more universal approach and thus will allow for spectral reduction of a much wider range of real-world graphs that may involve billions of elements: spectrally-reduced social (data) networks allow for more efficiently modeling, mining and analysis of large social (data) networks; spectrally-reduced neural networks allow for more scalable model training and processing in emerging machine learning tasks; spectrally-reduced web-graphs allow for much faster computations of personalized PageRank vectors; spectrally-reduced integrated circuit networks will lead to more efficient partitioning, modeling, simulation, optimization and verification of large chip designs, etc.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

谱方法在许多图形和数值应用中发挥着越来越重要的作用。该研究计划将研究一种真正可扩展且统一的谱图约简方法，该方法允许在保证保持原始图谱的情况下减少大规模、真实世界的有向图和无向图。拟议研究的成功将极大地推动谱图理论、电子设计自动化(EDA)、数据挖掘、机器学习以及科学计算的发展，导致更快的数值和基于图形的算法的发展。将开发的算法和方法将传播给领先的技术公司，如EDA软件和网络公司，以供潜在的工业采用。谱图约简算法/软件包也将通过合作提供给其他研究人员。该项目将研究一种真正可扩展且统一的谱图约简方法，该方法利用可伸缩(近线性复杂性)谱矩阵扰动分析框架来构造近线性大小的子图，该子图能够很好地保持原始图拉普拉斯算子的关键特征值和特征向量。与仅适用于处理特定类型的图(例如，无向图或强连接图)的现有方法不同，该项目使用更通用的方法，因此将允许对可能涉及数十亿元素的更广泛的真实世界图进行频谱缩减：频谱缩减的社会(数据)网络允许更高效地对大型社交(数据)网络进行建模、挖掘和分析；频谱缩减的神经网络允许在新兴的机器学习任务中进行更可伸缩的模型训练和处理；频谱缩减的网络图允许更快地计算个性化页面排名向量；频谱缩减的集成电路网络将导致大型芯片设计的更有效的分区、建模、模拟、优化和验证等。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

A Spectral Approach to Scalable Vectorless Thermal Integrity Verification

可扩展无矢量热完整性验证的光谱方法

• DOI: 10.23919/date48585.2020.9116438
• 发表时间: 2020
• 期刊: Automation & Test in Europe Conference & Exhibition (DATE
• 作者: Zhao, Zhiqiang;Feng, Zhuo
• 通讯作者: Feng, Zhuo

GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding

• 发表时间: 2019-10
• 期刊: ArXiv
• 作者: Chenhui Deng;Zhiqiang Zhao;Yongyu Wang;Zhiru Zhang;Zhuo Feng

Spectrum-preserving sparsification for visualization of big graphs

• DOI: 10.1016/j.cag.2020.02.004
• 发表时间: 2020-04-01
• 期刊: COMPUTERS & GRAPHICS-UK
• 影响因子: 2.5
• 作者: Imre, Martin;Tao, Jun;Wang, Chaoli
• 通讯作者: Wang, Chaoli