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.

1. INTRODUCTION

The success of Graph Neural Networks (GNNs) across a wide range of tasks has sparked significant research interest in demystifying their functionality and understanding their fundamental properties. In this pursuit, [1] delves into the analysis of GNNs’ permutation invariance-equivariance, and [2] proves their stability to perturbations. An important line of work investigates the transferability of GNNs to very large graphs [3], [4], while [5], [6] discuss the universality properties of GNNs, particularly in the context of functions that exhibit permutation invariance or equivariance.