Defining Expressiveness for Graph Classification

In the previous chapter, we traded accuracy for scalability. We saw that it was instrumental in applications such as recommender systems. However, it raises several questions about what makes GNNs “accurate.” Where does this precision come from? Can we use this knowledge to design better GNNs?

This chapter will clarify what makes a GNN powerful by introducing the Weisfeiler-Leman (WL) test. This test will give us the framework to understand an essential concept in GNNs – expressiveness. We will use it to compare different GNN layers and see which one is the most expressive. This result will then be used to design a more powerful GNN than GCNs, GATs, and GraphSAGE.

Finally, we will implement it using PyTorch Geometric to perform a new task – graph classification. We will implement a new GNN on the PROTEINS dataset, comprising 1,113 graphs representing proteins. We will compare different methods for graph...