Collaborative Research: SHF: Medium: Co-optimizing Spectral Algorithms and Systems for High-Performance Graph Learning

新兴的图学习技术在社区检测、药物发现和电子设计自动化(EDA)等各种重要应用中显示了良好的结果。然而，即使是最先进的图学习方法也不能扩展到大数据集，因为它们的算法复杂性很高。例如，最新的图神经网络(GNN)算法集中聚集了每个节点邻域的特征信息，这不仅大大增加了节点之间的计算次数，而且导致了存储中间结果的高内存使用率。因此，大多数图学习算法由于其高昂的计算和存储开销而不能有效地处理大规模问题，更不用说可能涉及数十亿条边的真实世界的图。本项目旨在通过研究基于最新理论突破的高性能谱图算法和系统来解决现代图学习任务中最紧迫的挑战。与以往谱图理论研究较少关注实际算法实现和应用不同，本项目的研究人员将开发实用高效的谱图压缩算法，通过算法和系统的联合优化来提高现有图学习方法的效率和解的质量，利用最新的异构计算设备，如图形处理器、现场可编程门阵列和计算存储设备。该项目的成果将潜在地推动谱图理论、机器学习、数据分析、EDA以及高性能计算的最先进水平。该项目还可能引发其他相关计算机科学和工程领域的新研究，如复杂系统/网络建模、计算生物学、精确医学和交通网络。研究人员将与史蒂文斯的STEM大使计划和康奈尔大学的工程多样性计划办公室合作，招募高度多元化的本科生和研究生参与这个项目，同时最新的研究成果将被整合到几个研究生和高级本科课程中，为高性能机器学习方面的新一代研究人员和实践者做准备。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Emerging graph learning techniques have shown promising results for various important applications such as community detection, drug discovery, and electronic design automation (EDA). However, even the state-of-the-art graph learning methods cannot scale to large data sets due to their high algorithm complexity. For example, the latest graph neural network (GNN) algorithms collectively aggregate feature information from the neighborhood of each node, which not only drastically increases the number of computations among nodes but also leads to high memory usage for storing the intermediate results. Hence most graph learning algorithms cannot efficiently handle large-scale problems due to their high computation and storage costs, not to mention the real-world graphs that may involve billions of edges.This project aims at addressing the most pressing challenges in modern graph learning tasks by investigating high-performance spectral graph algorithms and systems based on the latest theoretical breakthroughs. Unlike prior theoretical studies on spectral graph theory that put less focus on practical algorithm implementations and applications, the investigators of this project will develop practically-efficient spectral graph compression algorithms to boost the efficiency and solution quality of existing graph learning methods through algorithm and system co-optimizations by taking advantage of the latest heterogeneous computing devices, such as GPUs, FPGAs, and computational storage devices. The outcome of this project will potentially advance the state of the art in spectral graph theory, machine learning, data analytics, EDA, as well as high-performance computing. This project is also likely to spark new research in other related computer science and engineering fields such as complex system/network modeling, computational biology, precision medicine, and transportation networks. The investigators will partner with the STEM ambassador program at Stevens, and the Diversity Programs in Engineering office at Cornell to recruit highly diversified undergraduate and graduate students to participate in this project, while the latest research results will be integrated into several graduate and upper-division undergraduate courses to prepare a new generation of researchers and practitioners in high-performance machine learning.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.