mlsanityData to 14 Oct 2026

Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters

arXiv 2111.03317 ↗First posted 5 Nov 2021cs.LG stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

Theoretical analyses for graph learning methods often assume a complete observation of the input graph. Such an assumption might not be useful for handling any-size graphs due to the scalability issues in practice. In this work, we develop a theoretical framework for graph classification problems in the partial observation setting (i.e., subgraph samplings). Equipped with insights from graph limit theory, we propose a new graph classification model that works on a randomly sampled subgraph and a novel topology to characterize the representability of the model. Our theoretical framework contributes a theoretical validation of mini-batch learning on graphs and leads to new learning-theoretic results on generalization bounds as well as size-generalizability without assumptions on the input.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 45 of its 81 references that are in the map. First posted on arXiv 5 Nov 2021.

Builds on

45 of 81 references.

References · 45

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  7. 2018Dynamic Graph CNN for Learning on Point Cloudscited by 2,223
  8. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  9. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  10. 2014DeepWalk: Online Learning of Social Representationscited by 1,547
  11. 2017Deep Setscited by 1,421
  12. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
33 more
  1. 2018Deep Graph Infomaxcited by 1,106
  2. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  3. 2020Learning Mesh-Based Simulation with Graph Networkscited by 868
  4. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  5. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  6. 2020Directional Message Passing for Molecular Graphscited by 561
  7. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 509
  8. 2019Provably Powerful Graph Networkscited by 389
  9. 2018Invariant and Equivariant Graph Networkscited by 346
  10. 2018Neural Relational Inference for Interacting Systemscited by 339
  11. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 261
  12. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 222
  13. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  14. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 183
  15. 2017SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernelscited by 161
  16. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 161
  17. 2020DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphscited by 139
  18. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 124
  19. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  20. 2018Rethinking Knowledge Graph Propagation for Zero-Shot Learningcited by 87
  21. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 85
  22. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  23. 2020Computing Graph Neural Networks: A Survey from Algorithms to Acceleratorscited by 81
  24. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 76
  25. 2019SampleNet: Differentiable Point Cloud Samplingcited by 74
  26. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 69
  27. 2020Graph Homomorphism Convolutioncited by 27
  28. 2019A Simple Proof of the Universality of Invariant/Equivariant Graph Neural Networkscited by 19
  29. 2021Generalization bounds for graph convolutional neural networks via Rademacher complexitycited by 17
  30. 2018Mean-field theory of graph neural networks in graph partitioningcited by 16
  31. 2019Constant Time Graph Neural Networkscited by 4
  32. 2019Testable Properties in General Graphs and Random Order Streamingcited by 2
  33. 2018Estimating the Number of Connected Components in a Graph via Subgraph Samplingcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Dimension-Free Scaling Laws for Size Generalization: An Exponential Separationcited by 0