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 2025, and the current team consists of the PI, 1 Postdocs, 3 PhD students, and 1 Research Interns.
Team
He Sun, Principal Investigator
John Stewart Fabila Carrasco, Postdoctoral Researcher
Joyentanuj Das, Postdoctoral Researcher
Ben Jourdan, PhD Student
Steinar Laenen, PhD Student
Suranjan De, 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.
Publication
Can we measure the impact of a database?
with P. Buneman, D. Dosso, M. Lissandrini, and G. Silvello.
arXiv version
Dynamic Spectral Clustering with Provable Approximation Guarantee.
with S. Laenen (ICML'24).
Conference version | arXiv version | Code
Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime.
with B. Jourdan, and P. Macgregor.
arXiv version
Fast Approximation of Similarity Graphs with Kernel Density Estimation.
with P. Macgregor (NeurIPS'23, Spotlight).
Conference version | arXiv version | Code
Fast and Simple Spectral Clustering in Theory and Practice. P. Macgregor (NeurIPS'23).
Three Hardness Results for Graph Similarity Problems. with D. Vagnozzi. submitted
arXiv version
Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs.
with B. Manghiuc and S. Laenen (ICML'23).
Conference version | arXiv version | Talk | Code
The Support of Open versus Closed Random Walks.
with T. Sauerwald, and D. Vagnozzi (ICALP'23).
Conference version
Is the Algorithmic Kadison-Singer Problem Hard? with B. Jourdan, and P. Macgregor (ISAAC'23).
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 | Talk |
Code
Hierarchical clustering: O(1)-approximation for well-clustered graphs.
with B. Manghiuc (NeurIPS'21).
Conference version |
arXiv version | Talk |
Code
Finding bipartite components in hypergraphs.
with P. Macgregor (NeurIPS'21).
Conference version |
arXiv version | Talk |
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