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

Weakness #1 & Question #2: The extension of Theorem 3.2.

Answer #1: Thank you for this comment! It is indeed important to evaluate the effectiveness of Theorem 3.2 in real-world settings, including multi-class, imbalanced labels, imbalanced degrees, and so on, which are beyond the CSBM-H model. Thus, we conduct experiments to investigate the CMD-ENKL relationship on real datasets, and the results show that the negative correlation between CMD and ENKL still holds in various real-world settings.

The details are as follows:

• CMD: The CMDs of fixed CM and Weighted-CM on real datasets are easy to calculate according to the definition.
• ENKL: The ENKL is designed to measure the relationship between two distributions, which corresponds to the two-class setting. To approximately estimate the ENKL on real datasets with multiple classes, we first group the node embeddings according to node labels, regarding them as observed samples of different class distributions. Further, we calculate the pair-wise ENKL among classes and report the weighted mean values as results.
• Settings: For CMD, we report the fixed CM of the original data and the Weighted-CM of different operators. For ENKL, we report results of node embeddings after message passing (without feature transformation). We conduct the comparison of 4 operators (LP, HP, HTMP_0, HTMP_1) on 8 real-world datasets:

The results are as follows:

In line with expectations, the CMD and ENKL show an obvious negative correlation on all test datasets. This illustrates that Theorem 3.2 still holds empirically in various real-world settings.

Weakness #2 and Question #2: The discussion of the connection and differences with existing analyses.

Answer #2: Thank you for this suggestion! The discussion of the Connections and differences with existing analyses is as follows:

Connections:

• CSBM is a widely used generative model to study the behavior of GNNs, with some variations [1-4]. To better study the graph hererophily, Luan et al. [3] introduced the homophily ratio into CSBM and proposed the CSBM-H and ENKL. Our main theoretical analyses are based on the CSBM-H and ENKL.
• CM is proposed to describe the latent connection preference among classes within a graph [5,6]. It provides more information than the homophily ratio, thus is often utilized for heterophily study. Zhu et al. [7] highlighted that node degrees and CMs are key factors for message passing under heterophily. Similarly, Ma et al. [1] proposed the existence of a special case of heterophily where the homophily ratios remain low, but the VMP mechanism can achieve strong performance. One of our conclusions in lines 127-129 is consistent with their findings.

Differences:

• We newly introduce the HTMP operator in the CSBM-H to investigate the behavior of heterophilic GNNs, which is beyond existing analyses.
• We newly propose the CMD to measure the discriminability of CM, providing a quantitative metric to measure the quality of CM.
• Further, we theoretically prove the negative correlation between CMD and ENKL of VMP, providing formal proof for the findings of existing works.
• The ways of existing works to utilize CM are limited in studying what kind of data is suitable for the message-passing mechanism, which is the data perspective. We take a further step with the model perspective that the CM can be enhanced by the HTMP mechanism, and then propose the Weighted-CM for better description.
• Through empirical evaluation, we find that increasing CMD is a possible reason for the effectiveness of HTMP.

In summary, our work is based on the existing CSBM-H, ENKL, and CM, and we further proposed the CMD, Weighted-CM, along with other new theoretical and empirical findings. We will update the above discussion in the revised version.

Reference:

[1] Is homophily a necessity for graph neural networks? ICLR 2022.

[2] Understanding nonlinearity in graph neural networks from the bayesian-inference perspective. NeurIPS 2022.

[3] When do graph neural networks help with node classification? investigating the homophily principle on node distinguishability. NeurIPS 2023.

[4] Understanding Heterophily for Graph Neural Networks. ICML 2024.

[5] Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS 2020.

[6] Graph neural networks with heterophily. AAAI 2021.

[7] Heterophily and graph neural networks: Past, present and future. IEEE Data Eng. Bull. 2023.

Question #1: The training/optimization dynamics of the compatibility matrix.

Answer #3: We show the training dynamics of the compatibility matrix and GNN predictions approximately as follows:

• For CM, we use the corresponding CMD to better show its trend of change since the matrix is hard to visualize.
• For GNN prediction, we report the accuracy of the pseudo labels (pse_acc).
• Since the CM and GNN predictions can be updated many times during training, we choose some of them to show the dynamics.

The results are as follows:

As the training process progresses, the accuracy of GNN prediction gradually increases, while the CMD first declines and then rises. This is because the CMs are initialized mainly based on the training set labels at the beginning, since other predicted labels have extremely low confidence, which corresponds to low contributions. The inaccurate predictions may impact the CM estimation for a while at the early stage, leading to the reduction of CMD. Then, CMD will gradually increase along with the accuracy of GNN prediction, and enhance each other.

