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.