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.

图形是关系的自然抽象，被广泛用于模拟各种情况的数据，例如社交网络，深层神经网络和人脑神经元系统。科学研究界从图形的深刻表现性和分析能力中受益。但是，随着可用数据量的爆炸性增长，传统的图算法通常没有效率。该项目旨在从图形稀疏方面开发更快的图形算法，该算法将大图压缩到小图中，以便可以在较小的图表上执行计算。该项目的目的是将图形稀疏作为图形算法的新范式，并为图表问题提供新的基于稀疏的软件，这些软件对于机器学习，数据挖掘和计算生物学中的应用至关重要。研究人员将通过为本科生和研究生提供研究机会并将研究结果整合到相关课程中，将研究紧密地纳入教育。该项目旨在调查图形顶点稀疏工具，以减少图形和图形边缘，同时保留某些图形属性，同时保持某些图形属性顶点的子集。顶点稀疏的主要挑战在于一个事实，即通过线性操作员（例如高斯消除）很难实现顶点，而高斯消除是经典边缘降低所采用的。为了应对这一挑战，该项目将着重于开发和分析非线性操作员，例如组合截断和非线性代数变换，以构建用于基本图形属性的新顶点拼写器。此外，该项目还将提出用于设计基于顶点 - 平衡算法的新原则。特别是，这将包括将顶点弹药酶与优化方法结合在一起，研究弹药板和其他结构（例如图形分解）之间的相互作用，并确定稀疏器的关键特征，这些特征能够在动态，分布式和并行设置中应用其应用。使命，并被认为是通过基金会的知识分子优点和更广泛影响的审查标准通过评估值得支持的。

项目成果

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