Question #3: The detailed investigation focuses on low-degree and low label rate setting.

Answer #4: Thank you for the suggestion! The case studies on low-degree nodes and low label rate settings are indeed important to prove the effectiveness of CMGNN.

• Thus, we have provided an investigation on the performance of nodes with various levels of degrees in Appendix G.3. The results show that CMGNN can achieve outstanding performances on low-degree nodes.
• In addition, we conduct an experiment to investigate the performance of CMGNN under the low label rate setting. The results show that CMGNN can still outperform strong baselines, demonstrating the effectiveness of CMGNN on handling the noise issue.

The details of the experiment are as follows:

• Dataset: We conduct experiments on Roman-Empire, Amazon-Ratings, Chameleon-F, and Pubmed. The label rate for training is set as 5% to meet the low label rate setting.
• Baseline: We compare CMGNN with 2 base and 3 top-performance baseline methods, including MLP, GCN, GCNII, ACMGCN, and OrderedGNN.

The classification accuracies of methods are as follows:

Consistent with the results reported in the paper, CMGNN can also achieve outstanding performance on the low label rate setting.

We are expecting these could help answer your questions and look forward to further discussion. If you have any further questions, please feel free to contact us.

I thank the authors for providing an extensive followup on each of my raised points. In summary, the authors addressed (1) the practicality and feasibility of Theorem 3.2 as it pertains to real-world settings, (2) the relation between the analysis and existing analyses, (3) analyses and discussion of the joint training and optimization of the compatibility matrix and GNN, and (4) verification of the benefits of the approach in low label rate and low-degree settings. As such, I am happy to maintain my positive score.

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

Question #1: What is the definition of HTMP method? Is it just the truncated Krylov method?

Answer #1: Thank you for the reminder. We use "HTMP" methods to refer to the heterophilic GNNs that follow the message-passing mechanism. As mentioned in Section 2, HTMP methods often extend the neighborhood variously and redesign the COMBINE function to collect neighbor messages preferentially while preserving the ego messages.

Thus, the truncated Krylov method can be seen as a special case of HTMP methods since it has a similar way to conduct message passing. Further, the HTMP methods are not limited to the truncated Krylov method. The definition of extended neighborhood is more than the multi-hop neighborhood. It can also be extended to some flexible neighbor types, such as feature-similarity-based neighborhoods [1] and global neighborhoods [2].

For theoretical analysis, we start from the vanilla message passing and then extend it to heterophilic message passing. Since it can have various forms, we choose a typical scheme as the example, and it indeed can be seen as a special case of the truncated Krylov method. In addition, we study the representative HTMP methods, i.e., GloGNN, GPR-GNN, and ACM-GCN empirically.

Reference:

[1] Node similarity preserving graph convolutional networks. WSDM 2021.

[2] Finding global homophily in graph neural networks when meeting heterophily. ICML 2022.

Question #2: A more accurate description of the high-pass operator.

Answer #2: Thank you for the correction! Our intention is also to claim that the high-pass operator can capture the difference between the central node and its neighborhoods, but with a brief description, which may not be clear enough. We will improve it and update the citation in the revised version.

Question #3: Why do you use $\dot{\mathbf{A}}$ in equation (6)? Why not $\hat{\mathbf{A}}$?

Answer #3: $\dot{\mathbf{A}}$ is an indicator matrix of the practical aggregate weights matrix during message passing. It can be various in different message passing methods. For example, $\dot{\mathbf{A}}=\hat{\mathbf{A}}$ in low-pass filtering and $\dot{\mathbf{A}}=\mathbf{I}-\hat{\mathbf{A}}$ for high-pass filtering. In many heterophilic message passing methods, neighbors may have different contributions to the embedding of the central node. Thus, the aggregated messages meet a practical Weighted-CM different from the fixed CM. To better describe the practical CM of different message passing methods, we introduce the $\dot{\mathbf{A}}$ and the Weighted-CM.

Question #4: Why do we need CMD when we already have ENKL to measure node distinguishability?

Answer #4: First, ENKL measures the relationship between two distributions, which is designed for the two-class setting. Second, it is difficult to estimate the node embedding distribution of real-world datasets. In comparison, CMD focuses on the coupling of node labels and graph structure. It fits the multi-class settings and is easy to calculate.

Question #5: How sparsity will be harmful to MP theoretically (probably with a toy example) or empirically with real-world datasets?

