Linear Transformer Topological Masking with Graph Random Features
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913546818813952 |
|---|---|
| author | Reid, Isaac Dubey, Kumar Avinava Jain, Deepali Whitney, Will Ahmed, Amr Ainslie, Joshua Bewley, Alex Jacob, Mithun Mehta, Aranyak Rendleman, David Schenck, Connor Turner, Richard E. Wagner, René Weller, Adrian Choromanski, Krzysztof |
| author_facet | Reid, Isaac Dubey, Kumar Avinava Jain, Deepali Whitney, Will Ahmed, Amr Ainslie, Joshua Bewley, Alex Jacob, Mithun Mehta, Aranyak Rendleman, David Schenck, Connor Turner, Richard E. Wagner, René Weller, Adrian Choromanski, Krzysztof |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_03462 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Linear Transformer Topological Masking with Graph Random Features Reid, Isaac Dubey, Kumar Avinava Jain, Deepali Whitney, Will Ahmed, Amr Ainslie, Joshua Bewley, Alex Jacob, Mithun Mehta, Aranyak Rendleman, David Schenck, Connor Turner, Richard E. Wagner, René Weller, Adrian Choromanski, Krzysztof Machine Learning 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. |
| title | Linear Transformer Topological Masking with Graph Random Features |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2410.03462 |