Learning Long Range Dependencies on Graphs via Random Walks

Thank you for your encouraging words and helpful feedback. We have tried to address your points below and in the revised manuscript. If you have any further questions, please let us know.

A weakness of this paper is a lack of discussion of "old" RNN architectures like LSTMs.

We appreciate you bringing attention to the important role of classical RNN architectures like LSTMs. We acknowledge that our focus on recent advancements (SSMs, Transformers), which offer more efficient implementations, led us to overlook these classical RNN models. This is particularly relevant given the paper you cited $Merrill et al.$ regarding RNNs' superior expressivity for unbounded sequences. Based on your suggestion, we have included a discussion in Section B.3 in the revised manuscript.

The result that SSMs outperform Transformers in the context of NeuralWalker is very interesting. Are there some theoretical insights as to why self-attention is not well-aligned with processing walk embeddings?

The superior performance of SSMs over Transformers in our context was indeed an interesting empirical finding. While a complete theoretical analysis is beyond our current scope, we can offer several insights:

• We maintained a strict parameter budget of ~500K following previous work. However, transformers typically require more parameters than other sequence models to achieve optimal performance.
• While Transformers are universal approximators of sequence-to-sequence functions (Yun et al., 2020), this theoretical capability may require larger model capacities than our parameter budget allowed.

Thank you for your time and detailed feedback. We have addressed your concerns below and in the revised manuscript. If you have further questions, please let us know.

W1. Graph transformers compress random walks into fixed-size vectors, which either limits their structural expressivity or makes them difficult to analyze theoretically (Zhu et al. 2023). Our approach of treating random walks as sequences is theoretically motivated to avoid this limitation. Please see our (i) Technical contribution section for a detailed discussion of this motivation.

W2. Our choice of average pooling in the walk aggregator is deliberate for two key reasons: 1) It aligns with our theoretical analysis, maintaining the connection between practice and theory. 2) It enables flexible deployment: the number of random walk samples can be adjusted between training and inference to offer a trade-off between performance and computation. In our experiments, we always use a sampling rate of 1.0 at inference but it was selected based on the dataset size during training.

W3. Please refer to our general response section on (i) Technical contributions for a detailed discussion.

W4. While Mamba empirically outperformed transformers as the sequence layer in our experiments, we acknowledge that a comprehensive analysis of this phenomenon is beyond our scope. However, we can offer an insight: the performance difference may stem from parameter constraints (500K budget) as we strictly followed the configurations of previous works. Transformers typically require more parameters than other sequence models such as CNNs or Mamba to achieve optimal performance.

Regarding using bidirectional RNNs as the sequence layer, we would like to point out that SSMs are also RNN models. While exploring classical RNNs in depth could be an interesting further research direction, we want to emphasize that we focused on the most recent advances in RNNs (such as Mamba and S4), which offer more efficient implementations. As suggested by Reviewer eHiS, RNNs could indeed be useful for unbound sequences, we have thus added a discussion in Section B.3 in the revised manuscript.

W5. While long random walks theoretically capture long-range information (as proven in our theory for subgraph isomorphism test), we found empirical benefits from including global message passing for certain datasets since the walk length cannot be arbitrarily long in practice (the expressive power of NeuralWalker with length $\ell$ is also given in our Thm. 4.4). As a consequence, we use a global message passing to compromise this in practice. The global message passing strategies considered in our work are the virtual node module and the vanilla transformer layer (rather than a full graph transformer architecture) and an ablation study is provided in Table 6a. Please refer to the paragraph "Effect of local and global message passing" in Section 5.3 for more details.

W6. Our space complexity matches the time complexity proven in Theorem 4.5, with empirical validation shown in Figure 3. A key advantage of our method over graph transformers is explicit control over memory usage through sampling rates and walk lengths. For example, while Polynormer struggled with datasets of very large graphs like Pokec (they deactivated the attention module in their code), our method successfully scaled to this size.

W7. Please see the (ii) Additional baselines section in our general response.

W8. Our work presents a general graph representation learning framework, not specifically a node classification method. Our evaluation spans 19 diverse benchmarks, from synthetic to large-scale real-world datasets, covering graph, node, and edge prediction tasks. The inclusion of node classification datasets specifically demonstrates our method's scalability advantage over current transformer-based approaches, which often struggle with such scales. Future work could certainly explore additional larger scale datasets, but we believe our current evaluation provides strong empirical support for our method's effectiveness and generalizability across diverse graph learning scenarios. Our theoretical analysis on the complexity also provides sufficient promise of our model's scalability to larger datasets.

