Advective Diffusion Transformers for Topological Generalization in Graph Learning

Thank you for the nice suggestions. We are encouraged to see the positive comments on our novel ideas, significant research problem and good presentation.

Q1: Scalability of the model and solutions for acceleration

Thanks for this inquiry. As illustrated in Sec. 4.3, our model ADiT-Series only requires $O(N)$ (a.k.a. $O(|\mathcal V|)$) complexity instead of $O(N^2)$. This acceleration is achieved by altering the order of matrix product (the same technique is used by DIFFormer [1]), with the details presented in Appendix E.1.2. Equipped with the linear complexity w.r.t. node numbers, ADiT-Series can smoothly scale to large-sized graphs.

Apart from our used acceleration technique, there also exists other potential choices, such as the random feature map or sliding-window attention, used by efficient Transformers to achieve the similar goal.

[1] Difformer: Scalable (graph) transformers induced by energy constrained diffusion, ICLR 2023.

Q2: Is it possible to split the graph into batches of vertices / edges, and do it batch-by-batch?

Definitely yes. For graphs with larger sizes, e.g., with millions or even billions of nodes, it can be difficult for full-graph training on a GPU with moderate memory. In these situations, splitting the graph into random batches of nodes can help to reduce the overhead, as is done by recent scalable graph Transformers [1, 2]. This technique for scalability is orthogonal to our research focus and agnostic to the model backbone, and we'd like to leave more exploration along this promising direction for future works.

[2] Nodeformer: A scalable graph structure learning transformer for node classification, NeurIPS 2022.

Q3: A lot of linear graph diffusion methods corresponds to a random walk. What is the random walk counterpart of ADIT if there is any?

Thanks for this insightful question. For our ADiT model with the formulation of Eqn. 8, one can treat the coupling matrix $\mathbf C + \beta \tilde{\mathbf A}$ as a random walk propagation matrix, in which case the diffusion process can be considered as a continuous random walk counterpart. The key difference in our model lies in the dense propagation matrix that defines the transition probability over a densely connected latent graph produced by the attention incorporated with the observed structural information.

W1: Figure 3: needs a footnote explaining OOM

We thank the reviewer for the nice suggestion. The OOM indicates out-of-memory error with a 24GB GPU used in our experiment, as illustrated in the caption of Table 1 where it appears at the first time.

Please let us know if you had any further question or feedback.

For the graphon theory, we have cited the references at the beginning of Sec. 3.1: "inspired by the graph limits (Lovász & Szegedy, 2006; Medvedev, 2014) and random graph models (Snijders & Nowicki, 1997)". Please kindly notice that our data generation hypothesis does not directly follow the graphon, whose original definition ignores node features and labels, and instead, we generalize the data-generating mechanism to include alongside graph adjacency also node features and labels that can better represent the complex real data.

Q6: In the proof of Theorem 1, why $C = \overline C + m\log (I + \tilde A) - \beta \tilde A$

Our proof for Thm 1 is based on construction. In this step, we consider a construction for the global attention matrix $\mathcal C$, according to the universal approximation results that hold for MLPs on the compact set [10].

[10] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359–366, 1989

Q7: Why not using the numerical solvers proposed in [4]

Though the numerical solver proposed in [4] is widely adopted by other graph diffusion models, it is time-consuming and can be non-stable since it requires the backpropagation through a continuous PDE/ODE. In contrast, our diffusion model Eqn. 8 induces a closed-form solution, which enables us to implement the model via computing the closed-form solution rather than solving the PDE with numerical solvers as is done by other diffusion models. To be specific, our model implementation described in Sec. 4.3. is derived from computing the closed-form solution using the approximation of the Padé-Chebyshev theory. This scheme is much faster and more numerically stable. This also fundamentally distinguishes our implementation from other graph diffusion models.

To strengthen our contribution on this point, we supplement ablation study comparing with the counterpart of ADiT (called ADiT-PDESolver) using the numerical solver of [4] on the DDPIN dataset. The results below show the effectiveness of our scheme. Besides, we found ADiT-Inverse and ADiT-Series are about 3 and 20 times faster than ADiT-PDESolver for training.

[4] Neural ordinary differential equations, NeurIPS 2018

Q8: Why are there no results for ADIT-INVERSE in Table 1? It would be beneficial to include more baselines of graph neural diffusion models.

