The Transformer architecture has gained growing attention in graph representation learning recently, as it naturally overcomes several limitations of graph neural networks (GNNs) by avoiding their strict structural inductive biases and instead only encoding the graph structure via positional encoding. Here, we show that the node representations generated by the Transformer with positional encoding do not necessarily capture structural similarity between them. To address this issue, we propose the Structure-Aware Transformer, a class of simple and flexible graph Transformers built upon a new self-attention mechanism. This new self-attention incorporates structural information into the original self-attention by extracting a subgraph representation rooted at each node before computing the attention. We propose several methods for automatically generating the subgraph representation and show theoretically that the resulting representations are at least as expressive as the subgraph representations. Empirically, our method achieves state-of-the-art performance on five graph prediction benchmarks. Our structure-aware framework can leverage any existing GNN to extract the subgraph representation, and we show that it systematically improves performance relative to the base GNN model, successfully combining the advantages of GNNs and Transformers. Our code is available at https://github.com/BorgwardtLab/SAT.
翻译:最近,在图形代表学习中,变异器结构受到越来越多的注意,因为它自然地克服了图形神经网络(GNNS)的若干局限性,避免了严格的结构性导导偏,而只是通过定位编码对图形结构进行编码。在这里,我们表明变异器生成的带有位置编码的节点表示不一定反映它们之间的结构相似性。为了解决这一问题,我们提议了结构-软件变异器,这是建立在新的自我注意机制基础上的简单灵活的图形变异器的一类。这种新的自我注意将结构信息纳入原始自我注意,在计算注意之前从每个节点提取一个子图示表示法。我们提出了自动生成子图表示法的若干方法,并在理论上表明由此产生的表达方式至少与子表示法相似。我们的方法在五个图形预测基准上实现了“状态-艺术”的性能。我们的结构-恒定框架可以利用任何现有的GNNE来提取子表示法代表制,并且我们表明它系统地改进了相对于基础GNNNS模型的性能,从而成功地将GNNP/wardb/Ms的优势结合起来。我们的代码是GNNSP/GNS/GRAVLs。