CAREER: Fast algorithms via a spectral theory for graphs with a prescribed cut structure

职业：通过谱理论对具有指定切割结构的图进行快速算法

• 批准号: 1912051
• 负责人: Ioannis Koutis
• 金额: $ 4.61万
• 依托单位: New Jersey Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-22 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1912051&HistoricalAwards=false
• 关键词: CAREER; Fast; algorithms; via; spectral

Critical applications involving very large data sets require algorithms that run fast and provide strong performance guarantees. Among the numerous examples are the analysis of medical scans and the acquisition -via imaging- of connectivity in neural systems, an important task in current computational neuroscience. These problems are very often approached by first modeling the data as networks -also called graphs- and then applying graph-specific algorithms to solve them. Among many possibilities, algorithms that rely on certain algebraic representations of graphs have become very appealing due to recent theoretical progress that renders them very time-efficient. However, efficiency appears to come at the cost of an occasionally inferior quality in the generated solutions. Via the proposed extensions of the theory studying these algebraic representations, the project will design new algorithms with strong guarantees and wide applicability.Spectral graph theory studies the connections between algebraic and combinatorial properties of graphs. It is well known that these connections can be far from tight. For example, two given graphs may have approximately the same cuts, but significantly different eigenvalues and eigenvectors. As a result, spectral algorithms for cut problems on graphs, albeit very fast, do not provide good approximation guarantees. This project will extend aspects of spectral graph theory to a spectral theory for cut structures, defined as sets of graphs with approximately prescribed cuts. The central question of the new theory is: What kind of spectral properties can be realized by graphs within a given cut structure?A goal of the project is to show that any cut structure contains graphs whose eigenvectors provide tight information about its cuts. The project will also study algorithms for the efficient computation of these special graphs, by essentially modifying the spectrum of an input graph without significantly altering its cuts. Then, the combination of spectral modification and classical spectral algorithms will yield fast algorithms with enhanced approximation guarantees. The project will draw from connections of spectral graph theory with graph decompositions discovered in the context of oblivious routing algorithms. In turn, it is expected that the project will have an impact on routing problems too. In later stages the project will study the theoretical limits of spectral modification. It will also examine the descriptive quality of the developed theory in the performance of algorithms and other phenomena on interesting classes of graphs, such as social or biological networks.The project will freely disseminate prototype implementations of the new algorithms and will apply them to computer vision and machine learning problems in industry and academia. Applications will be pursued via selected interdisciplinary collaborations. The balance between theoretical and applied work will serve a broader educational effort at both the undergraduate and graduate level, which will also include the introduction of new courses. A significant part of the research will be carried out at the University of Puerto Rico, and so the project is expected to have a significant impact in the education of underrepresented minorities.

涉及非常大的数据集的关键应用程序需要快速运行并提供强大性能保证的算法。在众多的例子中，有医学扫描的分析和通过成像获取神经系统中的连通性，这是当前计算神经科学中的一项重要任务。这些问题通常通过首先将数据建模为网络（也称为图），然后应用特定于图的算法来解决它们。在许多可能性中，依赖于图的某些代数表示的算法已经变得非常有吸引力，这是由于最近的理论进展使得它们非常具有时间效率。 然而，效率似乎是以生成的解决方案偶尔质量低劣为代价的。通过对研究这些代数表示的理论提出的扩展，该项目将设计具有强保证和广泛适用性的新算法。谱图理论研究图的代数和组合性质之间的联系。众所周知，这些连接可能远非紧密。例如，两个给定的图可能具有近似相同的切割，但显著不同的特征值和特征向量。因此，谱算法切割问题的图，虽然非常快，不提供良好的近似保证。这个项目将谱图理论的各个方面扩展到切割结构的谱理论，定义为具有近似规定切割的图的集合。新理论的核心问题是：在给定的割结构中，图可以实现什么样的谱性质？该项目的一个目标是表明，任何切割结构包含的图，其特征向量提供有关其切割的紧密信息。 该项目还将研究这些特殊图形的有效计算算法，通过基本上修改输入图形的频谱而不显着改变其切割。然后，谱修改和经典谱算法的组合将产生具有增强的近似保证的快速算法。 该项目将从谱图理论与图分解的不经意路由算法的背景下发现的连接。反过来，预计该项目也将对路由问题产生影响。在后期阶段，该项目将研究光谱修改的理论极限。该项目还将研究所开发的理论在算法性能和其他有趣的图类（如社会或生物网络）上的现象的描述质量。该项目将免费传播新算法的原型实现，并将其应用于工业和学术界的计算机视觉和机器学习问题。申请将通过选定的跨学科合作进行。理论和应用工作之间的平衡将有助于在本科和研究生水平，这也将包括新课程的引入更广泛的教育努力。研究的很大一部分将在波多黎各大学进行，因此，该项目预计将对代表性不足的少数民族的教育产生重大影响。