In the realm of Graph Neural Networks (GNNs), two exciting research
directions have recently emerged: Subgraph GNNs and Graph Transformers. In this
paper, we propose an architecture that integrates both approaches, dubbed
Subgraphormer, which combines the enhanced expressive power, message-passing
mechanisms, and aggregation schemes from Subgraph GNNs with attention and
positional encodings, arguably the most important components in Graph
Transformers. Our method is based on an intriguing new connection we reveal
between Subgraph GNNs and product graphs, suggesting that Subgraph GNNs can be
formulated as Message Passing Neural Networks (MPNNs) operating on a product of
the graph with itself. We use this formulation to design our architecture:
first, we devise an attention mechanism based on the connectivity of the
product graph. Following this, we propose a novel and efficient positional
encoding scheme for Subgraph GNNs, which we derive as a positional encoding for
the product graph. Our experimental results demonstrate significant performance
improvements over both Subgraph GNNs and Graph Transformers on a wide range of
datasets.

本文提出了一个结合 Subgraph GNNs 和 Graph Transformers 的架构，名为 Subgraphormer，通过将 Subgraph GNNs 的增强表达能力、消息传递机制和聚合方案与 Graph Transformers 中最重要的组件 —— 注意力机制和位置编码相结合。我们的方法基于 Subgraph GNNs 和自身的图像乘积之间的新联系，将 Subgraph GNNs 表述为在图像乘积上操作的 Message Passing Neural Networks (MPNNs)。我们利用这种表述设计了我们的架构：首先，我们设计了一个基于图像乘积的连接性的注意力机制。其次，我们提出了一种新颖高效的 Subgraph GNNs 位置编码方案，将其推导为图像乘积的位置编码。我们的实验结果显示，在广泛的数据集上，相比于 Subgraph GNNs 和 Graph Transformers，我们的方法显著提升了性能。