Linear Transformer Topological Masking with Graph Random Features
When training transformers on graph-structured data, incorporating information about the underlying topology is crucial for good performance. Topological masking, a type of relative position encoding, achieves this by upweighting or downweighting attention depending on the relationship between the query and keys in a graph. In this paper, we propose to parameterise topological masks as a learnable function of a weighted adjacency matrix -- a novel, flexible approach which incorporates a strong structural inductive bias. By approximating this mask with graph random features (for which we prove the first known concentration bounds), we show how this can be made fully compatible with linear attention, preserving $\mathcal{O}(N)$ time and space complexity with respect to the number of input tokens. The fastest previous alternative was $\mathcal{O}(N \log N)$ and only suitable for specific graphs. Our efficient masking algorithms provide strong performance gains for tasks on image and point cloud data, including with $>30$k nodes.
Code (0)
등록된 구현이 없습니다.
Tasks
Inductive BiasMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers
In this paper we provide, to the best of our knowledge, the first comprehensive approach for incorporating various masking mechanisms into Transformers architectures in a scalable way. We show that recent results on line…
Graph AttentionFast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers
We present a new class of fast polylog-linear algorithms based on the theory of structured matrices (in particular low displacement rank) for integrating tensor fields defined on weighted trees. Several applications of t…
Graph ClassificationWhat Structural Inductive Bias Helps Transformers Reason Over Knowledge Graphs? A Study with Tabula RASA
What structural inductive bias helps transformers reason over knowledge graphs? Through controlled ablations of a minimal transformer modification with four independently removable components (sparse adjacency masking, e…
Knowledge GraphsOn the Trainability of Masked Diffusion Language Models via Blockwise Locality
Masked diffusion language models (MDMs) have recently emerged as a promising alternative to standard autoregressive large language models (AR-LLMs), yet their optimization can be substantially less stable. We study block…
What to Hide from Your Students: Attention-Guided Masked Image Modeling
Transformers and masked language modeling are quickly being adopted and explored in computer vision as vision transformers and masked image modeling (MIM). In this work, we argue that image token masking differs from tok…
Language ModelingLanguage ModellingMasked Language ModelingSelf-Supervised Learning