Revisiting the Message Passing in Heterophilous Graph Neural Networks

Thanks for your insightful and constructive review of our work. The following are our detailed responses to the reviewer’s thoughtful comments. We are expecting these could be helpful in answering your questions.

Question #1 & Weakness #1: The connections and differences between CMGNN and existing methods that use compatibility matrices.

Answer #1: Thanks for your suggestion! We would like to highlight that the usage of compatibility matrices in CMGNN differs significantly from existing methods.

Existing methods [1, 2, 3] utilize the compatibility matrix (CM) to redefine pair-wise 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]. In contrast, CMGNN leverages CM and virtual neighbors to construct supplementary messages while preserving the original neighborhood distribution. As a result, CMGNN benefits from its approach to utilizing CM in the following aspects compared with existing methods [1, 2, 3]:

• Better robustness for low-quality pseudo labels: Existing methods utilize CM to guide the weights of propagation, which can lead to error accumulation with inaccurate pseudo labels. This is a common limitation of CM-based methods. In CMGNN, the CM is used to construct supplementary messages while original neighborhoods are preserved, mitigating the impact of inaccurate pseudo labels.
• Unlock the effectiveness of CM for low-degree nodes: Existing methods redefine pair-wise relations only for existing edges, limiting the effectiveness of CMs for low-degree nodes. In CMGNN, virtual neighbors can provide prototype messages from every class, enhancing neighborhood messages for low-degree or even isolated nodes.
• More accurate estimation of CM: While existing methods take naive approaches to estimate or initialize CM, CMGNN considers the effects of node degrees and model prediction confidence, resulting in more accurate CM estimation, especially in real-world situations. Additionally, CM in CMGNN is continuously updated with more accurate pseudo labels, creating a positive cycle.

For quantitative comparison, we will add comparative experiments with these methods in the revised version, including performance, estimation accuracy of CM, efficiency, etc.

Question #2 & Weakness #2: Theoretical analysis for the observations in the paper.

Answer #2: Thank you for your valuable comment! We have provided theoretical analyses supporting a core condition behind Observation 1 and 2: the discriminability of obtained representations is positively correlated with the discriminability among classes in CM. For detailed analyses, please refer to the global response due to space limits.

Question #3 & Weakness #3: The differences and unique insights of proposed HTMP compared to existing categorizations and unifications.

Answer #3: Thanks for pointing out this! We delve into the message-passing mechanism in heterophilous GNN methods and propose a unification HTMP that clarifies the intrinsic mechanisms of these methods. In contrast, existing surveys [4, 5, 6] provide a macroscopic view, categorizing and unifying heterophilous GNNs with comprehensive but shallow analysis. Therefore, HTMP offers significant differences and unique insights compared to existing surveys [4, 5, 6]:

• HTMP provides a uniform symbolic form and categorizes methods based on the values of component modules (e.g. neighborhood indicator and aggregation guidance). As a comparison, existing surveys categorize methods based on their ideas and designs, which are described only by words but are not limited to message-passing mechanisms (e.g. learning strategies).
• As a result, the fine-grained HTMP can concretely guide the design of new heterophilous message-passing mechanisms through its modular architecture, whereas existing surveys offer guidance primarily at the conceptual level.

The detailed differences and connections with each work [4,5,6] are as follows:

• Survey [4]: This work categorizes the designs of heterophilous GNNs into non-local neighbor extensions and GNN architecture refinement. The first group corresponds to part of the neighborhood indicator in HTMP, while the second group includes some designs of HTMP functions (AGGREGATE, COMBINE and FUSE). It organizes heterophilous designs directly, whereas HTMP provides systematic categorizations from a message-passing perspective.
• Survey [5]: This work focuses on learning from heterophilous graphs, where message passing is only a minor aspect of its taxonomy. Thus, it offers a broader view, whereas HTMP is more specialized in message-passing mechanisms.
• Survey [6]: This survey examines the impact of heterophilous graph characteristics on GNNs. For categorizations, it simply lists some effective designs in heterophilous GNNs, whereas HTMP offers a clearer categorization of these and additional designs.

