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

By Zhengdao Chen, Soledad Villar, Lei Chen, Joan Bruna. 2019

311 citations recorded by the source corpus.

Graph neural networks (GNNs) have achieved lots of success on graph-structured data. In the light of this, there has been increasing interest in studying their representation power. One line of work focuses on the universal approximation of permutation-invariant functions by certain classes of GNNs, and another demonstrates the limitation of GNNs via graph isomorphism tests. Our work connects these two perspectives and proves their equivalence. We further develop a framework of the representation power of GNNs with the language of sigma-algebra, which incorporates both viewpoints. Using this framework, we compare the expressive power of different classes of GNNs as well as other methods on graphs. In particular, we prove that order-2 Graph G-invariant networks fail to distinguish non-isomorphic regular graphs with the same degree. We then extend them to a new architecture, Ring-GNNs, which succeeds on distinguishing these graphs and provides improvements on real-world social network datasets.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Set2Graph: Learning Graphs From Sets (2020, background): “…models, such as message passing (a.k.a. graph convolutional networks), are known to be non-universal (Xu et al., 2019; Morris et al., 2018; Maron et al., 2019a; Chen et al., 2019); high-order equivariant models are known to be universal (Maron et al., 2019c) but as discussed above, not practical.”
On the Equivalence between Positional Node Embeddings and Structural Graph Representations (2019, background): “y of literature focused on node and whole-graph classiﬁcation tasks. Theoretically, these works abandon metric spaces in favor of a group-theoretic description of graphs (Bloem-Reddy & Teh, 2019; Chen et al., 2019; Kondor & Trivedi, 2018; Maron et al., 2019; Murphy et al., 2019), with connec”
How Powerful are Spectral Graph Neural Networks (2022, background): “Since then, various works have attempted to analyze GNNs with the WL test and graph isomorphism testing (Zhang et al., 2018; Morris et al., 2019; Maron et al., 2019a; Chen et al., 2019; Li et al., 2020; Sato et al., 2019; 2021; Zhang et al., 2021; Zhang & Li, 2021).”
Can graph neural networks count substructures? (2020, background): “If k = 2, on one hand, it is known that 2-IGNs are at least as powerful as 2-WL [38]; on the other hand, 2-IGNs are not universal [8].”
Graph Neural Networks with Learnable Structural and Positional Representations (2021, methodology): “Another approach is to compute higher-order node-tuple aggregations such as in WL-based GNNs (Maron et al., 2019; Chen et al., 2019); though these models are computationally more expensive to scale than MP-GNNs, even for medium-sized graphs (Dwivedi et al.”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “Higher-order Invariant Graph Networks (IGNs) have been studied in a series of works [22], [23], [24], [39], [64], [65], establishing connections with the WL hierarchy, similarly to [17], [66].”
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (2020, methodology): “From the theoretical perspective, most previous works only considered representations of entire graphs [26–30,42,43] while Srinivasan & Ribeiro initialized the investigation of structural representations of node sets [44] from the view of joint probabilistic distributions.”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, background): “In particular, GRAPHEDM is general enough that it can be used to succinctly describe over thirty GRL methods (both unsupervised and supervised).”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “This inspired a large body of research on stronger variants of GNNs [20, 91, 85, 86, 92, 93, 94] which provably overcome these limitations.”
What graph neural networks cannot learn: depth vs width (2019, background): “Since Turing universality is a strictly stronger property than universal approximation, Chen et al. (2019)’s argument further implies that a Turing universal GNN mp can solve the graph isomorphism problem (a sufﬁciently deep and wide network can compute the isomorphism class of its input).”
Identity-aware Graph Neural Networks (2021, methodology): “Recently, many neural networks have been proposed with expressive power beyond the 1-WL test, including (Chen et al. 2019; Maron et al. 2019a; Murphy et al. 2019; You, Ying, and Leskovec 2019; Li et al. 2020).”
Representation Learning for Dynamic Graphs: A Survey (2019, background): “Chen et al. (2019c) demonstrate that these two approaches to the expressivity of GCNs are closely related.”
Graph Information Bottleneck (2020, unknown): “Recently, many works have been focusing on developing more powerful GNNs [8–13], in a sense that they can ﬁt more complex graph-structured data.”
Benchmarking Graph Neural Networks (2023, methodology): “We train on the 5-fold cross validation with 20 different seeds of initialization, following [18].”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “We repeated each experiment ﬁve times (with different random splits in case of A LCHEMY and Q M 9) and report average scores and standard deviations.”