Research

My overall research goal is to develop fast, effective, theoretically-grounded algorithms to power data science applications. At the moment, my focus is on improving algorithms for clustering, similarity search, and numerical linear algebra.

Highlighted Projects

Fast Spectral Clustering Code

Improved Spectral Clustering

Spectral clustering has been used for over two decades for clustering graphs and other data. Unfortunately, it has suffered from some scalability issues which may have limited its adoption in practice. It also had limited theoretical guarantees until recently.

In my recent work, I have (i) improved the theoretical analysis of spectral clustering and (ii) provided improved algorithms which allow spectral clustering to scale to large datasets with large numbers of clusters.

[1] Macgregor, Peter, and He Sun. "A tighter analysis of spectral clustering, and beyond." International Conference on Machine Learning. PMLR, 2022.

[2] Macgregor, Peter, and He Sun. "Fast approximation of similarity graphs with kernel density estimation." 36th Advances in Neural Information Processing Systems (NeurIPS 2024).

[3] Macgregor, Peter. "Fast and simple spectral clustering in theory and practice." 36th Advances in Neural Information Processing Systems (NeurIPS 2024).

STAG Library Website

STAG Library

The Spectral Toolkit of Algorithms for Graphs (STAG) library is a C++ and Python library providing an easy-to-use implementation of several recently developed algorithms for graph and data analysis.

As well as generic methods for constructing and working with graphs, STAG provides implementations of local graph clustering and spectral clustering, locality-sensitive hashing (LSH), and kernel density estimation (KDE).

For more information on how to use STAG and to see some of its functionality, please refer to the technical reports available on the STAG website.

All Publications

Tech. Report

Spectral Toolkit of Algorithms for Graphs: Technical Report (2)

Peter Macgregor and He Sun

@article{stag_report_2,
  author       = {Peter Macgregor and He Sun},
  title        = {Spectral Toolkit of Algorithms for Graphs: Technical Report {(2)}},
  journal      = {CoRR},
  volume       = {abs/2407.07096},
  year         = {2024},
  doi          = {10.48550/arXiv.2407.07096},
  eprinttype    = {arXiv},
  eprint       = {2407.07096},
}  

arXiv PDF code

---

Preprint

Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime

Ben Jourdan, Peter Macgregor, and He Sun

@misc{jourdan2024polynomialtime,
  title={Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime}, 
  author={Ben Jourdan and Peter Macgregor and He Sun},
  year={2024},
  eprint={2402.08545},
  archivePrefix={arXiv},
  primaryClass={cs.DS}
}

arXiv

---

NeurIPS 2023 Spotlight

Fast Approximation of Similarity Graphs with Kernel Density Estimation

Peter Macgregor and He Sun

@inproceedings{macgregorKDESimilarityGraph2023,
  title = {Fast Approximation of Similarity Graphs with Kernel Density Estimation},
  booktitle = {36th {{Advances}} in {{Neural Information Processing Systems}} ({{NeurIPS}}'23)},
  author = {Peter Macgregor and He Sun},
  year = {2023}
}

arXiv conference talk code

---

NeurIPS 2023

Fast and Simple Spectral Clustering in Theory and Practice

Peter Macgregor

@inproceedings{macgregorFastSpectralClustering2023,
  title = {Fast and Simple Spectral Clustering in Theory and Practice},
  booktitle = {36th {{Advances}} in {{Neural Information Processing Systems}} ({{NeurIPS}}'23)},
  author = {Macgregor, Peter},
  year = {2023}
}

arXiv conference talk code

---

ISAAC 2023

Is the Algorithmic Kadison-Singer Problem Hard?

Ben Jourdan, Peter Macgregor, and He Sun

@InProceedings{jourdan_et_al:LIPIcs.ISAAC.2023.43,
  author =	{Jourdan, Ben and Macgregor, Peter and Sun, He},
  title =	{{Is the Algorithmic Kadison-Singer Problem Hard?}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.43},
  URN =		{urn:nbn:de:0030-drops-193457},
  doi =		{10.4230/LIPIcs.ISAAC.2023.43},
  annote =	{Keywords: Kadison-Singer problem, spectral sparsification}
}

arXiv conference

---

Tech. Report

Spectral Toolkit of Algorithms for Graphs: Technical Report (1)

Peter Macgregor and He Sun

@article{stag_report_1,
  author       = {Peter Macgregor and He Sun},
  title        = {Spectral Toolkit of Algorithms for Graphs: Technical Report {(1)}},
  journal      = {CoRR},
  volume       = {abs/2304.03170},
  year         = {2023},
  doi          = {10.48550/arXiv.2304.03170},
  eprinttype    = {arXiv},
  eprint       = {2304.03170},
}  

arXiv PDF code

---

ICML 2022

A Tighter Analysis of Spectral Clustering, and Beyond

Peter Macgregor and He Sun

@inproceedings{macgregorTighterAnalysisSpectral2022,
  title = {A Tighter Analysis of Spectral Clustering, and Beyond},
  booktitle = {39th {{International Conference}} on {{Machine Learning}} ({{ICML}}'22)},
  author = {Macgregor, Peter and Sun, He},
  year = {2022},
  pages = {14717--14742}
}

arXiv conference talk code

---

NeurIPS 2021

Finding Bipartite Components in Hypergraphs

Peter Macgregor and He Sun

@inproceedings{macgregorFindingBipartiteComponents2021,
  title = {Finding Bipartite Components in Hypergraphs},
  booktitle = {34th {{Advances}} in {{Neural Information Processing Systems}} ({{NeurIPS}}'21)},
  author = {Macgregor, Peter and Sun, He},
  year = {2021},
  pages = {7912--7923}
}

arXiv conference talk code

---

ICML 2021 Oral

Local Algorithms for Finding Densely Connected Clusters

Peter Macgregor and He Sun

@inproceedings{macgregorLocalAlgorithmsFinding2021,
  title = {Local Algorithms for Finding Densely Connected Clusters},
  booktitle = {38th {{International Conference}} on {{Machine Learning}} ({{ICML}}'21)},
  author = {Macgregor, Peter and Sun, He},
  year = {2021},
  pages = {7268--7278}
}

arXiv conference talk code demo

---

PhD Thesis

On Learning the Structure of Clusters in Graphs

Peter Macgregor, University of Edinburgh, 2022

@phdthesis{macgregorLearningStructureClusters2022,
  title = {On Learning the Structure of Clusters in Graphs},
  author = {Macgregor, Peter},
  year = {2022},
  school = {University of Edinburgh}
}

arXiv University version

---