Post #85

​How powerful graph neural networks? I spent last night on studying the proofs from the ground-breaking ICLR paper of 2018, How Poweful are Graph Neural Networks by Xu et al. (a collaboration between MIT and Stanford). I almost convinced myself that everything is correct when I got a major insight that I think I need to share. This paper is revolutionary because it shows that you can build GNN such that it would solve graph isomorphism problem almost surely. In particular, their model, Graph Isomorphism Network (GIN) is as powerful as 1-WL algorithm, which is known for 50 years and almost solves graph isomorphism problem, except for a few edge cases. I think this is how everyone in the field think about this paper: there is an architecture which you can train such that it solves very hard combinatorial problem. But I realized it's not the case and there are situations when GIN cannot distinguish non-isomorphic graphs, essentially meaning that sometimes GIN can be less powerful than 1-WL. In their paper they show that if your aggregation and readout functions are injective then GNN will be as powerful as 1-WL algorithm. Look at theorem below.