Efficient Spectral Algorithms for Massive and Dynamic Graphs

谱图理论研究与图相关的矩阵的代数性质。在过去的20年里，谱图理论的研究成功地克服了组合算法面临的基本瓶颈，并成为理论计算机科学、机器学习和网络分析的主要研究热点。特别是，最近的一些突破性结果表明，谱技术可以在近线性时间内解决中心优化和学习问题。设计如此高效的算法对于应对来自技术、社会和生物网络的大量图形和实时数据集的出现至关重要。在这项奖学金中，我提出了三个研究方向来推进光谱算法的研究及其在数据科学中的应用：(1)我建议通过研究表示有向图的不同矩阵的光谱特性，探索图与其他数学对象（例如几何中研究的流形）之间的新联系，来推进我们对基本光谱技术的理解；(2)针对两个基本图问题，在不同环境下研究新的谱算法，并在算法的运行时间和性能方面进一步改进这两个问题的现状；(3)在最坏的情况下，谱算法在运行时间上大大优于组合算法，然而大多数谱算法的设计通常涉及许多过程，这为有效实现带来了数值稳定性问题。为了解决这个问题，我建议为光谱算法开发一个开源算法库，以便在奖学金结束时数据科学家能够使用最先进的算法以黑箱方式进行光谱稀疏化和图聚类。该奖学金的成功完成将使理解代数技术在各种设置中设计快速图算法的能力和局限性，以及在现实世界数据集中近线性时间谱算法的性能迈出重要的一步。

Spectral graph theory investigates the algebraic properties of matrices associated with graphs. Over the past 20 years, studies in spectral graph theory have successfully overcome fundamental bottlenecks faced by combinatorial algorithms, and have become a major research focus in theoretical computer science, machine learning, and network analysis. In particular, some recent breakthrough results show that spectral techniques can be applied to solve central optimisation and learning problems in nearly-linear time. Designing such highly efficient algorithms is crucial to cope with the emergence of massive graphs and real-time data sets coming from technological, social and biological networks. In this fellowship I propose three research directions to advance the studies of spectral algorithms and their applications in data science: (1) I propose to advance our understanding of fundamental spectral techniques by studying the spectral properties of different matrices representing directed graphs, and exploring new connections between graphs and other mathematical objects, e.g., manifolds studied in geometry; (2) I propose to investigate new spectral algorithms for two fundamental graph problems in different settings, and further improve the state-of-the-art of the two problems with respect to the algorithms' runtime and performance; (3) spectral algorithms vastly outperform combinatorial algorithms with respect to their runtime in the worst case, however the design of most spectral algorithms usually involve many procedures, which bring the issue of numerical stability for efficient implementations. To address this I propose to develop an open-source algorithmic library for spectral algorithms so that by the end of the fellowship data scientists would be able to use the state-of-the-art algorithms for spectral sparsification and graph clustering in a black box manner.A successful completion of the fellowship will make a significant step towards understanding the power and limits of the algebraic techniques in designing fast graph algorithms in various settings, and the performance of nearly-linear time spectral algorithms in real world data sets.