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.