mlsanityData to 14 Oct 2026

Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks

arXiv 2302.02922 ↗First posted 6 Feb 2023cs.LG cs.AI eess.SPcited by 16

Not on the map. Why?

Abstract (arXiv)

Due to the significant computational challenge of training large-scale graph neural networks (GNNs), various sparse learning techniques have been exploited to reduce memory and storage costs. Examples include textitgraph sparsification that samples a subgraph to reduce the amount of data aggregation and textitmodel sparsification that prunes the neural network to reduce the number of trainable weights. Despite the empirical successes in reducing the training cost while maintaining the test accuracy, the theoretical generalization analysis of sparse learning for GNNs remains elusive. To the best of our knowledge, this paper provides the first theoretical characterization of joint edge-model sparse learning from the perspective of sample complexity and convergence rate in achieving zero generalization error. It proves analytically that both sampling important nodes and pruning neurons with the lowest-magnitude can reduce the sample complexity and improve convergence without compromising the test accuracy. Although the analysis is centered on two-layer GNNs with structural constraints on data, the insights are applicable to more general setups and justified by both synthetic and practical citation datasets.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 58 of its 87 references that are in the map. First posted on arXiv 6 Feb 2023.

Builds on

58 of 87 references.

References · 58

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2015Distilling the Knowledge in a Neural Networkcited by 10,324
  3. 2017Graph Attention Networkscited by 8,923
  4. 2017Inductive Representation Learning on Large Graphscited by 6,320
  5. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  6. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  7. 2018The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networkscited by 2,262
  8. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  9. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,694
  10. 2014DeepWalk: Online Learning of Social Representationscited by 1,547
  11. 2019Simplifying Graph Convolutional Networkscited by 1,477
  12. 2016Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translationcited by 1,475
38 more
  1. 2018Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognitioncited by 1,209
  2. 2020LightGCN: Simplifying and Powering Graph Convolution Network for Recommendationcited by 1,139
  3. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  4. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  6. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  7. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  8. 2017Deep Neural Networks as Gaussian Processescited by 622
  9. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 584
  10. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  11. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  12. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  13. 2020Point-GNN: Graph Neural Network for 3D Object Detection in a Point Cloudcited by 335
  14. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  15. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  16. 2020Proving the Lottery Ticket Hypothesis: Pruning is All You Needcited by 201
  17. 2019Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networkscited by 177
  18. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  19. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 161
  20. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  21. 2020Distilling Knowledge from Graph Convolutional Networkscited by 129
  22. 2020Logical Neural Networkscited by 119
  23. 2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
  24. 2021A Unified Lottery Ticket Hypothesis for Graph Neural Networkscited by 118
  25. 2016An Analysis of Deep Neural Network Models for Practical Applicationscited by 116
  26. 2020Feature Purification: How Adversarial Training Performs Robust Deep Learningcited by 107
  27. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  28. 2020Degree-Quant: Quantization-Aware Training for Graph Neural Networkscited by 96
  29. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  30. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  31. 2020Learning Parities with Neural Networkscited by 78
  32. 2019Graph Few-shot Learning via Knowledge Transfercited by 63
  33. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  34. 2021E-GraphSAGE: A Graph Neural Network based Intrusion Detection System for IoTcited by 56
  35. 2021Topology-Imbalance Learning for Semi-Supervised Node Classificationcited by 56
  36. 2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
  37. 2022A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Featurescited by 49
  38. 2020Binary Graph Neural Networkscited by 34

50 most cited of 58 All 58 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 4; 2024: 9; 2025: 2; 2026: 1.

16 papers.

Sort:

By area:

  1. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  2. 2025When is Task Vector Provably Effective for Model Editing? A Generalization Analysis of Nonlinear Transformerscited by 38
  3. 2024How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?cited by 35
  4. 2024A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Expertscited by 21
  5. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  6. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  7. 2024Graph Neural Networks for Tabular Data Learning: A Survey with Taxonomy and Directionscited by 13
  8. 2023Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptronscited by 12
  9. 2024Node Identifiers: Compact, Discrete Representations for Efficient Graph Learningcited by 10
  10. 2024Learning on Transformers is Provable Low-Rank and Sparse: A One-layer Analysiscited by 8
  11. 2024SF-DQN: Provable Knowledge Transfer using Successor Feature for Deep Reinforcement Learningcited by 5
  12. 2024IGNN-Solver: A Graph Neural Solver for Implicit Graph Neural Networkscited by 3
4 more
  1. 2024Unifews: You Need Fewer Operations for Efficient Graph Neural Networkscited by 2
  2. 2026Efficient Quantization of Mixture-of-Experts with Theoretical Generalization Guaranteescited by 2
  3. 2023On the Equivalence of Graph Convolution and Mixupcited by 0
  4. 2025Theoretical Learning Performance of Graph Neural Networks: The Impact of Jumping Connections and Layer-wise Sparsificationcited by 0