Revisiting the Message Passing in Heterophilous Graph Neural Networks

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 14:48:49

Abstract: Graph Neural Networks (GNNs) have demonstrated strong performance in graph mining tasks due to their message-passing mechanism, which is aligned with the homophily assumption that adjacent nodes exhibit similar behaviors. However, in many real-world graphs, connected nodes may display contrasting behaviors, termed as heterophilous patterns, which has attracted increased interest in heterophilous GNNs (HTGNNs).
Although the message-passing mechanism seems unsuitable for heterophilous graphs due to the propagation of class-irrelevant information, it is still widely used in many existing HTGNNs and consistently achieves notable success. 
This raises the question: why does message passing remain effective on heterophilous graphs?
To answer this question, in this paper, we revisit the message-passing mechanisms in heterophilous graph neural networks and reformulate them into a unified heterophilious message-passing (HTMP) mechanism.
Based on HTMP and empirical analysis, we reveal that the success of message passing in existing HTGNNs is attributed to implicitly enhancing the compatibility matrix among classes.
Moreover, we argue that the full potential of the compatibility matrix is not completely achieved due to the existence of incomplete and noisy semantic neighborhoods in real-world heterophilous graphs.
To bridge this gap, we introduce a new approach named CMGNN, which operates within the HTMP mechanism to explicitly leverage and improve the compatibility matrix.
A thorough evaluation involving 10 benchmark datasets and comparative analysis against 13 well-established baselines highlights the superior performance of the HTMP mechanism and CMGNN method.