As illustrated in Sec. 4.3., ADiT-Series only requires $O(N)$ complexity (by means of the acceleration technique described in Appendix E.1.2) and has better scalability than ADiT-Inverse that requires $O(N^2)$ complexity. For the two node classification datasets in Table 1 that have relatively large graph sizes, it is hard for ADiT-Inverse to be trained on a single GPU with moderate 24GB memory, so we only use ADiT-Series in this case.

Following the suggestion of the reviewer, we supplement more comparison with other graph diffusion models including ADR-GNN [2] and Anti-Symmetric DGN [8], with the results below. We do not compare with [1] since it studies adversarial robustness which has different research focus from us.

[8] Anti-symmetric dgn: A stable architecture for deep graph networks, ICLR 2023.

As stated in our paper, we will release the codes upon publication. We thank the reviewer again for the constructive suggestions that help us strengthen the quality of the paper. And please let us know if you had any further question or feedback.

Q3: Comparison with other works using advective diffusion equations [2, 3]

We'd like to clarify that advective diffusion equations are a class of diffusion equations serving as a generic mathematical framework. Though we use this framework as a principled perspective for motivating the model, it remains much room for the originality of model designs. Compared with [2, 3], our work targets a distinct problem and our proposed model considerably differs.

To be specific, [2, 3] target the standard graph learning problem where the training and test graphs are assumed to be from the same distribution. In this regard, the local diffusion/advection terms are both instantiated as local message passing by [2, 3] to improve the model's expressivity and the capability to handle heterophily, respectively. Differently, our work studies the topological generalization problem where the training and test graphs come from disparate distributions, so the main goal is to improve the model's generalization capability. To this end, we consider the non-local diffusion instantiated as global attention. Furthermore, in terms of implementation, prior art including [2, 3] uses the numerical solver for solving the PDE model, while we harness the approximation scheme based on the Padé-Chebyshev theory for computing the closed-form PDE solution. The table below presents a head-to-head comparison.

[2] ADR-GNN: Advection-Diffusion-Reaction Graph Neural Networks. arXiv preprint 2023.

[3] Graph neural convection-diffusion with heterophily, IJCAI 2023

Q4: Comparison with other works focus on generalization of topology distribution shift based on the graphon theory [6, 7]

Thanks for this inquiry on the comparison, which allows us to illuminate our contributions.

Analysis Target First of all, [6, 7] do not study graph diffusion models, and instead they analyze the discrete GNN models. Though graph diffusion equations are intimately related to GNNs, analyzing the generalization behaviors of graph diffusion models and GNNs needs disparate technical aspects and proof techniques.

Data Hypothesis [6, 7] resort to the conventional graphon model as the data hypothesis that ignores node features and labels in the generation, while our hypothesis in Sec. 3.1 resorts to a more general setting that includes alongside graph adjacency node features and labels in the data generation. Moreover, the analysis in [7] is limited to three specific types of graphs whose distribution shifts are determined by specific edge distributions. These specific graph types are special cases of our framework, where one can flexibly instantiate the pairwise function $h$ in our data-generating mechanism. In this regard, our analysis targets a more general setting that better represents complex real data.

Model Designs The models proposed in [6, 7] belong to the conventional discrete MPNNs that resort to local message passing, while our proposed model consists of a Transformer-like architecture built on continuous PDE.

[6] Graphon neural networks and the transferability of graph neural networks, NeurIPS 2020.

[7] Transferability properties of graph neural networks. IEEE Transactions on Signal Processing, 2023.

Q5: How does this data generation hypothesis correspond to the real-world datasets in Sec. 5.2? The citations of the graphon theory are not given in Sec. 3.1. Can you explain more about the graphon?

The data generation hypothesis in Sec. 3.1 presents a general setting that can represent the complex real-world data with topological distribution shifts caused by the latent environment $E$. The latter can have different physical meanings in practical cases. For example, the environment for the Arxiv dataset is the publication year which introduces distribution shifts across papers published at different times, and the environment for the Twitch dataset is the geographic domain that leads to distribution shifts across users in different regions. For the molecule datasets, the environment is the molecular scaffold, and for the protein datasets, the environment is the protein identification method. In these situations, the training and test data correspond to disparate environments and distribution shifts are caused by the varied environments in each case.

(See the follow-up response for the graphon issue)

Thank you for the careful reviewing and checking our proofs in detail. We appreciate the nice suggestions for improvements and the acknowledgement on our problem setting, methodology and experiments. We also would like to clarify some key points that might be potentially misinterpreted in the review.

