DUALFormer: Dual Graph Transformer

Q4. The authors should report the overall training cost of each method for efficiency study, especially on large-scale graphs. Maybe authors can refer to the settings in NAGphormer. For instance, can the proposed method achieve more efficient and more powerful performance than NAGphormer on Aminer, Reddit, and Amazon2M?

R4. According to your advice, we have compared the training cost in terms of total running time (s) and GPU memory (MB) of the proposed DUALFormer and NAGphormer. The batch size is uniformly set to 2000. The total number of training epochs is set to 100. All shared configurations are set to the same to ensure fairness. The result is shown in the table below.

From the table, two results can be observed: firstly, the proposed DUALFormer consistently outperforms NAGpormer across the three datasets, and secondly, the proposed DUALFormer has short running times across the three datasets compared to the baseline NAGpormer. The advantage of DUALFormer primarily stems from its elimination of the need for preprocessing to acquire structural encoding and storage, unlike NAGphormer, which requires such steps. This agrees with the conclusion of the complexity analysis.

---

Q5. As shown in Section 4.2, DUALFormer relies on the sampling strategy to perform on large-scale graphs, just like advanced linear graph Transformers. Hence, I think the GPU memory comparison is questionable since it is largely related to the batch size. Do authors set the same batch for each method?

R5. I understand your concern about fairness. The common hyper-parameters (including batch size) are the same for each model, as mentioned in Line 953. Specifically, all models are trained on ogbn-arxiv using full batch, whereas, for ogb-products and pokec, the batch size is set to 10K. We will explicitly mention this in the captions of the corresponding tables and figures in the revised manuscript.

---

Q6. The analysis of the $\alpha$ is missing. According to Table 5, the performance of DUALFormer could be sensitive to the value of $\alpha$. So, the parameter analysis of $\alpha$ should be added into the experiment section.

R6. Thanks for your careful check. The impact of the hyper-parameter $\alpha$ on model performance is shown below.

From the table, it can be observed that DUALFormer is not sensitive to the parameter $a$. Specifically, within the parameter selection range, the variation of classification accuracy does not exceed $0.7\%$.

Q1. The key contributions of the proposed method are not clear.

R1. The key contribution of the proposed DUALFormer is to introduce self-attention on the feature dimension. Although the design is simple, it possesses the following three excellent characteristics.

1. A scalable self-attention. Due to the quadratic computational complexity of their self-attention to the node dimension, Vanilla GTs often encounter scalability issues. In contrast, self-attention in DUALFormer operates efficiently, with complexity linearly related to the size of the graph. It is designed to capture inter-feature correlations to approximate global inter-node dependencies. As a result, it is potentially scalable to large-scale graphs.

2. Improvement of discriminability. Rigorous theoretical analysis demonstrates the rationality behind this design of self-attention on a novel dimension in improving the discriminability of node representations.

3. Comprehensive expressivity. Due to the global self-attention operating on the feature dimension, it seamlessly integrates with the local GNN module without compromising their expressivity. Therefore, DUALFormer achieves an automatic trade-off between local and global expressivity.

Furthermore, the proposed DUALFormer has achieved state-of-the-art performances on many tasks, including node classification and node property prediction.

---

Q2. As the authors claim in Eq. 13, the proposed method only captures the feature-to-feature correlations. In my opinion, it is not the global information on the graph since it is unable to capture the relations between nodes. Why do authors claim the proposed method can capture the global information on the graph?

R2. The capability of capturing global information stems from the approximate equivalence between $\operatorname{softmax}(\mathbf{Q}\mathbf{K}^T)\mathbf{V}$ and $\mathbf{Q}(\mathbf{K}^T\mathbf{V})$. The global information is captured by the attention between nodes, i.e., $\operatorname{softmax}(\mathbf{Q}\mathbf{K}^T)$, in previous graph transformers. According to the combination law for matrix multiplication, it holds that $(\mathbf{Q}\mathbf{K}^T)\mathbf{V} = \mathbf{Q}(\mathbf{K}^T\mathbf{V})$ and $\operatorname{softmax}(\mathbf{Q}\mathbf{K}^T)\mathbf{V} \approx \mathbf{Q}(\mathbf{K}^T\mathbf{V})$. Thus, this paper tends to approximate the expensive node-node attention $(\mathbf{Q}\mathbf{K}^T)$ via efficient feature-feature attention $(\mathbf{K}^T\mathbf{V})$ since $\operatorname{softmax}(\mathbf{Q}\mathbf{K}^T)\mathbf{V} \approx \mathbf{Q}(\mathbf{K}^T\mathbf{V})$. Thus, the proposed DUALFormer can capture global information.