Main paper: 
 introduction: 
 Graph Neural Networks (GNNs) have shown remarkable performance in graph mining tasks, such as social network analysis [1, 2] and recommender systems [3, 4] . The design principle of GNNs is typically based on the homophily assumption [5] , which assumes that nodes are inclined to exhibit behaviors similar to their neighboring nodes [6] . However, this assumption does not always hold in real-world graphs, where the connected nodes demonstrate a contrasting tendency known as the heterophily [7] . In response to the challenges of heterophily in graphs, heterophilous GNNs (HTGNNs)have attracted considerable research interest [6, [8] [9] [10] , with numerous innovative approaches being introduced recently [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] . However, the majority of these methods continue to employ a messagepassing mechanism, which was not originally designed for heterophilous graphs, as they tend to incorporate excessive information from disparate classes. This naturally raises a question: Why does message passing remain effective on heterophilous graphs?Recently, a few efforts [6] have begun to investigate this question and reveal that vanilla message passing can work on heterophilous graphs under certain conditions. However, the absence of a unified Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute. and comprehensive understanding of message passing within existing HTGNNs has hindered the creation of innovative approaches. In this paper, we first revisit the message-passing mechanisms in existing HTGNNs and reformulate them into a unified heterophilous message-passing (HTMP) mechanism, which extends the definition of neighborhood in various ways and simultaneously utilizes the messages of multiple neighborhoods. Specifically, HTMP consists of three major steps namely aggregating messages with explicit guidance, combining messages from multiple neighborhoods, and fusing intermediate representations.Equipped with HTMP, we further conduct empirical analysis on real-world graphs. The results reveal that the success of message passing in existing HTGNNs is attributed to implicitly enhancing the compatibility matrix, which exhibits the probabilities of observing edges among nodes from different classes. In particular, by increasing the distinctiveness between the rows of the compatibility matrix via different strategies, the node representations of different classes become more discriminative in heterophilous graphs.Drawing from previous observations, we contend that nodes within real-world graphs might exhibit a semantic neighborhood that only reveals a fraction of the compatibility matrix, accompanied by noise. This could limit the effectiveness of enhancing the compatibility matrix and result in suboptimal representations. To fill this gap, we further propose a novel Compatibility Matrix-aware Graph Neural Network (CMGNN) under HTMP mechanism, which utilizes the compatibility matrix to construct desired neighborhood messages as supplementary for nodes and explicitly enhances the compatibility matrix by a targeted constraint. We build a benchmark to fairly evaluate CMGNN and existing methods, which encompasses 13 diverse baseline methods and 10 datasets that exhibit varying levels of heterophily. Extensive experimental results demonstrate the superiority of CMGNN and HTMP mechanism. The contributions of this paper are summarized as:• We revisit the message-passing mechanisms in existing HTGNNs and reformulate them into a unified heterophilous message-passing mechanism (HTMP), which not only provides a macroscopic view of message passing in HTGNNs but also enables people to develop new methods flexibly.• We reveal that the effectiveness of message passing on heterophilous graphs is attributed to implicitly enhancing the compatibility matrix among classes, which gives us a new perspective to understand the message passing in HTGNNs.• Based on HTMP mechanism and empirical analysis, we propose CMGNN to unlock the potential of the compatibility matrix in HTGNNs. We further build a unified benchmark that overcomes the issues of current datasets for fair evaluation 1 . Experiments show the superiority of CMGNN. 
preliminaries: 
 Given a graph G = (V, E, X, A, Y), V is the node set and E is the edge set. Nodes are characterized by the feature matrix X ∈ R N ×d f , where N = |V| denotes the number of nodes, d f is the features dimension. Y ∈ R N ×1 is the node labels with the one-hot version C ∈ R N ×K , where K is the number of node classes. The neighborhood of node v i is denoted as N i . A ∈ R N ×N is the adjacency matrix , and D = diag(d 1 , ..., d n ) represents the diagonal degree matrix, where d i = j A ij . Ã = A + I represents the adjacency matrix with self-loops. Let Z ∈ R N ×dr be the node representations with dimension d r learned by the models. We use 1 to represent a matrix with all elements equal to 1, and 0 for a matrix with all elements equal to 0.Homophily and Heterophily. High homophily is observed in graphs where a substantial portion of connected nodes shares identical labels, while high heterophily corresponds to the opposite situation.For measuring the homophily level, two widely used metrics are edge homophily h e [12] and node homophily h n [15] , defined as Vanilla Message Passing (VMP). The vanilla message-passing mechanism plays a pivotal role in transforming and updating node representations based on the neighborhood [25] . Typically, the WeightedAdd Z = Z L GAT [28] [ Ã] AdaWeight [B aw ] / Z = Z L GPR-GCN [20] [ Ã] DegAvg [ Bd ] / AdaAdd OrderedGNN [21] [I, A] [I, B d ] AdaCat Z = Z L ACM-GCN [18] [I, A, Ã] [I, B d , I -B d ] AdaAdd Z = Z L FAGCN [11] [I, A] AdaWeight [I, B naw ] WeightedAdd Z = Z L W GBK-GNN [24] [I, A, A] [I, B aw , 1 -B aw ] Add Z = Z LSimP-GCN [14] ReDef[I, Ã, A f ] DegAvg [I, Bd , B d f ] AdaAdd Z = Z L H2GCN [12] [A, A h2 ] [B d , B d h2 ] Cat CatGeom-GCN [15] [A c1 , ..., A cr , .. * The correspondence between the full form and the abbreviation: Raw Neighborhood (Raw), Neighborhood Redefine (ReDef), Neighborhood Discrimination (Dis), Degree-based Averaging (DegAvg), Adaptive Weights (AdaWeight), Relation Estimation (RelaEst), Addition (Add), Weighted Addition (WeightAdd), Adaptive Weighted Addition (AdaAdd), Concatenation (Cat), Adaptive Dimension Concatenation (AdaCat). * More details about the notations are available in Appendix A. 1. mechanism operates iteratively and comprises two stages:EQUATIONwhere the AGGREGATE function first aggregates the input messages Z l-1 from neighborhood A into the aggregated one Z l , and subsequently, the COMBINE function combines the messages of node ego and neighborhood aggregation, resulting in updated representations Z l .3 Revisiting Message Passing in Heterophilous GNNs.To gain a thorough and unified insight into the effectiveness of message passing in HTGNNs, we revisit message passing in various notable HTGNNs [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] and propose a unified heterophilous message passing (HTMP) mechanism, structured as follows:Z l r = AGGREGATE(A r , B r , Z l-1 ), Z l = COMBINE({ Z l r } R r=1 ), Z = FUSE({Z l } L l=0 ).(2) Generally, HTMP extends the definition of neighborhood in various ways and simultaneously utilize the messages of multiple neighborhoods, which is the key for better adapting to heterophily. We use R to denote the number of neighborhoods used by the model. In each message passing layer l, HTMP separately aggregates messages within R neighborhoods and combines them. The methodological analysis of some representative HTGNNs and more details can be seen in Appendix A.Compared to the VMP mechanism, HTMP mechanism has advances in the following functions: (A r , B r , Z l-1 ) = (A r ⊙ B r )Z l-1 W l r ,where ⊙ is the Hadamard product and W l r is a weight matrix for message transformation. We take (ii) Considering the existence of multiple neighborhoods, the COMBINE function in HTMP need to integrate multiple messages instead of only the ego node and the raw neighborhood. Thus, the input of the COMBINE function is a set of messages Z l r aggregated from the corresponding neighborhoods.In HTGNNs, addition and concatenation are two common approaches, each of which has variants.An effective COMBINE function is capable of simultaneously processing messages from various neighborhoods while preserving their distinct features, thereby reducing the effects of heterophily.(iii) In VMP, the final output representations are usually the one of the final layer: Z = Z L . SomeHTGNNs utilize the combination of intermediate representations to leverage messages from different localities, adapting to the heterophilous structural properties in different graphs. Thus, we introduce an additional FUSE function in HTMP which integrates multiple representations Z l of different layers l into the final Z. Similarly, the FUSE function is based on addition and concatenation.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: The limitations of this work are listed in the Sec 7.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
why does message passing still remain effective in heterophilous: 
 Graphs?Based on HTMP mechanism, we further dive into the motivation behind the message passing of existing HTGNNs. Our discussion begins by examining the difference between homophilous and heterophilous graphs. Initially, we consider the homophily ratios h e and h n , as outlined in Section 2.However, a single number is not able to indicate enough conditions of a graph. Ma et al. [6] propose the existence of a special case of heterophily, named "good" heterophily, where the VMP mechanism can achieve strong performance and the homophily ratio shows no difference. Thus, to better study the heterophily property, here we introduce the Compatibility Matrix [7] to describe graphs: EQUATIONwhere Norm(•) denotes the L1 normalization and T is the matrix transpose operation.C nb ∈ R N ×Kis the semantic neighborhoods of nodes, which indicates the proportion of neighbors from each class in nodes' neighborhoods.We visualize the CM of a homophilous graph Photo [29] and a heterophilous graph Amazon-Ratings [30] in Figure 1 (a) and 1(b). The CM in Photo displays an identity-like matrix, where the diagonal elements can be viewed as the homophily level of each class. With this type of CM, the VMP mechanism learns representations comprised mostly of messages from same the class, while messages of other classes are diluted. Then how does HTMP mechanism work on heterophilous graphs without an identity-like CM? The "good" heterophily inspires us, which we believe corresponds to a CM with enough discriminability among classes. We conduct experiments on synthetic graphs to confirm this idea, with details available in Appendix C. Also, we find "good" heterophily in real-world graphs though it's not as significant as imagined. Thus, we have the following observation:Observation 1 (Connection between CM and VMP). When enough (depends on data) discriminability exists among classes in CM, vanilla message passing can work well in heterophilous graphs.With this observation, we have a conjecture: Is HTMP mechanism trying to enhance the discriminability of CM? Some special designs in HTMP intuitively meet this. For example, feature-similarity-based neighborhood indicators and neighborhood discrimination are designed to construct neighborhoods with high homophily, that is, an identity-like CM with high discriminability. We plot the CM of feature-similarity-based neighborhood on Amazon-Ratings in Figure 1 (c) to confirm it. Moreover, we investgate two representative methods ACM-GCN [18] and GPRGNN [20] , showing that they also meet this conjecture with the posterior proof in Appendix D. ACM-GCN combines the messages of node ego, low-frequency and high-frequency with adaptive weights, which actually motifs the edge weights and node weights to build a new CM. GPRGNN has a FUSE function with adaptive weights while other settings are the same as GCN. It actually integrates the CMs of multiple-order neighborhoods with adaptive weights to form a more discriminative CM. These lead to the answer to the aforementioned question:Observation 2 (Connection between CM and HTMP). The unified goal of various message passing in existing HTGNNs is to utilize and enhance the discriminability of CM on heterophilous graphs.In other words, the success of message passing in existing HTGNNs benefits from utilizing and enhancing the discriminability of CM.Furthermore, we notice that the power of CM is not fully released due to the incomplete and noisy semantic neighborhoods in real-world heterophilous graphs. We use the perspective of distribution This brings a great challenge since the overlapping semantic neighborhood may become redundant information during message passing. 
method: 
 To fill this gap, we further propose a method named Compatibility Matrix-Aware GNN (CMGNN), which leverages the CM to construct desired neighborhood messages as supplementary, providing valuable neighborhood information for nodes to mitigate the impact of incomplete and noisy semantic neighborhoods. The desired neighborhood message denotes the averaging message within a neighborhood when a node's semantic neighborhoods meet the CM of the corresponding class, which converts the discriminability from CM into messages. CMGNN follows the HTMP mechanism and constructs a supplementary neighborhood indicator along with the corresponding aggregation guidance to introduce supplementary messages. Further, CMGNN introduces a simple constraint to explicitly enhance the discriminability of CM.Message Passing in CMGNN. CMGNN aggregates messages from three neighborhoods for each node, including the ego neighborhood, raw neighborhood, and supplementary neighborhood.Following the HTMP mechanism, the message passing of CMGNN cen be described as follows:EQUATIONwhere AdaWeight is the adaptive weighted addition implemented by an MLP with Softmax, ∥ denotes the concatenation. The neighborhood indicators and aggregation guidance of the three neighborhoods are formatted as follows:EQUATIONwhere A sup and B sup are described below.The supplementary neighborhood indicator A sup assigns K additional virtual neighbors for each node: A sup = 1 ∈ R N ×K . Specifically, these additional neighbors are K virtual nodes, constructed as the prototypes of classes based on the labels of the training set. The attributes X ptt ∈ R K×d f , neighborhoods A ptt ∈ R K×N and labels Y ptt ∈ R K×K of prototypes are defined as follows:EQUATIONwhere C train and X train are the one-hot labels and attributes of nodes in the training set. Utilizing class prototypes as supplementary neighborhoods can provide each node with representative messages of classes, which builds the basis for desired neighborhood messages.The supplementary aggregation guidance B sup = Ĉ M indicates the desired semantic neighborhood of nodes, i.e. the desired proportion of neighbors from each class in nodes' neighborhoods according to the probability that nodes belong to each class. M is the estimated compatibility matrix described in below. Using soft logits instead of one-hot pseudo labels preserves the real characteristics of nodes and reduces the impact of wrong predictions. During the message aggregation in the supplementary neighborhoods, the input representations Z l-1 are replaced by the representations of virtual prototype nodes Z l-1 ptt , which are obtained by the same message-passing mechanism as real nodes.Similar to existing methods [18, 19] , we also regard topology structure as a kind of additional available node features. Thus, the input representation of the first layer can be obtained in two ways:EQUATIONNote that in practice, we use ReLU as the activation function between layers. From the perspective of HTMP mechanism, our special design is to introduce an additional neighborhood indicator A sup by neighborhood redefining and aggregation guidance B sup , which can be seen as a form of relation estimation along with good interpretability. Meanwhile, these designs greatly reduce the time and space cost via the N × K form.Compatibility Matrix Estimation. The CM can be directly calculated via Eq 3 with full-available labels. However, the label information is not entirely available in semi-supervised settings. Thus, we try to estimate the CM with the help of semi-supervised and pseudo labels. Since the pseudo labels predicted by the model might be wrong, which can lead to low-quality estimation, we introduce the confidence g ∈ R N ×1 based on the information entropy to reduce the impact of wrong predictions, where a high entropy means low confidence:EQUATIONwhere Ĉ ∈ R N ×K is the soft pseudo labels composed of labels from the training set and model predictions. Then the nodes' semantic neighborhoodsC nb = Norm(A(g • Ĉ)) ∈ R N ×K are calculated considering the confidence.Further, the degrees of nodes also influence the estimation. As we mentioned in Section 4, the semantic neighborhood of low-degree nodes may display incomplete CM, leading to a significant gap between semantic neighborhoods and corresponding CM. Thus, they deserve low weights during the estimation. We manually set up two fixed thresholds and a weighting function range in [0, 1]:EQUATIONWhen a node's degree d i is smaller than the number of classes K, its semantic neighborhood is unlikely to display complete CM, corresponding to a low weight. And when the node degree is greater than 3K, we believe it can display near-complete CM, corresponding to the maximum weight.Finally, we can estimate the compatibility matrix M ∈ R K×K as follows: EQUATIONEQUATIONwhere Z ptt ∈ R K×dr is the representation of virtual prototypes nodes. More details about the implementation of CMGNN is available in Appendix E. 
benchmarks and experiments: 
 In this section, we conduct comprehensive experiments to demonstrate the effectiveness of the proposed CMGNN with a newly organized benchmark for fair comparisons.As reported in [30] , some widely adopted datasets in existing works have critical drawbacks, which lead to unreliable results. Therefore, with a comprehensive review of existing benchmark evaluation, we construct a new benchmark to fairly perform experimental validation. Specifically, we integrate 13 representative homophilous and heterophilous GNNs, construct a unified codebase, and evaluate their node classification performances on 10 unified organized datasets with various heterophily levels.Drawbacks of Existing Datasets. Existing works mostly follow the settings and datasets used in [15] , including 6 heterophilous datasets (Cornell, Texas, Wisconsin, Actor, Chameleon, and Squirrel) and 3 homophilous datasets (Cora, Citeseer, and Pubmed). Platonov et al. [30] for each dataset and report the mean performance and standard deviation of 10 splits. Baseline Methods. As baseline methods, we choose 13 representative homophilous and heterophilous GNNs, including (i) shallow base model: MLP; (ii) homophilous GNNs: GCN [1] ,GAT [28] , GCNII [27] ; (iii) heterophilous GNNs: H2GCN [12] , MixHop [16] , GBK-GNN [24] ,GGCN [23] , GloGNN [19] , HOGGCN [17] , GPR-GNN [20] , ACM-GCN [18] and OrderedGNN [21] .For each method, we integrate its official/reproduced code into a unified codebase and search for parameters in the space suggested by the original papers. More experimental settings can be found in Appendix F.4 and G.1.Following the constructed benchmark, we evaluate methods and report the performance in Table 2 .Performance of Baseline Methods. With the new benchmarks, some interesting observations and conclusions can be found when analyzing the performance of baseline methods. First, comparing the performance of MLP and GCN, we can find "good" heterophily in Amazon-Ratings, Chameleon-F, and Squirrel-F. Meanwhile, when the homophily level is not high enough, "bad" homophily may also exist as shown in BlogCatalog and Wikics. These results once again support the observations about CMs. Therefore, homophilous GNNs can also work well in heterophilous graphs as GCNII has an average rank of 4.1, which is better than most HTGNNs. This is attributed to the initial residual connection in GCNII actually playing the role of ego/neighbor separation, which is suitable in heterophilous graphs. As for heterophilous GNNs, they are usually designed for both homophilous and heterophilous graphs. Surprisingly, MixHop, as an early method, demonstrated quite good performance. In fact, from the perspective of HTMP, it can be considered a degenerate version of OrderedGNN with no learnable dimensions. As previous SOTA methods, OrderedGNN and ACM-GCN prove their strong capabilities again.Performance of CMGNN. CMGNN achieves the best performance in 6 datasets and an average rank of 2.1, which outperforms baseline methods. This demonstrates the superiority of utilizing and enhancing the CM to handle incomplete and noisy semantic neighborhoods, especially in heterophilous graphs. Regarding the suboptimal performance in Actor, we believe that this is due to the CM in this dataset are not discriminative enough to provide valuable information via the supplementary messages and hard to enhance. In homophilous graphs, due to the identity-like CMs, the overlap between distributions is relatively less, leading to a minor contribution from supplement messages. Yet CMGNN still achieves top-level performances.We conduct an ablation study on two key designs of CMGNN , including the supplementary messages of the desired neighborhood (SM) and the discrimination loss (DL). The results are shown in Table 3 .First of all, both SM and DL have indispensable contributions except for Flickr, BlogCatalog, and Pubmed, in which the discrimination loss has no effect. This may be due to the discriminability of desired neighborhood messages reaching the bottlenecks and can not be further improved by DL Meanwhile, the extent of their contributions varies across datasets. SM plays a more important role in most datasets except Roman-Empire, Wikics, and Photo, in which the number of nodes that need supplementary messages is relatively small and DL has great effects. Further, we notice that with SM and DL, CMGNN can reach a smaller standard deviation most of the time. This illustrates that CMGNN achieves more stable results by handling nodes with incomplete and noisy semantic neighborhoods. As for the opposite result on Chameleon-F, this may attributed to the small size of this dataset (890 nodes), which can lead to naturally unstable results. To verify the effect of CMGNN on nodes with incomplete and noisy semantic neighborhoods, we divide the test set nodes into 5 parts according to their degrees and report the classification accuracy respectively. We compare CMGNN with 3 top-performance methods and show the results in Table 4 .In general, nodes with low degrees tend to have incomplete and noisy semantic neighborhoods.Thus, our outstanding performances on the top 20% nodes with the least degree demonstrate the effectiveness of CMGNN for providing desired neighborhood messages. Further, we can find that OrderedGNN and GCNII are good at dealing with nodes with high degrees, while ACM-GCN is relatively good at nodes with low degrees. And CMGNN , to a certain extent, can be adapted to both situations at the same time. 
conclusion and limitations: 
 In this paper, we revisit the message passing mechanism in existing heterophilous GNNs and reformulate them into a unified heterophilous message passing (HTMP) mechanism. Based on the HTMP mechanism and empirical analysis, we reveal that the reason for message passing remaining effective is attributed to implicitly enhancing the compatibility matrix among classes. Further, we propose a novel method CMGNN to unlock the potential of the compatibility matrix by handling the incomplete and noisy semantic neighborhoods. The experimental results show the effectiveness of CMGNN and the feasibility of designing a new method following HTMP mechanism. We hope the HTMP mechanism and benchmark can further provide convenience to the community.This work mainly focuses on the message passing mechanism in existing HTGNNs under the semi-supervised setting. Thus, the other designs in HTGNNs such as objective functions are not analyzed in this paper. The proposed HTMP mechanism is suitable for only a large part of existing HTGNNs which still follow the message passing mechanism. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We list the hardware and software resources along with the space and space complexity in Appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper poses no such risk. The datasets we used are all publicly available online.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: The datasets and code of baseline methods are publicly available online. We cite the original paper and mark the URL in both papers and codebase.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. 
 
 Appendix: In this part, we list more details about the HTMP mechanism, including additional analysis about HTMP, method-wise analysis and overall analysis.A.1.1 Neighborhood IndicatorsThe neighborhood indicator explicitly marks the neighbors of all nodes within a specific neighborhood. In existing heterophilous GNNs, neighborhood indicators typically take one of the following forms: (i) Raw Neighborhood (Raw); (ii) Neighborhood Redefining (ReDef); and (3) Neighborhood Discrimination (Dis).Raw Neighborhood. Raw neighborhood, including A and Ã, provides the basic neighborhood information. The only difference between them lies in whether there is differential treatment of the node's ego messages. For example, APPNP [26] applies additional weighting to the nodes' ego messages compared with GCN [1] . For the sake of simplicity, we consider the identity matrix I ∈ R N ×N as a special neighborhood indicator for acquiring the nodes' ego messages. In heterophilous GNNs, ego/neighbor separation is a common strategy that can mitigate the confusion of ego messages with neighbor messages.Neighborhood Redefining. Neighborhood redefining is the most commonly used technique in heterophilous GNNs, aiming to capture additional information from new neighborhoods. As a representative example, high-order neighborhood A h can provide long-distance connection information but also result in additional computational costs. Feature-similarity-based neighborhood A f is often defined by the k-NN relationships within the feature space. Fundamentally, it only utilizes node features and thus needs to be used in conjunction with other neighborhood indicators. Otherwise, the model will be limited by the amount of information in node features. GloGNN [19] introduces fully-connected neighborhood 1 ∈ R N ×N , which can capture global neighbor information from all nodes. However, it can also cause significant time and space consumption. Additionally, there are some custom-defined neighborhood A c . For example, Geom-GCN [15] redefines neighborhoods based on the geometric relationships between node pairs. These neighborhood indicators may have limited generality, and the effectiveness is reliant on the specific method.Neighborhood Discrimination. Neighborhood discrimination aims to mark whether neighbors share the same label with central nodes. The neighborhoods are partitioned into positive A p and negative ones A n , which include homophilous and heterophilous neighbors respectively. GGCN [23] divides the raw neighborhood based on the similarity of node representations with a threshold of 0. Explicitly distinguishing neighbors allows for targeted processing, making the model more interpretable. However, its performance is influenced by the accuracy of the discrimination, which may lead to the accumulation of errors.After identifying the neighborhood, the aggregation guidance controls what type of messages to gather from the corresponding neighbors. The existing aggregation guidance mainly includes three kinds of approaches: (1) Degree Averaging (DegAvg), (2) Adaptive Weights (AdaWeight), andRelationship Estimation (RelaEst).Degree Averaging. Degree averaging, formatted as used in ACM-GCN [18] . Degree averaging is simple and efficient but depends on the discriminability of corresponding neighborhoods.B d = D -1 2 1D -1 2 or B d = D -1Adaptive Weights. Another common strategy is allowing the model to learn the appropriate aggregation guidances B aw . GAT [28] proposes an attention mechanism to learn aggregate weights, which guides many subsequent heterophilous methods. To better handle heterophilous graphs, FAGCN [11] introduces negative-available attention weights B naw to capture the difference between central nodes and heterophilous neighbors. Adaptive weights can personalize message aggregation for different neighbors, yet it's difficult for models to attain the desired effect.Relationship Estimation. Recently, some methods have tried to estimate the pair-wise relationships B re between nodes and use them to guide message aggregation. HOG-GCN [17] estimates the pair-wise homophily levels between nodes as aggregation guidances based on both attribute and topology space. GloGNN [19] treats all nodes as neighbors and estimates a coefficient matrix as aggregation guidance based on the idea of linear subspace expression. GGCN [23] estimates appropriate weights for message aggregation with the degrees of nodes and the similarities between node representations. Relationship estimation usually has theoretical guidance, which brings strong interpretability. However, it may also result in significant temporal and spatial complexity when estimating pair-wise relations.After message aggregation, the COMBINE functions integrate messages from multiple neighborhoods into layer representations. COMBINE functions in heterophilous GNNs are commonly based on two operations: addition and concatenation, each of which has variants. To merge several messages together, addition (Add) is a naive idea. Further, to control the weight of messages from different neighborhoods, weighted addition (WeightedAdd) is applied. However, it is a global setting and cannot adapt to the differences between nodes. Thus, adaptive weighted addition (AdaAdd) is proposed, which can learn personalized message combination weights for each node, but it will result in additional time consumption. Although the addition is simple and efficient, some methods [12, 16] believe that it may blur messages from different neighborhoods, which can be harmful in heterophilous GNNs, so they employ a concatenation operation (Cat) to separate the messages. Nevertheless, such an approach not only increases the space cost but may also retain additional redundant messages. To address these issues, OrderedGNN [21] proposes an adaptive concatenation mechanism (AdaCat) that can combine multiple messages with learnable dimensions. This is an innovative and worthy further exploration practice, but the difficulty of model learning should also be considered.Further, the FUSE functions integrate messages from multiple layers into the final representation. For the FUSE function, utilizing the representation of the last layer as the final representation is widely accepted: Z = Z L . JKNet [31] proposes that the combination of representations from intermediate layers can capture both local and global information. H2GCN [12] applies it in heterophilous graphs, preserving messages from different localities with concatenation. Similarly, GPRGNN [20] combines the representations of multiple layers into the final representation through adaptive weighted addition.The most commonly used AGGREGATE function isAGGREGATE(A r , B r , Z l-1 r ) = (A r ⊙ B r )Z l-1 r W l r .We take this as the fixed form of the AGGREGATE function following. Actually, the input representations Z -1 r and weight matrixes W l r also can be specially designed. Taking the initial node representations Z 0 as input is a relatively common approach as in APPNP [26] ,GCNII [27] , FAGCN [11] and GloGNN [19] . Further, GCNII [27] adds an identity matrix I w to the weight matrixes to keep more original messages. However, the methods that specially design these components are few and with a similar form. Thus, we don't discuss them too much, but leave it for future extensions.In this part, we utilize HTMP mechanism to revisit the representative GNNs. We start from homophilous GNNs as simple examples and further extend to heterophilous GNNs.Graph Convolutional Networks (GCN) [1] utilizes a low-pass filter to gather messages from neighbors as follows:EQUATION)It can be revisited by HTMP with the following components:EQUATIONSpecifically, GCN has a raw neighborhood indicator Ã and a degree averaging aggregation guidanceB d .Since there is only one neighborhood, the COMBINE function is meaningless in GCN. GCN utilizes a naive way to fuse messages about the original neighborhood and central nodes. However, it may confuse the representations in heterophilous graphs.PPNP [26] is also a general method whose message passing is based on Personalized PageRank (PPR). To avoid massive consumption, APPNP is introduced as the approximate version of PPNP with an iterative message-passing mechanism:EQUATION)It can be revisited by with the following components:EQUATIONSpecifically, APPNP aggregates messages from node ego and neighborhoods separately and combines them with a weighted addition. Compared with GCN, APPNP assigns adjustable weights to nodes, for controlling the proportion of ego and neighbor messages during message-passing, which becomes a worthy design in heterophilous graphs.Going a step further, Graph Attention Networks (GAT) [28] allows learnable weights for each neighbor:EQUATIONwhere α ij is the weight for aggregating neighbor node j to center node i, whose construction process is as follows:α ij = exp(e ij ) k∈ Ñ (i) exp(e ik ),EQUATIONLet P GAT be the matrix of aggregation weights in GAT:EQUATION)HTMP can revisit GAT with the following components:EQUATIONwhich is the matrix version of Eq 16. Specifically, GAT aggregate messages from raw neighborhood Ã with adaptive weights B aw . Aggregation guidance with adaptive weights is a nice idea, but simple constraints are not enough for the model to learn ideal results.GCNII [27] is a novel homophilous GNN with two key designs: initial residual connection and identity mapping, which can be formatted as follows:EQUATIONwhere α and β are two predefined parameters and I w ∈ R dr×dr is an identity matrix.From the perspective of HTMP, it can be viewed as follows:EQUATIONwhere the COMBINE function is weighted addition. Specifically, the first design of GCNII is a form of ego/neighbor separation, and the second design is a novel transformation weights matrix. This can also be specially designed, but only GCNII does this, so we won't analyze it too much and leave it as a future extension.Geom-GCN [15] is one of the most influential heterophilous GNNs, which employs the geometric relationships of nodes within two kinds of neighborhoods to aggregate the messages through bi-level aggregation:EQUATIONwhere ∥ denotes the concatenate operator, {g, s} is the set of neighborhoods including the original graph and the latent space. R is the set of geometric relationships. A i,r is the corresponding adjacency matrix in neighborhood i and relationship r.It can be revisited by HTMP with the following components:EQUATIONwhere the COMBINE function is concatenation and the weight matrix W l in Eq 22 can be viewed as the combination of multiple W l i,r . Specifically, Geom-GCN redefines multiple neighborhoods based on the customized geometric relations in both raw and latent space. The messages are aggregated from each neighborhood and combined by a concatenation. This approach may be applicable to some datasets, yet it has weak universality.H2GCN [12] is also an influential method with three key designs: ego-and neighbor-message separation, higher-order neighborhoods, and the combination of intermediate representations. Its single-layer representations are constructed as follows:EQUATIONwhere Âh2 denotes the 2-order adjacency matrix with normalization.It can be revisited by HTMP with the following components:EQUATIONwhere the COMBINE function is concatenation. Meanwhile, H2GCN also uses the concatenation as the FUSE function. Specifically, H2GCN aggregates messages from the raw and 2-order neighborhoods in a layer of message passing and keeps them apart in the representations. The design of ego/neighbor separation is first introduced by H2GCN and gradually becomes a necessity for subsequent methods.SimP-GCN [14] constructs an additional graph based on the feature similarity. It has two key concepts:(1) the information from the original graph and feature kNN graph should be balanced, and (2) each node can adjust the contribution of its node features. Specifically, the message passing in SimP-GCN is as follows:EQUATIONwhere s l ∈ R n is a learnable score vector that balances the effect of the original and feature graphs,D l K = diag(K l 1 , K l 2 , ..., K l n ) is a learnable diagonal matrix.It can be revisited by HTMP with the following components:EQUATIONwhere the COMBINE function is adaptive weighted addition. Specifically, SimP-GCN aggregates messages from ego, raw and feature-similarity-based neighborhoods, and combines them with node-specific learnable weights. The feature-similarity-based neighborhoods can provide more homophilous messages to enhance the discriminability of the compatibility matrix. However, it's still limited by the amount of information on node features.FAGCN [11] proposes considering both low-frequency and high-frequency information simultaneously, and transferring them into the negative-allowable weights during message passing:EQUATIONwhere α G ij can be negative as follows:EQUATIONwhich can form a weight matrix:EQUATION)It can be revisited by HTMP with the following components:EQUATIONwhere the COMBINE function is weighted addition, same as the matrix form of Eq 28. Specifically, FAGCN aggregates messages from node ego and raw neighborhood with negative-allowable weights.It has a similar form to GAT but allows for ego/neighbor separation and negative weights, which means the model can capture the difference between center nodes and neighbors.A.2.9 GGCN GGCN [23] explicitly distinguishes between homophilous and heterophilous neighbors based on node similarities, and assigns corresponding positive and negative weights:EQUATIONwhere Ẑl = Z l-1 W l + b l , Ãl T = Ã ⊙ T l is an adjacency matrix weighted by the structure property, β l 0 , β l 1 and β l 2 are learnable scalars. The neighbors are distinguished by the cosine similarity of node representations with a threshold of 0:EQUATIONIt can be revisited by HTMP with the following components:EQUATIONwhere A p and A n are discriminated by the representation similarities:EQUATIONThe COMBINE function is an adaptive weighted addition. Specifically, GGCN divides the raw neighborhood into positive and negative ones based on the similarities among node presentations.On this basis, it aggregates messages from node ego, positive and negative neighborhoods, and combines them with node-specific learnable weights. This approach allows for targeted processing for homophilous and heterophilous neighbors, yet can suffer from the accuracy of discrimination, which may lead to the accumulation of errors.ACM-GCN [18] introduces 3 channels (identity, low pass and high pass) to capture different information and mixes them with node-wise adaptive weights:EQUATIONwhere diag(α l I ), diag(α l L ), diag(α l H ) ∈ R N ×1 are learnable weight vectors.It can be revisited by HTMP with the following components:EQUATIONwhere the COMBINE function is adaptive weighted addition. Specifically, ACM-GCN aggregates node ego, low-frequency, and high-frequency messages from ego and raw neighborhoods, and combines them with node-wise adaptive weights. With simple but effective designs, ACM-GCN achieves outstanding performance, which shows that complicated designs are not necessary.OrderedGNN [21] is a SOTA method that introduces a node-wise adaptive dimension concatenation function to combine messages from neighbors of different hops:EQUATIONwhere P d ∈ R N ×dr is designed to be matrix with each line P l d,i being a dimension indicate vector, which starts with continuous 1s while the others be 0s. In practice, to keep the differentiability, it's "soften" as follows:EQUATIONwhere f l ξ is a learnable layer that fuses two messages.It can be revisited by HTMP with the following components:EQUATIONwhere the COMBINE function is concatenation with node-wise adaptive dimensions. Specifically, in each layer, OrderedGNN aggregates messages from node ego and raw neighborhood and concatenates them with learnable dimensions. Combined with the multi-layer architecture, this approach can aggregate messages from neighbors of different hops and combine them not only with adaptive contributions but also as separately as possible.The HTMP mechanism splits the message-passing mechanism of HTGNNs into multiple modules, establishing connections among methods. For instance, most message passing in HTGNNs have personalized processing for nodes. Some methods [24, 11, 13, 22] utilize the learnable aggregation guidance and some others [14, 18, 21, 23] count on learnable COMBINE functions. Though neighborhood redefining is commonly used in HTGNNs, there are also many methods [24, 11, 18, 20, 21] using only raw neighborhoods to handle heterophily and achieve good performance. Degree averaging, which plays the role of a low-pass filter to capture the smooth signals, can still work well in many HTGNNs [12, [14] [15] [16] 20] . High-order neighbor information may be helpful in heterophilous graphs. Existing HTGNNs utilize it in two ways: directly defining high-order [12, 13, 16, 17] or even full-connected [19] neighborhood indicators and by the multi-layer architecture of message passing [20, 21] .With the aid of HTMP, we can revisit existing methods from a unified and comprehensible perspective.An obvious observation is that the coordination among designs is important while good combinations with easy designs can also achieve wonderful results. For instance, in ACM-GCN [18] , the separation and adaptive addition of ego, low-frequency, and high-frequency messages can accommodate the personalized conditions of each node. OrderedGNN's design [21] , which includes an adaptive connection mechanism, ego/neighbor separation, and multi-layer architecture, allows discrete and adaptive combinations of messages from multi-hop neighborhoods. This advises us to take into account all components simultaneously when designing models. As an illustration, please be cautious about using multiple learnable components. Also, here are some additional model design tips and considerations. Please separate the messages from node ego and neighbors. When combining them afterward, whether by weighted addition or concatenation, this approach is at least harmless if not beneficial, especially when dealing with heterophilous graphs. Last but not least, try to design a model capable of personalized handling different nodes. Available components include but are not limited to, custom-defined neighborhood indicators, aggregation guidance with adaptive weights or estimated relationships, and learnable COMBINE functions. This is to accommodate the diversity and sparsity of neighborhoods that nodes in real-world graphs may have.Homophilous Graph Neural Networks. Graph Neural Networks (GNNs) have showcased impressive capabilities in handling graph-structured data. Traditional GNNs are predominantly founded on the assumption of homophily, broadly categorized into two classes: spectral-based GNNs and spatial-based GNNs. Firstly, spectral-based GNNs acquire node representations through graph convolution operations employing diverse graph filters [1, 32, 33] . Secondly, spatial-based methods gather information from neighbors and update the representation of central nodes through the message-passing mechanism [26, 28, 34] . Moreover, for a more comprehensive understanding of existing homophilous GNNs, several unified frameworks [35, 36] have been proposed. Ma et al. [35] propose that the aggregation process in some representative homophilous GNNs can be regarded as solving a graph denoising problem with a smoothness assumption. Zhu et al. [36] establishes a connection between various message-passing mechanisms and a unified optimization problem.However, these methods have limitations, as the aggregated representations may lose discriminability when heterophilous neighbors dominate [11, 12] .Heterophilous Graph Neural Networks. Recently, some heterophilous GNNs have emerged to tackle the heterophily problem [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] . Firstly, a commonly adopted strategy involves expanding the neighborhood with higher homophily or richer messages, such as high order neighborhooods [12, 13] ,feature-similarity-based neighborhoods [13, 14] , and custom-defined neighborhoods [15, 22] . Secondly, some approaches [11, [17] [18] [19] 23] aim to leverage information from heterophilous neighbors, considering that not all heterophily is detrimental et al. [6] . Thirdly, some methods [12, 16, 20, 21] adapt to heterophily by extending the combine function in message passing, creating variations for addition and concatenation. On this basis, several works have reviewed existing heterophilous methods. Zheng et al. [8] and Zhu et al. [9] identifies effective designs in heterophilous GNNs and analyzes the relationship between heterophily and graph-related issues. Gong et al. [10] provide a higher-level perspective on learning heterophilous graphs, summarizing and classifying existing methods based on learning strategies, architectures, and applications. However, these reviews merely classify and list methods hierarchically, lacking unified understandings and not exploring the reason behind the effectiveness of message passing in heterophilous graphs.To explore the performance impact of homophily level, node degrees and compatibility matrix (CMs) on simple GNNs, we conduct some experiments on synthetic datasets.We construct synthetic graphs considering the factors of homophily, CMs and degrees. For homophily, we set 3 levels including Lowh (0.2), Midh (0.5), and Highh (0.8). For CMs, we set two levels of discriminability, including Easy and Hard. For degrees, we set two levels including Lowdeg (4) and Highdeg (18) . Note that with a certain homophily level, we can only control the non-diagonal elements of CMs. Thus, there are a total of 12 synthetic graphs following the above settings. These synthetic graphs are based on the Cora dataset, which provides node features and labels, which means, only the edges are constructed. We visualize the CMs of these graphs in Figure 3 . Since there is no significant difference in CMs between low-degree and high-degree, we only plot the high-degree ones. Further, the edges are randomly constructed under the guidance of these CMs and degrees to form the synthetic graphs.We use GCN to analyze the performance impact of the above factors. The semi-supervised node classification performance of GCN is shown in Overall Message Passing Mechanism. The overall message passing mechanism in CMGNN is formatted as follows:EQUATIONwhere diag(α l 0 ), diag(α l 1 ), diag(α l 2 )R N ×1 are the learned combination weights introduced below.COMBNIE Function with Adaptive Weights. Firstly, we list the aggregated messages Z l r from 3 neighborhoods:EQUATION)The combination weights are learned by an MLP with Softmax:EQUATIONwhere W l att ∈ R (3dr+1)×3 and W l mix ∈ R 3×3 are two learnable weight matrixes, d is the node degrees which may be helpful to weights learning.The Message Passing of Supplementary Prototypes. In practice, the virtual prototype nodes are viewed as additional nodes, which have the same message passing mechanism as real nodes:EQUATIONEQUATIONwhere A sup,ptt = 1 ∈ R K×K and B sup,ptt = Ĉptt M are similar with those of real nodes.Update Strategy for the Estimation of the Compatibility Matrix. For the sake of efficiency, we do not estimate the compatibility matrix in each epoch. Instead, we save it as fixed parameters and only update it when the evaluation performance is improved during the training.Predition of CMGNN. CMGNN leverages the prediction of the model during message passing. For initialization, nodes have the same probabilities belonging to each class. During the message passing, the prediction soft label Ĉ is replaced by the output of CMGNN, formatted as follow:EQUATION)where CLA is a classifier implemented by an MLP and Z is the final node representations.In this section, we describe the details of the new benchmarks, including (i) the reason why we need a new benchmark: drawbacks of existing datasets; (ii) detailed descriptions of new datasets; (iii) baseline methods and the codebase; and (iv) details of obtaining benchmark performance.As mentioned in [30] , the widely used datasets Cornell, Texas, and Wisconsin 2 have a too small scale for evaluation. Further, the original datasets Chameleon and Squirrel have an issue of data leakage, where some nodes may occur simultaneously in both training and testing sets. Then, the splitting ratio of training, validation, and testing sets are different across various datasets, which is ignored in previous works.Therefore, to build a comprehensive and fair benchmark for model effectiveness evaluation, we will newly organize 10 datasets with unified splitting across various homophily values in the next Subsection F.2.In our benchmark, we adopt ten different types of publicly available datasets with a unified splitting setting (48%/32%/20% for training/validation/testing) for fair model comparison, including Roman-Empire [30] , Amazon-Ratings [30] , Chameleon-F [30] , Squirrel-F [30] , Actor [15] , Flickr [37] ,BlogCatalog [37] , Wikics [38] , Pubmed [39] , and Photo [29] . The datasets have a variety of homophily values from low to high. The statistics and splitting of these datasets are shown in Table 6 .The detailed description of the datasets is as follows: • Roman-Empire3 [30] is derived from the extensive article on the Roman Empire found on the English Wikipedia, chosen for its status as one of the most comprehensive entries on the platform.It contains 22,662 nodes and 65,854 edges between nodes. Each node represents an individual word from the text, with the total number of nodes mirroring the length of the article. An edge between two nodes is established under one of two conditions: the words are sequential in the text or they are linked in the sentence's dependency tree, indicating a grammatical relationship where one word is syntactically dependent on the other. Consequently, the graph is structured as a chain graph, enriched with additional edges that represent these syntactic dependencies. The graph encompasses a total of 18 distinct node classes, with each node being equipped with 300-dimensional attributes obtained by fastText word embeddings [40] .• Amazon-Ratings 3 [30] is sourced from the Amazon product co-purchasing network metadata dataset [41] . It contains 24,492 nodes and 186,100 edges between nodes. The nodes within this graph represent products, encompassing a variety of categories such as books, music CDs, DVDs, and VHS video tapes. An edge between nodes signifies that the respective products are often purchased together. The objection is to forecast the average rating assigned to a product by reviewers, with the ratings being categorized into five distinct classes. For the purpose of node feature representation, we have utilized the 300-dimensional mean values derived from fastText word embeddings [40] , extracted from the textual descriptions of the products.• Chameleon-F and Squirrel-F 3 [30] are specialized collections of Wikipedia page-to-page networks [42] , of which the data leakage nodes are filtered out by [30] . Within these datasets, each node symbolizes a web page, and edges denote the mutual hyperlinks that connect them. The node features are derived from a selection of informative nouns extracted directly from Wikipedia articles. For the purpose of classification, nodes are categorized into five distinct groups based on the average monthly web traffic they receive. Specifically, Chameleon-F contains 890 nodes and 13,584 edges between nodes, with each node being equipped with 2,325-dimensional features.Squirrel-F contains 2,223 nodes and 65,718 edges between nodes, with each node being equipped with a 2,089-dimensional feature vector.• Actor4 [15] is an actor-centric induced subgraph derived from the broader film-director-actor-writer network, as originally presented by [43] . In this refined network, each node corresponds to an individual actor, and the edges signify the co-occurrence of these actors on the same Wikipedia page. The node features are identified through the presence of certain keywords found within the actors' Wikipedia entries. For the purpose of classification, the actors are organized into five distinct categories based on the words of the actor's Wikipedia. Statistically, it contains 7,600 nodes and 30,019 edges between nodes, with each node being equipped with a 932-dimensional feature vector.• Flickr and Blogcatalog5 [37] are two datasets of social networks, originating from the blog-sharing platform BlogCatalog and the photo-sharing platform Flickr, respectively. Within these datasets, nodes symbolize the individual users of the platforms, while links signify the followship relationships that exist between them. In the context of social networks, users frequently create personalized content, such as publishing blog posts or uploading and sharing photos with accompanying tag descriptions. These textual contents are consequently treated as attributes associated with each node. The classification objection is to predict the interest group of each user. Specifically, Flickr contains 7,575 nodes and 479,476 edges between nodes. The graph encompasses a total of 9 distinct node classes, with each node being equipped with a 12047-dimensional attribute vector.BlogCatalog contains 5,196 nodes and 343,486 edges between nodes. The graph encompasses a total of 6 distinct node classes, with each node being equipped with 8189-dimensional attributes.• Wikics6 [38] is a dataset curated from Wikipedia, specifically designed for benchmarking the performance of GNNs. It is meticulously constructed around 10 distinct categories that represent various branches of computer science, showcasing a high degree of connectivity. The node features are extracted from the text of the associated Wikipedia articles, leveraging the power of pretrained GloVe word embeddings [44] . These features are computed as the average of the word embeddings, yielding a comprehensive 300-dimensional representation for each node. The dataset encompasses a substantial network of 11,701 nodes interconnected by 431,206 edges.• Pubmed7 [39] is a classical citation network consisting of 19,717 scientific publications with 44,338 links between them. The text contents of each publication are treated as their node attributes, and thus each node is assigned a 500-dimensional attribute vector. The target is to predict which of the paper categories each node belongs to, with a total of 3 candidate classes.• Photo8 [29] is one of the Amazon subset network from [29] . Nodes in the graph represent goods and edges represent that two goods are frequently bought together. Given product reviews as bag-of-words node features, each node is assigned a 745-dimensional feature vector. The task is to map goods to their respective product category. It contains 7,650 nodes and 238,162 edges between nodes. The graph encompasses a total of 8 distinct product categories.For comprehensive comparisons, we choose 13 representative homophilous and heterophilous GNNs as baseline methods in the benchmark, including (i) Shallow base model: MLP; (ii) Homopihlous GNNs: GCN, GAT, GCNII; and (iii) Heterophilous GNNs: H2GCN, MixHop, GBK-GNN, GGCN, GloGNN, HOGGCN, GPR-GNN. Detailed descriptions of some of these methods can be seen in Appendix A.2.To explore the performance of baseline methods on new datasets and facilitate future expansions, we collect the official/reproduced codes from GitHub and integrate them into a unified codebase.Specifically, all methods share the same data loaders and evaluation metrics. One can easily run different methods with only parameters changing within the codebase. The codebase is based on the PyTorch9 framework, supporting DGL10 and PyG11 . Detailed usages of the codebase are available in the Readme file of the codebase.Following the settings in existing methods, we construct 10 random splits (48%/32%/20% for train/valid/test) for each dataset and report the average performance among 10 runs on them along with the standard deviation.For all baseline methods except MLP, GCN, and GAT, we conduct parameter searches within the search space recommended by the original papers. The searches are based on the NNI framework with an anneal strategy. We use Adam as the optimizer for all methods. Each method has dozens of search trails according to their time costs and the best performances are reported. The currently known optimal parameters of each method are listed in the codebase. We run these experiments on NVIDIA GeForce RTX 3090 GPU with 24G memory. The out-of-memory error during model training is reported as OOM in Table 2 .In this section, we describe the additional details of the experiments, including experimental settings and results.Our method has the same experimental settings within the benchmark, including datasets, splits, evaluations, hardware, optimizer and so on as in Appendix F.4.Parameters Search Space. We list the search space of parameters in Table 7 , where patience is for early stopping, nhidden is the embedding dimension of hidden layers as well as the representation dimension d r , relu_varient decides ReLU applying before message aggregation or not as in ACM-GCN, structure_info determines whether to use structure information as supplement node features or not. Ablation Study. In the ablation study, there are three variants of our methods: without SM, without DL, without SM and DL. For "without SM", we delete the supplementary messages during message passing, using only messages from node ego and raw neighborhood for combination. For "without DL", we simply set λ = 0 to delete the discrimination loss. For "without SM and DL", we just combine the above two settings.In this subsection, we show some additional experimental results and analysis.The additional visualizations of CM estimations are shown in Figure 5 . As we can see, our method can estimate quite accurate CMs among various homophily and class numbers, which provides a good foundation for the construction of supplementary messages. 0.11 0.00 0.18 0.12 0.11 0.09 0.02 0.04 0.00 0.01 0.02 0.01 0.01 0.00 0.00 0.03 0.07 0.17 0.12 0.07 0.09 0.06 0.08 0.08 0.05 0.05 0.02 0.09 0.00 0.01 0.02 0.04 0.00 0.00 0.03 0.17 0.01 0.25 0.08 0.14 0.12 0.08 0.07 0.03 0.05 0.00 0.05 0.00 0.03 0.00 0.02 0.01 0.00 0.05 0.15 0.07 0.00 0.00 0.00 0.06 0.12 0.01 0.02 0.02 0.00 0.05 0.01 0.05 0.03 0.00 0.09 0.31 0.03 0.15 0.08 0.07 0.07 0.09 0.09 0.04 0.04 0.03 0.03 0.01 0.09 0.01 0.02 0.01 0.02 0.11 0.29 0.10 0.00 0.00 0.00 0.08 0.00 0.01 0.01 0.06 0.00 0.09 0.01 0.00 0.19 0.00 0.05 0.10 0.20 0.05 0.09 0.11 0.10 0.06 0.00 0.02 0.01 0.01 0.03 0.04 0.02 0.15 0.00 0.01 0.04 0.08 0.03 0.23 0.17 0.04 0.07 0.04 0.06 0.02 0.10 0.01 0.01 0.00 0.01 0.00 0.01 0.01 0.02 0.16 0.00 0.12 0.12 0.04 0.02 0.02 0.24 0.01 0.14 0.04 0.00 0.06 0.02 0.02 0.03 0.01 0.00 0.10 0.17 0.18 0.17 0.20 0.29 0.15 0.17 0.18 0.21 0.28 0.14 0.17 0.19 0.22 0.28 0.14 0.17 0.17 0.24 0.28 0.14 0.16 0.17 We show the additional performance on nodes with various degrees in Justification: The contributions and scope of this paper are included in the abstract and introduction.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Codebase is available at the supplementary material.https://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-11/www/wwkbhttps://github.com/yandex-research/heterophilous-graphs/tree/main/datahttps://github.com/bingzhewei/geom-gcn/tree/master/new_data/filmhttps://github.com/TrustAGI-Lab/CoLA/tree/main/raw_datasethttps://github.com/pmernyei/wiki-cs-datasethttps://linqs.soe.ucsc.edu/datachttps://github.com/shchur/gnn-benchmarkhttps://pytorch.orghttps://www.dgl.aihttps://www.pyg.org 


Decision: This paper revisits ideas for addressing heterophily in graph neural networks and proposes a "unified heterophilous message-passing (HTMP) mechanism". Overall concerns about heterophily in graphs addressed by GNNs is a rough area of research with confusion about relevant notions of heterophily, whether heterophily is itself a primary problem or merely a distraction from other relevant aspects of graph structure that differentiate datasets of interest. The reviewers appreciated the paper's detailed experiments but raised a number of concerns, including the lack of clairty about "good" vs "bad" heterophily, claims that require greater theoretical backing, insufficient contexutalization of the paper in previous work on heterophily, and missing comparisons with relevant baselines. After a discussion and the raising of a reviewer score, the paper remains on the low side of borderline.

Reviews: review: paper_summary: paper_summary: This paper aims to address the question of "why does message passing remain effective on heterophilous graphs" and proposes a unified framework called heterophilous message-passing (HTMP) mechanism. It extensively reviews the architecture of existing heterophilous GNNs under this framework. It then moves on to discuss the empirical observation that the success of message passing in existing heterophilous GNNs is attributed to their implicitly enhancement of the compatibility matrix among classes, and proposed a new GNN approach called CMGNN to further enhance the separability of the compatibility matrix for different classes in the message passing process. The paper includes an extensive empirical analysis involving 10 benchmark datasets and 13 well-established baseline GNNs, and show that the proposed CMGNN approach has the best overall performance against the baselines.
strength_weakness: strength_weakness: - This work builds upon the findings of several previous works regarding the effective designs for GNNs under heterophily and when is heterophily challenging (or in other words, "bad") for GNNs. While the authors cited these works in some parts of the paper ([6,9,12,18] in References), I feel that **some of the observations in the paper overlapped with the findings in previous works, and their connections and differences are not clearly stated in the paper**. 
  - For example, Observation 1 seems to overlap with the previous observations made in [6] ("to ensure that the neighborhood patterns for nodes with different labels are distinguishable, the inter- class similarity should be low") and [9] ("two key factors, low-degree nodes and complex compatibility matrices, deteriorate the distinguishability of the neighborhood label distributions when coupled with heterophily, thus making heterophily a unique challenge for GNNs in most cases"). 
  - Given this, I also think that the claim in the related work section (line 732-734) that "these reviews ... not exploring the reason behind the effectiveness of message passing in heterophilous graphs" is inaccurate, as this paper is in fact built upon these analyses regarding the effectiveness of message passing in heterophilous graphs. 

- Section 5 (method) is too condensed to present a clear picture of how the proposed Compatibility Matrix-Aware GNN (CMGNN) works for the readers. For example, it is unclear what "topology structure" that the authors are considering as "additional available node features", and the term in Eq. 7 is not well explained. The authors also didn't explain clearly in the main paper how is the "soft pseudo labels" being generated for the model. It will help with the understanding if the authors can include a figure showing the architecture of the proposed CMGNN model. I feel the "method" section is the most novel part in the paper and deserves more length in the paper. 

- It would be good to analyze the computational complexity and/or compare the empirical runtime of the model with the baselines. 

- As a minor point, the "Norm" term in Eq. 3 should be explained as "L1 normalization for matrix row vectors" to avoid the confusion that the normalization is done with the L1 norm for *matrix* (instead of for vectors).
questions: questions: - As per Weakness point 1, can you describe how the observations in the paper are connected to, and different with, prior observations in [6,9,12,18]? 
- As per Weakness point 2, what is the "topology structure" that you considered as "additional available node features"? How does the use of these features affect the performance of the proposed model? 
- Can you provide some analysis regarding the computational complexity and/or the empirical runtime of the model?
limitations: limitations: The authors acknowledged the limitation that the proposed HTMP framework is only applicable to GNNs following the message-passing mechanism. One additional limitation is that the paper is mostly empirical and does not give theoretical underpinnings.
paper_summary: paper_summary: This work revisits the message-passing mechanisms in existing HTGNNs and reformulates them into a unified heterophilous message-passing (HTMP) mechanism. Based on HTMP, the authors propose a new framework named CMGNN. Experiments on 10 datasets with 13 different baseline models demonstrate the effectiveness of the proposed framework.
strength_weakness: strength_weakness: 1. Paper presentation could be further improved. For example, the conception of "good" heterophily and "bad" homophily deserves further explanation. There are some spelling mistakes, such as "heterophilious" in line 12.
2. If space permits, I feel like moving experiments in Appendix C to the main body would be better for the introduction of *Observation 1*. 
3. It might be hard to follow as this paper has so many equations, especially those about CMGNN. So I suggest providing a flow chart or a pseudo algorithm for better understanding.
4. Conclusions in this paper are mainly based on experiment results. It would be better if corresponding theoretical analysis or proofs are provided.
questions: questions: 1. What are the contributions to the newly built benchmark datasets? It seems that this work just collects 10 existing datasets and sets them with the same train-valid-test split ratio.
2. The weighting function (Eq.9) seems to be quite empirical. Is it possible to further discuss it?
limitations: limitations: As the authors mentioned, this work mainly focuses on semi-supervised settings, which could be further generalized.
paper_summary: paper_summary: 1. The paper unifies existing heterophilous graph neural networks (HTGNNs) into a Heterophilous Message-Passing (HTMP) mechanism.
2. The authors reveal that the effectiveness of HTMP is due to increasing differences among node representations belonging to different classes.
3. Guided by this revelation, the paper then introduces Compatibility Matrix-aware Graph Neural Network (CMGNN) to further enhance HTGNNs.
4. The authors conduct fair evaluations and comparative analysis on multiple benchmark datasets, highlighting the superior performance of the HTMP mechanism and the proposed CMGNN method.
strength_weakness: strength_weakness: 1. Several research publications [1, 2, 3] have used compatible matrices to boost the effectiveness of GNNs on heterophilic graphs. In-depth qualitative and quantitative comparisons are missing from this submission. Including such analyses would significantly increase the importance of the contributions.
2. Some claims made in the paper, such as Observation 1 and Observation 2 in Section 4, would benefit from additional analysis. For instance, including theoretical analysis with formal notations would provide more rigorous support for these claims.
3. Existing survey articles have unified and categorised message passing on heterophilic graphs [4,5,6]. This submission should compare and position the proposed HTMP unification against these categorisations.
4. The experiments lack a comparison of training times with baseline models. Including an analysis of the tradeoff between accuracy and training time would greatly enhance the results.




References:
1. Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation, In TMLR'22,
2. Explicit pairwise factorized graph neural network for semi-supervised node classification, In UAI'21,
3. Graph Neural Networks with Heterophily, In AAAI'21,
4. Graph Neural Networks for Graphs with Heterophily: A Survey,
5. Learning from Graphs with Heterophily: Progress and Future,
6. Heterophily and Graph Neural Networks: Past, Present and Future.



**Edit post Rebuttal:**
The authors have promised to include detailed comparisons in a future revised version. Since these details cannot be verified within the review period, I will lower my confidence from 4 to 3. However, given that other major concerns have been addressed, I will raise my rating by one point from 4 to 5.
questions: questions: 1. Were there insights on how the compatible matrices utilised in CMGNN compared with the methods in the referenced publications [1, 2, 3]? What were the pros and cons of CMGNN to tackle heterophily with existing methods that use compatibility matrices?
2. Were there theoretical foundations that support Observation 1 and Observation 2? What formal notations and theoretical analyses could be included to strengthen the support for these observations?
3. How did the proposed HTMP unification differ from the categorisations presented in the existing survey articles [4, 5, 6]? What unique insights did the HTMP unification offer compared to existing unifications?
4. What did the tradeoff between accuracy and training times of the proposed methods and the baselines look like?
limitations: limitations: The authors have provided some discussion on the limitations of their work (for instance, see section 7 on Page 9).

Potential negative societal impacts are not relevant to this study.

Comments: title: Response to Authors' Rebuttal
Thank you
Thanks for the Rebuttal
comment: Thanks again for your careful reading and valuable suggestions, which have significantly improved our manuscript.

Best Regards!
I appreciate the authors detailed response to my questions and comments. After reading authors' response, I decide to keep my original rating.
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!
Thanks to the authors for the rebuttal.

The responses mostly address the concerns raised. The paper should include in-depth qualitative and quantitative comparisons with existing methods that use compatibility matrices. This should involve performance metrics, robustness tests, and case studies to highlight the differences and advantages of the proposed method compared to similar methods in the literature.

The authors have promised to include these comparisons in a future revised version. Since these details cannot be verified within the review period, I will lower my confidence. However, given that all other concerns have been addressed, I will raise my rating by one point.