Although Transformer has achieved great success in natural language process and computer vision, it has difficulty generalizing to medium and large-scale graph data for two important reasons: (i) High complexity. (ii) Failing to capture the complex and entangled structure information. In graph representation learning, Graph Neural Networks(GNNs) can fuse the graph structure and node attributes but have limited receptive fields. Therefore, we question whether can we combine Transformers and GNNs to help each other. In this paper, we propose a new model named TransGNN where the Transformer layer and GNN layer are used alternately to improve each other. Specifically, to expand the receptive field and disentangle the information aggregation from edges, we propose using Transformer to aggregate more relevant nodes' information to improve the message passing of GNNs. Besides, to capture the graph structure information, we utilize positional encoding and make use of the GNN layer to fuse the structure into node attributes, which improves the Transformer in graph data. We also propose to sample the most relevant nodes for Transformer and two efficient samples update strategies to lower the complexity. At last, we theoretically prove that TransGNN is more expressive than GNNs only with extra linear complexity. The experiments on eight datasets corroborate the effectiveness of TransGNN on node and graph classification tasks.

在这篇论文中，我们提出了一种名为TransGNN的新模型，其中Transformer层和GNN层交替使用以相互改进。我们利用Transformer来聚合更相关的节点信息以改善GNNs的消息传递，并利用位置编码和GNN层将图结构融入节点属性中，改善Transformer在图数据中的表现。通过理论证明，我们证明了TransGNN相对于仅具有额外线性复杂度的GNNs更具表达力。在八个数据集上的实验证实了TransGNN在节点和图分类任务上的有效性。

Transformer和GNN能互助吗？