Monophilic Neighbourhood Transformers

Dear Reviewer,

We are grateful for your insightful comments and the opportunity to clarify our work. We have reevaluated your concerns and would like to address them in a sequence that we hope will provide a clearer understanding of our partitioning algorithm (W2), before proceeding to other matters such as baselines (W3) and theoretical analysis (W1 & W4).

We acknowledge that our initial explanation may not have fully conveyed the intricacies of our method. To rectify this, we would like to walk you through our approach, using Eq.1 to Eq.3 and corresponding to Figure 2c, with a focus on calculating the representation of node 1 (the double-circled node in Figure 2c).

Firstly, your interpretation of Eq.3 in W2.2 is correct. This step involves collecting edge messages from 1-hop neighbours. In Figure 2c, the information of node 1 and node 2 is mixed and encoded as a blue square. Subsequently, Eq.2 represents the self-attention mechanism where all edge messages (squares) engage in message exchanging within their belonging neighborhoods. This is depicted in Figure 2c as the interactions among squares of the same colors. Finally, Eq.1, the aggregator, combines the edge messages related to node 1 (the three squares surrounding node 1 in the figure) to form node 1's representation. It is important to note that these aggregated edge messages have already undergone message exchanging within their neighborhoods, thus incorporating 2-hop information (W2.2). For instance, the blue square aggregated by node 1 also includes information from nodes 3, 4, 5, and 6.

With this understanding, we address your points W2.1, W2.2, and W2.3.

W2.1 Why are 2-hop neighbors useful for node classification on graphs regardless of whether they are homophilic or heterophilic?

We appreciate your grasp of how NT handles heterophily through the monophily property of 2-hop neighbors. Regarding homophily, NT's effectiveness does not rely on the usefulness of 2-hop information but on its adaptability of switching to use 1-hop information. When a graph is homophilic and benefits from 1-hop information processing, NT can effectively reduce its complexity to operate like a normal GNN based on message passing, as mentioned in lines 104 to 106. This occurs when NT in Eq.3 primarily uses the information from the neighbours, reduces self-attention of Eq.2 to a simple feed-forward transformation. In essence, NT can flexibly utilize information from both 1-hop and 2-hop neighbors, making it suitable for both homophilic and heterophilic graphs.

W2.2 It looks like the proposed method still utilizes information from 1-hop neighbors. No information from 2-hop neighbors is included.

As previously explained, a node's representation is derived from all its 'belonging' neighborhoods, a.k.a. neighbours' neighbourhoods, which inherently includes information from neighbors of neighbors.

W2.3 Why previous methods cannot capture the information from 2-hop neighbors? If the 2-hop information is that useful, I think many previously proposed methods should be able to capture it.

You are correct that several previous methods have incorporated 2-hop information to address heterophily, as discussed in the Introduction and Related Works sections. However, these methods often rely on the second-order adjacency matrix, which can result in the loss of certain information, such as the specific path through which a 2-hop neighbor is connected. Our method, as outlined in Eq.3, preserves this information, ensuring that message exchanging within each neighborhood is uniquely conditioned on the central node. This enhances the diversity of exchanging patterns and the expressiveness of the aggregated representations, as detailed in lines 101 to 104.

We trust that this detailed explanation clarifies our NT method and its novel aspects.

Thank you for your patience and for prompting us to delve into the theoretical aspects of our work. We have carefully considered your suggestions and have strived to formalize the theoretical propositions to address your concerns. Below, we outline the theoretical foundations and propositions that underpin our approach

Proposition 1: When the combiner concentrates on information from central nodes of neighbourhoods, the Neighbourhood Transformer is a message passing layer.

