Numerous subgraph-enhanced graph neural networks (GNNs) have emerged recently, provably boosting the expressive power of standard (message-passing) GNNs. However, there is a limited understanding of how these approaches relate to each other and to the Weisfeiler--Leman hierarchy. Moreover, current approaches either use all subgraphs of a given size, sample them uniformly at random, or use hand-crafted heuristics instead of learning to select subgraphs in a data-driven manner. Here, we offer a unified way to study such architectures by introducing a theoretical framework and extending the known expressivity results of subgraph-enhanced GNNs. Concretely, we show that increasing subgraph size always increases the expressive power and develop a better understanding of their limitations by relating them to the established $k\text{-}\mathsf{WL}$ hierarchy. In addition, we explore different approaches for learning to sample subgraphs using recent methods for backpropagating through complex discrete probability distributions. Empirically, we study the predictive performance of different subgraph-enhanced GNNs, showing that our data-driven architectures increase prediction accuracy on standard benchmark datasets compared to non-data-driven subgraph-enhanced graph neural networks while reducing computation time.
翻译:最近出现了许多亚字加固的图形神经网络(GNNs),这可以明显地增强标准(消息传递)GNNs的表达力。然而,对于这些方法彼此之间以及与Weisfeiler-Leman等级的关系,人们的认识有限。此外,目前的方法要么使用一个特定大小的所有子图,统一地随机抽样,要么使用手工制作的休眠技术,而不是学习以数据驱动的方式选择子图。这里,我们提供了一个统一的方法来研究这些结构,方法是引入一个理论框架,扩大子图加固的GNNs已知的表达力结果。具体地说,我们表明,增加子图的规模总是增加表达力,并通过将其与既定的 $k\ text{ ⁇ mathsf{{WL}等级挂钩,来更好地了解其局限性。此外,我们探索了不同的方法来学习抽样子图,利用最近的方法,通过复杂的离心概率分布进行反向调整。我们用想象力研究的是,我们比较了预测的GNS型数据驱动的子计算结构,同时比较了我们以不同基准数据驱动的G的精确度预测性数据结构。