Subgraph-enhanced graph neural networks (SGNN) can increase the expressive
power of the standard message-passing framework. This model family represents
each graph as a collection of subgraphs, generally extracted by random sampling
or with hand-crafted heuristics. Our key observation is that by selecting
"meaningful" subgraphs, besides improving the expressivity of a GNN, it is also
possible to obtain interpretable results. For this purpose, we introduce a
novel framework that jointly predicts the class of the graph and a set of
explanatory sparse subgraphs, which can be analyzed to understand the decision
process of the classifier. We compare the performance of our framework against
standard subgraph extraction policies, like random node/edge deletion
strategies. The subgraphs produced by our framework allow to achieve comparable
performance in terms of accuracy, with the additional benefit of providing
explanations.

该论文介绍了如何利用有意义的子图来加强图神经网络的表达能力，并提出了一个能够同时预测图分类和辅助解释性稀疏子图的新框架，其所提供的子图能够在保持相近精度的情况下提供说明性的解释。

结合随机解释器和子图神经网络可提高表达能力和可解释性

Combining Stochastic Explainers and Subgraph Neural Networks can  Increase Expressivity and Interpretability

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 可表达性的已知结果进行扩展，同时研究了三种用于学习采样子图的方法，通过实验证明了数据驱动架构可以提高标准基准数据集的预测精度，同时减少计算时间。