As analyzed in line 223 to 225, when Eq.3 omits $\boldsymbol{H}' _{k,:}$ and $\boldsymbol{M}'^{(j)} _{(k)}$ to become $\boldsymbol{Z} _{(j,k),:} = \phi(\text{Combiner}(\boldsymbol{H}' _{j,:})) \triangleq \boldsymbol{Z}^{(j)},$ Eq.2 becomes a simple transformation of $\boldsymbol{Z}^{(j)}$ as $\boldsymbol{M}^{(j)} = \phi(\text{SelfAttention}(\oplus \\{ \boldsymbol{Z}^{(j)}, \boldsymbol{Z}^{(j)}, \ldots, \boldsymbol{Z}^{(j)} \\} ) = \begin{bmatrix} \phi(\boldsymbol{Z}^{(j)} \boldsymbol{W} _v) \\\\ \phi(\boldsymbol{Z}^{(j)} \boldsymbol{W} _v) \\\\ \cdots \\\\ \phi(\boldsymbol{Z}^{(j)} \boldsymbol{W} _v) \end{bmatrix}.$ Then, the final representations (Eq.1) are actually equivalent to the output of a message passing layer: $\boldsymbol{H} _{i,:} = \text{Aggregator}(\\{ \boldsymbol{M}^{(j)} _{(i),:} | v _j \in \mathcal{N}(v _i) \\}) = \text{Aggregator}(\\{ \phi(\phi(\text{Combiner}(\boldsymbol{H}' _{j,:})) \cdot \boldsymbol{W} _v) | v _j \in \mathcal{N}(v _i) \\}).$

$\blacksquare$

Proposition 1 demonstrates that NT is compatible with message passing (MP) and possesses superior or at least equivalent expressiveness. This ensures that NT can leverage the proven strengths of MP when dealing with homophily, while still potentially offering additional benefits.

Proposition 2: When the combiner omits information from central nodes of neighbourhoods, the Neighbourhood Transformer with linear-attention is a two-layered message passing network.

When omitting $\boldsymbol{H}' _{j,:}$ and $\boldsymbol{M}'^{(j)} _{(k)}$ in Eq.3 and using linear-attention in Eq., the final representations of Eq.1 are $\boldsymbol{H} _{i,:} = \text{Aggregator}( \\{ \phi(\frac{\boldsymbol{\hat Q} _{i,:} \cdot \boldsymbol{K} _v^{(j)}}{\boldsymbol{\hat Q} _{i,:} \cdot \boldsymbol{K} _1^{(j)}}) | v _j \in \mathcal{N}(v _i) \\} ),$ where $\boldsymbol{K} _v^{(j)}$ and $\boldsymbol{K} _1^{(j)}$ indicates the formulas $\boldsymbol{\hat K}^T \cdot \boldsymbol{V}$ and $\boldsymbol{\hat K}^T \cdot \boldsymbol{1} _{n \times 1}$ of Performer applied in the neighbourhood $\mathcal{N}(v _j)$. In detail, the element at the position $(x, y)$ of $\boldsymbol{K} _v^{(j)}$ is $\sum\limits _{v _k \in \mathcal{N}(v _j)} \hat K _{k,x} V _{k,y}$ and the $x$-th element of $\boldsymbol{K} _1^{(j)}$ is $\sum\limits _{v _k \in \mathcal{N}(v _j)} \hat K _{k,x}$.

Regarding $\boldsymbol{K} _v^{(j)}$ and $\boldsymbol{K} _1^{(j)}$ as the result of a message passing layer, which aggregates information of $\mathcal{N}(v _j)$ to node $v _j$, NT can be rewritten as a two-layered message passing network, as

We would like to express our gratitude for your guidance, which has been instrumental in refining the theoretical foundation of our partitioning algorithm as presented in Section 4.2.2. Below, we outline the assumptions and proposition that we have developed to formalize our analysis:

Assumption 1 on paralleled processing: The memory consumption of applying the transformer to a group of neighbourhoods is proportional to the group's area, defined as the product of the number of neighbourhoods and their maximum size.

Assumption 2 on sequential processing: Sequentially processing two neighbourhood groups with areas $s_1$ and $s_2$ consumes memory proportional to $\max(s_1, s_2)$.

With these assumptions in place, we are able to state and prove the following proposition:

Proposition 3: Given any partitioning that divides neighbourhoods into two groups, there exists an alternative partitioning that requires the same or less processing memory, where all neighbourhoods in one group are not smaller than those in the other group.

Considering a partitioning where group $G_1$ contains $c_1$ neighbourhoods and group $G_2$ contains $c_2$ neighbourhoods, with the maximum size $d_1$ of neighbourhoods in $G_1$ being not smaller than that $d_2$ of $G_2$ ($d_1 \ge d_2$).If the smallest neighbourhood (with size $d_3$) in $G_1$ is smaller than the largest one (with size $d_2 \gt d_3$) in $G_2$, we can swap their positions to create two new groups $G'_1$ and $G'_2$. The area of $G'_1$ remains unchanged since $\max(d_1, d_2) \times c_1 = d_1 \times c_1$, while the area of $G'_2$ is unchanged or reduced since $\min(d_3, d_4) \times c_2 \le d_2 \times c_2$, where $d_4$ is the size of the second-largest neighbourhood in $G_2$. We can keep swapping the smallest neighbourhood in the first group with the largest neighbourhood in the second group if the former is smaller than the latter until any neighbourhood in the first group is not smaller than those in the second, with the processing memory remaining unchanged or reduced.

