ALS: Attentive Long-Short-Range Message Passing

Response to concerns regarding novelty

We have carefully examined the references you kindly pointed out and would like to clarify several aspects:

computing only the non-zero gradients of PPR (Theorem 3.1) was already proposed in [1]

We respectfully note that the computation of non-zeros in $A \odot (\nabla_Z \cdot Z^T)$ at line 215 is not included in Theorem 3.1. So even if similar gradient computation methods exist, this does not diminish the novelty of Theorem 3.1, which demonstrates how to optimize a PPR process iterated to convergence - a fundamentally different approach from existing PPR-based methods with truncated iterations (e.g., PPNP and MAGNA).

Moreover, the non-zero computation you mentioned in [1] actually refers to computing $P \hat \pi_s^{(L)}$. It is simply a forward-pass propagation, analogous to computing $A X$ in our framework. This differs significantly from our edge-wise computation of $A \odot (\nabla_Z \cdot Z^T)$.

"the contribution of long-short-range message passing is incremental"

We are afraid that the reference [2] shares only method name similarity with our approach. Their method addresses molecular dynamics simulation in a two-level graph structure (atom-level many-body interations and molecule-level long-range interactions), whereas our work focuses on single-graph learning with distance-aware message passing. And heterophily is not considered in [2].

"the proposed algorithm is merely a simple integration of several existing methods"

Due to the previous explanations, we respectfully disagree with your assessment. However, we greatly appreciate your positive comments on other aspects of our work.

• [1] Efficient Algorithms for Personalized PageRank Computation: A Survey
• [2] Long-short-range message-passing: A physics-informed framework to capture non-local interaction for scalable molecular dynamics simulation

Response to concerns on datasets

We sincerely appreciate your suggestion to evaluate ALS on additional datasets.

However, we would like to note that reference [3] identifies significant limitations with Cora, Citeseer and Pubmed datasets, particularly regarding fragile and misleading results from their data splits. These datasets also represent a narrow range of network types (all citation networks). We instead employ the Amazon Computer, Amazon Photo, Coauthor CS, and Coauthor Physics datasets recommended by [3] as more robust homophilic benchmarks.

For heterophilic graphs, reference [4] demonstrates issues with traditional datasets (e.g., train-test leakage in Chameleon and Squirrel) and proposes new benchmarks - the five heterophilic datasets we adopted.

While we would be happy to conduct additional evaluations on your suggested datasets, we believe our current selection better represents modern, rigorous benchmarking practices in graph learning research.

