Understanding and Enhancing Message Passing on Heterophilic Graphs via Compatibility Matrix
Authors: Zhuonan Zheng
Yuanchen Bei
Zhiyao Zhou
Sheng Zhou
Yao Ma
Ming Gu
HONGJIA XU
Jiawei Chen
Jiajun Bu
Venue: NeurIPS 2025 poster ()
Keywords: Graph Neural Networks
Heterophily
Message Passing
Compatibility Matrix
Primary area: deep_learning
TL;DR: This paper explore the essence of message passing on heterophilic graphs from the perspective of model and design a method with the guidance of theoretical findings.

Abstract: Graph Neural Networks (GNNs) excel in graph mining tasks thanks to their message-passing mechanism, which aligns with the homophily assumption. However, connected nodes can also exhibit inconsistent behaviors, termed heterophilic patterns, sparking interest in heterophilic GNNs (HTGNNs). Although the message-passing mechanism seems unsuitable for heterophilic graphs owing to the propagation of dissimilar messages, it is still popular in HTGNNs and consistently achieves notable success. Some efforts have investigated such an interesting phenomenon, but are limited in the data perspective. The model-perspective understanding remains largely unexplored, which is conducive to guiding the designs of HTGNNs. To fill this gap, we build the connection between node discriminability and the compatibility matrix (CM). We reveal that the effectiveness of the message passing in HTGNNs may be credited to increasing the proposed Compatibility Matrix Discriminability (CMD). However, the issues of sparsity and noise pose great challenges to leveraging CM. Thus, we propose CMGNN, a novel approach to alleviate these issues while enhancing the CM and node embeddings explicitly. A thorough evaluation involving 13 datasets and comparison against 20 well-established baselines highlights the superiority of CMGNN.

Understanding and Enhancing Message Passing on Heterophilic Graphs via Compatibility Matrix
Zhuonan Zheng** Yuanchen Bei*, Zhiyao Zhou Sheng Zhou *
Yao Ma², Ming Gu**, Hongjia Xu* a .Jaaeei Chen Jiajun Bu
Zhejiang Key Laboratory of Accessible Perception and Intelligent Systems, Zhejiang University College of Computer Science and Technology. Zhejjang University
Schooo of Software Technology, Zhejiang University School of Science, Rensselaer Polytechnic Institute
Abstract
Graph Neural Networks (GNNs) excel in graph mining tasks thanks to their message-passing mechanism, which aligns with the homophily assumption. How- ever, connected nodes can also exhibit inconsistent behaviors, termed heterophilic patterns, sparking interest in heterophilic GNNs (HTGNNs), Although the message- passing mechanism seems unsuitable for heterophilic graphs owing to the propaga- tion of dissimilar messages, is still popular in HTGNNs and consistently achieves notable success. Some efforts have investigated such an interesting phenomenon, but are limited in the data perspective. The model model- perspective understanding re- mains largely unexplored, which is conducive to guiding the designs of HTGNNs. To fill this gap, we build the connection between node discriminability and the compatibility matrix (CM). We reveal that the effectiveness of the message passing in HTGNNs may be credited increasing the proposed Compatibility Matrix Discriminability (CMD). However, the issues of sparsity and noise pose great chal- lenges to leveraging CM. Thus, we propose CMGNN, novel approach to alleviate these issues while enhancing the CM and node embeddings explicitly. A thor- ough evaluation involving 13 datasets and comparison against 20 establistbl baselines highlights the superiority of CMGNN.
Introduction
Graph Neural Networks (GNNs) have shown remarkable performance graph mining tasks, such as social network analysis [ and recommender systems 3 4 The widely used message-passing
mechanism is typically based on the homophily assumption (5), which assumes that nodes are inclined to behave similarly to their neighbors [6). However, this assumption is often violated in real-world graphs, where connected nodes exhibit a contrasting tendency called heterophily [7]. In response to the challenges of heterophily, heterophilic GNNs (HTGNNs) have attracted considerable interest 66, 8 19] with numerous innovative approaches [10 However, the majority of them continue to employ
pessage-passsig mechanism and remain successful, which was not originally designed for heterophilic graphs, as they tend to incorporate excessive messages from disparate classes. This raises question: Why does message passing remain effective on heterophilic graphs?
Some efforts 6 9 15] have begun to investigate this question and reveal that vanilla message- passing (VMP) can still work on heterophilic graphs under certain conditions. However, these works are limited in studying what kind of data is suitable for VMP. A large part of HTGNNs have modified the pesssage-passingg mechanism in response to heterophily, namely heterophilic message- passing (HTMP), which outperforms VMP on heterophilic graphs. How HTMP works effectively in
"Corresponding Author: zhousheng zju@ zju.edu.cn.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