$\blacksquare$

From Proposition 3, we conclude that the optimal partitioning can be achieved by first ordering the neighbourhoods and then scanning linearly for the partitioning point, as done in line 8 of Algorithm 1. The complexity of this search is $O(n \log n)$, accounting for the sorting step.

We will include the above theoretical analysis in the appendix of our paper and would like to thank you once again for highlighting the areas where our work could be strengthened.

Dear Reviewer,

Thank you for your patience and for providing us with the opportunity to address your concerns. We have carefully considered your comments and attempt to resolve them as follows. Should you find any issues or omissions in our responses, please do not hesitate to inform us.

W1: It is recommended to discuss related work focusing on monophily.

We acknowledge your point regarding the monophily. In fact, monophily is a property that emerges from heterophily. When a graph is heterophilic, where the traditional message passing methods for homophily fails, we may further utilize the property of monophily to help handling heterophily. Thus, the work of monophily is actually a subset of the work of heterophily. In our Introduction and Related Works sections, we have discussed heterophily, which inherently covers the subset of monophily-related work.

W2: Need more experimental analysis such as why the performance improvement of NT on homophilic graphs is not as significant as on heterogeneous graphs.

We appreciate your suggestion for further experimental analysis. On heterophilic graphs, different from baselinses' utilizations of the plain second-order adjacencies, NT exchanges messages conditioned on the central node, which enriches the diversity of patterns and enhances representation expressiveness, as detailed in lines 100 to 107. On homophilic graphs, NT may downgrade to 'mimic' traditional message passing, which is already effective for such graphs, as explained in lines 451 to 453 and 223 to 225. In conclusion, NT has an improvement when comparing against heterophilic GNNs while are compatible with homophilic GNNs. We think this is why NT's performance improvement on heterophilic graphs is more significant than on homophilic graphs.

Q1: Is there any limitation of the linear attention mechanism? How might these affect the model's performance? Are there specific scenarios where linear attention might fall short compared to traditional self-attention?

We have conducted experiments to investigate the limitations of the linear attention mechanism, as detailed in lines 522 to 530 and illustrated in Figure 6. Our findings indicate that while a pure linear-attention model (Performer) underperforms on 5 out of 10 datasets, our NT method, which is a hybrid of linear-attention and self-attention (Switchable), remains competitive with pure self-attention (Transformer) across all datasets. This suggests that the combined approach mitigates the potential shortcomings of linear attention in certain scenarios.

Q2: How does the NT perform on graphs with extreme degree distributions that are significantly different from those in the training?

Your question regarding the performance of NT on graphs with extreme degree distributions is insightful. We have conducted an analysis to measure the discrepancy between degree distributions in the training set and beyond. We first approximate the averaged size of belonging neighbourhoods for each node using $S = \text{deg}(A^2) / \text{deg}(A)$, where A is the adjacency matrix and deg is a function to derive node degrees from the adjacency matrix. Then, with 100 histogram bins, we transform $S[m]$ and $S[\bar m]$ into two distributions $P$ and $Q$, respectively, where $m$ indicates the training set. After that, we calculate the discrepency between the two distributions as $\sum\limits_i |p_i - q_i|$ and report the discrepencies for the 10 datasets in the following table.

The results indicate varying levels of discrepancy across the datasets, with Minesweeper showing low discrepancy and WikiCS showing high discrepancy. Despite these variations, NT maintains consistent performance, as demonstrated by the experiments in our paper.

We hope that these responses adequately address your concerns and provide a clearer understanding of our work. We are committed to further refining our manuscript based on your valuable feedback.

Best regards.

Dear Reviewer,

We sincerely appreciate your valuable insights and the time you have dedicated to reviewing our manuscript. Upon careful consideration of your comments, we have noted that there might be some misunderstandings regarding the partitioning algorithm we have proposed. We would very like to address these concerns (Q2 & Q1) first, in order to provide a clearer understanding of our work and facilitate a more accurate assessment. Following this clarification, we will proceed to address the other issues you have raised, such as the SoTA Graph Transformers (Q3), the novelty (W4), and the scalability (W1 & W2) of our approach.

