Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers
Authors: Krzysztof Marcin Choromanski
Arijit Sehanobish
Somnath Basu Roy Chowdhury
Han Lin
Kumar Avinava Dubey
Tamas Sarlos
Snigdha Chaturvedi
Venue: NeurIPS 2024 poster (2024)
Keywords: Tree Metrics
Low Displacement Rank
Field Integrators
Topological Transformers
Graph Theory
Efficient Algorithms on Graphs
Primary area: machine_learning_for_other_sciences_and_fields
TL;DR: We present a new class of algorithms for the efficient integration of tensor fields defined on weighted trees, with several applications in ML, ranging from mesh modeling to training Topological Transformers.

Abstract: 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- Integrators: From Low Displacement Rank to Topological Transformers
Krzysztof Choromanski 1, Arijit Sehanobish Somnath Basu Roy Chowdhury" Han Lin Avinava Dubey Tamas Sarlos Snigdha Chaturvedi'
Google DeepMind, 2 Columbia University, Independent, UNC Chapel Hill, Google Research.
Abstract
We present new class of fast polylog-lineat algorithms based on the theory of structured matrices (in particular low displacement rank) for integrating tensor fields defined weighted trees. Several applications of the resulting fast tree-field integrators (FTFIs) are presented, including (a) approximation of graph metries with tree metrics, (b) graph classification, (c) modeling
meshes, and finally (d) Topological Transformers (TTs) [Choromanski et al., 2022] for images. For Topological Transformers, we propose new relative position encoding (RPE) mask- ing 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.
Introduction
Matrix-vector multiplication remains a key computational block of virtually all modern machine learning (ML) algorithms. For this reason, decades of research have been dedicated towards making this fundamental operation more efficient. One approach to achieve this goal through efficient hardware design, e.g., using modern GPU and TPU accelerators [Abadi al., 2016, Yu al., 2022, 2020J. The alternative method involves developing algorithms for efficient matrix-vector multiplication by leveraging either (1) sparse matrices [Wang, 2021, Beniamini al., 2020], (2) structured dense matrices [TThomas et al., 2018, Chandrasekaran et al., 2018J. These algorithms can be applied in modern neural network systems, where weights are pruned to encourage sparsity [Blalock et al., 2020] or they can be parameterized with structured matrices [Sindhwani et al., 2015].
In this work, aim accelerate multiplications with large class of matrices, that refer to as fddistance matrices, which play an important role several ML algorithms. Consider matrix M
IR N*N, where dist(i,j) stands for the shortest-pate distance between the i-th and j-th vertex of undirected graph G (V, F, W). Here V = {1, (1,... N) stands for the set of vertices (nodes), E denotes the set of edges, W E + R4 maps them to their positive def
(i)
weights, and f IR + R. We call M a f-distance matrix in G. Note that if f(z) x, then MD is the Shortest Path Kernel matrix.
The product M (where x E NR represents a scalar field on obtained by discretely integrating the field defined by x. this integration, a new field value at a vertex is calculated by averaging the old field values at all vertices weighted according to the function f (dist(u, u)). This integration can
"cqual contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

be extended to general tensor fields by replacing vector x E R with a tensor X E R R.Nxd xxxxxxdxx... xdgx...
M
Σ [)
JEV(G)
We refer to the above procedure as the fiintegration of a field X on G. We will use the terms graph field integration (GFT) and multiplication with f-distance matrices interchangeably throughout the paper. When the graph, G, is a tree, we call this procedure (Eq. 1) tree field integration. Next, we highlight several applications that rely on multiplications with f-distance matrices, MT.
1. Interpolation on manifolds:
This task involves predicting unseen values on manifold from a set of known values. For example, predicting the velocities of all points on a flag with known velocities for a few points [Pfaff et al., 2021]. For a discretized manifold, the interpolated values can be obtained using a weighted average using graph field integration (Eq. 1).
2. Optimal Transport (OT); A popular method used to solve the entropic OT problem [Peyré and Cuturi, 2019] is the Sinkhorn algorithm [Eckstein and Nutz, 2022]. Sinkhorn relies on multiplications with cost matrices, which are special cases of f-distance matrices for metric spaces induced by shortest-path distances in graphs. This can be efficiently solved using graph field integration.
Topological Transformers (TTs): Topological Transformers [Choromanski al., 2022] are extensions of traditional Transformers [ [Vaswani et al., 2017] 7] for graph inputs. TT's modify the 1-D relative positional encoding (RPE) using "mask matrices", which are f-distance matrices. We show how these matrices can be efficiently integrated into the attention mechanism (Sec. 4.4).
In the above applications, apart from the graph field integration step, the bottleneck lies in the process of explicitly materializing the f-distance matrix. Naively performing the integration in Eq consists of two steps: (a) computing the f-distance matrix, M which requires O(N*) time in the worst case (which we call preprocessing), and (b) performing the multiplication takes O time. This is prohibitively expensive while using large graphs.
In this paper, we introduce a new class of fast polylog- linear algorithms for graph field integration that uses low displacement rank (LDR) matrices [Thomas et al., 2018, Chandrasekaran et al., 2018). To summarize, our primary contributions are given below:
1. We provide the first exact polylog-lineal multiplication algorithms called Fast Tree-Fielb In- tegrators (FTFIs), for general weighted trees and a rich class of maps f, including rational, trigonometric, exponential and exponentiated quadratic functions (Sec. 3.2).
2. We show how Fast Tree-Field Integrators can be applied to support fast computations on general graphs by approximating graph metrics with tree metrics (Sec. 4).
3. We show that FTFIs are 5.7-10x faster than baseline graph field integration methods for large-scale graphs (Sec. 4.1 and 4.2).
4. We showcase the efficacy of FTFIs in several applications including graph classification (Sec. 4.2), interpolation meshes (Sec. 4.2), and Topological Vision Transformers (TVTs) (Sec. 4.4). For TVT's, we propose new relative position encoding (RPE) masking mechanisms by introducing only three extra learnable parameters, which leads to 1.0-1.5% % accuracy gains. We provide an exhaustive evaluation on Vision Performers (25 models on multiple datasets). Some of our best models use exponentiated quadratic functions f. which has not been applied in this context before.
For completeness, we also propose approximate FTFI extensions via Non-Uniform FFT (NU-FFT) [Kircheis et al., 2023] and random Fourier features (RFFs) [Rahimi and Recht, 2007] (Sec. A.2).
2 Related work
Efficient graph field integration (Eq. 1) has been studied by prior works for different classes of matrices. For example, Al-Mohy and Higham [2011] considered exponentiated adjacency matrix- vector multiplication, Spielman and Teng [2012] targeted symmetric diagonally dominant matrices (e.g., Laplacian), Arrigo et al. [2018] analyzed matrices that are power series of random walk kernels. In contrast to these approaches, Saad and Schultz [1986] proposed general iterative methods for solving certain linear systems using Arnoldi' iterations. However, These iterative methods can suffer

---

level 3
left
right
left-ids
01234
6
right-ids
2
level 2
left-id-d
01228
right-id-d
left-d
0
0 0877
right-d
level 1
0112244
left-s
right-s
13
3
left
right
left
right
pivot
level 0
1
0
5
8
6
2
0 2
012
1
0
0
5
level 1
023
020
D23
025
0112
012
0 011
012
6
level 2
Do
D
D2
D3
8
level 3
0 2 3
0
2
4
0
2
3
0
2
5
T
f
2
0
1
2
0
6
2
0
1
0
7
3
1 0
4
6
0
3
1 0
5
7
0
Figure 1: Pictorial representation of the IntegratorTree (see: See 3.1) data structure for the nine-vertex input tree T the left. Numbers in blue IntegratorTree object represent f-transformed (element-wise) distance matrices: Do, D1, D2, Dy sub-trees induced by vertex-sets: {1, 2, 4) (1,3, 0), (5, 7,8} and (5,6,0) respectively. Different levels correspond to different distances from the pivol point.
the input denote the weights of its edges. Leaves of the
from convergence issues. Williams [2007] showed that it is possible to pre-process any boolean matrix to achieve sub-quadrath matrix-vector multiplication.
The general problem computing the action of a matrix on vector, where the matrix the graph kernel, in sub-quadratic time is intractable, except for few special cases [AI-Mohy and Higham, 2011, Choromanski et al., 2023]. this work, we embed the graph under consideration in a tree (replacing the graph metric by the underlying free metric). Then, we leverage the tree structure to approximate the action of the kernel on given vector by providing exact integration on a tree.
Previous works [Bartal et al., 2022, 2019, Abraham et al., 2008, Bartal, 1998] have used the theory of tree metrics (TMs) in several applications mathematics and computer science. TMs are widely used to embed a complex metric space (e.g.. a Riemannian manifold) into a more tractable one, while approximately preserving (all or most the) pairwise distances. They find applications in distributed & online algorithmss [Khan et al., 2008, Bubeck et al., 2018], biology [Mossel, 2007], vision, robotics [Athitsos and Sclaroff, 2003], and MI. (e.g., metric spaces' regression [Gottlieb et al., 201 1]).
Tree metries for fast matrix multiplication: Applying tree metrics (TM) to compute approximate M is natural approach scale up matrix multiplications. space well, then the derived embeddings should have low distortion. However, in the worst-case scenario, this is not true for deterministic tree embeddings. A natural alternative is to sample trees from probabilistic distributions, which are shown provide logarithmic distortion in expectation [Faccharoenphol et al., 2004b, Bartal et al., 2022]. This can be further improved to constant distortion for certain classes of metries, e.g., celebrated snowflake metics [Leeb, 2016]. For graph metrics defined by shortest-path distances, there exist spanning trees providing constant average distortion (over all pairs of nodes). These spanning trees can be constructed as near minimum weight spanning trees [Bartal et al., 2016]. Unfortunately. explicit application of any tree metric still requires O(N2) time (impractical for large N) to: (1) compute all shortest-paid -atte distances via the breadth-firse firt--f-tt-ercchh algorithm (BFS), even if sub-quadratic methods were used to construct tree (e.g. minimum spanning tree), (2) store the matrix, and (3) perform matrix-vect vector multiplications. We provide more details about work related to graph field integration in Appendix B.
TM approximates the metric
3 Fast Tree-Field Integrators (FTFI)
In this section, we present our approach for performing efficient field integration on tree, which we call fast tree field integrator. We begin by introducing the concept of integrator trees (ITs), which is

---

specialized decomposition of a tree using the theory of balanced separators (Sec 3.1). Subsequently. we leverage these integrator trees execute efficient integration on tree via divide-and-come and-conquer algorithm (Sec 3.2).
3.1 IntegratorTrees (ITs)- preliminaries
To support fast integration for various tensor fields X E IR Ngdx X..xxx defined on a given input tree T, we first design a special data structure that we refer to as an IntegratorTive (IT). An object of this type is constructed only once per T. regardless of the number of tensor fields used. An IT is rooted binary tree. To avoid confusion, we will refer to its vertices as nodes, reserving term vertices for those of T. Each node of IT corresponds to the induced sub-tree ST of T. For every non-leaf' node corresponding to some ST, a pivor point along with two sub-trees: STie and STright are constructed. The following needs be satisfied:
|ST 2 [ST] for x E fleft, right),
. ST NTT {p] (1 denotes the number of vertices).
The next lemma shows that every tree with [C] 2 6 has the above decomposition and it can be efficiently found.
Lemma 3.1 (Pivoting). If KC is a tree with [K] 2 6, then K. admits a decomposition (Kieft, Kright p) given above and it can be constructed in linear time.
The algorithmic proof is provided Appendix A.I and uses standard tools from the theory of balanced separators.
The left child of the non-leaf node for ST corresponds to STiet left and the right child ST right- In addition to these two pointers, non-leaf node also contains eight extra fields, partitioned into two groups, one corresponding to left child and one its right children. The fields corresponding to the left child are as follows:
Left-ids: an array of the ids (in T) of those vertices that are in ST left. mapping the ids of vertices in ST left to the original ids in T (each sub-tree uses consecutive numbers from 0 as ids locally). Left-d: array of different shortest-patt path distances from the pivot point the vertices in ST left-
Left-id-d: an array mapping the ids of vertices (in ST to the indices in left-d of their corre-
sponding distances from the pivot point.
Left-s: a corresponding array of the ordered sub-sets of ids (in ST STiei) of vertices within a particular distance from the pivot point.
Fields corresponding to the right child are defined similarly. The leaf nodes of the consist only of the f-transformed telement-wise) distance matrices D for their corresponding sub-trees (see: Fig 1). In principle, the leaf nodes of IT correspond to sub-trees with less than 6 vertices each. In practice, we choose higher for more efficient integration (see: discussion in Sec. 4.1).
From what we have said so far, it is clear that an IT can be constructed by applying breadth first search (BFS) and the linear algorithmic procedure for constructing the decomposition from Lemma 3.1. Note that every vertex of the input tree appears in the logarithmic number of nodes the IT since the size of the sub-tree is at most & x the size of its parent in IT. We conclude that IT for the given input tree T can be computed in O log(N)) time, where stands for the number of vertices [T] of
Time & space complexity of constructing ITs::
3.2 Integrating with IntegratorTrres
We are ready to explain how IT's allow us to efficiently integrate any given tensor field X E Nxxx x.. defined on T for wide class of function f R - R. We will apply divide-and- conquer strategy.
We start in the root node of IT. If that node is leaf then the f-transformed distance matrix is stored and can directly used for matrix-tense multiplication. this node not a leaf, then it encodes the decomposition (Tiet, Tright, p). Take some (TTet)). Note that the value M X(e] of the new

---

field in u after f- fintegration is given as follows for W = ((Tright) Mppp:
[(dist(e, (E
(dd
JEW
Fme(())
F (v)e(v)
To compute the new values the field for nodes E Tiett. one needs to:
Compute the contribution from Tiott (F inner teeres))) This can be done simply by applying Eq. recursively for Tien, which means traversing to the left child of the root.
Add the so-called cross-terms contributions coming from the vertices of W (F (u)
The key observation is that the latter (cross-term) contributions can be retrieved simply by computing
CX', where: (1) C E R&xi with k and being the sizes of the node's left-d and right-d arrays def respectively. j(i.j) = flefttdd[]] + right-d(jl)- and (2) Let by = |right-s[i]] where size of the subset. Then gixd x...xd, is defined as follows:
refers to the
(riight-
Given the structure of IT, tensor X' can computed in linear time. Note that the following holds:
F Peross (v) (CX)) -(ee]]]]]eee]]/]]]))))"00000
(4)
where 7(V) left-id-dfe]. Analogous analysis can be derived for E Tright. with matrix CT replacing C. Thus the overall time complexity of the cross-terms computations is determined by the algorithm for matrix-tensor multiplications with matrices C and CT.
3.2.1 The case for structured matrices: multiplications with C, C and cordiality
Matrices C, CT are of the form: [f(x; y for some sequences (2t)) (v;) and a, b N4.
Definition 3.2 (cordial functions). A function f R + IR is d-cordial (or: cordial if d is not not specified), if there exists e N such that matrix- multiplication with matrix M [f( + y, " can be conducted in time O((a + b) log" bb) b)) for every (ax) (u5))=1-
Next, we demonstrate the importance of cordial functions in our FTFI framework. Lemma 3.3 (f-integration with cordial functions). If f is d-cordial then f-integration for the general weighted free of N vertices can be conducted in time O(N log (N)).
Proof. Denote by T(N) time complexity for running FTFI on the N-vertex tree. We have the following recursive formula for T, where < c < 3:
T(N) < T(cN) T(( - N) + O(N log" (N))
(S)
This is implied by the fact that: (1) the size of each sub-tree is at most x the size of its parent, (2) the computation across left and right children is dominated by multiplications with matrices C' and CT. The solution of this recursion leads the statement.
Next, we show some practical implications of Lemma 3.3, where tree weights are completely arbitrary. Additional results are given Sec. A.2.3.
Rational functions: We claim that every rational f is (2 c)-cordial for any > 0. We will use Lemma from [Cabello, 2022] stating that: given any set of rational functions (z(x) (,(2) and {a+ H one can compute the a values Σラ= Rg (zx) in time O((a + b) log" (b) (lg((b()))) (by applying FFT). For given vector E & it thus suffices to define: Rz vy (x + yU) and that
(z)
lemma can be applied to efficiently compute Mv. We conclude that for any > 0, f f-integration can be conducted in O(N 3 (N)) time for N-vertex weighted trees and any rational f RR + (see
also: Sec. 4.3, Sec. 4.2, Sec. 4.4).
5

---

Ma.2
M
M
Mo.1
Mp
Vell
13
OgX -2 [18)
S++W
exp
2+1
omp:
expt
X
c3p
D1
M
M
D2
Figure 2: Pictorial representations of the main concepts behind efficient matrix- vector multiplications Mv with M E R5x4 for the polynomial and fx) = exp(A=) low-rank outer-product matrices corresponding to terms of different degrees (c.g., constant, linear, quadratic, etc.). Matrix associativity property is applied for efficient calculations (dotted-border blocks indicating the order computations). In the second case, high-rank, but the so-called low displacement rank operator Ap,.D, X - D,M- MD, for diagonal D.. D2 can be applied to make it low-rank outer-product matrix. The multiplication with M can be efficiently performed using the theory of LDR matrices [Thomas et al., 2018J.
2-c In the polynomial case, M is re-written as sum of
The above result on rational functions clearly applies also to polynomial f. but here we can do better. We show that f is O-cordial. Assume that f(x) = Σt= a,z'. We have: M - Eizo ag Mi, where matrix M E Ra is defined as an outer-product of two vectors: (xi, xx") E IR and (yi, vh)) E RRd, Thus each MM.,, supports linear matrix- vector multiplication (via associativity property). The proof is completed, since B is constant. We conclude that f f-integration can conducted in O(N log(N)) time for N-vertex weighted trees and any polynomial RR- + R (see: Fig, 2 and Fig 9).
Polynomial functions:
Exponential functions: Take f(x) exp(Ar). Then M is an outer-product of two vectors: E Rº and (exp(Ay;))5 E R², The remaining analysis and conclusion is thus the same as for the polynomial case (see also: Sec. 4.4).
atc (c is a constant) We claim that f is 2-cordial. In that setting, matrix M satisfies: M(i,j) exp(Ax;) exp()g.) and thus is a Cauchy-like LDR, supporting fast O(N log²
Function: f(x) exp(Ax);
(a, + +)))) matrix-vector multiplication [Victor Y. Pan, 2000]. We conclude that f-integration can be conducted in O(N log" (NV) time for N-vertex weighted trees and [(x
exp(Az) (see: Fig. 2).
ztc
Functions f()) = exp(ux² + uIr w)) and trees with positive rational weights: Now matrix M can be re-written as M eXp(w)D) VD2, where D E Iaxe and D2 E gxxb are diagonal, with diagonal entries given by sequences fexp (ux; + uux, } and (exp(uy, uy, respectively, and furthermore V the generalized Vandermonde matrix (GVM) (using arbitrary nonnegative integers as exponents). It is defined as: (ii,j) = r,", where r; exp( 2uz.) and 8j у/ E N. As in the previous case, the embedding trick can be applied, but will use it only for columns. That effectively leads to the completion of the set exponents { to the set of consecutive integers starting from 0 and a regular Vandermonde matrix, that supports O(N log (N)) matrix-vector multiplication, replacing GVM. The benefit of this embedding. as compared to the previous one, that even though still increases the number of columns by a multiplicative factor of p. the number rows does not change. Therefore, for p > log(NV) substantial computational speedups are achieved (see: Sec. 4.4).
4 Experiments
In this section, we outline the experimental setup and report the performance of FTFI across various settings. For all the experiments, we only consider minimum spanning tree (MST) as an approximation of our graph. Specifically, design experiments to answer these research questions:

---

(Q1) How efficient are FTFIs for tree field integration?
(Q2) How does the approximation quality of FTFI compare to other integration algorithms?
(Q3) How can we further improve the approximation quality in FTFI?
(Q4) How can we use FTFI in real-world large-scale settings?
4.1 Runtime Efficiency of FTFI
The main goal of this experiment is to evaluate the speedups obtained by FTFI as compared to brute-force tree field in- tegrator (BTFI) i.e. the explicit calcu- lation of Eq on a tree. We consider two classes of graphs: (a) synthetic, ob- tained from a path-graph by adding ran- dom edges and (b) mesh graphs from Thingi10K [Zhou and Jacobson, 2016] dataset. For BTFI, we compute the MST and then integrate a random scalar field X on the vertices of the MST. Since BTFI & FTFI are numerically equiva- lent, we report the pre-processing time and integration as function of vertex count (N) Fig. 3. We observe that FTFI achieves up to 13x speedups for 20K-vertex meshes and 5.7x+ for synthetic graphs with over 10K vertices compared to BTFI.
STF1 STR (suns)
synthetic
10a
Bm
FIFI)uun)
moshes
100
13.00
1134
Figure 3: Runtime comparison of FTFI with BTFI as a function of the number of vertices, N. Left: Synthetic graphs. Right: Mesh-graphs from Thingi 10K. The speed is not necessarily monotonic in N as it depends distribution of lengths of the shortest paths. For each graph, 10 experiments were run (std. shown via dotted lines).
the
4.2 Approximation Quality of FTFI
We evaluate the approximation quality achieved by FTFI across a wide range of graph-based tasks.
Interpolation on meshes. We compare the efficiency of FTFI with baselines on the normal vector prediction task. Every node of the considered mesh G with vertex-set V, associated with a location X; E IR and a vertex normal F; E RR For each mesh, we randomly select subset V C V with [V'| = 0.8| V| and mask out their vertex normals (set as zero vectors). The interpolation task involves where Ky v) f (dist(w, v)), with dist(w, 2) being the shortest path distance between node and and f is a rational function f(x) = 1/(1 + Xx²). We perform grid search to set hyperparameter À for each mesh and report the result with the highest cosine similarity between predicted and ground truth vertex normals, averaged over all the nodes. We run tests on 40 meshes of the 3D-printed objects with a wide range of sizes from the Thingi10K dataset (details in Appendix D.3). We compare FTFI with BTFI, dis-oittotion tree-based algorithms such Bartal Trees [Bartal, 1996] and FRT trees [Fakcharocnphol et al., 2004a] alongside the state-of the-aat method for graph-field integration, the Scparator Factorization (SF) algorithm [Choromanski et al., 2023]. We also compare against the baseline BGFI which entails explicitly materializing the kernel matrix of G and then performing matrix tensor multiplication with tensor field F defined by the F,'s.
predicting the vertex normals of each masked node i E V as: F, = Σyeviy
Preprocessing involves building specific tree structures (FRT. Bartal), calculating the kernel matrices (BGFI, BTFI), or creating specialized data structures (SF, FTFI) for efficient later use. The first two plots in Fig. shows the pre-processing time and cosine similarity for various algorithms applied to meshes of different sizes. FTFI is the fastest in terms of pre-processing time and achieves competitive performance in terms of cosine similarity (between predicted and actual vertex normals) when compared with the SF algorithm while being numerically equivalent to BTFL. FTFI is a few orders of magnitude faster than BTFI and the tree-based methods while maintaining accuracy.
Graph classification. Graph kernels have been widely used for graph classification tasks in previous works [Kriege al., 2020, Nikolentzos et al., 2021]. We compare the classification results obtained using the approximate kernel from FTFI with those from the exact SP kernel. In this setting. we use the Shortest Path (SP) kernel, (dist (i,j)) J)). We perform experiments on a wide range of bioinformatics and social networks datasets like D&D, MUTAG, REDDIT, IMDB, among others. We follow [de Lara and Pineau, 2018] and construct the graph feature for both kernels by using the
smallest & eigenvalues (k is hyperparameter). This feature set is then used for classification, using
7

