k-Maximum Inner Product Attention for Graph Transformers and the Expressive Power of GraphGPS
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 o...
| Authors | Jonas De Schouwer, Haitz Sáez de Ocáriz Borde, Xiaowen Dong |
|---|---|
| Primary category | cs.LG |
| Published | 4 April 2026 |
| Last updated at source | 7 April 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.