mlsanityData to 14 Oct 2026

Technical report: Graph Neural Networks go Grammatical

arXiv 2303.01590 ↗First posted 2 Mar 2023cs.LG cs.CLcited by 0

Not on the map. Why?

Abstract (arXiv)

This paper introduces a framework for formally establishing a connection between a portion of an algebraic language and a Graph Neural Network (GNN). The framework leverages Context-Free Grammars (CFG) to organize algebraic operations into generative rules that can be translated into a GNN layer model. As CFGs derived directly from a language tend to contain redundancies in their rules and variables, we present a grammar reduction scheme. By applying this strategy, we define a CFG that conforms to the third-order Weisfeiler-Lehman (3-WL) test using MATLANG. From this 3-WL CFG, we derive a GNN model, named G2N2, which is provably 3-WL compliant. Through various experiments, we demonstrate the superior efficiency of G2N2 compared to other 3-WL GNNs across numerous downstream tasks. Specifically, one experiment highlights the benefits of grammar reduction within our framework.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 26 of its 36 references that are in the map. First posted on arXiv 2 Mar 2023.

Builds on

26 of 36 references.

References · 26

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  6. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  7. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,051
  8. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  9. 2019Provably Powerful Graph Networkscited by 389
  10. 2018Invariant and Equivariant Graph Networkscited by 346
  11. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  12. 2020Can Graph Neural Networks Count Substructures?cited by 236
14 more
  1. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  2. 2021Identity-aware Graph Neural Networkscited by 198
  3. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 161
  4. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  5. 2021Nested Graph Neural Networkscited by 137
  6. 2020GraphNorm: A Principled Approach to Accelerating Graph Neural Network Trainingcited by 117
  7. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  8. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  9. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 64
  10. 2020Wasserstein Embedding for Graph Learningcited by 56
  11. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 56
  12. 2017On the Combinatorial Power of the Weisfeiler-Lehman Algorithmcited by 18
  13. 2017On the expressive power of query languages for matricescited by 14
  14. 2018On the expressive power of linear algebra on graphscited by 14

Built on by

Not cited yet.