Answer #5: Sparsity may cause an outlier neighborhood for nodes, leading to embedding overlap among classes after message passing. We give a toy example to illustrate this process.

Considering a graph with nodes belonging to 3 classes. The latent connection preference among classes follows the compatibility matrix:

For simplicity, the features of nodes in the same class are set to the same:

We use a vanilla message passing $\mathbf{H}=\hat{\mathbf{A}}\mathbf{X}$ as an example. Suppose we have two nodes $u$ and $v$, belonging to class 0 and class 1, respectively.

If node degrees are large enough, e.g., 10. Then node $u$ may have 3 neighbors from class 0, 1 from class 1 and 6 from class 2. Similarly, node $v$ may have 1 neighbor from class 0, 7 from class 1 and 2 from class 2. Thus, the node embeddings are as follows after message passing:

which can be easily distinguished.

Further, we consider the sparsity issue. Now, nodes $u$ and $v$ can only have 2 neighbors each due to sparsity. Therefore, there might be a situation where nodes $u$ and $v$ have similar neighborhoods. For example, node $u$ has 1 neighbor from class 0 and 1 from class 2, while node $v$ also has 1 neighbor from class 0 and 1 from class 2. Thus, the node embeddings after message passing are:

Thus, two nodes from different classes may share similar embeddings after message passing in sparsity settings and it's difficult to distinguish them.

In addition, we have conducted experiments on synthetic datasets to investigate the influence of node degrees in Appendix C. The results also show that low degrees have a negative impact on the performance of GCN, which is consistent with the above analysis.

Question #6: The writing for "Sufficient Neighborhood Supplement" is confusing. Need to re-organize the contents, clarify the notations and their dimensions.

Answer #6: Thanks for your suggestion! This is indeed that the "Sufficient Neighborhood Supplement" may not be clear enough. In this component, we additionally introduce $K$ virtual neighbors for each node to alleviate the sparsity issue. Thus, "Virtual Neighborhood Supplement" might be relatively clearer. We will further improve this part in the revised version.

Question #7: More ablation studies on different proposed model components are needed.

Answer #7: We further conduct ablation studies on several components on all datasets, including Confidence-based CM Estimation (CE), degree weighting function (DW) and adaptive weighting message combine (AW), where the latter two are introduced in Appendix E.

• "W/O CE" means that we remove the confidence during the CM estimation.
• "W/O DW" means that we remove the degree weighting function during the CM estimation.
• "W/O AW" means that we replace the adaptive weighting with the mean operator in the message combination.

The complete results are as follows:

The results demonstrate the effectiveness of these components.

• For SM and DL, the results are consistent with the results reported in the paper, except that DL shows no significant improvement on some datasets. This may be due to the discriminability of SM reaching the bottlenecks, and can not be further improved by DL.
• For CE, we observe that "W/O CE" shows performance drops on all datasets, which indicates that CE is effective in alleviating the issue of noise.
• For DW and AW, we can find that they both have positive contributions to the performance. DW has a relatively low impact, while AW makes significant performance differences on some datasets. This may be due to the high demand for ego messages on heterophilic graphs.

We are expecting these could help answer your questions and look forward to further discussion. If you have any further questions, please feel free to contact us.

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

Weakness #1: The analysis of experimental results considering different homophily levels.

Answer #1: Thank you for pointing that out! We divide the graphs into two groups according to their edge homophily levels with a threshold of 0.5. The rank of CMGNN on various datasets and groups is as follows:

Further, the average ranks of baseline methods on heterophilic and homophilic groups are as follows:

• From the results, we can find that CMGNN shows significant effectiveness on heterophilic graphs with an average rank of 1.3 and achieves the best on 9 of 10.
• Also, CMGNN can keep competitive performance on homophilic graphs with an average rank of 2.3, which is also the best compared with baseline methods.
• Interestingly, some heterophilic GNNs work relatively better on homophilic graphs rather than heterophilic graphs, such as GloGNN and OrderedGNN. This might be because these methods are relatively more inclined to adapt to both situations.

Weakness #2: The lack of direct validation of the CMD-ENKL relationship on real datasets.

Answer #2: Thank you for this suggestion! A validation of the CMD-ENKL relationship on real datasets is indeed necessary. We have investigated it, and the results show that the negative correlation between CMD and ENKL still holds in real-world datasets.

The details are as follows:

