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.

本文提供了一种统一的方法来研究增强次图 GNN 的架构，包括理论框架和对子图增强 GNN 可表达性的已知结果进行扩展，同时研究了三种用于学习采样子图的方法，通过实验证明了数据驱动架构可以提高标准基准数据集的预测精度，同时减少计算时间。