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

• URL: http://arxiv.org/abs/2404.03380v1
• Date: Thu, 4 Apr 2024 11:26:51 GMT
• Title: On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformers
• Authors: Cai Zhou, Rose Yu, Yusu Wang,
• Abstract summary: We study the theoretical expressive power of order-$k$ graph transformers and sparse variants. We show that a natural neighborhood-based sparse order-$k$ transformer model is not only computationally efficient, but also expressive.
• Score: 20.73012427295352
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• SGFormer: Single-Layer Graph Transformers with Approximation-Free Linear Complexity [74.51827323742506]
  We evaluate the necessity of adopting multi-layer attentions in Transformers on graphs. We show that one-layer propagation can be reduced to one-layer propagation, with the same capability for representation learning. It suggests a new technical path for building powerful and efficient Transformers on graphs.
  arXiv  Detail & Related papers  (2024-09-13T17:37:34Z)
• Deep Prompt Tuning for Graph Transformers [55.2480439325792]
  Fine-tuning is resource-intensive and requires storing multiple copies of large models. We propose a novel approach called deep graph prompt tuning as an alternative to fine-tuning. By freezing the pre-trained parameters and only updating the added tokens, our approach reduces the number of free parameters and eliminates the need for multiple model copies.
  arXiv  Detail & Related papers  (2023-09-18T20:12:17Z)
• Are More Layers Beneficial to Graph Transformers? [97.05661983225603]
  Current graph transformers suffer from the bottleneck of improving performance by increasing depth. Deep graph transformers are limited by the vanishing capacity of global attention. We propose a novel graph transformer model named DeepGraph that explicitly employs substructure tokens in the encoded representation.
  arXiv  Detail & Related papers  (2023-03-01T15:22:40Z)
• Transformers over Directed Acyclic Graphs [6.263470141349622]
  We study transformers over directed acyclic graphs (DAGs) and propose architecture adaptations tailored to DAGs. We show that it is effective in making graph transformers generally outperform graph neural networks tailored to DAGs and in improving SOTA graph transformer performance in terms of both quality and efficiency.
  arXiv  Detail & Related papers  (2022-10-24T12:04:52Z)
• Pure Transformers are Powerful Graph Learners [51.36884247453605]
  We show that standard Transformers without graph-specific modifications can lead to promising results in graph learning both in theory and practice. We prove that this approach is theoretically at least as expressive as an invariant graph network (2-IGN) composed of equivariant linear layers. Our method coined Tokenized Graph Transformer (TokenGT) achieves significantly better results compared to GNN baselines and competitive results.
  arXiv  Detail & Related papers  (2022-07-06T08:13:06Z)
• Latent Augmentation For Better Graph Self-Supervised Learning [20.082614919182692]
  We argue that predictive models weaponed with latent augmentations and powerful decoder could achieve comparable or even better representation power than contrastive models. A novel graph decoder named Wiener Graph Deconvolutional Network is correspondingly designed to perform information reconstruction from augmented latent representations.
  arXiv  Detail & Related papers  (2022-06-26T17:41:59Z)
• What Dense Graph Do You Need for Self-Attention? [73.82686008622596]
  We present Hypercube Transformer, a sparse Transformer that models token interactions in a hypercube and shows comparable or even better results with vanilla Transformer. Experiments on tasks requiring various sequence lengths lay validation for our graph function well.
  arXiv  Detail & Related papers  (2022-05-27T14:36:55Z)
• Dynamic Graph Representation Learning via Graph Transformer Networks [41.570839291138114]
  We propose a Transformer-based dynamic graph learning method named Dynamic Graph Transformer (DGT) DGT has spatial-temporal encoding to effectively learn graph topology and capture implicit links. We show that DGT presents superior performance compared with several state-of-the-art baselines.
  arXiv  Detail & Related papers  (2021-11-19T21:44:23Z)
• Do Transformers Really Perform Bad for Graph Representation? [62.68420868623308]
  We present Graphormer, which is built upon the standard Transformer architecture. Our key insight to utilizing Transformer in the graph is the necessity of effectively encoding the structural information of a graph into the model.
  arXiv  Detail & Related papers  (2021-06-09T17:18:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.