• CMD: The CMDs of fixed CM and Weighted-CM on real datasets are easy to calculate according to the definition.
• ENKL: The ENKL is designed for two-class setting. To approximately estimate the ENKL with multiple classes, we first group the node embeddings according to node labels and then calculate the pair-wise ENKL among classes and report the weighted mean values.
• Settings: For CMD, we report the fixed CM and the Weighted-CM of different operators. For ENKL, we report results of node embeddings after message passing (without feature transformation). We conduct the comparison of 4 operators (LP, HP, HTMP_0, HTMP_1):

The results are as follows:

In line with expectations, the CMD and ENKL show an obvious negative correlation on all test datasets. This illustrates that Theorem 3.2 still holds empirically on real-world datasets.

Weakness #3 & Question #2: A more comprehensive evaluation of ablation studies across all datasets including the implementation details.

Answer #3: Thank you for the suggestion! We investigate the influence of Confidence-based CM Estimation (CE), degree weighting function (DW), and adaptive weighting message combination (AW).

• "W/O CE" means removing the confidence during the CM estimation.
• "W/O DW" means removing the degree weighting function during the CM estimation.
• "W/O AW" means replacing the adaptive weighting with the mean operator in the message combination.
• The ablation study of additional structural features is provided in Appendix G.2.

The complete results are as follows:

The results demonstrate the effectiveness of these components.

• For SM and DL, the results are consistent with the results reported in the paper, except that DL shows no significant improvement on some datasets. This may be due to the discriminability of SM reaching the bottlenecks, and can not be further improved by DL.
• For CE, we observe that "W/O CE" shows performance drops on all datasets, which indicates that CE is effective in alleviating the issue of noise.
• DW and AW both have positive contributions to the performance. DW has a relatively low impact, while AW makes significant performance differences on some datasets. This may be due to the high demand for ego messages on heterophilic graphs.

Question #1: Why GraphSAGE is not included in the comparison?

Answer #4: Thank you for the supplement! We simply chose some of the representative homophilic GNNs as baseline methods rather than all of them since this paper focuses more on the heterophilic setting. We have added GraphSAGE for comparison and its performance is as follows:

Indeedly, GraphSAGE performs well in both homophilic and heterophilic graphs. It significantly outperforms GCN and GAT and even many heterophilic GNNs. It further enhances our evaluation, and we will update the corresponding part in the revised version.

Question #3: The relationship between CMD and model performance on real-world datasets. How CMGNN addresses such cases and whether CMD remains a reliable indicator.

Answer #5: CMD measures the discriminability considering the graph structure and labels, without node features. The quality of node embeddings after message passing relies on both CMD and node features. CMD can play a reliable indicator in real-world datasets when the node features are fixed as shown in Answer #2. However, the feature transformations are different in the methods. Thus, the high CMD and relatively poor performance of Rom-Glo may be due to its feature transformation being unsatisfactory. Even extremely high CMD can not ensure the good performance of Rom-Glo.

To address real-world issues, CMGNN constructs supplementary neighbors for each node and utilizes the discrimination loss to directly enhance the discriminability of node embeddings.

Question #4: How much does the Weighted-CM contribute to the overall performance gains?

Answer #6: To show the detailed contribution of Weighted-CM, we conduct an ablation study. For "W/O WCM", we use the fixed CM of the original data to replace the Weighted-CM during CM-aware message passing. The results are as follows:

The results show that the Weighted-CMs can achieve better performance compared with the "W/O WCM" setting, which uses the exact CM of the original data rather than estimating. The performance difference is relatively insignificant on some datasets. This might be because the other components of CMGNN, such as SM and CE, have already made significant contributions to learn better node embeddings.

We are expecting these could help answer your questions and look forward to further discussion. If you have any further questions, please feel free to contact us.

We sincerely appreciate your valuable comments and suggestions. Although you mentioned that you have already compared the new version, we would like to kindly remind you that the weaknesses you pointed out have been significantly and explicitly addressed in the current revision. Specifically,

• For Weakness #1, the HTMP framework has been totally removed in this version, since it has relatively little connection with the theme of this paper.
• For Weakness #2, in this version, we have newly proposed the Compatibility Matrix Discriminability (CMD) to measure the discriminability of CM. Further, we theoretically and empirically prove the positive correlation between node discriminability and CMD. In addition, a toy example and a posterior evaluation in representative HTGNNs show that the effectiveness of existing heterophilic message-passing mechanisms may be attributed to increasing CMD, which leads to better node embeddings.
• For Weakness #3, the motivation behind method design is to address the issues of sparsity and noise in real-world graphs, with a detailed description in lines 168-177 and Section 4.

