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

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

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.