Article,
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
(2020)cite arxiv:2006.09252.
Abstract
While Graph Neural Networks (GNNs) have achieved remarkable results in a
variety of applications, recent studies exposed important shortcomings in their
ability to capture the structure of the underlying graph. It has been shown
that the expressive power of standard GNNs is bounded by the Weisfeiler-Lehman
(WL) graph isomorphism test, from which they inherit proven limitations such as
the inability to detect and count graph substructures. On the other hand, there
is significant empirical evidence, e.g. in network science and bioinformatics,
that substructures are often informative for downstream tasks, suggesting that
it is desirable to design GNNs capable of leveraging this important source of
information. To this end, we propose a novel topologically-aware message
passing scheme based on subgraph isomorphism counting. We show that our
architecture allows incorporating domain-specific inductive biases and that it
is strictly more expressive than the WL test. Importantly, in contrast to
recent works on the expressivity of GNNs, we do not attempt to adhere to the WL
hierarchy; this allows us to retain multiple attractive properties of standard
GNNs such as locality and linear complexity, while being able to disambiguate
even hard instances of graph isomorphism. We extensively evaluate our method on
graph classification and regression tasks and show state-of-the-art results on
multiple datasets including molecular graphs and social networks.
