权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Efficient Spectral Algorithms for Massive and Dynamic Graphs

适用于海量动态图的高效谱算法

基本信息

批准号：
EP/T00729X/1
负责人：
He Sun
金额：
$ 153.63万
依托单位：
University of Edinburgh
依托单位国家：
英国
项目类别：
Fellowship
财政年份：
2020
资助国家：
英国
起止时间：
2020 至无数据
项目状态：
未结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FT00729X%2F1
关键词：
Efficient Spectral Algorithms Massive Dynamic

项目摘要

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.

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