---

Q3. The authors claim that the computational complexity of the proposed method is $O(n)$, which is obviously wrong. Based on Eq. 14, the calculation involves the adjacency matrix. Hence, the computational complexity of this part is $O(E)$, and it cannot be ignored since $|E| > |N|$(even $|E| \gg |N|$ on some graphs).

R3. Thanks for pointing out this error. In the previous version, only the complexities of self-attention in ALL GTs are considered. We will add the time complexity of GNNs to the time complexity of corresponding methods, including GraphTrans, SAT, GraphGPS, NodeFormer, NAGphormer, Exphormer, GOAT, SGFormer, Polynormer, GoBFormer, and the proposed DUALFormer. The adjusted time complexity is shown in the following table, where $e$ denotes the number of edges.

The table reveals that the computational complexity of the proposed DUALFormer is linearly proportional to the number of nodes and edges, demonstrating its efficiency. Note that the complexity of DUALFormer aligns with those of the existing scalable graph transformers, such as NodeFormer, SGFormer, and Polynormer, while it does NOT require complicated preprocessing. This highlights the scalability of the proposed DUALFormer. Therefore, the conclusion of the high scalability of the proposed DUALFormer is not changed.

Q1. The paper has some minor errors that need fixing. For example, Table 2 misses the mean value for the GraphGPS model on the Citeseer dataset.

R1. Thanks for your careful checking. We will thoroughly check the manuscript to correct any omissions.

---

Q2. To enhance readability, Equation 13 should be split into two or three equations.

R2. Based on your suggestion, we will divide Equation 13 into three formulas by row.

---

Q3. The model DUALFormer places the GNN layers, such as the SGC layers, after the attention layers. What is the rationale behind this design? Is it possible to reverse this order?

R3. We would like to explain this design choice as follows.

This choice is primarily motivated by the desire to decouple local and global modules, thereby minimizing their mutual interference. The self-attention module generally relies on input representations to calculate attention coefficients, whereas the GNN module, typically GCN and GAT, utilizes fixed propagation coefficients that are input-independent. Therefore, placing the GNN module after the self-attention module can mitigate their mutual interference and ensure that comprehensive information is retained. Thus, it seems that this order cannot be reversed.

---

Q4. Figure 4 shows that the model utilizing APPNP outperforms the one using SGC in the Cora and Pubmed datasets. What accounts for this performance difference?

R4. This performance difference is primarily attributed to the difference in the localizing property of these two models. As can be seen in Figure 4, the original APPNP has a performance advantage over the original SGC on the Cora and PubMed datasets. This demonstrates the superiority of the former in terms of localizing property. By designing the global self-attention module in the pairwise dimension of the local GNN module, DUALFormer naturally obtains the global information with the guarantee that it does not interfere with each other. Thus, the DUALFormer based on APPNP with superior localizing property outperforms the DUALFormer based on SGC.

Thank you for the reminder. It underscores the compatibility of DUALFormer and suggests the potential for further enhancements by integrating it with more advanced GNNs.

---

Q5. The effect of certain hyper-parameters, such as the parameter $\alpha$ in Equation 13, on performance has yet to be unverified.

R5. Thanks for your careful check. The impact of the hyper-parameter $\alpha$ on model performance is shown below.

From the table, it can be observed that DUALFormer is not sensitive to the parameter $a$. Specifically, within the parameter selection range, the variation of classification accuracy does not exceed $0.7\%$.

---

Q6. The paper does not mention any plans to open-source the code.

R6. We promise to open-source the code and provide a GitHub link once the paper is accepted.

Q4. The first question concerns the reasonableness of applying softmax to the global correlations between features. Could you clarify these differences and explain why it is reasonable to replace $\phi(\mathbf{Q})(\phi(\mathbf{K})^{\top}\mathbf{V})$ with $\mathbf{Q}\operatorname{softmax}(\mathbf{K}^{\top}\mathbf{V})$?

