CAREER: On Non-Linear Graph Eliminations

图是关系的自然抽象，被广泛用于对来自各种场景的数据建模，例如社交网络、深度神经网络和人脑神经元系统。科学研究界受益于图形的深刻的可表达性和分析能力。然而，随着可用数据量的爆炸式增长，传统的图算法往往效率不足。该项目旨在从图稀疏化方面开发更快的图算法，将大图压缩成小图，以便在较小的图上进行计算。该项目的目标是推进图稀疏化作为图算法的新范式，并为图问题提供新的基于稀疏化的软件，这些软件对机器学习、数据挖掘和计算生物学中的应用至关重要。研究者将通过为本科生和研究生提供研究机会，并将研究成果整合到相关课程中，将研究与教育紧密结合。该项目旨在研究图顶点稀疏化工具，该工具可以减少图的顶点和边，同时保留顶点子集之间的某些图属性。顶点稀疏化的主要挑战在于，经典的边缘约简采用高斯消去等线性算子难以实现顶点的约简。为了应对这一挑战，该项目将专注于开发和分析非线性算子，如组合截断和非线性代数变换，以构建用于基本图属性的新顶点稀疏器。此外，本项目将提出设计基于顶点稀疏的算法的新原则。特别是，这将包括将顶点稀疏化器与优化方法结合起来，研究稀疏化器与其他结构（如图分解）之间的交互，并确定稀疏化器的关键特征，使其能够在动态、分布式和并行设置中应用。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Graphs, being natural abstractions of relationships, are widely used to model data from various scenarios, such as social networks, deep neural networks, and human brain neuron systems. The scientific research community has benefited from the profound expressibility and analysis power of graphs. However, with the explosive growth in the amount of available data, traditional graph algorithms often fall short of efficiency. This project aims to develop faster graph algorithms from the aspect of graph sparsification, which compresses large graphs into small graphs so that computation can be performed on smaller graphs. The goal of this project is to advance graph sparsification as a new paradigm of graph algorithms and to provide new sparsification-based software for graph problems that are crucial to applications in machine learning, data mining, and computational biology. The investigator will incorporate the research closely into education by providing research opportunities for undergraduate and graduate students and integrating the research results into related courses.This project aims to investigate graph vertex sparsification tools that reduce both vertices and edges of graphs while preserving certain graph properties between a subset of vertices. The major challenge of vertex sparsification lies in the fact that the reduction of vertices is difficult to achieve with linear operators, such as Gaussian elimination, which are employed by classic edge reduction. To address this challenge, this project will focus on developing and analyzing non-linear operators, such as combinatorial truncation and non-linear algebraic transform, to construct new vertex sparsifiers for fundamental graph properties. In addition, this project will propose new principles for designing vertex-sparsification-based algorithms. Particularly, this will include incorporating vertex sparsifiers with optimization methods, investigating the interaction between sparsifiers and other structures such as graph decompositions, and identifying the key features of sparsifiers that enable their applications in dynamic, distributed, and parallel settings.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.