Department of Computer, Control and Management Engineering

Abstract

Graph Neural Networks (GNNs) are a wide class of connectionist models for graph processing. Recent studies have linked the expressive power of GNNs to the Weisfeiler--Lehman algorithm, which is a method of verifying whether two graphs are isomorphic or not. On the other hand, it was also observed that the computational power of GNNs is related to the unfolding trees,  namely  trees that can be constructed by visiting the graph from a given node. In this paper, we unify these two theories and prove that the  Weisfeiler--Lehman test and the unfolding trees induce the same  equivalence relationship on the graph nodes: such an equivalenceexactly explains which nodes can or cannot be distinguished by a GNN. Moreover, it is proved that GNNs can approximate in probability, up  to  any  precision,  any  function  on  graphs  that  respects  the  above mentioned equivalence relationship. These results provide a more comprehensive understanding of the computational power of GNNs in node classification/regression tasks

You can also join online at https://meet.google.com/mja-amts-tze?authuser=0&hs=122