# A Poincar'e Inequality and Consistency Results for Signal Sampling on Large Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 47 references that are in the map.
- First posted on arXiv 17 Nov 2023.

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

- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Modeling polypharmacy side effects with graph convolutional networks](https://mlsanity.com/paper/1802.00543/) (2018)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Discrete Signal Processing on Graphs: Frequency Analysis](https://mlsanity.com/paper/1307.0468/) (2013)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [A Statistical Perspective on Algorithmic Leveraging](https://mlsanity.com/paper/1306.5362/) (2013)
- [Graphon Signal Processing](https://mlsanity.com/paper/2003.05030/) (2020)
- [Discrete Signal Processing on Graphs: Sampling Theory](https://mlsanity.com/paper/1503.05432/) (2015)
- [Learning by Transference: Training Graph Neural Networks on Growing Graphs](https://mlsanity.com/paper/2106.03693/) (2021)
- [Sampling of graph signals with successive local aggregations](https://mlsanity.com/paper/1504.04687/) (2015)
- [Limits, approximation and size transferability for GNNs on sparse graphs via graphops](https://mlsanity.com/paper/2306.04495/) (2023)
- [Private Graphon Estimation for Sparse Graphs](https://mlsanity.com/paper/1506.06162/) (2015)
- [Graph Neural Tangent Kernel: Convergence on Large Graphs](https://mlsanity.com/paper/2301.10808/) (2023)
- [The geometry of kernelized spectral clustering](https://mlsanity.com/paper/1404.7552/) (2014)
- [MalNet: A Large-Scale Image Database of Malicious Software](https://mlsanity.com/paper/2102.01072/) (2021)
- [Graphons, mergeons, and so on!](https://mlsanity.com/paper/1607.01718/) (2016)
- [The Graphon Fourier Transform](https://mlsanity.com/paper/1910.10195/) (2019)
- [Greedy Sampling of Graph Signals](https://mlsanity.com/paper/1704.01223/) (2017)
- [Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks](https://mlsanity.com/paper/1706.01143/) (2017)
- [Computing Heat Kernel Pagerank and a Local Clustering Algorithm](https://mlsanity.com/paper/1503.03155/) (2015)
- [Polynomial Time Algorithms for Dual Volume Sampling](https://mlsanity.com/paper/1703.02674/) (2017)

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

- [A Generative Model for Controllable Feature Heterophily in Graphs](https://mlsanity.com/paper/2509.23230/) (2025)

## Abstract (arXiv)

Large-scale graph machine learning is challenging as the complexity of learning models scales with the graph size. Subsampling the graph is a viable alternative, but sampling on graphs is nontrivial as graphs are non-Euclidean. Existing graph sampling techniques require not only computing the spectra of large matrices but also repeating these computations when the graph changes, e.g., grows. In this paper, we introduce a signal sampling theory for a type of graph limit -- the graphon. We prove a Poincar'e inequality for graphon signals and show that complements of node subsets satisfying this inequality are unique sampling sets for Paley-Wiener spaces of graphon signals. Exploiting connections with spectral clustering and Gaussian elimination, we prove that such sampling sets are consistent in the sense that unique sampling sets on a convergent graph sequence converge to unique sampling sets on the graphon. We then propose a related graphon signal sampling algorithm for large graphs, and demonstrate its good empirical performance on graph machine learning tasks.