k-Maximum Inner Product Attention for Graph Transformers and the Expressive Power of GraphGPS

• URL: http://arxiv.org/abs/2604.03815v2
• Date: Tue, 07 Apr 2026 19:22:13 GMT
• Title: k-Maximum Inner Product Attention for Graph Transformers and the Expressive Power of GraphGPS
• Abstract summary: We introduce k-MIP attention for graph transformers, which selects the most relevant key nodes per query via a top-k operation.<n>This results in linear memory complexity and practical speedups of up to an order of magnitude compared to all-to-all attention.<n>We prove that k-MIP transformers can approximate any full-attention transformer to arbitrary precision.
• Score: 12.688538382869659
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph transformers have shown promise in overcoming limitations of traditional graph neural networks, such as oversquashing and difficulties in modeling long-range dependencies. However, their application to large-scale graphs is hindered by the quadratic memory and computational complexity of the all-to-all attention mechanism. Although alternatives such as linearized attention and restricted attention patterns have been proposed, these often degrade performance or limit expressive power. To better balance efficiency and effectiveness, we introduce k-Maximum Inner Product (k-MIP) attention for graph transformers. k-MIP attention selects the most relevant key nodes per query via a top-k operation, yielding a sparse yet flexible attention pattern. Combined with an attention score computation based on symbolic matrices, this results in linear memory complexity and practical speedups of up to an order of magnitude compared to all-to-all attention, enabling the processing of graphs with over 500k nodes on a single A100 GPU. We provide a theoretical analysis of expressive power, showing that k-MIP attention does not compromise the expressiveness of graph transformers: specifically, we prove that k-MIP transformers can approximate any full-attention transformer to arbitrary precision. In addition, we analyze the expressive power of the GraphGPS framework, in which we integrate our attention mechanism, and establish an upper bound on its graph distinguishing capability in terms of the S-SEG-WL test. Finally, we validate our approach on the Long Range Graph Benchmark, the City-Networks benchmark, and two custom large-scale inductive point cloud datasets, consistently ranking among the top-performing scalable graph transformers.

Related papers

• VecFormer: Towards Efficient and Generalizable Graph Transformer with Graph Token Attention [61.96837866507746]
  VecFormer is an efficient and highly generalizable model for node classification.<n>VecFormer outperforms the existing Graph Transformer in both performance and speed.
  arXiv  Detail & Related papers  (2026-02-23T09:10:39Z)
• HopFormer: Sparse Graph Transformers with Explicit Receptive Field Control [7.178718630094309]
  We introduce HopFormer, a graph Transformer that injects structure exclusively through head-specific n-hop masked sparse attention.<n>We show that our approach achieves competitive or superior performance across diverse graph structures.
  arXiv  Detail & Related papers  (2026-02-02T16:09:58Z)
• Plain Transformers are Surprisingly Powerful Link Predictors [57.01966734467712]
  Link prediction is a core challenge in graph machine learning, demanding models that capture rich and complex topological dependencies.<n>While Graph Neural Networks (GNNs) are the standard solution, state-of-the-art pipelines often rely on explicit structurals or memory-intensive node embeddings.<n>We present PENCIL, an encoder-only plain Transformer that replaces hand-crafted priors with attention over sampled local subgraphs.
  arXiv  Detail & Related papers  (2026-02-02T02:45:52Z)
• 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)
• Masked Graph Transformer for Large-Scale Recommendation [56.37903431721977]
  We propose an efficient Masked Graph Transformer, named MGFormer, capable of capturing all-pair interactions among nodes with a linear complexity. Experimental results show the superior performance of our MGFormer, even with a single attention layer.
  arXiv  Detail & Related papers  (2024-05-07T06:00:47Z)
• An end-to-end attention-based approach for learning on graphs [8.552020965470113]
  transformer-based architectures for learning on graphs are motivated by attention as an effective learning mechanism.<n>We propose a purely attention-based approach consisting of an encoder and an attention pooling mechanism.<n>Despite its simplicity, the approach outperforms fine-tuned message passing baselines and recently proposed transformer-based methods on more than 70 node and graph-level tasks.
  arXiv  Detail & Related papers  (2024-02-16T16:20:11Z)
• Key-Graph Transformer for Image Restoration [122.7334034968327]
  We introduce the Key-Graph Transformer (KGT) in this paper. Specifically, KGT views patch features as graph nodes. The proposed Key-Graph Constructor efficiently forms a sparse yet representative Key-Graph by selectively connecting essential nodes instead of all the nodes.
  arXiv  Detail & Related papers  (2024-02-04T23:00:24Z)
• Graph Transformers without Positional Encodings [0.7252027234425334]
  We introduce Eigenformer, a Graph Transformer employing a novel spectrum-aware attention mechanism cognizant of the Laplacian spectrum of the graph. We empirically show that it achieves performance competetive with SOTA Graph Transformers on a number of standard GNN benchmarks.
  arXiv  Detail & Related papers  (2024-01-31T12:33:31Z)
• 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)
• Rethinking Graph Transformers with Spectral Attention [13.068288784805901]
  We present the $textitSpectral Attention Network$ (SAN), which uses a learned positional encoding (LPE) to learn the position of each node in a given graph. By leveraging the full spectrum of the Laplacian, our model is theoretically powerful in distinguishing graphs, and can better detect similar sub-structures from their resonance. Our model performs on par or better than state-of-the-art GNNs, and outperforms any attention-based model by a wide margin.
  arXiv  Detail & Related papers  (2021-06-07T18:11:11Z)

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.