Linear Transformer Topological Masking with Graph Random Features Article Swipe

PDF

Isaac Reid , Kumar Avinava Dubey , Deepali Jain , Will Whitney , Amr Ahmed , Joshua Ainslie , Alex Bewley , Mithun George Jacob , Aranyak Mehta , David Rendleman , Connor Schenck , Richard E. Turner , René Wagner , Adrian Weller , Krzysztof Choromański ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2410.03462

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.

Related Topics

Concepts

Transformer Masking (illustration) Topology (electrical circuits) Mathematics Graph Computer science Discrete mathematics Combinatorics Physics Voltage Quantum mechanics Visual arts Art

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2410.03462
PDF: https://arxiv.org/pdf/2410.03462
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4403572216

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4403572216

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2410.03462

Digital Object Identifier
Title: Linear Transformer Topological Masking with Graph Random Features

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-10-04

Full publication date if available
Authors: Isaac Reid, Kumar Avinava Dubey, Deepali Jain, Will Whitney, Amr Ahmed, Joshua Ainslie, Alex Bewley, Mithun George Jacob, Aranyak Mehta, David Rendleman, Connor Schenck, Richard E. Turner, René Wagner, Adrian Weller, Krzysztof Choromański

List of authors in order
Landing page: https://arxiv.org/abs/2410.03462

Publisher landing page
PDF URL: https://arxiv.org/pdf/2410.03462

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2410.03462

