@inproceedings{
choromanski2024fast,
title={Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers},
author={Krzysztof Marcin Choromanski and Arijit Sehanobish and Somnath Basu Roy Chowdhury and Han Lin and Kumar Avinava Dubey and Tamas Sarlos and Snigdha Chaturvedi},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=Eok6HbcSRI}
}
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.
Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers
Krzysztof Marcin Choromanski Arijit Sehanobish Somnath Basu Roy Chowdhury Han Lin Kumar Avinava Dubey Tamas Sarlos Snigdha Chaturvedi