We consider the problem of discovering subgroup $H$ of permutation group
$S_{n}$. Unlike the traditional $H$-invariant networks wherein $H$ is assumed
to be known, we present a method to discover the underlying subgroup, given
that it satisfies certain conditions. Our results show that one could discover
any subgroup of type $S_{k} (k \leq n)$ by learning an $S_{n}$-invariant
function and a linear transformation. We also prove similar results for cyclic
and dihedral subgroups. Finally, we provide a general theorem that can be
extended to discover other subgroups of $S_{n}$. We also demonstrate the
applicability of our results through numerical experiments on image-digit sum
and symmetric polynomial regression tasks.

我们考虑寻找置换群 S_n 的子群 H 的问题。我们提出了一种方法，可以在满足一定条件的情况下发现隐藏的子群 H。我们的结果表明通过学习一个 S_n 不变函数和一个线性变换可以发现任何类型为 S_k (k ≤ n) 的子群。我们还证明了循环子群和二面体子群的类似结果。最后，我们提供了一个可以扩展到发现 S_n 的其他子群的通用定理。我们还通过图像位数和对称多项式回归任务的数值实验验证了我们的结果的适用性。

置换子群的神经发现

Neural Discovery of Permutation Subgroups

Graph Neural Networks (GNN) come in many flavors, but should always be either
invariant (permutation of the nodes of the input graph does not affect the
output) or equivariant (permutation of the input permutes the output). In this
paper, we consider a specific class of invariant and equivariant networks, for
which we prove new universality theorems. More precisely, we consider networks
with a single hidden layer, obtained by summing channels formed by applying an
equivariant linear operator, a pointwise non-linearity and either an invariant
or equivariant linear operator. Recently, Maron et al. (2019) showed that by
allowing higher-order tensorization inside the network, universal invariant
GNNs can be obtained. As a first contribution, we propose an alternative proof
of this result, which relies on the Stone-Weierstrass theorem for algebra of
real-valued functions. Our main contribution is then an extension of this
result to the equivariant case, which appears in many practical applications
but has been less studied from a theoretical point of view. The proof relies on
a new generalized Stone-Weierstrass theorem for algebra of equivariant
functions, which is of independent interest. Finally, unlike many previous
settings that consider a fixed number of nodes, our results show that a GNN
defined by a single set of parameters can approximate uniformly well a function
defined on graphs of varying size.

本文研究了一类具有单隐藏层的不变和等变网络，并证明了其新的普适性定理。首先，本文提出了一种以代数理论为基础的证明方式。其次，本文将这一结果扩展到等变网络中，该领域的理论研究相对较少。最后，本文的结果表明，相同的参数可以在具有不同规模的图上近似实现一定的函数。

普适不变与等变图神经网络

Universal Invariant and Equivariant Graph Neural Networks

Invariant and equivariant networks have been successfully used for learning
images, sets, point clouds, and graphs. A basic challenge in developing such
networks is finding the maximal collection of invariant and equivariant linear
layers. Although this question is answered for the first three examples (for
popular transformations, at-least), a full characterization of invariant and
equivariant linear layers for graphs is not known.
In this paper we provide a characterization of all permutation invariant and
equivariant linear layers for (hyper-)graph data, and show that their
dimension, in case of edge-value graph data, is 2 and 15, respectively. More
generally, for graph data defined on k-tuples of nodes, the dimension is the
k-th and 2k-th Bell numbers. Orthogonal bases for the layers are computed,
including generalization to multi-graph data. The constant number of basis
elements and their characteristics allow successfully applying the networks to
different size graphs. From the theoretical point of view, our results
generalize and unify recent advancement in equivariant deep learning. In
particular, we show that our model is capable of approximating any message
passing neural network
Applying these new linear layers in a simple deep neural network framework is
shown to achieve comparable results to state-of-the-art and to have better
expressivity than previous invariant and equivariant bases.

本文提供了对（超）图数据的所有置换不变和等变线性层的表征，并展示了它们的维度，并计算出这些层的正交基，包括对多图数据的推广。同时，在简单的深度神经网络框架中应用这些新的线性层，可以获得比之前的不变性和等变性基础更好的表现，并且可以实现任何消息传递神经网络的近似。