He Sun

Efficient Spectral Algorithms for Massive and Dynamic Graphs

EPSRC Early Career Fellowship

Efficient Spectral Algorithms for Massive and Dynamic Graphs is an EPSRC Fellowship awarded to He Sun (EP/T00729X/1). The fellowship studies advances of spectral graph theory, designs efficient spectral algorithms for massive and dynamic graphs, and develops an open-source library of spectral algorithms for graphs. With a total award of 1,507,133 pounds, the Fellowship runs from 2020 to 2024, and the current team consists of the PI, 2 Postdocs, and 2 PhD students. This presentation summaries the recent activities of the research group.


He Sun, Principal Investigator

Aparajita Haldar, Postdoctoral Researcher (to start in May 2023)

Peter Macgregor, Postdoctoral Researcher

Danny Vagnozzi, Postdoctoral Researcher

Ben Jourdan, PhD Student

Steinar Laenen, PhD Student

STAG: Spectral Toolkit of Algorithms for Graphs

As part of the Fellowship, we are developing STAG, an open-source library of efficient spectral algorithms for graphs. STAG is the first such algorithmic library mainly written in C++, with a python wrapper around the underlying C++ library for python users. The source code of STAG can be found from our GitHub page, and will be updated actively. More information can be also found from the STAG website.


Measuring the Impact of a Database, with P. Buneman, D. Dosso, M. Lissandrini, and G. Silvello.

Is the Algorithmic Kadison-Singer Problem Hard? with B. Jourdan, and P. Macgregor. submitted
arXiv version

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. with A. Bernstein, J. van den Brand, M. Gutenberg, D. Nanongkai, T. Saranurak, and A. Sidford (ICALP'22).
Conference version | arXiv version

A Tighter Analysis of Spectral Clustering, and Beyond. with P. Macgregor (ICML'22).
Conference version | arXiv version | Code

Hierarchical clustering: O(1)-approximation for well-clustered graphs. with B. Manghiuc (NeurIPS'21).
Conference version | arXiv version | Code

Finding bipartite components in hypergraphs. with P. Macgregor (NeurIPS'21).
Conference version | arXiv version | Code

Local algorithms for finding densely connected clusters. with P. Macgregor (ICML'21 for a long talk).
Conference version | arXiv version | Talk | Code

Higher-order spectral clustering of directed graphs. with S. Laenen (NeurIPS'20).
Conference version | arXiv version | Talk

Augmenting the Algebraic Connectivity of Graphs. with B. Manghiuc, and P. Peng (ESA'20)
Conference version | arXiv version

Hermitian matrices for clustering directed graphs: insights and applications. with M. Cucuringu, H. Li, and L. Zanetti (AISTATS'20).
Conference version | arXiv version