Graph Rewriting for Graph Neural Networks
Adam Machowczyk Reiko Heckel
Given graphs as input, Graph Neural Networks (GNNs) support the inference of
nodes, edges, attributes, or graph properties. Graph Rewriting investigates the
rule-based manipulation of graphs to model complex graph transformations. We
propose that, therefore, (i) graph rewriting subsumes GNNs and could serve as
formal model to study and compare them, and (ii) the representation of GNNs as
graph rewrite systems can help to design and analyse GNNs, their architectures
and algorithms. Hence we propose Graph Rewriting Neural Networks (GReNN) as
both novel semantic foundation and engineering discipline for GNNs. We develop
a case study reminiscent of a Message Passing Neural Network realised as a
Groove graph rewriting model and explore its incremental operation in response
to dynamic updates.