Technical report: Graph Neural Networks go Grammatical

03/02/2023
by   Jason Piquenot, et al.
0

This paper proposes a new GNN design strategy. This strategy relies on Context-Free Grammars (CFG) generating the matrix language MATLANG. It enables us to ensure both WL-expressive power, substructure counting abilities and spectral properties. Applying our strategy, we design Grammatical Graph Neural Network G^2N^2, a provably 3-WL GNN able to count at edge-level cycles of length up to 6 and able to reach band-pass filters. A large number of experiments covering these properties corroborate the presented theoretical results.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset