Dear Reviewer,
Thank you for your response. We wish we had heard about this concern earlier during the discussion period to address it more thoroughly. Given the time constraints, we would like to briefly address some points regarding your response:
1. SGFormer has indeed been our main baseline for the large graphs datasets in Table 2 (see the row just before our model). While we can add this baseline to Table 1, that is not the primary purpose of Table 1. The goal of Table 1 is to demonstrate that the sparsification from Exphormer maintains competitive results, and the other numbers provide context for the extent of the results for those datasets. If it satisfies you, we can add SGFormer to this table as well.
Regarding large graphs, our model uses around 2-3 GB of memory, which is comparable to the SGFormer model. For instance, on Amazon2M, our model uses 3 GB while SGFormer uses 2.7 GB. Notably, our model allows for batch size reduction to train with less memory without sacrificing accuracy. However, as mentioned in Appendix E and Figure 4, random subset batching has its flaws, and reducing the batch size can significantly hinder the model’s performance.
2. Regarding the Polynormer, we have already outlined several reasons why we are not comparing our model with this baseline, and we are happy to include these reasons in our paper if it helps. To summarize, the reasons are:
- Polynormer introduces an orthogonal idea that can be applied to many models, including ours. This idea enables a polynomial mixture of features and node embeddings. However, this process introduces several complexities, such as a two-stage training process and the requirement for a very large network. Our final model is sublinear with respect to graph size and achieves competitive results against linear or superlinear models. We are not pursuing every possible extension, such as adding polynomial characteristics, merely to chase state-of-the-art results. Our work has a specific purpose, and we explore ideas around it, comparing our model with reasonable baselines.
- As is customary with deep learning models, models with a similar number of parameters should be compared. While our model is a much smaller network, Polynormer uses a hidden dimension of 512, and a single linear map in their network has more parameters than most of our networks. Although they do not explicitly mention the number of parameters, they typically use between 6 to 13 layers, each with many linear mappings. Additionally, while our model and our main baseline, SGFormer, aim to train on a 4 GB budget, Polynormer uses 48 GB GPU devices for training and still applies random subset batching in their work.
- Not every model must achieve state-of-the-art results to be valuable. Our model aims to be memory-efficient and extend sparse pattern Graph Transformers to large graphs, offering a memory-time trade-off. We have demonstrated its effectiveness and compared it to relevant models that prioritize memory efficiency. In the NLP context, sparse pattern Transformers and low-rank models have always been distinct development threads, each excelling in different aspects.
- We have addressed the limitations of a baseline mentioned in Figure 4 and Appendix E, and our model avoids these pitfalls. Even if model sizes are not convincing, we emphasize that different models should be developed in parallel. Suppressing a research direction because it does not immediately achieve top results is not scientifically sound. Different models have unique advantages, and the lack of benchmarks or not achieving the best results should not deter their development. After all, if neural networks had been abandoned early due to lack of best results, we would not enjoy their benefits today.