Research map / Graph learning / Graph algorithms and clustering
Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes fast exact polylog-linear tree-field integrators (FTFIs) for f-distance matrices on weighted trees, applies them to graph metric approximation, graph classification, mesh interpolation, and learnable-mask Topological Vision Transformers.
Problem
Multiplying f-distance matrices (shortest-path kernel matrices with a function f applied) on graphs costs O(N^3) preprocessing and O(N^2) multiplication, which is prohibitive for large graphs used in graph ML, mesh interpolation, optimal transport and masked Transformers.
Approach
Use integrator trees (balanced-separator divide-and-conquer decomposition) of a weighted tree so that cross-term contributions reduce to structured (cordial, e.g. Cauchy-like, Vandermonde, Hankel) matrix-vector products, giving exact integration in polylog-linear time for classes of f; apply to MST of graphs and learn f as a rational function in tree-based masks for Transformers.</�core_idea>
Key results
- FTFI achieves up to 13x speedup over brute-force tree field integration on 20K-vertex meshes and 5.7x+ on synthetic graphs over 10K vertices.
- Topological ViT with exponentiated-quadratic-style learnable RPE mask reaches 78.79% top-1 on ImageNet with ViT-B/16 vs. 76.76% best Performer baseline, using three extra learnable parameters per layer in the synced setting.
- On graph classification, FTFI reduces feature processing time by 90% on Reddit-Binary (338.2s vs 3371.9s for BGFI) while matching accuracy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add tree-based FTFI masking with exp and t=1 | ViT-B/16 · ImageNet, ReLU attention kernel | accuracy (%): 76.23 -> 77.79 | Helped |
| Add tree-based FTFI masking with exp and t=1 | ViT-B/16 · ImageNet, x^2 attention kernel | accuracy (%): 75.03 -> 76.76 | Helped |
| Add tree-based FTFI masking with exp and t=2 | ViT-B/16 · ImageNet, x^4 attention kernel | accuracy (%): 76.37 -> 78.15 | Helped |
| Add tree-based FTFI masking with exp and t=1 | ViT-B/16 · ImageNet, exp attention kernel | accuracy (%): 76.76 -> 78.79 | Helped |
| Add tree-based FTFI masking with exp and t=1, synced | ViT-B/16 · Places365 | accuracy (%): 54.80 -> 56.69 | Helped |
| Replace explicit BGFI kernel computation with FTFI | Graph feature processing · IMDB Binary, IMDB Multi, Reddit Binary, Reddit Multi-5K, Reddit Multi-12K, Collab, Mutag, Enzymes, NCI1, Ptc-Mr, D&D, Proteins | feature processing time: IMDB Binary +23.2%; IMDB Multi +38.2%; Reddit Binary +90.0%; Reddit Multi-5K +88.0%; Reddit Multi-12K +75.8%; Collab -11 | Mixed |
| Use FTFI with a degree-2 polynomial instead of the Shortest Path kernel | Graph classification · ModelNet10 | accuracy (%): 39.6\% -> 44.2\% | Helped |
| Use tree-based FTFI masking instead of the Performer baseline | Topological Vision Transformers · ImageNet and Places365 | accuracy: 1.0-1.5\% | Helped |
Surprising findings
- Graph classification feature processing time is slower with FTFI on some datasets (e.g., Enzymes, Proteins, Collab), contrary to the general speedup trend.
Limitations
- Approximation for general graphs relies on minimum spanning tree, so accuracy depends on tree approximation quality.
- Exactness holds only on trees; the general-graph application is approximate.
- Several cordiality results (e.g., rational functions) incur extra log factors and may be impractical.
Experimental setup
Datasets: ImageNet Places365 I-Naturalist Thingi10K CUBES ModelNet10 IMDB Reddit Collab Mutag Enzymes NCI1
Benchmarks: ImageNet Places365 Thingi10K CUBES ModelNet10 IMDB Reddit Collab Mutag Enzymes NCI1 D&D
Metrics: accuracy speedup preprocessing time cosine similarity relative Frobenius norm error feature processing time
Baselines: BTFI BGFI Bartal trees FRT trees Separator Factorization Performer Shortest Path kernel
Builds on: Topological Transformers (TopViT) Performer Separator Factorization Random Fourier Features Non-Uniform FFT
Closest papers by meaning
- Linear Transformer Topological Masking with Graph Random Features (ICLR 2025 · similarity 0.89)
- Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs (NeurIPS 2026 · similarity 0.85)
- GIST: Gauge-Invariant Spectral Transformers for Scalable Graph Neural Operators (NeurIPS 2026 · similarity 0.85)
- Tree-Sliced Wasserstein Distance: A Geometric Perspective (ICML 2025 · similarity 0.85)
- Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework (NeurIPS 2025 · similarity 0.84)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.