STAG: Spectral Toolkit of Algorithms for Graphs

STAG is an open-source library for efficient spectral algorithms. It is the first such algorithmic library mainly written in C++, with a python wrapper STAGPy around the underlying C++ library for python users.


Component on Local Graph Clustering

Given a vertex of some underlying graph as input, a local graph clustering algorithm is to find some low-conductance set around the input vertex, while the algorithm runs in time proportional to the size of the target cluster and independent of the size of the entire graph. As one of the key components in designing nearly-linear time graph algorithms, local graph clustering has been extensively studied in algorithmic spectral graph theory.

The GitHub page contains our implemention of the local graph clustering based on PageRank (the ACL algorithm). Comparing with several existing open-source implementation for local graph clustering, our code connects to a Neo4j database running in the AuraDB cloud service, or a database running locally. With this feature, one can run local graph clustering on the entire Wikipedia graph of more than 20GB with a single PC.


Reference

Reid Andersen, Fan R. K. Chung, Kevin J. Lang: Local Graph Partitioning using PageRank Vectors. FOCS 2006: 475-486

Daniel A. Spielman, Shang-Hua Teng: A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM J. Comput. 42(1): 1-26 (2013)

Technical Reports


This series of technical reports is to document our progress on STAG, including implementation details, engineering considerations, and the data sets against which our implementation is tested.

Technical Report (1)

This report describes local graph clustering, provides a user guide to the essential features of STAG which allow a user to apply local clustering, and includes experiments and demonstrations of the functionality of STAG. The final part of the report discusses several technical details. Read here

About STAG


This project is part of He Sun's 5-year EPSRC Fellowship titled "Efficient Spectral Algorithms for Massive and Dynamic Graphs" with a total award of 1.5 million pounds. We are based in the School of Informatics, University of Edinburgh, United Kingdom.

Code

You can find STAG's source code from our Github page .

Funding Information

UK Engineering and Physical Sciences Research Council, EP/T00729X/1

Contact

Postal address

School of Informatics
University of Edinburgh
Edinburgh, EH8 9AB
United Kingdom