R4. The introducted softmax is just a implementation strategy, while the obvious equivalence $\phi(\mathbf{Q})(\phi(\mathbf{K})^{\top}\mathbf{V}) = (\phi(\mathbf{Q})\phi(\mathbf{K})^{\top})\mathbf{V}$ is the key point we want to emphasize. This equivalence motivates the additional transformer on feature dimension and the proposed DUALFormer. To demonstrate the ignorability of softmax, we conduct an ablation study on the impact of softmax with results shown in the following tables. It illustrate that we can employ $\phi(\mathbf{Q})(\phi(\mathbf{K})^{\top}\mathbf{V})$, which is equivalent to $(\phi(\mathbf{Q})\phi(\mathbf{K})^{\top})\mathbf{V}$. We sincerely apologize for any confusion caused by the introduced softmax and will remove it in the final version.

---

Q5. The interpretation of the proposed global attention on the special case of one-dimensional feature.

R5. For the case of a one-dimensional feature, neither previous approaches nor the proposed DUALFormer gather information. $\phi(\mathbf{Q})\phi(\mathbf{K})^T$ in previous methods reduces to a rank-1 matrix, whose rows only differ from each other by a factor since $\phi(\mathbf{K})^T$ is a row vector and $\phi(\mathbf{Q})$ is a column vector. Thus, the aggregation patterns/coefficients for different nodes, represented by the rows of $\phi(\mathbf{Q})\phi(\mathbf{K})^T$, only differ by this factor. As a result, $\phi(\mathbf{Q})\phi(\mathbf{K})^T\mathbf{V}$ degrades to the same aggregation pattern/coefficient for different nodes. Since the essence of aggregation is the different aggregation patterns/coefficients for different nodes, previous approaches lose this characteristic for a one-dimensional feature. Therefore, they also do NOT gather information as the proposed DUALFormer in this special case.

---

Q6. The motivation for the study is not fully convincing.

R6. We hope the above two responses could clarify the rationality of our motivation. Firstly, the key motivation is the obvious equivalence $\phi(\mathbf{Q})(\phi(\mathbf{K})^{\top}\mathbf{V}) = (\phi(\mathbf{Q})\phi(\mathbf{K})^{\top})\mathbf{V}$. Second, neither previous approaches nor the proposed DUALFormer gather information for the case of a one-dimensional feature. Thanks for your special case. It also demonstrates the importance of multiple features for the transformer. Thus, the proposed DUALFormer is further justified by exploring the correlation among multiple features with an additional transformer.

Q1. Suggested datasets include Roman-Empire, Question[1], Wiki, and ogbn-papers100M.

R1. According to your suggestion, we have conducted model comparisons on the Roman-Empire, Question, and ogbn-papers100M datasets. For the Roman-Empire and Questions datasets, the data partitioning follows the scheme from [1], specifically, a 50/25/25 split for training, validation, and testing. For the ogbn-papers100M, the split ratio is public split [2], namely 78/8/14. The statistics of the dataset and the experimental results are shown in the following table.

The table reveals that, in comparison to the baselines, our proposed DUALFormer achieves consistently performance advantages on all three datasets, underscoring its superiority and scalability.

[1] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? ICLR 2023 [2] Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS 2020

---

Q2. The statement, “Most GTs consistently show superior performance over GNNs across all datasets” (line 451), would be more convincing if compared with recent GNN baselines, such as ChebNetII[2] and OptBasis[3].

R2. Thank you for pointing out the imprecise description. The correct description would be: "Most GTs consistently show superior performance over the backbone GNNs, which typically are GCN and GAT, across all datasets.” Based on your advice, we further compare the proposed DUALFormer with these two recent GNN baselines, namely ChebNetII and OptBasis, on five datasets. As can be seen from the following table on five datasets, the proposed DUALFormer consistently outperforms the baseline GNNs. This underscores the effectiveness of DUALFormer.

---

Q3. There are a few typographical errors.

R3. Thanks for your careful review. We will meticulously check the manuscript to ensure all errors are corrected.

Q1. The proposed method can be interpreted as "attention on attributes". I wonder how is it different from the standard self attention. Especially why it can perform better on node classification? And when it is expected to perform better and when not?

