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.

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