Graph Neural Networks Are More Powerful Than we Think
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, we derive an alternative analysis that employs
linear algebraic tools and characterize the representational power of GNNs with
respect to the eigenvalue decomposition of the graph operators. We show that
GNNs can distinguish between any graphs that differ in at least one eigenvalue
and design simple GNN architectures that are provably more expressive than the
WL algorithm. Thorough experimental analysis on graph isomorphism and graph
classification datasets corroborates our theoretical results and demonstrates
the effectiveness of the proposed architectures.