certain data remains largely unexplored. In this paper, we investigate the connection between node discriminability and the compatibility matrix (CM), that is, the latent connection preference among classes within graph. We propose the Compatibility Matrix Discriminability (CMD) to measure the discriminability of CM. Theoretical and empirical analyses prove that node discriminability and CMI) are positively correlated in VMP while ignoring the influence of node degrees. In addition, toy example and a posterior evaluation in representative HTGNN show that the effectiveness of existing HTMP mechanisms may be attributed to increasing CMD, which leads to better node embeddings.
This discovery explains the essence of HTMP and provides insight for the design of new HTGNNs. Nevertheless, the graph sparsity and noise bring significant challenges for leveraging the CM as they can cause low-quality CM estimations, misguiding the message passing. To fill this gap, we propose novel Compatibility Matrix aware Graph Neural Network (CMGNN), which alleviates the sparsity and noise issues by introducing supplementary CM-aware messages while preserving the original neighborhood information. Meanwhile, targeted constraint is applied to explicitly and simultaneously enhance the CMD and node embeddings. We then conduct fair comparisons to evaluate the effectiveness of CMGNN, compared with 20 baseline methods on 13 datasets with varying homophily levels and scales. Extensive experimental results demonstrate that CMGNN outperforms all baseline methods on heterophilic graphs while also being competitive homophilic graphs. The contributions of this paper are summarized as follows:
Theoretical Findings. We reveal the possible principle behind the heterophilic message-passing mechanism through comprehensive theoretical and empirical analyses, which may help people better understand the HTMP mechanism.
Proposed Method. We introduce CMGNN, a novel approach that leverages and enhances the CM learn better node embeddings while alleviating the issues of graph sparsity and noise.
Benchmarking and Evaluation. We construct comprehensive and fair benchmark to evaluate the effectiveness of CMGNN, Extensive experimeettl results show the superiority of CMGNN. Our code is available at htttss//ghhabbbcom/////3//CCC
2 Preliminaries
Notations. Given a graph 9 = E, Y), Vss the node set and E is the edge set. Nodes are characterized by the feature matrix X E NR,,, where = |V/ denotes the number of nodes, d is the feature dimension. Y Nx1 is the node labels with the one-hot version C E R N K where K is the number of node classes. A E N is the adjacency matrix, each element asj in A denotes whether there is an edge between i and j. and D = diag(d), (d.,,,.,dd dn) represents the diagonal degree matrix, where d; = Σj Oij. The normalized adjacency matrix is denoted by À = D-D AA. We use 1 to represent a matrix with all elements equal to I.
Homophily and Heterophily. Graphs exhibit high homophily when large fraction of neigh- boring nodes have the same labels as the central nodes, whereas graphs with high heterophily show the contrary. For measuring the homophily level, two widely used metrics are edge
homophily he [16] and node homophily h" [17. defined as he EE Y.=Y..J and
[8]
ha 1
[v] Evev E8 Y.=Y.Hl Both metries range from [o, 1]. with higher values denoting d.
greater homophily and lower values signifying stronger heterophily.
Vanilla Peessag--Passingg (VMP). The vanilla pessage-passingg mechanism plays pivotal role in transforming and updating node embeddings based on the neighborhood [8]. Typically, the mechanism operates iteratively and comprises two stages:
Ž' AGGREGATE(A. Zz=1), z' COMBINE (Z'-1
(1)
where the AGGREGATE function first aggregates the input messages 1 from neighborhood A into Z' and subsequently, the COMBINE function combines the messages of the node ego and neighborhood aggregation, resulting in updated embeddings Z'
Heterophilic Message-Passing (HTMP). To adapt to heterophily, many heterophilic message- passing methods have been proposed, which usually extend the neighborhood variously, enriching the sources of messages. In addition, the aggregation weights and the COMBINE function are
2

---

often redesigned to collect neighbor messages preferentially while preserving the ego messages. Moreover, there may exist multiple messages collected from different neighborhoods in HTMP, which simultaneously form node embeddings. In this paper, we use "HTMP" methods to refer to the heterophilic GNNs that follow the message-passing mechanism. More detailed related works are available in Appendix A.
Exploring the Essence of Message Passing on Heterophilic Graphs
In this section, we aim uncover the underlying principle that explains the effectiveness of HTMP Inspired by the key factors identified by Zhu et al. (9. we consider the compatibility matrix (CM) M as a potential path. To formally explore the connection between node discriminability and CM in message passing, we use the Expected Negative KI.-divergence (ENKL. [15 to measure node diseriminability and define Compatibility Matrix Discriminability (CMD) for CM.
Expected Negative KL-divergence (ENKL) 15 ENKL can measure the inter-class node discrim- inability in the graph generated by the Contextual Stochastic Block Model for Homophily/Heterophii
(CSBM-H) [3], a variation of the generative model CSBM [19], which has been widely adopted to study the behavior of GNNs 6 20 21 In CSBM-H, the generated graph comprises two disjoint node sets, i E Co and j E C1, representing two classes. The node features are generated independently. where z; generated from (Ho, I and 2y from ((H4oo1I) with Po l4 E R. and Fj, as the embedding dimension. Node degrees for Co and C1 are do, di respectively. For i E Co. its neighbors are independently sampled as h do intra-class and (1 - h) do inter-class nodes, mirrored for j E C1. Then, the ENKL. is defined as follows:
ENKL(X) -dx(
Fh 40² 402)- (0'
1
2),
(2)
P²
where dx (1 (Ho p= o. Different message-passing mechanisms can obtain different node embeddings with corresponding ENKL values, where smaller ENKL values correspond to more distinguishable node embeddings. Thus, ENKL can serve theoretically guaranteed evaluation criterion for different message passing approaches.
Compatibility Matrix (CM) 77. CM characterizes the latent connection preference among classes within a graph. It formatted as matrix M E xx where the i-th row M, denotes the connection probabilities between class and all classes. It can be estimated empirically as follows:
= Norm ( CC Cm
ÁC,
where Norm(.) is the L1 normalization for matrix row vectors and T is the matrix transpose operation. Cru E R N'K is the semantic neighborhoods of nodes, indicating the proportion of neighbors from each class in the neighborhoods. Thus, the CM under CSBM-H settings is:
h. h,
1- h
McSBM-H
1
(4)
To measure the discriminability of CM, we define the Compatibility Matrix Discriminability (CMD). Definition 3.1 (Compatibilityy Matrix Discriminability (CMD)). Given a compatibility matrix M, the CMD is defined as the average I.1 distance between rows (classes):
Σ ΣK M - M,yl
179 K. KKKK-
CMD(M)
(5)
where K is the number of classes and M, is the i-th row of M. || ||1 denotes the Ll distance. The higher the CMD, the more distinguishable each row in the CM is.
We start with VMP to investigate the potential connection between CMD and ENKL. Following previous work [5), we use a low-pass (LP) operator A as an example of VMP: HLP Áx. Since all neighbors of each node share the same weight in VMP, CM can also indicate the proportion of class-level neighbor messages in node embeddings. Thus, discriminability CM can be transferred to node embeddings in VMP. Formally, through theoretical analysis, have the following theorem.
3

---

Expected Negative Ku-diveggenc Comparison
Compatiblity Matrix Dicciminabliity Comparison
CMD.
CMD_
CMD.
BMLLLL [ML HP
DVR ITPP
Homophily
Homophily
(a) ENKL
(b) CMD
Figure 1: Visualization of CSBM-H (Ho = [1-,, 11 = 1, 2, = 5, 5).
=
Theorem 3.2 (Negatively Correlation between CMD and ENKL of VMP). Consider a graph CSBM-H 14 ogl, ,o,, d)) and the LP operator A as VMP. When ignoring the influence of node degrees, i.e., do = d1, we have Cov CMD(McsaM-H). ENKL(HH)) < 0, where Cov(.) denotes the covariance. It means that the CMD and ENKL of VMP are negatively correlated.
The detailed proof is available in Appendix B We visualize the changing trends of CMD and ENKL of VMP (LP) in Figure D. which does show negative correlation. Thus, more discriminable CM can lead to better node embeddings in VMP. This gives the reason why VMP can work well in some heterophilic situations: CM with low homophily but high discriminability can also lead to high node discriminability in VMP. We conduct experiments on the synthetic dataset to provide empirical analysis in Appendix C This conclusion is similar to previous works 6 9 from the perspective of data, since heterophily and CM are both characteristics of data. However, they lack the understanding from the perspective of the model, which is conducive to guiding the designs of HTGNNs. To fill this gap, we take further step in understanding this theoretical finding with a model perspective and consider such a question: when given the exact data, can we enhance the CMD through the model learn better embeddings? Coincidentally, this may able to explain the essence of HTMP methods, as the weights of practical class-leve neighbor messages in these HTMP methods may be different from the original CM. Since CM is fixed concept for describing the original data, we introduce Weighted-CM for the sake of distinction.
that discuss heterophily
Definition 3.3 (Weighted Compatibility Matrix (Weighted-CMM), The weights of practical class- level neighbor messages after message passing. is also formatted as a matrix M E K where the i-th row M, denotes the aggregate weights of all classes for class i. It can be estimated follows:
= = C.AC.
(6)
where Á NNN the practical aggregate weights matrix during message passing. Note that there is no strict limit to the values: may E R.
For further analysis, we define the identity (D), high-pass (HP) and heterophilic message-pass (HTMP) operators as Á = I. APP = I A. and À HTMP = al + bÂ + cλ2, where a, b, c E [-1, are three learnable weight parameters. The high-pass operator can capture the difference between the central node and its neighborhoods in heterophilic graphs. The HTMP operator is a typical scheme that aims to utilize the linear combination of multiple-order neighborhood messages to obtain more distinguishable embeddings. The embedding matrices after message passing can be represented as Hº = Á o E {I, LP, HP, HTMP). Thus, the Weighted-CMs and corresponding CMDs of identity, LP. HP, and HTMP operators are as follows:
M
11
0
LP
h
1 h
"P =
[ h, h 1 h 1,
0,
1
h
1 h
ITMP
[a+ bh c(ho²
h)
b(1 h) + 2ch(1 h)
(7)
b(1 h) + 2ch(11 h).
a + bh + c(h² + (1 h)
CMD' = 2, CMD IP = 4/4
1
CMD HP
4/h 11. CMD HTMP 2 + (4 2
2(h
2
1
2d)

---

Table 1: CMD and ENKL values of different operators real-world graphs.
Dataset
Roman-Empire
Amazon- Ratings
Chameleon-F
Squirrel-F
Operator
CMD
FNKL
CMD
ENKT.
CMD
ENKL.
CMD
ENKL.
LP
0.85
-0.76
0.46
-0.26
0.27
-25.38
0.08
-14,84
HP
2.77
-2.62
1.95
-0.80
2.07
-126.5
2.02
-67.89
HTMP (Case 1)
3.31
-413
2.35
-1.14
2.39
-150.8
2.22
-80.05
HTMP (Case
3.55
-5.04
3.10
-2.41
2.85
-170.6
2.28
-89.52
10
0.45
0.35
0.14
0.04
0.02
0.52
0.30
0.12
0.04
0.02
0.53
0.28
0.04
0.02
0-0
0.36
0.03
0.50
04
0.08
28
0.07
0.06
0.20
0.07
9.03
0.00
0.16
0.37
0.30
0.12
0.04
0.15
0.31
0.38
0.12
0.04
0.10
0.04
0.16
0.45
0.46
9:18
0.08
84
144
24
=-0.12
0.30
0.37
0.18
0.08
0.13
0.27
0.79
0.21
0:11
0.13
0.26
0.25
0.29
0.67
0.01
41
20
0.33
0.06
0:21
.0.03
-0.03
1
-03
1
116
6
3
(a) Fixed(LP),CMDD00.6 (b) GIoGNN,CMD=O.. (c) GPR- GPR-GNN.CMIN CMDD-00 (d) ACM-GCN,CMI=-0999
Figure 2: Visualizations of Weighted- CM estimated through various methods Amazon- Ratings..
Since we aim to obtain the largest CMD, the values of a, b, can be set as follows:
Case 1, 2 : a 1,b 1, À HTMP + Å + A CMD 8(12
)
1
2'
(8)
Case 2,
-,b=-1.-=
À A², CMD 8(1
1
3,2
3
We visualize the changing trends of CMD and ENKL of the four operators in Figure T Similarly, the two changing trends are negatively correlated independently for each operator, which can also be proven by theoretical analysis. Although the relationship between the CMD and ENKL values among different operators is not consistent, we still show that it is feasible obtain better embeddings by increasing the CMD in HTMP as the HTMP operator achieves the minimum ENKL, i.e., the best node discriminability, most cases by different combinations of parameters a, b,
However, there are significant gaps between the theoretical assumptions of CSBM-H and real- wolld graphs, including multi-class, low-quality node features, among others. What is the impact on the relationship between CMD and ENKL? We count the values of ENKL and CMD when different operators graphs, as in Table We find that the negative correlation between CMD) and ENKL still holds on real-world graphs, which expands the Theorem 3.2
supervisd settings, imbalanced node degrees, and potential
used on some real
3.2 In addition to the above analyses, also
investigated three representative methods, GloGNN 22 GPR-GNN (33, and ACM-GCN [12]
Observation 3.4 (The increased CMDs of representative HTGNNs). We conduct a posterior evaluation on the results of GloGNN, GPR-GNN, and ACM-GCN. All the CMDs of Weighted-CMa have been significantly improved compared to the fixed one of the original data, as shown in Figure 2
More details and examples about the posterior evaluation can be found in Appendix D The success of the HTMP operator and Observation 3.4 gives a possible answer to the effectiveness HTMP:
Remark 3.5 (Increasing CMD a possible reason for the effectiveness HTMP). Given certain data, the HTMP mechanism can increase the CMD by replacing the fixed one with the Weighted-CM via various model-level designs, leading to better node embeddings.
This explains the underlying principle of HTMP and provides insight for designing new HTGNNs via increasing CMD. Several existing works 7 24 25 have naively estimated and used CM without increasing CMD. However, to make good use of CM, there are still two significant issues, namely sparsity and noise, when considering real-world heterophilic graphs. First, node degrees can be very imbalanced. Some nodes may have few neighbors due to the sparsity of the graph, which may not only show a highly inconsistent semantic neighborhood with CM but also be harmful to the effectiveness of message passing. Second, node labels not fully available in the semi-supervised
5

---

Virtual Neighborhood Supplement
7
Llayer Concatenation
O Prstatppss
Z
A stp
O Ceatrol zode
CMlaaaar MP
Clasifier
CM-aware Message Passing
Vietual edges
.......
(00
Rell
Confidence-based Compatibility Matrix Estimation
CM-anarr MP
Prodiction Confedeace:
E: II(C.)
Z tgx
Wour Nightrrted
Zea highterton
Semantic Neitbseebodd:
C Aig C
Auribuutc
Compatbiliy Motix Normil (of)
Figure 3: The overall framework of CMGNN.
setting. Inaccurate predictions of node labels can cause low-quality CM estimation, which misguides the message passing, leading to low-discrininative node embeddings. These issues pose significant challenges to the explicit modeling and effective utilization of CM.
Methodology
To address these issues, introduce Compatibility Matrix-Aware GNN (CMGNN). shown in Figure 3 which alleviates the sparsity and noise issues by virtual neighborhood supplement, confidence-basee compatibility matrix estimation, and CM-aware message passing. Then, straight- forward constraint is applied to explicitly enhance the discriminability of CM and node embeddings.
Virtual Neighborhood Supplement. Given the graph sparsity, some nodes may have low degrees. Thus, CMGNN introduces an additional virtual neighborhood to provide nodes with supplemental messages from each class. The virtual neighborhood is the same for all nodes, which consists of K additional virtual neighbors: A sud = 1 E R NN* It ensures accessibility to the messages of all classes for each node. Specifically, these additional neighbors are K virtual nodes, designed as the class prototypes based on the training set labels. The attributes X E R xd,, neighborhoods A R x and labels Y R R
of prototypes are defined follows:
X Norm (C Xtrain), A = 0, y""=1
(9)
where Ctrain and Xtrain are the one-hot labels and attributes of nodes in the training set. Utilizing class prototypes construct virtual neighborhoods can provide each node with representative messages of all classes, which builds the basis for CM-aware message passing.
Confidence- CM Estimation. The CM can be calculated via Eq 3 with full-available labels. However, label information is not entirely available in semi-supervised settings. Thus, we try to estimate the CM with the help of pseudo labels. To mitigate the impact of potentially incorrect pseudo labels predicted by the model, we introduce confidence metric E R& x1 information entropy, with high entropy indicating low confidence:
derived from the
g.
log K H(C.) E [0, log K],
(10)
where H(p) - E,
Ps P. log(p:) denotes the entropy, Č NxN is the soft pseudo labels composed of training labels Ctrain and model predictions C:
c, c.-f Cirgin,t C₁
0, E Verains otherwise,
(11)
where Virain is the training set. Then the semantic neighborhoods of the nodes are calculated considering the confidence: Čnu = Norm( C)) E NRX Finally, we can estimate the compatibility matrix M E IR K as follows:
M Norm(( C)")
(12)
Note that the CM is repeatedly updated during training. improve efficiency and stability, CM not estimated in every epoch. It remains fixed until the evaluation performance improves.

---

CM-aware Message Passing, Relying entirely on CM to guide message passing can lead to confus- ing embeddings when the quality of CM is low. Therefore, we regard it as a separate supplementary message source while preserving the original neighhorhood distribution. Specifically, CMGNN col- lects messages from node ego, raw neighborhoods A and the supplement neighborhoods A sup, respectively. The first two are widely used in HTGNNs as the ego-neighbor separation design principle [16), while the last provides novel approach to apply CM. The messages from node ego and raw neighborhoods are obtained follows:
E = Z' egon
Drow AZ
w
(13)
raws
where z'-1 is the input node embedding of layer I, W W transformation. For the supplement neighborhood, we leverage CM to offer nodes additional messages
rour are learnable matrices for message
ego:
personalized by their soft pseudo labels, which converts discriminability from CM into messages:
Zemp = (A sup C CM W!
(14)
snp
where O is the Hadamard product, 1-1 pet are the input embeddings of virtual prototype nodes obtained
via the same pressage-passing process as real nodes. The aggregation weights ČM indicate the desired semantic neighborhoods of nodes, i.e., the desired class proportion of neighbors according to the class probability of central nodes. Using soft logits rather than one-hot pseudo labels preserves the real characteristics of nodes and reduces the impact of wrong predictions.
Given the diverse conditions of nodes, we apply adaptive weighted addition to combine these messages. Meanwhile, messages of multiple layers are concatenated to preserve information from different localities within the graph. The overall CM-aware message passing is described as follows:
z' diag(Olego (olgg) Z + diag(aaran YZ.... (aag((ampp))) Z
Z
|| z 1=0
(15)
where diag(algo)) (wag( diag(( E Nx1 are the learnable combination weights, || denotes the concatenation operation, Z is the final node embeddings. The input embedding of the first layer Z XW" where W Rdy xd, and d, is the dimension of node emebddings. practice, we use ReLU as the activation function between layers. Note that use the prediction of the model C to estimate CM in the above process. It is initialized as a uniform distribution on each class and replaced by the output of CMGNN via a classifier CLA during the learning process:
xd,
Č = CLA(Z).
(16)
Objective Function. As mentioned in See enhancing the discriminability of CM is beneficial for learning better node embeddings. Thus, we introduce an additional discrimination loss Ldia to reduce the similarity of the desired neighborhood message among different classes, which simultaneously enhances the discriminability of CM and node embeddings. Experimental analysis in Section 5.4 demonstrates the effectiveness of this constraint enhance the CM. The overall loss consists of CrossEntropy loss Lee and the discrimination loss Laisi
L= Loo (2, Y) ALdiny Litt
Σ Sim(M,Zpar. Zpiss 144
(17)
where Sim(.) denotes the cosine similarity, Zpts E R xxd, is the embeddings of virtual prototype nodes. More details of CMGNN including pseudo-code are available in Appendix E
5 Experiments
5.1 Experimental Settings
As reported in Platonov et al. (26]. some widely adopted datasets in existing works have critical drawbacks, leading to unreliable comparisons. Therefore, with comprehensive review of existing benchmark evaluations, we construct a new collection of datasets and unified codebase to fairly perform experimental evaluation. Specifically, we integrate 20 representative homophilic and het- erophilic GNNs, construct unified codebase, and evaluate their node classification performances on 13 datasets with various scales and heterophily levels.
7

---

Table 2: Node classification accuracy comparison (%). The error bar (#) denotes the standard deviation of results over 10 runs. The best and second-best results in each column are highlighted in bold font and underlined. OOM denotes oft-of-memory error during training.
Dutaave
Romun-Baae Emppre
Amazun-Ratings
Chumeleun-F
Squirreb-F
Actor
Flickr
BlugCatalog
Pubmed
Rank
0.05
0.25
0.22
0.8
24,492 186,10
2.323
19.717
Edges
68,854
18,584
66.718
30,019
479,476
483
88.651
Clases
18
5
5
MLP
62.29 g 1.03
42.66 & 0.81
38,66 a 1,02
36.74
1.80
36.70
a 0.85
89.82
a 0.663
93.57
0.55
87,48 0:16
15.6
OKN
5x 2:35
45.00 0.55
42.12 3.82
37. 20
2.40
50.09
0.74
68 33
2,82
78.07
1.17
87.66
0:42
16.3
GAT
59.55 1.45
47.72 0.73
40.89
3.50
38.
1.71
30.94
0.95
57.33 23
1.004
88.30
1.37
87.45 4 0.53
15.6
GrapSSGGE
1,40
45 0.54
1.71
1.40 37.51
0.58
88 0.56
9.0
10.9
GCNU
82.53 0.37
47.53 0.72
4.15
40.70
21.64
0.67
89.96 0.43
HXGNN
68.61 1.05
37.20 0.67
42.29
4.57
35.82
2.20
53.32
0.990
91 25 0.58
96.34 00.30
0.37
12.6
Mixllop
79:06 0.61
47.41 & 1.00
$4,97 4 3.12
10.43
1.40
36.99 4 0.88
91.10 1 0.16
96 95.23 2 0.42
89
0.35
6.6
GBK-GNN
06.04 = 144
4018 = 1.94
41:23 + 4.57
36.29
1.37
55.91
0.84
ODM
G0M
88.
14 0.43
16.5
CGCN
00M
00M
41:23
4.08
36 16.7611
2.19
35.68
84 0.65
95.58 a 0.49
89.04 0.40
15.4
0.59
5.95
90:47
89.60
HOGGCN
00M
00M
38
13.1
GPR-GNN
01.10=000 0.66
4687 0.60
42.85
3.48
37.66
1008
36.16
1.02
91. 20.20:3 0.46
96.29 2
89.26 0.37
8.5
ACM-GGN
0.23
50.64 0.61
45.20
0.14
40.90
1.74
35.99
1.44
0
96
96.1620.57
89.94 0.335
6.0
OnleneGGNN
0.71
0.166
31.514..1 4.15
36.95
2.4
37.07
0.95
91.43 0.778
96
2
00.011::..3
6.1
M2MGNN
$3.97 0.77
5093 0.45
40.39 4 3.68
36.36
3.06
35.92
1 0.76
91. 0.76
96.31
89.91 1 0.35
8.8
X
S0.42 & 1.30
49.94 0.86
42/46 a 4.37
10.92
1 2.25
35.51
4 1.20
90.85
0.788
96.22 0.63
88.53 1 0.50
8.5
CLP
67.36 0.62
41.42 2
4.823
31.64
1.37
35.67 4 1.64
90. 13 0.67
94.45 0.59
88.88 à 0:42
11.8
EPEGNN
43.05
3.91
40:47
1:77
87 07.00
59.55
46.65 0.7
41,45 0.84
37.24
2.09
33.37
1.02
50.16
1.35
81.90
87.96 0.40
15.6
CMGNN
84.35 1,27
45.70 4,92
41.89 2.34
56.83
92.66 0.46
97.00 = 0.52
89.99 0.32
1.5
Table 3: Node classification accuracy (%) and time cost (minutes) comparison on large-scale graphs.
Dataset
Peun94
Twitch- Gamer
Genius
Pokec
Snap Putents
Avg. Bank
Homm.
0.47
0.55
0.62
0.45
0:07
Nodes
41,554
168.114 114 6,797.557 2
431 961
1,632.033
2,923
Edges
1,362 2
984,979
30,622.564
13,975,788
Classes
2
2
Method
Accuracy
Cost
Accuracy
|
Cost
Accurncy
|
Cost
Accuracy
| Cost
Accuracy
Cost
MLP
74.71 a 0.40
|
1
61.25 1 0.19
1.5
82.54 a 0.14 |
0.8
62.27 a 0.08 |
48
31.50 1 0.06
14
13.8
GCN
78.48 1
2.7
61.30
a 0.10
2.6
81.05 a 0.12
1.6
70.17 a 0.10
75
37.91
1 0.05
35
9.1
77.94
0.20
0.25
0.18
8.8
GraphSAGE
14
134
1..12
125
APINP
0.335
4.5
60:28
= 0.25
5.4
82.81
= 0.29
4.7
62.01
14
32.64
57
GCNI
79.97
0.40
14
64.97
a 0.40
221
86.45
0.19
89
77.75
1.17
343
42.24
x 0.68
495
3,4
MisHepp
76.74 1
8
62. 25
a 0.17
52
83.49
0.27
10
76.97
0.27
305
36.94 0.17
152
8.6
GloGNN
$2.29 2 0.62
65.
74
0.20
163
84.34 = 0.15
9.5
78.61
= 0.79
263
34,27
6 5.228
165
4.0
GPR GNN
82.50 e 0.32
61
03
m 0.38
8
82.80
m 0.64
4.4
75:45
= 0.00
54
32,87
0.10
30
9.2
ACM-GCN
$0.67 + 0.49
12
61.87
= 0.71
80.63
= 0.53
4.9
14.00
= 0.46
293
37.53
= 0.22
378
10.2
OklersiCNNN
70.400
0.86
0.32
66
84
0.75
31
75.79
0.20
2A5
39.56
0.34--0.33
385
5.4
M2MGNN
$1.96 0.24
74
00M
84.43
0.13
OOM
N²
$0.69 0.44
35
65.76 a 0.19
294
84.08
a 1,40
538
0OM
00M
8.8
74
0.5
+
1.7
0.10
20
0.58
61.19 a
a 0.80
=
CPGNN
78
14
0.25
80.70
3.9
75.80
123
37,09
0.09
137
9.8
CMGNN
83.01 0.48
17
65.18
247
85.19 0.55
20
81.42
0.55
376
$9.86
0.61
69
1.6
Newly Organized Datasets. The newly organized datasets include (i) small-scale: Roman-Empire, Amazon-Ratinge Chameleon-F, Squirrel-F, Actor, Flickr, BlogCatalog and Pubmed; (ii) large-scale: Penn94, Switch-Gamen Genius, Pokec and Snap-Patents. Their statistics are summarized in Table 2 and Table 3 For consistency with existing methods, we randomly construct 10 splits with predefined proportions (48% / 32% / 20% for training/ / validation / test) for each dataset and report the mean accuracy and standard deviation of 10 splits.
Baseline Methods. For baseline methods, we choose 20 representative homophilic and heterophilic
GNNs, including (i) shallow base model: MLP: (ii) homophilic GNNs: GCN M. GAT [77. Graph-
SAGE (88) APPNP (29]. GCNII (30); (iii) heterophilic GNNs: H2GCN [6). MixHop [0], GBK-
GNN 3 GGCN (32), GloGNN 22
HOGGCN 333 GPR-GNN 23 ACM-GCN [12] Or-
deredGNN 13), M2MGNN 34 and 2
(35; (iv) compatibility matrix-based methods: CLP (25),
EPFGNN 24). CPGNN 77. For each method, we integrate its code inoo a unified codebase and search for parameters in the space suggested by the original papers. All methods share the same call interfaces, ensuring fair environment for comparison. More detailed descriptions about the drawbacks of previous datasets, newly organized datasets and other experimental settings can be found in Appendix F
5.2 Performance Comparison
We evaluate the above methods and report their performances in Table 2 and Table 3
8

---

Table 4: Ablation study results (%) between CMGNN and five ablation variants, where CE denotes the confidence- based CM estimation, SM denotes supplementary messages from the sufficient neighborhoods and DL denotes the discrimination loss.
Variants
Romann- Empire
Squirrel-t'
Actor
Chameleon-F
Ammzon-Ratings
Pokec
Poun14
Genias
CMGNN
H4.35 1.27
41.89 2.34
36,82 0,78
45.70 4.92
52.13 0.55
81.42
0.55
83,01
9.48
85.19 a 0,53
WIO CE
83.88 141
2.43
36.77
1.22
44.75
0.38
82.58
850t
W/O SM
83.82 1.29
40.72 2.28
1.24
4.38
84.94 0.56
W/O DL
83.63
1.35
41.65 2.55
36.41
1: 1.08
11.92 4.12
52.05 a 0.57
80.28 a 0.49
81.34 4 1.83
84.87 0.75
W/O and DL
K3.77
1.38
39.80
1 2.36
36.32
1 1.05
64,58 3.28
51.74 0.55
79.26 0.34
81.20 0.6
84.53 1 0.59
W/O SM and DI.
83.48
1.89
40.19 2.69
35.66
1.42
41.01 3.09
51,49 + 1.02
77.57 x 0.44
80.71 0:48
84.28 + 0,50
Performance of Baselines. With the comprehensive benchmark, some interesting observations can be found. First, comparing MLP and homophilic GNNs we find that VMP can still work well in -atzonnRatings, Chameleon-F FF, and Squirrel-F, which meet the observations of previous works. Specifically, GCNII achieves an average rank of 4.9, which is even better than all HTGNNs. This may be attributed to the initial residual connection in GCNII, which enhances the practical Weighted-CNN in message passing. As for heterophilic GNNs, they generally achieve better results than VMPs (GCN, GAT), demonstrating the effectiveness of their various designs for heterophily. Notably, MixHop, as an early method, can also achieve quite good performance. The previous SOTA methods, OrderedGNN and ACM-GCN, prove their effectiveness again through good rankings.
Performance of CMGNN. CMGNN achieves the best performance in 6 small-scale datasets with an average rank of 1.5, outperforming all baseline methods. This demonstrates the superiority of leveraging CM and increasing CMD while alleviating the sparsity and noise issues. Regarding the suboptimal performance in Actor, we speculate that this is because its node attributes and CM are not discriminative enough provide valuable information via the supplementary messages, and are hard to enhance. On Pubmed, the raw identity-lik like CM is good enough, leading to minor contribution from supplement messages. Despite this, CMGNN still achieves top-level performance.
Comparision with CM-based Methods. Some existing methods also utilize the CM to redefine pairwise relations (e.g., edge weights) for nodes. However, they suffer from the issues of sparsity and noise, as their performances and average ranks have significant gaps compared with CMGNN. In contrast, CMGNN leverages CM and virtual neighbors to construct supplementary messages while preserving the original neighborhood distribution, leading to the following advantages: (i) Better robustness for low-quality pseudo labels; (ii) Unlock the effectiveness of CM for low-degree nodes; (iii) More accurate estimation of CM. More detailed analyses are listed in Appendix G.I
Performance on Large-Scale Graphs. To further evaluate the scalability of CMGNN, we also conduct experiments on five large-scale datasets. The performance and computational cost comparison listed in Table 3 Again, CMGNN achieves superior performance with the best average rank of 1.6, while GCNII follows behind with a rank of 3.4. Meanwhile, CMGNN strikes a good balance between performance and efficiency, especially in Snap-Patents with 17% significant improvements and less time cost, demonstrating great scalability in handling of large-scale graphs.
Performance on Homophilic and Heterophilic Graphs. We divide all datasets into two groups according to their edge homophily levels with a threshold of 0.5. CMGNN shows significant effectiveness on heterophilic graphs with an average rank of 1.3 and achieves the best on 9 of 10 datasets. 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 hetter 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.
5.3 Ablation Study
We conduct an ablation study on three key designs of CMGNN, including the confidence- based CM estimation (CE), supplementary messages from the virtual neighborhood (SM) and the discrimination loss (DL). The results are shown Table Firstly, all three components have indispensable contributions to CMGNN, as the absence of any part will degrade the performance. Meanwhile, the CE and DL have relatively small impacts while SM plays a more important role in most datasets. Further, we notice that CMGNN can reach smaller standard deviation compared with the variants

---

0.1
015
0.1
0:71
0.18
p00 1.25
075 570
015
0204
932
-3
022
9:08
0222 9.23
0.23
9.3
0.23
000 0.22
0.2
(a) Ama-O, 0.46 (b) Ama-W, 0.63 (c) Cha-O, 0.27 (d) Cha-W, 0.49 (e) Squ-O, 0.08
(f) Squ- W, 0.16
Figure 4: Visualizations of the original CM (O) and Weighted-CMs (W) on Amazon-Ratings (Ama), Chameleon-F (Cha), and Squirrel-F (Squ), along with the corresponding CMD values.
most of the time. This shows that CMGNN achieves more stable results by alleviating the sparsity and noise issues. As for the opposite result on Chameleon-F this may be attributed to its small size (890 nodes), which naturally leads to unstable results.
5.4 Case Study on the Estimated CMs and CMDs
To evaluate the effectiveness of CMGNN in increasing CMD, calculate the CMD of both original and Weighted-CNN CMs,, as illustrated in Figure The results demonstrate that CMGNN is capable of enhancing the CMD across graphs with varying homophily levels, thereby resulting in better node embeddings. Even for CM with tiny CMD on Squirrel-F, CMGNN can still maintain its effectiveness.
More experimental results can be found in Appendix G including more ablation studies, case studies on node degrees and low label rate settings, comprehensive complexity analysis, and runtime- performance tradeoff comparison.
6 Conclusion and Limitation
In this paper, we explore the underlying principle that explains the effectiveness of HTMP by investigating the connection between node discriminability and CM. We find that the effectiveness of many existing HTMP mechanisms may be credited to increasing the CMD. Inspired by this discovery, we propose CMGNN, a novel approach to enhance the CMD and node embeddings explicitly while alleviating the sparsity and noise issues. Experimental results show the effectiveness of CMGNN.
This work mainly focuses on the message-passing mechanism in existing HTGNNs under the semi- supervised setting. Thus, this paper does not analyze the other designs in HTGNNS, such as spectral- and graph-trame twttt-tttnnnnmmmmaee methods. Theoretical analyses and proofs are based on the CSBM-H with corresponding assumptions about node features, degrees and edges.
Acknowledgments and Disclosure of Funding
This work is supported by the National Natural Science Foundation of China (Grant No. 62476245), Zhejiang Provincial Natural Science Foundation of China (Grant No. LTGG23F030005).
References
[1] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[2] Yanfu Zhang, Hongchang Gao, Jian Pei, and Heng Huang. Robust self-supervised struc- tural graph neural network for social network prediction. Proceedings of the ACM Web Conference 2022, pages 1352-1361. 1361, 2022.
[3] Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. Neural graph collabo- rative filtering. In Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval, pages 165-174, 2019.
[4] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings
10

---

of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pages 639-648, 2020.
[5] Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-444, 2001.
[6] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In International Conference on Learning Representations, 2022.
[7] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI conference artificial intelligence, volume 35, pages 11168-11111 1116,, 2021.
[8] Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.07082, 2022.
[9] Jiong Zhu, Yujun Yan, Mark Heimann, Lingxiao Zhao, Leman Akoglu, and Danai Koutra. Heterophily and graph neural networks: Past, present and future. IEEE Data Engineering Bulletin, 2023.
[10] Sami Abu-El Ha-aja,, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pages 21-29. PMLR, 2019.
[11] Deyu Bo. Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low- frequency information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 3950-3957, 2021.
[12] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35:1362-1377 1375, 2022.
[13] Yunchong Song, Chenghu Zhou, Xinbing Wang, and Zhouhan Lin. Ordered GNN: Ordering message passing to deal with heterophily and over-smoothing In The Eleventh International Conference on Learning Representations, 2023.
[14] Junfu Wang, Yuanfang Guo, Liang Yang, and Yunhong Wang. Understanding heterophily for graph neural networks. In International Conference on Machine Learning, pages 50489-50529, PMI.R, 2024.
[15] Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao-War Chang. Jie Fu, Jure Leskovec, and Doina Precup. When do graph neural networks help with node classification? in- vestigating the homophily principle on node distinguishability. Advances Neural Information Processing Systems,
2023.
[16] Jiong Zhu, Yujun Yan. Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7800 2020.
[17] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geo- metric graph convolutional networks. In International Conference on Learning Representations, 2020.
[18] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
[19] Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems, 31, 2018.
[20] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. In International Conference on Machine Learning, pages 684-693 PMLR, 2021.
11

---

[21] Rongzhe Wei, Haoteng Yin, Junteng Jia, Austin R Benson, and Pan Li. Understanding non- linearity in graph neural networks from the bayesian-inferre inference perspective. Advances in Neural Information Processing Systems, 35:34024-34038 2022.
[22] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference Machine Learning, pages 13242-13256. PMLR, 2022.
[23] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. pagerank graph neural network. In International Conference on Learning Representations, 2021.
Adaptive universal generalized
[24] Yu Wang. Yuesong Shen, and Daniel Cremers. Explicit pairwise factorized graph neural network for semi-supervised node classification. In Uncertainty in Artificial Intelligence, pages 1979-1987. PMLR, 2021.
[25] Zhiqiang Zhong, Sergei Ivanov, and Jun Pang. Simplifying node classification on heterophilous graphs with compatible label propagation. Transactions on Machine Learning Research, 2022. ISSN 2835-8856.
[26] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we re- ally making progress? In The Eleventh International Conference Learning Representations, 2023.
[27] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In The International Conference on Learning Representations, 2018.
[28] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[29] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
[30] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pages 1735-1735. PMLR, 2020.
[31] Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. Ghk-gnn: Gated ki-kel graph neural networks for modeling both homophily and heterophily. In Proceedings of the ACM Web Conference 2022, pages 1550-1558, 2022.
[32] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), pages 1287-1292. IEEE, 2022.
[33] Tao Wang, Di Jin, Rui Wang, Dongxiao He, and Yuxiao Huang. Powerful graph convolutional networks with adaptive propagation mechanism for homophily and heterophily. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pages 4210-4218 2022.
[34] Langzhang Liang, Sunwoo Kim, Kijung Shin, Zenglin Xu, Shirui Pan, and Yuan Qi. Sign not remedy: Multiset-to-muule mulliiset message passing for learning on heterophilic graphs. In International Conference on Machine Learning, pages 29621-2229990 -96443. PMLR, 2024.
[35] Junshu Sun, Chenxue Yang, Xiangyang Ji, Qingming Huang, and Shuhui Wang. Towards dy- namic message passing on graphs. In Thirty-Fighth Annual Conference on Neural Information Processing Systems, 2024.
[36] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-24 2020.
12

---

[37] Hao Chen, Yuanchen Bei, Qijie Shen, Yue Xu, Sheng Zhou, Wenbing Huang, Feiran Huang, Senzhang Wang. and Xiao Huang. Macro graph neural networks for online billion-scale recommender systems. In Proceedings of the ACM on Web Conference 2024, pages 3598- 3608, 2024.
[38] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[39] Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. In International Conference on Learning Representations, 2018.
[40] Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view on graph neural networks as graph signal denoising. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 1202-1211, 2021.
[41] Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with optimization framework. In Proceedings of the Web Conference 2021, pages 1215-1226, 2021.
[42] Di Jin, Zhizhi Yu, Cuiying Huo, Rui Wang, Xiao Wang, Dongxiao He, and Jiawei Han. Universal graph convolutional networks. Advances in Neural Information Processing Systems, 14:14464-10664 2021.
[43] Wei Jin, Tyler Demr Yiqi Wang. Yao Ma, Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM international conference on web search and data mining, pages 1566 2021.
[44] Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns, In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1541-1551, 2021.
[45] Chenghua Gong, Yao Cheng, Jianxiang Yu, Can Xu, Caihua Shan, Siqiang Luo, and Xiang Li. A survey on learning from graphs with heterophily: Recent advances and future directions. arXiv preprint arXiv:2401.0970 2024.
[46] Sitao Luan, Mingde Zhao, Chenqing Hua, Xiao-Wen Chang, and Doina Precup. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. arXiv preprint arXiv:2008 200.:20000.088444, 2020.
[47] Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. Anomaly detection on attributed networks via contrastive self-supervised learning. IEEE Transactions on Neural Networks and Learning Systems, 2021.
[48] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. AI magazine, 29(3):93 93, 2008
[49] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 14:20887-20902. 2021.
[50] Édouard Grave, Piotr Bojanowski, Prakhar Gupta, Armand Joulin, and Tomá's Mikolov. Learning word vectors for 157 languages. In Proceedings of the Eleventh International Conference Language Resources and Evaluation (LREC 2018), 2018.
[51] Leskovec Jure. Snap datasets: Stanford large network dataset collection. Retrieved December 2021 from http://snap. stanford. edu/data, 2014.
[52] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cn4, 2021.
13

---

[53] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 807-816, 2009.
[54] Amanda L Traud, Peter J Mucha, and Mason A Porter. Social structure of facebook networks. Physica A: Statistical Mechanics and Applications, 391(16):41554115 2012.
[55] Benedek Rozemberczki and Rik Sarkar. Twitch gamers: dataset for evaluating proximity preserving and structural role-based node embeddings. arXiv preprint 1rXIv:2101.03091 2021.
[56] Derek Lim and Austin R Benson. Expertise and dynamics within crowdsourced musical knowledge curation: A case study of the genius platform. In Proceedings of the International
AAAI Conference Web and Social Media, volume 15, pages 373-384, 2021.
[57] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.sttart stanford..doodd..ooooom wwd.ooodd.duddaeeee. data, June 2014.
[58] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 177-187, 2005.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The contributions and scope of this paper are included in the abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this work are listed in the Seo
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 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 few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
14

---

The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails 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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. 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]
Justification:
We provide the formalization proof of Theorem 3.2 in Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The details of the method and experimental settings are provided in Section and Appendix E
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
15

---

While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c)
If the contribution is new model (e.g., . a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
The data and code are available in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public/guidest Saglli/cuuiaas//ddeeuuuiisssssss poooeesubmissiooooliieeo
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The detailed experimental settings are provided in Section 5 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
16

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report the average accuracy and the standard deviation as the performance in experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 96% CI, if the hypothesis of Normality 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 out of range (e.g. negative етror 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.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We list the hardware and software resources along with the space and space complexity and run time in Appendix F andd G
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, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well 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 into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in this paper conforms, in every respect, with the NeurlPS Code of Ethics.
17

---

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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction)
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The potential positive societal impacts are provided in See while the potential negative societal impacts are meaningless since this work is foundational research.
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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses no such risk. The datasets used are all publicly available online.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 best faith effort.
18

---

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 the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The datasets and codes of baseline methods are publicly available online. We cite the original paper and mark the URL in both papers and the 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 dataset.
The authors should state which version of the asset is used and, if possible, include 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.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi wwwode....d..... com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
We provide public codebase along with an illustrative README file.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
19

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this paper does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hbtppp///oorrgsccc////ffrrrrer/p for what should or should not be described.
20

---

A Related Works
Homophilic Graph Neural Networks. Graph Neural Networks (GNNs) have showcased impressive capabilittes in handling graph-structured data 36 37.. Traditional GNNs are predominantly founded on the assumption of homophily, broadly categorized into two classes: spectral-bast baasd GNNs and spatial-based GNNs. Firstly, spectral- -based GNNs acquire node representations through graph convolution operations employing diverse graph filters [8 39] Secondly, spatial-based methods gather information from neighbors and update the representation of central nodes through the Moreover, for more comprehensive understanding of existing homophilic GNNs, several unified frameworks [40 41 have been proposed. Ma et al. [40] propose that the aggregation process in some representative homophilic GNNs can be regarded as solving graph denoising problem with a smoothness assumption. Zhu et al. [T 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 heterophilic neighbors dominate [1 [6].
message-passing mechanism [27 29
Heterophilic Graph Neural Networks, Recently, some heterophilic GNNs have emerged to tackle
the heterophily problem [00
34 Firstly, commonly adopted strategy involves expanding the neighborhood with higher homophily or richer messages,
33
16
42
43
17
22
23
44
32
35
such as high order neighborhooods [16]
42], ceature-similarity-baarr -baed neighborhoods 42] 43 and
custom-defin defined neighborhoods [17] 44]. Secondly, some approaches [I] 12 [2 32) aim to lever- age information from heterophilic neighbors, considering that not all heterophily is detrimental [6]. Thirdly, some methods [16] 10 23 [3] adapt to heterophily by extending the combine function in message passing, creating variations for addition and concatenation.
Reviewing Heterophilic Graph Neural Networks. Heterophilic GNNs have attracted more and more research attention. Some surveys have provided a macroscopic view for reviewing heterophilic GNNs, categorizing heterophilic GNNs with shallow analysis. Specifically, Zheng et al. S categorizes the designs of heterophilic GNNs into non-local neighbor extensions and GNN architecture refinement. Zhu et al. [9] examines the impact of heterophilic graph characteristics on GNNs. For categorizations, it simply lists some effective designs in heterophilic GNNs. Gong al. graph learning, where message passing is only a minor aspect of its taxonomy with a broader view.
45 reviews heterophilic
The Connection Between Message Passing and Heterophily. Recently, some efforts 6 6 15
46 have begun to investigate the connection between message passing and heterophily. Zhu et al. 9 highlighted that node degrees and compatibility matrices key factors for message passing under heterophily. In ACM [12). the authors found that the performance curves of the VMP mechanism under different levels of homophily are U-shaped. Similarly, Ma et al. (6) proposed the existence of special case of heterophily, named "good" heterophily, where the homophily ratios remain low, but the VMP mechanism can achieve strong performance. Luan et al. (15) shows that the low-pass filter works better at very low and very high homophily intervals, while the high-past pass filter works better at the low to medium homophily interval. However, these works are limited in studying what kind of data is suitable for the message-passing mechanism, lacking a model perspeepeeee understanding of heterophilic message passing.
B Proof of Theorem 3.2
To prove Theorem 3.2 we first calculate the CMD(McsBMH)) and ENKL(H respectively. According to the definitions in CSBM-H, the corresponding compatibility matrix is as follows:
h.
1 h
McSBM-1 =
(18)
1
h
Thus, the corresponding CMD can be calculated by
Eq
CMD(McSBM+H) 2(h (1 h) +
h))
2/2h - 1 4/h //1
1
(19)
2
On the other hand, the original X and LP features HIP Ax are as follows:
i E 2; N(p, II;;; R.P N(Po, OgD, j E Cr, ~ N(H, II; h N(P,, TTD),
(20)
21

---

where iho h(pp - M1) + M1. 11 h(p Mo) + Mo. og
M(az-a3)) do
09
B[oj -
d
Considering the formula of ENKL Eq
we first calculate dig..
xx de
l|440 - M
HI
l1ã4 - 11112
|1 11) + 14 - (h(H) 12) + +b)
(21)
|1 - (M0 14)
(2h 1)2d
In CSBM-H, FA = 2, we further assume do = d1 = d, that is, ignoring the influence of node degrees.
Now we have o M(o - --))=
and o h(o] az) +06
d
The ENKL of LP feature is as follows:
ENKL(H')) diuel
0
of
2)
407
40
0
%
d
= =1 (2h 1)2
4[h(o} d + 56
4
1 h(o oi) + 0î
Moi o + t
2 h(op of) o
hoj of) o
(o + o
= 1- - (2h - 1)²
4
1 2(0) σं) ot
2 (oh
( o/
o h h
= 1 + &x d
[o - 2/2 (0) 2 o
c 212 (o) of 1000 001
G of ) (a - o.o
& d(oó + +of
n22 h
h22 h h
2( )
5 to
(22)
11
(o) )1
of
oo
h² - h
h2
[o -
[0g -0
1 doo
a aot
& d(o + of)
[0 of
2 12
[0ā of 1
(oū o1)
(h- 1/2 1 [0 7
(h - 1/4
1
[0] 0
+ 2 d(a) + +oi)
(d) 07)²
& d(o) + of)
-
2 -
(0) o
(h-
1
(h 1
1(16- 1
4l0 17
B d( + oi)
-2
(o) 0
(0)) alo
& d(o + o
- oz
+2
+1
(o) - o7
1)²
+
4(o3
Since Po, 14, og of and d are fixed parameters in CSBM-H when only considering the change of homophily hi we simplify the above formulation by new variables a, b.
dx d(ož + of)
2 E [2. +00),
a
(0) o72
(23)
(o + 0
1
E 1 +00).
4 ot)²
22

---

Fight Miphiig
003
(a) Highh, Easy
(b) Midh, Easy
(c) Lowh, Easy
43
021
D4Y 027
221
(d) Highh, Hard
(e) Midh, Hard
(1) Lowh, Hard
Figure 5: The visualization of the compatibility matrix synthetic graphs.
Thus, the ENKL can be represented as follows:
b ENKL(H! (h )
(24)
---2)
Furthermore, let t = 1/- 1 E [0, 1 since h E [0, the CMD and ENKL can be represented as follows:
CMD(McsEM=H) = 4f,
ab
(25)
+ a. ENKL t2 b
To simplify the computation, we analyze monotonicity with the aid of derivatives.
dCMD = - 0,
dt
(26)
dENKL
-2abt (t2 6)2 - 0.
dt
That means CMD increases monotonically with t, while ENKL decreases monotonically with t. Thus, the covariance between CMD and ENKL is negative: Cov(CMD(MccsevH)) ENKL(H!)) < 0.
C The Experiments on Synthetic Datasets
To explore the performance impact of homophily level, node degrees, and compatibility matrix (CMs) on simple GNNs, we conduct some experiments on synthetic datasets.
C.1 Synthetic Datasets
We construct synthetic graphs considering the factors of homophily, CMs, and degrees. For homophily, we set 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 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 5 Since there is no
23

---

Table 5: Node classification accuracy of GCN on synthetic datasets.
Factors
Highh, Easy
Highh, Hard
Midh, Easy
Midh, Hard
Lowh, Easy
Lowh, Hard
Highd
99.15 0.35
99.48 + 0.24
86.42 = 4.13
90.52 1.05
89.34 2.19
39.22 # 2.34
Lowd
89.98 1.59
91.25 a 0.85
70.85 # 1.59
70.20 1.41
56.46 2.63
40.91 # 1.75
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.
C.2 Experiments Synthetic Datasets
We use GCN to analyze the performance impact of the above factors. The semi-supervised node classification performance of GCN is shown in Table [5] while the baseline performance of MLP (72.54 + 2.18) is the same among these datasets since their difference is only on edges. From these results, have some observations: (1) High homophily is necessary; GCN also work well on low homophily but discriminative CM; (2) Low degrees have a negative impact on performance, especially when the CMs are relatively less discriminative. This also indicates that nodes with lower degrees are more likely to have confused semantic neighborhoods; (3) When handling nodes with confused semantic neighborhoods, GCN may contaminate central nodes with their neighborhoods' messages, which leads to worse performance than MLP. This once again reminds us of the importance of enhancing the CM diseriminability.
D The Posterior Evaluation about the Weighted-CMM and CMD in HTGNNs
In this part, we give the details of the empirical posterior evaluation on GloGNN 22 GPR-GNN 23 and ACM-GCN 12
GloGNN, GloGNN learns a global pair-wise coefficient matrix and utilizes it as the aggregation weights during message passing. Thus, directly calculate this matrix the practical aggregate weights matrix gloo Z, then regard Á the neighborhood and calculate the Weighted-CM and its corresponding CMD.
ACM-GCN. ACM-GCN merges messages from various filters using adaptive weights, effectively altering edge weights to construct the Weight-CM with optional negative elements due to the high-pass filter. Thus, we leverage the learned weights to rebuild a practical aggregate weights matrix Á acm based on the low-pass filter Å and high-pass filter I Å, then regard Á acm as the neighborhood and calculate the Weighted- CM and its corresponding CMD.
GPRGNN. GPR-GNN integrates the CMs of multiple-order neighborhoods with adaptive weights to form a more discriminative Weighted-CM, Thus, utilize the learned weights to rebuild a practical
aggregate weights matrix À aPr based the multi-hop adjacency matrices [I. A. A .... A+ then regard Á the neighborhood and calculate the Weighted-CM and its corresponding CMD.
The visualization of Weighted-CNN and corresponding CMD on various datasets can seen in Figure 6
E
Additional Detailed Implementation of CMGNN
Considering the influence of node degree in compatibility matrix estimation. As mentioned in Section 3, the semantic neighborhood of low-degree nodes may display inconsistencies with CM. Thus, nodes with low degrees deserve low weights during the CM estimation. We manually set up weighting function range in [0, 1]:
d,/2K, 0.25
d, S K, K < d. <3, otherwise.
di /KK, 1,
(27)
24

---

10
0:4.5
0.35
0.14
0.04
0.02
0.52
0.30
0:12
0.04
0.
0.51
0.28
0.14
0.04
0.02
0.36
0.03
0.50
0.04
0.08
0.03
0.10
0.00
0.16
0.37
0.30
0.12
0.04
0.15
0.31
0.38
0.32
0.44
0.15
0.30
0.40
0.10
0.04
8-10.6
0.45
0.46
0.18
0.08
-0122
0.32
0.18
0:21
0.11
0:33
0.25
0.29
0.07
0.01
0:33
0.06
0.14
0.26
0.20
0.19
0.13
0.14
0.23
0.25
0:21
0.
0.35
0.22
0.23
0.13
0.26
0.38
0.03
0.36
0.32
0.03
Ama-O, 0.46
(b) Ama-Glo, 0.59
Ama-GPR, 0.62
(d) Ama-ACM, 0.97
(c) Rom-O, 0.85
(f) Rom-Glo, 7.15
Rom-GPR, 1.16
(h) Rom-ACM, 0.87
0.24
0.21 0.10
0.13
0.25
0.51
0.17 0.15
0.04 0:13
01
03 0.16 9.05 -0.14
0.27
0.25
0.14
0.09
0.25
80
-41
-.0.33
0.16
0.23
0.17
0.20
0.28
0.32
0.21
0.07
0.11
26 0.17
0.23
0.18 0.16
0.27
0.18
0.23
0.15
0.17
0.27
0.23
0.27
0.16
0:27
0:29
0.22 0.19
0.13
0.29
64
44
64
0.09 0.11
0.27 0.23
0.30
0.06
0.05
0:24
0:35
0:30
03 0.22
0.27
0:23
0.26
0.12
0.11
0.19
0.25
0.32
0:25
0:57
.00
-03
1
22
3
(i) Cha-O, 0.27
(i) Cha-Chaa Glo, 0.87
(k) Cha G.aa-GRR.O 0.80
(I) CCa-ACM, 0.43
0.16 0.18
0.09 0:11
0.24 0.22
0.17
0.32
66
-03
00
0.21 0.20 0.19 0.20 0.21
0.33
0.30
0.12 0.12
0:13
0.24 0. 0.16
0.22 0.22
0.19 0.20 0.19
0.17
0.25
104
-0a
- 20 0.21 0.20 0.20 0.20
~-0
0.15
0:15
0.16
0:31
24
n-0 23
05 0.17 0.22 0.23
0.20.29 0.29 0.05
.0.12
0.58
0.77
0.19 0.19
0.13
0:36
0.60
0.19
0.21
0.02
(m) Squ-O, 0.08
(n) Squ-Glo, 0.81
(0) Squ-GPR, 0.10
(p) Squ-ACM, 0.94
Figure 6: Visualizations of Weighted and CMD of GloGNN, GPR-GNN, and ACM-GCN on various datasets.
For low-degree nodes, increases in degree should yield more significant benefits compared to high- degree nodes. Beyond a certain threshold, increases degree yield tiny benefits. We have empirically chosen K and 3K as fixed thresholds for the weighting function to simplify the design without multiple attempts. This approach is straightforward and can be substituted with other forms that meet the same criteria. In practice, the compatibility matrix is estimated considering the various node degrees:
M = Norm(( .g (C))))
(28)
The utilization of additional structural features. In line with existing methods [2] we treat the topology structure additional node features. These features, shown as the adjacency matrix A, depict node connections. Each row A; can be viewed as an extra N-dimensional feature of node i. Thus, the input representation of the first layer can be obtained in two ways:
Z XXW*X Á W' or Z XWO
(29)
Specifically, (i) using additional features, where W Rdy W Nxd, and We R 222,xd, xd, are learnable matrices; (ii) using only attribute features, where w E Rd, where d, is the dimension of node embeddings.
Message COMBNIE with Adaptive Weights. The aggregated messages from node ego, raw, and supplementary neighborhoods are Zegoo Zyam and Zuup respectively. The combination weights
25

---

Algorithm Algorithm of CMGNN
Require: Graph 9 (V,E, X, A, Y), loss weight epoch E
Ensure:
Predicted labels Y
1: Initialize the soft predicted labels C' with other elements ..
2: Construct class prototypes as additional virtual neighbors for all nodes via Eq
3: for iteration 1, 2, .... E do
4: Obtain the input representations for the first layer via Eq
5: Estimate the compatibility matrix via Eq 10 [ 27 and Eq 28
6:
Obtain the output representations through the CM-aware message-pastiee mechanism via
[3 [4] and [5]
7:
Obtain the predicted logits (soft label) Č via 1 16
8:
Calculate loss L via 17
9:
Back- pack-propagation L to optimize the weights of networks. if the performance in the validation set improved then
10:
11:
update the compatibility matrix with current soft predicted label C. end if
13:
end for
Obtain the predicted labels Y via Y Softmax C)).
15:
output Y
learned by MLP with Softmax:
[e Srows o dsupl Softmax(Sigmoi(((4. //aw [Z
||
W att W
mix);
(30)
where W att E +13,,+1xx3 and W miz E 3 are two learnable weight matrixes, d is the node degrees which may be helpful to weights learning.
The Message Passing of Class Prototypes. Specifically, the virtual prototype nodes are viewed as additional nodes, which have the same message-pasee passsing mechanism as real nodes:
l p diag(a / yZ W
ego + diag(oratd ptt. A ptt zut..
raw
+ dit I
sup ] sut @ Butt, y I W!
supt
(31)
Zott.l
where A sup.ptt
=1 E Rx and B puup.ptt Čztt M are similar with those of real nodes.
F More Details about the Experimental Settings
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 newly organized datasets; (iii) baseline methods and the codebase; (iv) details of obtaining benchmark performance; and (v) detailed experimental settings of CMGNN.
F. Drawbacks in Existing Datasets
Existing works mostly follow the settings and datasets used in Pei et al. [17], including 6 heterophilic datasets (Cornell, Texas, Wisconsin, Actor, Chameleon, and Squirrel) and 3 homophilic datasets (Cora, Citeseer, and Pubmed). Platonov et al. 26 pointed out serious data leakages in Chameleon and Squirrel, while Cornell, Texas, and Wisconsin are too small with very imbalanced classes. Further, we revisit other datasets and discover new drawbacks: (i) In the ten splits of Citeseer, there are two inconsistent ones, which have smaller training, validation. and test sets that could cause issues with statistical results; (ii) Cora's 's data split ratios are inconsistent with the expected ones. These drawbacks may lead to certain issues in the conclusions of previous works.
Therefore, build comprehensive and fair benchmark for model effectiveness evaluation, we newly organize 13 datasets with unified splitting across various homophily values and scales.
26

---

F.2 Newly Organized Datasets
In our benchmark, we adopt ten different types of publicly available datasets with unified splitting setting (48%/32%/20%% for
for fair model comparison, including Roman- Empire (26), Amazon-Ratings (26). Chameleon-F [26). Squirrel-F (2). Actor [7]] Flickr (47).
BlogCatalog 477. Pubmed [48, Penn94 [49]. Twitch-Gamer [4). Genius [9], Pokec [49 and
Snap-Patents 49 The datasets have 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:
Table 6: Statistics and splitting of the experimental benchmark datasets.
Nodes
Edges
Attributes
Classes
Arg. Degree
Undirested
Homophily
Train Valid
Rommn-Eimpir
22,662
65,854
300
2.9
0.05
10,877 /7.251 10,877/7.251 /4,534
Amszon-Ratings
24,492
186,
0.38
11,756 7.837 /4,99
Chameloon-F
890
13,584
2.325
15.3
X
0.25
427 / 284/ 179
Squirel. F
2,223
65,718
2,089
29.6
X
0.22
1,067 711 4445
Actor
7,600
30,019
932
3.9
X
0.22
3,648 / 2,432 1,520
7,575
479,476
12,047
0.24
3,636 2,442/ 1,515
BlogCatalog
343,486
2,494 1,662
Pubmed
19,717
88,651
500
4.5
0.80
9,463 6,510/ 3,944
Pena94
41,554
1,362,229
5
65.6
0.47
19:945 13,297/ 8,312
Twitch- Gamer
168,114
6,797,557
40.4
X
0.55
80,694 53,796 33,624
421,961
984.979
X
0.62
202,541 135,022 (35,027 84,393
Pakes
1,632,803
30,622,564
65
18.8
X
0.45
783.667
522,444/ 326,529
Snap- Patents
2,923,922
13,975,788
260
4.8
X
0.07
1,403,482/ 935,655 58447885
Roman-Empire (26) is derived from the extensive article 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 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 's dependency tree, indicating a grammatical relationship where one word is syntactically dependent the other. Consequently, the graph is structured as a chain graph, enriched with additional edges that represent these syntactic dependencies. It encompasses total of 18 distinct node classes, with each node being equipped with 300-dimensional attributes obtained by fastText word embeddings [50].
individual
Amazon- Amazon-Rating 26 is sourced from the Amazon product co co-purchasing network metadata dataset [51]. 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 often purchased together. The objective 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 [50), extracted from the textual descriptions of the products.
x [26] are specialized collections of Wikipedia page-to-page net- works (52), of which the data leakage nodes are filtered out by Platonov et al. [26]. 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 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-dimensions features. Squirrel-F contains 2,223 nodes and 65,718 edges between nodes, with each node being equipped with a 1..889-dimension feature vector.
Chameleon-F and Squirrel-r"
3 17 is an actor-centric induced subgraph derived from the broader olm-director-actor wrrttr network, as originally presented by Tang et al. [53]. 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
27

---

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 Blogeatalog" 47 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 relations 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 objective to predict the interest group of each user. Specifically, Flickr contains 7.575 nodes and 479,476 edges between nodes. The graph encompasses 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 total of 6 distinct node classes, with each node being equipped with 189-diimnsioonal attributes.
Pubmed 1 44,338 links between them. The text contents of each publication are treated as its node attributes, and thus each node is assigned 500-dimensional attribute vector. The target to predict which of the paper categories each node belongs to, with total of 3 candidate classes.
48 is classical citation network consisting of 19,717 scientific publications with
P 49 is a friendship network derived from the Facebook 100 networks, featuring university students from 2005 [54]. In this network, each node represents a student and labeled with the user's 's reported gender. The node features include major, second major or minor, dorm or house, year, and high school.
Twitch-Gamer [49 is subgraph from the streaming platform Twitch, with nodes representing users and edges connecting mutual followers [55]. Node features encompass the number of views, creation and update dates, language, lifetime, and account status. The task is to predict whether a channel contains explicit content.
is a subnetwork extracted from genius.com, a website for crowdsourced annotations of song lyries [56). In this graph, nodes represent users, and edges connect users who follow each other. User features include expertise scores, contribution counts, roles, and more. Some users are labeled as "gone", indicating higher likelihood of being spam accounts. Our goal is to predict whether a user is marked as "gone".
Genius
c 49
Poked 6 49 is a friendship graph from a Slovak online social network, with nodes representing
and edges indicating directed friendship relations [57]. Node features derived from profile information, such as geographical region, registration time, and age. The task is to classify users based on their gender.
Snap-Patent
5 49 is a U.S. patent network, where nodes correspond to patents and edges denote citation relationships [58]. Node features are derived from patent metadata. The task to classify patents into five categories based on the time of their grant.
F,3 Baseline Methods and the Codebase
For comprehensive comparisons, we choose 20 representative baseline methods as in the benchmark, which can be categorized into four main groups of works as follows:
(i) Shallow Model: MLP;
(ii) Homopihlous Graph Neural Networks: GCN 1, GAT 27). GraphSAGE 28
APPNP 29
and GCNII 30;;
(iii) Heterophilous Graph Neural Networks: H2GCN 16), MixHop
10
GBK-GNN OrderedGNN
GGCN 32) GloGNN (22), HOGGCN 33 GPR-GNN 23 ACM-GCN
12
13
M2MGNN 455 and N (4];
(iv) Compatibility Matrix-based Models: CLP
25 EPFGNN 24), and CPGNN 7
28

---

To explore the performance of baseline methods on newly organized datasets and facilitate future expansions, we collect the official/reprodueed 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 widely used Py PyTorch framework, supporting both DGI 8 and Pyce Detailed usage of the codebase is available in the Readme file of the codebase.
F,4 Details of Obtaining Benchmark Performance
Following the settings in existing methods, construct 10 random splits (48%/32%/200 /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 the NNI framework with an annealing strategy. We use Adam the optimizer for all methods. Each method has dozens of search trails according to their time costs, and the best performances reported. The currently known optimal parameters of each method are listed in the codebase. We run these experiments on NVIDIA GeForce RTX 3090 GPUs with 24G memory. The mem-oy- error during model training is reported as OOM in Table 2 and 3
F.5 Detailed Experimental Settings of CMGNN
CMGNN has the same experimental settings within the benchmark, including datasets, splits, evalua- tions, hardware, optimizer, and so on.
Parameters Search Space. We list the search space of parameters in Table 7 where patience is for the maximum epoch early stopping, n hidden the embedding dimension of hidden layers as well as the representation dimension d,,, relu_reriioe varient decides ReLU applying before message aggregation or not as in Luan al. [12, structure info determines whether use structure information as supplement node features or not.
Table 7: Parameter search space of our method.
Parameters
Range
learning rate weight_ decay
(0.001, 0.005, 0.01, 0.05) (0, 1e-7, 5e-7, 1e-6, 5e-6, 5e-5, 5e-4) {200, 400}
patience
dropout
[0, 0.9] {0, 0.01, 0.1, 1, 10) [1, 2, 8) {32, 64, 128, 256} (True, False)
layers
n ni_hidden
relu_variaa variant
structure_ing info
(True, False]
G More Details about Experiments
In this section, we show some additional experimental results and analyses.
G.1 Detailed Analysis about the comparison between CMGNN and existing CM-based methods
Specifically, CMGNN achieves better performance and benefits from the approach of utilizing CM in the following aspects: (i) Better robustness for low-quality pseudo labels: Existing CM-based
methods utilize CM to guide the weights of propagation, which can lead to error accumulation with
httts://pytorre org
httpa:// http::/wwwwwlll...m dgl.ai
https://www http:/wwwpppppppp/////t..pt.. org
29

---

Table &: Ablation study results (%) on the effects of additional structural features, where True denotes CMGNN with additional structural features and False denotes CMGNN with only node features.
Structoral Features
Romon-Famire
Amazon- Ratings
Chamckon-F
Squirreb-F
Actor
Flickr
BlogCatolog
Pubmed
True
68.13 a 2.23
52.13 a 0.55
45,70 a 4.92
41.89 a: 2.34
35.72 a 0.75
92.66 a. 0.46
96.47 a:
$ a 0.15 89.99 = 0.32
False
84.35 1,27
0.55
44.85 5.64
40.49 + 1.55
36,82 + 0.78
92.05 + 0.75
97.00 + 0.52
Table 9: Node classification accuracy comparison (%) among nodes with different degrees.
Dataset
Amazzn- Kalings
Flickar
BlogCntaing
Deg. Prup
0--20
20--80
40-60
60-80
80-100
0--20
20-w40
40-66
60-88
80-100
0-220
20--40
40-55
60-80
80-110
CMGNN
59.78
58.36
53,08
41.24
57.86
92.56
91.19
92.71
93.24
23.65
94.13
97.17
98.29
97.99
97.47
GCN
$2.35
16.21
51.74
41.55
46.47
90.44
91.17
92.85
22.19
89.50
92.17
96.58
92.83
97.84
96.51
OrderdANNN
56.30
56.16
$1.20
41.85
50.26
86.48
90.07
92.40
90.70 79
93. 40
92.19
96.00
97.48
97.36
96.27
GCNI
50.61
49.94
47.49
41.85
47.76
N7.49
90.54
92.29
92.68
95.09
92.81
96.73
90.58
97.90
97.43
Dataset
Koman-EEpiire
Chamcloon-F
Actor
Deg. Prop/15)
0--20
20-00
40-60
50-80
90~1100
00-20
20-40
40-66
60-80
90-100
0--20
20-40
40-66
00--80
S0-100
CMGNN
88.60
87.00
85.59
$6.25
74.38
40.73
46.28
56.02
46.64
30.93
35.56
37.14
38.40
36.05
36.84
ACM-GON
79,00
77.87
73.52
72.09
53.77
39.51
41.21
$2.25
45.80
47.09
34.48
36.58
36.27
24.63
37.46
OrderelGNN
88.60
$7.00
85.56
84.68
69.69
43.21
44.51
19.16
38.27
30.23
35.94
38.06
37.87
35.77
37.15
GUNI
86.79
85.1
55.20
$4.75
21.09
34.54
42.56
47,50
40.45
41.84
36,89
37.20
38.53
38.02
36.99
Dataset
Squirrel
Pubmed
Deg. Prup
0--20
20-440
40-66
60-80
80~1100
0--20
20--40
40-66
60-880
80-100
CMGNN
45.37
47.10
45.25
34.86
37.10
89.32
39.33
59.31
92.62
89.39
ACM-GON
41.12
44.30
44.22
30.97
42.10
89.60
89.54
50.58
92.0
80:23
OddaedtNN
43.78
45.53
43.09
27.90
25.48
39.67
89.37
89:45
92.54
89.02
GCNI
43.08
45.55
43.65
33.07
$9.50
92.45
$8.86
inaccurate pseudo labels. This is a common limitation of CM-based methods. In CMGNN, the CM is used to construct desired messages while original neighborhoods are preserved, mitigating the impact of inaccurate pseudo labels. (ii) Unlock the effectiveness of CM for low-degree nodes: Existing CM-based methods redefine pair-wise relations only for existing edges, limiting the effectiveness of CMs for low-degree nodes. In CMGNN, virtual neighbors can provide prototype messages from every class, enhancing neighborhood messages for low-degree or even isolated nodes. (iii) More accurate estimation of CM: While existing CM-based methods take naive approaches to estimate or initialize CM, CMGNN considers the effects of node degrees and model prediction confidence, resulting in more accurate CM estimation, especially in real-world situations. Additionally, CM in CMGNN is continuously updated with more accurate pseudo labels, creating a positive cycle.
G.2
A blation study on additional structural features
Utilizing additional structural features is a common approach in heterophilous GNNs that offers another way to use connection relationships, introducing both discriminant and redundant information. Thus, it presents trade-off between the advantages and disadvantages. We conducted ablation study to examine its effects and report the results in Table The additional structure features have positive effects four datasets, while others have negative effeets. It doesn't 't significantly impact performance except for Roman- -amanne Moreover, CMGNN can still achieve competitive results without using additional structural features.
G.3 Performance on Nodes with Various Levels of Degrees
To verify the effect of CMGNN on low-degree nodes, we divide the test set nodes into 5 parts accord- ing to their degrees and report the classification accuracy respectively. We compare CMGNN with 3 hop-performance methods and show the results in Table 9 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 supplementary neighborhood messages. Further, we can find that OrderedGNN and GCNII are good at dealing with nodes with high degrees, while ACM-GCN relatively good at nodes with low degrees. And CMGNN, to a certain extent, can be adapted to both situations at the same time.
30

---

Table 10: Performance comparison on low-label rate setting.
Method
Koman-Empire
Amazon-Ratings
Chameleon-F
Pubmed
MLP
58.14=1.40
37.03=0.43
36.74=2.97
83.07+0.55
GCN
33.53=0.77
37.3240.52
36.9122.22
83.9540.62
GCNII
63.27=0.72
39.93:0.87
38.40=3.27
86.04+0.74
ACM-GCN
59.93=2.03
39.9640.8
37.43=2.84
85.54+0.70
OrderedGNN
64.76:2.20
40.00=0.90
38.91=2.57
85.59+0 68
CMGNN
65.93=2.17
40.02240.6
40.11
85.62+0.94
G.4 Performance on low label rate setting
We conduct an experiment to investigate the performance of CMGNN under the low label setting, The label rate for training is set as 5% to meet the low label rate setting, and the datasets include Homann- Amazon-Ratinge Chameleon-F: and Pubmed. We compare CMGNN with 2 base and 3 pop-performance baseline methods, including MIP, GCN, GCNII, ACMGCN, and OrderedGNN. The classification accuracy comparison as Table TO Consistent with the main results, CMGNN can also achieve outstanding performance the low label rate setting, demonstrating the effectiveness of CMGNN on handling the noise issue.
G.5 Visualization of Weighted-CCN and CMD of CMGNN
We visualize the original and Weighted-CNy CMg of CMGNN along with the corresponding CMDs in Figure Obviously, CMGNN has increased the CMDs with Weighted-CMs. This shows that even with incomplete node labels, CMGNN can estimate and enhance high-quality CMs that provide valuable neighborhood information to nodes. Meanwhile, can adapt graphs with various levels of heterophily.
G.6 Efficiency Study
Complexity Analysis. The number learnable parameters layer of CMGNN is (d, compared to d,dd, in GCN and 3d, (d, + 1) + 9 in ACM-GCN, where dp is the dimension of representations. The time complexity of layer is composed of three parts:
+
(i) AGGREGATE: O(Nd, ONd,, + Md,) and O(Nd, + N ) for node ego, neighbor- hood and the sufficient neighborhood respectively, where N and M = |3| denotes the number of nodes and edges;
(ii) COMBINE: (33N(33,+1)+12N for calculating adaptive weights and O(3N) for combination;
(iii) Final: ((1) for concatenations.
Thus, the overall time complexity of L-layer CMGNN is (3d, or O(LNd, + LMd,) for brevity.
Experimental Running Time. We report the actual average running time (ms per epoch) of baseline methods and CMGNN in Table for comparison. The results demonstrate that CMGNN can balance both performance effectiveness and running efficiency.
Trade-off Analysis between Effectiveness and Efficiency. We have also visualized the trade-off between performance accuracy and empirical runtime compared baseline methods in Figure g From the results, we can see that CMGNN achieves the best performance with relatively low time consumption. Compared with OrderedGNN and GCNII, which have the second- and third-best average ranks, CMGNN offers both better accuracy and lower time consumption.
31

---

3:
0.04
0.38
-0.40
0.24
0.00
0.13
0.40
0.00
0.47
000
0.13
0.22
01
0.43
3.07
0:23
0
6.33
0.64
0.18
6.33
0.12
24
6.37
03
9.48
6.30 0:33
0.12
116
3.37
0:
0.22
0.04
9.36
0.32
0.37
0.12
0.03
6:30
24
0.12
30 0:32
0:38
0.08
0.32
0.5
0.30
0.26
0.07
0.00
0.12
0.13
0.27
w-0.14
26
0.39
0.33
0.26
0.18
-0.0
0.58
0.30
0.17
0.36
(a) Ama-O, 0.46
(b) Ama-
(c) Blo-O, 0.69
(d) Blo- W. 0.70
24
16
0.24
0.21
0.18 0.13
0.25
0.26
0.35
0.10 0.09
20
60
0.23
0.16
0.23
0.17
0.20
0.29
0.13
0.19
621
018
seriie enta unta urta snro
0.12
0.34 0.13
0.26
0.24
0.25
0.09
0.00
0.19
0.31 0.33
(e) Rom-O, 0.85
(l) Rom- W. 0.86
(g) Cha-O, 0. 0.27
(h) Cha-W W, 0.49
--0.21 20 9.0 0.21
0.22
0:18
0.31
0.17 0.20
0.26 0.26
0.13 0.15
26
85
-04
n-0.18 0. 0.00 0.21 0.20
K-
0.33
0.05
0.32
0.22
0.28
0.11
0.17 0.20 0.26 0.26
N- 0.09 0.13 0.16 0.28 0.34
0.20 21 0.20 0.20 0.20
0.11
0.04
0.27
0.21
0.36
0.11
0.17 0.21 0.26 0.25
0.09 0.14 0.15 0.29 0:3
0.19
0:23
0.24
Squ-O, 0.08
(j) Squ- W. 0.16
(k) Act-O, 0.03
(I) Act- W, 0.04
sox
1.0
0.66
0.11
0.24
0.74
0.10
0.16
voo 332 sm
550
0.05
0.85
0.10
0.04
0.89
0.07
0.4
0.10
0.09
0.82
0.2
~
0.07
0.09
0.84
-02
0.00
-0.0
(m) Fli-O, 0.40
(n) Fli-W, 0.44
(0) Pub-O, 1.40
(p) P, 1.51
Figure 7: The visualization of original (O) and Weighted-CN (W) of CMGNN along with the CMDs on all small-scale datasets.
Table 11: Efficiency study results of average model running time (ms/epoch). OOM denotes an out-of-memory error during the model training.
Method
Roman-Empin
Amazon- Rutings
Chameleon-F
Squirrel-F
Actor
Flickr
BlogCatalog
Pubmed
GCN
33.8
33.4
7,9
20.6
34.4
37.2
30.4
35.6
GAT
15.9
67.3
14.0
20.8
66.2
17.6
33.4
APPNP
14.6
15.9
13.9
21.3
14.6
20.2
23.2
21.2
GCNI
29.4
28.4
37.3
19.6
37.7
84.2
97.6
258.0
CPGNN
12.7
20.3
12.2
13.6
18.9
16.7
14.0
H2GCN
20.0
31.2
17.2
32.4
S5.6
415.7
165.5
39.0
MixHop
434.6
486.3
GBK GNN
119.8
191.8
31.0
238.1
157.9
OOM
OOM
137.0
42.1
199,8
111.2
108.7
2290.8
GloGNN
25.4
19.3
121.8
23.3
1292
562.9
30.9
43,2
HOGGCN
OOM
0OM
25.2
$4.3
1002.9
707.3
367.4
00M
GPR GNN
15.9
12.5
22.3
23.2
16.7
15.9
14.7
13.2
ACM-GCN
56.7
56.7
26.1
29.7
22.5
60.7
31.7
37.1
OrderedGNN
86.0
110.8
107.0
88.3
88.1
M2MGNN
275.6
84.3
527
169.1
400.2
136.7
220.5
151.0
N
236.8
184.4
172.0
134.5
191.2
116.5
1849
CMGNN
51.5
93.5
62.5
64.7
19.0
$2.5
69.8
102.9
32

---

BegCetang Saytoie
(rggee $57 Zuzk
ERax
200r
15
12.00
3100
2008
Tatt
Thrs
Time
Traiding Thme
(a) Coman--mmiir
(b) Flickr
(c) Blogcatalog
Figure 8: Visualizations of the trade-off between performance accuracy and training time compared with baseline methods on three representative datasets.
33


Reviews:
[{"review_id": "DnYTR65zEV", "reviewer": "Reviewer_5t7f", "summary": "This paper investigates why message passing mechanisms in Graph Neural Networks (GNNs) remain effective on heterophilic graphs, where connected nodes tend to belong to different classes. The authors introduce the concept of Compatibility Matrix Discriminability (CMD), proposing that the success of message passing in such settings can be attributed to an increase in CMD which means better discriminability in CM. Building on this insight, they propose CMGNN, a new method that enhances CMD through a combination of sufficient neighborhood supplementation, confidence-based compatibility matrix estimation, and CM-aware message passing. The model is evaluated on 13 datasets against 19 baselines, showing superior performance.", "questions": "1、Since the model needs to do CM estimation under semi-supervised settings, how sensitive is CMGNN to the choice or accuracy of pseudo labels used in compatibility matrix estimation?\n2、In evolving graphs (new nodes or labels arrive over time), would re-estimating CMD and retraining CMGNN be feasible, or is the method inherently static?\n3、Many real-world semi-supervised graphs have imbalanced class distributions. Does CMD offer a reliable signal under label imbalance?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well-motivated and logically structured, guiding the reader from motivation to methodology and results. The authors provide a theoretical analysis connecting Compatibility Matrix Discriminability (CMD) with node discriminability (ENKL), showing that the increase in CMD is a possible reason for the effectiveness of heterophilic message-passing. And extensive experiments of the proposed CM-aware GNN against baselines further validate their findings.\n\nHowever, the theoretical results rely heavily on the CSBM-H model, which may not fully represent real-world graph structures. Although the method performs well, it introduces extra computation, which might become costly on dynamic or real-time graphs.", "was_revised": true, "final_justification": "Most of my main concerns have been well addressed and the authors' effort during the rebuttal phase has made this work much more solid, I will increase my **confidence score from 3 to 4**.", "rebuttal": "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.\n\n\n> **Question #1: How sensitive is CMGNN to the choice or accuracy of pseudo labels used in compatibility matrix estimation?**\n\nAnswer #1: \nTo 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.\nThe 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.\n\nThe details of the experiment are as follows:\n* For CM, we use the corresponding **CMD** to better measure its quality since the matrix is hard to visualize.\n* We use an additional low label setting (5% nodes for training) to construct different quality of pseudo labels.\n* 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.\n  \nThe results are as follows:\n|Dataset|Rom.|Rom.|Ama.|Ama.|Cha.|Cha.|Pub.|Pub.|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|**Setting**|**CMD**|**pse_acc**|**CMD**|**pse_acc**|**CMD**|**pse_acc**|**CMD**|**pse_acc**|\n|Fixed|0.847|-|0.458|-|0.274|-|1.396|-|\n|Normal|0.859|0.919|0.626|0.746|0.488|0.682|1.507|0.938|\n|Low Label Rate|0.834|0.648|0.592|0.416|0.417|0.397|1.490|0.830|\n\nFrom 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.\n\n\n> **Question #2 & Weakness #2: In evolving graphs, would re-estimating CMD and retraining CMGNN be feasible since it introduces extra computation?**\n\nAnswer #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:\n* 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**.\n* For the increase of the node itself, there is **unavoidable time consumption** for all methods. \n* 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.\n* 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.\n\nIn 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**.\n\n\n> **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?**\n\nAnswer #3: \nWe investigate the effectiveness of CMD under a label imbalance setting theoretically and empirically as follows:\n* 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.**\n* 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.\n\n\nThe details of the experiment are as follows:\n\nTo 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.\nThe following are the experimental settings:\n* **CMD**: The CMDs of fixed CM and Weighted-CM on real datasets are easy to calculate according to the definition. \n* **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.\n* **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:\n$$\n\\mathbf{H}^{LP}=\\hat{\\mathbf{A}}\\mathbf{X},\\quad\n\\mathbf{H}^{HP}=(\\mathbf{I}-\\hat{\\mathbf{A}})\\mathbf{X},\\quad\n\\mathbf{H}^{HTMP_0}=(\\mathbf{I}-\\hat{\\mathbf{A}}+\\hat{\\mathbf{A}}^2)\\mathbf{X},\\quad\n\\mathbf{H}^{HTMP_1}=(\\mathbf{I}+\\hat{\\mathbf{A}}+\\hat{\\mathbf{A}}^2)\\mathbf{X}.\n$$\nTo 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:\n|Dataset|Amazon-Ratings|Roman-Empire|Squirrel-F|Actor|\n|:-:|:-:|:-:|:-:|:-:|\n|num_class|5|18|5|5|\n|Rate of max/min class|8.5|10|3.2|2.3|\n|class proportion (%)|(36.8, 26.8, 23.2, 8.9, 4.3)|(14.0, 13.8, 11.0, 11.0, 9.7, 6.0, 5.5, 4.8, 4.2, 3.8, 3.5, 3.2, 2.0, 1.9, 1.6, 1.5, 1.4, 1.4)|(34.0, 23.2, 17.9, 13.4, 10.5)|(25.9, 23.9, 21.4, 17.5, 11.2)|\n\nThe results are as follows:\n|Dataset|Ama.|Ama.|Rom.|Rom.|Squ.|Squ.|Act.|Act.|\n|-|-|-|-|-|-|-|-|-|\n|**MP Operator**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|\n|**LP**|0.46|-0.26|0.85|-0.76|0.08|-14.84|0.03|-2.77|\n|**HP**|1.95|-0.80|2.77|-2.62|2.02|-67.89|2.01|-9.28|\n|**HTMP_0**|2.35|-1.14|3.31|-4.13|2.22|-80.05|2.29|-11.53|\n|**HTMP_1**|3.10|-2.41|3.55|-5.04|2.28|-89.52|2.31|-11.63|\n\nIn 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.\n\n\n**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.**"}, {"review_id": "1LSrL7RQpb", "reviewer": "Reviewer_tib1", "summary": "This paper examines the effectiveness of message-passing mechanisms in heterophilous graph neural networks (HTGNNs), where connected nodes often display contrasting behaviors. This paper propose a unified heterophilous message-passing (HTMP) mechanism and introduce CMGNN, which enhances the compatibility matrix to address incomplete and noisy semantic neighborhoods.", "questions": "See the Weakness.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "I have previously reviewed this paper. Compared to the earlier version I evaluated, the authors have included experiments on large datasets to demonstrate the scalability of their method. However, some issues still remain unresolved.\n\n**Strengths:**\n\n1.  The superior performance of CMGNN is substantiated through comprehensive evaluations across 13 varied datasets, benchmarked against 19 existing methods.\n\n**Weaknesses:**\n\n1.  **Motivation**: The introduced HTMP framework does not seem to be specifically designed for the problem of heterophily. Its core components, such as FUSE and COMBINE, are common techniques in the GNN field (e.g., used to address over-smoothing or over-squashing) rather than being exclusive solutions for heterophily, making the framework appear more like a generalized enhancement of the message-passing paradigm.\n\n2.  **Novelty**: The concept of a Compatibility Matrix has been previously explored in GNNs. This work does not seem to offer any new methodological contributions to it, which casts doubt on its originality.\n\n3.  **Methodology**\n\n    - The paper fails to provide a clear rationale for the specific architectural choices within AGG, COMBINE, and FUSE, leaving it unclear how these designs contribute to a more effective estimation of the compatibility matrix by the HTMP framework.\n\n    - Furthermore, the construction of these components seems excessively handcrafted and arbitrary. For instance, it is not justified why the COMBINE step integrates information from only the three specified neighbor types, or why FUSE employs concatenation while COMBINE uses a weighted sum, giving the impression of an ad-hoc assembly of pre-existing techniques.", "was_revised": true, "final_justification": "My main concern, the doubts regarding the motivation of the paper have been resolved, therefore I have decided to increase the score.", "rebuttal": "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,\n\n* 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.\n* 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.\n* 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.\n\nBased 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.\n\nIf you have any further questions, please feel free to contact us."}, {"review_id": "9jGLndipPA", "reviewer": "Reviewer_eeXf", "summary": "This paper explores the connection between the discriminability of node embedding and the compatibility matrix (CM), and attributes the effectiveness of heterophilic message passing to increasing the proposed Compatibility Matrix Discriminability (CMD). Building on this insight, the authors introduce CMGNN, a novel framework that explicitly improves CMD to enhance node embeddings, while alleviating the issues of graph sparsity and noise.", "questions": "1. Why GraphSAGE is not included in the comparison, given that it has demonstrated strong performance on both homophilic and heterophilic graphs in prior studies and our own experience?\n2. Appendix E details engineering practices like a weighting function for CM estimation, additional structural features and adaptive weighting of three sources of messages. Can you provide ablation studies to quantify their individual contributions to CMGNN’s performance?\n3. In Figure 6, the CMD value of Rom-Glo is exceptionally high, yet its performance reported in Table 1 is relatively poor. This discrepancy suggests that the relationship between CMD and model performance may be more nuanced than the paper implies, especially on datasets characterized by multiple classes, high heterophily, and low average degree. It would be helpful to clarify how CMGNN addresses such cases and whether CMD remains a reliable indicator of representation quality under these challenging conditions.\n4. In Figure 7, the improvements in CMD achieved by the Weighted-CMs appear marginal compared to the original versions. This raises the question of how much the weighted design actually contributes to the overall performance gains. A quantitative analysis or ablation would help clarify the effectiveness of this component.", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "1. Extensive experiments have been conducted on multiple real-world and synthetic datasets with various homophily levels, node degrees and CMD levels, demonstrating the significance of CMD for heterophilic message passing and the robustness and cost-effectiveness of the proposed CMGNN.\n2. A total of 19 representative homophilic and heterophilic GNN models have been integrated into a unified codebase and evaluated on 13 benchmark datasets with diverse proporties. The implementation details are also provided, facilitating reproducibility and further research in this area.\n3. The presentation of experimental results lacks clarity in distinguishing performance across different homophily levels. Grouping the results (or at least the average ranks) by homophilic and heterophilic graphs would better highlight the effectiveness of the proposed CMGNN in each setting. Such stratified evaluation is particularly important for assessing heterophily-specific models.\n4. While Theorem 3.2 provides insight into the negative correlation between CMD and ENKL, its assumptions—two-class setting, Gaussian feature distributions, ignored node degree effects, and reliance on the CSBM-H model—limit its direct applicability to real-world complex datasets. Although CMGNN mitigates some of these issues empirically, the paper lacks direct validation of the CMD-ENKL relationship on real datasets.\n5. In Table 3, the ablation study on the effects of supplementary messages (SM) and discrimination loss (DL) is conducted on only five datasets. It remains unclear how these components perform on the remaining datasets. A more comprehensive evaluation across all datasets would provide a clearer understanding of their generalizability and overall contribution.", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> **Weakness #1: The analysis of experimental results considering different homophily levels.**\n\nAnswer #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:\n|Datasets|Rom.|Sna.|Squ.|Act.|Fli.|Cha.|Ama.|Blog|Pok.|Pen.|Avg. Rank|\n|-|-|-|-|-|-|-|-|-|-|-|-|\n|Homo.|0.05|0.07|0.22|0.22|0.24|0.25|0.38|0.4|0.45|0.47|-|\n|CMGNN|1|1|1|4|1|1|1|1|1|1|1.3|\n\n|Datasets|Twi.|Gen.|Pub.|Avg. Rank|\n|-|-|-|-|-|\n|Homo.|0.55|0.62|0.8|-|\n|CMGNN|3|2|2|2.3|\n\nFurther, the average ranks of baseline methods on heterophilic and homophilic groups are as follows:\n\n|Method|Hetero. Group|Homo. Group|Overall|\n|-|-|-|-|\n|MLP|15|14.7|14.9|\n|GCN|13.9|12.7|13.6|\n|GAT|13.1|12.7|13|\n|GraphSAGE|8.1|10|8.5|\n|APPNP|11.7|12.3|11.8|\n|GCNII|4.8|2.7|4.3|\n|H2GCN|14.7|14.7|14.7|\n|MixHop|7.1|8.3|7.4|\n|GBK-GNN|17.1|17|17.1|\n|GGCN|16.6|15.7|16.4|\n|GloGNN|9.9|4|8.5|\n|HOGGCN|13.8|19|15|\n|GPR-GNN|8|11.3|8.8|\n|ACM-GCN|6.6|11|7.6|\n|OrderedGNN|6.8|3.3|6|\n|M2MGNN|10|9|9.8|\n|N$^2$|9|7.3|8.6|\n|CLP|12.3|11|12|\n|EPFGNN|14.5|14|14.4|\n|CPGNN|13.3|13.7|13.4|\n|**CMGNN**|**1.3**|**2.3**|**1.5**|\n\n* 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.\n* 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.\n* 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.\n\n\n> **Weakness #2: The lack of direct validation of the CMD-ENKL relationship on real datasets.**\n\nAnswer #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**.\n\nThe details are as follows: \n* **CMD**: The CMDs of fixed CM and Weighted-CM on real datasets are easy to calculate according to the definition. \n* **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.\n* **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):\n$$\nH^{LP}=\\hat{A}X,\\quad\nH^{HP}=(I-\\hat{A})X,\\quad\nH^{HTMP_0}=(I-\\hat{A}+\\hat{A}^2)X,\\quad\nH^{HTMP_1}=(I+\\hat{A}+\\hat{A}^2)X.\n$$\nThe results are as follows:\n|Dataset|Ama.|Ama.|Rom.|Rom.|Cha.|Cha.|Squ.|Squ.|Act.|Act.|Fli.|Fli.|Blo.|Blo.|Pub.|Pub.|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|**Operator**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|\n|**LP**|0.46|-0.26|0.85|-0.76|0.27|-25.38|0.08|-14.84|0.03|-2.77|0.40|-0.78|0.69|-0.41|1.40|-0.30|\n|**HP**|1.95|-0.80|2.77|-2.62|2.07|-126.50|2.02|-67.89|2.01|-9.28|1.88|-10.95|1.64|-16.01|0.71|-0.22|\n|**HTMP_0**|2.35|-1.14|3.31|-4.13|2.39|-150.75|2.22|-80.05|2.29|-11.53|1.93|-11.18|1.87|-16.48|2.00|-0.81|\n|**HTMP_1**|3.10|-2.41|3.55|-5.04|2.85|-170.64|2.28|-89.52|2.31|-11.63|2.67|-11.26|3.14|-16.77|4.73|-1.35|\n\nIn 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.\n\n\n> **Weakness #3 & Question #2: A more comprehensive evaluation of ablation studies across all datasets including the implementation details.**\n\nAnswer #3: \nThank you for the suggestion! We investigate the influence of Confidence-based CM Estimation (CE), degree weighting function (DW), and adaptive weighting message combination (AW).\n* \"W/O CE\" means removing the confidence during the CM estimation.\n* \"W/O DW\" means removing the degree weighting function during the CM estimation.\n* \"W/O AW\" means replacing the adaptive weighting with the mean operator in the message combination.\n* The ablation study of additional structural features is provided in Appendix G.2.\n\nThe complete results are as follows:\n|Variants|Rom.|Sna.|Squ.|Act.|Fli.|Cha.|Ama.|Blog|Pok.|Pen.|Twi.|Gen.|Pub.|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|CMGNN|84.35±1.27|59.86±0.61|41.89±2.34|36.82±0.78|92.66±0.46|45.70±4.92|52.13±0.55|97.00±0.52|81.42±0.55|83.01±0.48|65.18±0.31|85.19±0.53|89.99±0.32|\n|W/O CE|83.88±1.41|59.54±0.77|40.35±2.43|36.47±1.22|92.51±0.51|44.75±3.05|51.93±0.38|96.72±0.51|80.67±0.65|82.58±0.49|65.09±0.26|85.03±0.47|89.68±0.36|\n|W/O SM|83.82±1.29|59.48±0.78|40.72±2.28|36.05±1.24|92.22±0.47|42.29±4.38|51.91±0.83|96.61±0.44|79.39±0.37|81.68±1.55|65.01±0.34|84.94±0.56|89.53±0.41|\n|W/O DL|83.63±1.35|59.68±0.72|41.65±2.55|36.41±1.08|92.66±0.46|44.92±4.12|52.05±0.57|97.00±0.52|80.28±0.49|81.34±1.83|64.88±0.20|84.87±0.75|89.99±0.32|\n|W/O CE and DL|83.77±1.38|59.46±0.71|39.80±2.36|36.32±1.05|92.28±0.52|44.58±3.28|51.74±0.55|96.53±0.53|79.26±0.34|81.20±0.61|64.64±0.19|84.53±0.59|88.97±0.48|\n|W/O SM and DL|83.48±1.89|59.25±0.75|40.19±2.69|35.66±1.42|91.98±0.49|41.01±3.09|51.49±1.02|96.39±0.58|77.57±0.59|80.71±0.48|64.33±0.32|84.28±0.50|88.71±0.45|\n|W/O DW|83.80±1.68|59.62±0.72|41.61±2.39|36.45±1.26|92.51±0.56|44.25±5.06|52.08±0.52|96.85±0.51|80.82±0.72|82.69±0.57|65.04±0.38|85.13±0.56|89.93±0.32|\n|W/O AW|78.88±4.03|58.12±0.65|36.40±2.95|36.56±1.21|90.77±0.44|42.01±3.70|51.21±0.74|96.23±0.51|80.13±0.34|81.66±0.42|64.84±0.22|84.39±0.15|89.73±0.42|\n\nThe results demonstrate the effectiveness of these components. \n* 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.\n* 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**.\n* 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.\n\n\n> **Question #1: Why GraphSAGE is not included in the comparison?**\n\nAnswer #4:\nThank 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.\nWe have added GraphSAGE for comparison and its performance is as follows:\n|Datasets|Rom.|Sna.|Squ.|Act.|Fli.|Cha.|Ama.|Blog|Pok.|Pen.|Twi.|Gen.|Pub.|Hetero. Rank|Homo. Rank|Overall Rank|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|GraphSAGE|69.62±1.40|35.72±0.12|38.13±1.71|36.12±1.40|92.00±0.58|42.18±4.64|45.07±0.54|96.30±0.44|77.22±0.06|78.90±0.37|62.14±0.09|84.37±0.15|88.86±0.56|8.1|10|8.5|\n\n**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.\n\n\n> **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.**\n\nAnswer #5: CMD measures the discriminability considering the graph structure and labels, without node features. \nThe quality of node embeddings after message passing relies on both CMD and node features.\n**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.\n\nTo address real-world issues, CMGNN constructs supplementary neighbors for each node and utilizes the discrimination loss to directly enhance the discriminability of node embeddings.\n\n\n> **Question #4: How much does the Weighted-CM contribute to the overall performance gains?**\n\nAnswer #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:\n|Variants|Rom.|Sna.|Squ.|Act.|Fli.|Cha.|Ama.|Blog|Pok.|Pen.|Twi.|Gen.|Pub.|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|**CMGNN**|84.35±1.27|59.86±0.61|41.89±2.34|36.82±0.78|92.66±0.46|45.70±4.92|52.13±0.55|97.00±0.52|81.42±0.55|83.01±0.48|65.18±0.31|85.19±0.53|89.99±0.32|\n|W/O WCM|83.55±2.40|59.38±0.47|41.12±1.96|36.19±1.05|92.40±0.50|44.75±4.25|51.88±0.63|96.67±0.51|81.20±0.62|82.79±0.52|65.01±0.49|84.89±0.62|89.82±0.36|\n\nThe 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**. \nThe 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.\n\n\n**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.**"}, {"review_id": "DI6hy1AUFB", "reviewer": "Reviewer_SFcH", "summary": "This paper investigates why message passing remains effective for Graph Neural Networks on heterophilic graphs, introducing the concept of Compatibility Matrix Discriminability (CMD) to explain the connection between message passing and node discriminability. Building on these insights, the authors propose CMGNN, a novel model that explicitly enhances CMD and demonstrates superior performance on heterophilic graphs across extensive benchmarks.", "questions": "1. What is the definition of HTMP method? Is it just the truncated Krylov method [1], i.e. identity + multi-hop neighborhood information? It seems that you are studying the normal message passing all the time.\n\n2. \"The high-pass operator is often used to capture the difference in heterophilic graphs.\" This is not accurate. High-pass operator computes the dissimilarity between the central node features and its aggregated neighborhood features, or conduct the neighborhood diversification operation [2].\n\n3. What do you use $\\dot{A}$ in equation (6)? Why not $\\hat{A}$?\n\n4. Why do we need CMD when we already have ENKL to measure node distinguishability?\n\n5. Could you please demonstrate how sparsity will be harmful to MP theoretically (probably with toy example) or empirically with real-world datasets?\n\n6. The writing for \"Sufficient Neighborhood Supplement\" is confusing. Need to re-organize the contents, clarify the notations and their dimensions.\n\n7. More ablation studies on different proposed model components are needed are needed.\n\n\n\n\n\n[1] Break the ceiling: Stronger multi-scale deep graph convolutional networks. Advances in neural information processing systems. 2019;32.\n\n\n[2] Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. arXiv preprint arXiv:2008.08844. 2020 Aug 20.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "# Strengths\n \nQuality: good \\\nClarity: medium\\\nSignificance: good\\\nOriginality: medium\n\n# Weaknesses\n\nSee below", "was_revised": true, "final_justification": "After going through the discussion from other reviewers, I'll keep my positive score.", "rebuttal": "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.\n\n\n> **Question #1: What is the definition of HTMP method? Is it just the truncated Krylov method?**\n\nAnswer #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.\n\nThus, 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].\n\nFor 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.\n\nReference:\n\n[1] Node similarity preserving graph convolutional networks. WSDM 2021.\n\n[2] Finding global homophily in graph neural networks when meeting heterophily. ICML 2022.\n\n\n\n> **Question #2: A more accurate description of the high-pass operator.**\n\nAnswer #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.\n\n\n\n> **Question #3: Why do you use $\\dot{\\mathbf{A}}$ in equation (6)? Why not $\\hat{\\mathbf{A}}$?**\n\nAnswer #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.\n\n\n\n> Question #4: Why do we need CMD when we already have ENKL to measure node distinguishability?\n\nAnswer #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.\n\n\n\n> **Question #5: How sparsity will be harmful to MP theoretically (probably with a toy example) or empirically with real-world datasets?**\n\nAnswer #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.\n\nConsidering a graph with nodes belonging to 3 classes. The latent connection preference among classes follows the compatibility matrix:\n$$\n\\mathbf{M}=\\\\begin{bmatrix}\n0.3,&0.1,&0.6\\\\\\\\ \n0.1,&0.7,&0.2\\\\\\\\ \n0.6,&0.2,&0.2\n\\\\end{bmatrix}.\n$$\nFor simplicity, the features of nodes in the same class are set to the same:\n$$\n\\mathbf{X}\\_{c0}=(1, 0, 0),\\\\quad\n\\mathbf{X}\\_{c1}=(0, 1, 0),\\\\quad\n\\mathbf{X}\\_{c2}=(0, 0, 1).\n$$\n\nWe use a vanilla message passing $\\mathbf{H}=\\hat{\\mathbf{A}}\\mathbf{X}$ as an example.\nSuppose we have two nodes $u$ and $v$, belonging to class 0 and class 1, respectively.\n\nIf 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:\n$$\n\\mathbf{h}\\_{u}=(0.3, 0.1, 0.6),\\quad\n\\mathbf{h}\\_{v}=(0.1, 0.7, 0.2),\n$$\nwhich can be easily distinguished.\n\nFurther, 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:\n$$\n\\mathbf{h}\\_{u}=(0.5, 0, 0.5),\\quad\n\\mathbf{h}\\_{v}=(0.5, 0, 0.5).\n$$\nThus, **two nodes from different classes may share similar embeddings after message passing in sparsity settings** and it's difficult to distinguish them.\n\nIn 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.\n\n\n\n> **Question #6: The writing for \"Sufficient Neighborhood Supplement\" is confusing. Need to re-organize the contents, clarify the notations and their dimensions.**\n\nAnswer #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.\n\n\n\n> **Question #7: More ablation studies on different proposed model components are needed.**\n\nAnswer #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.\n* \"W/O CE\" means that we remove the confidence during the CM estimation.\n* \"W/O DW\" means that we remove the degree weighting function during the CM estimation.\n* \"W/O AW\" means that we replace the adaptive weighting with the mean operator in the message combination.\n\nThe complete results are as follows:\n\n|Variants|Rom.|Sna.|Squ.|Act.|Fli.|Cha.|Ama.|Blog|Pok.|Pen.|Twi.|Gen.|Pub.|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|**CMGNN**|84.35±1.27|59.86±0.61|41.89±2.34|36.82±0.78|92.66±0.46|45.70±4.92|52.13±0.55|97.00±0.52|81.42±0.55|83.01±0.48|65.18±0.31|85.19±0.53|89.99±0.32|\n|W/O CE|83.88±1.41|59.54±0.77|40.35±2.43|36.47±1.22|92.51±0.51|44.75±3.05|51.93±0.38|96.72±0.51|80.67±0.65|82.58±0.49|65.09±0.26|85.03±0.47|89.68±0.36|\n|W/O SM|83.82±1.29|59.48±0.78|40.72±2.28|36.05±1.24|92.22±0.47|42.29±4.38|51.91±0.83|96.61±0.44|79.39±0.37|81.68±1.55|65.01±0.34|84.94±0.56|89.53±0.41|\n|W/O DL|83.63±1.35|59.68±0.72|41.65±2.55|36.41±1.08|92.66±0.46|44.92±4.12|52.05±0.57|97.00±0.52|80.28±0.49|81.34±1.83|64.88±0.20|84.87±0.75|89.99±0.32|\n|W/O CE and DL|83.77±1.38|59.46±0.71|39.80±2.36|36.32±1.05|92.28±0.52|44.58±3.28|51.74±0.55|96.53±0.53|79.26±0.34|81.20±0.61|64.64±0.19|84.53±0.59|88.97±0.48|\n|W/O SM and DL|83.48±1.89|59.25±0.75|40.19±2.69|35.66±1.42|91.98±0.49|41.01±3.09|51.49±1.02|96.39±0.58|77.57±0.59|80.71±0.48|64.33±0.32|84.28±0.50|88.71±0.45|\n|W/O DW|83.80±1.68|59.62±0.72|41.61±2.39|36.45±1.26|92.51±0.56|44.25±5.06|52.08±0.52|96.85±0.51|80.82±0.72|82.69±0.57|65.04±0.38|85.13±0.56|89.93±0.32|\n|W/O AW|78.88±4.03|58.12±0.65|36.40±2.95|36.56±1.21|90.77±0.44|42.01±3.70|51.21±0.74|96.23±0.51|80.13±0.34|81.66±0.42|64.84±0.22|84.39±0.15|89.73±0.42|\n\n\nThe results demonstrate the effectiveness of these components. \n* 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.\n* 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**.\n* 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.\n\n\n\n**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.**"}, {"review_id": "e2Rr14wNHT", "reviewer": "Reviewer_ZGc9", "summary": "The authors introduce a novel Correlation Theorem that rigorously links the separability of node classes to the distinguishability of the underlying compatibility matrix, validating this relationship through synthetic experiments and arguing that the strong empirical performance of heterophilous GNNs stems from enhanced compatibility-matrix distinguishability. They further propose a compatibility-guided message-passing framework that dynamically weights neighbor contributions based on compatibility scores, explicitly designed to mitigate issues arising from low-degree nodes and noisy edges. Finally, they conduct an extensive study on 19 real-world heterophilous benchmarks, demonstrating that the proposed model consistently outperforms existing baselines across both classification accuracy and robustness metrics.", "questions": "1. Do you have any sense on the training/optimization dynamics of the compatibility matrix? To me, this is an interesting component since in your formulation it depends on the GNN predictions, so both the GNN and the compatibility matrix are being jointly optimized. Addressing this either theoretically or empirically would be appreciated and interesting.\n2. Does the result in Theorem 3.2 generalize to the multiclass case? How do other graph distributions other than the CSBM fit into the theorem? Do you expect the result to hold when the degrees from the classes and across nodes are not equal? This case is particularly important since the method ultimately addresses the low-degree issue for nodes, common in many social networks (powerlaw distributions). Related to weakness #2, how does this analyses build on existing ones either looking at node distinguishability or the class compatibility matrix?\n3. It would be interesting to see a detailed investigation of which types of nodes are benefiting over other methods. For example, if there were a way to show that low degree nodes benefit the most over other methods, perhaps by looking at accuracy specifically for low-degree nodes compared to other methods that don't take into account low-degree issues, this would be interesting. Similarly, for graphs with high noise or a low label rate, I would also expect the method to show improvements over other baselines.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**  \n- Specifically targeting low node degree and high noise is very important and many works have outlined issues in these regimes. I liked the use of the $K$ virtual nodes to address the degree issue and the confidence estimation to address the noise issue. The combination of these components fit very well in the overall architecture.\n- Experiments were very rigorous with 19 heterophilous benchmarks and impressive performance compared to many of the existing and popular heterophilous models. The ablation analysis was also nice to see. \n- There was sufficient discussion against how their approach differed from existing compatibility-based models. This highlighted the contributions of the paper. \n\n**Weaknesses**  \n- I think the theoretical section is a bit weak. Since Theorem 3.2 considers the two class case, it is really asking the question of if homophily correlates with node distinguishability. The compatibility matrix is interesting in my view since it generalizes homophily from the two-class case to the multi-class case. Since it is well-known that homophily correlates with class distinguishability, this seems to be not a major finding. There are also analyses that have shown the relationship between the class compatibilty matrix and node distinguishability, so I'm not sure how significant the theoretical contributions are. \n- I think the work would benefit from a discussion of the similarities and differences with with existing analyses. Throughout the analyses I was unsure of the contributions. Thus making explicit the relations to other analyses and how this analyses builds on existing ones would be beneficial to the reader.", "was_revised": true, "final_justification": "Overall, the paper proposed a novel approach to leveraging the compatibility matrix, a powerful tool for homophilic and heterophilic graph learning. While the compatibility matrix has been proposed in the past, specifically addressing low degree nodes with the sufficient neighborhood supplement and addressing uncertainty with confidence based CM estimation, is novel as far as I'm aware. Extensive experiments were conducted to evaluate the utility of the approach. During the rebuttal period, the authors addressed each of my concerns with additional experiments or pointers to existing analyses in the Appendix. Thus, I recommend this paper for acceptance.", "rebuttal": "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.\n\n\n> **Weakness #1 & Question #2: The extension of Theorem 3.2.**\n\nAnswer #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**.\n\nThe details are as follows: \n* **CMD**: The CMDs of fixed CM and Weighted-CM on real datasets are easy to calculate according to the definition. \n* **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.\n* **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:\n$$\n\\mathbf{H}^{LP}=\\hat{\\mathbf{A}}\\mathbf{X},\\quad\n\\mathbf{H}^{HP}=(\\mathbf{I}-\\hat{\\mathbf{A}})\\mathbf{X},\\\\\n\\mathbf{H}^{HTMP_0}=(\\mathbf{I}-\\hat{\\mathbf{A}}+\\hat{\\mathbf{A}}^2)\\mathbf{X},\\quad\n\\mathbf{H}^{HTMP_1}=(\\mathbf{I}+\\hat{\\mathbf{A}}+\\hat{\\mathbf{A}}^2)\\mathbf{X},\\\\\n$$\nThe results are as follows:\n|Dataset|Ama.|Ama.|Rom.|Rom.|Cha.|Cha.|Squ.|Squ.|Act.|Act.|Fli.|Fli.|Blo.|Blo.|Pub.|Pub.|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|**MP Operator**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|**CMD**|**ENKL**|\n|**LP**|0.46|-0.26|0.85|-0.76|0.27|-25.38|0.08|-14.84|0.03|-2.77|0.40|-0.78|0.69|-0.41|1.40|-0.30|\n|**HP**|1.95|-0.80|2.77|-2.62|2.07|-126.50|2.02|-67.89|2.01|-9.28|1.88|-10.95|1.64|-16.01|0.71|-0.22|\n|**HTMP_0**|2.35|-1.14|3.31|-4.13|2.39|-150.75|2.22|-80.05|2.29|-11.53|1.93|-11.18|1.87|-16.48|2.00|-0.81|\n|**HTMP_1**|3.10|-2.41|3.55|-5.04|2.85|-170.64|2.28|-89.52|2.31|-11.63|2.67|-11.26|3.14|-16.77|4.73|-1.35|\n\nIn 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**.\n\n\n\n> **Weakness #2 and Question #2: The discussion of the connection and differences with existing analyses.**\n\nAnswer #2: \nThank you for this suggestion! The discussion of the Connections and differences with existing analyses is as follows:\n\n**Connections**:\n* 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.**\n* 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.**\n\n**Differences**:\n* We newly introduce the **HTMP operator** in the CSBM-H to investigate the behavior of heterophilic GNNs, which is beyond existing analyses.\n* We newly propose the **CMD** to measure the discriminability of CM, providing a **quantitative metric** to measure the quality of CM.\n* Further, we theoretically prove the **negative correlation between CMD and ENKL** of VMP, providing **formal proof** for the findings of existing works.\n* 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.\n* Through empirical evaluation, we find that **increasing CMD is a possible reason for the effectiveness of HTMP**.\n\nIn 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.\n\nReference:\n\n[1] Is homophily a necessity for graph neural networks? ICLR 2022.\n\n[2] Understanding nonlinearity in graph neural networks from the bayesian-inference perspective. NeurIPS 2022.\n\n[3] When do graph neural networks help with node classification? investigating the homophily principle on node distinguishability. NeurIPS 2023.\n\n[4] Understanding Heterophily for Graph Neural Networks. ICML 2024.\n\n[5] Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS 2020.\n\n[6] Graph neural networks with heterophily. AAAI 2021.\n\n[7] Heterophily and graph neural networks: Past, present and future. IEEE Data Eng. Bull. 2023.\n\n\n\n> **Question #1: The training/optimization dynamics of the compatibility matrix.**\n\nAnswer #3: We show the training dynamics of the compatibility matrix and GNN predictions approximately as follows:\n* For CM, we use the corresponding **CMD** to better show its trend of change since the matrix is hard to visualize.\n* For GNN prediction, we report **the accuracy of the pseudo labels** (pse_acc).\n* Since the CM and GNN predictions can be updated many times during training, we choose some of them to show the dynamics.\n\nThe results are as follows:\n|Dataset|Rom.|Rom.|Ama.|Ama.|Cha.|Cha.|Pub.|Pub.|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|**Update Step**|**CMD**|**pse_acc**|**CMD**|**pse_acc**|**CMD**|**pse_acc**|**CMD**|**pse_acc**|\n|Init.|0.740|0.501|0.456|0.574|0.424|0.564|1.391|0.587|\n|1|0.739|0.503|0.448|0.619|0.364|0.621|1.119|0.676|\n|2|0.434|0.554|0.242|0.670|0.341|0.584|1.113|0.693|\n|3|0.501|0.554|0.275|0.683|0.318|0.591|0.997|0.699|\n|4|0.575|0.647|0.286|0.695|0.187|0.594|0.847|0.711|\n|5|0.594|0.664|0.370|0.698|0.225|0.587|0.789|0.730|\n|10|0.608|0.714|0.424|0.716|0.246|0.659|0.847|0.808|\n|15|0.647|0.739|0.481|0.726|0.254|0.669|1.062|0.822|\n|20|0.687|0.755|0.535|0.731|0.418|0.674|1.168|0.839|\n|30|0.752|0.780|0.604|0.738|0.444|0.679|1.205|0.844|\n|40|0.806|0.798|0.622|0.741|-|-|1.211|0.847|\n|50|0.807|0.800|0.623|0.743|-|-|1.234|0.852|\n|100|0.826|0.858|-|-|-|-|1.383|0.935|\n|150|0.844|0.901|-|-|-|-|-|-|\n|Last.|0.859|0.919|0.626|0.746|0.488|0.682|1.507|0.938|\n\nAs the training process progresses, **the accuracy of GNN prediction gradually increases, while the CMD first declines and then rises**.\nThis 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.\nThe inaccurate predictions may impact the CM estimation for a while at the early stage, leading to the reduction of CMD.\nThen, CMD will gradually increase along with the accuracy of GNN prediction, and enhance each other.\n\n\n\n> **Question #3: The detailed investigation focuses on low-degree and low label rate setting.**\n\nAnswer #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. \n* 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**.\n* 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**.\n  \nThe details of the experiment are as follows:\n* 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.**\n* Baseline: We compare CMGNN with 2 base and 3 top-performance baseline methods, including MLP, GCN, GCNII, ACMGCN, and OrderedGNN.\n\nThe classification accuracies of methods are as follows:\n\n|Method|Roman-Empire|Amazon-Ratings|Chameleon-F|Pubmed|\n|-|-|-|-|-|\n|MLP|58.14±1.40|37.03±0.43|36.74±2.97|83.07±0.55|\n|GCN|33.53±0.77|37.32±0.52|36.91±2.22|83.95±0.62|\n|GCNII|63.27±0.72|39.93±0.87|38.40±3.27|**86.04±0.74**|\n|ACMGCN|59.93±2.03|39.96±0.81|37.43±2.84|85.54±0.79|\n|OrderedGNN|64.76±2.20|40.00±0.90|38.91±2.57|85.59±0.68|\n|CMGNN|**65.93±2.17**|**40.02±0.86**|**40.11±2.82**|85.62±0.94|\n\nConsistent with the results reported in the paper, CMGNN can also **achieve outstanding performance on the low label rate setting**.\n\n\n\n**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.**"}]

Author rebuttal:

Meta-review: This paper introduces CMGNN, which leverages a new structural–label metric, Compatibility Matrix Discriminability (CMD), to improve performance on heterophilous graphs through confidence-based CM estimation, virtual neighbor supplementation for low-degree nodes, and CM-aware aggregation. Experiments on 13 datasets with 19 baselines show consistent gains, especially under low degree or label rates, supported by robustness tests, ablations, and a unified codebase. While theoretical analysis is limited to simplified settings and some design choices seem engineered, the empirical breadth, clear motivation, and practical utility make the contribution strong. I recommend accept, with camera-ready improvements including clarifying theoretical scope, tightening exposition, and contextualizing the benefits and overhead of individual components.
Decision: Accept (poster)