# Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers

arXiv: https://arxiv.org/abs/2406.15881 · HTML: https://mlsanity.com/paper/2406.15881/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 85 references that are in the map.
- First posted on arXiv 22 Jun 2024.

## Builds on (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [The Kinetics Human Action Video Dataset](https://mlsanity.com/paper/1705.06950/) (2017)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Learning Mesh-Based Simulation with Graph Networks](https://mlsanity.com/paper/2010.03409/) (2020)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [What is the State of Neural Network Pruning?](https://mlsanity.com/paper/2003.03033/) (2020)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Thingi10K: A Dataset of 10,000 3D-Printing Models](https://mlsanity.com/paper/1605.04797/) (2016)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding](https://mlsanity.com/paper/2106.12566/) (2021)
- [Graph Kernels: A Survey](https://mlsanity.com/paper/1904.12218/) (2019)
- [Structured Transforms for Small-Footprint Deep Learning](https://mlsanity.com/paper/1510.01722/) (2015)
- [From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers](https://mlsanity.com/paper/2107.07999/) (2021)
- [Quantitative Stability of Regularized Optimal Transport and Convergence of Sinkhorn's Algorithm](https://mlsanity.com/paper/2110.06798/) (2021)
- [Learning Compressed Transforms with Low Displacement Rank](https://mlsanity.com/paper/1810.02309/) (2018)
- [A Simple Baseline Algorithm for Graph Classification](https://mlsanity.com/paper/1810.09155/) (2018)
- [SparseDNN: Fast Sparse Deep Learning Inference on CPUs](https://mlsanity.com/paper/2101.07948/) (2021)
- [k-server via multiscale entropic regularization](https://mlsanity.com/paper/1711.01085/) (2017)
- [A Survey of Multi-Tenant Deep Learning Inference on GPU](https://mlsanity.com/paper/2203.09040/) (2022)
- [Efficient Graph Field Integrators Meet Point Clouds](https://mlsanity.com/paper/2302.00942/) (2023)
- [Covering Metric Spaces by Few Trees](https://mlsanity.com/paper/1905.07559/) (2019)
- [Towards Latency-aware DNN Optimization with GPU Runtime Analysis and Tail Effect Elimination](https://mlsanity.com/paper/2011.03897/) (2020)
- [On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion](https://mlsanity.com/paper/1609.08801/) (2016)
- [Computing the inverse geodesic length in planar graphs and graphs of bounded treewidth](https://mlsanity.com/paper/1908.01317/) (2019)
- [Sparsifying the Operators of Fast Matrix Multiplication Algorithms](https://mlsanity.com/paper/2008.03759/) (2020)

## Built on by (most cited first, 3 of 3)

- [Computationally-efficient Graph Modeling with Refined Graph Random Features](https://mlsanity.com/paper/2510.07716/) (2025)
- [Neural-HSS: Hierarchical Semi-Separable Neural PDE Solver](https://mlsanity.com/paper/2602.18248/) (2026)
- [RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodings](https://mlsanity.com/paper/2605.10706/) (2026)

## Abstract (arXiv)

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.