While (message-passing) graph neural networks have clear limitations in approximating permutation-equivariant functions over graphs or general relational data, more expressive, higher-order graph neural networks do not scale to large graphs. They either operate on $k$-order tensors or consider all $k$-node subgraphs, implying an exponential dependence on $k$ in memory requirements, and do not adapt to the sparsity of the graph. By introducing new heuristics for the graph isomorphism problem, we devise a class of universal, permutation-equivariant graph networks, which, unlike previous architectures, offer a fine-grained control between expressivity and scalability and adapt to the sparsity of the graph. These architectures lead to vastly reduced computation times compared to standard higher-order graph networks in the supervised node- and graph-level classification and regression regime while significantly improving over standard graph neural network and graph kernel architectures in terms of predictive performance.

通过引入新的图同构解决方案，我们设计了一类通用的置换等变图网络，这些架构与以前的架构不同，提供了表达能力和可扩展性之间的细粒度控制，并适应了图的稀疏性。在监督节点和图级分类和回归方案中，这些架构与标准高阶图网络相比计算时间大大缩短，同时在预测性能方面显着提高，而且与标准图神经网络和图内核架构相比也有很大的优势。

SpeqNets：稀疏感知置换等变图网络