---

Scalability
Cosine Simiarity
Cosine Siilierity us Time
1.
50
BCF
Time (sarc)
BTT!
Dantal
10
PieT
120
10
0.2
0.2
0.4
0.6
1:0
0.0
02
06
08
1.0
Number of Points
Time (sec)
Figure 4: Speed (pre- proceeseessnng time) and accuracy (cosine similarity) comparison of the FTFI and other baselines for vertex normal prediction on meshes. Cosine similarity of BFFI and FTFI almost overlaps. The last figures are qualitative examples showcasing the tradeoff between cosine similarity and preprocessing time for meshes sizes 3K and 5K nodes respectively.
IMDB BINARY
IMDB MULT
REDDIT BINARY
REDDIT MULTI 5K
672
Acounacy (Rg)
05.6
48-
83.5
44.8
+.2.22%
+-88.
84.0
+:900
+88.0%
64.0
48
82.5
43.2
632
81
41.6
PTC-MR
MUTAG
D&D
NC11
85.5
77
76
74.4
Arorney (9)
60.0
-4.5
02.5
38.45
585
81.0
+58.0%
74
+34.5
72.8
57.0
72.0
78.0
FTRI
BGFI
Feature Processing Time seconds)
Figure 5: Trade-off plot comparing graph classification accuracy and feature processing time for the classifiers using FTFI and BGFL. FTFI achieves similar accuracy as BGFI while significantly reducing fp time across most datasets. We report the reduction in FTFI's processing time (+xx) compared to BGFI using a dotted line.
random forest classifier. We observe that FTFI achieves significant speed improvements while achieving similar accuracy compared to its brute-force counterpart, BGFI (see Fig. 5). We provide more details about the experimental setup and baselines Appendix D.4. We also report additional experiments meshes and point clouds in Appendix D.1.
4.3 Improving approximation quality with learnable f-distance matrices
We propose further improve the approximation quality of FTFI by learning f-distance matrix metrics derived from the MST. As an application, we choose general graph metrics, where our goal is to learn the shortest-path distance dy between given pair of nodes (v, w) in graph. Given
f-distance matrix and tree-derived metric d the objective to learn a mapping to minimize
(d Sbb.... (du,..)
B(O,w)DD
(6)
Rather than using fixed f. we parameterize and train it. We consider rational function f:
Go + aIœ + a,x*
at (x) hoo.... b,
bo bi b
where ag ag...., Oz, bo. .... E IR are trainable parameters.

---

0
100
100, den:
100, den:
200
100, num: dan
100, num: den.
Training Loes
300
14
100, num: d den:
100, num: den.d =
400
12
14-
20
300
20
40
30 200
123
Itcrations
Figure 6: Left: Relative Frobenius norm error as a function of the number of training iterations for different sizes n and learnable quadratic f. Middle: Comparison of the training of different rational functions f with num:d defining the degree of the numerator and den:d, the degree of the denominator for the synthetic graph obtained from path N 800 by adding 600 random edges and assigning random weights taken from (0, 1). Right: constructed similarly, but for a sampled mesh graphs from Thingi 10k dataset.
Training dataset D. For graph G, we randomly sample vertices. The training dataset consists of tuples of the form: (u, w, dy w do E D. where v, w are randomly sampled vertices. Each data point can be constructed in time O(N log(N)), even O(N) if weights are in N [Thorup, 1997].
Final evaluation. To evaluate the quality of the approximation, we compute the relative Frobenius norm error: [IM - - where || ||r stands for the Frobenius norm, T is tree for given |M graph G and id is identity function (see: notation from Sec. 1). It quantifies how closely the distance matrix G is approximated by the f-distance matrix of T. Computing e expensive and training does not rely it. Our empirical results show that the relative error, can be substantially improved by using the hight- MSE training loss (defined in Eq. 6).
We report the evaluation eтrоr for these experiments in Fig. 6 (with additional results in Fig. 8 in the Appendix). We observe that a rational function with quadratic numerator and denominator provides strong performance across different graphs. We notice that increasing the training set to > 100 data points does not have a substantial impact on the final error. Estimating the coefficients of ʃ provides approximation improvements across all graphs in as few as 40 training steps.
These above results show that tree-based estimators are expressive enough emulate integration on arbitrary graphs. This expressive power can be further enhanced by pairing them with "nonlinear" functions Thus, they explain why the presented techniques are relevant for general graphs.
4.4 Large Scale Transformer Experiments using FTFI
For large-scale applications of FTFI, we select Topological Vision Transformers (TTD [Choro- manski et al., 2022], and leverage for efficient incorporation of masking within ViT's We provide detailed description of masked Transformers in Appendix C.
We propose an extension to Top that seamlessly integrates FTFL. In this extension, we model the mask matrix as an f-distance matrix (with learnable f) defined on the minimum spanning tree (MST) obtained from the 2D grid graph image encoding,
Topological Vision Transformers with trees
where vertices correspond different patches. We parameterize f as ft g(Σt -i= a,z"). We use the linear attention mechanism introduced in Performers [Choromanski et al., 2021], where the attention kernel is written as: K(q, k) = ó(q) Φ(k) for deterministic [ddox + R. applied seement-wise. We experiment with different values of hyperparameters t, á and cross-heads parameter sharing strategies as shown in Table (synced indicates that aPE-parameters across different attention heads).
shared
We run experiments on ImageNet and Places365 datasets using VIT-B/16 (see Table 1). For all the kernels, our variants beat the baselines. For Φ(x) xA, the best variant applies an exponentiated quadratic function, for which we apply Vandermonde matrices (see: discussion in Sec. 3.2. Our

---

Table 1: Performance of Topological Vision Transformers with tree-based masking. For each attention
kernel, we present the results of the best variant in bold and Performer baselines in blue.
ImtggeNet
Place365 g Rod.U
Om 2
esp
gyoed
Acc.
(1)
synced
Aec. (S)
syncod
Ace. (8)
syneed
R
Ace. (5)
synord
Ace. (%)
NA
NA
NA
76.23
NA
NA
NA
75.03
NA
NA
NA
76.37
NA
NA
NA
76 76.76
NA
NA
NA
54.80
exp
77.28
esp
exp
78.79
esp
56,69
exp 76.60
exg
2
75.91
uxp
77.23
esgi
78.51
X
5 5-+1--
77.79
X
1
76.76
X
77.94
2--22
77.39
2-
56.32
exp 77.43
76.27
esp
78.15
37.09
56.51
best variant across all kernels (78.79%) provides 2% accuracy gains over the best baseline (76.76%) In the synced setting, we use only three extra learnable parameters per layer (shared in all attention heads across all layers) and obtain 1-1.5% accuracy gains. the asynced setting, we use a small set of 36 extra learnable parameters per layer (3 extra parameters per head). Overall, we observe that FTFI improves the approximation quality within Transformers with a minimal number of parameters. We provide additional discussions on the VIT results for ImageNet in Appendix D.5.1 and for Places365 in Appendix D.5.2.
ImageNet Training Curve
Additional results on the I-Naturalist dataset, where we outperform various low-rank attention baselines, are provided in Appendix D.5.3.
0.8
0.7
0.6
Accuracy
0.5
Larger Transformer models: We scale our experi- ments to run on the larger ViT-L architectures and eval- uate on ImageNet.
0.3
this setting, we use RPE mecha- nism with exp and /= = I (that provided strong per- formance in previous experiments) and asynced strat- egy. We observe that FTFI provides 7 % accuracy im- provement (see: Fig. 7).
0.2
ViT Performer
0.1
ViT Performer (FTFI)
0.0
20000
40000
60000
80000
Iterations
Experiments with the RPE mechanism for ViT-B and on ImageNet. We observe that FTFI provides 7% accuracy gain compared to the Performer variant.
Figure 7: Left:
Further results on Video Transformer (ViVIT) [Arnab al., 2021] are provided in Appendix D.6. We also provide additional experiments including Gromov- Wasserstein distance computation [Vayer et al., 2018] (see Sec. D.2), along with code pointers (Appendix D).
5 Conclusion
We provided a new class of algorithms for fast and exact integration of tensor fields defined on weighted trees, relying on the theory of structured (in particular low displacement rank) matrices. We showed how those algorithms can be applied for accurate integration on general graphs, in particular via their minimum weight spanning trees. We presented several applications of the presented methods, from graph classification and interpolation on meshes, through graph metric approximation Topological Vision Transformers. Our methods provide significant (5-13x) speedups while maintaining the quality of their exact counterparts.
6 Author Contributions
KC conceived the idea behind FTFI, proved the theoretical results, implemented FTFI algorithm and ran the vision experiments in this paper. AS integrated the FTFI algorithm in the GW style algorithms and ran some graph and point cloud classification tasks. SBRC ran graph classification experiments as well as experiments develop methods, and along with TS and SC acted as senior advisors for the project. All authors contributed to the writing of the manuscript.
the CUBES dataset. HL ran the experiments the meshes. AD helped
10

---

References
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Gordon Murray, Benoit Steiner, Paul A. Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: A system for large-scale machine learning. In Kimberly Keeton and Timothy Roscoe, editors, 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016, pages 265-283. USENIX Association, 2016. URL https::/wwwr http:///wwwwwwwxx.././///// wsw.ix..n.... org/ conference/ osdi 16 htt//teccniiiiieee cal-
Ittai Abraham, Yair Bartal, and Ofer Neiman. Nearly tight low stretch spanning trees. In 49th Annual IEFE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 781-790. IEEE Computer Society, 2008 doi: 10.1109/FOCS.2000 62. URL https: htt//dii.ooo org/ 10. 10.1109/FOGG 2008. 62.
Juan Acebron. monte carlo method for computing the action of matrix exponential on a vector, 2019.
Juan A. Acebron, Jose R. Herrero, and Jose Monteiro. A highly parallel algorithm for computing the action of matrix exponential vector based on a multilevel monte carlo method, 2019.
Awad H. Al-Mohy and Nicholas J. Higham. A new scaling and squaring algorithm for the matrix exponential. SIAM Journal on Matrix Analysis and Applications, 31()):770-995 11700-999,,000 2010. doi: 10.1 10.1137/990772IIX URL petttps://oot wttp//0.111/0000477717
Awad H. Al-Mohy and Nicholas J. Higham. Computing the action of the matrix exponential, with an application to exponential integrators. SIAM Journal on Scientific Computing. 33(2):488-51 2011. doi: 13/107700008888 URL https: / /tt.i/ii.ooooo 100 1137 1117/100788866
Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lučié, and Cordelia Schmid. Vivit: A video vision transformer. In Proceedings of the IEEE/CVF international conference on computer vision, pages 1836-6846, 2021.
Walter E. Arnolii.
The principle of minimized iterations in the solution of the matrix eigenvalue prob- lem. Quarterly of Applied Mathematics, 9:17-29, 1951. URL https://app. http:://ppp.sssaisieeeeeeeee cemaanticscoolll Drg/CorpusID: 115852469.
Francesca Arrigo, Peter Grindrod, Desmond J. Higham, and Vanni Noferini. On the exponential generating function for non non-backtracking walks. Linear Algebra and its Applications, 556:381- 399, 2018. ISSN 0024-3795. doi: http:////..aaae///00022221133231
07.010 URL https:
www..sciencedirectt. com/ htmm/science..e htt///ciinne/articiiccc
Vassilis Athitsos and Stan Sclaroff. Database indexing methods for 3d hand pose estimation. In Antonio Camurri and Gualtiero Volpe, editors, Gesture-Basel Communication in Human-Compun Interaction, 5th International Gesture Workshop. GW 2003, Genova, Italy, April 15-17, 2003, Selected Revised Papers, volume 2915 of Lecture Notes in Computer Science, pages 288-299. Springer, 2003. doi: (0.1007/978-3-544-2455---- 27. URL https://doi..or//00 1007/ 118-3-540-24598- 8_27.
Auckenthaler, M. Bader, Huckle, A. Spörl, and K. Waldherr. Matrix exponentials and parallel prefix computation in quantum control problem. Parallel Computing, 36(5-6):359-369, May 2010. ISSN 0167-8191, doi: wtt.::j.apccoo2.......
Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of 37th Conference on Foundations of Computer Science, pages 184-193. IEEE, 1996.
Yair Bartal. On approximating arbitrary metrices by tree metrics. In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 161-168. ACM, 1998. doi: 10.1 10.115//26698.2767555 URL https:/ //doi org 10. 1111/11161669 1161111111177777777777775 276725.

---

Yair Bartal, Arnold Filtser, and Ofer Neiman. On notions of distortion and an almost minimum spanning tree with constant average distortion. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithums, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 873-882 SIAM, 2016, doi: 10. URL https::t/////...t //o.i//o.i./oo org/ 10. 1137/ / 97811119971133 ch62.
Yair Bartal, Arnold Filtser, and Ofer Neiman. On notions of distortion and almost minimum spanning tree with constant average distortion. J. Comput. Syst. Sci., 105:116-129, 2019. doi: 10.10166..CCSS.2011.440006 URL https //doi/d///// wor.oogg///o 1016/j jess 2019. 0060
Yair Bartal, Ora Nova Fandina, and Ofer Neiman. Covering metric spaces by few trees. J. Comput. Syst. Sci., 130:26-42, 2022. doi:
www.://SSS............. URL https:://don /ttp::///ooooo//10...
1016/j j- jcss. 2022.0222222222 06.001.
Gal Beniamini, Nathan Cheng, Olga Holtz, Elaye Karstadt, and Oded Schwartz. Sparsifying the operators of fast matrix multiplication algorithms, 2020.
Michele Benzi, Thomas M. Evans, Steven P. Hamilton, Massimiliano Lupo Pasini, and Stuart R. Slattery. Analysis of monte carlo accelerated iterative methods for sparse linear systems. Numeri- cal Linear Algebra with Applications, 24, 2017. URL https::t///at //api. semanticscholas org/
CorpusID: :99701344
Davis W. Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John V. Guttag. What is the state of neural network pruning? CoRR, abs/2003.03033, 2020. URL https://arxiv org/abs/ 2003.03033
Guy E. Blelloch, Anupam Gupta, Ioannis Koutis, Gary L. Miller, Richard Peng, and Kanat Tang- wongsan. Near linear-work parallel sdd solvers, low-diameter decomposition, and low-stretch subgraphs, 2011.
Erik Boman, Bruce Hendrickson, and Stephen Vavasis. Solving elliptic finite element systems in near-linear time with support preconditioners, 2008
Richard P. Brent. Stability of fast algorithms for structured linear systems. CoRR, abs/1005.0617 2010. URL /ttp:///axivv org/ abs/ 1005.0000000 0671.
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. k- server via multiscale entropic regularization. In llias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 3-16. ACM, 2018. doi: 10.1 10.1145/3188745.31888
URL
org/ 10.
3188798.
Sergio Cabello. Computing the inverse geodesic length in planar graphs and graphs of bounded treewidth. ACM Trans. Algorithums, 18(2):14:1-14:26, 2022. doi: 10.1145/3501303. URL https://doi. org/10 10. 1145/3501303.
Shivkumar Chandrasekaran. Nithin Govindarajan, and Abhejit Rajagopal. Fast algorithms for displacement and low-rank structured matrices. In Manuel Kauers, Alexey Ovchinnikov, and Éric Schost, editors, Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2018, New York, NY, USA, July 16- 19, 2018, pages 17-22. ACM, 2018. doi: 10. T..114//220876.332000 20000025. URI https: //tettss:///o/ /toi. org/ 10. 1145/ 02009/3209766.. 22222299..2.2225.....
3209025.
Krzysztof Choromanski, Han Lin, Haoxian Chen, Tianyi Zhang, Arijit Sehanobish, Valerii Likhosh- erstov, Jack Parker-Holdee Tamás Sarlós, Adrian Weller, and Thomas Weingarten. From block- toeplitz matrices to differential equations on graphs: towards general theory for scalable masked transformers. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvári. Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning. ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 3962- 3983. PMLR, 2022. URL https: http://pooceeeeegeee//ee mlr www.m.r..esss.e..... www.prresvvvv..... wttass/vvve//e/ cho.om2si2crommm.2222e. html.
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Ben- jamin Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking attention with performers. In 9th
12

---

International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL hwt.ittt///pparrriiii....o. htt///orrrrr/////AUauaao
Krzysztof Marcin Choromanski, Anijit Sehanobish, Han Lin, Yunfan Zhao, Eli Berger, Tetiana Parshakova, Alvin Pan, David Watkins, Tianyi Zhang, Valerii Likhosherstov. Somnath Basu Roy Chowdhury. Kumar Avinava Dubey, Deepali Jain, Tamás Sarlós, Snigdha Chaturvedi. and Adrian Weller. Efficient graph field integrators meet point clouds. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning. ICML. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 5978-690887 8004. PMLR, 2023. URL wttp:/ig.......rrrreeereee
mlr. ppress/v20// http///horooioooccoo prtesss/2222//cororaaas2222222
html.
Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang- Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs, 2010.
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipezuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithmms. Springer, 2015. ISBN 978-3-319-21274-6. doi: 00.1077978-33319-22225 URL https://dol org 1tt/100.0077 978 978-3-319-21275--
Samuel I. Daitch and Daniel Spielman. Faster approximate lossy generalized flow via interior point algorithms, 2008.
Nathan de Lara and Edouard Pineau. A simple baseline algorithm for graph classification, 2018.
P. Drineas and R. Kannan. Fast monte-carlo algorithms for approximate matrix multiplication. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 452-459, 2001.
doi: 10.1109/SFCS 2001.959921.
Petros Drineas, Ravindran Kannan, and Michael Mahoney. Fast monte carlo algorithms for matrices Approximating matrix multiplication. SIAM J. Comput., 36: 137-157,, 01 2006. doi: 10.1137)
500975397044466844
Stephan Eckstein and Marcel Nutz. Quantitative stability of regularized optimal transport and convergence of sinkhomn's 's algorithm. SIAM J. Math. Anal., 54(6):5922-599 5948, 2022. doi: 10.1137/ 21M145505X. URL https: / //oi//o/.////////// org/10 /0. 1137 1113722mm1550555
Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang- Hunng-HuaTie Teng. Lower-stretch spanning trees, 2005.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485-497, 2004a.
Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3) 2004b. doi: 10.10166JJCSSS.004 04.011. URL https: //oi org/10. httg//...116//1111 - jcss. 2004 011.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021. URL http:/
wwwpoo/gggp/.//////..o 451 html.
Lee-Ad Gottleb, Aryeh Kontorovich, and Robert Krauthgamer. Efficient regression in metric spaces via approximate lipschitz extension. CoRR, abs/1 11s/1111,,440,, 2011. URL. http:://aarra org/ abs/ abs/1111.4 11111.443 4470.
13

---

Leslie Greengard and June- Yub Lee. Accelerating the nonuniform fast fourier transform. SIAM Rev. 46(3):443 454, 2004. doi: 10.1157/500301444554400000000 URL https://doot wrg/oo...... 1137/ $0036144503432001
Rana Hanocka, Amir Hertz, Noa Fish, Raja Giryes, Shachar Fleishman, and Daniel Cohen-Or. Meshenn: network with an edge. ACM Transactions on Graphics (ToG), 38(4):1-122 2019.
Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green. Trevor Back, Paul Natsev, al. The kinetics human action video dataset. arXiv preprint 1rxxiv:705..00
2017.
Maleq Khan, Fabian Kuhn, Dablia Malkhi, Gopal Pandurangan, and Kunal Talwar. Efficient dis- tributed approximation algorithms via probabilistic tree embeddings. In Rida A. Bazzi and Boaz Paut-Shamir, editors, Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21 2008, pages 263 272. ACM, 2008. doi: 40.1145/1400551.4440 14007877. URL https:///oi. org/ 10. 00145/140070 1400787.
Melanie Kircheis, Daniel Potts, and Manfred Tasche. Nonuniform fast fourier transforms with nonequispaced spatial and frequency data and fast sinc transforms. Numer. Algorithms, 92(4): 2307-2339, 2023. doi: 10.1007/11075--22-013888 07775-022-018888
URL https://doi. otwp./...g11111
Kyle Kloster and David F. Gleich. nearly-sublinear method for approximating a column of the matrix exponential for matrices from large, sparse networks. In Algorithms and Models for the Web Graph: 10th International Workshop, WAW 2013, Cambridge, MA, USA, Decem- ber 14-15, 2013, Proceedings, page 68-79, Berlin, Heidelberg, 2023. Springer- ISBN 978-3-319-03535-2 doi: 10.1007/978-3331--033333 6. URL https:///doii http///.....g/1....0...... 978-3-319- 9_66669966..
Ioannis Koutis and Gary L. Miller. A linear work, o(n1/6) time, parallel algorithm for solving planar laplacians. In ACM-SIAM Symposium on Discrete Algorithms, 2007. URL https://api.
semanticscholar org/ worg/Corpp Corpus 9556221..
Ioannis Koutis and Gary L. Miller. Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning. ACM Symposium Parallelism in Algorithms and Architectures, 2008 URL httpp:://ae //api http://app.ssaatiieeeeeooee sewanticscholeseeeo.o. org/ :
Joannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving sdd systems, 2010.
Ioannis Koutis, Gary Miller, and Richard Peng. A nearly-mlogn time solver for sdd linear systems, 201
Ioannis Koutis, Gary L. Miller, and David Tolliver. Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing. Comput. Vis. Image Underst., 115(12):1638-1646, dee lb. ISSN 1077-3142.
doi: 10.1016/..viu.2011.000011 URL
https://doi. org/10. 1016/j-oeeej cviu.. 2011. 15......00 013.
Ioannis Koutis, Gary L. Miller, and Richard Peng. A fast solver for a class of linear systems. Commun. ACM, 55(10) oct 2012. ISSN 0001-0782, doi: (0.1145/234773622447555 URL
https://doi. http://....rrr//111.1144////7/// 2347759.
Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5(1), January 2020. ISSN 2364-8228, doi: 10. 10.1007/s41109-009-0099 URL attp://ds. doi. wot. 100.11110000///10000100000
William Leeb. Approximating snowflake metries by trees. Applied and Computational Harmonic Analysis, 45, 12 2016. doi: 10.
Shengjie Luo, Shanda Li, Tianle Cai, Di He, Dinglan Peng, Shuxin Zheng, Guolin Ke, Liwei Wang, and Tie-Yan Liu. Stable, fast and accurate: Kereeiized attention with relative positional encoding. In Marc" Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 227922222222 22807, 2021.
14

---

Bruce M. Maggs, Gary L. Miller, Ojas D. Parekh, Ramamoorthi Ravi, Sha-Sha Leung, and Maverick
Woo. Solving symmetric diagonally-dommnnat systems by preconditioning. 2003. URL https:
sepesstimnttcccchooo.. org/ htg/CorrussIll ID 1593940.
Per-Gunnar Martinsson, Randomized methods for matrix computations, 2019.
Facundo Mémoli. Gromov-waseertein distances and the metric approach to object matching.
Foundations of computational mathematics, 1 11:17-4887 2011.
Cleve Moler and Charles Van Loan. Nineteen dubious ways to compute the exponential a matrix, twenty-five years later. SIAM Review, 45(1):3-49, 2003. doi: 10. 10.1137/500361 04577/5000611450441110 445024180. URL
https://doi. org/10. 10. 11.11.117//S001 1137/$003614450241888
Gerald Moore. Orthogonal polynomial expansions for the matrix exponential. Linear Alge- bru and its Applications, 435(3):537-559) 2011. ISSN 0024-3795. doi: https:/doi..or//10
URL hwtph::tts/e/t httpp://wwwsssceneediiieee www.nccdiieectt.....m.m.m..
$0024379510004842. Special Issue: Dedication to Pete Stewart the occasion of his 70th birthday.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In JCML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL WWw. www.hheaaaainnnn.....ee.eeegeeee io.
Elchanan Mossel. Distorted metrics trees and phylogenetic forests. IEEE ACM Trans. Comput. Biol. Bioinform. (01)::08-116 2007. doi: 10. N0.1109/TCBB.200.. URL https://doi org/ 10.
2007 1010.
Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: A survey. Journal of Artificial Intelligence Research, 72:943-1027, November 2021. ISSN 1076-9757. doi: 10.1613/ jair. mair...1325.. URL http://dx; doi org/10 10. 1613/jair 13225.
Gabriel Peyré and Marco Cuturi. Computational optimal transport. Found. Trends Mach. Learn., 11(5- 007, 2019. doi: 10.1561 10.1561/2200000073. URL https: org/10 10. 1561/2200000073..
Tobias Pfaff, Meire Fortunato, Alvaro Sanchez-Gonzalee and Peter W. Battaglia. Learning mesh- based simulation with graph networks. In 9th International Conference on Learning Repre- sentations, ICIR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https://opennreiee:
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In John C. Platt, Daphne Koller, Yoram Singer, and Sam T. Roweis, editors, Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-Fith Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007, pages 1177-1184. Curran Associates, Inc., 2007.
Youcef Saad and Martin H. Schultz. Gmres: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on Scientific and Staristical Computing, 7(3):856-869, 1986. doi: 10.1137/090705. URL https: //doi. org/10 10. 1137 1137/0907058.
Jonathan Shewchuk. An introduction to the conjugate gradient method without the agonizing pain. Technical report, USA, 1994.
Vikas Sindhwani, Tara N. Sainath, and Sanjiv Kumar. Structured transforms for sootl-fo deep learning. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Confer- ence on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 3088-3096, 2015. URL https::t////et 2aaa//883300e44222000000005ee222 225.eeeedd4005111e226666666 Abstract. html.
Daniel A. Spielman and Shang-Hus Teng. A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning, 2008.
Daniel A. Spielman and Shang- Hua Teng. Spectral sparsification of graphs, 2010.
15

---

Daniel A. Spielman and Shang- Hua Teng. Nearly- time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems, 2012.
Anna Thomas, Albert Gu, Tri Dao, Atri Rudra, and Christopher Ré. Learning compressed trans- forms with low displacement rank. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances Neural Information Processing Systems 31: Anmual Conference Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 9066-9078, 2018.
Mikkel Thorup. Undirected single source shortest path in linear time. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997, pages 12-21. IEEE Computer Society, 1997. doi: 10.1109/SFCS.199 6996086. URL https:/ / org/10 1109/99C9SS 1997 646088.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, V. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5998 00086, 2017.
Titouan Vayer, Lactitia Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty. Fused gromov- wasserstein distance for structured objects: theoretical foundations and mathematical properties. CoRR, abs/ 1.02834, 2018. URL /tatp://arxiv...//
abs/ 11111.111.11111 02834.
Ailong Zheng Victor Y. Pan. Superfast algorithms for cauchy-like matrix computations and extensions. Linear Algebra and its Applications, 310(1-3):33-00, 2000. URL https:
//www www.sssceecedirec....m www.ssciincaaa.ooccccccccccoocoe /ttpa//c///atttccaa/aa/////////0
Ziheng Wang. Sparsednn: Fast sparse deep learning inference on cpus. CoRR, abs/2101.07948, 2021.
URL https: httppp://aaaxi..oom www.or////////ooooe 011.//991..........
Ryan Williams. Matrix-vector multiplication in sub-quadratic time: (some preprocessing re- quired). In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, page 995-1001, USA, 2007. Society for Industrial and Applied Mathematics. ISBN 9780898716245.
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes, 2015.
Fuxun Yu, Zirui Xu, Tong Shen, Dimitrios Stamoulis, Longfei Shangguan, Di Wang, Rishi Madhok, Chunshui Zhao, Xin Li. Nikolaos Karianakis, Dimitrios Lymberopoulos, Ang Li, Chenchen Liu, Yiran Chen, and Xiang Chen. Towards lateney-aware DNN optimization with GPU runtime analysis and tail effect elimination. CoRR, abs/2011.03880 2020. URL httpp:://aaatt org/ abs/2011 0tt.//001.00.......
Fuxun Yu, Di Wang, Longfei Shangguan, Minjia Zhang, Chenchen Liu, and Xiang Chen. A survey of multi-tenant deep learning inference on GPU. CORR, abs/2203.099 099000, 2022. doi: 11448500ARXXIV.220.00000
URL httpp:://ot org/10. 000.0455///// arXiv 22033 09040.
Qingnam Zhou and Alec Jacobson. Thingil0k: A dataset of 10,000 3d- printing models, arXiv preprint 1rXiv 2016.
16

---

A Theoretical results
In this section, we provide proofs of all theoretical results in the paper.
A.1 Proof of Lemma 3.1
Proof.
We will apply Lemma 7.19 from [Cygan et al., 2015] (that we provide also below for reader's s convenience) and its algorithmic proof. We refer to Cygan et al. [2015] for a definition of the related graph terms.
Lemma A.1. Assume that G is graph of treewidth most k, and consider nonnegative weight function w V(G) + R20 on the vertices of Then in there exists a 1 -balanced separator of size most k + 1.
Note first that for each rooted tree, we can compute the size of each of its rooted sub-trees (and store it in the root of the sub-tree) in the linear time, simply by applying dynamic programming. We can now apply the above lemma for the tree G K. with the weight function that assigns weight = 1.0 for each vertex. By following its algorithmic proof (and using breadth first search for tree exploration), we can obtain node p and sub-trees Tı, Ti rooted in vertices connected with p, with the following properties:
U(.))U...UV(( U (p) V(K),
. IV(T.)) S (VC)) for i l,.., / and where || stands for the set size.
We then choose the first index k such that [V(Ti)] +... IV(Ta)] > 3 V(K)). Note that such an index it exists and define as Kleft a sub-tree of K. induced by the set: (..))...VV(T U Up) and by Kright a sub-tree of KC induced by the set: V(T&) U ... V(T) U {p}. Note that the triple (Kieft Kright p) satisfies the requirements of Lemma 3.1. That completes the proof.
1 because the above and the fact that our tree has at least six vertices. We
A.2 Fast Approximate Tree-Field Integrators
If matrices M = [f + +)) from Sec. 3.2.1 do not support fast matrix-vector multiplication, the question arises whether fast approximate procedures can be applied.
A.2.1 Random Fourier Features (RFFs)
Assume that the Fourier Transform (FT) of f exists and denote it by T C C. Note that f is the inverse FT of and can be re-written as f(z) f& exp(2niwz)r (ww Therefore, the following holds:
f(z + Ms) = exp(2xiwx.) exp(2rioy,)
(8)
We conclude that for any probabilistic distribution P on R with pdf p. f(x;; + Mj) can be re- written as: f(x + y1) = Elu(,,)) (((,)), where random R + I is given as: ((()T = Vim (Vrren)) exp(2niwit)
for w1, wi...,, Win P and m N4. Thus matrix M can be unbiasedly
approximated as: M UW for U Raxm W R.xm with rows given by ((zz)T..... ((..)) respectively. Matrix-vector product Mv can be then unbiasedly approximated and ((v1) "..,))"...,,,,)))))) (vv) as U(W v) and computed in time O((a + b)m) For m < a+t substantial computational gains are obtained. In particular, if m Ollog - b)). the approximate cociinatteffinneee f-integration is conducted in time O(N log*+((N) (N)). Note that m controls estimator's variance, thus decreasing increases the error.
_bb
A.2.2 Non-Uniform FFT (NU-FFT)
We will now propose closely-related method, that relies the non-uniform FFT (NU-FFT),
"See [Greengard and Lee, 2004] for excellent introduction.
17

---

Denote: g = Mv for a given v= (U.,..,.b))' E ERR. Define: g(x) f(x where P is given as: P(z) = Σj= 0z - 22),, and furthermore: (1) 6 is a delta-Dirac function, (2)
2j -リj Our goal is to efficiently evaluate function in points: ".)....aa...
Assume that the inverse FT of g exists and denote it by 1) C + C. Note that g is the FT of
and can be written as: g(z) = Jx n((w) exp( ( --riirr)ddd Since g is also a convolution of f and
P. 17 is a product of the inverse FTs: p and respectively. Therefore, we can write: g(x)
Ja ((pW)) R(w) exp( expp(2niie --riiw))dd where R(w) = Σj= 1ij exp(2riwzz). Now, function can be evaluated for {ai...... .T
I'a J as follows: (1) quadrature method is applied to obtain points: Wi.... (and corresponding weights) for the approximate computation of the integral defining g. (2) the NU-FFT is applied to compute R(w) simultaneously in those points in polylog- polylog-linear time, (3) given pre-computed (p(w,) R(w., )[= (and the quadrature weights), NU-FFT is applied again to compute seadrature-base approximation of g.
The f-integration process applying this method runs in volylog-linear time since the computation of g Mv takes polylog- time. prominent application given as: f(xx = sin(z) with
p being a renormalized indicator of belonging to interval |-0.5, 0.5). In this setting, the integral defining g thus limited to 1-0.5, 0.5]. Interestingly, for f()) sin(.) we can also apply methods from Sec. 3.2.1 (see: our discussion below on the trigonometric case).
A.2.3 Additional implications of Lemma 3.3
Products of exponentials and polynomials: Note that a Hadamard (element-wise) product of two outer- matrices is itself an outer-product matrix. Using the analysis from the polynomial and exponential cases, we conclude that M is a sum of a constant number of terms, each being an outer-product matrix. Thus the same conclusion follows.
The case of the trigonometric f: If f(z) = cos(x) then it can be re-written as: f(x) = 4ex(())) Observe that the cordiality property is preserved under linear combination of the finite number of cordial functions. We can thus conclude that analogous results as the above for fx) = (Xz) can be derived for f(z) cos(z). That is also the case for f(x) sin(x) that can be re-written as: fxx exp(ix) exxl iiz) In both cases, we extend the domain from TR to C, but this does not affect the analysis.
2
2i
So far we have not put any restrictions on the tree weights. If we restrict all weights to be the same (without loss of generality, equal to onc), then the problem becomes easier. In this case for any function f. matrices C' and C are Hankel [Brent, 2010] (constant on each anti- anti-diagonal and belonging to LDR class). Then, matrix-vector multiplication can be done in O((a + b) log(a- + b)). The analysis from the proof of Lemma 3.3 for d = 1 can be repeated. We conclude that f-integration can be conducted in ONN (NV) time for N-vertex unweighted trees and any f R2 R. This was already proven in [Choromanski et al., 2022].
Trees with positive rational weights: Assume that tree weights take values of the form: ( :e:ee (1...,p)) }}} for some p&g N4. Then, matrices C and CT do not need to be Hankel, but can be embedded into Hankel matrices with rows/columns corresponding to distances L from the pivot, where / = (0, .... mp} and ma is the largest distance between a vertex and the pivot. Tensor X can also be padded into a larger one with extra rows/columns (corresponding to unrealized distances) set to zero. If p is constant, the asymptotic time complexity remains the same as in the previous case, but the algorithm might not be practical since the number rows and columns grows by multiplicative factor of p. For certain non-cordial f. the algorithm can be modified for potential gains.
q
B Additional Related Work
In this section we provide additional related works. One of the methods to tackle this problem is via iterative methods [Koutis et al., 2012] like Arnoldi iteration [Amoldi, 1951], I, Conjugate Gradi- ent [Shewchuk, 1994] and the celebrated Spielman-Teng algorithm [Spielman and Teng, 2012] for symmetric diagonally dominant (SDD) matrices. There are number of extensions and variations of the above methods [Blelloch et al., 2011, Boman et al., 2008, Christiano et al., 2010, Koutis and
18

---

Miller, 2007, Spielman and Teng, 2008, Daitch and Spielman, 2008, Koutis and Miller, 2008].They mainly take into account the structure of the matrix (SDD) [Koutis et al., 2010, 201 1a, 2012], embed- ding of graph into low stretch spanning trees [Elkin et al., 2005], graph sparsification [Spielman and Teng, 2010] and the choice of a good pre-conditioner [Maggs et al., 2003, Koutis et al., 201 1b]. We want to emphasize that the research on low stretch trees for general graphs is orthogonal to the main topic of this work. In our manuscript, we show in particular how to conduct efficient integration on arbitrary trees. Thus our work can be naturally combined with those algorithms to leverage all the above low stretch tree constructions for a better approximation of the graph's 's metric.
The other class of method comes from the celebrated work of [AI-Mohy and Higham, 2011] and there are a number of extensions of this work [Kloster and Gleich, 2023, Al-Mohy and Higham, 2010, Moore, 2011, 1, Moler and Van Loan, 2003, Auckenthaler et al., 2010].
Another class of methods is via sampling, where one samples subset of large matrix, which is then used to approximate the matrix-vector multiplication (i.e. Monte Carlo sampling) methods [Drineas al., 2006, Drineas and Kannan, 2001, Acebron, 2019, Acebron et al., 2019, Benzi et al., 2017, Martinsson, 2019].
We note that none of these methods are directly applicable in our cases our f-matrix is neither Hermitian or SDD. The randomized algorithms are harder to use in the setting of training of a neural network. Moreover our method is exact on trees, where all the above methods approximations.
C Topological Transformers
Algorithm 1 General Efficient Low-Rank Masked Attention from Choromanski et al. [2022]
Input: Query/key matrices: Q K E Lxdqx, value matrix V E Rixxd mask M E Rixt. procedure FastMultM R- + R calculating Mx (or its approximation) for the input R² kernel feature map: Φ: Rd + RT. vec(-) denotes vectorization.
Output: Masked low-rank attention embeddings using ó.
1. Compute matrices V1 E [24((mmd) V E & with rows defined as: VL. vec(o(k, Jv:).
V?. = oT,,),, where k,/v, stands for the ith row of K/V.
2. D = [astMullt (V?)), ..., Must (V1 mma)] RLxmd
2 :=
[FastMultm V3),, Fast (V ml E R 1. for v denoting ith column of 1/2
Output the embedding r, of the ith tokens as: r; = ((q.) (Dv where qi is the ith row of Q
$(q, (D.)
and devec(-) devectorizes its input back to ma
We now recall the formulation of general masked transformers.
Let us denote by L the number of input tokens. The attention used in regular Transformer linearly projects their representations into three learnable matrices Q K RLxxde V E Rexd called queries, keys and values respectively.
Definition C.1 (general masked attention). General masked attention is given by the following equation, where M E R is the mask matrix, and A E RLXL is the so-called masked atlention matrix (MAM): which is defined as:
(Q, V V. = AV, K(, D diag( A1).)
where O denotes the element-wise (Hadamard) matrix product, K Rdd x Rd + IR is some kernel function and K(Q, K) is kernel matrix defined as: K(Q, K)., K(q kj. for the ith row qi of Q and the jth row k, of K respectively. We call A' K(Q, K) the unmasked attention matrix (UAM). Note that when K is the softmax function, we recover the well-known attention mechanism in Transformers.
Here 1, is the all-ones vector of length L,, and diag(.) is a diagonal matrix with the input vector as the diagonal. The time complexity of computing (9) is ((L2d).
19

---

100, numm d den:
Training Loss
100, numt: don: d
Iterations
Figure 8: Relative Frobenius norm error as function of the number of training iterations for different sizes and learnable quadratie f. We report the results for mesh graphs from Thingi10k.
If the kernel K admits (at least in expectation) dot-product decomposition, i.e. K(x,y) [[ő(x) o(y)] for some mapping: ø Rd - R (and some 0). o(u) is called (random) feature map (RFM) for e IR. For Q', K' E IR with rows given as ((q,)) and o(k) )T
respectively, RFM-based kernel linearization leads directly the efficient unmasked attention mecha- nism of the form:
Attk A (Q,K, V) D (Q(((("())) VV),
(10)
D = diag( Q Q'((") 1z)).
Here Attk stands for the approximate attention and brackets indicate the order of computations. Such mechanism characterized by time complexity O as opposed to ( I) for regular attention. If m < I., computational gains obtained.
The central question in [Choromanski et al., 2022] was how to incorporate the masking in the linear attention above. Note that in this case A' is never materialized. Building the work of [Luo et al., 2021], the authors [Choromanski et al., 2022] propose a general algorithm that efficiently implements masked linear attention.
In this work, we use different mappings (see Table 1). Our key contribution in this work is to propose novel mask matrix M and the implementation of fast matrix multiplication by M. The above result then allows to construct novel classes of Topological Transformers.
D Experimental Details and Additional Experiments
In this section, we provide additional details regarding the experimental setup and present addi- tional results from our experiments. Our code is available at https: thub. cww/br FastTree Integrator. Specifically, we provide there the code for: (1) our algorithm leveraging IntegratorTree data structure (depicted in Fig 1). (2) adaptation the Gromov-War wassov--ssssttnn-ttyeeee computation, (3) graph classification and (4) experiments on interpolation on meshes.
D.1 Additional experiments for graph metric approximation with fdistancc matrices
We present additional results for the training loss, relative Frobenius Norm Error (c), for more samples from the Thingi 10K dataset (to complement the results in Fig. 6). In Fig. 9, we observe that in most cases having rational functions with higher polynomial degrees results in lower training loss.
We also perform similar experiments for graph classification the CUBES dataset Hanocka et al. [2019]. Specifically, we investigate how the polynomial degree affects the graph classification performance in Fig. (left). We observe that increasing the polynomial degree improves the classification accuracy up to a certain degree. For the same dataset, we also compute the training loss for different polynomial degrees in Fig. (right). Similarly, functions achieve lower training loss for fitting the polynomial coefficients.
observe that higher-degree rational
Moreover, we benchmark FTFI on ModelNet10 [Wu et al., 2015). a dataset for 3D Point Cloud (PC) classification. For each PC, we create an e-neighborhood -rrphh and use FTFI for graph classification The Shortest Path kernel achieves an accuracy of 39.6%, whereas FTFI with the degree-2
20

---

31-
30
20
Accuracy
28
27
26
25
23
40
100
ftxi=x GAFGI GRR2) CRF(3 GRF(4)
Itorations
Figure 9: Left: Variation in FTFI performance with different f-distance functions the CUBES dataset. We use general rational functions (GRF) of varying polynomial degrees. GRF()) indicates a rational function of the i-th degree. We observe a general trend of accuracy increase with function complexity up to a certain degree. The coefficients of the GRF were learnt using a few graph instances. Right: We show the training loss curves for estimating the coefficients of the rational function, f. for samples in the CUBES dataset. We report the training loss for rational functions with varying polynomial degrees. We observe that the training loss lower when use rational functions with high-degree polynomials.
polynomial improves the accuracy to 44.2% (10% relative improvement over the baseline), similar to the observation in 9.
D.2 Integration of FTFI into GW-style algorithms
GW
FTFI-GW
Time (s)
1600
800
2000
4000
6000
8000
Number of Vertices
Figure 10: Comparison of field integration time between GW and FTFI-GW. We observe that FTFI achieves significant computation time gain over the baseline.
Wasserstein distance has found many uses in MI, particularly due to it's principled approach to compare probability distributions. Gromov Wasserstein Mémoli [201 1] discrepancy an extension of Wasserstein distance to graph structured data, with lot of downstream applications like graph clustering and classification. Inspired by the work of [Choromanski et al., 2023], we follow the exact same procedure in the integration of FTFI in the conditional gradient algorithm. The FTFI can be injected seamlessly in place of the Fast Matrix Multiplication (FMM) algorithms in Algorithm 2 and Algorithm 3 (see [Choromanski al., 2023])-
Our method GW-FTFI run consistently 2-6x faster than the baseline methods using the Shortest Path kernel, with no drop in accuracy in computing the associated costs (Figure 10). The plots shown are obtained by averaging over seeds and random trees various sizes. For the baseline experiments, we use the implementation from the POT library [Flamary et al., 2021].
D.3 Interpolation on Meshes
In this section, we present implementation details for the mesh interpolation experiments in run a computer with 19-12900k CPU and 64GB memory.
Section 4.2. All experiments
In the vertex normal prediction task Section 4.2, we choose 40 meshes for 3D-printed objects with wide range of size from the ThingilOK [Zhou and Jacobson, 2016] dataset with the File IDs:
21

---

Table 2: Statistics of the graph classification datasets used in this paper.
Avg. Nodes
Avg. Edges
Node Labels
Node
DATASETS
Graphs
Labels
Attributes
17.93
7
PTC-MR
344
14.29
14.69
ENZYMES
600
32.63
62.14
3
18
PROTEINS
1113
39.06
72.82
3
D&D
1178
284.32
715.66
82
IMDB BINARY
1000
19.77
96.53
IMDB MULTI
1500
13.0
65.94
NCII
4110
29.87
32,30
37
COLLAB
5000
74.49
2457.78
REDDIT BINARY
2000
429.63
497.75
MULTI-SK
4999
508.52
594.87
REDDIT MULTI-12K
11929
391.41
456.89
Table 3: Feature processing time of FTFI compared to exact shortest path kernel computation. We observe that FTFI achieves significant speedups up to 90% reduction in processing time. All times reported in seconds (s).
DATASETS
IMDB BINARY
IMDB MULTI
REDDIT BINARY
REDDIT MULTI-SK
REDDIT MULTI-12K
COLLAB
Algoritim
BGFI
5.6
7.6
3371.9
6267.6
8086.3
209.1
FIFI
4,3
4.7
338.2
755.3
1959.5
232.4
Improvement
+23.2%
+38.2%
+90.0%
+88.0%
+75.8%
-11.1%
DATASETS
Algorithm
MUTAG
ENZYMES
NCI1
PTC-MR
D&D
PROTEINS
BGFI
0.88
3.68
32.8
0.89
715.4
14.9
FTFT
0.37
4.39
20.2
0.93
325.3
18.6
Improvement
+58.0%
-19.3%
+38.4%
-4.5%
+54.5%
-24.8%
[60246, 85580, 40179, 964933, 1624039, 91657, 79183, 82407, 40172, 65414, 90431, 74449, 73464, 230349, 40171, 61193, 77938, 375276, 39463, 110793, 368622, 37326, 42435, 1514901, 65282, 116878, 550964, 409624, 101902, 73410, 87602, 256172, 98480, 57140, 285606, 96123, 203289, 87601, 409629, 37384, 57084]
For both FTFI and the baseline BFFI methods, do grid- search over the hyper-parameter for each mesh and report the pre-processing time associated with the hyper-parameter(s) that give(s) us the best cosine similarity.
D.4 Additional Details on Graph Classification
We conduct graph classification experiments wide range of benchmark datasets. We report the dataset statistics for the graph classification datasets in Table More details about the datasets are available in Morris et al. [2020]. To evaluate the performance of the different kernels, employ the framework proposed by [Errica et al., 2020]. In particular, 10-fold cross-valis cross-validation used to obtain estimate of the generalization performance of our method and the bascline method. We repeat this cross validation experiment 5 times to get a robust estimation and report the standard deviation for each setup.
To obtain graph features, we follow the approach presented in [de Lara and Pineau, 2018). In this setting, we obtain the k-smallest eigenvalues from the approximated kernel from FTFI and forward these features to a random forest classifier for classification. For BGFI, we perform same process obtaining the k-smallest eigenvalues from the exact shortest kernel. FTFI achieves similar performance to the BGFI while being significantly faster. We tune the hyperparameter independently for each method.
22

---

In Table 4, we report the results for a wide range of baselines and compare FTFI. We observe that FTFI achieves competitive performance among various strong kernel- classification baseline approaches. Note that FTFI results are not directly comparable with other approaches, as FTFI constructs an intra-graph kernel while other methods use inter-graph kernels. Despite the afore- mentioned considerations, we contend that positioning our results within the broader framework of alternative methodologies demonstrates that FTFI remains a compelling approach, owing to its speed and comparable classification accuracy.
D.5 Additional details on experiments for Topological transformers
In this subsection, provide additional training details for image classification tasks. Table and table 6 present the architectural as well as the training details.
We train the ViT models starting from their pretrained checkpoint (pretrained on ImageNet-21k), We replace the dense attention ViT by the Performer attention (see Equation 10). We use Algorithm to efficiently incorporate the mask matrix M in the attention mechanism.
D.5.1 ImageNet
We have already provided comparison with SOTA efficient-aateention methods: low-rank attention Transformers in Sec 4.4, quality-wise. On standard ImageNet benchmark, our best Transformer with FTFI provide 78. 1.5% accuracy, as compared to 76.37% of the best low-rank -attention variant (obtained by testing three different linear variants). That gives 1.78% accuracy improvement with only extra trainable parameters per head (36 extra trainable parameters per layer). We have also run the experiments with cosFormer. It achieved 76.3% accuracy (consistent with what is reported in the literature, see [8]), lower than both: our method and the best tested low-rank attention variant. The RF-Gat FF-GGae--Gaud Gaussian achieved 76.35% accuracy, which is is still lower than both: FTFI and the best tested low-rank attention variant.
D.5.2 Places365
We have also conducted tests on another challenging dataset: Places365, In the paper, we report 1.71% accuracy improvement over low-rank attention Transformer (56.51% 1% accuracy 54.8% accuracy). For the rebuttal, we also run the experiment with cosFormer which achieved 55.4% accuracy (consistent with what is reported in the literature, see: [8]). This is still 0.93% behind our method. The RF-GGat-Gauusian achieved accuracy 55.1% 1%, lower than this of cosFormer.
D.5.3 I-naturalist 2017
I-naturalist is yet another challenging dataset, with 10K classes, diverse image quality and significant class imbalance. Transformer with FTFI provides 1% accuracy improvement over its regular low- rank attention counterpart and the cosFormer. Furthermore, FTFI achieved 0.8% improvement over RF-GGate-Gaussin The convergence of the FTFI variant is 20-23% faster than this of its regular low-rank attention counterpart, the cosFormer and TF-GGae--Gassinn
D.6
Video Vision Transformer
VIVIT ([Arab et al., 2021]) is a novel architecture that adapts the Vision Transformer (ViT) for video processing. It efficiently handles the spatiotemporal dimensions video data by factorizing the input and applying attention mechanisms across both space and time. This allows VIVIT to capture complex motion patterns and long-range dependencies in videos.
Applying FTFI with topological masking mechanism to the ViVIT architecture (factorized Trans- former model variant, trained from scratch, as described in Arnab et al. [2021]) results in 0.8% absolute improvement on the Kinetics dataset ([Kay et al., 2017D). The experimental setup fol- lows Arnab al. [2021]. To the best of our knowledge, this is the first application of Topological Transformers to video data.
23

---

Table 4: Comparison of FTFI with a broad range of graph kernel-based classification approaches. We observe that FTFI achieves performance similar to that of Exact SP, its exact counterpart, across almost all datasets. The baseline results have been compiled from Nikolentzos et al. [2021]. OOT and OOM indicate that the corresponding algorithm ran out of time or memory respectively.
DATASETS
IMDB
IMDB
REDDIT BINARY
REDDIT MULTI-5K
REDDIT
COLLAB
Algorithm
BINARY
MULTI
MULTI-12K
VH
50.0 0.0)
(3.3
(+
20.0 0.0)
21,7 (# 1.5)
52.0 (# 0.1)
RW
64.1 4.5)5)
(+4.1)
OOT
OOT
OOT
68.0 (# 1.7)
SP
58.2 (.77
(*22.))
81.7 (#5)
(1
OOT
58.8 1.2)
GR
66.1 (1777)
(2
76.1 (#
34.7 (+
23.0 (# 1.4)
73.0 (=))
WL-VH
(1
(#4.4)
67.8 (#5)
50.5 (# 1.6)
38.7 (# 1.7)
78.3 (#1)
WL-SP
58.2
39.2
OOT
OOT
OOT
58.8 (# 1.2)
WL-PM
73.6
49.1 (#5.5)
OOM
OOM
OOM
OOM
WL-OA
(+
51.1 4.33)
89.0 (# 1.3)
54.0 (# 1.2)
OOT 39.6 1.4)
80.5 (.0)
NH
71.6 (.)55)
50.5 (=5.0)
81.2 (.0.)
49.9 (+
81.1 (# 2.4)
NSPDK
44.6 67.4 (333)
OOT
OOT
OOT
OOT
Lo-8
51.0 4.2))
39.8 (#2
OOT
OOT
OOT
OOT
SVM-0
52.3 4.0)
39.5
74.8 (.
1.11))
22.9 (.9.)
(=.01)
ODD-STh
65.0 4.00)
46.7 3.4)
52.1 (#22)
43.1 (+ 188
30.0 1.6)
52.0 (.I))
PM
66.3 (.22
46.1 3.8)
86.5 (#2.1)
48.3 (+)
41.1 (#6.
74.0 (:4))
GH
59.4 3.4)
39.5 2.6
OOT
OOT
OOT
60.0 (# 1.4)
SM
OOT
OOT
0OM
OOM
OOM
OOT
PK
51.7 (277
34.5(4..0)
63.9 (+3.0
34.9 (+
23,9 (+ 1.2)
ML
69.9 (.)
47.7 (#3.2
89.4 (+1.1)
35.4 (+2.0)
OOM
75.6 (# 1.6)
CORE-WIL WL-VH
73.5 6.1)
51.7 4.1)
73.0 (+4.5)
51.1 (1.
40.2 (# 1.8)
84.5 (.0.))
CORE-SP
68.5 (.9)
51.0 3.5)
91.0 1.8)
OOT
OOM
OOT
FTFI
65.1 (# 1.6)
46.4 (# 1.9)
83.7 (# 1.3)
43.8 (+.0)
31.8 (+ 0.3)
63.7 (# 0.3)
BGFI
65.1 2.0)
47.6 2.0)
84.3 3.5)
44.0 1.9)
37.6 (+ 0.3)
75.5 (# 0.3)
DATASETS
Algorithm
MUTAG
ENZYMES
NCII
PTC-MR
D&D
PROTEINS
VH
69.1 4.1)
20.0 (+
55.7 2.00)
57.1 (+
74.8 (+
71.1 (# 4.4)
RW
81.4 8.9)
(6.7
OOT
(4..()
OOM
69.5 5.1)
SP
82.4
3
(0.2 (2
77.9 (+:.5)
74.9
WL-VH
86.7 7.33)
(2..)
85.2 (.)
(4.44))
78.7 (+).3)
76.2 (+:))
WL-SP
(1
27.3 (3:44)
(.44
54.5
76.0
(+.11)
WL-PM
7.17)
57.5 (.8
1.77
(57.5)
OOM
75.9 (+:.8)
WL-OA
(4544)
58.0 (+50)
(5.7 (6
(4..0)
76.2 (4.9)
NH
88.3
54.5 (43.)
1.99)
74.6 (39.2)
75.0 (4
NSPDK
8.
42.2 (.00)
(#2.1)
(9..)
78.9
72.5 (+ 2.9)
ODD-STh
848.8)
(2.8)
75.2 (+
(9.8
76.4 (+55)
70.9 (+ 4.1)
PM
43.2 (25.8)
73.5 (+19)
(+.2
77.9 (+77.)
70.9 (+
GH
(45.8)
37.2 6.6
71.0
60.2
OOT
74.8 (+4)
SM
85.7
35.7 (.5))
OOT
(+)
OOM
OOM
76.6 (.2))
44.0 6.3))
82.1 (.1
65.1 (#5.6)
77.7 (+:22
73.1 (+:77)
ML
87.2 (.5))
48.5 7.8
79.7 1.8)
(+5.8)
78.6 (+:00)
74.2 (+:44)
CORE WL-VH
85.6 6.5)
51.7 7.00
85.2 (.2)
65.5 (+5.6)
79.5 (+3.2)
76.5 (+4.4)
CORE-SP
85.1 (2 6.8)
39.5 (2)33)
73.8 1.4)
(19.7)
79.3 (+3.8)
76.5 (1
FIFI
81.6 3.8)
34.6 1.0)
72.8
(# 1.2)
60.6 (11
73.6 (.1)
72.5 1.2)
BGFI
82.2 (+ 2.8)
42.5 + 1.8)
73.7 (= 1.2)
58.7 2.5)
74.8 (1 2.1)
71.7 (+ 2.0)
24

---

Table 5: Hyperparameters for the different ViT models used in this paper
Model
Heads
Layers
Hidden Dim.
MLP Dim.
Params
Patch Size
ViT-Base
12
768
3072 4096
86M
Vir-Large (16)
24
16
1024
307M
16
Table Hyperparameters for Topological Transformer experiments
Parameter
Value
Activation layer
gelu
Dropout prob
Atlention dropout prob
0.1
Optimizer
Adam
Learning rate
10-3
Batch Size
4096
Compute resources
x
TPUv3
Number of Epochs
300
Warmup
10K
weight decay
learning schedule
cosine decay
E
Broader Impact
We do believe that the potential impact of this work is significant, as providing both: (a) theoretical advancements in structural graph theory as well as (b) practical applications in (1) designing com- putationally efficient Transformers leveraging topological inductive priors, (2) graph classification and (3) interpolation manifolds. The core problem of fast multiplication with f-distance matrices plays an important role in various fields: physical sciences, chemistry, and network sciences. Our main contributions are algorithmic, with no clear negative side effects. While used in the context of Transformers, they should be though applied cautiously due to the nontrivial carbon emission footprint associated with training large Transformer models.
F Limitations
Currently, FTFI can be applied on general graphs via certain classes of trees defined on these graphs (e.g. spanning trees), with low-distortion trees being more preferable. It would be interesting whether the main concepts used in the FTFI algorithm (such as the theory of balanced separators) can be directly incorporated into efficient and exact algorithms operating on general graphs (or general sparse graphs that appear in most machine learning applications). Determining general conditions on the classes of graphs and functions ff under consideration that are sufficient exact sub-quadratic time integration is yet another important problem for future work.
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We give detailed explanations of our contributions in the introduction (page 2).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are clearly explained in Appendix F
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
26

---

Justification: We introduce the notion of our algorithm Fast Tree Field Integrator in section 3. We describe the main algorithm in detail and introduce the technical (theoretical) results. The proofs of these results can be found in Appendix A.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Training details to replicate each experiment are in the Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
27

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide the code as well details experiments in Appendix D.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
wwm.issiiiiiccyiiiccoocomoo for more details. Sttpl//ggiidd//ooeeeeee
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: CCodeeubeeeeeeeeeeeeee /nips. wttpcccpppppccceeececc..ccccctct /ttaa//geeeeee/eeeeeubaiiiiii ssi onnolicy))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All details are presented in Sec 4 and Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All experiments in the paper except for the ones using large Transformer models have been run multiple times using various random seeds and we report the relevant statistics. The experiments using Transformers are too expensive to run multiple times as the experiments are run on huge dataset like ImageNet.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
28

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report the compute resources used in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: / htt///nerrpppp cc htcpppplcc/////eeeceeeeeellllltt
Answer: [Yes]
Justification: All authors have reviewed the NeurIPS code of ethics and the research conform the code.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The broader impacts of our work is detailed in Appendix E.
Guidelines:
The answer NA means that there is no societal impact of the work performed.

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper is theoretical in nature and we are not releasing any new models or data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have properly cited all the papers that introduced various algorithms and data that are used this work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
30

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release the code for the main algorithm. The usage is detailed in the anonymous github repo.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: We do not conduct any research that involves crowd sourcing with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowd sourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
31

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "BCInzPfJFG", "reviewer": "Reviewer_SX39", "summary": "This paper proposes faster matrix multiplication algorithms for a class of structured matrices, namely, f-distance matrices, where the $(i, j)^{th}$ entry of the matrix is $f(\\text{dist}(i, j))$, for nodes $i, j$ in a graph. The authors propose an algorithm, referred to as Fast Tree-Field Integrators (FTFI), for the case of tree graphs (and in the experiments, for general graphs, the graph is approximated by its spanning tree).\n\nThe FTFI algorithm works as follows: first, an \"integrator tree\" is constructed (which is created only once for the f-distance matrix, and reused whenever this matrix is multiplied by another matrix). The integrator tree is a binary tree where each node is a subtree of the original tree. To obtain the two children of a node, they pick some vertex in the subtree (of the original tree) that this node corresponds to - this node will be called the \"pivot point\", and the subtree will be split into a \"left\" and \"right\" subtree at this pivot point.\n\nThis integrator tree is used to recursively compute the product of the $f$-distance matrix (denoted $M^G_f$) with another arbitrary matrix/tensor $X$. To compute the row of $M^G_f X$ corresponding to the vertex $v$, suppose $v$ is in the left subtree of the current node of the integrator tree. Then, we have to consider the contribution of rows of $X$ from vertices $j$ that are also in the left subtree (which is dealt with recursively) and vertices $j$ that are in the right subtree. In the latter case, the entry $f(dist(v, j))$ of the $f$-distance matrix can be written as $f(dist(v, p) + dist(p, j))$ where $p$ is the pivot point, and this property is leveraged to achieve a running time faster than naive matrix multiplication in several cases, such as when $f$ is a rational function or an exponential function.\n\nThe authors compare FTFI to BTFI (brute-force matrix multiplication in the tree setting), and other algorithms including BGFI (brute-force matrix multiplication without approximating the graph by a tree). The tasks studied include interpolation on meshes and graph classification. For interpolation on meshes, FTFI is the fastest in terms of preprocessing. It performs similarly to the SF algorithm (a state of the art algorithm for this problem), and performs worse than BGFI, which is a more brute force, but more accurate, algorithm. In the graph classification setting, FTFI gets similar accuracy as BGFI while being significantly faster.\n\nThe authors finally do experiments with FTFI on topological vision transformers. In a large scale setting, FTFI obtains a 7% improvement on ImageNet compared to the standard ViT performer (which obtains around 70% accuracy).", "questions": "- Why does BTFI require more time for processing than BGFI in Figure 4? Intuitively, they would require similar effort, and BGFI should perhaps be slower (with computing the shortest paths potentially having a longer running time for more general graphs than for trees).\n- Also, given that BGFI does significantly better than BTFI/FTFI in terms of cosine similarity, at the cost of a roughly 5x slowdown compared to FTFI according to Figure 4, is it better to use BGFI compared to FTFI? What are the considerations here?\n- Do the plots on the right-hand side of Figure 4 contradict the plots on the left-hand side of Figure 4? The second plot from the left in Figure 4 suggests that BGFI generally achieves greater cosine similarity than FTFI for various numbers of points (though it is slower) while the third plot from the left shows that FTFI is both faster and achieves higher cosine similarity than BGFI. How do you interpret the difference?\n- In Figure 5, on PTC-MR, why is BGFI slightly faster than FTFI? Is this a specific distribution of graphs?\n- For the experiments in Figure 6, the goal is to show that tree-based estimators can emulate integration on arbitrary graphs, using a rational function with quadratic numerator and denominator. I am not convinced that this experiment shows that tree-based metrics can emulate general graph metrics, since the MSE loss seems to plateau around 1. This seems a bit large given that the distribution of weights is taken from (0, 1). What is the distribution of graphs?\n\n========================================\n\nThese questions are addressed by the rebuttal, and I am increasing my score from 6 to 7.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The matrices studied in this work are far more general than those studied by previous works (structured matrices studied in previous works are exponentials of adjacency matrices, symmetric diagonally dominant matrices, power series of random walk kernels, boolean matrices).\n- The algorithm is interesting technically - decomposing the entries of the f-distance matrix to avoid the running time of naive matrix multiplication is a good idea.\n- The results are strong, particularly on graph classification.", "weaknesses": "- There are some questions I have about the experimental results, mentioned below in the questions section. If these questions are addressed, I would be willing to raise the score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**General comment:**\n\nWe would like to sincerely thank the Reviewer for the feedback.\n\n**Processing time of BTFI vs BGFI in Fig. 4:**\n\nThank you very much for an excellent comment. We have realized that for BTFI we unnecessary applied Kruskal algorithm two times to compute the minimum spanning tree. After the correction, BTFI pre-processing time is shorter than before, in particular a little shorter than this of the BGFI algorithm. FTFI is still the fastest and SF is still second fastest. Thus our claims remain the same. In the pdf attached to the rebuttal, we put in particular corrected first plot of Fig. 4. We will also put corrected Fig. 4 in the camera-ready version of the paper. Once more, thank you for catching this !\n\n\n**BGFI vs FTFI:** \n\nThe FTFI algorithm is designed to scale-up to massive graphs, where **5x** speedup differentiates between a feasible and non-feasible processing time. FTFI is the fastest method among all six tested algorithms (achieving 2.5x+ speedup over the second fastest method in Fig. 4), obtaining similar or better accuracy than other tested fast algorithms. Thus we recommend to apply FTFI for massive graphs, where the processing time of BGFI is not acceptable. Furthermore, for several meshes FTFI matches quality-wise BGFI, yet it might be hard to see that on the second plot, since the corresponding dots overlap (this is clearly illustrated in particular on the third plot; see also: our discussion on second vs third plot in Fig. 4).\n\nWe also would like to emphasize that we showed in Sec. 4.4 that FTFI is an option for Topological Transformers to provide accuracy-gains over regular ViTs. The ability to process massive graphs translates in this setting to processing high-resolution images or images partitioned into small patches (e.g. for pixel-to-pixel attention).\n\n\n**Second plot vs the third plot in Fig. 4:**\n\nThank you very much for the comment. Even though computational advantages of FTFI for mesh-graphs from Thingi10K dataset considered in the first part of Sec. 4.2 in general imply some accuracy loss as compared to the brute-force baseline, the gap depends a lot on the graph structure (this observation is aligned with the voluminous literature on the quality of tree-metric based approximation and a subject on its own). To show it, we created third and fourth plot in Fig.4 where we sampled two meshes of sizes 3K (the actually mesh size is ~2.7K) and 5K respectively (as described in the caption of Fig. 4). In the third plot, we demonstrate that the gap might not even exist. These were not “cherry-picked examples”. To see that note that even though in the third plot FTFI matches quality-wise BGFI, in the fourth plot we show that BGFI is the best accuracy-wise (with FTFI being second-best and the fastest). To sum it up, the role of the last two plots in Fig. 4 was to focus on a particular mesh (per plot) to make presentation more clean. Note that in the second plot lots of dots overlap due to different methods performing similarly accuracy-wise and thus some well-performing FTFI variants as the 3K-one can be easily missed. We will clarify it in the final version of the paper and improve second plot to make it more clear.\n\nTo be very specific, the sampled 3K- and 5K-size meshes from the Thingi10K dataset were of ids: 1514901 and 39463 respectively.\n\n\n**BGFI vs FTFI speed-wise in Fig. 5; PTC-MR:** \n\nThe Reviewer is correct, this is due to a particular structure of those graphs and the fact that they are very small (average number of nodes is only **14.29**, as shown in Table 2 in the Appendix).\n\n**Experiments in Fig. 6:**\n\nWe would like to emphasize that even though graphs’ weights in these experiments are taken from the interval (0, 1), the entries of the matrices under consideration are much larger since they encode distances of the paths. Thus in practice they can be of order a few hundred, since considered graphs have **800** nodes. SOTA non-learnable, purely algorithmic approaches based on low-distortion trees, such as Bartal trees ([1]) or Fakcharoenphol trees ([2]), providing log(N)lo log(N) and log(N) distortion ratio respectively, would lead to errors 9.0+. The goal of this experiment was to show that by learning functions of distances, this loss can be dramatically decreased, even if the underlying spanning tree is a minimum spanning tree (that can be quickly computed). Furthermore,  we showed that training can be done in sub-quadratic time by sampling a compact set of source-target points and computing shortest-path distances between them. Note that we used a relatively simplistic training setting with only **six** trainable parameters since function f was parameterized as a ratio of two quadratic functions.\n\nAs we explained in the caption of Fig.6, the graphs are obtained from a path on 800 nodes, by adding 600 random edges and assigning independent weights to them from the interval (0, 1). Thus considered graphs are sparse.\n\n[1] On approximating arbitrary metrics by tree metrics, Bartal, Y., STOC 1998\n\n[2] A tight bound on approximating arbitrary metrics by tree metrics, Fakcharoenphol et al., . J. Comput. Syst. Sci.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PgTFjikqpQ", "reviewer": "Reviewer_Lag9", "summary": "The authors propose an algorithm for exact polylog-linear multiplication for general weighted trees and cordial functions f, which leads to a fast algorithm for distance-matrix tensor multiplication as used in transformers and graph kernels. The core of the algorithm is a binary tree structure called integration tree, which allows to perform the integration using an efficient divide and conquer scheme. The authors show that, for matrices defined by d-cordial functions, the integration can then be done by O(N log^{d+1} (N)). The authors show that their algorithm improves runtime against naive baselines in graph classification, vertex normal prediction, interpolation on meshes and topological vision transformers.\n\nThe work in general is far away from my research area. Thus, my confidence is low and I feel not qualified to judge the significance of  theoretical contributions in this work.", "questions": "How does the quality vs. efficiency trade-off behave in the topological vision transformers experiment? It is only shown that the quality slightly improves but not if the method has an impact on transformer efficiency.", "limitations": "The authors briefly discuss limitations in the appendix.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The results suggests that the presented algorithm is clearly faster than brute force tree-field integration and that it does not negatively impact the quality of results on downstream tasks.\n- The technical and theoretical contributions seem to be well thought and thorough. The algorithm makes sense to me on a high level.\n- I reviewed this paper before and the presentation quality improved, making it a bit easier to understand how it embeds into related work and what its contributions are.", "weaknesses": "I agree with the authors that the tackled integration problem is relevant in many machine learning / deep learning models. It is unclear to me though how often the tree assumption is applicable. The practical experiments on topological vision transformers and graph classification, showing usefulness in practice. However, the experiments seem to be a bit inconclusive due to lacking trade-off analysis\n\nWhat this paper lacks is an experiment that conclusively shows that the presented algorithm can be integrated into a state-of-the-art method (such as general masked transformers on multiple tasks) and that it has a positive impact on the quality/efficiency trade-off.\n\nIt would be also helpful if source code would be released in order to replicate/verify results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**General comment:**\n\nWe would like to sincerely thank the Reviewer for the feedback.\n**We provide additional responses in the official comment titled: \"Additional responses for Reviewer Lag9\".**\n\n**A conclusive experiment showing integration into SOTA and positive impact on the quality/efficiency trade-off:**\n\nThank you very much for the comment. Following Reviewer’s suggestion, we have decided to extend our experiments on efficient Transformers, to provide a **conclusive** evidence of the broad applicability of the method for Transformers. We target efficient-attention methods (an important field of the research on Transformers), since our paper focuses on **computational efficiency**. Thus comparing quality-wise with brute-force quadratic-attention Transformers is not relevant. **We show that FTFI leads to consistent accuracy improvements over SOTA efficient-attention Transformer models, with no speed loss or even speed gains**. For the comparison, we chose in particular low-rank attention Transformers due to their conceptual simplicity and the fact that they are broadly applied in various fields, including vision, speech, NLPs, Robotics, see: [1], [2], [3], [4], [5]. The interest in low-rank attention led also to designing hardware-efficient algorithms to optimize its on-device performance ([6]). We also compared against popular cosFormer architectures ([7]) and modified low-rank attention mechanism with gating (RF-Gate-Gaussian) from [4]. **We have also added extra experiments with video input data.**\n\n[1] Rethinking Attention with Performers, Choromanski et al., ICLR 2021.\n\n[2] Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention, Katharopoulos et al., ICML 2020. \n\n[3] The Hedgehog & the Porcupine: Expressive Linear Attention with Softmax Mimicry, Zhang et al., ICLR 2024.\n\n[4] Random Feature Attention, Peng et al., ICLR 2021.\n\n[5] SARA-RT: Scaling up Robotics Transformers with Self-Adaptive Robust Attention, Leal et al., ICRA 2024, Bert Robotic Manipulation Paper Award.\n\n[6] Gated Linear Attention Transformers with Hardware-Efficient Training, Yang et al., ICML 2024.\n\n[7] cosFormer: Rethinking Softmax in Attention, Qin et al., ICLR 2022.\n\n[8] Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers, Choromanski et al., AISTATS 2024.\n\nWe present detailed comparison below.\n\n**1. ViTs - accuracy**\n\n**1.1 ImageNet:**\n\nWe have already provided comparison with SOTA efficient-attention methods: low-rank attention Transformers in Sec 4.4, quality-wise.  On standard ImageNet benchmark, our best Transformer with FTFI provide **78.15%** accuracy, as compared to **76.37%** of the best low-rank -attention variant (obtained by testing three different linear variants). That gives **1.78%** accuracy improvement with only **3** extra trainable parameters per head (**36** extra trainable parameters per layer). To understand how significant **1.78%** accuracy improvement on ImageNet is, note that the technique of self-supervised pre-training objective (masked patched prediction, inspired by masked language modeling), widely considered as providing a **significant improvement** of regular ViTs and adopted in most ViT repositories, yet requiring a completely different training procedure, provides **2%** accuracy gain on ImageNet. For the rebuttal, we have also run the experiments with cosFormer. It achieved **76.3%** accuracy (consistent with what is reported in the literature, see [8]), lower than both: our method and the best tested low-rank attention variant. The RF-Gate-Gaussian achieved **76.35%** accuracy, which is is still lower than both: FTFI and the best tested low-rank attention variant.\n\n\n**1.2 Places365:**\n\nWe have also conducted tests on another challenging dataset: Places365. In the paper, we report **1.71%** accuracy improvement over low-rank attention Transformer (**56.51%** accuracy vs **54.8%** accuracy). For the rebuttal, we also run the experiment with cosFormer which achieved **55.4%** accuracy (consistent with what is reported in the literature, see: [8]). This is still **0.93%** behind our method. The RF-Gate-Gaussian achieved accuracy **55.1%**, lower than this of cosFormer.\n\n**1.3. I-naturalist dataset:** \n\nI-naturalist is yet another challenging dataset, with **10K** classes, diverse image quality and significant class imbalance. Transformer with FTFI provides **1%** accuracy improvement over its regular low-rank attention counterpart and the cosFormer. Furthermore, FTFI achieved **0.8%** improvement over RF-Gate-Gaussian.  The convergence of the FTFI variant is **20-23%** faster than this of its regular low-rank attention counterpart, the cosFormer and RF-Gate-Gaussian.\n\n**2. ViTs - speed**\n\nIn the rebuttal, we also add speed tests, to completely describe quality-efficiency trade-off. Our Transformer with FTFI is  as fast as regular low-rank attention Transformers and cosFormer, and 10% faster than RF-Gate-Gaussian. It provides **25%** speedup over regular brute-force quadratic-attention ViT.\n\nThose speedups are for a setting with a default number of patches used in the brute-force variants of the architectures. With more patches, speed gains are even more substantial. However then brute-force variants are too slow to train and thus we could not incorporate those results into our studies.\n\n**3. Masked Transformers for videos**\n\nWe applied FTFI also for Transformers operating on videos. To the best of our knowledge, we are the first to use topological masking min that setting.\n\nFTFI applied in a topological masking mechanism in ViViT ([1], factorized Transformer model for videos,  trained from scratch) leads to the **+0.8% absolute** improvement as compared on the Kinetics dataset ([2]). **To the best of our knowledge, this is the first application of the Topological Transformers for videos**. \n\n[1] ViViT: A Video Vision Transformer, Arnab et al., ICCV 2021.\n\n[2] The kinetics human action video dataset, Kay et al., 2017.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f3LiWmAOyo", "reviewer": "Reviewer_o1jE", "summary": "The paper tackles the problem of integrating tensor fields defined on graphs. The paper suggests Fast Tree-Field Integrators (FTFI) that integrate tensors on weighted trees with reduced time complexity, which is based on their data structure called IntegralTrees (IT). The idea is original and new, and the algorithm is carefully designed. All the properties of Fast Tree-Field Integrators are theoretically supported and experimentally verified.", "questions": "In the experiments, the authors have only used minimum spanning tree (MST) as the tree approximation of a graph. On one side, this makes sense since the paper focuses on the fast computation of matrix-vector multiplication on a graph, not on choosing an appropriate tree. However, it seems to me that one reason of the relatively unsatisfactory accuracy (cosine similarity) of Fast Tree-Field Integrators (FTFI) is due to the distortion of the geometry of a graph by MST. As the authors have presented related work in embedding graphs to trees, I was wondering if we can get some improvements in accuracy when we use more advanced methods of embedding graphs to trees.\n\n========================================\n\nThe question is addressed by the rebuttal.", "limitations": "The authos have addressed the limitations that Fast Tree-Field Integrators (FTFI) can work well provided that a graph is well approximated by a tree. I do not find any societal impact of this work.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The idea of IntegratorTree (IT) is original and new. The structure of IntegratorTree is carefully designed to reduce the computational complexity. The method is widely applicable for many practically used functions, not restricted to Hermitian or SDD. All the properties of Fast Tree-Field Integrators are theoretically supported and experimentally verified.", "weaknesses": "The paper seems to consider the machine learning community as potential readers, but the underlying concepts are fairly unknown to the machine learning community. The reviewer also does not do research in integrating tensor fields on graphs, and it was a bit difficult to follow the concepts and structures in Fast Tree-Field Integrators (FTFI). I think this presentation problem can be greatly improved by providing examples or figures. For example, Section 3.2 would have been more easily grasped if the authors provided pictorial examples as Figure 1.\n\n========================================\n\nThis weakness about the presentation of FTFI is addressed by the rebuttal, so I am increasing my score from 6 to 7.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**General comment:**\n\nWe would like to sincerely thank the Reviewer for the feedback.\n\n**Improved presentation with the pictorial example in Sec. 3.2 (as Fig. 1):**\n\nThank you very much for the comment. Following Reviewer’s suggestion, we added a pictorial description of the divide-and-conquer method presented in Sec. 3.2. We have included it in the pdf attached to the rebuttal.\n\n**More advanced embeddings of graphs to trees for improved accuracy:**\n\nThank you for an excellent comment. It is indeed the case that FTFI in principle can work with any tree, not necessarily only Minimum Spanning Tree (MST). However if the pre-processing time, necessary for tree-construction, is itself quadratic in the graph size, that defeats the purpose of using FTFI. For that reason, we focused on trees that can be efficiently constructed. MST is a perfect candidate since it can be build in log-linear time. Furthermore, near minimum spanning trees, often provide constant average distortion ([1]). We want to emphasize that for mesh-modeling experiments in Fig. 4, FTFI for several meshes performs similarly accuracy-wise to the brute-force algorithm (as we show in the third plot on one 3K-size mesh example). This might not be clearly seen in the second plot, since many dots overlap there. We will clarify it in the camera-ready version of the paper.\n\nWe actually already applied more advanced tree embeddings of graphs for mesh-modeling, as shown in Fig. 4. We used in particular: (1) Bartal trees and ([2])  Fakcharoenphol trees (FRT, [3]), as well as non-tree embeddings leveraging small-separator factorization of mesh-graphs (SF), recently introduced in [4]. The Bartal tree approach provided some accuracy improvements over MST (the FTFI instantiation used in Fig. 4 applied MST), but at the price of 4x slower pre-processing time. The method applying Fakcharoenphol trees could be in practice applied only for very small meshes of sizes <=1K, due to the infeaibly large pre-processing time for larger graphs. The SF method was worse accuracy-wise than FTFI.\n\nWe have also conducted additional experiments, applying FTFI to masked Transformers for video data. FTFI applied in a topological masking mechanism in the ViViT architecture ([5], factorized Transformer model for videos,  trained from scratch) leads to the **+0.8% absolute** improvement as compared on the Kinetics dataset ([6]). **To the best of our knowledge, this is the first application of the Topological Transformers for video data**. If instead of the MST, a full grid was applied for masking, the additional improvement was only negligible ( **+0.2%**). That shows that using other, more sophisticated graph-embeddings would also lead to only marginal additional improvements.\n\n\n\n[1] On notions of distortion and an almost minimum spanning tree with constant average distortion., Bartal et al., STOC 2016. \n\n[2] On approximating arbitrary metrics by tree metrics, Bartal, Y., STOC 1998\n\n[3] A tight bound on approximating arbitrary metrics by tree metrics, Fakcharoenphol et al., . J. Comput. Syst. Sci.\n\n[4] Efficient Graph Field Integrators Meet Point Clouds, Choromanski et al. ICML 2023.\n\n[5] ViViT: A Video Vision Transformer, Arnab et al., ICCV 2021.\n\n[6] The kinetics human action video dataset, Kay et al., 2017.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nQh541tHck", "reviewer": "Reviewer_H9MT", "summary": "In \"Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers\", the authors propose a novel method for integrating scalar fields, and more generally tensor fields, on trees. Given an input tree and potentially multiple tensor fields, FTFI constructs an auxiliary binary \"IntegratorTree\" with nodes corresponding to sub-trees of the input tree. The efficiency of FTFIs is then demonstrated on a variety of experiments and tasks on synthetic and real-world datasets.", "questions": "In the introduction and related work, you talk about general graphs as an input (line 84), however, in section 3.1 you explicitly talk about the input tree. How do you turn the general graph into a tree? What information or what accuracy is lost in that process? Are there theoretical considerations that quantify this?\n\nThank you in advance for your answers!", "limitations": "The authors discuss limitations in the appendix.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. FTFI significantly improves the runtime in contrast to previous tree integration algorithms\n2. The paper conducts extensive experiments, showing promising applications with Topological Vision Transformers.\n3. The illustrations (Figure 1&2) are very well-made and illustrate the relevant concepts.", "weaknesses": "1. Figure 5 claims that FTFI achieves similar accuracy as its brute force counterpart BGFI. However, BGFI seems to outperform FTFI on almost all datasets and often with accuracy gains of >1%.\n2. Many graphs in practice are not trees. The paper does not discuss any theoretical guarantees or qualitative patterns on how well FTFI can be used as approximate integrators for almost tree-like and general graphs.\n3. In the conclusion, speedups of 5--13x while maintaining quality are claimed. Both of these claims don't seem to be supported by all experiments and should be framed more cautiously.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**General comment:**\n\nWe would like to sincerely thank the Reviewer for the feedback. **We provide responses below and in the official comment titled: \"Additional responses for Reviewer H9MT**.\n\n**Fig. 5: FTFI vs BGFI accuracy-wise:**\n\nThank you very much for the comment. Given the substantial speedups, often of the order of **1.5-2x**, we consider loss of accuracy of the order of **1%** small. Following Reviewer’s suggestion, in the camera-ready version we will avoid less precise phrases to describe the results in Fig. 5 (e.g. “similar accuracy”) and simply provide all the numbers describing accuracy-speed trade-off also in the comments. We also want to notice that for a fixed budget of training time corresponding to FTFI, the BGFI results accuracy-wise were much lower than those of FTFI. We will clarify it in the final version of the paper. \n\n**5--13x speedup claims in the conclusion:**\n\nThank you very much for the comment ! The 5--13x speedups were obtained for examples from Sec. 4.1 (Fig. 3). Those included both: synthetic networks as well as mesh-graphs of real objects. In that section, we could test the limits of our methods and consider graphs as large as **20K** nodes. The problem with using graphs of those sizes in downstream applications, where we compared different method accuracy-wise is that graphs with 15K+ nodes are infeasible for standard algorithms. Thus we needed to scale down graph sizes in those experiments and that of course made computational improvements smaller, yet still very significant.  For instance, for mesh-modeling (Fig. 4) we obtained **3x+** speedups over brute-force method and **2x+** speedups as compared with all other tested methods. For graph classification (Fig. 5), we obtained **1.5x-2x** speedups for many graphs. For Gromov-Wasserstein (Appendix D.2), we obtained up to **5x** speedups. \n\nThe exact statement in the conclusion section is: “Our methods provide significant (5-13x) speedups while maintaining the quality of their **exact counterparts**”. The “exact counterparts”-phrase is very important here. We do not claim that across all the experiments, we maintain the quality of previous more brute-force approaches. We claim that across all the experiments we maintain the quality of methods that use trees and apply brute-force integration on them (the exact counterparts). This is true, since our efficient algorithms is **numerically equivalent** to the one conducting brute-force integration on trees.\nWe will clarify it in the final version of the paper, by explaining what we mean by “exact counterparts”.\n\n**FTFI to approximate almost-tree like graphs and general graphs: theoretical analysis (PART I: SECOND PART IN THE EXTRA OFFICIAL COMMENT, PARAGRAPH: THEORETICAL GUARANTEES FOR  ALMOST-TREE LIKE GRAPHS):**\n\nThank you for an excellent question. **We provide the first part of the response here and the second part (where we explicitly provide guarantees for almost-tree like graphs in the official comment, title: \"Theoretical guarantees for almost-tree like graphs\").**\nThe general answer to the question of the quality guarantees of FTFI is that those are the derivatives of the guarantees of the distortion ratio of the underlying trees. The quality of the general graph metric approximation with tree-metrics is a research area on its own, with voluminous literature. We provided a summary in Sec. 2 as well as in Appendix B. Notably, tree-metrics is a well-established tool, used in several applications, e.g. in distributed & online algorithms and biology (see: [1,2,3]). Since in the presentation of the FTFI algorithm we did not focus on any particular tree construction, we did not provide corresponding theoretical analysis. However, since in the experiments we focus on minimum spanning trees (MSTs), as particularly easy to construct, we would like to note that the so-called near minimum spanning trees, often provide **constant** average distortion ([4]). In the camera-ready version, following Reviewer’s suggestions. We will discuss this construction and the corresponding theoretical results in more depth, as particularly relevant for us.\n\nWe want to emphasize that standard algorithmic distortion upper bounds on tree-metrics provide only **very loose** upper bounds for the distortion of the FTFI since our algorithm is applied in the ML setting, where the nonlinear mapping f is learned. Let us explain it in more depth. Assume that we want to approximate h(d), where d is the shortest path distance between two nodes: x and y in the original graph and h is some function. Assume also that in order to do it, we apply tree T. Assume that in that tree the distance between x and y is l. Then even if the distortion is large, i.e. l>>d, as long as we can find a function f such that\nf(l) accurately approximates h(d), the approximation quality will be good. All that is needed in addition to that is to make sure that f can be parameterized in such a way that it belongs to the considered by us class of cordial functions. We very explicitly show that this strategy works well in Sec. 4.3, where we take: h=identity and effectively demonstrate that learnable cordial f can achieve distortion much lower that theoretical log(N) ratio (for the worst-case optimal Fakcharoenphol trees ([5])). In that section, the log(N) distortion would translate to losses >=9, whereas losses achieved by us there are <= 1 or <=1.3.\n\n[1] Efficient distributed approximation algorithms via probabilistic tree embeddings, Khan et al.,\n     PODC 2008.\n\n[2] K-server via multiscale entropic regularization, Bubeck et al., STOC 2018\n\n[3] Distorted metrics on trees and phylogenetic forests, Mossel et al., IEEE ACM Trans. Comput.\n     Biol. Bioinform, 2007. \n\n[4] On notions of distortion and an almost minimum spanning tree with constant average distortion., Bartal et al., STOC 2016. \n\n[5] A tight bound on approximating arbitrary metrics by tree metrics, Fakcharoenphol et al., . J. Comput. Syst. Sci.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**Additional pdf with updated plot for Fig. 4 and an additional visualization for the paper**

We would like to sincerely thank all the Reviewers for the very valuable comments and feedback. We summarize our rebuttals in the official comment below and then provide responses to the individual questions of the reviewers in the rebuttals and additional official comments. Here we also attach the pdf with the updated plot for Fig. 4 and an additional visualization for the paper.

Meta-review: All reviewers argue for acceptance, albeit with partial low scores. The improvements the paper has made are noted as well as the interesting theoretical contributions. The paper meets the bar for acceptance.
Decision: Accept (poster)