Foundations and Frontiers of Graph Learning Theory
Not on the map. Why?
Abstract (arXiv)
Recent advancements in graph learning have revolutionized the way to understand and analyze data with complex structures. Notably, Graph Neural Networks (GNNs), i.e. neural network architectures designed for learning graph representations, have become a popular paradigm. With these models being usually characterized by intuition-driven design or highly intricate components, placing them within the theoretical analysis framework to distill the core concepts, helps understand the key principles that drive the functionality better and guide further development. Given this surge in interest, this article provides a comprehensive summary of the theoretical foundations and breakthroughs concerning the approximation and learning behaviors intrinsic to prevalent graph learning models. Encompassing discussions on fundamental aspects such as expressiveness power, generalization, optimization, and unique phenomena such as over-smoothing and over-squashing, this piece delves into the theoretical foundations and frontier driving the evolution of graph learning. In addition, this article also presents several challenges and further initiates discussions on possible solutions.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 200 of its 269 references that are in the map. First posted on arXiv 3 Jul 2024.
Builds on
200 of 269 references.
References · 200
- 2015Deep Residual Learning for Image Recognitioncited by 51,809
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2017Graph Attention Networkscited by 8,854
- 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
- 2017Inductive Representation Learning on Large Graphscited by 6,284
- 2016Layer Normalizationcited by 5,579
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
- 2017Neural Message Passing for Quantum Chemistrycited by 3,460
- 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
- 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
38 more
- 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
- 2014DeepWalk: Online Learning of Social Representationscited by 1,543
- 2016Instance Normalization: The Missing Ingredient for Fast Stylizationcited by 1,187
- 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
- 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
- 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
- 2021E(n) Equivariant Graph Neural Networkscited by 951
- 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
- 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
- 2020Simple and Deep Graph Convolutional Networkscited by 857
- 2018Link Prediction Based on Graph Neural Networkscited by 829
- 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
- 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
- 2020Benchmarking Graph Neural Networkscited by 672
- 2020A Generalization of Transformer Networks to Graphscited by 653
- 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
- 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
- 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
- 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
- 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
- 2020Directional Message Passing for Molecular Graphscited by 556
- 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
- 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
- 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
- 2019Provably Powerful Graph Networkscited by 385
- 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 361
- 2018Invariant and Equivariant Graph Networkscited by 339
- 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
- 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
- 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
- 2020Towards Deeper Graph Neural Networkscited by 296
- 2021Mesh Graphormercited by 264
- 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 260
- 2021GRAND: Graph Neural Diffusioncited by 258
- 2023A Survey on Oversmoothing in Graph Neural Networkscited by 246
- 2020A Note on Over-Smoothing for Graph Neural Networkscited by 245
- 2020Can Graph Neural Networks Count Substructures?cited by 235
- 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
50 most cited of 200 All 200 (JSON)
Built on by
Citing papers per year: 2025: 3.
3 papers.