Question #4 & Weakness #4: The tradeoff between accuracy and training times of CMGNN and baselines.

Answer #4: Thank you for this suggestion! We have followed your suggestion and visualized the tradeoff between accuracy and training time in the supplemental PDF of the global response. From the results in the figures, we can find that our proposed CMGNN achieves the best performance while maintaining relatively low computational complexity. Compared to the top-2 performed baselines (OrderedGNN, GCNII), CMGNN has superior classification performance and lower time consumption.

Thank you for engaging in the discussion.

We greatly appreciate your constructive comments, which have contributed to the improvement and solidity of our work!

Best regards!

We sincerely appreciate your thoughtful review of our paper. Below, we address the reviewer's concerns point by point, hoping that a better understanding of every point can be delivered.

Question #1: The contributions of benchmark datasets and unified codebase.

Answer #1: To address the issues of method comparison caused by drawbacks like data leakages and extremely imbalanced classes in existing datasets, we have collected and filtered suitable graph datasets from heterophilous GNNs methods and other fields (e.g. Anomaly Detection). 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. Instead, we consider them an additional resource to assist the community in better evaluating methods.

In addition to addressing dataset limitations, we have built a unified heterophilous GNN codebase, which has the following contributions:

• We have gathered the official and reproduced codes of 13 representative baseline methods and integrated them along with our CMGNN into a unified PyTorch-based codebase. All methods share the same call interfaces, ensuring a fair comparison environment.
• The codebase will be open-sourced, enabling easier research and further development of this field, such as quickly evaluating baseline methods on new datasets.

Question #2: The explanation and discussion of Eq.9.

Answer #2: Eq.9 defines a weighting function considering the effects of node degrees. The core idea is that nodes with lower degrees correspond to lower weights during compatibility matrix estimation, as high-degree nodes usually have representative neighborhoods while low-degree nodes often have incomplete ones. However, the relationship between weights and node degrees should not be 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 yield tiny benefits.

We have empirically chosen $K$ and $3K$ as fixed thresholds for the weighting function to simplify the design without multiple attempts. This approach is straightforward and can be substituted with other forms that meet the same criteria. It allows for further design but is not a priority compared to other modules.

Weakness #1: Suggestions for paper presentation.

Answer #3: Thank you for these suggestions. We will work on improving the paper presentation and correcting the spelling errors in the revised version. Here is a detailed explanation of "good" heterophily and "bad" homophily:

• The conception of "good" heterophily, introduced by [1], is based on empirical observations and highlights the existence of different kinds of heterophily. Specifically, GCNs can achieve strong performance in "good" heterophily settings, where the compatibility matrix exhibits strong discriminability. This concept is qualitative rather than quantitative.
• "Bad" homophily describes a scenario where, despite having more neighbors from the same class than from any other classes, the homophily level is insufficient for vanilla message-passing methods (GCN, GAT) to outperform MLPs.

Reference:

[1] Is Homophily a Necessity for Graph Neural Networks? in ICLR 2022.

Weakness #2: Suggestion for paper architecture.

Answer #4: Thanks for this suggestion. We will consider it in the revised version.

Weakness #3: The flow chart and algorithm of CMGNN.

Answer #5: Thanks for your suggestion. We have followed your suggestions and included the figure and algorithm of CMGNN in the PDF of the global response, which will be added in the revised version to better illustrate the architecture of CMGNN.

Weakness #4: Theoretical analysis for the observations in the paper.

Answer #6: Thanks for your suggestion! We have provided theoretical analyses and support for a core condition underlying Observation 1 and 2: the discriminability of obtained representations is positively correlated with the discriminability among classes in CM. For detailed analyses, please refer to the global response due to the space limits.

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.

Question #1 & Weakness #1: The connections and differences between the observations in this paper and prior works.

Answer #1: Thanks for pointing out the omission. Our principal finding is Obs.2 with Obs.1 serving as a foundational context to enhance the understanding of Obs.2. The detailed comparisons are as follows:

