Scalable Graph Coreset Selection via Greedy Sampling

What the math gives to ML

The paper's transferable asset is a scalable, column-local graph sampling rule: it uses randomly accessed Laplacian columns and a minimum-inner-product criterion instead of storing or diagonalizing the full Laplacian. This naturally becomes a graph-minibatch or graph-token coreset for GNN training, where selected nodes should retain cluster coverage and low-frequency graph signals. The graph Fourier formulation also suggests evaluating whether the selected batch preserves smooth node features and labels, rather than optimizing only uniform coverage. The most practical first transfer is a drop-in sampler for neighbor-sampled GNNs, with importance weighting to prevent biased gradients.