Using substructures for provably expressive graph neural networks

The figure below shows an example most of us are familiar with, the molecule of caffeine, whose level in my bloodstream is alarmingly low. TL;DR: In this post, I discuss how to design local and computationally efficient provably powerful graph neural networks that are not based on the Weisfeiler-Lehman tests hierarchy. This is the second in the series of posts on the expressivity of graph neural networks. In Part 3, I will argue why we should abandon the graph isomorphism problem altogether._ Recent groundbreaking papers [1–2] established the connection between graph neural networks and the graph isomorphism tests, observing the analogy between the message passing mechanism and the Weisfeiler-Lehman (WL) test [3].