Graph transformers have recently received significant attention in graph
learning, partly due to their ability to capture more global interaction via
self-attention. Nevertheless, while higher-order graph neural networks have
been reasonably well studied, the exploration of extending graph transformers
to higher-order variants is just starting. Both theoretical understanding and
empirical results are limited. In this paper, we provide a systematic study of
the theoretical expressive power of order-$k$ graph transformers and sparse
variants. We first show that, an order-$k$ graph transformer without additional
structural information is less expressive than the $k$-Weisfeiler Lehman
($k$-WL) test despite its high computational cost. We then explore strategies
to both sparsify and enhance the higher-order graph transformers, aiming to
improve both their efficiency and expressiveness. Indeed, sparsification based
on neighborhood information can enhance the expressive power, as it provides
additional information about input graph structures. In particular, we show
that a natural neighborhood-based sparse order-$k$ transformer model is not
only computationally efficient, but also expressive -- as expressive as $k$-WL
test. We further study several other sparse graph attention models that are
computationally efficient and provide their expressiveness analysis. Finally,
we provide experimental results to show the effectiveness of the different
sparsification strategies.

系统研究了高阶图转换器和稀疏变体的理论表达能力，通过基于邻域信息的稀疏化，提高了传统模型的效率和表达能力。

关于高阶图变换器的理论表达能力和设计空间

On the Theoretical Expressive Power and the Design Space of Higher-Order  Graph Transformers

DETR-like models have significantly boosted the performance of detectors and
even outperformed classical convolutional models. However, all tokens are
treated equally without discrimination brings a redundant computational burden
in the traditional encoder structure. The recent sparsification strategies
exploit a subset of informative tokens to reduce attention complexity
maintaining performance through the sparse encoder. But these methods tend to
rely on unreliable model statistics. Moreover, simply reducing the token
population hinders the detection performance to a large extent, limiting the
application of these sparse models. We propose Focus-DETR, which focuses
attention on more informative tokens for a better trade-off between computation
efficiency and model accuracy. Specifically, we reconstruct the encoder with
dual attention, which includes a token scoring mechanism that considers both
localization and category semantic information of the objects from multi-scale
feature maps. We efficiently abandon the background queries and enhance the
semantic interaction of the fine-grained object queries based on the scores.
Compared with the state-of-the-art sparse DETR-like detectors under the same
setting, our Focus-DETR gets comparable complexity while achieving 50.4AP
(+2.2) on COCO. The code is available at
this https URL and
this https URL

DETR-like 模型相比传统卷积模型有很大的提升效果，然而现有的编码器结构中所有的令牌都被平等对待，不加区分地处理给传统的编码器结构带来了冗余计算负担，因此提出了 Focus-DETR 来得到更好的计算效率和模型准确性的权衡，通过使用双重注意力的编码器对更具信息量的令牌进行关注，并通过得分来增强细粒度对象查询的语义交互。