Scalable Graph Coreset Selection via Greedy Sampling

Zhaiming Shen, Alex Cloninger
Proceedings of the 2nd Conference on Topology, Algebra, and Geometry in Data Science(TAG-DS 2026), PMLR 334(2):246-261, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v334-shen26a, title = {Scalable Graph Coreset Selection via Greedy Sampling}, author = {Shen, Zhaiming and Cloninger, Alex}, booktitle = {Proceedings of the 2nd Conference on Topology, Algebra, and Geometry in Data Science(TAG-DS 2026)}, pages = {246--261}, year = {2026}, editor = {Berman, Eddie and Bernárdez, Guillermo and Chen, Samantha and Cloninger, Alex and Doster, Timothy and Emerson, Tegan and Grigsby, J. Elisenda and Kvinge, Henry and Lawrence, Hannah and Marrinan, Tim and Myers, Audun and Papillon, Mathilde and Tahmasebi, Behrooz and Telyatnikov, Lev and Walters, Robin and Weber, Melanie and Xie, YuQing and Yeats, Eric}, volume = {334}, number = {2}, series = {Proceedings of Machine Learning Research}, month = {18--20 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v334/main/assets/shen26a/shen26a.pdf}, url = {https://proceedings.mlr.press/v334/shen26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Scalable Graph Coreset Selection via Greedy Sampling %A Zhaiming Shen %A Alex Cloninger %B Proceedings of the 2nd Conference on Topology, Algebra, and Geometry in Data Science(TAG-DS 2026) %C Proceedings of Machine Learning Research %D 2026 %E Eddie Berman %E Guillermo Bernárdez %E Samantha Chen %E Alex Cloninger %E Timothy Doster %E Tegan Emerson %E J. Elisenda Grigsby %E Henry Kvinge %E Hannah Lawrence %E Tim Marrinan %E Audun Myers %E Mathilde Papillon %E Behrooz Tahmasebi %E Lev Telyatnikov %E Robin Walters %E Melanie Weber %E YuQing Xie %E Eric Yeats %F pmlr-v334-shen26a %I PMLR %P 246--261 %U https://proceedings.mlr.press/v334/shen26a.html %V 334 %N 2 %X 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.
APA
Shen, Z. & Cloninger, A.. (2026). Scalable Graph Coreset Selection via Greedy Sampling. Proceedings of the 2nd Conference on Topology, Algebra, and Geometry in Data Science(TAG-DS 2026), in Proceedings of Machine Learning Research 334(2):246-261 Available from https://proceedings.mlr.press/v334/shen26a.html.

Related Material