k-Maximum Inner Product Attention for Graph Transformers and the Expressive Power of GraphGPS
Jonas De Schouwer, Haitz Sáez de Ocáriz Borde, Xiaowen Dong · 2026
Read k-Maximum Inner Product Attention for Graph Transformers and the Expressive Power of GraphGPS by Jonas De Schouwer, Haitz Sáez de Ocáriz Borde, Xiaowen Dong (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-03815.txt.
Introduction
Jonas De Schouwer and colleagues built k-Maximum Inner Product attention, a sparse attention pattern for graph transformers that picks only the top-k keys per query. Full attention costs quadratic memory, while linearized and restricted variants often lose power. Their design runs in linear memory, speeds up work by up to an order of magnitude, and handles graphs over 500,000 nodes on one A100 GPU. Theory shows it can approximate full attention arbitrarily well.
Catalog record
| CREATOR | Jonas De Schouwer, Haitz Sáez de Ocáriz Borde, Xiaowen Dong |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 117172 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.03815
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
k-Maximum Inner Product Attention for Graph Transformers and the Expressive Power of GraphGPS Jonas De Schouwer, Haitz Sáez de Ocáriz Borde, Xiaowen Dong Abstract Graph transformers have shown promise in overcoming limitations of traditional graph neural networks, such as oversquashing and difficulties in modelling 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. 1 Introduction Since the advent of the original Graph Neural Network (GNN) model ( 53 ) , graph machine learning has become a powerful tool for analyzing relational data across domains ranging from social networks ( 7 ; 23 ) to molecular biology ( 33 ; 26 ) and recommendation systems ( 30 ; 68 ) , and has become a cornerstone of Geometric Deep Learning ( 10 ; 9 ) . Traditional approaches typically follow the message-passing paradigm, where information is propagated locally between neighbouring nodes. Despite its effectiveness, this paradigm has certain shortcomings such as oversmoothing ( 40 ) , oversquashing ( 2 ) and limited expressive power ( 48 ; 73 ; 45 ) , all of which may lead to difficulties in capturing long-range dependencies ( 1 ) . Graph transformers have recently emerged as a promising alternative ( 75 ; 18 ; 49 ) , enabling information exchange between every pair of nodes. However, this comes at the cost of quadratic complexity, and it remains an open question how to adapt the Transformer architecture ( 62 ) to scale effectively to large graphs with potentially millions of nodes. In this paper we propose the k-Maximum Inner Product (k-MIP) self-attention mechanism for graph transformers. k-MIP attention dynamically selects the k most influential keys for each query based on the intermediate activations, achieving scalability while avoiding the drawbacks of linearisation, rigid attention patterns and graph subsampling, which we discuss in Section 2.2 . The main contributions of this paper are the following. • We introduce k-Maximum Inner Product (k-MIP) self-attention for graph transformers, which achieves linear memory complexity and yields up to a ten-fold speedup over full attention 1 1 1 In our implementation; performance depends on the KeOps backend and GPU memory regime. . As a result, k-MIP attention enables the processing of graphs with over 500k nodes on a single A100 GPU. • We show that k-MIP attention can be seamlessly integrated into the GraphGPS framework and provide a theoretical analysis of its expressive power, establishing an upper bound on the graph-distinguishing capability of GraphGPS in terms of the S-SEG-WL test ( 83 ) . This analysis clarifies how positional and structural encodings enable expressivity in graph transformers. • We prove that k-MIP transformers can approximate any full-attention transformer to arbitrary precision, thereby guaranteeing that the proposed sparsification does not reduce the expressive power of transformer-based architectures. • We empirically demonstrate competitive performance against other scalable graph transformers on a range of benchmarks, including the Long Range Graph Benchmark (LRGB) ( 21 ) , the City-Networks benchmark ( 41 ) , and two custom large-scale inductive point cloud datasets based on ShapeNet-Part ( 74 ) and S3DIS ( 3 ) . 2 Related work This section provides background on the k-MIP attention mechanism and surveys related work on scalable graph transformers. An extended discussion can be found in Appendix G . 2.1 k-Maximum inner product attention The attention mechanism used in this paper was first introduced by 80 in the context of natural language processing, revisited by 29 , and later applied to computer vision by 66 . While these works demonstrated the mechanism’s effectiveness in their respective domains, their methods suffered from quadratic memory complexity, rendering them unsuitable for direct adaptation to large graph datasets. To handle the substantially larger scale of the benchmarks considered in this work, we enhance the k-MIP attention mechanism through the use of symbolic matrices ( 12 ) , similar to previous work in latent graph inference ( 34 ; 5 ; 4 ) (see Appendix F for more details). This optimization achieves linear memory complexity and accelerates computation by an order of magnitude compared to full attention. Although the computational complexity remains quadratic, it nevertheless enables processing of graphs with over 500k nodes, as in City-Networks ( 41 ) , on a single A100 GPU. Furthermore, we provide a novel theoretical exploration of its expressive power in section 4 . We also note that other approximate variants of k-MIP attention have recently been proposed in the literature ( 79 ; 46 ) . 2.2 Graph transformers Inspired by the success of Transformers ( 62 ) in natural language modeling, substantial effort has been devoted to adapting this architecture to the graph domain ( 6 ) . Most graph transformers achieve this by treating graph nodes as tokens, since using edges and/or subgraphs as tokens would lead to a combinatorial explosion in the number of tokens for large graphs. Early graph transformers, such as Graphormer ( 75 ) and Graph Transformer ( 18 ) , demonstrated strong performance. However, they inherited the quadratic memory complexity of the Transformer, restricting their applicability to graphs with at most a few thousand nodes. To overcome this scalability hurdle, various approaches have been proposed since then, which can be broadly classified into four categories with examples provided in table 1 . (1) Graph subsampling approaches process only sampled portions of large graphs but are consequently unable to capture long-range dependencies. (2) Methods with engineered attention patterns restrict attention along predefined patterns, potentially missing out on important relationships between nodes. (3) Linearized attention methods approximate standard attention through kernel tricks or matrix factorization, achieving linear complexity but often at the cost of performance. (4) Methods with learnable attention patterns dynamically determine which node pairs are relevant for attention in order to focus computational resources on the most important connections. These approaches promise both efficiency gains and strong predictive performance, but remain relatively underexplored in the literature. Having established this categorization, we position k-MIP attention within the learnable patterns