Local Permutation Equivariance For Graph Neural Networks
  In this work we develop a new method, named Sub-graph Permutation Equivariant
Networks (SPEN), which provides a framework for building graph neural networks
that operate on sub-graphs, while using permutation equivariant update
functions that are also equivariant to a novel choice of automorphism groups.
Message passing neural networks have been shown to be limited in their
expressive power and recent approaches to over come this either lack
scalability or require structural information to be encoded into the feature
space. The general framework presented here overcomes the scalability issues
associated with global permutation equivariance by operating on sub-graphs. In
addition, through operating on sub-graphs the expressive power of
higher-dimensional global permutation equivariant networks is improved; this is
due to fact that two non-distinguishable graphs often contain distinguishable
sub-graphs. Furthermore, the proposed framework only requires a choice of
$k$-hops for creating ego-network sub-graphs and a choice of representation
space to be used for each layer, which makes the method easily applicable
across a range of graph based domains. We experimentally validate the method on
a range of graph benchmark classification tasks, demonstrating either
state-of-the-art results or very competitive results on all benchmarks.
Further, we demonstrate that the use of local update functions offers a
significant improvement in GPU memory over global methods.
