DIRECTIONALITY IN GRAPH TRANSFORMERS

Thank you for your feedback. Below are our responses to the issues you've highlighted:

W1. We provide the answer to this question in our general response. As noted, our model does not use more parameters, since we adjust the choices to keep it aligned with the competitive baselines.

W2. The complexity of graph transformers typically depends on their structural design. Standard graph transformers, such as Vanilla Graph Transformer and DiGT, assume that all nodes are interconnected, resulting in a complexity that is quadratic relative to the number of nodes. In contrast, graph transformers employing sparse attention focus only on neighboring nodes and ignore non-existent edges. This approach reduces both computational time and memory requirements and works like graph neural networks. We will explore sparse attention techniques in the future.

W3. There are no definitive measures to characterize the importance of directionality. One option is to use various directed graph metrics like distribution of in and out-degrees, directed cycles, etc. Another option is to use some spectral measures. We used the SCC entropy that combines some aspects of the directed metrics, and we also study the empirical effect of random edge flipping. We believe this is an interesting open question for the graph learning community.

W4. Thank you for suggesting the Dir-GNN work, which is a directed graph neural network that focuses on incoming and outgoing edges. However, DiGT assumes that all the nodes are connected since our model is a graph-level transformer model. Dir-GNN was first published on May 17, 2023, making it concurrent to our research. We will thoroughly explore it in our future studies.

We want to thank you for your thoughtful ideas. Here is our response to the concerns you raised regarding potential weaknesses:

W1. We choose to retain the k-hop constraint, since it helps somewhat, as shown in Table 11 in the appendix. We replicate the last two rows of that table here:

As we can see the use of k-hops confers a slight benefit. But, one critical difference from GCNs should be noted. The GCNs are always constrained by the direct neighbors which add a very strict inductive bias. On the other hand, when we used k-hops, we treat the entire set of k-hop neighbors as the context, i.e., any node can directly communicate with any other node within the k-hops, which is a much less restrictive "bias", and lets us tradeoff the global attention with somewhat localized attention.

When we say that we use dual encodings throughout, it does not imply that there is no exchange between these source and target embeddings. In fact, it is clearly of benefit to allow information to flow from one to the other, enabling them to mutually exchange information. We do not want to reduce the system to a mere duplication of single-encoding attention, so it is not clear whether the reviewer is suggesting that keeping them independent is a better choice?

W2. We refer the reviewer to Tables 6 and 7 in the appendix, that already does a comprehensive comparison of all the flipping experiments to show the importance of directionality.

In these experiments, we implement a strategy of randomly shuffling the dataset at each training step. This approach means that the dataset appears different in each of the 100 epochs during model training. As a result, a slight decrease in model performance is anticipated, given that the model encounters a 'new' dataset each time. However, for datasets like MNIST, CIFAR10, and Ogbg-Code2, we observed only about a 1% drop in model accuracy. This finding suggests that directional information is considerably less significant, and potentially negligible, compared to the node or edge features.

Since the study of flipping edges is an independent experiment, we establish a standard pipeline applicable to all datasets. In the case of the Twitter dataset we first generate Twitter datasets for all the experiments. Then, for the random flip study, we randomly flip the edges for each step. The changes in the accuracy highlight the impact of edge directionality in this dataset, though there may also be an effect of class label confusion. Please note that, whatever may be the final effect, DiGT displays superior performance compared to all other (undirected) models, which leads further credence to the important role of directionality in the Twitter dataset.

Q1. We provide the answer to this question in our general response. As noted, our model does not use more parameters, since we adjust the choices to keep it aligned with the competitive baselines.

Q2. Thank you for your suggestions. We will mark "OOM" on these tables.

Thank you authors for your commitment into providing additional clarifications. Many of my concerns have been addressed, but I still have two concerns remaining:

• Interactions between dual embeddings. I agree that exchanging information across source and target embeddings would help in performance. However, due to commutativity of vector addition, adding the two embeddings and processing the result through two separate linear layers to obtain dual embeddings for the next layer (Equations 9 and 10) loses information on the ordering of the two embeddings, and thus we can no longer tell which embedding corresponds to the source or target. One simple way to exchange information while preserving the source/target ordering would be to fuse the embeddings via $S' = S+ L_{VS}(T)$ (similar to feature fusion in [A]), instead of $S' = L_{VS}(S+T)$ which is used in the presented work. Did I miss something that makes this commutativity a nonissue?
• Experiments under Randomized Directionality. My previous concern was that Table 1 only shows results from certain model-dataset pairs, and does not seem conclusive to say that "directionality does not play significant role in these datasets." While the authors have referred to Tables 6 and 7 in response, I am guessing the authors meant Tables 3 and 4 since Tables 6 and 7 pertain to another experiment. Nonetheless, these results still do not cover all model-dataset settings and the numbers still are not really convincing.

Because of these remaining concerns, I will retain my score.

[A] Zhu et al., Graph Geometry Interaction Learning. NeurIPS 2020.

We appreciate your positive feedback. Here are our answers to the points raised:

W1. Visualizing the attention scores would be interesting, something we can explore for the future.

W2. We used SVD-based positional encodings (PEs) since the left and right singular values/vectors can be used very naturally for directed graphs, unlike the Graph Laplacian, which is symmetric. For a comparison with Magnetic Laplacian PEs, see Q2 below.

W3. We have included the number of parameters used by our model and others in the general response above. Thus, our method is no more and no less scalable than other (dense) transformer based models.

Q1. We ran our model on the WebKB and the Telegram datasets. WebKB contains Cornell, Wisconsin, and Texas datasets. The table below reports on the accuracy of DiGT vs other baselines; we see clear improvements using DiGT (we do not include std-dev for clarity, but we will include them in our revised paper). Nevertheless, transformer-based models work only for medium sized datasets; for large number of nodes all (dense) attention methods will have scalability issues.

[i] Z. Tong, Y. Liang, C. Sun, X. Li, D. Rosenblum, and A. Lim. Digraph inception convolutional networks. Advances in Neural Information Processing Systems, 33, 2020.

[ii] Z. Tong, Y. Liang, C. Sun, D. S. Rosenblum, and A. Lim. Directed graph convolutional network. arXiv preprint arXiv:2004.13970, 202

Q2. Thanks for suggesting the use of the Magnetic Laplacian PEs, which are indeed even better than SVD based positional encodings, as shown in the table below (we will include these new results in Table 2 in our updated paper; we do not show the std-dev values below for clarity, but we will include those as well):

We want to thank you for your thoughtful comments. Below are our responses:

W1. Our DiGT model is inspired by the well known HITS approach for directed graphs using notion of authority and hub scores (which, are eigenvectors of the $A^T A$ and $A A^T$ matrices). Our key innovation is the use of source/target vectors (embeddings) with a learnable adjacency matrix in the HITS approach, and thus it has a solid theoretical foundation.

W2. We not only suggest a novel learnable formulation for the directed embeddings, but we also study alternative formulations for incorporating directionality, which we study empirically. Thus, our work is not just a set of ad-hoc methods, but rather a systematic study of how direction can be added effectively within transformer models.

W3. We disagree. If a dataset has no directionality, then how or why will a directional transformer help? For example, if a graph is undirected, then its adjacency matrix A, will be symmetric, and the notion of hub or authority collapse -- $A^TA$ and $A A^T$ will be the same.

W4. Please note that directionality is not significant in the original ogb-code2 dataset, as we have shown in Table 1. Furthermore, please note that Geisler et al preprocess and modify the original graph to get competitive results, but we consider the original graph, which has little directionality.