PatchGT: Transformer over Non-trainable Clusters for Learning Graph Representations
PatchGT: Transformer over Non-trainable Clusters for Learning Graph Representations
复制标题
DOI：
10.48550/arxiv.2211.14425
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Han Gao;Xuhong Han;Jiaoyang Huang;Jian-Xun Wang;Liping Liu
中科院分区：
文献类型：
--
作者：
Han Gao;Xuhong Han;Jiaoyang Huang;Jian-Xun Wang;Liping Liu
最近，Transformer 结构在图学习任务中表现出了良好的性能。然而，这些 Transformer 模型直接在图节点上工作，可能难以学习高级信息。受到应用于图像补丁的视觉 Transformer 的启发，我们提出了一种新的基于 Transformer 的图神经网络：Patch Graph Transformer (PatchGT)。与之前用于学习图表示的基于 Transformer 的模型不同，PatchGT 从不可训练的图补丁中学习，而不是直接从节点中学习。它可以帮助节省计算量并提高模型性能。其关键思想是基于谱聚类将图分割成图块，无需任何可训练参数，模型可以首先使用 GNN 层学习图块级表示，然后使用 Transformer 获得图级表示。该架构利用了图的光谱信息，并结合了 GNN 和 Transformer 的优势。此外，我们从理论上和经验上展示了先前分层可训练集群的局限性。我们还证明了所提出的不可训练谱聚类方法是排列不变的，可以帮助解决图中的信息瓶颈。 PatchGT 比 1-WL 型 GNN 实现了更高的表达能力，实证研究表明 PatchGT 在基准数据集上实现了有竞争力的性能，并为其预测提供了可解释性。我们的算法的实现发布在我们的 Github 存储库中：https://github.com/tufts-ml/PatchGT。
Recently the Transformer structure has shown good performances in graph learning tasks. However, these Transformer models directly work on graph nodes and may have difficulties learning high-level information. Inspired by the vision transformer, which applies to image patches, we propose a new Transformer-based graph neural network: Patch Graph Transformer (PatchGT). Unlike previous transformer-based models for learning graph representations, PatchGT learns from non-trainable graph patches, not from nodes directly. It can help save computation and improve the model performance. The key idea is to segment a graph into patches based on spectral clustering without any trainable parameters, with which the model can first use GNN layers to learn patch-level representations and then use Transformer to obtain graph-level representations. The architecture leverages the spectral information of graphs and combines the strengths of GNNs and Transformers. Further, we show the limitations of previous hierarchical trainable clusters theoretically and empirically. We also prove the proposed non-trainable spectral clustering method is permutation invariant and can help address the information bottlenecks in the graph. PatchGT achieves higher expressiveness than 1-WL-type GNNs, and the empirical study shows that PatchGT achieves competitive performances on benchmark datasets and provides interpretability to its predictions. The implementation of our algorithm is released at our Github repo: https://github.com/tufts-ml/PatchGT.