Q1: The communicative property of $\tilde{\mathbf A}$ and $\tilde{\mathbf A}'$

We'd like to clarify upfront that our studied topological generalization problem has distinct technical aspects from the adversarial robustness studied in [1]. The latter situation involves varied topology introduced by the adversarial attack, which can significantly differ from the original graph, while in our case, the new topology with distribution shifts conforms to the underlying data manifold and mechanism. In this regard, we are interested in the extrapolation behavior of the model w.r.t. the small change of $\tilde{\mathbf A}$. Therefore, throughout our analysis sections, we assume $\Delta \tilde{\mathbf A}$ to be a small perturbation, i.e., $||\Delta \tilde{\mathbf A}||_2 \rightarrow 0$.

This paves the way for analyzing the quantity $\lim_{||\Delta \tilde{\mathbf A}||_2 \rightarrow 0} \frac{||\mathbf Z(T; \tilde{\mathbf A}') - \mathbf Z(T; \tilde{\mathbf A})||_2}{||\Delta \tilde{\mathbf A}||_2}$ that measures the change rate of node representations w.r.t. the small change centered at $\tilde{\mathbf A}$. In this regime, it holds that $\tilde{\mathbf A}$ and $\tilde{\mathbf A}' = \tilde{\mathbf A} + \Delta \tilde{\mathbf A}$ share the same eigenspace and are commutative. This makes the property satisfied $e^{\tilde{\mathbf A} \tilde{\mathbf A}'} = e^{\tilde{\mathbf A}' \tilde{\mathbf A}} = e^{\tilde{\mathbf A}}\cdot e^{\tilde{\mathbf A}'}$ that is used in our proof.

Also, we agree with the reviewer that our analysis for Prop 1 and 2 is not as specific as the conclusion in [1]. However, we do not consider this as a disadvantage or major limitation of our work since ** this paper mainly focuses on the methodology side**. The Prop 1 and 2 serve as the preliminary results exploring the problem, and our main goal is not to show the failure of local diffusion but to suggest its potential sensisitity to topological shifts. Our latter analysis for non-local diffusion and proposal of the new model aim at addressing the potential sensisitity and improving the generalization capabilities.

[1] On the robustness of graph neural diffusion to topology perturbations, NeurIPS 2022

Q2: The validity of Equation (73) requires that $\mathcal H$ be a finite hypothesis class and the loss function be bounded within [0, 1]

We thank the reviewer for pointing out this issue that helps us to fix our proof for considering more generic neural networks. The original Eqn. 73 is not rigorous enough for $\Gamma$ as a neural network that induces an infinite hypothesis space size, yet the proof can be easily fixed to accommodate neural networks without impacting the main conclusion of Prop 3 and Thm 2.

To be specific, if the hypothesis space has infinite size, we can leverage the well-established techniques, such as VC-dimension or Rademacher complexity, to derive the generalization bound. This does not impact the conclusion—the hypothesis space size $|\mathcal H(\Gamma)|$ can be replaced by the Rademacher complexity of $\Gamma$. The latter is a complexity measure of the function class, and Prop 3 and Thm 2 still hold with the original implications unchanged. (We slightly modify the statement in Prop 3 and the proof around Eqn. 73 in the new PDF).

Thanks for the feedback.

1. We will fix the proofs in later version to address the issue caused by the commutation.

2. For the Rademacher complexity, we thank the reviewer for the suggestion and we agree that more discussions on the complexity of \Gamma will add some value to our work from the side. We'd also like to point out that the big picture of our work focues on the topological generalization, and the main focus of our generalization analysis lies in the influence of topological shifts on the generalization error, i.e., $\mathcal D_2$ in Thm 2. We have discussed how the model can reduce the influence of topological shifts on generalization. In this sense, the analysis is specific to our studied problem and fundamental to the solution in this paper.

3. We used the widely adopted Euler for the ADiT-PDESolver.

1, I share the concerns raised by reviewer SG1T in point 1 and 2. The authors have not addressed these, which are fundamental errors in the paper.

2, Merely substituting the hypothesis space size with Rademacher complexity in Proposition 3 and Theorem 2 is overly simplistic and lacks specificity. For a meaningful analysis of generalization error in GNNs, detailed insights into the Rademacher complexity of your $\Gamma$ are essential.

Thank you for reviewing our manuscript and proposing the inquiries that allow us to clarify our differences and properly position our work with existing ones.

Q1 & W1: The proposed model is very close to [1, 2]. The authors need to explain the differences.

Thanks for suggesting these related works, which enables us to clarify our contributions. Though [1,2] also build their models upon continuous PDE diffusion as the foundation, our work targets distinct problems and proposes considerably different models.

In terms of problem settings, [1,2] focuses on the standard graph learning problem (where training and test data are assumed to be from the same distribution) and the main goal is to address the heterophily and over-smoothing. In contrast, our work aims at topological generalization (where training and test data are from dissimilar distributions), which has fundamentally different technical aspects.

In terms of models and implementation, [1,2] are both built on local graph diffusion equation. To be specific, [1] extends the diffusion operator to combine the attractive and repulsive effects, while [2] instantiates both the diffusion/advection operators as local message passing. Also, for implementation, these models uses ODE/PDE solver for solving the continous PDE. Differently, our model resorts to non-local diffusion operator instantiated as global all-pair attention. For implementation, we leverage the Padé-Chebyshev theory for computing the closed-form PDE solution. The table below presents a head-to-head comparison.

[1] ACMP: Allen-cahn message passing with attractive and repulsive forces for graph neural networks in ICLR 2023

[2] Graph neural convection-diffusion with heterophily in IJCAI 2023

Q2 & W1: The effect of graph structure changes on neural diffusion GNN models have been studied in the following [3,4,5]. Generalization results in GNNs have also been proposed. What are the additional new results in this paper?

Our work is actually different from [3,4,5], with detailed comparison below.

Comparison with [3,5] First of all, [3,5] do not study graph diffusion models, and instead they analyze the discrete GNNs. Though graph diffusion equations are intimately related to GNNs, analyzing the generalization behaviors of graph diffusion models and GNNs needs disparate technical aspects and proof techniques. More importantly, [3,5] resort to the conventional graphon model as the data hypothesis that ignores node features and labels in the generation, while our hypothesis in Sec. 3.1 resorts to a more general setting that includes alongside graph adjacency node features and labels in data generation. Also, their analysis focuses on three specific types of graphs whose distribution shifts are determined by specific edge distributions. These specific graph types are special cases of our framework, where one can flexibly instantiate the pairwise function $h$ in our data-generating mechanism. In this regard, our analysis targets a more general and difficult setting that better represents complex real data.

Comparison with [4] Our work largely differs from [4] in terms of distinct research problems: [4] studies the robustness of graph diffusion models under adversarial attack, while we focus on the topological generalization (see recent works [6,7] highlighting the differences between the two problems). In specific, we have unique contributions on the generalization analysis (e.g. Prop 3, Thm 2). Furthermore, [4] limits the analysis in local graph diffusion, while we also discuss non-local diffusion (Sec. 3.3) as well as the advective diffusion equation (Sec. 4.2) in our framework. The results of [4] lead to a new approach for improving the robustness of GNNs under attack on topology, while our results serve to motivate our new Transformer-like model from the PDE solution.

[3] Graphon neural networks and the transferability of graph neural networks in NeurIPS 2020

[4] On the robustness of graph neural diffusion to topology perturbations in NeurIPS 2022

[5] Transferability properties of graph neural networks in IEEE Transactions on Signal Processing.

[6] David Stutz, Matthias Hein, Bernt Schiele. Disentangling Adversarial Robustness and Generalization, CVPR 2019.

[7] Kimin Lee, Kibok Lee, Honglak Lee, Jinwoo Shin. A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks, NeurIPS 2018.

Q3 & W3: In the proof of Proposition 1, it is stated that $A$ and $\Delta A$ share the same eigenspace. Why is this true?

In our analysis for topological generalization, we are mainly interested in the extrapolation behavior of the model w.r.t. the small variation of $\tilde{\mathbf A}$. In this regard, throughout our analysis, we assume a small perturbation $\Delta \tilde{\mathbf A}$, i.e., $||\Delta \tilde{\mathbf A}||_2 \rightarrow 0$.

This allows us to analyze the quantity $\lim_{||\Delta \tilde{\mathbf A}||_2 \rightarrow 0} \frac{||\mathbf Z(T; \tilde{\mathbf A}') - \mathbf Z(T; \tilde{\mathbf A})||_2}{||\Delta \tilde{\mathbf A}||_2}$ that measures the change rate of node representations w.r.t. the tiny change on $\tilde{\mathbf A}$. In this regime, we have the property that $\tilde{\mathbf A}$ and $\tilde{\mathbf A}'$ share the same eigenspace and are commutative. This gives rise to $e^{\tilde{\mathbf A} \tilde{\mathbf A}'} = e^{\tilde{\mathbf A}' \tilde{\mathbf A}} = e^{\tilde{\mathbf A}}\cdot e^{\tilde{\mathbf A}'}$ used in our proof. We add more illustration on this assumption at the beginning of Sec. 3.2.

Q4: How does the proposed model perform under heterophily datasets?

The Twitch dataset we used is essentially a heterophily graph (see [8] for more info on this dataset), which guarantees the diversity of our experimental datasets and shows the competitiveness of our model on heterophily datasets. Having said that the main focus of our paper is topological generalization where training and test graphs come from different distributions, which distinguishes our work from the line of research focusing on heterophily graphs.

[8] New Benchmarks for Learning on Non-Homophilous Graphs, WWW 2021.

W2: The given bounds in Proposition 1 and 2 are very loose. I am unconvinced by the authors' motivations for this work

The Prop 1 and 2 in our paper show that the extrapolation behavior of local diffusion has an exponential upper bound and could lead to undesired significant change on the node representations. The Big-O bounds do not necessarily mean the exponential change rate would definitely happen in practice, but at least suggest the model could be sensisitive to the topological shifts. In contrast, Thm 1 shows that the Big-O bound of advective diffusion can be reduced to arbitrary polynomial orders, which suggests the non-local model is insensisitive to the topological shifts. Therefore, these results together show that non-local diffusion with advection is preferable over local diffusion, since the former has guarantee of bounding the change of node representations. This reasonably motivates our model design in Sec. 4 built upon non-local diffusion with advection.

Also please kindly notice that our work is not a theoretical paper. While we agree with the reviewer that the Big-Omega bounds can more accurately reflect the behavior than Big-O bounds, to be honest, it will require deriving the lower bound of matrix exponential norm, which still remains an open question. And, since we mainly focus on the methodology side, it is not necessary to show the negative result of local diffusion, which is not our main target neither. Our goal is to design an effective model with principles and groundings. We thus leave exploration on the Big-Omega bounds as future works along the theoretical line.

We thank the reviewer for the valuable feedback and please let us know if you had any further question or feedback.

Thank you for the constructive feedback and suggestions for improvement. We address your questions and comments in detail below.

Q1 & W2: Comparison with [1]

First, we would like to note that [1] was posted on ArXiv two months ago and should be considered concurrent work. While both our paper and [1] consider PDE-based graph learning models, our work is clearly distinct from [1] in terms of the target problem settings and model designs. First, [1] focuses on the standard graph learning problem where training and test data are assumed to be drawn from the same distribution, while our work focuses on topological generalization where the main goal is to extrapolate to out-of-distribution (OOD) test data with new topologies. The different problem settings lead to different technical challenges and model designs: [1] instantiates the diffusion term as local message passing to improve the expressivity of fitting training data; in contrast, our work considers diffusion as a global attention for better generalization to OOD test data. The implementation of the two models also differs substantially: ADR-GNN follows prior art using finite-difference numerical iterations for solving the PDE model, while our work harnesses the Padé-Chebyshev theory for computing the closed-form PDE solution. Besides the different problem setting, our experiments cover a broader range of tasks than [1]. (See the comparison below).

That being said, we added new experiments to compare ADiT with ADR-GNN on node classification. Since no code was provided by the authors, we implemented their model according to the description in their paper and obtain the results below, which shows the superiority of our approach ADiT over ADR-GNN:

[1] "ADR-GNN: Advection-Diffusion-Reaction Graph Neural Networks", Arxiv 2023

Q2 & W1/W2: Comparison with other models using local/global message passing [2, 3]

To be honest, there are a number of recent works considering the hybrid architecture of local and global message passing in the model (e.g., GraphTrans, GraphGPS and DIFFormer that have been compared in our experiments). These models including [2, 3] suggested by the reviewer have fundamental differences in the problem settings and model designs. First, similar to [1], they all focus on the standard graph learning problem, wherein the main target aims to improve the model's expressivity instead of the generalization capability (our focus). Second, from the architectural view, these models are composed of discrete feed-forward layers, which is largely different from our model built upon continuous PDE and its closed-form solution.

In the weakness section, the reviewer recognizes the motivation of "the composition of mpnn and transformer" shared by these models and ours as limited originality, but we argue that given the similar high-level motivation, it is still important and under-determined how to design the effective models for different tasks. The latter, which actually remains an open question, can lead to different model designs and architectures competent in distinct tasks.

To better justify our contributions, we present a comparison with these models that consider local/global message passing in the table below.

[2] "A generalization of vit/mlp-mixer to graphs", Arxiv 2023.

[3] "GPS++: An optimised hybrid mpnn/transformer for molecular property prediction", Arxiv 2022.

Q3: Check the results of MLP as baseline performance

Thank you for this constructive suggestion, and we supplement new experiments of MLP on all the datasets (see results in Table 1, 2, 3 in the revised paper). It demonstrates the superiority of our model over MLP which does not leverage any inter-dependence among nodes and yields inferior generalization. These results can strengthen our contributions.

Q4: What is the definition of hypothesis space size

In general machine learning context, the hypothesis space refers to the set of all possible hypotheses that a learning algorithm can consider or output. In our case, the hypothesis space particularly refers to the set of candidate functions induced by $\Gamma_\theta$ as approximated mapping from $\mathbf A$, $\mathbf X$ to $\mathbf Y$.

Q5 & W3: What topological shift was induced through splitting for OGB-Bace and -Sider

The public splits of these datasets provided by the OGB team are based on the molecular scaffolds. The latter refers to a pre-defined set of molecular substructures. In this regard, as illustrated in Appendix F.1.3 in our original paper, the molecules in the training and test sets have different scaffolds, introducing the topological distribution shifts.

Q6: Why local diffusion models have comparable performances compared to non-local diffusion models in Table 1?

The real-world datasets are much more complex than the hypothetical regimes used for theoretical analysis. Particularly, given the node-level inter-dependence in these datasets, it is challenging for the model to learn the generalizable topological features that are complex and abstract. Also, the structural information of observed graphs is important for prediction, so the non-local models also need to make good use of the input graphs for desired generalization. The improvements of ADiT over other non-local models (DIFFormer and GraphGPS) suggest that our model can better exploit both the observed structural information and unobserved global interactions for generalization.

Q7 & W2: It is necessary to compare with relevant non-local (transformer) models [4, 5], and models that considers out-of-distribution [6,7,8,9]

While we agree that it's always better to compare with more competitors, we'd like to point out that [4-9] focus on different problem settings or are orthogonal to our approach, and in these regards, we did not compare with them in our original experiments.

For the non-local (transformer) models, we have compared with three state-of-the-art graph Transformers (GraphTrans, GraphGPS and DIFFormer) in our experiments. [4, 5] focus on standard graph learning instead of topological generalization, and have different research focus. Even so, we add new comparison with them in node classification datasets.

The OOD methods [6,7,8] focus on size generalization where distribution shifts are purely caused by change of graph sizes, which is different from topological generalization. Also, these works are technically orthogonal to our model, as they focus on designing regularization approaches or learning algorithms that are agnostic to the model backbone. In contrast, our model is a new encoder backbone, in parallel to other GNN models. This is why our original comparison focuses on the peer models that can equally serve as the encoder backbones. That being said, we add new comparison with SizeShiftReg [7] and MoleOOD [9] on the molecular datasets, using GCN as the backbone that is used by their original papers. The table below shows the testing ROC-AUC and demonstrates the competitiveness of ADiT.

Q8: Time comparison

Thanks for the nice suggestion that can help to strengthen our paper. We supplement new results of training/inference time per epoch of all the models on the DDPIN dataset.

The results show that our models, in particular ADiT-Series, is as efficient as other Transformer-based models (GraphGPS and DIFFormer). This suggests our model can achieve better performance with the cost of comparable time.

Q9: Why local interactions are more important than non-local interactions in Table 9?

This is because in these node classification datasets, the observed graph contains much useful information and is important for generalization. In our paper, we did not state that non-local interactions are necessarily more important than local interactions, and actually, this may depend on specific datasets in practice. Instead, our main point is that learning non-local interactions can facilitate generalization (and also notice that the local interactions can be useful as well), which is validated by the improvement of ADiT over ADiT w/o diffusion in Table 9.

Thank you again for reviewing our manuscript, and please let us know if you had any further question or feedback.