Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis
This work addresses a foundational limitation in graph learning for researchers and practitioners, offering improved expressivity in GNNs, though it is incremental in advancing theoretical understanding.
The paper tackles the problem of limited representation power in Graph Neural Networks (GNNs) by showing that standard GNNs with anonymous inputs are more discriminative than the Weisfeiler-Lehman algorithm, as proven through algebraic analysis and validated on graph isomorphism and classification datasets.
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.