Graph Neural Networks Are More Powerful Than we Think. (arXiv:2205.09801v1 [cs.LG])

Graph Neural Networks (GNNs) are powerful convolutional architectures that
have shown remarkable performance in various node-level and graph-level tasks.
Despite their success, the common belief is that the expressive power of GNNs
is limited and that they are at most as discriminative as the Weisfeiler-Lehman
(WL) algorithm. In this paper we argue the opposite and show that the WL
algorithm is the upper bound only when the input to the GNN is the vector of
all ones. In this direction, …

arxiv graph graph neural networks networks neural networks think