# Neighborhood Sampling Does Not Learn the Same Graph Neural Network

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 30 references that are in the map.
- First posted on arXiv 26 Sep 2025.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Gaussian Process Behaviour in Wide Deep Neural Networks](https://mlsanity.com/paper/1804.11271/) (2018)
- [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1911.07323/) (2019)
- [Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes](https://mlsanity.com/paper/1810.05148/) (2018)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [Tensor Programs I: Wide Feedforward or Recurrent Neural Networks of Any Architecture are Gaussian Processes](https://mlsanity.com/paper/1910.12478/) (2019)
- [Neural Tangents: Fast and Easy Infinite Neural Networks in Python](https://mlsanity.com/paper/1912.02803/) (2019)
- [Deep Convolutional Networks as shallow Gaussian Processes](https://mlsanity.com/paper/1808.05587/) (2018)
- [Infinite attention: NNGP and NTK for deep attention networks](https://mlsanity.com/paper/2006.10540/) (2020)
- [Stochastic Gradient Descent with Biased but Consistent Gradient Estimators](https://mlsanity.com/paper/1807.11880/) (2018)
- [Graph Neural Tangent Kernel: Convergence on Large Graphs](https://mlsanity.com/paper/2301.10808/) (2023)
- [Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspective](https://mlsanity.com/paper/2103.03113/) (2021)
- [Graph Neural Network-Inspired Kernels for Gaussian Processes in Semi-Supervised Learning](https://mlsanity.com/paper/2302.05828/) (2023)
- [Prediction performance after learning in Gaussian process regression](https://mlsanity.com/paper/1606.03865/) (2016)

## Abstract (arXiv)

Neighborhood sampling is an important ingredient in the training of large-scale graph neural networks. It suppresses the exponential growth of the neighborhood size across network layers and maintains feasible memory consumption and time costs. While it becomes a standard implementation in practice, its systemic behaviors are less understood. We conduct a theoretical analysis by using the tool of neural tangent kernels, which characterize the (analogous) training dynamics of neural networks based on their infinitely wide counterparts -- Gaussian processes (GPs). We study several established neighborhood sampling approaches and the corresponding posterior GP. With limited samples, the posteriors are all different, although they converge to the same one as the sample size increases. Moreover, the posterior covariance, which lower-bounds the mean squared prediction error, is uncomparable, aligning with observations that no sampling approach dominates.