Subgraph Neural Networks
  Deep learning methods for graphs achieve remarkable performance on many
node-level and graph-level prediction tasks. However, despite the proliferation
of the methods and their success, prevailing Graph Neural Networks (GNNs)
neglect subgraphs, rendering subgraph prediction tasks challenging to tackle in
many impactful applications. Further, subgraph prediction tasks present several
unique challenges: subgraphs can have non-trivial internal topology, but also
carry a notion of position and external connectivity information relative to
the underlying graph in which they exist. Here, we introduce SubGNN, a subgraph
neural network to learn disentangled subgraph representations. We propose a
novel subgraph routing mechanism that propagates neural messages between the
subgraph's components and randomly sampled anchor patches from the underlying
graph, yielding highly accurate subgraph representations. SubGNN specifies
three channels, each designed to capture a distinct aspect of subgraph
topology, and we provide empirical evidence that the channels encode their
intended properties. We design a series of new synthetic and real-world
subgraph datasets. Empirical results for subgraph classification on eight
datasets show that SubGNN achieves considerable performance gains,
outperforming strong baseline methods, including node-level and graph-level
GNNs, by 19.8% over the strongest baseline. SubGNN performs exceptionally well
on challenging biomedical datasets where subgraphs have complex topology and
even comprise multiple disconnected components.
