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

Authors

  • Christopher Morris TU Dortmund University
  • Martin Ritzert RWTH Aachen University
  • Matthias Fey TU Dortmund University
  • William L. Hamilton Stanford University
  • Jan Eric Lenssen TU Dortmund University
  • Gaurav Rattan RWTH Aachen University
  • Martin Grohe RWTH Aachen University

DOI:

https://doi.org/10.1609/aaai.v33i01.33014602

Abstract

In recent years, graph neural networks (GNNs) have emerged as a powerful neural architecture to learn vector representations of nodes and graphs in a supervised, end-to-end fashion. Up to now, GNNs have only been evaluated empirically—showing promising results. The following work investigates GNNs from a theoretical point of view and relates them to the 1-dimensional Weisfeiler-Leman graph isomorphism heuristic (1-WL). We show that GNNs have the same expressiveness as the 1-WL in terms of distinguishing non-isomorphic (sub-)graphs. Hence, both algorithms also have the same shortcomings. Based on this, we propose a generalization of GNNs, so-called k-dimensional GNNs (k-GNNs), which can take higher-order graph structures at multiple scales into account. These higher-order structures play an essential role in the characterization of social networks and molecule graphs. Our experimental evaluation confirms our theoretical findings as well as confirms that higher-order information is useful in the task of graph classification and regression.

Downloads

Published

2019-07-17

How to Cite

Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., & Grohe, M. (2019). Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 4602-4609. https://doi.org/10.1609/aaai.v33i01.33014602

Issue

Section

AAAI Technical Track: Machine Learning