Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

  • 2018-10-04 14:31:57
  • Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe
  • 15

Abstract

In recent years, graph neural networks (GNNs) have emerged as a powerfulneural architecture to learn vector representations of nodes and graphs in asupervised, end-to-end fashion. Up to now, GNNs have only been evaluatedempirically---showing promising results. The following work investigates GNNsfrom a theoretical point of view and relates them to the $1$-dimensionalWeisfeiler-Leman graph isomorphism heuristic ($1$-WL). We show that GNNs havethe same expressiveness as the $1$-WL in terms of distinguishing non-isomorphic(sub-)graphs. Hence, both algorithms also have the same shortcomings. Based onthis, we propose a generalization of GNNs, so-called $k$-dimensional GNNs($k$-GNNs), which can take higher-order graph structures at multiple scalesinto account. These higher-order structures play an essential role in thecharacterization of social networks and molecule graphs. Our experimentalevaluation confirms our theoretical findings as well as confirms thathigher-order information is useful in the task of graph classification andregression.

 

Introduction (beta)

None

 

Conclusion (beta)

None