Provably Powerful Graph Networks

Recently, the Weisfeiler-Lehman (WL) graph isomorphism test was used to measure the expressive power of graph neural networks (GNN). It was shown that the popular message passing GNN cannot distinguish between graphs that are indistinguishable by the 1 -WL test \citep{morris2019,xu2019}. Unfortunately, many simple instances of graphs are indistinguishable by the 1 -WL test. In search for more expressive graph learning models we build upon the recent k -order invariant and equivariant graph neural networks \citep{maron2019} and present two results: First, we show that such k -order networks can distinguish between non-isomorphic graphs as good as the k -WL tests, which are provably stronger than the 1 -WL test for k 2 . This makes these models strictly stronger than message passing models. Unfortunately, the higher expressiveness of these models comes with a computational cost of processing high order tensors.