Direct OA link when available
Concepts: Transformer, Masking (illustration), Topology (electrical circuits), Mathematics, Graph, Computer science, Discrete mathematics, Combinatorics, Physics, Voltage, Quantum mechanics, Visual arts, Art

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4403572216
doi	https://doi.org/10.48550/arxiv.2410.03462
ids.doi	https://doi.org/10.48550/arxiv.2410.03462
ids.openalex	https://openalex.org/W4403572216
fwci
type	preprint
title	Linear Transformer Topological Masking with Graph Random Features
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10824
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9236999750137329
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1707
topics[0].subfield.display_name	Computer Vision and Pattern Recognition
topics[0].display_name	Image Retrieval and Classification Techniques
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C66322947
concepts[0].level	3
concepts[0].score	0.5331973433494568
concepts[0].wikidata	https://www.wikidata.org/wiki/Q11658
concepts[0].display_name	Transformer
concepts[1].id	https://openalex.org/C2777402240
concepts[1].level	2
concepts[1].score	0.511681318283081
concepts[1].wikidata	https://www.wikidata.org/wiki/Q6783436
concepts[1].display_name	Masking (illustration)
concepts[2].id	https://openalex.org/C184720557
concepts[2].level	2
concepts[2].score	0.505226194858551
concepts[2].wikidata	https://www.wikidata.org/wiki/Q7825049
concepts[2].display_name	Topology (electrical circuits)
concepts[3].id	https://openalex.org/C33923547
concepts[3].level	0
concepts[3].score	0.4507635831832886
concepts[3].wikidata	https://www.wikidata.org/wiki/Q395
concepts[3].display_name	Mathematics
concepts[4].id	https://openalex.org/C132525143
concepts[4].level	2
concepts[4].score	0.41525357961654663
concepts[4].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[4].display_name	Graph
concepts[5].id	https://openalex.org/C41008148
concepts[5].level	0
concepts[5].score	0.35448700189590454
concepts[5].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[5].display_name	Computer science
concepts[6].id	https://openalex.org/C118615104
concepts[6].level	1
concepts[6].score	0.26976722478866577
concepts[6].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[6].display_name	Discrete mathematics
concepts[7].id	https://openalex.org/C114614502
concepts[7].level	1
concepts[7].score	0.2682809829711914
concepts[7].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[7].display_name	Combinatorics
concepts[8].id	https://openalex.org/C121332964
concepts[8].level	0
concepts[8].score	0.2645871043205261
concepts[8].wikidata	https://www.wikidata.org/wiki/Q413
concepts[8].display_name	Physics
concepts[9].id	https://openalex.org/C165801399
concepts[9].level	2
concepts[9].score	0.1003735363483429
concepts[9].wikidata	https://www.wikidata.org/wiki/Q25428
concepts[9].display_name	Voltage
concepts[10].id	https://openalex.org/C62520636
concepts[10].level	1
concepts[10].score	0.05661937594413757
concepts[10].wikidata	https://www.wikidata.org/wiki/Q944
concepts[10].display_name	Quantum mechanics
concepts[11].id	https://openalex.org/C153349607
concepts[11].level	1
concepts[11].score	0.0
concepts[11].wikidata	https://www.wikidata.org/wiki/Q36649
concepts[11].display_name	Visual arts
concepts[12].id	https://openalex.org/C142362112
concepts[12].level	0
concepts[12].score	0.0
concepts[12].wikidata	https://www.wikidata.org/wiki/Q735
concepts[12].display_name	Art
keywords[0].id	https://openalex.org/keywords/transformer
keywords[0].score	0.5331973433494568
keywords[0].display_name	Transformer
keywords[1].id	https://openalex.org/keywords/masking
keywords[1].score	0.511681318283081
keywords[1].display_name	Masking (illustration)
keywords[2].id	https://openalex.org/keywords/topology
keywords[2].score	0.505226194858551
keywords[2].display_name	Topology (electrical circuits)
keywords[3].id	https://openalex.org/keywords/mathematics
keywords[3].score	0.4507635831832886
keywords[3].display_name	Mathematics
keywords[4].id	https://openalex.org/keywords/graph
keywords[4].score	0.41525357961654663
keywords[4].display_name	Graph
keywords[5].id	https://openalex.org/keywords/computer-science
keywords[5].score	0.35448700189590454
keywords[5].display_name	Computer science
keywords[6].id	https://openalex.org/keywords/discrete-mathematics
keywords[6].score	0.26976722478866577
keywords[6].display_name	Discrete mathematics
keywords[7].id	https://openalex.org/keywords/combinatorics
keywords[7].score	0.2682809829711914
keywords[7].display_name	Combinatorics
keywords[8].id	https://openalex.org/keywords/physics
keywords[8].score	0.2645871043205261
keywords[8].display_name	Physics
keywords[9].id	https://openalex.org/keywords/voltage
keywords[9].score	0.1003735363483429
keywords[9].display_name	Voltage
keywords[10].id	https://openalex.org/keywords/quantum-mechanics
keywords[10].score	0.05661937594413757
keywords[10].display_name	Quantum mechanics
language	en
locations[0].id	pmh:oai:arXiv.org:2410.03462
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2410.03462
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2410.03462
locations[1].id	doi:10.48550/arxiv.2410.03462
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2410.03462
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5089700738
authorships[0].author.orcid
authorships[0].author.display_name	Isaac Reid
authorships[0].author_position	first
authorships[0].raw_author_name	Reid, Isaac
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5042341289
authorships[1].author.orcid
authorships[1].author.display_name	Kumar Avinava Dubey
authorships[1].author_position	middle
authorships[1].raw_author_name	Dubey, Kumar Avinava
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5016687983
authorships[2].author.orcid	https://orcid.org/0000-0001-5315-9814
authorships[2].author.display_name	Deepali Jain
authorships[2].author_position	middle
authorships[2].raw_author_name	Jain, Deepali
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5114335671
authorships[3].author.orcid
authorships[3].author.display_name	Will Whitney
authorships[3].author_position	middle
authorships[3].raw_author_name	Whitney, Will
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5009154893
authorships[4].author.orcid	https://orcid.org/0000-0002-7749-7911
authorships[4].author.display_name	Amr Ahmed
authorships[4].author_position	middle
authorships[4].raw_author_name	Ahmed, Amr
authorships[4].is_corresponding	False
authorships[5].author.id	https://openalex.org/A5072605113
authorships[5].author.orcid
authorships[5].author.display_name	Joshua Ainslie
authorships[5].author_position	middle
authorships[5].raw_author_name	Ainslie, Joshua
authorships[5].is_corresponding	False
authorships[6].author.id	https://openalex.org/A5043765267
authorships[6].author.orcid	https://orcid.org/0000-0002-8428-9264
authorships[6].author.display_name	Alex Bewley
authorships[6].author_position	middle
authorships[6].raw_author_name	Bewley, Alex
authorships[6].is_corresponding	False
authorships[7].author.id	https://openalex.org/A5059566769
authorships[7].author.orcid
authorships[7].author.display_name	Mithun George Jacob
authorships[7].author_position	middle
authorships[7].raw_author_name	Jacob, Mithun
authorships[7].is_corresponding	False
authorships[8].author.id	https://openalex.org/A5075894805
authorships[8].author.orcid	https://orcid.org/0000-0002-6132-4901
authorships[8].author.display_name	Aranyak Mehta
authorships[8].author_position	middle
authorships[8].raw_author_name	Mehta, Aranyak
authorships[8].is_corresponding	False
authorships[9].author.id	https://openalex.org/A5091963000
authorships[9].author.orcid
authorships[9].author.display_name	David Rendleman
authorships[9].author_position	middle
authorships[9].raw_author_name	Rendleman, David
authorships[9].is_corresponding	False
authorships[10].author.id	https://openalex.org/A5004337298
authorships[10].author.orcid
authorships[10].author.display_name	Connor Schenck
authorships[10].author_position	middle
authorships[10].raw_author_name	Schenck, Connor
authorships[10].is_corresponding	False
authorships[11].author.id	https://openalex.org/A5108284020
authorships[11].author.orcid	https://orcid.org/0000-0003-0066-0984
authorships[11].author.display_name	Richard E. Turner
authorships[11].author_position	middle
authorships[11].raw_author_name	Turner, Richard E.
authorships[11].is_corresponding	False
authorships[12].author.id	https://openalex.org/A5108403016
authorships[12].author.orcid
authorships[12].author.display_name	René Wagner
authorships[12].author_position	middle
authorships[12].raw_author_name	Wagner, René
authorships[12].is_corresponding	False
authorships[13].author.id	https://openalex.org/A5042278493
authorships[13].author.orcid	https://orcid.org/0000-0003-1915-7158
authorships[13].author.display_name	Adrian Weller
authorships[13].author_position	middle
authorships[13].raw_author_name	Weller, Adrian
authorships[13].is_corresponding	False
authorships[14].author.id	https://openalex.org/A5031842812
authorships[14].author.orcid	https://orcid.org/0000-0003-3626-414X
authorships[14].author.display_name	Krzysztof Choromański
authorships[14].author_position	last
authorships[14].raw_author_name	Choromanski, Krzysztof
authorships[14].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2410.03462
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Linear Transformer Topological Masking with Graph Random Features
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10824
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9236999750137329
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1707
primary_topic.subfield.display_name	Computer Vision and Pattern Recognition
primary_topic.display_name	Image Retrieval and Classification Techniques
related_works	https://openalex.org/W4391375266, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596, https://openalex.org/W2072657027, https://openalex.org/W2600246793, https://openalex.org/W4238204885
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2410.03462
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2410.03462
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2410.03462
primary_location.id	pmh:oai:arXiv.org:2410.03462
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2410.03462
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2410.03462
publication_date	2024-10-04
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	19, 42, 54, 58, 63, 69
abstract_inverted_index.--	62
abstract_inverted_index.By	74
abstract_inverted_index.In	44
abstract_inverted_index.as	53
abstract_inverted_index.be	96
abstract_inverted_index.by	27
abstract_inverted_index.in	41
abstract_inverted_index.is	12
abstract_inverted_index.of	21, 57, 114
abstract_inverted_index.on	3, 33, 141
abstract_inverted_index.or	29
abstract_inverted_index.to	49, 111
abstract_inverted_index.we	47, 84, 91
abstract_inverted_index.N)$	124
abstract_inverted_index.Our	131
abstract_inverted_index.The	117
abstract_inverted_index.and	39, 106, 125, 143
abstract_inverted_index.can	95
abstract_inverted_index.for	14, 128, 139
abstract_inverted_index.how	93
abstract_inverted_index.the	9, 34, 37, 86, 112
abstract_inverted_index.was	121
abstract_inverted_index.(for	82
abstract_inverted_index.When	0
abstract_inverted_index.\log	123
abstract_inverted_index.good	15
abstract_inverted_index.keys	40
abstract_inverted_index.made	97
abstract_inverted_index.mask	77
abstract_inverted_index.only	126
abstract_inverted_index.show	92
abstract_inverted_index.this	26, 45, 76, 94
abstract_inverted_index.time	105
abstract_inverted_index.type	20
abstract_inverted_index.with	78, 100, 109, 148
abstract_inverted_index.about	8
abstract_inverted_index.bias.	73
abstract_inverted_index.cloud	145
abstract_inverted_index.data,	5, 146
abstract_inverted_index.first	87
abstract_inverted_index.fully	98
abstract_inverted_index.gains	138
abstract_inverted_index.graph	79
abstract_inverted_index.image	142
abstract_inverted_index.input	115
abstract_inverted_index.known	88
abstract_inverted_index.masks	52
abstract_inverted_index.point	144
abstract_inverted_index.prove	85
abstract_inverted_index.query	38
abstract_inverted_index.space	107
abstract_inverted_index.tasks	140
abstract_inverted_index.which	67, 83
abstract_inverted_index.graph.	43
abstract_inverted_index.linear	101
abstract_inverted_index.matrix	61
abstract_inverted_index.nodes.	150
abstract_inverted_index.novel,	64
abstract_inverted_index.number	113
abstract_inverted_index.paper,	46
abstract_inverted_index.random	80
abstract_inverted_index.strong	70, 136
abstract_inverted_index.between	36
abstract_inverted_index.crucial	13
abstract_inverted_index.fastest	118
abstract_inverted_index.graphs.	130
abstract_inverted_index.masking	133
abstract_inverted_index.propose	48
abstract_inverted_index.provide	135
abstract_inverted_index.respect	110
abstract_inverted_index.tokens.	116
abstract_inverted_index.achieves	25
abstract_inverted_index.approach	66
abstract_inverted_index.bounds),	90
abstract_inverted_index.features	81
abstract_inverted_index.flexible	65
abstract_inverted_index.function	56
abstract_inverted_index.masking,	18
abstract_inverted_index.position	23
abstract_inverted_index.previous	119
abstract_inverted_index.relative	22
abstract_inverted_index.specific	129
abstract_inverted_index.suitable	127
abstract_inverted_index.topology	11
abstract_inverted_index.training	1
abstract_inverted_index.weighted	59
abstract_inverted_index.$>30$k	149
abstract_inverted_index.adjacency	60
abstract_inverted_index.attention	31
abstract_inverted_index.depending	32
abstract_inverted_index.efficient	132
abstract_inverted_index.encoding,	24
abstract_inverted_index.including	147
abstract_inverted_index.inductive	72
abstract_inverted_index.learnable	55
abstract_inverted_index.algorithms	134
abstract_inverted_index.attention,	102
abstract_inverted_index.compatible	99
abstract_inverted_index.complexity	108
abstract_inverted_index.preserving	103
abstract_inverted_index.structural	71
abstract_inverted_index.underlying	10
abstract_inverted_index.Topological	17
abstract_inverted_index.alternative	120
abstract_inverted_index.information	7
abstract_inverted_index.performance	137
abstract_inverted_index.topological	51
abstract_inverted_index.upweighting	28
abstract_inverted_index.incorporates	68
abstract_inverted_index.parameterise	50
abstract_inverted_index.performance.	16
abstract_inverted_index.relationship	35
abstract_inverted_index.transformers	2
abstract_inverted_index.approximating	75
abstract_inverted_index.concentration	89
abstract_inverted_index.downweighting	30
abstract_inverted_index.incorporating	6
abstract_inverted_index.$\mathcal{O}(N	122
abstract_inverted_index.$\mathcal{O}(N)$	104
abstract_inverted_index.graph-structured	4
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	15
citation_normalized_percentile