**Published:** 12.05.2020

**Paper Author:** Ryoma Sato

**Paper:** arXiv

# 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.