SGFormer: Single-Layer Graph Transformers with Approximation-Free Linear Complexity

• URL: http://arxiv.org/abs/2409.09007v1
• Date: Fri, 13 Sep 2024 17:37:34 GMT
• Title: SGFormer: Single-Layer Graph Transformers with Approximation-Free Linear Complexity
• Authors: Qitian Wu, Kai Yang, Hengrui Zhang, David Wipf, Junchi Yan,
• Abstract summary: 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.
• Score: 74.51827323742506
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning representations on large graphs is a long-standing challenge due to the inter-dependence nature. Transformers recently have shown promising performance on small graphs thanks to its global attention for capturing all-pair interactions beyond observed structures. Existing approaches tend to inherit the spirit of Transformers in language and vision tasks, and embrace complicated architectures by stacking deep attention-based propagation layers. In this paper, we attempt to evaluate the necessity of adopting multi-layer attentions in Transformers on graphs, which considerably restricts the efficiency. Specifically, we analyze a generic hybrid propagation layer, comprised of all-pair attention and graph-based propagation, and show that multi-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, particularly through simplifying model architectures without sacrificing expressiveness. As exemplified by this work, we propose a Simplified Single-layer Graph Transformers (SGFormer), whose main component is a single-layer global attention that scales linearly w.r.t. graph sizes and requires none of any approximation for accommodating all-pair interactions. Empirically, SGFormer successfully scales to the web-scale graph ogbn-papers100M, yielding orders-of-magnitude inference acceleration over peer Transformers on medium-sized graphs, and demonstrates competitiveness with limited labeled data.

Related papers

• Graph Transformers for Large Graphs [57.19338459218758]
  This work advances representation learning on single large-scale graphs with a focus on identifying model characteristics and critical design constraints. A key innovation of this work lies in the creation of a fast neighborhood sampling technique coupled with a local attention mechanism. We report a 3x speedup and 16.8% performance gain on ogbn-products and snap-patents, while we also scale LargeGT on ogbn-100M with a 5.9% performance improvement.
  arXiv  Detail & Related papers  (2023-12-18T11:19:23Z)
• 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)
• Curve Your Attention: Mixed-Curvature Transformers for Graph Representation Learning [77.1421343649344]
  We propose a generalization of Transformers towards operating entirely on the product of constant curvature spaces. We also provide a kernelized approach to non-Euclidean attention, which enables our model to run in time and memory cost linear to the number of nodes and edges.
  arXiv  Detail & Related papers  (2023-09-08T02:44:37Z)
• SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations [75.71298846760303]
  We show that a one-layer attention can bring up surprisingly competitive performance across node property prediction benchmarks. We frame the proposed scheme as Simplified Graph Transformers (SGFormer), which is empowered by a simple attention model. We believe the proposed methodology alone enlightens a new technical path of independent interest for building Transformers on large graphs.
  arXiv  Detail & Related papers  (2023-06-19T08:03:25Z)
• 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)
• Hierarchical Graph Transformer with Adaptive Node Sampling [19.45896788055167]
  We identify the main deficiencies of current graph transformers. Most sampling strategies only focus on local neighbors and neglect the long-range dependencies in the graph. We propose a hierarchical attention scheme with graph coarsening to capture the long-range interactions.
  arXiv  Detail & Related papers  (2022-10-08T05:53:25Z)
• Graph Reasoning Transformer for Image Parsing [67.76633142645284]
  We propose a novel Graph Reasoning Transformer (GReaT) for image parsing to enable image patches to interact following a relation reasoning pattern. Compared to the conventional transformer, GReaT has higher interaction efficiency and a more purposeful interaction pattern. Results show that GReaT achieves consistent performance gains with slight computational overheads on the state-of-the-art transformer baselines.
  arXiv  Detail & Related papers  (2022-09-20T08:21:37Z)
• 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)
• Gophormer: Ego-Graph Transformer for Node Classification [27.491500255498845]
  In this paper, we propose a novel Gophormer model which applies transformers on ego-graphs instead of full-graphs. Specifically, Node2Seq module is proposed to sample ego-graphs as the input of transformers, which alleviates the challenge of scalability. In order to handle the uncertainty introduced by the ego-graph sampling, we propose a consistency regularization and a multi-sample inference strategy.
  arXiv  Detail & Related papers  (2021-10-25T16:43:32Z)

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.