• [3] Shchur O. Pitfalls of Graph Neural Network Evaluation. ArXiv 2018 (#Citation: 1620)
• [4] Platonov O. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? ICLR 2023

Oversmoothing

While the authors claim that the proposed method mitigates oversmoothing, the experimental results do not provide a detailed analysis.

We appreciate this observation regarding oversmoothing. As established in prior work [1,2], the incorporation of Personalized PageRank (PPR) inherently addresses the oversmoothing issue in graph neural networks. Since this has been thoroughly demonstrated in the literature, we did not show the mitigation of oversmoothing in our manuscript but focused our experimental validation on other novel aspects of our approach.

• [1] Klicpera J, et al. Predict then Propagate: Combining neural networks with personalized pagerank for classification on graphs. ICLR, 2018
• [2] Choi J. Personalized pagerank graph attention networks[C]. ICASSP, 2022.

Are improvements significant?

Results in some cases do not show significant improvement over existing methods, and additional experiments or clearer explanations are needed.

We respectfully submit that improvements exceeding one standard deviation in accuracy can reasonably be considered significant. Our method achieves this standard in 9 out of 12 datasets in Table 1 and demonstrates consistent significance when compared to MPNN baselines in Table 2. While we understand the desire for universal improvement across all cases, we believe this may be an overly stringent expectation given the diversity of graph datasets.

To better address the reviewer's concern, we would be grateful for more specific guidance regarding what 'additional experiments or clearer explanations' would be most valuable for evaluating our method's contributions.

The memory usage

While the algorithm's complexity is analyzed, it would be beneficial to also evaluate its memory usage with other baselines.

We appreciate this suggestion regarding memory analysis. The attention weights of ALS are computed with the same formula in standard GAT. The difference is that ALS will propagate information following these attention weights for multiple iterations. However, the memory usage maintains the same thanks to implicit differentiation, as shown in Figure 2. Thus, the memory usage of ALS is the same as GAT.

Are improvements significant with long-range dependencies?

Although the proposed method is designed to capture long-range information, it does not achieve significant improvements on two datasets with long-range dependencies.

This is an insightful observation. We agree that when compared to Graph Transformers (GT), ALS shows more modest improvements because GTs inherently possess global receptive fields that can capture both long-range and non-adjacent node dependencies. However, as an MPNN variant, ALS consistently outperforms other MPNN baselines by more than one standard deviation in accuracy. Furthermore, the integration of ALS with GT architectures yields better performance than other MPNN-GT combinations. These results substantiate our claim that ALS offers superior long-range information capturing capability compared to conventional MPNN approaches.

We sincerely appreciate the reviewer's time and valuable feedback. We hope our following clarifications help the reviewer better appreciate the significance of our contributions, and we would be happy to provide any additional information that might assist in their evaluation.

Oversmoothing

It is not easy to trace the relation between oversmoothing and the proposed method

We sincerely appreciate this thoughtful observation regarding oversmoothing analysis. As demonstrated in prior work [1,2], the integration of Personalized PageRank (PPR) fundamentally addresses oversmoothing in graph neural networks. Since this relationship has been well-established in the literature, we did not show the alleviation of this problem in our manuscript but focused our experimental validation on the novel aspects of our approach.

• [1] Klicpera J. Predict then Propagate: Combining neural networks with personalized pagerank for classification on graphs. ICLR, 2018
• [2] Choi J. Personalized pagerank graph attention networks. ICASSP, 2022

Complexity

The derivation or proof of theoretical time complexity mentioned in the abstract is not easy to locate

We appreciate this careful reading. We would like to clarify that the complexity analysis mentioned in the abstract specifically refers to memory complexity rather than time complexity. We will ensure this distinction is made clearer in any subsequent revisions.

Baselines

In table 1, "baselines" are vague.

Thank you for this helpful feedback. Table 1 presents aggregated results comparing our method against all baselines. The "Rank-1" column indicates the highest-performing baseline result for each dataset, while "Rank-2" shows the second-best baseline performance. Complete baseline results are available in Appendix E for reference.

Baselines in Table 4 are a subset of the mentioned in Section 4.3

Thank you for this observation. We have verified that baselines are correctly described. The second paragraph of Section 4.3 describes baselines for Table 1, which is the combination of Table 4 and Table 5. In those baselines, only LINKX does not show up in Table 4, but it is in Table 5. The third paragraph introduces baselines for Table 2. So these baselines does not have to show up in Table 4.

Section 4.3 lacks the baselines after 2023

We appreciate this suggestion for contemporary comparisons. Our evaluation includes several recent works of 2024, namely Graph Mambas [3,4]. While other baselines predate 2023, many of them are from the recent literature [5].

• [3] Behrouz A. Graph mamba: Towards learning on graphs with state space models. KDD 2024
• [4] Wang C. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces. arXiv 2024
• [5] Chenhui D. Polynormer: Polynomial-Expressive Graph Transformer in Linear Time. ICLR 2024

Notations

In Section 3.1, the theorem comes as a sudden...

We apologize for any confusion caused by the theorem's presentation. The notation PPR($\alpha$, A, X) is explicitly defined in line 117 of the manuscript. We will consider adding additional transitional text to improve the flow in future revisions.

The Equation (1) seems problematic, the dimension is inconsistent...

We appreciate this careful examination of our equations. The dimensions are indeed consistent: $x_i \in \mathbb{R}^{1 \times d}$ (line 89), so $q_i, k_j \in \mathbb{R}^{1 \times c}$ and $s_{ij}$ is a scalar. $c$ is just another dimension, not the number of labels. $\mathbf{Z}$ is node representations (same dimensionality as $\mathbf{X} \in \mathbb{R}^{n \times d}$) rather than classification outputs.

Link prediction and graph classification

This narrow focus raises concerns about the method’s generalizability to other graph-related tasks, such as link prediction or graph classification.

The study lacks an analysis of the method’s generalizability to other graph-related tasks.

We sincerely appreciate the reviewer's valuable suggestion regarding additional evaluation tasks. Due to time constraints during the rebuttal period, we may not be able to conduct comprehensive evaluations across different types of graph tasks.

However, we would like to note that among the PPR-based methods we referenced (APPNP, GPRGNN, PPRGo, PPRGAT, and MAGNA), only MAGNA included link prediction evaluations. Therefore, focusing on node classification for our DPPR-based ALS method aligns with standard practice in this research area.

Furthermore, all claims in our manuscript - including memory optimization, time efficiency, and effectiveness on heterophilic graphs - have been thoroughly validated. Since heterophily fundamentally concerns node-level relationships, node classification tasks sufficiently demonstrate our method's capabilities in this regard.

Efficiency and scalability

the study lacks a thorough analysis of computational efficiency and scalability.

We acknowledge the reviewer's concern about computational analysis. The attention weight computation in ALS follows the same algorithmic approach as standard GAT. The key distinction lies in ALS's multiple iterations of information propagation, which typically results in computation time proportional to the number of iterations compared to GAT. This iteration count is primarily determined by the parameter $\alpha$ and can be significantly reduced by our three acceleration techniques.

Regarding scalability, our experiments demonstrate ALS's scalability because they include two large-scale OGB datasets, and while individual subgraphs in the LRGB datasets are small, their combined scale is substantial.

The innovation of accelerating techniques

I find the authors' claim of proposing three acceleration techniques for expediting the computation of DPPR to be unsubstantiated.

We appreciate this opportunity to clarify our technical contributions.

As mentioned in our discussion of AdaTerm, traditional PPR applications typically solve a single linear system, whereas we must solve H × C independent linear systems due to the multi-dimensional nature of node representations in GNNs. This novel challenge motivated our AdaTerm.

Moreover, the multi-dimensional node representations make Krylov subspace methods difficult to apply. While Krylov methods may require dozens of basis vectors to construct subspaces (negligible overhead for single systems), combining them with GNNs would require independent subspaces for each representation dimension, leading to H × C times of memory usage. This inspired our SymGAT, which enables more memory-efficient conjugate gradient algorithms.

Regarding EigenInit, since PPR was originally designed for homophilic graphs like page recommendations where EigenInit showed limited benefits, traditional PPR methods did not investigate into it. However, our experiments demonstrate that EigenInit provides significant acceleration on heterophilic graphs - an important finding given the growing interest in heterophilic graph research.

In summary, the three techniques were specifically designed to enhance PPR-based GNN methods, including our DPPR approach.

Experimental Designs Or Analyses

We respectfully disagree with this particular critique.

We have provided detailed experimental settings in Appendix E and included reproduction scripts with submitted code. We omit other LRGB datasets because they are inadequate for the evaluation, as explained in the footnote on page 6. Furthermore, Appendices C and D contain extensive ablation studies - we believe these address the reviewer's concerns about 'different optimization techniques'. We would welcome further clarification if we have misunderstood the reviewer's point.

Multi-layered ALS

why stacking multiple ALS layers is helpful?

This is an excellent and commonly raised question about many methods.

As shown in Appendix C of the IGNN paper, stacking multiple layers is theoretically equivalent to using a single wider layer. However, empirical results demonstrate that multi-layer IGNN architectures achieve substantially better performance on datasets like PPI. A similar phenomenon occurs with Graph Transformers (GT) - while a single GT layer can theoretically access all global information, deeper architectures typically perform better. Our work validates this design pattern's effectiveness, though the underlying reasons remain an open research question.

We hope this common architectural consideration won't negatively impact the evaluation of our contributions.