Q2: What is the difference between the partitioning algorithm and METIS-like algorithms?

We would like to clarify a point regarding our partitioning algorithm.

The primary objective of the algorithm is not to partition a large graph into independent subgraphs for mini-batch training, akin to the METIS algorithm. Instead, our algorithm groups graph nodes in a way that still requires full-batch training. This is because, in NT, applying transformers in all neighborhoods is only an intermediate step; the final representation of a node is then aggregated from all its belonging neighborhoods.

We illustrate this difference with an example. Suppose METIS divides a graph into isolated subgraphs A, B, and C. A graph model can then be applied to one of these subgraphs, say A, to obtain the representation of a node, say $v$ that is in subgraph A. However, in NT, even if we divide graph nodes into groups A, B, and C, the process is different. If node $v$ is in group A and has connected nodes $u$ in group B and $w$ in group C, the representation of node $v$ is not derived from applying the transformer in group A. Instead, it is obtained by gathering information from the neighborhoods of nodes $u$ and $w$ after the transformer has been applied to groups B and C, respectively. In summary, while the graph nodes are partitioned in NT, all their neighborhoods must still be processed by the transformer, with their results being combined later.

Our partitioning algorithm is designed to optimize both memory and computation time during the transformer's processing, before the results combination, as depicted in Figure 1 and explained in lines 73 to 80 of our manuscript. Thus, our method is tailored only to address the unique challenges that arise in NT and is fundamentally different from METIS-like graph partitioning algorithms.

We sincerely hope that this explanation clarifies any misunderstanding you may have had about our partitioning algorithm. Should there be any further lack of clarity, please do not hesitate to reach out to us.

Q1: How is $p$ determined?

As mentioned in line 195 of Section 3.3, $p$ is a hyperparameter coming from Performer [1]. The original article on Performer indicates that setting $p = h \log h$ is suffices to accurately approximate the attention matrix.

[1] Krzysztof Marcin Choromanski, et al.: Rethinking Attention with Performers. ICLR 2021

We would like to provide a detailed comparison between our proposed NT and the SoTA Graph Transformers (GT), specifically the Polynormer [1], by referencing the latest data from Polynormer’s publication. We have compiled the following two tables to illustrate this comparison.

Table A: Performance on heterophilic graphs.

In Table A, we observe that NT outperforms GT on the Roman Empire dataset by a significant margin due to its utilization of directional information. Since GT layers do not consider the edges of nodes, they are unable to model the directionality of edges. On other heterophilic datasets, NT is only slightly behind Polynormer.

We would like to emphasize that the hyperparameter budgets for Polynormer are higher than those for NT. Specifically, even without considering the additional GT layers, the maximum number of its convolutional layers is 10, while for NT, it is 5. This is because many of our (and also Performer's) baselines, which are cited from [2], are with this low-budget settings.

Table B: Performance on homophilic graphs.

In Table B, NT is ranked as one of the top 2 methods across all five homophilic datasets. The averaged rank for NT is $(2+2+1+2+2)/5=1.8$, which is better than Polynormer’s average rank of $(1+1+4+3+1)/5=2$. This demonstrates that our method maintains strong competitiveness when compared to SoTA GTs.

In conclusion, NT demonstrates competitive performance against the SoTA GTs across both heterophilic and homophilic datasets.

However, we would like to emphasize additionally that, as analyzed in the Related Works, GTs are unable to replace Message Passing Neural Networks (MPNN) as an independent method due to the information loss of topology. Consequently, the current GT methods are usually combined with MPNNs (e.g. GraphGPS) and would be more accurately described as 'GT-augmented MPNNs'. In contrast, our research demonstrates that NT is capable of handling heterophily and can be adaptively compatible with MP, potentially replacing it as a key component in future GNN architectures. This is actually orthogonal to the GT approach; that is, NT can also be combined with GT to form an enhanced 'GT-augmented NT'. This is the primary reason we did not directly compare GT and NT in the main text of the manuscript.

We will include the above comparisons in the appendix of our paper to provide a more comprehensive evaluation of our method. Thank you again for your valuable suggestions.

[1] Krzysztof Marcin Choromanski, et al.: Rethinking Attention with Performers. ICLR 2021

[2] Oleg Platonov, et al.: A critical look at the evaluation of GNNs under heterophily: Are we really making progress? ICLR 2023

[3] Ladislav Rampásek, et al.: Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS 2022