mlsanityData to 14 Oct 2026

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

arXiv 2406.15881 ↗First posted 22 Jun 2024cs.LG cs.AIcited by 3

Not on the map. Why?

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.

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

27 of 85 references.

References · 27

  1. 2017Attention Is All You Needcited by 60,361
  2. 2017The Kinetics Human Action Video Datasetcited by 1,909
  3. 2020Rethinking Attention with Performerscited by 1,601
  4. 2020Learning Mesh-Based Simulation with Graph Networkscited by 868
  5. 2018Computational Optimal Transportcited by 780
  6. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  7. 2020What is the State of Neural Network Pruning?cited by 583
  8. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  9. 2016Thingi10K: A Dataset of 10,000 3D-Printing Modelscited by 183
  10. 2019A Survey on Graph Kernelscited by 148
  11. 2018Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical propertiescited by 93
  12. 2021Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encodingcited by 51
15 more
  1. 2019Graph Kernels: A Surveycited by 44
  2. 2015Structured Transforms for Small-Footprint Deep Learningcited by 42
  3. 2021From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformerscited by 38
  4. 2021Quantitative Stability of Regularized Optimal Transport and Convergence of Sinkhorn's Algorithmcited by 22
  5. 2018Learning Compressed Transforms with Low Displacement Rankcited by 19
  6. 2018A Simple Baseline Algorithm for Graph Classificationcited by 15
  7. 2021SparseDNN: Fast Sparse Deep Learning Inference on CPUscited by 13
  8. 2017k-server via multiscale entropic regularizationcited by 7
  9. 2022A Survey of Multi-Tenant Deep Learning Inference on GPUcited by 7
  10. 2023Efficient Graph Field Integrators Meet Point Cloudscited by 7
  11. 2019Covering Metric Spaces by Few Treescited by 2
  12. 2020Towards Latency-aware DNN Optimization with GPU Runtime Analysis and Tail Effect Eliminationcited by 2
  13. 2016On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortioncited by 1
  14. 2019Computing the inverse geodesic length in planar graphs and graphs of bounded treewidthcited by 1
  15. 2020Sparsifying the Operators of Fast Matrix Multiplication Algorithmscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Computationally-efficient Graph Modeling with Refined Graph Random Featurescited by 2
  2. 2026Neural-HSS: Hierarchical Semi-Separable Neural PDE Solvercited by 1
  3. 2026RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodingscited by 1