On the equivalence between graph isomorphism testing and function approximation with GNNs

Abstract

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.

Strengthened Theorem 4 with a modified proof; Updated Figure 2 to include results from the later literature; Made other minor edits to improve clarity. 22 pages

References in corpus (5)

• Semi-Supervised Classification with Graph Convolutional Networks
• How Powerful are Graph Neural Networks?
• Universal Invariant and Equivariant Graph Neural Networks
• Probabilistic symmetries and invariant neural networks
• Relational Pooling for Graph Representations

Cited by in corpus (12)

• On Learning Sets of Symmetric Elements
• Graph Neural Networks: Methods, Applications, and Opportunities
• What graph neural networks cannot learn: depth vs width
• Soft-mask: Adaptive Substructure Extractions for Graph Neural Networks
• Set2Graph: Learning Graphs From Sets
• Equivariant Subgraph Aggregation Networks
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
• Learning Graph Normalization for Graph Neural Networks
• Fundamental Limits of Deep Graph Convolutional Networks
• Complete Neural Networks for Complete Euclidean Graphs
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version
• Equivariant and Invariant Reynolds Networks