• Prior works [6, 9] have primarily analyzed the challenging issue of heterophily in vanilla GNNs. While their conclusions are similar to our Obs.1, as they emphasize data, our focus is more on the message passing. However, they did not explore the reasons behind the effectiveness of heterophilous message passing (HTMP). Further, prior works [12, 18] investigate the effectiveness of specific designs separately. In contrast, our Obs.2 encompasses a comprehensive set of various effective designs in HTMP and attributes their effectiveness to a unified goal. Consequently, our Obs.2 provides a more comprehensive and unified perspective for understanding the working mechanism of HTMP.
• Upon the above analysis, we also recognize that there are inaccuracies in our related works section that could lead to misunderstandings. A more accurate description would be: "These reviews do not explore the unified reasons for the effectiveness of various designs in heterophilous message passing." We will correct this in the revised version.

Question #2 & Weakness #2: More detailed description of the method and "topology structure".

Answer #2: Thank you for the suggestions! We completely agree that a figure can significantly aid readers in understanding the whole method. Following your suggestions, we have included a figure in the PDF of the global response. The detailed descriptions of "topology structure" are as follows:

• The explanation of "topology structure": The term "topology structure" refers to the connection relationship among nodes, represented by the adjacency matrix $\mathbf{A}$. Each row $\mathbf{A}_i$ can be viewed as an additional $N$-dimensional feature for the corresponding node $i$. The inclusion of additional features is optional, depending on the observed performance on the validation set, as it may introduce extra computational cost and potentially redundant information.
• The explanation of terms in Eq.7: In Eq.7, $\mathbf{Z}^0$ is the input for the first layer of message passing and can be obtained in two ways: (1) by using the topology structure as additional features, with $\mathbf{W}^{X}\in \mathbb{R}^{d_f \times d_r}$, $\mathbf{W}^{A} \in \mathbb{R}^{N \times d_r}$ and $\mathbf{W}^{0} \in \mathbb{R}^{2d_r \times d_r}$ as learnable weight matrices; (2) by using only attribute features, where $\mathbf{W}^{0} \in \mathbb{R}^{d_f \times d_r}$ is a learnable weight matrix.
• The effect of additional structural features: The additional structural features offer another way to utilize connection relationships, introducing both discriminant and redundant information. Thus it presents a trade-off between the advantages and disadvantages. We conducted an ablation study to examine its effects and report the results in the table below. The additional structure features have positive effects on five datasets while others are negative. It doesn’t significantly impact performance except for Roman-Empire. Moreover, CMGNN can still achieve competitive results without using additional structural features.

Question #3 & Weakness #3: Computational complexity analysis and empirical runtime comparison.

Answer #3: Thanks for your suggestion! The analysis of computational complexity and empirical runtime comparison are described as follows:

• Computational complexity analysis: The computational complexity of layer $l$ consists of 3 parts: (i) AGGREGATE function: $O(N{d_r}^2)$, $O(N{d_r}^2+Md_r)$ and $O(N{d_r}^2+NKd_r)$ for identity, raw and the supplementary neighborhood, respectively, where $N$ and $M=|\mathcal{E}|$ denote the number of nodes and edges, $d_r$ is the dimension of representations; (ii) COMBINE function: $O(3N(3d_r+1)+12N)$ for calculating adaptive weights and $O(3N)$ for combination; (iii) FUSE function: $O(1)$ for concatenations. Thus, the time complexity of $L$-layer CMGNN is $O(L(Nd_r (3d_r+K+9)+Md_r+18N)+1)$, or $O(LN{d_r}^2+LM d_r)$ for brevity.
• Empirical runtime comparison: Following your suggestions, we have visualized the tradeoff between accuracy and empirical runtime compared to baseline methods in the PDF of the global response. The results show that CMGNN achieves the best performances with relatively low time consumption. Compared with OrderedGNN and GCNII, which have the second- and third-best average ranks, CMGNN offers both better accuracy and lower time consumption.

Weakness # 4: Correction of the "Norm" term.

Answer #4: Thank you for pointing out this mistake. We will correct it in the revised version.