Message Passing Neural Networks (MPNNs) are a common type of Graph Neural
Network (GNN), in which each node's representation is computed recursively by
aggregating representations (messages) from its immediate neighbors akin to a
star-shaped pattern. MPNNs are appealing for being efficient and scalable,
how-ever their expressiveness is upper-bounded by the 1st-order
Weisfeiler-Lehman isomorphism test (1-WL). In response, prior works propose
highly expressive models at the cost of scalability and sometimes
generalization performance. Our work stands between these two regimes: we
introduce a general framework to uplift any MPNN to be more expressive, with
limited scalability overhead and greatly improved practical performance. We
achieve this by extending local aggregation in MPNNs from star patterns to
general subgraph patterns (e.g.,k-egonets):in our framework, each node
representation is computed as the encoding of a surrounding induced subgraph
rather than encoding of immediate neighbors only (i.e. a star). We choose the
subgraph encoder to be a GNN (mainly MPNNs, considering scalability) to design
a general framework that serves as a wrapper to up-lift any GNN. We call our
proposed method GNN-AK(GNN As Kernel), as the framework resembles a
convolutional neural network by replacing the kernel with GNNs. Theoretically,
we show that our framework is strictly more powerful than 1&2-WL, and is not
less powerful than 3-WL. We also design subgraph sampling strategies which
greatly reduce memory footprint and improve speed while maintaining
performance. Our method sets new state-of-the-art performance by large margins
for several well-known graph ML tasks; specifically, 0.08 MAE on ZINC,74.79%
and 86.887% accuracy on CIFAR10 and PATTERN respectively.

本文提出了一种称为 GNN-AK 的框架，旨在将任何 MPNN 提升为具有更高表达能力的模型，通过扩展 MPNN 中的局部聚合算法到更一般的子图模式，以提高实用性能，同时维持可扩展性；这种方法被证明比常见的 Weisfeiler-Lehman 同构测试更具表达能力，可以用于多个图机器学习任务中.