# Scalable Graph Coreset Selection via Greedy Sampling

arXiv: https://arxiv.org/abs/2607.27602 · HTML: https://mlsanity.com/paper/2607.27602/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 30 Jul 2026.

## Builds on (most cited first, 17 of 17)

- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [GRAM: Graph-based Attention Model for Healthcare Representation Learning](https://mlsanity.com/paper/1611.07012/) (2016)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent](https://mlsanity.com/paper/1802.01737/) (2018)
- [Network Cross-Validation for Determining the Number of Communities in Network Data](https://mlsanity.com/paper/1411.1715/) (2014)
- [Sampling of graph signals with successive local aggregations](https://mlsanity.com/paper/1504.04687/) (2015)
- [Random sampling of bandlimited signals on graphs](https://mlsanity.com/paper/1511.05118/) (2015)
- [Little Ball of Fur: A Python Library for Graph Sampling](https://mlsanity.com/paper/2006.04311/) (2020)
- [Eigendecomposition-Free Sampling Set Selection for Graph Signals](https://mlsanity.com/paper/1809.01827/) (2018)
- [A Compressed Sensing Based Least Squares Approach to Semi-supervised Local Cluster Extraction](https://mlsanity.com/paper/2202.02904/) (2022)
- [Compressive Sensing for cut improvement and local clustering](https://mlsanity.com/paper/1808.05780/) (2018)
- [Graph-based Semi-supervised Local Clustering with Few Labeled Nodes](https://mlsanity.com/paper/2211.11114/) (2022)
- [Spectral Greedy Coresets for Graph Neural Networks](https://mlsanity.com/paper/2405.17404/) (2024)
- [Global and Local Uncertainty Principles for Signals on Graphs](https://mlsanity.com/paper/1603.03030/) (2016)
- [A low discrepancy sequence on graphs](https://mlsanity.com/paper/2010.04227/) (2020)
- [Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods](https://mlsanity.com/paper/2504.19419/) (2025)

## Abstract (arXiv)

Sampling representative nodes from large graphs is fundamental to graph signal processing and network analysis, yet existing methods require access to the full graph Laplacian, making them impractical at scale. We propose a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule. At each iteration, the algorithm accesses only a small random subset of Laplacian columns, requiring no eigendecomposition or global graph traversal, making it well-suited for large-scale graphs where the full Laplacian cannot be stored in memory. We analyze the algorithm under the stochastic block model and show that, when the degree distribution is balanced across nodes, the algorithm achieves sampling proportional to cluster size, and that the resulting mean estimate is controlled for band-limited graph signals in the Paley-Wiener space, with the error decaying as inter-cluster connectivity weakens. Numerical experiments on both synthetic and real-world data validate the effectiveness of the proposed method.