Exploring and Unleashing the Power of Message Passing on Heterophilous Graphs

We would like to thank you for your deeply thorough review. We have carefully considered your comments and suggestions, and the following are our detailed responses.

Weakness #1: Explanations about Eq.9.

Answer #1: Thank you for pointing out this error. We initially described the message passing of the supplementary neighborhood in text, but in the revised version, we have added a separate formula to describe it more accurately. Specifically, the aggregated message $\mathbf{Z}^{l-1}r$ in the supplementary neighborhood is replaced by $\mathbf{Z}^{l-1}{ptt}$, which represents the virtual prototype nodes. These virtual nodes are obtained through the same message-passing mechanism as the real nodes. Therefore, $\mathbf{A}^{sup}, \mathbf{B}^{sup} \in \mathbb{R}^{N \times K}$ and $\mathbf{Z}^{l-1}_{ptt} \in \mathbb{R}^{K \times d_r}$ satisfy the inner product requirements.

Weakness #1 & Weakness #2: Explanations about $\mathbf{A}^{sup}$ and $\mathbf{B}^{sup}$.

Answer #2: The supplementary neighborhood indicator $\mathbf{A}^{sup}$ contains $K$ additional prototype nodes. Given the sparsity of graphs, some nodes may have low degrees, and the all-one neighborhood indicator ensures that each node has access to messages from all classes. Meanwhile, the supplementary aggregation guidance, $\mathbf{B}^{sup} = \hat{\mathbf{C}} \hat{\mathbf{M}}$, specifies the desired semantic neighborhood of the nodes, i.e., the desired proportion of neighbors from each class, according to the probability that nodes belong to each class. As a result, $\mathbf{A}^{sup} \odot \mathbf{B}^{sup}$ provides each node with the desired neighborhood messages based on the predicted labels.

Weakness #3: Explanations about $\text{H}$ in Eq.5 and $\tilde{\mathbf{C}}$ in Eq.6.

Answer #3: $H(p) = -\sum_i p_i \log(p_i)$ represents the information entropy. $\tilde{\mathbf{C}}$ refers to the predicted soft labels generated by the model, which is described in Eq.12 (or Eq.14 in the revised version).

We are expecting these could be helpful in answering your questions. If you have any further questions, please feel free to contact us.

We would like to thank you for your deeply thorough review. We have carefully considered your comments and suggestions, and the following are our detailed responses.

Weakness 1: Concern about the compatibility matrix.

Answer #1: Thank you for your valuable comments. Indeed, the compatibility matrix models the connection preferences among classes rather than nodes, which may create a gap between the CM and the neighborhood of a single node due to sparsity and noise in real-world graphs, as discussed at the end of Section 4. Some existing methods use the compatibility matrix to redefine pairwise relations (i.e., edge weights) for existing edges, such as label propagation in CLP [1], log-likelihood estimation in EPFGNN [2], and prior belief propagation in CPGNN [3]. However, these methods still suffer from sparsity and noise. In contrast, CMGNN leverages the compatibility matrix and virtual neighbors to construct supplementary messages while preserving the original neighborhood distribution in the CM, resulting in better performance. A more detailed qualitative and quantitative comparison and analysis between CMGNN and existing CM-based methods are available in Section 6.3 and Appendix H.2.1.

References:

[1] Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation.

[2] Explicit Pairwise Factorized Graph Neural Network for Semi-supervised Node Classification.

[3] Graph Neural Networks with Heterophily.

Weakness #2: Comparisons with spectral GNNs.

Answer #2: Thank you for your suggestion. On the one hand, the message-passing mechanism plays a significant role in existing heterophilous GNNs and is relatively straightforward to understand. Therefore, we proposed the HTMP mechanism to provide a unified understanding of several representative methods from a message-passing perspective. On the other hand, we have also reviewed some relatively simple spectral GNNs and understood them from a message-passing perspective, such as FAGCN and ACMGCN. For more complex methods like BernNet and ChebNetII, we will consider conducting experiments to compare their performance and evaluate the feasibility of understanding them from the message-passing perspective.

Weakness #3: Explanations about the results of the ablation study.

Answer #3: In the implementation of CMGNN, the weight parameter of the DL loss, denoted as $\lambda$, has a search space that includes 0, as shown in Table 7. The best choice of $\lambda$ for these three datasets is 0, which results in identical performance for both the "CMGNN" and "W/O DL" settings. This may be due to the discriminability of the desired neighborhood messages reaching a bottleneck, where further improvement by DL is no longer possible.

Weakness #4: Format of Figure 8.

Answer #4: Thank you for this suggestion! We have updated it to PDF format in the revised version.

We are expecting these could be helpful in answering your questions. If you have any further questions, please feel free to contact us.

We would like to thank you for your deeply thorough review. We have carefully considered your comments and suggestions, and the following are our detailed responses.

Weakness #1: The association between the HTMP mechanism and the heterophily issue.

Answer #1: Indeed, HTMP is an extension of the vanilla message-passing mechanism. Some components, like the FUSE and COMBINE functions, may be applicable to other topics related to message passing. However, certain specific designs are exclusive to heterophily, such as ego-neighbor separation and negative adaptive weight. On the other hand, some works have found that the over-smoothing issue mentioned shares the same root causes as heterophily and can be addressed with similar approaches. Thus, it is reasonable that similar designs exist in both cases.

Weakness #2: The scalability of CMGNN.

Answer #2: Thank you for pointing this out. To further evaluate the scalability of CMGNN, we conducted additional experiments on three large-scale datasets, comparing its performance with representative baselines. The details of the datasets and the results are listed as follows (or in Table 8 of the revised version). As a result, CMGNN achieves superior performance while maintaining good efficiency, especially on snap-patents, with a 22% improvement, which demonstrates its great scalability.