Q1. Is the motivation for using the random walk sampler driven by memory constraints?

The role of the random walk sampler is to independently sample a subset of random walks on each graph. We kindly point the reviewer to Section 3.2.

Q2. in Figure 3, why does the ZINC dataset display a different trend compared to the other two datasets?

The apparent difference in ZINC's trend is due to its use of MAE as the evaluation metric for regression. The underlying performance pattern aligns with other datasets when accounting for this metric difference.

Thank you for your time and detailed feedback. We have addressed your concerns below and in the revised manuscript. If you have further questions, please let us know.

The authors claim that our approach achieves significant performance improvements on 19 graph and node benchmark datasets. Based on the reported results NeuralWalker underperforms baselines and several missed state-of-the-art methods.

We apologize for the unclear language regarding performance improvements. We have revised our statement to "our approach achieves competitive performance on 19 graph and node benchmark datasets". Regarding your concern on missing methods, please refer to our answer (ii) Additional baselines in our general response above.

The authors claim that CNNs present a compelling alternative for large datasets due to their faster computation (typically 2-3x faster than Mamba on A100). Where are the results for this? How is this trade-off between efficiency and performance?

The performance comparison between CNN and Mamba is presented in Table 6b. While we observed CNNs to be 2-3x faster than Mamba on an A100, with training times reported in Tables 9, 10, 11, and 12, we omitted detailed time comparison results due to space constraints. This comparison primarily serves to justify our use of CNN for large-scale datasets in OGB, rather than being a central claim of our work. Based on your suggestion, we have included the time comparison results in Table 14 in the Appendix.

The authors several times mentioned efficiency as the motivation of their method.

We want to clarify that efficiency is not our primary motivation. Our method is fundamentally motivated by the complementary nature of random walks (depth-first) and message passing (breadth-first) in graph exploration (Please see (i) Technical contribution section in our general response). On the other hand, our discussion of efficiency focuses on the flexibility to balance model complexity and expressivity through walk sampling parameters, as presented in Section 5.3.

Without local/global encoding the performance of NeuralWalker significantly drops. How the results can support the importance of using random walks for long-range dependencies?

Based on the results in Table 6, without local and global message passing the performance of the proposed method drops significantly.

The significant performance impact of local message passing actually supports our core thesis: the synergy between random walks and message passing is crucial for achieving superior expressivity. This is both theoretically proven and empirically demonstrated in our work (please also see (i) Technical contributions section in our general response regarding this aspect).

although the results of POLYNORMER (Deng et al., ICLR 2024) are reported in Table 5, their results are missing in other experiments.

Why Polynormer’s results are missing in LRGB and GNN benchmark experiments?

We included Polynormer results where directly comparable, noting that its primary focus is on extending the scalability of graph transformers for node classification on large graphs. Polynormer aims to balance expressivity and scalability for GTs rather than improve expressivity. Extending it to graph-level or edge-level tasks falls outside our paper's scope.

Adding other baselines such as GSSC, GOAT, and GRED.

Please refer to our discussion of (ii) Additional baselines in our general response, which explains our focus on methods directly comparable to our key innovations.

I believe a comparison with random walk-based GNNs like GraphSAGE is required.

GraphSAGE uses random walks to design their loss function rather than explicitly encoding them into graph representations. Based on your suggestion, we have included a comparison with it in Table 5.

The paper has overlooked graph-mamba (Behrouz et al., KDD 2024). What are the differences between Graph-Mamba and your work?

What are the main differences between NeuralWalker with the tokenization module in graph-mamba (Behrouz et al., 2024), where the number of random walk samples (M) in their framework is 1?

Please note that we did not overlook this version of graph-mamba, and we discussed the key difference in the "sequence modeling" paragraph in Section 2. Following your comment, we provide a more detailed discussion of the key differences between our approach and Graph-Mamba in the (ii) Additional baselines section of our general response.

Thank you for your time and detailed feedback. We have addressed your concerns below and in the revised manuscript. If you have further questions, please let us know.

Novelty is limited

While we agree that methods such as random walks, message passing, and SSMs are established techniques, we believe our approach introduces significant novelty by successfully combining them into a method that achieves state-of-the-art performance with several theoretically relevant properties. Please refer to the (i) Technical contributions above for a discussion on our contribution and its novelty. Furthermore, we discuss a detailed comparison between Graph-Mamba and our method in (ii) Additional baselines above.

The datasets for node classification are mainly heterophilic.

