  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.
