On the equivalence between graph isomorphism testing and function approximation with GNNs
This work provides a foundational theoretical framework for understanding GNN expressive power, impacting researchers in graph machine learning.
The paper connects two perspectives on Graph Neural Networks (GNNs) by proving the equivalence between their ability to approximate permutation-invariant functions and test graph isomorphism, and introduces Ring-GNN, which distinguishes non-isomorphic regular graphs and performs well on real-world datasets.
Graph Neural Networks (GNNs) have achieved much success on graph-structured data. In light of this, there have been increasing interests in studying their expressive power. One line of work studies the capability of GNNs to approximate permutation-invariant functions on graphs, and another focuses on the their power as tests for graph isomorphism. Our work connects these two perspectives and proves their equivalence. We further develop a framework of the expressive power of GNNs that incorporates both of these viewpoints using the language of sigma-algebra, through which we compare the expressive power of different types of GNNs together with other graph isomorphism tests. In particular, we prove that the second-order Invariant Graph Network fails to distinguish non-isomorphic regular graphs with the same degree. Then, we extend it to a new architecture, Ring-GNN, which succeeds in distinguishing these graphs and achieves good performances on real-world datasets.