Technical report: Graph Neural Networks go Grammatical
This work addresses a formalization challenge in GNN design for researchers, though it appears incremental by building on existing 3-WL methods.
The paper tackles the problem of connecting algebraic languages to Graph Neural Networks (GNNs) by introducing a framework that uses Context-Free Grammars (CFG) and grammar reduction to derive a GNN model, G^2N^2, which is provably 3-WL compliant and demonstrates superior efficiency in experiments.
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 G$^2$N$^2$, which is provably 3-WL compliant. Through various experiments, we demonstrate the superior efficiency of G$^2$N$^2$ compared to other 3-WL GNNs across numerous downstream tasks. Specifically, one experiment highlights the benefits of grammar reduction within our framework.