Graph Transformers (GTs) such as SAN and GPS are graph processing models that
combine Message-Passing GNNs (MPGNNs) with global Self-Attention. They were
shown to be universal function approximators, with two reservations: 1. The
initial node features must be augmented with certain positional encodings. 2.
The approximation is non-uniform: Graphs of different sizes may require a
different approximating network.
We first clarify that this form of universality is not unique to GTs: Using
the same positional encodings, also pure MPGNNs and even 2-layer MLPs are
non-uniform universal approximators. We then consider uniform expressivity: The
target function is to be approximated by a single network for graphs of all
sizes. There, we compare GTs to the more efficient MPGNN + Virtual Node
architecture. The essential difference between the two model definitions is in
their global computation method -- Self-Attention Vs Virtual Node. We prove
that none of the models is a uniform-universal approximator, before proving our
main result: Neither model's uniform expressivity subsumes the other's. We
demonstrate the theory with experiments on synthetic data. We further augment
our study with real-world datasets, observing mixed results which indicate no
clear ranking in practice as well.

图形转换器是与全局自注意结合的消息传递 GNN 的图形处理模型，它们被证明是通用的函数逼近器，但依赖于位置编码来扩展初始节点特征。此研究对比了图形转换器和更高效的消息传递 GNN + 虚拟节点结构在图形大小上的一致表达性，并证明两种模型的表达能力不相互包含。实验结果表明在实践中无法明确排名。

身着荣誉：自注意力与虚拟节点

Distinguished In Uniform: Self Attention Vs. Virtual Nodes

We propose an extension to the transformer neural network architecture for
general-purpose graph learning by adding a dedicated pathway for pairwise
structural information, called edge channels. The resultant framework - which
we call Edge-augmented Graph Transformer (EGT) - can directly accept, process
and output structural information of arbitrary form, which is important for
effective learning on graph-structured data. Our model exclusively uses global
self-attention as an aggregation mechanism rather than static localized
convolutional aggregation. This allows for unconstrained long-range dynamic
interactions between nodes. Moreover, the edge channels allow the structural
information to evolve from layer to layer, and prediction tasks on edges/links
can be performed directly from the output embeddings of these channels. We
verify the performance of EGT in a wide range of graph-learning experiments on
benchmark datasets, in which it outperforms Convolutional/Message-Passing Graph
Neural Networks. EGT sets a new state-of-the-art for the quantum-chemical
regression task on the OGB-LSC PCQM4Mv2 dataset containing 3.8 million
molecular graphs. Our findings indicate that global self-attention based
aggregation can serve as a flexible, adaptive and effective replacement of
graph convolution for general-purpose graph learning. Therefore, convolutional
local neighborhood aggregation is not an essential inductive bias.

该论文提出了一种名为 Edge-augmented Graph Transformer (EGT) 的框架来处理任意形式的结构数据，其中使用全局自我关注作为聚合机制，并通过边缘通道来演化结构信息，从而在图结构数据的学习任务中超越了卷积 / 消息传递图神经网络，并在 OGB-LSC PCQM4Mv2 数据集上实现了量子化学回归任务的最新性能。

全局自注意力作为图卷积替代方案

Global Self-Attention as a Replacement for Graph Convolution

Medical image segmentation is an essential prerequisite for developing
healthcare systems, especially for disease diagnosis and treatment planning. On
various medical image segmentation tasks, the u-shaped architecture, also known
as U-Net, has become the de-facto standard and achieved tremendous success.
However, due to the intrinsic locality of convolution operations, U-Net
generally demonstrates limitations in explicitly modeling long-range
dependency. Transformers, designed for sequence-to-sequence prediction, have
emerged as alternative architectures with innate global self-attention
mechanisms, but can result in limited localization abilities due to
insufficient low-level details. In this paper, we propose TransUNet, which
merits both Transformers and U-Net, as a strong alternative for medical image
segmentation. On one hand, the Transformer encodes tokenized image patches from
a convolution neural network (CNN) feature map as the input sequence for
extracting global contexts. On the other hand, the decoder upsamples the
encoded features which are then combined with the high-resolution CNN feature
maps to enable precise localization.
We argue that Transformers can serve as strong encoders for medical image
segmentation tasks, with the combination of U-Net to enhance finer details by
recovering localized spatial information. TransUNet achieves superior
performances to various competing methods on different medical applications
including multi-organ segmentation and cardiac segmentation. Code and models
are available at this https URL

本文提出了一种新的医学图像分割框架 TransUNet，它将 Transformers 和 U-Net 结合起来，通过编码全局上下文和恢复本地细节信息来实现更精确的分割，针对不同的医学应用，TransUNet 优于其他竞争方法。