Graph Neural Networks are More Powerful than We Think

Graph Neural Networks (GNNs) are powerful architectures that have demonstrated remarkable performance in various node-level and graph-level tasks. Despite this success, prominent analysis shows that their representation power is limited and that they are at most as expressive as the Weisfeiler-Lehman (WL) test. In this paper, we take a different approach and analyze the expressive power of GNNs with respect to the spectral decomposition of the graph operators. We prove that GNNs can produce distinct equivariant outputs for all graphs with different eigenvalues, therefore surpassing the limitations of the WL test. On the practical front, our approach enables the design of GNNs that unlock the full potential of their expressive power. Thorough experimental analysis on graph classification datasets supports our theoretical findings and showcases the effectiveness of the proposed approach.