Neural networks that satisfy invariance with respect to input permutations
have been widely studied in machine learning literature. However, in many
applications, only a subset of all input permutations is of interest. For
heterogeneous graph data, one can focus on permutations that preserve node
types. We fully characterize linear layers invariant to such permutations. We
verify experimentally that implementing these layers in graph neural network
architectures allows learning important node interactions more effectively than
existing techniques. We show that the dimension of space of these layers is
given by a generalization of Bell numbers, extending the work (Maron et al.,
2019). We further narrow the invariant network design space by addressing a
question about the sizes of tensor layers necessary for function approximation
on graph data. Our findings suggest that function approximation on a graph with
$n$ nodes can be done with tensors of sizes $\leq n$, which is tighter than the
best-known bound $\leq n(n-1)/2$. For $d \times d$ image data with translation
symmetry, our methods give a tight upper bound $2d - 1$ (instead of $d^{4}$) on
sizes of invariant tensor generators via a surprising connection to Davenport
constants.

该论文研究了神经网络在输入排列不同时的不变性，针对异构图数据，提出了保留节点类型排列的线性层公式，实验表明该方法可以更有效地学习节点交互。并对张量层大小问题进行了探究，发现对于 $n$ 个节点的图数据，张量大小的上限为 $n$，优于之前的结果。