Weakness #3: The underlying reasons for component design in CMGNN.

Answer #3: CMGNN aggregates messages from three neighborhoods for each node: the ego, raw, and supplementary neighborhoods. The first two are the most commonly used and contain information about the central node itself and its one-hop neighbors, respectively, while the latter introduces a new way to utilize the compatibility matrix. Given the diverse situations of different nodes, we use adaptive weighted addition to combine the messages from the three neighborhoods. Additionally, the messages from multiple layers are concatenated to preserve information with varying levels of locality in the graph.

Weakness #4: Problems caused by additional structural features.

Answer #4: Utilizing additional structural features is a common approach in heterophilous GNNs, as it offers another way to leverage connection relationships, introducing both discriminative and redundant information. This creates a trade-off between the advantages and disadvantages. In CMGNN, the use of additional structural features is optional, meaning they can be excluded in large-scale graphs to ensure scalability. Additionally, we have conducted an ablation study to examine the effects of these features, with results reported in Appendix H.2.2 (or H.2.3 in the revised version). CMGNN can still achieve competitive results even without using additional structural features. The results in Answer #2, which do not use these features, also support this conclusion.

Question #1: The difference in computation time between updating CM per epoch or not.

Answer #5: We conducted a comparison of computation times and show the results below, where "CMGNN*" refers to the identical model, except that the CM is updated per epoch. According to the results, the CM update strategy reduces computation time by up to 25% (on Pubmed) while maintaining similar performance.

We are expecting these could be helpful in answering your questions. If you have any further questions, please feel free to contact us.

We would like to thank you for your deeply thorough review. We have carefully considered your comments and suggestions, and the following are our detailed responses.

W1 & Q1: The causal relationship between compatibility matrix and representations.

A1: The compatibility matrix (CM) is used to represent the connection preferences inherent in the graph, which are computed from node labels and edges rather than from representations or model predictions. Therefore, better representations are not the cause of a more desirable CM. Theorem 1 shows a positive correlation between the discriminability of CM and the discriminability of representations in the message-passing mechanism. Thus, existing heterophilous methods can enhance the CM in various ways (e.g., by modifying the aggregated edge weights) to learn better representations.

W2: The theorems and lemmas are overly simple.

A2: Indeed, the theorems and lemmas are simple, but they lead to interesting conclusions about the CM. Existing works treat CM as a fixed property of graph data, but we argue that it can be enhanced for heterophilous message passing to learn better representations.

W3: The motivation for "supplementary neighborhood construction" is not explained.

A3: Considering the sparsity of graphs, some nodes may have low degrees, limiting the potential of CM. Thus, we construct supplementary neighborhoods to guarantee accessibility to messages from each class for all nodes. We have added more detailed descriptions of this motivation in the revised version.

W4: No time and space complexity analysis of the proposed method.

A4: Due to page limitations, the efficiency study, including computational and memory complexity analysis as well as empirical runtime comparisons, is provided in Appendix H.2.5 (or H.3 in the revised version).

W5: The claim about "New datasets" is inappropriate.

A5: We have revised the wording to "Newly organized datasets" in the revised version. Specifically, to address the issues of method comparison caused by drawbacks like data leakage in existing datasets, we have recollected and filtered suitable graph datasets. This collection spans various levels of homophily, providing a robust foundation for performance evaluation. However, the benchmark datasets are not the main contribution of the paper, and we have not modified the details of the datasets. Thus, we have corrected the description accordingly.

W6: Supplement of baseline methods.

A6: Thank you for your suggestion. We will consider adding them to the baseline methods for comparison in further revised versions, due to the limited time and computational resources.

W7: The writing needs improvement.

A7: Thank you for the feedback. We have revised some of the expressions and will continue to improve the writing in future revisions.

Q2: Why design weights in the form of Eq.7?

A8: Eq.7 defines a weighting function that accounts for the effects of node degrees. The core idea is that nodes with lower degrees should correspond to lower weights in the CM estimation, as high-degree nodes usually have more representative neighborhoods, while low-degree nodes often have incomplete ones. Meanwhile, the relationship between weights and node degrees is not linear. For low-degree nodes, increases in degree should yield more significant benefits compared to high-degree nodes. Beyond a certain threshold, increases in degree offer diminishing returns. We empirically chose K and 3K as fixed thresholds for the weighting function to simplify the design without extensive trials. This approach is straightforward and can be substituted with any other forms that meet the same criteria. While further design is possible, it is not a priority compared to other modules.

Q3: The performance improvement is marginal compared to the baselines.

A9: The main contribution of this paper is to provide a unified theoretical framework for existing heterophilous GNNs and to re-understand the underlying mechanism. Guided by the HTMP mechanism, CMGNN has a simple architecture and outperforms existing complex methods. Furthermore, we conducted additional experiments on large-scale graphs with results shown in Table 8 of the revised version. The performance and efficiency comparison demonstrates the effectiveness of CMGNN, particularly on snap-patents (with a 22% improvement).

Q4: What does "k neighborhoods" mean? How do you count the number of neighborhoods for a node in question?

A10: We apologize for the confusion, but we are unsure what "k neighborhoods" refers to, as this term does not appear in the paper. If you are referring to the "R neighborhoods" mentioned in Section 3, this refers to the multiple neighborhoods used by heterophilous GNNs for message passing, such as raw, high-order, and similarity-based neighborhoods.

We are expecting these could be helpful in answering your questions. If you have any further questions, please feel free to contact us.