TLDR

This is a review paper on theoretical guarantees of Graph Neural Networks (GNNs).
Message passing GNNs are linked to the Weisfeiler Lehman (WL) graph isomorphism test.
Several variants of vanilla GNNs are proposed with guarantees to increasingly powerful WL tests by considering larger subgstrutures and improving the injective properties of aggregation functions.

Problem

The goal of this work is to explore the theoretical limitations of graph neural networks (GNNs) and propose alternatives with more powerful theoretical guarantees. Typically, the power of a GNN, which we can think of a function which maps a graph to a point in a certain vector space, is measured by its ability to distinguish non-isomorphic graphs. More formally, given two graphs \(G\) and \(G'\), a GNN is a function \(f : G \rightarrow \mathbb{R}^d\), and we wish for \(f\) to be fully injective. This means that if \(f(G) \neq f(G') \implies G \neq G'\). A failure of \(f\) is when non-isomorphic graphs are mapped to the same representation. The most powerful GNN is therefore the one that can produce a different output for all non-isomorphic graphs. Most currently used GNNs, while they show good performance empirically, are not able to fully distinguish all classes of graphs which is a direct limitation on their capacity as learners on graphs.

Results

The 1-WL test is introduced, in which a hash of a graph is computed by propagating and hashing IDs (colors) between neighborhoods of each node. For a more detailed explanation see this blog post
The authors describe cases of non-isomorphic graphs for which the 1-WL test fails.
Higher-order \(WL\) tests, \(k-WL\) perform the message passing over all \(k\) subsets of nodes in the graph. This increases discrimination power but imposes an exponential cost.
Two GNN variants with strong drawbacks but theoretical discrimination equivalent to some higher-order WLs are presented.
Maron et al. propose a model which composes invariant transformations on the node features coupled with a fully connected neural network. However, this only works with fixed-size graphs.
Murphy et al. propose relational pooling which averages a GNN over all permutaitons of the nodes. Since this depends on the number of nodes, it can also only work on fixed-size graphs.