Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910730339483648 |
|---|---|
| author | Choromanski, Krzysztof Sehanobish, Arijit Chowdhury, Somnath Basu Roy Lin, Han Dubey, Avinava Sarlos, Tamas Chaturvedi, Snigdha |
| author_facet | Choromanski, Krzysztof Sehanobish, Arijit Chowdhury, Somnath Basu Roy Lin, Han Dubey, Avinava Sarlos, Tamas Chaturvedi, Snigdha |
| contents | 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 the resulting fast tree-field integrators (FTFIs) are presented, including (a) approximation of graph metrics with tree metrics, (b) graph classification, (c) modeling on meshes, and finally (d) Topological Transformers (TTs) (Choromanski et al., 2022) for images. For Topological Transformers, we propose new relative position encoding (RPE) masking mechanisms with as few as three extra learnable parameters per Transformer layer, leading to 1.0-1.5%+ accuracy gains. Importantly, most of FTFIs are exact methods, thus numerically equivalent to their brute-force counterparts. When applied to graphs with thousands of nodes, those exact algorithms provide 5.7-13x speedups. We also provide an extensive theoretical analysis of our methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_15881 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers Choromanski, Krzysztof Sehanobish, Arijit Chowdhury, Somnath Basu Roy Lin, Han Dubey, Avinava Sarlos, Tamas Chaturvedi, Snigdha Machine Learning Artificial Intelligence 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 the resulting fast tree-field integrators (FTFIs) are presented, including (a) approximation of graph metrics with tree metrics, (b) graph classification, (c) modeling on meshes, and finally (d) Topological Transformers (TTs) (Choromanski et al., 2022) for images. For Topological Transformers, we propose new relative position encoding (RPE) masking mechanisms with as few as three extra learnable parameters per Transformer layer, leading to 1.0-1.5%+ accuracy gains. Importantly, most of FTFIs are exact methods, thus numerically equivalent to their brute-force counterparts. When applied to graphs with thousands of nodes, those exact algorithms provide 5.7-13x speedups. We also provide an extensive theoretical analysis of our methods. |
| title | Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2406.15881 |