R1. Firstly, both the proposed self-attention on dimension regarding attributes and standard self-attention are to capture global information despite their different forms. The former approximately describes the global dependence between nodes, which is the main role of the latter, by characterizing the correlation between features. Secondly, the performance boost is not due to this alone but rather the dual design of local and global modules. This prevents the trade-off between local and global information and enables comprehensive information modeling. Finally, the proposed method improves the performance of GNNs by capturing the relationships between features. They perform better when there is a strong correlation among features, and their effectiveness may be less effective when such correlations are weak.

---

Q2. Can you provide further analysis, such as case studies, to further explain the semantic meanings of the "attention on attributes"?

R2. The semantic meaning of the proposed attribute (feature) attention is that it focuses on the correlation among features, allowing the model to capture the information that is most discriminative for the task. We would like to provide the following case to illustrate this point.

Suppose there are five nodes with four features, where three of these nodes (the index are the first three) belong to one class, and the other two belong to the other class. When the feature matrix exhibits low-class discriminability, the matrix can be exemplified by $\mathbf{H}=$

[[ $\frac{1}{3}$, $\frac{2}{3}$, 0, 0 ],

[ $\frac{2}{3}$, $\frac{1}{3}$, 0 , 0 ],

[ 0, 1, 0, 0 ],

[ 0, 0, 1, 0 ],

[ 0, 0, 0, 1 ]]$_{5\times 4},$ where the rows correspond to nodes and columns to features.

Assuming a clear feature correlation, e.g., the first two features signal the first class, while the last two features correspond to the second class. The attention score matrix can be expressed as $\mathbf{S}=$

[[ $\frac{1}{2}$, $\frac{1}{2}$, 0, 0 ],

[ $\frac{1}{2}$, $\frac{1}{2}$, 0 , 0 ],

[ 0, 0, $\frac{1}{2}$, $\frac{1}{2}$ ],

[ 0, 0, $\frac{1}{2}$, $\frac{1}{2}$ ]]$_{4 \times 4}$.

Using feature attention, the updated features can be expressed as $\hat{\mathbf{H}}= \mathbf{H}\mathbf{S} =$

[[ $\frac{1}{2}$, $\frac{1}{2}$, 0, 0 ],

[ $\frac{1}{2}$, $\frac{1}{2}$, 0 , 0 ],

[ $\frac{1}{2}$, $\frac{1}{2}$, 0, 0 ],

[ 0, 0, $\frac{1}{2}$, $\frac{1}{2}$ ],

[ 0, 0, $\frac{1}{2}$, $\frac{1}{2}$ ]]$_{5\times 4}.$

The updated features exhibit more obvious class discriminability compared to the input features.

---

Q3. Can you provide further analysis and empirical studies to show that the GNNs after the graph Transform can indeed learn the localities in graphs?

R3. We would like to provide the following theoretical analysis to explain that the GNN module is able to learn the locality of the graph.

Firstly, from the perspective of graph learning, many classical GNNs (e.g., GCN and SGC) can be induced by optimizing the objective function [1, 2], namely

$tr(\mathbf{H}^{\top}\tilde{\mathbf{L}}\mathbf{H})=\frac{1}{2}\sum_{v,u}\tilde{a}_{v,u}\Vert \mathbf{h}_v-\mathbf{h}_u\Vert_2^2$,

where $\tilde{\mathbf{L}}$ denotes the Laplacian matrix of the normalized adjacent matrix $\tilde{\mathbf{A}}$, and $\mathbf{H}$ stands for the node features such as $\mathbf{H}=\mathbf{X}\mathbf{W}$ in GCN and $\mathbf{H}= \mathbf{X}$ in SGC. This indicates that GNNs essentially learn local information through feature updates that are constrained by the graph topology.

From the above perspective, the GNN module in the proposed DUALFormer is equivalent to solving the above objective function with $\mathbf{H}=\mathbf{Z}$, that is, $tr(\mathbf{H}^{\top}\tilde{\mathbf{L}}\mathbf{H})$, where $\mathbf{Z}$ denotes the node features obtained from the self-attention on the dimension regarding features. Thus, even as a post-processing technique, the GNN module can ensure localizing property by leveraging graph topology to constrain the feature updates.

[1] Interpreting and Unifying Graph Neural Networks with An Optimization Framework. WWW 2021

[2] Why Do Attributes Propagate in Graph Convolutional Neural Networks? AAAI 2021