Based on the above improvement, we believe the weakness of the previous submission does not match this version, especially the parts that have been totally removed. We appreciate your time for reviewing our paper and providing feedback, but we also hope the improvement can be considered fairly and justly.

If you have any further questions, please feel free to contact us.

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

Question #1: How sensitive is CMGNN to the choice or accuracy of pseudo labels used in compatibility matrix estimation?

Answer #1: To investigate how sensitive CM estimation is to the accuracy of pseudo labels, we conduct an experiment to compare the quality of estimated CMs with different accuracy of pseudo labels. The results show that the CM estimation is quite robust to the accuracy of pseudo labels. This may be thanks to the confidence-based CM estimation.

The details of the experiment are as follows:

• For CM, we use the corresponding CMD to better measure its quality since the matrix is hard to visualize.
• We use an additional low label setting (5% nodes for training) to construct different quality of pseudo labels.
• We report the CMD and accuracy of pseudo labels (pse_acc) after training on the normal setting and low label rate setting, along with the CMD of the fixed CM in the original data.

The results are as follows:

From the above results, we can see that CMGNN can estimate CMs with relatively stable CMD values, even when the pseudo labels are of low quality in the low label rate setting. This demonstrates the robustness of CMGNN to the quality of pseudo labels.

Question #2 & Weakness #2: In evolving graphs, would re-estimating CMD and retraining CMGNN be feasible since it introduces extra computation?

Answer #2: Thank you for this question! CMGNN is largely adapted to the evolving graphs while introducing little computing consumption compared with normal graphs. The detailed analyses are as follows:

• For a newly arrived node, it will influence the following part of CMGNN: the node itself, the corresponding class prototype, and the estimated compatibility matrix.
• For the increase of the node itself, there is unavoidable time consumption for all methods.
• For new nodes with available labels, the corresponding class prototype in CMGNN should be updated too. And the update is quite simple if we record the number of nodes for each class, as the class prototype is set as the average of all nodes in the same class.
• For the estimated CM, the new node can be easily integrated into the update, since the CM needs to be gradually updated during the training process. Of course, this will bring a little extra computational cost, as the number of updates may increase.

In summary, CMGNN can be easily adapted to the evolving graphs since the arrival of new nodes and labels meets the update strategy of CMGNN and brings little extra computation.

Question #3 and Weakness #1: Does CMD offer a reliable signal under label imbalance, since the theoretical results rely heavily on the CSBM-H model?

Answer #3: We investigate the effectiveness of CMD under a label imbalance setting theoretically and empirically as follows:

• Theoretical analysis: The CMD is designed to measure the discriminability of CM. Since each row of CM is calculated for the corresponding class separately, the label imbalance will not impact the CM. Further, during the calculation of CMD, the contribution of all classes is the same, regardless of the node number of each class. Thus, CMD can hold the effectiveness in the real-world label imbalance setting theoretically.
• Empirical analysis: We conduct experiments on 4 real-world datasets with label imbalance to evaluate the effectiveness of CMD. The experimental results show that CMD can still offer a reliable signal under label imbalance. Meanwhile, CMGNN achieves outstanding performance on these datasets, as shown in Table 1, also providing empirical proofs.

The details of the experiment are as follows:

To evaluate the effectiveness of CMD, we try to calculate the ENKL (node discriminability) and CMD on a real-world label imbalance setting, and investigate the relationship between them. The following are the experimental settings:

• CMD: The CMDs of fixed CM and Weighted-CM on real datasets are easy to calculate according to the definition.
• ENKL: The ENKL is designed to measure the relationship between two distributions, which corresponds to the two-class setting. To approximately estimate the ENKL on real datasets with multiple classes, we first group the node embeddings according to node labels, regarding them as observed samples of different class distributions. Further, we calculate the pair-wise ENKL among classes and report the weighted mean values as results.
• Settings: For CMD, we report the fixed CM of the original data and the Weighted-CM of different operators. For ENKL, we report results of node embeddings after message passing (without feature transformation). We conduct the comparison of 4 operators (LP, HP, HTMP_0, HTMP_1) on 4 real-world datasets:

To show the details of label imbalance in real-world datasets, we report the rate of node numbers of the largest and smallest classes and the proportion of classes:

The results are as follows:

In line with expectations, the CMD and ENKL show an obvious negative correlation on all test datasets. This illustrates that Theorem 3.2 still holds empirically on real-world datasets with label imbalance, indicating the effectiveness of CMD.

We are expecting these could help answer your questions and look forward to further discussion. If you have any further questions, please feel free to contact us.