We appreciate the reviewer's observation about the heterophilic datasets. However, our work presents a general graph representation learning framework, not specifically a node classification method. Our evaluation spans 19 diverse benchmarks, from synthetic to large-scale real-world datasets, covering graph, node, and edge prediction tasks. The inclusion of node classification datasets specifically aims to demonstrate our method's scalability advantage over current transformer-based approaches, which often struggle with such scales. Future work could certainly explore additional datasets, but we believe our current evaluation provides strong empirical support for our method's effectiveness and generalizability across diverse graph learning scenarios.

The source of the performance gains is unclear

The sources of our performance improvements are systematically studied and documented in Sections 5.2 and 5.3. Section 5.2 provides empirical evidence of pretraining benefits on the ZINC dataset, while Section 5.3 offers detailed ablation studies on message passing and sequence layer architectures. Furthermore, our random walk positional encodings are not merely an implementation detail but a theoretical cornerstone, enabling our proven $(\lfloor\ell/2 \rfloor + 1)$-subgraph isomorphism expressiveness (Section 4). We have added a clarification sentence in Section 3.2.

While we provide individual responses to specific comments and concerns below, we address here several general points of feedback:

(i) Technical contributions

We would like to clarify our technical contributions:

1. (Novel combination of complementary graph exploration paradigms for graph learning) Our primary contribution lies in combining random walks and message passing paradigms. This combination is theoretically motivated by their complementary exploration nature: Random walks exhibit depth-first exploration and message passing follows breadth-first patterns. We prove that this synergy enables greater expressiveness than methods using either paradigm alone. More precisely, random walks of length $\ell$ help our model achieve $(\lfloor\ell/2 \rfloor + 1)$-subgraph isomorphism test power while message passing achieves 1-WL test power. Note that 1-WL test is not necessarily dominated by the $(\lfloor\ell/2 \rfloor + 1)$-subgraph isomorphism test as the size of WL-unfolding subtrees can be arbitrarily large. Please see Thm 4.4 and its discussion below for more details. The importance of combining the two paradigms is also validated in our experiments in Table 6. We believe this combination offers an important insight for future graph learning research.
2. (Explicit sequence treatment of random walks) Our approach fundamentally differs from existing graph transformers and GNNs in its explicit treatment of random walk as sequences, and processes them with state-of-the-art sequence models. While graph transformers compress random walks into fixed-size vectors, limiting their expressivity or making a theoretical analysis more difficult (Zhu et al. 2023), our explicit sequence handling offers two key advantages. First, it enables us to leverage advances in sequence modeling (in our experiments, we found Mamba worked the best). Second, it allows for an explicit analysis of model expressivity, as demonstrated in Thm. 4.4. These theoretical benefits are further validated by our empirical results, which show improved performances over graph transformers (e.g. GraphGPS which typically uses a random walk structural encoding) on several datasets. Moreover, the strong performance of our model does not necessarily rely on the global message passing module (which is nevertheless the main building block for GTs), making our model more scalable than most GTs (by scaling linearly with the number and length of random walks, which can be explicitly controlled in practice).

Appreciate the authors' effort! After reading this paper, I have one comment and one question.

Regarding Related Works To the best of my knowledge, there are earlier works that utilize walks and positional encoding for graph representation learning [1][2][3]. I suggest the authors include these earlier references and properly position them in the paper. These works predate Tonshoff et al. (2023b) which was cited as the primary inspiration for this paper.

Scalability of the Work If the time is allowed, could the authors add a figure to illustrate the relationship between the number of walks required for optimal performance for each dataset v.s. the number of nodes in the graphs? Similarly, it would be helpful to include a figure showing how the optimal walk lengths vary with the number of nodes. While I appreciate that Figure 3 provides insights into the sampling rate for selected graph datasets, it would be more informative to understand how these metrics scale with graph size.

[1] Anonymous Walk Embeddings, Ivanov & Burnaev, ICML 2018 [2] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks, Wang et al., ICLR 2021 [3] Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning, Yin et al., VLDB 2022

The wall-clock times are measured as averages per graph. Training can sometimes appear faster because we typically use a larger sampling rate during inference to achieve better performance (which is another advantage of walk-based methods). Specifically, for Benchmarking GNNs, LRGB, and OGBG datasets, the sampling rate is fixed at 1.0 during inference while it is usually smaller than 1.0 during training. For node classification datasets, the inference sampling rate is 5 or 10 times higher than the rate used during training (where these values have already been provided in Table 12).

Thank you again for your valuable feedback!