Towards Graph-to-Graph Transformation Networks
Date:
Graph Neural Networks (GNNs) operate primarily by performing matrix operations, such as multiplication, Hadamard product, transposition and inversion, on graph adjacency matrices. Due to their essential use in machine learning, they are efficiently implemented even for large matrices. Instead, the complexity of finding a match of the LHS in the host graph, as required in rule-based graph rewriting, is worst-case exponential. GNNs perform a simple form of parallel graph rewriting where a single rule with a central node is applied to all nodes of the graph to aggregate data from all its neighbors. However, this model can only compute on node or edge attributes, not change the graph itself, and pattern matching is usually restricted to this node and its outgoing edges. We are interested in a GNN architecture that can efficiently implement general transformations from input to output graphs.