Timezone: »

 
Poster
On the equivalence between graph isomorphism testing and function approximation with GNNs
Zhengdao Chen · Soledad Villar · Lei Chen · Joan Bruna

Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #69
in Algorithms -- Relational Learning »

Graph neural networks (GNNs) have achieved lots of success on graph-structured data. In 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-GNN, which succeeds in distinguishing these graphs as well as for tasks on real-world datasets.

Keywords: Algorithms -> Relational Learning · Deep Learning; Deep Learning -> Interaction-Based Deep Networks; Theory -> Hardness of Learning and Approximations; Theory -> S

Author Information

Zhengdao Chen (New York University)
Soledad Villar (New York University)
Lei Chen (New York University)
Joan Bruna (NYU)

More from the Same Authors