​​Weisfeiler and Leman Go Relational

by Pablo Barcelo (PUC Chile & IMFD & CENIA Chile), Mikhail Galkin (Mila), Christopher Morris (RWTH Aachen), Miguel Romero Orth (Universidad Adolfo Ibáñez & CENIA Chile)

arxiv

Multi-relational graphs have been surprisingly neglected by the GNN theory community for quite a while. In our fresh LOG 2022 paper, we bridge this gap and propose Relational WL (RWL), an extension of the classical Weisfeiler-Leman test for multi-relational graphs (such as molecular graphs or knowledge graphs).

We prove several important theorems:

1) 1-RWL is strictly more powerful than 1-WL;
2) R-GCN and CompGCN, common multi-relational GNNs, are bounded by 1-RWL;
3) R-GCN and CompGCN are in fact equally expressive

Even more interesting finding is that the most expressive message functions should capture vector scaling, eg, multiplication or circular correlation. This result gives a solid foundation for GINE with multiplicative message function (one of the most popular GNN encoders for molecular graphs) and CompGCN with DistMult.

Based on the theory for homogeneous higher-order GNNs, we show there exist higher-order relational networks, k-RNs, that are more expressive than 1-RWL. Similarly to local k-GNNs, there exist approximations that reduce their computational complexity.

---

Now we have theoretical mechanisms to explain the expressiveness of relational GNNs! In the next post, we’ll check the other places Weisfeiler and Leman visited in 2022 and what are the results of their trips 🚠