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

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.

Strengths

1. FTFI significantly improves the runtime in contrast to previous tree integration algorithms 2. The paper conducts extensive experiments, showing promising applications with Topological Vision Transformers. 3. 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%. 2. 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. 3. 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.

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? Thank you in advance for your answers!

Rating

7

Confidence

2

Soundness

3

Presentation

4

Contribution

3

Limitations

The authors discuss limitations in the appendix.

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.

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. ======================================== This weakness about the presentation of FTFI is addressed by the rebuttal, so I am increasing my score from 6 to 7.

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. ======================================== The question is addressed by the rebuttal.

Rating

7

Confidence

2

Soundness

4

Presentation

2

Contribution

3

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.

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. The 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.

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. - The technical and theoretical contributions seem to be well thought and thorough. The algorithm makes sense to me on a high level. - 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 What 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. It would be also helpful if source code would be released in order to replicate/verify results.

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.

Rating

5

Confidence

1

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors briefly discuss limitations in the appendix.

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). The 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. This 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. The 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. The 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).

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). - 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. - 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.

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). - 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? - 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? - In Figure 5, on PTC-MR, why is BGFI slightly faster than FTFI? Is this a specific distribution of graphs? - 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? ======================================== These questions are addressed by the rebuttal, and I am increasing my score from 6 to 7.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes.

General comment

We would like to sincerely thank all the Reviewers for their very valuable feedback and comments. We addressed all of them in the rebuttals below and additional official responses. We also want to emphasize that we provide the pointer to the anonymous repository with the code: https://anonymous.4open.science/r/FastTreeFieldIntegrator/README.md. That repository contains in particular: **detailed implementation** of the FTFI algorithm (key contribution of the paper) with several unit tests, as well as the code for graph classification and vertex-normal prediction tasks (we will release any remaining code upon the acceptance of the paper). Finally, we have also run additional experiments with Transformers on new image dataset (I-naturalist) as well as on a **new modality**, namely: videos. In those experiments we also test many other efficient Transformer-architectures. These additional experiments **confirm all our previous findings**. In particular, FTFI applied in a topological masking mechanism in the ViViT architecture ([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 video data**. [1] ViViT: A Video Vision Transformer, Arnab et al., ICCV 2021. [2] The kinetics human action video dataset, Kay et al., 2017. We also conducted additional speed tests for Transformers to describe speed-quality trade-offs, showing that our methods are as fast as previous efficient-attention Transformers, while providing better quality.

Addressing comments of Reviewer Lag9

Dear Reviewer Lag9, We would like to once more sincerely thank you for all the comments and very useful feedback. We think that we have addressed in depth all Reviewer's questions. Please let us know. If the Reviewer has any additional questions, we would be more than happy to answer them. Yours sincerely, The Authors

Addressing comments of Reviewer o1jE

Dear Reviewer o1jE, We would like to once more sincerely thank you for all the comments and very useful feedback. We think that we have addressed in depth all Reviewer's questions. Please let us know. If the Reviewer has any additional questions, we would be more than happy to answer them. Yours sincerely, The Authors

Addressing comments of Reviewer H9MT

Dear Reviewer H9MT, We would like to once more sincerely thank you for all the comments and very useful feedback. We think that we have addressed in depth all Reviewer's questions. Please let us know. If the Reviewer has any additional questions, we would be more than happy to answer them. Yours sincerely, The Authors