Natural Graph Networks
This work addresses a foundational issue in graph representation learning for researchers and practitioners, offering a novel theoretical framework with practical applications.
The paper tackled the problem of making graph neural networks independent of graph description by proposing naturality as a sufficient condition instead of equivariance, resulting in a more flexible class of networks that perform well on benchmarks.
A key requirement for graph neural networks is that they must process a graph in a way that does not depend on how the graph is described. Traditionally this has been taken to mean that a graph network must be equivariant to node permutations. Here we show that instead of equivariance, the more general concept of naturality is sufficient for a graph network to be well-defined, opening up a larger class of graph networks. We define global and local natural graph networks, the latter of which are as scalable as conventional message passing graph neural networks while being more flexible. We give one practical instantiation of a natural network on graphs which uses an equivariant message network parameterization, yielding good performance on several benchmarks.