Peter Macgregor

activity

20212025

most citedA Tighter Analysis of Spectral Clustering, and Beyond

2 citations · 5 across the 12 of their papers we have counts for

collaborators

13 papers

cs.DS2025

Dynamic Similarity Graph Construction with Kernel Density Estimation

Steinar Laenen, Peter Macgregor, He Sun

In the kernel density estimation (KDE) problem, we are given a set $X$ of data points in $R^{d}$ , a kernel function $k: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{…

cs.LG2025

Dynamic DBSCAN with Euler Tour Sequences

Seiyun Shin, Ilan Shomorony, Peter Macgregor

We propose a fast and dynamic algorithm for Density-Based Spatial Clustering of Applications with Noise (DBSCAN) that efficiently supports online updates. Traditional DBSCAN algori…

cs.LG2025

Coreset Spectral Clustering

Ben Jourdan, Gregory Schwartzman, Peter Macgregor +1

Coresets have become an invaluable tool for solving $k$ -means and kernel $k$ -means clustering problems on large datasets with small numbers of clusters. On the other hand, spectral…

cs.DS2024

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

Peter Macgregor, He Sun

Spectral Toolkit of Algorithms for Graphs (STAG) is an open-source library for efficient graph algorithms. This technical report presents the newly implemented component on localit…

cs.DS2024

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

Ben Jourdan, Peter Macgregor, He Sun

Given $v_{1}, \dots, v_{m} \in C^{d}$ with $∥ v_{i} ∥^{2} = α$ for all $i \in [m]$ as input and suppose $\sum_{i = 1}^{m} ∣ ⟨ u, v_{i} ⟩ ∣^{2} = 1$ for every unit vector $u\in\mathbb…

cs.DS2023

Fast Approximation of Similarity Graphs with Kernel Density Estimation

Peter Macgregor, He Sun

Constructing a similarity graph from a set $X$ of data points in $R^{d}$ is the first step of many modern clustering algorithms. However, typical constructions of a similari…

cs.DS2023★ 1 cited

Fast and Simple Spectral Clustering in Theory and Practice

Peter Macgregor

Spectral clustering is a popular and effective algorithm designed to find $k$ clusters in a graph $G$ . In the classical spectral clustering algorithm, the vertices of $G$ are embed…

cs.SI2023

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

Peter Macgregor, He Sun

Spectral Toolkit of Algorithms for Graphs (STAG) is an open-source library for efficient spectral graph algorithms, and its development starts in September 2022. We have so far fin…

cs.DS2022★ 1 cited

On Learning the Structure of Clusters in Graphs

Peter Macgregor

Graph clustering is a fundamental problem in unsupervised learning, with numerous applications in computer science and in analysing real-world data. In many real-world applications…

cs.DS2022★ 2 cited

A Tighter Analysis of Spectral Clustering, and Beyond

Peter Macgregor, He Sun

This work studies the classical spectral clustering algorithm which embeds the vertices of some graph $G = (V_{G}, E_{G})$ into $R^{k}$ using $k$ eigenvectors of some matrix of $G…

cs.DS2022

Finding Bipartite Components in Hypergraphs

Peter Macgregor, He Sun

Hypergraphs are important objects to model ternary or higher-order relations of objects, and have a number of applications in analysing many complex datasets occurring in practice.…

cs.CC2022

Is the Algorithmic Kadison-Singer Problem Hard?

Ben Jourdan, Peter Macgregor, He Sun

We study the following $KS_{2} (c)$ problem: let $c \in R^{+}$ be some constant, and $v_{1}, \dots, v_{m} \in R^{d}$ be vectors such that $∥ v_{i} ∥^{2} \leq α$ for any $i\…

cs.DS2021★ 1 cited

Local Algorithms for Finding Densely Connected Clusters

Peter Macgregor, He Sun

Local graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective…