TY - JOUR AU - Morris, Christopher AU - Ritzert, Martin AU - Fey, Matthias AU - Hamilton, William L. AU - Lenssen, Jan Eric AU - Rattan, Gaurav AU - Grohe, Martin PY - 2019/07/17 Y2 - 2024/03/29 TI - Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: Machine Learning DO - 10.1609/aaai.v33i01.33014602 UR - https://ojs.aaai.org/index.php/AAAI/article/view/4384 SP - 4602-4609 AB - <p>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 <em>k</em>-dimensional GNNs (<em>k</em>-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.</p> ER -