Research map / Graph learning / GNN architectures
Position: Future Directions in the Theory of Graph Machine Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
A position paper arguing that graph machine learning theory should move beyond combinatorial expressivity toward a balanced treatment of expressivity, generalization, optimization, and practical alignment, and lists concrete challenges.
Problem
Current theory of graph neural networks is dominated by coarse-grained, binary expressivity results (e.g., 1-WL equivalence), with few analyses of generalization and SGD optimization that match practice.
Approach
Argues for a holistic research agenda: fine-grained (metric/geometric) expressivity, uniform and architecture-aware expressivity, generalization that reflects overparameterization and graph structure, and optimization dynamics of SGD, all tied to practical benchmarks and domain needs.
Surprising findings
- Random-weight GNNs can perform on par with trained GNNs on some tasks, suggesting SGD optimization sometimes yields little improvement over initialization.
- More expressive GNN architectures often generalize better, contrary to classical bias-variance expectations.
Limitations
- Position paper with no new experiments or theorems; claims are not empirically validated here.
- Challenges are proposals rather than solved problems.
Experimental setup
Builds on: 1-WL test k-WL message-passing neural networks
Closest papers by meaning
- Almost Surely Asymptotically Constant Graph Neural Networks (NeurIPS 2024 · similarity 0.91)
- Covered Forest: Fine-grained generalization analysis of graph neural networks (ICML 2025 · similarity 0.91)
- On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks (ICML 2025 · similarity 0.91)
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.90)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.90)
- On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.