CAREER: On Non-Linear Graph Eliminations

职业：关于非线性图消除

• 批准号: 2240024
• 负责人: Xiaorui Sun
• 金额: $ 56.1万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-02-01 至 2028-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2240024&HistoricalAwards=false
• 关键词: CAREER; 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.

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

项目成果

Faster Isomorphism for ?-Groups of Class 2 and Exponent ?

2 类和指数的 ?-群的更快同构？

• DOI: 10.1145/3564246.3585250
• 发表时间: 2023
• 期刊: ACM
• 作者: Sun, Xiaorui

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

次多项式时间内超常数尺寸的全动态最小割

• 发表时间: 2024
• 期刊: SIAM
• 作者: Jin, Wenyu;Sun, Xiaorui;Thorup, Mikkel
• 通讯作者: Thorup, Mikkel