Graph neural networks (GNNs) are commonly described as being permutation
equivariant with respect to node relabeling in the graph. This symmetry of GNNs
is often compared to the translation equivariance symmetry of Euclidean
convolution neural networks (CNNs). However, these two symmetries are
fundamentally different: The translation equivariance of CNNs corresponds to
symmetries of the fixed domain acting on the image signal (sometimes known as
active symmetries), whereas in GNNs any permutation acts on both the graph
signals and the graph domain (sometimes described as passive symmetries). In
this work, we focus on the active symmetries of GNNs, by considering a learning
setting where signals are supported on a fixed graph. In this case, the natural
symmetries of GNNs are the automorphisms of the graph. Since real-world graphs
tend to be asymmetric, we relax the notion of symmetries by formalizing
approximate symmetries via graph coarsening. We present a bias-variance formula
that quantifies the tradeoff between the loss in expressivity and the gain in
the regularity of the learned estimator, depending on the chosen symmetry
group. To illustrate our approach, we conduct extensive experiments on image
inpainting, traffic flow prediction, and human pose estimation with different
choices of symmetries. We show theoretically and empirically that the best
generalization performance can be achieved by choosing a suitably larger group
than the graph automorphism group, but smaller than the full permutation group.

图神经网络 (GNNs) 和欧几里德卷积神经网络 (CNNs) 的等变性对称性不同，本篇论文侧重于探讨 GNNs 的主动对称性，通过对信号在固定图上的支持进行学习，将近似对称性形式化为图粗化，提出了一个偏差 - 方差公式来量化损失表达性与学习估计的规则性之间的权衡，实验证明，选择比图自同构群大但小于全排列群的适当大的群可以达到最佳泛化性能。