  Despite the remarkable success of Graph Neural Networks (GNNs), the common
belief is that their representation power is limited and that they are at most
as expressive as the Weisfeiler-Lehman (WL) algorithm. In this paper, we argue
the opposite and show that standard GNNs, with anonymous inputs, produce more
discriminative representations than the WL algorithm. Our novel analysis
employs linear algebraic tools and characterizes the representation power of
GNNs with respect to the eigenvalue decomposition of the graph operators. We
prove that GNNs are able to generate distinctive outputs from white
uninformative inputs, for, at least, all graphs that have different
eigenvalues. We also show that simple convolutional architectures with white
inputs, produce equivariant features that count the closed paths in the graph
and are provably more expressive than the WL representations. Thorough
experimental analysis on graph isomorphism and graph classification datasets
corroborates our theoretical results and demonstrates the effectiveness of the
proposed approach.
