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.

本研究通过引入 sigma 代数框架，将 GNN 的表现力和测试同构性的角度进行了比较，证明了不同类型的 GNN 的表现力在确定的条件下是等价的，提出了一种新的结构 Ring-GNN，该结构成功地区分了具有相同度数的非同构正则图，并在现实世界数据集上取得了良好的性能。

图同构测试与 GNN 函数逼近的等价性研究

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

We consider a simple and overarching representation for permutation-invariant
functions of sequences (or multiset functions). Our approach, which we call
Janossy pooling, expresses a permutation-invariant function as the average of a
permutation-sensitive function applied to all reorderings of the input
sequence. This allows us to leverage the rich and mature literature on
permutation-sensitive functions to construct novel and flexible
permutation-invariant functions. If carried out naively, Janossy pooling can be
computationally prohibitive. To allow computational tractability, we consider
three kinds of approximations: canonical orderings of sequences, functions with
$k$-order interactions, and stochastic optimization algorithms with random
permutations. Our framework unifies a variety of existing work in the
literature, and suggests possible modeling and algorithmic extensions. We
explore a few in our experiments, which demonstrate improved performance over
current state-of-the-art methods.

本文提出了 Janossy pooling 方法，可以将置换不变函数表示为输入序列的所有重新排序应用置换敏感函数的平均值，并且通过三种近似方法实现了可计算性可控，实验结果表明该方法在置换不变函数的构建上表现出了比当前最先进的方法更好的性能。