# Subsampling Graphs with GNN Performance Guarantees

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 45 references that are in the map.
- First posted on arXiv 23 Feb 2025.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Condensing Graphs via One-Step Gradient Matching](https://mlsanity.com/paper/2206.07746/) (2022)
- [Graph Representation Learning in Biomedicine](https://mlsanity.com/paper/2104.04883/) (2021)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [A Survey of Graph Neural Networks for Social Recommender Systems](https://mlsanity.com/paper/2212.04481/) (2022)
- [GraKeL: A Graph Kernel Library in Python](https://mlsanity.com/paper/1806.02193/) (2018)
- [Federated Graph Neural Networks: Overview, Techniques and Challenges](https://mlsanity.com/paper/2202.07256/) (2022)
- [Reducing Communication in Graph Neural Network Training](https://mlsanity.com/paper/2005.03300/) (2020)
- [On Valid Optimal Assignment Kernels and Applications to Graph Classification](https://mlsanity.com/paper/1606.01141/) (2016)
- [Towards Sustainable Learning: Coresets for Data-efficient Deep Learning](https://mlsanity.com/paper/2306.01244/) (2023)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [PyTorch Geometric Signed Directed: A Software Package on Graph Neural Networks for Signed and Directed Graphs](https://mlsanity.com/paper/2202.10793/) (2022)
- [Mirage: Model-Agnostic Graph Distillation for Graph Classification](https://mlsanity.com/paper/2310.09486/) (2023)
- [A Degeneracy Framework for Scalable Graph Autoencoders](https://mlsanity.com/paper/1902.08813/) (2019)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [GC-Bench: An Open and Unified Benchmark for Graph Condensation](https://mlsanity.com/paper/2407.00615/) (2024)
- [GNN at the Edge: Cost-Efficient Graph Neural Network Processing over Distributed Edge Servers](https://mlsanity.com/paper/2210.17281/) (2022)
- [Spectral Greedy Coresets for Graph Neural Networks](https://mlsanity.com/paper/2405.17404/) (2024)
- [A Local Graph Limits Perspective on Sampling-Based GNNs](https://mlsanity.com/paper/2310.10953/) (2023)

## Built on by (most cited first, 4 of 4)

- [Graph neural networks extrapolate out-of-distribution for shortest paths](https://mlsanity.com/paper/2503.19173/) (2025)
- [Graph Data Selection for Domain Adaptation: A Model-Free Approach](https://mlsanity.com/paper/2505.17293/) (2025)
- [GRACE: Graph Neural Networks for Locus-of-Care Prediction under Extreme Class Imbalance](https://mlsanity.com/paper/2510.20671/) (2025)
- [Dual-Primal Graph VAEs for Noisy Label Aggregation](https://mlsanity.com/paper/2608.11473/) (2026)

## Abstract (arXiv)

How can we subsample graph data so that a graph neural network (GNN) trained on the subsample achieves performance comparable to training on the full dataset? This question is of fundamental interest, as smaller datasets reduce labeling costs, storage requirements, and computational resources needed for training. Selecting an effective subset is challenging: a poorly chosen subsample can severely degrade model performance, and empirically testing multiple subsets for quality obviates the benefits of subsampling. Therefore, it is critical that subsampling comes with guarantees on model performance. In this work, we introduce new subsampling methods for graph datasets that leverage the Tree Mover's Distance to reduce both the number of graphs and the size of individual graphs. To our knowledge, our approach is the first that is supported by rigorous theoretical guarantees: we prove that training a GNN on the subsampled data results in a bounded increase in loss compared to training on the full dataset. Unlike existing methods, our approach is both model-agnostic, requiring minimal assumptions about the GNN architecture, and label-agnostic, eliminating the need to label the full training set. This enables subsampling early in the model development pipeline (before data annotation, model selection, and hyperparameter tuning) reducing costs and resources needed for storage, labeling, and training. We validate our theoretical results with experiments showing that our approach outperforms existing subsampling methods across multiple datasets.