Scalable Graph Coreset Selection via Greedy Sampling

DOI10.48550/arXiv.2607.27602MaRDI QIDQ7284488arXivFDO

Authors Zhaiming Shen, Alexander Cloninger

Publication date 30 July 2026

Published in arXiv

Tldr We present a scalable greedy sampling algorithm for selecting representative nodes from large graphs based on minimum inner product selection rule, which accesses only a small random subset of Laplacian columns at each iteration, making it memory-efficient and fast. We analyze its performance under stochastic block model and show that the sampled set is proportional to cluster size with controlled mean estimate error in Paley-Wiener space for band-limited graph signals.

Full work available at URL https://doi.org/10.48550/arXiv.2607.27602

arXiv classification

math.NAstat.ML

Cites work

• A compressed sensing based least squares approach to semi-supervised local cluster extraction
• A low discrepancy sequence on graphs
• Compressive Sensing for cut improvement and local clustering
• Eigendecomposition-Free Sampling Set Selection for Graph Signals
• Global and Local Uncertainty Principles for Signals on Graphs
• Graph Signal Processing: Overview, Challenges, and Applications
• Network cross-validation for determining the number of communities in network data
• Random graph models of social networks
• Random sampling of bandlimited signals on graphs
• Sampling of Graph Signals With Successive Local Aggregations
• Semi-supervised Local Cluster Extraction by Compressive Sensing

This page was built for publication: Scalable Graph Coreset Selection via Greedy Sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7284488)