What Is Missing For Graph Homophily? Disentangling Graph Homophily For Graph Neural Networks
Authors: Yilun Zheng
Sitao Luan
Lihui Chen
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Networks
Graph Homophily
Primary area: graph_neural_networks
TL;DR: We disentangle graph homophily from label, structural, and feature aspects and investigate their impact on the performance of GNNs

Abstract: Graph homophily refers to the phenomenon that connected nodes tend to share similar characteristics. Understanding this concept and its related metrics is crucial for designing effective Graph Neural Networks (GNNs). The most widely used homophily metrics, such as edge or node homophily, quantify such "similarity" as label consistency across the graph topology. These metrics are believed to be able to reflect the performance of GNNs, especially on node-level tasks. However, many recent studies have empirically demonstrated that the performance of GNNs does not always align with homophily metrics, and how homophily influences GNNs still remains unclear and controversial. Then, a crucial question arises: What is missing in our current understanding of homophily? To figure out the missing part, in this paper, we disentangle the graph homophily into three aspects: label, structural, and feature homophily, which are derived from the three basic elements of graph data. We argue that the synergy of the three homophily can provide a more comprehensive understanding of GNN performance. Our new proposed structural and feature homophily consider the neighborhood consistency and feature dependencies among nodes, addressing the previously overlooked structural and feature aspects in graph homophily. To investigate their synergy, we propose a Contextual Stochastic Block Model with three types of Homophily (CSBM-3H), where the topology and feature generation are controlled by the three metrics. Based on the theoretical analysis of CSBM-3H, we derive a new composite metric, named Tri-Hom, that considers all three aspects and overcomes the limitations of conventional homophily metrics. The theoretical conclusions and the effectiveness of Tri-Hom have been verified through synthetic experiments on CSBM-3H. In addition, we conduct experiments on $31$ real-world benchmark datasets and calculate the correlations between homophily metrics and model performance. Tri-Hom has significantly higher correlation values than $17$ existing metrics that only focus on a single homophily aspect, demonstrating its superiority and the importance of homophily synergy. Our code is available at https://github.com/zylMozart/Disentangle_GraphHom.

What Is Missing In Homophily? Disentangling Graph Homophily For Graph Neural Networks
Yilun Zheng', Sitao Luan', Lihui Chen
yilun001@e 0 ntu atu.edu..... sg, sitao. luan@mail. mwg.il............ ca, elhchen@ntu. edu. sg Naayyan Technological University, Centre for Info. Sciences and Systems; Mila Quebec Artificial Intelligence Institute; Corresponding Author
Abstract
Graph homophily refers to the phenomenon that connected nodes tend to share similar characteristics. Understanding this concept and its related metrics is crucial for designing effective Graph Neural Networks (GNNs). The most widely used homophily metrics, such as edge or node homophily, quantify such "similarity" as label consistency across the graph topology. These metrics are believed to be able reflect the performance of GNNs, especially on node-level tasks. However, many recent studies have empirically demonstrated that the performance of GNNs does not always align with homophily metrics, and how homophily influences GNNs still remains unclear and controversial. Then, a crucial question arises: What is missing in our current understanding of homophily? To figure out the missing part, in this paper, disentangle the graph homophily into three aspects: label, structural, and feature homophily, which are derived from the three basic elements of graph data. We argue that the synergy of the three homophily can provide more comprehensive understanding of GNN performance. Our new proposed structural and feature homophily consider the neighborhood consistency and feature dependencies among nodes, addressing the previously overlooked structural and feature aspects in graph homophily, To investigate their synergy, we propose Contextual Stochastic Block Model with three types of Homophily (CSBM-3H), where the topology and feature generation are controlled by the three metrics. Based on the theoretical analysis of CSBM-3H -HH,, we derive new composite metric, named Tri-Hom, that considers all three aspects and overcomes the limitations of conventional homophily metrics. The theoretical conclusions and the effectiveness of Tri-Hom have been verified through synthetic experiments on CSBM-31 real-world benchmark datasets and calculate the correlations between homophily metrics and model performance. Tri-Hom has significantly higher correlation values than 17 existing metrics that only focus on single homophily aspect, demonstrating its superiority and the importance homophily synergy. Our code is available at /https://ggtt gitttu...b...... com/ http:///tt.b...oe/yyaaaaaa////a/ coom//yylMoaart//isetaaaagggga/ Graaphh
In addition, we conduct experiments on 31
Introduction
Graph Neural Networks (GNNs) have been widely used processing non-Euclidean data due to their superiority in extracting topological relations [10 13 26
35.. They have achieved great success
on numerous real-world applications, e.g., recommendation [49 58 bio-informatics 21 20 and
telecommunication (34]. It is found that their success, especially node-level tasks, is closely related to the homophily assumption [47 72 38 43 36 711. i.e., similar nodes tend to be connected [17]. On the other hand, when dissimilar nodes are more likely to be connected, which is known as the non-homophilly/eteree
scenario, GNNs fail to capture the useful neighbor information and underperform Multilayer perceptrons (MLPs) 337. Several homophily metrics, such as edge homophily [72] [ and node homophily [50] were proposed, which were believed to be able to
recognize the difficult datasets 43 and measure the performance of GNNs 39].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

show that the conventional homophily metrics 11 50 are insufficient to measure the performance of GNNs: Luan et al. [38] show that the homophily metries cannot tell if GNNs work well under heterophily. Ma et al. [46] reveals that homophily is not necessary assumption for effective GNNs and they propose to identify "good" and "bad" heterophily to explain why GNNs still work well under heterophily. Luan et al. [39] discovers a mid-homophily pitfall, showing the performance of GNNs reaches the worst in a medium level of homophily instead of the lowest. Then, a crucial question arises based on the above studies; What is missing in our current understanding of homophily?
However, recent studies [46 39 51 40
In this paper, we fill the missing parts by investigating different perspectives of the "node similar- ity". Conventional homophily metries quantify the "similarity" as an indicator function of whether connected nodes share the same label while ignoring the co-existence of three basic elements in graph data: lahel, structural, and node feature information. The ignorance of structural and feature information leads to insufficient understanding and unsatisfactory alignment between homophily metries and GNN performance.
A complete understanding of graph homophily should include all the above three basic elements. To this end, we disentangle graph homophily into three corresponding aspects: label, structural, and feature homophily. Specifically, our new proposed structural homophily quantifies the "simi- larity" by considering the neighborhood structure consistency, and feature homophily measures the dependencies of node features across the topology. To investigate how their synergy affects GNN performance, we propose a Contextual Stochastic Block Model controlled with three types of Ho- mophily (CSBM-3H). The node feature generation process in CSBM-3H breaks the i..d assumption in previous studies [46] [9], which is closer to real-world scenarios 14 59 61. With the three metrics, CSBM-3H enables more comprehensive study on the impact of graph homophily than
previous analysis [46]]] 39 29 60).
From the theoretical study of CSBM-3H, we derive a new composite metric named Tri-Hom to measure the synergy, which includes all three homophily aspects. Through CSBM-3H, our theoretical analysis and simulation results both show that the performance of GNNs is highly influenced by Tri-Hom. It can help explain how the three types of homophily influence GNN behavior individually or collectively. In addition, our theoretical findings can explain some interesting phenomena observed in previous literature, such as "good" or "bad" heterophily 46 3X and the impact of feature shuffling on GNNs (9). To verify the effectiveness of Tri-Hom, we conduct experiments on 31 real-world datasets. The results show that GNN performance is significantly better aligned with Tri- Tri-Hom than the other 17 existing metrics that focus only on single homophily aspect. This implies that Tri-Hom can complete the absent parts in existing homophily metrics.
2 Preliminary
We denote G = (V,E) as an undirected graph, where V is the node set and E is the edge set. The graph has N nodes with C classes. The adjacency matrix of the graph is denoted as A E RR NxN
We use Age = 1 or Cuv E E to denote the existence of an edge between node u and v, otherwise Aur 0 or Eun $ E. Node degree vector is denoted
D E EN where D,, is the degree of node u. Node label vector is denoted as Y E R and its one-hot encoding matrix is Z E -NNx XC The number of nodes in class e is denoted
N. = [u Y.. c,u V}I. The neighbor set of node is denoted as Nv = {uleue E E}. The features of all the nodes is denoted as X E RN x where X.,: are the features of node with M dimensions. We use Ig E I Ex E and 1g R ExE to denote identify matrix and all-ones matrix with size E, respectively.
Graph homophily metrics are used to measure the similarity between connected nodes. Edge 1 and node homophily (50) are most commonly used metrics and are defined as follows,
72
hedge (G, Y)- PrueleueEE.. EE.Y.=Y.J. Pnode(G. (G,Y) 1 Evev
(uluENN.YY.-Y...
(1)
No
These metrics qualify the ratio of whether the labels of two connected nodes are the same in a graph. However, this definition of graph homophily only considers label aspect and neglects structural and feature aspects, resulting in a partial understanding of graph homophily. Therefore, we propose to disentangle the graph homophily as label, structural, and feature homophily in the next section.
Graph-aware models MM and graph-agnostic models M refer to the models that either utilize structure information or do not, respectively. For example, bascline graph-aware models
2

---

M such Graph Convolutional Network (GCN) 26], Graph Attention Network (GAT) [57] and GraphSage [16]. encode both graph structure and node feature information in each layer; the corresponding graph-agnostic models M are the Multilayer Perceptrons (MLPs), which only encode node features [39].
Structural-agnostic featurre refer to the node features X that are conditionally independent of graph topology A given Y, (X. TT A A structural-aware features indicate (x JKL A|Y).
3 Disentangled Graph Homophily
In this section, we first introduce the definition of disentangled graph homophily from label, structural, and feature aspects to complete the missing part of the graph homophily. Then, the next section, we will introduce how they collectively impact the performance of GNNs.
3.1 Label Homophily
Definition 1. Label homophily is defined the consistency of node labels across the topology.
Label homophily is the most widely used con- ventional metric of graph homophily and qual- ifies the similarity between connected nodes and v using an indicator function 1 (Y, = Y.). Most of the conventional homophily metrics focus on label homophily, including edge ho- mophily [1] [72). node homophily [50], class ho- mophily [33]. adjusted homophily [51], density- aware homophily 30), 2-hop neighbor class ho- mophily [5] and neighbor homophily [15].
(a) hr = 0.1
hb) = 0.5
(c) hc) 0.9
However, label homophily only focuses on the consistency of label information for connected nodes while neglecting structural and feature in- formation, which are two indispensable compo- nents of graph data. Hence, it offers only par- tial understanding of graph homophily, which cannot always align well with the performance of GNNs [46
(s) 0.1
hs) = 0.5
0hs = 0.9
38 39]. To capture the miss- ing structural and feature information and better understand graph homophily, we give the defini- tions of structural and feature homophily in the following subsections.
(g) hr = 0.7 (h) hg 0.7 (i) hr = 0.9
3.2 Structural homophily
For structural homophily, the "atom" informa- tion of node structural information instead of the label. It is meaningless to define the struc- tural homophily using the consistency across the graph topology as in the label homophily be- cause the structural information already contains the information from the graph topology. There- fore, we define the structural information as the consistency of structural information among the nodes from the same classes which better disentangles itself from the label homophily.
Figure Visualization of synthetic graphs gen- erated by CSBM-3H with varying levels of label homophily, structural homophily, and feature ho- mophily. The node colors denote node classes in sub-figure (a-f) and node features in sub-figure (g- i)
Definition 2. Structural homophily is defined as the consistency of structural information of nodes within the same class. The structural homophily in graph is defined as:
hs(9,8, = Σ hg.or where hs,e =1 a((S(u)lu u E V.Y. c})
Omaz
'There we do not consider the inter-class structural information because the structural homophily repre- sents a property of graph instead of the node distinguishability (39). The detailed discussion of the node distinguishability is shown in Section 4.2

---

where hs.c is the class-wise structural homophity for class ffncciin S measures structural information, a denotes standard deviation of structural information, and maz denotes the maximum value ofa. a.
In this paper, we quantify the structural information for node u through neighbor distribution (the class distribution of local neighbors) D. [Pu.1 Pu. Pu.cl. where Pu.k 10Y, [0Y=)) is the proportion of neighbors of node that belong to class A high structural homophily indicates that the graph-aware models leveraging structural encoding will have similar embeddings for intra-class nodes after aggregation, which are expected to outperform graph-agnostic models, irrespective of low label homophily. There are also some homophily metrics that focus on the structural aspect in previous studies, including label informativeness [51], neighborhood similarity [46), and aggregation homophily 38), which is similar as the structural homophily defined there.
IN..l
3.3 Feature Homophily
Previous ceature-based graph homophily metrics, such as generalized edge homophily (2] local similarity 77, attribute homophily [67), and class-controlled feature homophily [29], mainly focus on the consistency of node features across the graph topology, which is similar as the definition of Dirichlet energy in graphs. However, these homophily metrics feature consistency cannot fully disentangle itself from label homophily: Since the features of nodes in a graph are supposed to depend on their classes, when the graph shows high/low label homophily, the connected nodes are more likely to share the same/different labels, resulting in a high/low feature similarity. Therefore, these feature-basee homophily metries are dependent on label homophily. Such dependency contains redundancy, which decreases the useful information inside feature- based homophily and impedes our understanding of the relationship between node features and GNN performance.
To disentangle the feature effect from label and graph structure, we define the feature homophily as the dependencies of node features across the graph topology, thereby dissociating it from label homophily and structural homophily. Inspired by graph diffusion [6] and interactive particle systems [55] 64],
we have the -aantura--agnottcc unobserved feature X (0) and the observed structural-aware feature
X that satisfy the following relation
DO
X
Σ (WA)* (0) = (I -----A)-- X() t=0
The detailed process of this relation is given in Appendix B Here w E (- P(Aj p(Ay) is parameter that controls the feature dependencies, where positive, negative, zero value corresponds to an attractive relation, repulsive relation, or independence of the nodes with their neighbors in graphs [55] 64) The feature dependencies (wa) of t-order neighbors are introduced structural- agnostic features X (0). Finally, the state of all the nodes will converge to an equilibrium with structure-aware feature X. The in Eq. (3) is independent of the graph topology because no matter how the label homophily or structural homophily changes, w will remain unaffected. To disentangle feature homophily from label homophily and structural homophily, we define the feature homophily based on w as follows.
Definition 3. Feature homophily is defined as the degree of feature dependencies of nodes across the topology. For the linear case of the graph diffusion process with feature dependencies, the feature homophily for feature m satisfies
X 1.m -(1
1FFm A
P(A) -
X.m (0)
(4)
where p(A) is the spectral radius of A, X ~ p(X are the unseen structural-agnostec node features, and X p(X A) is the observed structural-awar -awae node features. The feature homophily for the whole graph is the averaged feature homophily for all the features
M
hr X,Y)
Σ hFm
(5)
M
Note that it is easy to control the feature homophily in the generation of synthetic graphs. However, since both hr and X., (0) are unknown in Eq. (4). one more condition is required to estimate feature homophily in real-world datasets. To address this issue, we consider the case where the
intra-class distances of X mm (0) are small. This case holds in lots of real-world scenarios [38 39

---

and we can utilize this property to estimate hpm without solving X., (0). Specifically, the feature homophily h F.mm for feature m can be estimated with the following optimization process
o (G, x.m Y) = arg minh Exvey. [l Xmm (0)) where x. (0) = =(1 Arrm Y,=Yo
m(A) A) X.m (6)
The estimation of feature homophily is invariant to the operations of feature shifts, scaling, or changing variance, where the proof is shown Appendix C This estimation process will be used in Section calculation.
Remark To better understand the definitions of three types of graph homophily, Figure T visualizes examples of graphs under varying h1. hss and hy: 1) Label homophily. As label homophily hy increases, as shown in Figures T a). (b), and (c), nodes are more likely to connect with others that share the same label. Particularly. high ht.. (Figure[e)) results in several clusters with distinct class boundaries, while a low ,t. causes nodes to more likely connect to nodes with different classes. 2) Structural homophily. As structural homophily hg increases, shown in Figures [d), (e), and (f), the neighbor distributions of intra-class nodes become more consistent. Therefore, a high hy expected to capture effective structural information with message aggregation. Interestingly, we also find that a higher hy makes a graph resemble planar graphs [3] and periodic graphs [9]. We hypothesize this phenomenon occurs because stable structural information leads more regular and meaningful patterns, which would be interesting to explore the connection between hş and these geometric properties of graphs in the future. 3) Feature homophily. Figures gg), (h), and (i) illustrate different levels of feature homophily (hg) within the same graph topology. Figure I (h) demonstrates that under a medium positive hF, features of some boundary nodes exhibit characteristics of both neighboring classes. For instance, a node on the boundary of the red class and the blue class appears purple, a mixture of these classes. A higher bF (Figure increases feature dependencies, particularly affecting more nodes closer to class boundaries. In social networks, positive hF indicates that people's opinions are influenced by their friends, resulting in similar characteristics. Conversely, a negative for causes nodes to become more dissimilar from their neighbors. As shown in Figure (g), a negative h creates a distinct boundary between classes. Additionally, for the intra-class nodes in Figure [] (g), the node colors differ in shades from their neighbors. This occurs because node features become more dissimilar due to the "repulsive force" rather than the "attractive force" induced by negative hp. For example, in online social media, people are likely to argue with those holding different opinions on certain topics. After such interactions, individuals may reinforce their original opinions, a phenomenon resulting from the "repulsive force" associated with negative hr.
4 Impact of Disentangled Graph Homophily
To study the model performance in a graph, the Contextual Stochastic Block Model (CSBM) has been widely used to study the performance of GNNs with controlled graph topology and node features. Previous studies [5T] 29 39. 466 on graph homophily generally adopt a modified CSBM to control the label homophily through assigning nodes with different probabilities that connect to the nodes from other classes. Then the node features are sampled solely based on the classes. However, this graph modeling, which only considers label homophily, has two drawbacks: First, the probabilities of nodes from the same class connecting to the nodes with different classes are uniform, which lacks diversity. Second, the sampled node features are independent with their structures ie, JL A which is uncommon in real-world scenarios where interactions influence the attributes of connected nodes [61 14 59]. Therefore, we propose Contextual Stochastic Block Model with three types of Homophily (CSBM-3H), a random graph generative model that integrates the three types of homophily (Section J.I. where the newly proposed structural homophily hg and feature homophily he can well address the aforementioned two drawbacks and fills the missing part of graph homophily. Then, Based on CSBM-3H, we theoretically study how the graph-agnoste and graph-aware models are affected by label, structural, and feature homophily metrics to explore their relationship and verify the effectiveness of proposed metrics (Section 4.2).
4.1
CSBM-3H
Graph Topology Generation Following the topology generation process in existing studies [39 60 we assume all the nodes are class-balanced and share the same node degree d. We use node homophily hr to control the label consistency across the graph topology and hss to control the consistency of neighbor distribution DM of nodes within the same classes. Then, the neighbor distribution can be expressed as:
5

---

1 1 hr, c-1 1c + (hy
1- hr c
DV E.[[ where S =
Ic
te
where DV E I RNNC is the neighbor distribution for all the nodes, S E BCx is a class-sampling matrix, and E RCxC is a noise matrix. Each entry of is a noise of neighbor sampling that follows
Gaussian distribution (0, (1haal²) The class-sampling matrix S should be legal in practice [60] i.e. Su. > 0 and Σ. S = 1. Then adjacency matrix A can be sampled from neighborhood sampling matrix A, Cdd DN where E[A,. = 1] (Ap)ur for each pair of nodes u, v. In this way, we control the label homophily ft, and structural homophily hs in graph.
Node Feature Generation. For any node in graph, we first sample its structural-agnostie features (0) E F from class-wised Gaussian distribution (0) Ny, (My, Σy,) with jay, E Rf and Σy, E RRPx F. We also assume each dimension of the feature vector is independent of each other, thereby Σy, E F=x is a diagonal matrix. Then the observed structural-aware features can be generated by the unseen structure-agne agnostic feature as described in Eq. (4)
4.2 Node distinguishability
Suppose we have the representations of node u as H.: - X.: for graph-aware models M and H..- = X.. for graph-agnostic models M Inspired by the principles of neural collapse 28 [27] and node distinguishability (39]. we quantify the impact of the aforementioned homophily metrics both the graph-aware models M and graph-agnostic models M by measuring the ratio of intra-class node distance to inter-class distance. To idcally distinguish nodes from different classes, smaller intra-class distance Dintra and larger inter-class distance Dimma (H) is preferred because this will reduce boundary nodes and increase the margins among classes. The metric is defined as follows,
D Dintra
H
Ey, M
H Ho H H
J
(8)
Dincer
H
E Ey
A smaller J indicates better node embeddings for the model performance and vice versa, which has been proved in [39]. With the proposed CSBM-3H, we can analyze the impacts of fı,, hg, and hF on M and M by studying their relations with J, which will be derived in the following theorems.
Theorem 1. In CSBM-3H, the ratio of the expectation of intra-class distance to the expectation of inter-class distance of node representations for graph-agnostic models M and graph-aware models M is:
J-H = (1+ JNJ and J (1+ JNJ
where IN Eree, (20(C-)) |KY mY J 1- 1 PCC "o Poo (160-1)))
C-1la²
1- M (
C-1
و + ال C-1 Ci c-
and Jg
J.. (See the proof in Appendix G.1
From Theorem I we can see that, IN is a normalized distance term which is a constant given the distribution of atructural-agostte features and is irrelevant with graph information; J, and Jg are controlled by the three types of homophily, which can reflect the influence of graph homophily on model performance. We name J- and Jh as Tri-Hom for M and M4 To study the effect of Tri-Hom in more detail, we take the partial derivative of JR with respect to hgg hys and h to show the analytical results of their influences (See calculation in Appendix G.5 G.6 and G.7
Theorem 2.1. The partial derivative of Jh with respect to label homophily hy satisfies,
8J7 0, hr E 10, t)) DR
(10)
2 0, hr E [2. 1]
Dhy
From Theorem 2.1 can see that, the worst performance of M is reached when h5 = = which
corresponds to the scenario with the highest number of unpredictable boundary nodes among classes. This finding explains the misalignment between label homophily and GNN performance mentioned
in previous studies [46] 38 39].
We also calculate the partial derivative of J, & and discuss the impact of three types of homophily on M 9
in Appendix

---

Theorem 2.2. The partial derivative of Jh with respect to structural homophily hg satisfies,
aJK Shs 2 0
(11)
From Theorem 2.2 we can see that, a larger hi consistently improves the performance of M This is intuitive for M because more consistent intra-class neighbor distributions will lead to closer intra-class node representations after feature aggregation. This conclusion also shown in Wang er al. (60], where the topological noise (which is inversely proportional to hş) has a detrimental impact on node separability.
Theorem 2.3. The partial derivative of Jg with respect to feature homophily hf satisfies,
0gk <0, 0, Thg
h E (0, ho) by E (hi, ht) and hp E (hp; 1) hr E (h 1I; hy E (hz, ht) and hp E (-1, if hf di hr E (h7, (t))) and hF = hF
0JA
> 0,
(12)
Thg
0,
The
where 0 hT < <h < 1 and -1 < hr < 1. The expressions and detailed calculation of hi, h and hp are shown in Appendix G.7
From Theorem 2.3 we can see that, when hy is high a graph, nodes with the same labels tend to be connected, thereby a larger hig makes the intra-class nodes share more similar representations and positively affect M when Jy is low in graph, nodes with the different labels tend to be connected, thereby larger he makes the inter-class nodes share more similar representations and negatively affect M when hy is on a medium level i.e., h2 E (hī, h an increase of hp will first improve and then reduces the performance of M with the cut-off point at hr hr. There the he is influenced by h1, hs, C, and p(A), and the h and A are influenced by hs, C, and p(A).
Remark Apart from the new findings mentioned above, Tri-Hom can help explain other interesting but under-explored phenomena of the graph homophily in previous studies, egg., 1) "good" or "bad" heterophily [46]. which states that GNN can still perform well in some heterophily cases; and 2) feature shuffling (29), which states that shuffling the node features randomly within the same class can improves the performance of GNNs on node classification. Our explanations with Tri-Hom are: 1) The occurrence of "good" or "bad" heterophily is due the fact that the model performance is influenced by a combination of hL, hp, and hg, instead of J alone. When the h is low, the graph-awars models can still achieve good performance with a high hs a low hF: 2) feature shuffling is due to the existence of the ceccuurallaware features of nodes. When hF >> 0, nodes are positively dependent on their neighbors. In this case, the nodes the class boundaries or class centers are the hardest or easiest ones to predict because of the feature dependencies. If we randomly shuffle the nodes inside their classes, the nodes at the class boundaries will be easier be classified because their features are more likely to be replaced by the nodes from the center, which are more distinguishable. For the nodes close to the class centers, it will be compensated by their neighbors.
Experimental Results
we conduct experiments on synthetic data generated by CSBM-3H to verify the conclusions from Theorem 2.1, 2.2, and 2.3, demonstrate the synergy of label h,, structural hs. and feature homophily hF and test whether Tri-Hom J can reflect GNN performance. In Section 5.2 we evaluate the effectiveness of Tri-Hom on real-worke benchmark datasets to test how well it can predict the model performance in real-world scenarios. addition, we calculate the correlation between Tri-Hom value and model performance and compare them with the results of other 17 existing metrics. The results show that Tri-Hom has a significantly higher correlation with the model performance, demonstrating the necessity of filling the missing part by disentangling graph homophily from three aspects.
In Section 5.1
5.1 Experiments on Synthetic Datasets
To verify our theoretical results in a more general case, we measure the performance of GCN on synthetic datasets, where we can casily control h hs. and fF. Specifically,
7

---

Mr, fig
MP,
Mr 0.8
MM fig
1.0
0.5
0.5
03
0.5
00
0.0
0.0
0.0
10
100
1.00
1.00
0.76
-10 R
10 0.
1.0
0.000
0.30
-18 0266
0.30
Ay
0.00
by
0.00
0300
(a) Numerical results of Tri-Hom
GON, ha 0.2
GCN, Av 0.4
GON, As 0.6
GON, Aa 0.8
Ln
10
1.
1/0
0.8
0.3
0.8
066
0.6
0.8
0.0
1000
100
1.00
L40
0.73
0.73
1.0
0.46
-1.0
1.00hho 0.0
05
10
0.25
0.50
-1.0
0.5
3.0
0.20
0.50
-1.0
05 1.0
0.26
0.50
(b) Model Performance on synthetic datascts
Figure 2: We measure the impact of label homophily hs. feature homophily hr, and structural homophily hy through numerical results of Tri-Hom Jh and simulation results of the node classifi- cation accuracy with GCN on synthetic datasets.
Synthetic Data Generation We generate the synthetic graphs using CSBM-3H with a given tuple (hz, hg, hr), where h2 E (0,0.1,......99.11 0.9,1}, hs E {0, 0.1...., 0.9, }} and hr {-0.8, 0.6,.... 0.6, 0.8). For each (hı, hy hr), we generate 1000 nodes with three balanced classes and the node degrees are sampled from uniform distribution [1, 10). For node features, we first sample the structural-annostic features from class-specific Gaussian distributions, then we use Eq. (4) to propagate these features across the graph topology with feature homophily hF to generate the observed structural -awae features as the final node features. Then, we evaluate the node classification performance of GCN (26) on these synthetic graphs. To get a robust evaluation and mitigate the numerical instability, we generate 10 graphs with 10 random seeds for each (hL, hg hF) and report the average and standard deviation of classification accuracy on validation sets. The detailed process of topology and feature generation is shown in Appendix E.I.I
Numerical Results of Tri-Hom To verify whether Tri- Tri-Hom, The can reflect the behavior of GCN, calculate its numerical results with the same setting as the synthetic graphs and make a comparison. Specifically, we set C = 3 and ((A) = 10 to mitigate the influences of varying numbers of classes and spectral radius.
Comparison and Analysis The results are shown in Figure 2 For a better demonstration, we only show the results for hs {0.2, 0.4, 0.6, 0.8) and each subfigure is slice of hs that visualizes the impact of h and hr on GCN and Tri-Hom. From the comparison of Figure 2a and 2b we have two main observations: 1) Overall, the impact of h hg, and hF on synthetic datasets aligns well with the numerical results of Tri-Hom- Jh The only difference is that hF seems have less impact on GCN. We speculate that this is because the parameters in the graph filter in GCN are optimized during the training process, while these parameters are simplified as a fixed value in the thcoretical analysis, leading to the difference 2) Our theoretical analysis of the impact of h hr and hys on Tri-Hom is consistent with GCN's behavior in Figure 2b Theorem 2.1 shows the worst performance of M is reached when h2 = c corresponding to the ravine in Figure 2b for hı; Theorem 2.2 shows an increase of hs consistently improves the performance of MMS corresponding to the overall increases of the accuracy in Figure from the left to the right; Theorem 2.3 shows the influences of hr to MS is determined by the hr Even if this is not obvious in Figure 2b we show more detailed figures of the individual impact of h1, hs, and hr in Appendix E.6 confirming the impact of hy in Theorem 2.3.
We also show the detailed influences of hr, hss and be individually to MLP or GCN in Appendix E.6 which correlates well with our theoretical results of the homophily impact.
8

---

5.2 Experiments on Real-world Datasets
In this subsection, we show the superiority of our proposed Tri-Hom over the existing metrics by studying the correlation between the estimated metric values and model performance real-world graph data.
Experimental Settings To verify the effectiveness of our proposed Tri-Hon and compare with existing metrics, we train baseline models, MLI GCN [26), GraphSage [16], GAT [57] and estimate metrics, Jn Jhh hy, hg, and (we use Mode in our experiments), on real- world heterophilii and homophilic datasets. These datasets include Roman Roman-Empire Empire, Amazon- Amazon-Ratings, Mineweeper, Tolokers, and Questions from [52]: Squirrel, Chameleon, Actor, Texas, Cornell, Wisconsin originally
from [50 53] and refined by [52 Cora, PubMed, and CiteSeer from [69]; CoraFull, Amazon-Photo Amazon- Corrtonn-omuuter, Coauthor- CS, and Coauther-Physics from (54] Flickr from [7]; WikiCS from
48]; Clog-Catalog from [68]; Oghn-Arxiv from [9:; Genius, Twitch-DE, Twitch-ENGB Twitch-ES,
Twitch-FR, Twitch-PTBR, Twitch-RU, and Twitch-TW from [32] S Besides, we also calculate other
graph homophily and performance metrics the benchmark datasets, the metrics include label-based
homophily: hedge [72], Amode [50]. helass (33), Ntdjj [51], /iden [30], 1/2hop [5], hnnii 15
structural-
based homophily: LI [51]. hNs [46,, hage [38]: feature-basee homophily: hGB 23 hLS--oo 77.
hLS-cue [7]. Patr [67]. hCF [29]; and classifier-based homophily metries [39]: hgR. hGNB. fasvM on
these datasets. The detailed definitions of these metrics are summarized in Appendix and the
details of all estimations are shown in Appendix 1.2
MLP
GCN
GraphSage
GAT
Metric
Rank
Cor.
p-value
Cor.
v-value
Cor.
p-value
Cor.
p-value
hedge
0.4441
0.0123
0.5663
0.0009
0.4737
0.0071
0.5344
0.0020
6.25
Pnode
0.4232
0.0177
0.5457
0.0015
0.4524
0.0106
0.5257
0.0024
8.00
helass
0.6078
0.0003
0.6120
0.0003
0.5790
0.0006
0.6169
0.0002
2.50
hadj
0.4972
0.0044
0.5486
0.0014
0.4932
0.0048
0.5396
0.0017
5.25
haen
0.0038
0.9839
0.1483
0,4258
0.0525
0.7791
0.1258
0.5001
19.00
hzwop
0.4517
0.0107
0.5182
0.0028
0.4692
0.0078
0.4870
0.0055
7.50
Anei
0.3961
0.0274
0.4793
0.0064
0.4473
0.01
0.4535
0.0104
10.75
LI
0.4502
0,0110
0,4992
0.0043
0,4270
0.0166
0,4731
0.0072
9.75
hNs
0.2898
0.1139
0.3603
0.0465
0.3452
0.0572
0.3671
0.0422
14.00
hagg
0.5201
0.0027
0.5617
0.0010
0.6040
0.0003
0,5832
0.0006
3.75
hs
0.0981
0.5994
0.2345
0.2042
0.1981
0.2854
0.2886
0.1153
17.50
hGE
0.3641
0.0440
0.4501
0.0111
0.4347
0.0145
0.4094
0.0222
11.75
by S-oo
0.3511
0.0528
0,4389
0.0135
0.4254
0.0170
0.4061
0.0234
13.00
hLS--enc
0.1272
0.4953
0.1101
0.5555
0.1117
0.5498
0.1168
0.5313
18.50
hatt
0.2022
0.2754
0.0990
0.5963
0.0735
0.6945
0.1121
0,5482
19.00
ber
0.2549
O. 1664
0.2890
0.1149
0.3154
0.0840
0.3167
0.0825
15.25
hF
0.4035
0.0244
0.4994
0.0042
0.4814
0.0061
0.4767
0.0067
8.50
hKR
-0.5318
0.0021
-0.3536
0.0510
-0.3854
0.0323
-0.3599
0.0468
22.00
hONB
-0.3796
0.0352
-0.2440
0.1858
-0.2828
0.1232
-0.2421
0.1894
21.00
hSvM
0.2430
0.1878
0.2741
0.1356
0.3320
0.0681
0.2961
0.1058
15.75
J 0,5800
0.0006
0.6286
0.0002
0.5978
0.0004
0.6136
0.0002
2.50
Jh
0.5471
0.0014
0.6650
0.0000
0.6223
0.0002
0.6731
0.0000
1.50
Table 1: Pearson correlation with p-value of all the metrics with model performance of node classification on 31 real-world datasets.
Correlations with Model Performance To find out which metric can better align with the per- formance of GNNs on graphs with different properties, in Table [ we show Pearson correlation between all the metrics and model performance on the 31 real-world dataset For example, to show
"We measure the performance of ML. verify the effectiveness our proposed J. and compare the performance gap between GNNs and MLP.
"See the dataset statistics, training details and model performance node classification in Appendix E.1
E.2
and E.3 respectively.
In addition to the Pearson correlation, we show Kendall's Tau rank correlation 4 in Appendix E. E.
Besides, we show the correlations between the metrics with performance gaps between GNNs and MLP in
Appendix E.9

---

how well hedge align with the performance of GCN, we measure the values of hedge (in Table and GCN performance (in Table on node classification tasks across 31 datasets then calculate their correlation. For each model, the homophily metrics with the best, second, and third highest correlation values are highlighted in red, blue and purple, respectively. To get more robust comparison results, we rank the metrics for each model and report the average rank in the last column.
Comparison and Analysis The results show that: 1) Jh achieves the highest correlation values with all models, much better than the other metrics that only consider a single aspect of graph data. This confirms the effectiveness of Tri-Hom in filling the missing part of graph homophily by taking all the three types of homophily hu, h., hy into account, providing a comprehensive understanding of graph homophily; 2) J/ -0 the Tri-Hom for M also shows high correlation values. This indicates the existence of structural-aware features of nodes in graphs, which justifies our modeling of feature homophily in CSBM-3H 3H. Compared with other variants of CSBM [46) (39,, which assume node features are conditionally independent of graph topology given node labels, the setting of CSBM-3H is closer to real-world scenarios. This is one of the important reasons that the metrics derived from CSBM-3H are better than the existing metrics.
Conclusions
In this paper, we study the missing components of graph homophily by disentangling it from label, structural, and feature perspectives. Compared with previous homophily metrics, the combination of the three homophily metries provides a unique and comprehensive understanding of graph homophily, Notably, our proposed feature homophily can measure the feature dependencies among nodes, fully disentangling itself from the label and structural homophily, which helps us analyze the disentangled impact. The theoretical study on CSBM-3F -H leads us to Tri-Hom, a combination of the three types of homophily. By investigating how each type influences Tri-Hom, we gain deeper insights into the effect of graph homophily on model performance and elucidate intriguing phenomena observed in previous studies [29] 60) The synthetic experiments on CSBM-3H verify the theoretical results and the effectiveness of Tri-Hom. The high correlation with GNN behaviors on 31 real-world benchmark datasets confirms the superiority of Tri-Hom over 17 existing metries.
7 Future Directions
In the future, it will be interesting to investigate the disentangled graph homophily in more general CSBM settings without some assumptions, e-g., uniform node degrees, balanced class, and linear feature dependencies. Additionally, the estimation of three types of homophily in unsupervised or weak-supervised scenarios would be important for label-scarcity cases. Since the theoretical results in the paper reveal a nuanced understanding of graph homophily, we briefly introduce future studies on model designs or applications as follows.
For the model designs, previous studies 38 50 42 of beterophill--oriente GNNs mostly focus on label homophily, neglecting structural homophily hg and feature homophily hy, that also influence GNN performance. For hg, the proposed structural information function S(.) could be replaced by any of the measurements regarding the task. Besides, the consistency of structural information could be different in the different classes, leading to the class-specific designs for each class. For hy. it will be interesting to propose new approaches to identify how node features neighhors from both the global and local perspectives and then design new methods to treat the graphs or nodes differently according to hp. Please refer to Appendix F.I for more detailed explanations of the future directions on model designs
influenced by their
For the applications, such social networks, recommendation systems, urban computing, proposed disentangled graph homophily could provide new insights. For example, in recommendation systems, the preferences of each user could be influenced by their neighbors. When people recognize or reject others' suggestions, it leads to a high hF or low hp, causing them more likely or less likely to buy specific items. Please refer to Appendix F2 for more details on the applications of the disentangled graph homophily.
8 Acknowledgements
Thanks to all the reviewers for their insightful comments. We also thank the organizers of NeurlPS for honoring us with the Scholar Award.
10

---

References
[1] S. Abu-EI-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan, G. Ver Steeg, and A. Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pages 21-29. PMLR, 2019.
[2] J. L. Ba, J. R. Kiros, and G. E. Hinton. Layer normalization. arXiv preprint arXiv: 10Xiv:6607.064500 2016.
[3] M. Barthelemy. Morphogenesis of spatial networks. Springer, 2018.
[4] D. J. Best and P. G. Gipps. Algorithm as 71: The upper tail probabilities of kendall's tau. Journal of the Royal Statistical Society. Series C (Applied Statistics), 23(1):98-100, 1974.
[5] A. Cavallo, C. Grohnfeldt, similarity (2nes): A graph structural metric indicative of graph neural network performance. arXiv preprint arXiv:2212. 13202, 2022.
Russo, G. Lovisotto, and L. Vassio. 2-hop neighbor class
[6] B. Chamberlain. Rowbottom, M. Gorinova, M. Bronstein, S. Webb, and Rossi. Grand: Graph neural diffusion. In International Conference on Machine Learning, pages 1407-1418. PMLR, 2021.
[7] Y. Chen, Luo, J. Tang. L. Yang, S. Qiu, C. Wang, and X. Cao. Lsgnn: towards general graph neural network in node classification by local similarity. arXiv preprint arXiv:2305.04225, 2023.
[8] E. Chien, J. Peng, P. Li, and O. Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint 2Xiv:2006607988, 2020.
[9] E. Cohen and N. Megiddo. Recognizing properties of periodic graphs. In Applied geometry and discrete mathematics, pages 135-146, Citeseer, 1990.
[10] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. arXiv, abs/ htbb///60.09375.... 2016.
[11] B. Finkelshtein, X. Huang, M. Bronstein, and Ceylan. Cooperative graph neural networks. arXiv preprint arXiv:23
2023.
[12] N. Gholinejad and M. H. Chehreghani. Heterophily awarr fair recommendation using graph convolutional networks. arXiv preprint arXiv:2402.088 03366, 2024.
[13] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 1263-1272. JMLR. org, 2017.
[14] P. Boadsmiith-Pinkhann and G. W. Imbens. Social networks and the identification of peer effects. Journal of Business & Economic Statistics, 31(3)2553 2244,226622222 2013.
[15] S. Gong, Zhou, C. Xie, and Q Xuan. Neighborhood homophily-based graph convolutional network. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pages 3908-3911 32,2, 2023.
[16] W. Hamilton, Z. Ying, and Leskovee. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[17] W. L. Hamilton. Graph representation learning. Morgan & Claypool Publishers, 2020.
[18] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-
778, 2016.
[19] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 18-22133, 2020.
[20] C. Hua, Y. Liu, D. Zhang, O. Zhang, S. Luan, K. K. Yang. G. Wolf, D. Precup, and Zheng. Enzymeflow: Generating reaction-specifi enzyme catalytic pockets through flow matching and co-evolutionary dynamics. arXiv preprint arXiv:2410.00327, 2024.
[21] C. Hua, S. Luan, M. Xu, Ying, Fu, Ermon, and Precup. Mudiff: Unified diffusion for complete molecule generation. In Learning on Graphs Conference, pages 33-1. PMLR, 2024.
11

---

[22] W. Jiang, X. Gao, G. Xu, T. Chen, and H. Yin. Challenging low homophily in social recommen- dation. In Proceedings of the ACM on Web Conference 2024, pages 3476-3484, 2024.
[23] D. Jin, R. Wang, M. Ge, D. He, X. Li, W. Lin, and W. Zhang. Raw-gnn: Random walk aggregation based graph neural network. arXiv preprini arXiv:2206.13880
2022.
[24] K. Z. Khanam, G. Srivastava, and V. Mago. The homophily principle in social network analysis:
A survey. Multimedia Tools and Applications, 82(6):8811-8855) 2023.
[25] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint
arXiv: 6980, 2014.
[26] N. Kipf and M. Welling. Sumi-supe classification with graph convolutional networks. arXiv preprint
2016.
[27] V. Kothapalli. Neural collapse: A review on modelling principles and generalization. arXiv preprint arXiv:2206. 04041, 2022.
[28] V. Kothapalli, T. Tirer, and J. Bruna. A neural collapse perspective feature evolution in graph neural networks. Advances in Neural Information Processing Systems, 36, 2024.
[29] S. Y. Lee, S. Kim, F. Bu, J. Yoo, J. Tang, and K. Shin. Feature distribution on graph topology mediates the effect of graph convolution: Homophily perspective. International Conference on Machine Learning, 2024.
[30] S. Li, D. Kim, and Q. Wang. Restructuring graph for higher homophily via adaptive spectral clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 8622 0630, 2023.
[31] X. Li, R. Zhu, Y. Cheng, C. Shan, S. Luo, D. Li, and W. Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Learning, pages 13242-13256. PMLR, 2022.
[32] D. Lim, F. Hohne, X. Li, S. L.. Huang, V. Gupta, O. Bhalerao, and S. N. Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 14220887229022 2021.
[33] D. Lim, X. Li, F. Hohne, and S.-N. Lim. New benchmarks for learning on non-homophilous graphs. arXiv preprint arXiv:2104.01 104.00404, 2021.
[34] Q. Lu, S. Luan, and X.-W. Chang. Geepnet: Graph convolution expectation propaga- tion for massive mimo detection. arXiv preprint arXiv:2004. /4886, 2024.
[35] Q. Lu, J. Zhu, S. Luan, and X.-W. Chang. Flexible diffusion scopes with parameterized laplacian for heterophilic graph learning, arXiv preprint arXiv:2409 208888880 2024.
[36] S. Luan, C. Hua, Q. Lu, L. Ma, L. Wu, X. Wang. M. Xu, X.-W. Chang, D. Precup, R. Ying, et al. The heterophilic graph learning handbook: Benchmarks, models, theoretical analysis, applications and challenges. arXiv preprint ar arXiv:2407.096
2024.
[37] S. Luan, C. Hua. Q. Lu, J. Zhu, X.-W. Chang, and D. Precup. When do we need graph neural networks for node classification? In International Conference on Complex Networks and Their Applications, pages 37-48. Springer, 2023.
[38] S. Luan, C. Hua, Q. Lu, J. Zhu, M. Zhao, S. Zhang, X.-W. Chang, and D. Precup. Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35:1362-1375. 2022.
[39] S. Luan, C. Hua, M. Xu, Q. Lu, J. Zhu, X.W. Chang, J. Fu, J. Leskovec, and D. Precup. When do graph neural networks help with node classification? investigating the homophily principle on node distinguishability. Advances in Neural Information Processing Systems, 36, 2024.
[40] S. Luan, Q. Lu, C. Hua, X. Wang, J. Zhu, X.WW Chang, G. Wolf, and J. Tang. Are heterophily- specific gnns and homophily metrics really effective? evaluation pitfalls and new benchmarks. arXiv preprini
2024.
[41] S. Luan, M. Zhao, X.-W. Chang, and D. Precup. Break the ceiling: Stronger multi-scale deep graph convolutional networks. Advances in neural information processing systems, 32, 2019.
[42] S. Luan, M. Zhao, C. Hua, X.-W. Chang, and D. Precup. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. arXiv preprint MxXiv2008.088844 2020.
12

---

[43] S. Luan, M. Zhao, C. Hua, X.-W. Chang, and D. Precup. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. In NeurIPS 2022 Workshop: New Frontiers in Graph Learning, 2022.
[44] M. Luenendonk. Niche to discount: 12 major types of retail stores & retailers. In FounderJar, 2023.
[45] Y. Luo, L.. Shi, and X.-M. Wu. Classic gnns are strong baselines: Reassessing gnns for node classification. arXiv preprint arXiv:2406.00 08993, 2024.
[46] Y. Ma, X. Liu, N. Shah, and J. Tang. Is homophily necessity for graph neural networks? arXiv preprint arXiv:2106.00 210220000066144 34, 2021.
[47] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415544)))) 2001.
[48] Mernyei and C. Cangea. Wiki-es: A wikipedia-basee benchmark for graph neural networks. arXiv preprini arXiv:2007.02901, 2020.
[49] R. K. Ong. W. Qiu, and A. W. Khong. Quad-tier -iee entity fusion contrastive representation learning for knowledge aware recommendation system. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM '23, page 1949-1959, New York, NY, USA, 2023. Association for Computing Machinery.
[50] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-gen: Geometric graph convolutional networks, arXiv preprint arXiv:2002.05225 2020.
[51] O. Platonov, D. Kuznedelev, A. Babenko, and L. Prokhorenkova. Characterizing graph datasets for node classification: -hotophily-heterophhil dichotomy and beyond. Advances in Neural Information Processing Systems, 36, 2024.
[52] O. Platonov, D. Kuznedelev, M. Diskin, A. Babenko, and L. Prokhorenkova, A critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv preprint arXiv:2302. 1640, 2023.
[53] B. Rozemberczki, C. Allen, and R. Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
[54] O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 10/118/11..000 1.05868, 2018
[55] D. Shi, A. Han, L. Lin, Y. Guo, Z. Wang, and J. Gao. Design your own universe: A physics-informed agnostic method for enhancing graph neural networks. arXiv preprint 2rXiv:2401.14500 2024.
[56] S. Suresh, V. Budde, J. Neville, P. Li, and J. 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 Knowledge Discovery & Data Mining, pages 1541-1551, 2021.
[57] P. Velicković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv preprint arXiv:1710.1090. 2017.
[58] B. Wang, J. Chen, C. Li, S. Zhou, Q. Shi, Y. Gao, Y. Feng, C. Chen, and C. Wang. Distri- butionally robust graph- recommendation system. In Proceedings of the ACM on Web Conference 2024, pages 3777-3788, 2024.
[59] G.-N. Wang. H. Gao, L. Chen, D. N. Mensah, and Y. Fu. Predicting positive and negative relationships in large social networks. PloS one, 1016))e01 2015.
[60]] J. Wang, Y. Guo, L. Yang, and Y. Wang. Understanding heterophily for graph neural networks. arXiv preprint 20 2024.
[61] Wang, H. Xie, F. L. Wang, L.-K. Lee, and M. Wei. Jointly modeling intra-and inter-session dependencies with graph neural networks for session-based recommendations. Information Processing Management, 60(2):103209 2023.
[62] K. Wang. Li, S. Wang, G. Zhang, K. Wang, Y. You, J. Fang, X. Peng, Y. Liang, and Y. Wang- The snowflake hypothesis: Training and powering gnn with one node one receptive field. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3152-3163, 2024.
13

---

[63] Y. Wang, S. Xiang, and C. Pan. Improving the homophily of heterophilic graphs for semi- supervised node classification. In 2023 IEEE International Conference on Multimedia and Expo (ICME), pages 1865-1870. IEEE, 2023.
[64] Y. Wang, K. Yi, X. Liu, Y. G. Wang, and Jin. Acmp: Allen-cahn message passing for graph neural networks with particle phase transition. arXiv preprint arXiv:2206.04337, 2022.
[65] C. Xiao, J. Zhou, J. Huang, T. Xu, and H. Xiong. Spatial heterophily aware graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2752-2763, 2023.
[66] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, How powerful are graph neural networks? arXiv preprint arXiv: 180000082, 2018.
[67] I.. Yang. M. Li, L.. Liu, C. Wang, X. Cao. Y. Guo, et al. Diverse message passing for attribute with heterophily. Advances in Neural Information Processing Systems, 34:4751-4763, 2021.
[68] R. Yang, J. Shi, X. Xiao, Y. Yang. S. Bhowmick, and J. Liu. Pane: scalable and effective attributed network embedding. The VLDB Joumnal, 32(6):1237--266: 2023.
[69] 7. Yang, W. Cohen, and R. Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
[70] H. Zeng. H. Zhou, A. Srivastava, R. Kannan, and Prasanna. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv: 2019.
[71] Y. Zheng, J. Xu, and L. Chen. Learn from heterophily: Heterophilous information-enhancee graph neural network. arXiv preprint 2rXXi::240317335 2024.
[72] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra. Beyond homophily in graph
neural networks: Current limitations and effective designs. Advances Neural Information Processing Systems, 33, 2020.
14

---

A Related Work on Homophily Measurements
In general, graph homophily metrics can be categorized as either statistic-based metrics classifier- based metrics. The former can be further classified into the homophily on label, structural, or feature aspect. The definitions of these metries are introduced as follows.
A.1 Homophily on Label Aspect
Edge homophily 72 measures the graph homophily at the edge level, which is defined as the fraction of edges in graph that connects nodes with the same labels:
Redge (9, Y) Hewo
Cuv E Yu
(13)
[3]
Node homophily 550 measures the graph homophily at the node level, where the homophily degree for each node is computed as the proportion of the neighbors sharing the same class. Then the node homophily for the whole graph is defined as the average homophily degree for all the nodes:
No., Yu YY.H
Anode ()
= [V]
Σ REV
du
(14)
Class homophily (33 addresses class imbalance by treating all classes equally. This metric mitigates the sensitivity of edge homophily and node homophily to the number of classes and nodes in each class. The definition of class homophily is given by:
EneVY =c VelUEN,,YY Y.)
N N
helass (0,Y) = C -
(15)
Eue(u|Y(=e)} du
Adjusted homophily [51] considers the probability of edge endpoint connecting a node with particular class and adjusts the edge homophily using node degrees, which is defined as:
Redge (G, Y) >
D
hady (9, Y)
(16)
D2 1 -- c== (2/ET)²
where De represents the total degree of class c, i.e,Ds = He Ya = c or Y, c, EE)
Density-aware homophily [30 is introduced as an improvement over class homophily, which only captures relative edge proportions and disregards graph connectivity. This limitation results in inflated homophily scores for highly disconnected graphs [51]. The proposed density-aware homophily aims to provide a more accurate measurement of edge density and defined as:
1 min (Co - -co
C
Idee (9, Y)
(17)
2
where Ça is the edge density of the subgraph formed by intra-class edges of class k and Ču is the maximum intra-class edge density of class k.
2-hop Neighbor Class Similarity [5]. Since the information of 1-hop neighbors might be less
representative or even misleading [5), 2-hop Neighbor Class Similarity extends the concept of "neighbors" from 1-hop 2-hop, which is defined as:
{u u E AAE) YoH
h2zhop (YYY)
1
Σ
(18)
M
du
NEV
where (222) = U NoN represents the two-hop neighbors of node u.
VEN,
Neighbor Homophily 15 is proposed to address the "good" and "bad" heterophily issue by consid- ering the dominant neighbors. The homophily score for any given node is based on the number
15

---

of nodes in which its class holds dominance among its k-hop neighbors. The definition of neighbor homophily in a graph is defined as:
max f/ol E 1 F0=1
hDN k.)
(19)
where A) represents the k-hop neighbors of node u.
A.2 Homophily on Structure Aspect
Label informativeness [51 measures the informativeness of neighbor's label for a node's label using condition entropy:
LI Y) Eonoor pe,, 02) log plares) ((c.).((2)) log((c)
Een,o p(c1, 02) log pog
(20)
E.F(c) log p(c)
where p(c1, 02) E(uY)eE SYY.=0,Y.E edge from class e₁ to class 02 and Pa. 2
represents mutual distribution for a randomly sampled
2
Da
represents the distribution of the node degree for class c.
Neighborhood Similarity [46] measures the similarity of the neighbor distributions between two classes. A high similarity of intra-class neighbor distributions and a low similarity of inter-class neighbor distributions ensure the neighborhood patterns for nodes with different labels are distin- guishable (46). Therefore, the ratio of inter-class to intra-class neighborhood similarity could reflect the performance of GNN
Ey. (D Ey. NY, DD (D
hNs(G, DV,, Y)
(21)
where No is the k-hop neighbors of node u.
Aggregation homophily 38 measures the ratio of nodes in graph that has a higher intra-class aggregation similarity than inter-class aggregation similarity. The aggregation similarity of node u and the multiplication of their neighbor distribution D.e. D The definition of aggregation homophily is given as:
1 115 Σr.=y D& (DN)T
Σx.r. D. .VER
DN Nags(S (9, DV Y)
|V| (4
2
[u|Y, = Y.H
Kujy, + Y.
(22)
A.3 Homophily on Feature Aspect
Generalized edge homophily across the graph topology:
23 defines the feature homophily in graphs the feature consistency
X X |X|||
hGE x)
Σ
(23)
ES
The difference between this homophily with edge homophily is that generalized edge homophily replaced the indicator function of two connected nodes in edge homophily, i.e., 1(Y,. Y.}, to similarity measurement of node features, i.e., sim(X., X.).
Local Similarity ( measures feature homophily at the node level based the hypothesis that nodes with similar features are likely to belong to the same class. The definition is given based on either cosine similarity
h ons (G, X)
1 1 V
Σ vEN.
X.X! X
(24)
dhe
NEV
"This definition is not directly given in the original paper [46). We define this ratio based on the proposition 46 that high intra class neighborhood similarity and low inter-class neighborhood similarity improves GNN performance.
16

---

or Euclidean similarity.
ALS-euc(9.X) =
Σ NEV
Σ
(-1 - 12
(25)
M
du
BEN:
Attribute homophily 67 considers the homophily with respect to each feature, which is defined as:
Battr,m (9, x.m) Enev Xu,
1
Σ
Xu,
EVEN. Xum
du
WEV
(26)
M
Nater (..))
= M
Σ
hattr, ,m (9, X ;,m,,
m=1
where battr represents the attribute homophily for the whole graph and hattr,m represents the attribute homophily for feature m.
Class-controlled feature homophily 129 considers the interplay between graph topology and feature
dependence through the disparity of nodes' expected distances random nodes with their neighbors, which is defined as:
Cor(G,X,Y
Σ
Σ vEN.
((, d(u, (u)))
[
du
NEV
d(u, V*)
((x,|)) - Y)
(27)
|
NE
Σv.=y, X,
x. Y X,,
[w|Y,, = Yo, E
where X Y represents class-controlled features and d(-) denotes distance function.
A.4 Classifier-based homophily
Classifier-based homophily (39 uses classifier capture the Ceature-based linear or non-linear information without iterative training. To determine when graph-aware models perform better than graph-agnostic models, a hypothesis test is conducted the original feature X and the aggregated features H, as shown below:
Hg Prop(G-aware G-aware model)= 2 Prop(G-agnostic model); H₃ Propo G-aawae model) < Prop(G-agnostic model)
The resulting p-value from this hypothesis test can indicate whether the performance of H is superior to that of X. Three types of classifier, Gaussian Naive Bayes, Kernel Regression, and Support Vector Machine are used in 339. which correspond to the metrics hGNB, lunn and hSv in this paper.
B Structural-Aware Node Features
This section explores the impact of graph topology node features. Unlike the data in Euclidean space, where samples are i.i.d. the data sampled from a graph for each node are structural-awe awwre iee 11 A Y.. To model the feature dependencies of nodes in graphs, we follow (55) and adopt graph diffusion process (6), which shown as follows
x(1) x(0) + / Ox(() dl,
(28)
where a (F(A) () X(0)
0t
Here the structural-agnostic node features X(0) p(X are sampled from the distributions
with respect to each class, while the structural-aware node features X(1 (L> 0) p( X YY, A) are
generated through the diffusion process. In (x(() the first term describes how the dependencies are introduced with a feature dependency function F (A) + N and the second term X(0)
preserves the node distinguishability. Then, based on the Eq. 28 we have
X x (0) + F(A)X
X()) (F(A)) X (0) (F(A)) X
(29)
17

---

We can also interpret the process as an interactive particle system into an equilibrium eventually. The equilibrium requires Eq.
where all node features collapse 29 have closed form when - oc. implying the spectral radius of the adjacency matrix ((F(A)) 1. This constraint also implies that
55
[F(A)) 2 [F(A){== for k > 0, which aligns with the common relations in graphs that nodes likely to have higher dependencies with their closer neighbors than with farther neighbors.
For simplicity and better understanding of feature dependencies, consider linear [5] and use a parameter w to control the feature dependencies ((A) = WA with a range of ((A) p(Aj). Then we can represent the structural-aware features
in
X
Σ (WA) x (I WA) -A) (())
(30)
t=0
C Properties of Feature Homophily
We further investigate properties of the estimation of feature homophily under specific feature transformations, including shifts, scaling, and changes in variance. The problem is defined as follows: In graph G {V,& } with N nodes, there node labels Y and node features X ,,m in dimension m. We can estimate the feature homophily hipm for feature X.m in dimension m as:
Σ (x,,((0) Xumm (0))², where X.m (0) = (T hF A X i.m P(A)
F (9, ,,, Y) min hF.m
M.DEV. Y.=Y.
(31)
Then we prove the estimation of feature homophily is invariant to the operations of feature shifts, scaling, changing variance.
A. Shifts
Let's consider a shift of node features X by constant vector C:
X i.m X,m C
(32)
Then we have structural-agnostic features as
F
X s,m (0)
I
A
X! i,m
p(A)
F A
I
(X m,m. + C)
(33)
p(A)
hFmm
X (0) +
I
A
C
p(A)
Then new estimation of Mm.m under this feature shift can be expressed as
W' (9, X k, Y)- arg min hymm U.VEV.
[X km (0) X x..m(00) (0)]
Yu=Yo
Xx,m + (I 1F A Cn
Σ
arg min
p(A)
U.EEV. Yu=Y.
hFm A p(A)
Xumm(0) (0)
(Xnm (0) - X (0)) (1 (I-
hFmm A (Cn, Cv)
arg min hemm
p(A)
U.EEV. =Y=Y
(34)
18

---

Since C' is constant vector, we have C₂ C. O. Next, we have
F (9, X i, Y)
arg min bF
Σ
((Xu,m X u.m (0)))
U,DEV. Yu=Yv
(35)
= p (9, X,,,, Y)
Therefore, we proved the estimation of feature homophily is invariant to the operation of feature shifts.
B. Scaling
Let's consider scaling node features X ,m by constant at
X axi.m
(36)
Then we have structural-agnostie features as
I h A ((A)
X mm (0)
(ax.m.)
hFm
(37)
A
X! i,m
p(A)
a (0)
Then estimation of h'y,m under this feature shift can be expressed as
p (9, X mm Y)= = arg min hy
Σ
X k,m (0) -x, x,m)())) (0))
u.VEV.
Yo=Y.
arg min
Σ
a² [Xum (0) - X (0)]
(38)
u.VEV.
Vu=Y,
arg min by
(Xam((0) - X (0))
V,DEV,
Y.=Yy
Since arg (-) is invariant the scaling, e.g. arg min (cf(x)) arg min (f())) have
Nr. (9, X Y) arg min
Σ
I(Xu,m Xu,m (0))}
hF.m
U,DEV.
(39)
Yu=Y,
h (9, X X,m, Y)
Therefore, we proved the estimation of feature homophily is invariant to the operation of feature scaling.
C. Variance Changing
Changing the variance of X.m be seen as the combination of scaling and shifts. Assume node features follow Gaussian distribution N (u, o²), after the operation of changing the variance from o² to Ba², we have new node features as
X mm VB(X.,m .m 11) +
(40)
where X,,. is calculated by deducing μ. multiplying VB, and adding μ. already show the estimation of feature homophily is invariant to the operations of feature shifts and scaling. Since the operation of variance changing a combination of scaling and shifts, we can conclude that the estimation of feature homophily is invariant to the variance changing.
19

---

D Impact of Graph Homophily on Graph-agnostic Models
In addition the impact of label homophily hy, structural homophily hş, and feature homophily hr on Graph-awand models as discussed in Section 4.2 we further discuss the impact on Graph-agnostic models through J in this section. Specifically, we compute the partial derivative of J, with respect hig hp, and bg reveal the analytical influences. (See calculation in Appendix G.2 G.3
and G.4
Theorem 3.1. The partial derivative of J with respect label homophily h, satisfies,
0J < 0,
hf E (-1,0) if [0.
(41)
Ohg 2 0,
From Theorem 3.1 similar, the increase Jı makes the features of intra-class nodes more distinguishable, thereby improving the performance of M $ Conversely, under negative hr iee, features of con- nected nodes become dissimilar, the increase of h2 makes the features of intra-class nodes more indistinguishable, resulting in degradation of the performance of M
that, under positive hp i.e., features of connected nodes become
Theorem 3.2. The partial derivative of J/P with respect structural homophily hg satisfies,
0J
20
(42)
ahs
From Theorem 3.2 that, since the existence of feature dependencies, a larger ls makes the structural-aware features more distinguishable among different classes, improving the performance of M
Theorem 3.3. The partial derivative J with respect to feature homophily hr satisfies,
< 0, hr E (0, h7);; E (h7,, h()) and hF E (hr, 1) if hf e (ht, hr E (h7, ht) and hr (-1, if hf E ht) and hr hF
aJ, g
0,
(43)
OhF
0,
where 0 << hi
hi and -1 < hj 1
From Theorem 3.3 we can see, how the impact of hp M is determined by hg. This result is similar to the Theorem 2.3 in the case of M The increase of hp makes node features more similar their neighbors. As result, under high h2, features of intra-class nodes become more similar, thereby improving the performance of M under a low h2, features of intra-class nodes becomes more similar, thereby reducing the performance of M
E
Experimental Details
E.1
Datasets
E.1.1 Synthetic Datasets
We show the detailed process constructing CSBM-3H in Algorithm First, graph topology is constructed with label homophily hy and structural homophily hg. Then, structural-aware node features are constructed with feature homophily hp. To investigate how three types of homophily influence the model performance,
generate graphs with h2 [0, 0.1. 1], hg [0, 0.1, 1). and hp E [-0.8, 0.66. 0.8]. For each given hz, hg. and hp, we generate the graphs with 10 seeds from J0, 1, ... 9] to mitigate random deviations. Each graph contains 1000 nodes distributed across 3 classes, with node degrees sampled from a uniform distribution in the range
For the random graph generative models with homophily, current studies 51 adopt a Contextual Stochastic Block Model with Homophily(CSBM) hy through assigning nodes with different probabilities that connect to the nodes from other classes.
generally to control label homophily
29 39
46
20

---

Algorithm Stochastic Block Model controlled with types Homophily(CSMM-31
Input:
Label homophily hı, structural homophily hig and feature homophily hr. number of nodes N, number of classes C. node degree D,
dimension of node features M, random seed ó, class-wised Gaussian mean μ [M1:.... Mcc" covariance Σ . Ecl" with pee E R and Ee E RM XM for class c. Output: Adjacency matrix A, node features X and node labels Y of synthetic graph. Initialize node features X, node labels Y, with X E R N.M, Y E R... Set random seed Φ. for to N do k [Uniform(O,, C)] Yn +
Sample node labels
end for Z +- One-hot(Y
One-hot encoding of node labels
Lhn $ + hclc + C-1 (1c Ic)
b Introduce label homophily h
D +- -Z
Construct neighbor distribution
for DW E DVV do uic
e~ (O, (=hel²
Introduce structural homophily hg
u.e DV +e
end for
D diag D)
Ap C DNDDDD D -T
Construct neighbor sampling matrix with node degrees
Ap + ma min(1, 1, Ap))
D> Bound with [0, 1] before sampling
A Sym Binarize (Ap) for to N do
Binarization sampling and symmetrize adjacency matrix >> Sample Structural- aggnosicc node features
Xn,: Normal( Ey.)
end for
X (Ic
2X be 2 a(A)
Introduce feature homophily hr
return A, X.Y
Then the node features are sampled solely based on the classes. However, these random graph generative models have two drawbacks: First, the probabilities of nodes connecting the nodes with different classes are uniform, which lacks diversity. Second, the sampled node features are independent with their structures i.., IL A which is uncommon in real-world scenarios where interactions influence the attributes of connected nodes [4 59. Our proposed CSBM-3H well address these drawbacks by considering hy and hF, thereby providing a more comprehensive and realistic model.
E.1.2 Real- World Datasets
We conduct our experiments on 31 real- datasets: Roman-Empire, Amazon-Ratings, Mine- weeper, Tolokers, and Questions from [2]; Squirrel, Chameleon, Actor, Texas, Cornell, Wisconsin
originally from [50] and refined by [52]: Cora, PubMed, and CiteSeer from [69; CoraFull, Amazon-
Photo, Amazon-Computer, Coauthor-CSS CS, and Seuuther-Physics from
[54]; Flickr from [70]: WikiCS
from 48 Blog-Catalog from [68]: Ogbn-Arxiv from 19): Genius, Twitch-DE, Twitch-
Twitch-ES, Twitch-FR, TWitch-PTBR, Twitch-RU, and Twitch-TW from (32] These datasets contain both the homophilic and heterophilic graphs that come from citation networks, webpage networks, purchase networks, image description networks, coauthor networks, actor networks, and social networks. The diversity of these datasets enables to evaluate the model performance in general case. For these datasets, we show basic statistics in Table 2 and the graph homophily metrics or model performance metrics in Table
E.2 Training Detail
For all the datasets, we randomly split the train, validation, and test set as 50%:25%:25% for 10 runs. We use the Adam optimizer (25) with learning rate 0.001. The maximum training epoch is set to 1000 with patience of 40 for carly stopping. To enhance performance, we incorporated
21

---

Dataset
#Nodes
#Fdges
#Features
#Classes
Average Degrees
Spectral Radius
noman-Empiree
22,662
32,927
300
18
1.45
4.58
Amazon-Rating
24,492
93,050
300
3.80
20.39
Minesweeper
10,000
39,402
7
3.94
7.99
Tolokers
11,758
519,000
10
2
44.14
392.36
Questions
48,921
153,540
301
2
3.14
95.31
Squirrel
2,223
46,998
2,089
5
21.14
206.02
Chameleon
890
8,854
2,325
S
9.95
78.05
Actor
7,600
26,659
932
3.51
37.37
Texas
279
1,703
10.98
Cornell
183
277
1,703
5
1,51
10.08
Wisconsin
251
450
1,703
5
1.79
11.88
Cora
2,708
10,556
1,433
7
3.90
14.39
CoraFull
19,793
126.842
8,710
70
6.41
25.63
CiteScer
3,327
9,228
3,703
2.77
13.74
PubMed
19,717
88,651
500
23.24
Flickr
89,250
899,756
500
10.08
83.06
Amazon-Photo
7,650
238,162
745
8
31.13
122.54
Amazon-Compuce
13,752
491,722
767
10
35.76
169.71
Coauthor-CS
18,333
163,788
6,805
15
8.93
24.60
Coauthor-Physse
34,493
495,924
8,415
5
14.38
51.18
WikiCS
11,701
431,726
300
36.90
149.77
Blog-Catalog
5,196
343,486
8,189
6
66.11
114.01
Ogbn-Arxiv
169,343
1,166,243
128
40
6.89
180.27
Genius
421,961
984,979
12
2
2.33
212.82
Twitch-DE
9,498
153,138
2,514
2
16.12
149.92
Twitch-ENGB
7,126
35,324
2,545
2
4.96
43.41
Twitch-ES
4,648
59.382
2,148
12.78
89.82
Twitch-FR
6,549
112,666
2,275
17.20
130.24
TWBtch-PTBR
1,912
31,299
1,449
2
16.37
99.09
Twitch-RU
4,385
37,304
2,224
2
8.51
76.26
Twitch-TW
2.772
63,462
1,288
2
22.89
143.43
Table Statistics on real-world datasets
skip connections [8] and layer normalization 2 in each layer. All models are trained on a single NVIDIA RTX A5000 GPU with 24GB memory. For hyperparameter tuning, we perform grid search on the validation set. The search space included the following hyperparameters:
Number of layers: [1, 2}.
Hidden dimension: [64, 128, 256),
Dropout rate: (0.2, 0.4, 0.6, 0.8),
Weight decay: (le-3, le-4, le-5).
E.3 Node Classification Performance
4hows the averaged mean and stand deviation accuracy of node classification performance for MLP, GCN, GraphSage, and GAT across 10 runs. Notably, graph-aware models M outperform graph-agnostic models - in most datasets. This phenomenon holds true for both homophilic datasets, such as Cora, Citeseer, and PubMed, and heterophilic datasets, such as Roman-empire, Chameleon-filtreed and Flickr. Consequently. relying solely on label homophily is insufficient to
determine the performance of M which aligns with previous studies 46 39
E.4 Tri-Hom for Graph-agnostic Models
We show the numerical results of Tri-Hom J, 9 for graph-agnostic models M 9 in Figure 3a where each subfigure slicer of hy that visualizes the influences of h and hp on JH For the impact of hr, hr. and hy individually, we can get the same conclusions as in Theorem 3.1, and 3.3. To validate our theoretical results of - in a more general case, we further show the impact of three types of homophily with MLP synthetic datasets in Figure 3b The results correlate well with our
22

---

Dataset
hadge
Raoaie
Acluss
hudi
Aden
Aghuv
bugi
L1
Rys
Aapo
hs
RomannEmmire
0.0469
0.0460
0.0208
-0.0497
0.4994
0.0750
0.2925
-0.6554
3.2151
0.5874
0.5271
Amazon-Rating Ratings
0,3804
0.3757
0.1266
0. 0.1386
0,5000
0.3686
0.5132
-0.1462
1.7253
0.4191
0.5256
Minesweeper
0.6828
0.6829
0.0094
0.0095
0,5000
0.6809
0.7999
0,0200
2.1402
0.3937
0,7070
Tolokers
0,5945
0.6344
0.1801
0.0944
0.4984
0.6510
0.7390
0.0047
2.1232
0.3217
0,5451
Questions
0.8616
0.8980
0.0790
0.1552
0.4999
0.9097
0.9342
0.0007
23.2975
-0.5480
0.5576
Squirrel
0.2072
0.1905
0.0398
0.0087
0.4907
0.2239
0,3191
-0,0316
1.2125
-0.1498
0.6030
Chameleon
0.2361
0.2441
0.0444
0.0276
0.4917
0.2739
0.4141
-0.0620
1.1318
0.1685
0.5367
Actor
0.2167
0.2199
0.0064
0.0024
0,4999
0.2135
0,3091
-0,2189
1,0833
-0.1476
0.3841
Texas
0,0609
0.0567
0.0000
-0.2822
0,4444
0,5429
0.6946
-0.2338
4,3899
0.4863
0,5158
Cornell
0.1227
0.1110
0.0383
-0.2526
0,4828
0,3989
0,5819
-0,4002
2.5518
0.4098
0,3676
Wisconsin
0,17778
0,1552
0.0461
-0.1909
0,4838
0.4239
0.5959
-0.2842
3,0825
0.6574
0.4687
Cora
0,8100
0.8252
0.7657
0.7717
0,5015
0.7407
0,8118
0.3240
14 1689687
0.8789
0.6164
CoraFull
0.5670
0.5861
0.4959
0,5552
0,5012
0.4383
0.5661
0,2895
44.7329
0,8626
0.6980
CiteSeer
0.7391
0.7166
0.6267
0.6673
0,5010
0.6849
0.8389
-0.0571
6.4521
0.6495
0.3909
PubMed
0.8024
0.7924
0.6641
0.6836
0,5002
0.7435
0.8179
0.2525
3,9050
0.6707
0,3792
Flickr 0,3809
0.3221
0.0698
0.1758
0,5000
0.3362
0.4657
0.0130
2,9056
0.1328
0.6086
Amazonn Photo
0.8272
0.8493
0.7722
0.7845
0,5036
0.6576
0,7112
0.6373
22.0358
0.7559
Amazon Computer
0.7772
0.8017
0.7002
0.6809
0,5015
0.5656
0.6439
0.4962
19.7670
0.9236
0.7628
Coauthor CS
0,8081
0.8320
0.7547
0.7846
0,5008
0.6862
0.7274
0.5292
43.5786
0.9474
0.7213
Coauthor-Physee
0.9314
0.9155
0.8474
0.8699
0,5005
0.8369
0.8655
0.6675
26.9190
0.9424
0,7330
WikiCS
0.6547
0.6774
0.5675
0.5786
0,5022
0.3710
0.4306
0,3340
9,3530
0.7431
0.6366
Blog-Cutalog
0,4011
0.3914
0,2680
0.2722
0,5029
0.2061
0,2479
0.0704
1.5237
0.5277
0.6987
Ogbu-Arxiv
0.6778
0.6353
0.42111
0.61558
0,5001
0,5013
0.6251
0.4535
51.7619
0.7367
0.5939
Genius
0.6689
0.5087
0.0229
0.1432
0,5000
0.7216
0,8078
0,0025
2,9629
0.0931
Twitch-DE
0.6322
0,5958
0.1394
0.1351
0,5001
0,5431
0.6568
-0.0029
1.1644
0.2426
0,5364
Twitch ENGB
0,5560
0.5452
0.0852
0.0823
0,5000
0.5235
0.6060
-0.0489
1.0328
0. 0.1485
0.3853
Twitch-FS
0,5800
0.6186
0.1468
0,1067
0,4995
0.5794
0.6712
-0.0051
1.5146
-0.4148
0.5700
Twitch-FR
0,5595
0,5739
0.0855
0.0856
0,5000
0,5349
0.6105
-0.0081
1.1885
-0.2628
0.6009
Twitch-PTBR
0,5708
0.5949
0.1196
0,1082
0.4996
0,5418
0.6213
-0.0047
1,2712
-0.3086
0,5801
Twitch RU
0.6176
0.6383
0.0424
0.0296
0.4998
0.6276
0.7470
-0.0086
1.7610
-0,5097
0.5698
Twitch-TW
0.5332
0.5500
0.0339
0.0331
0.5000
0.5212
0.5884
-0.0101
1.1133
-0.2150
0.6248
Dataset
hGg
Ags-cus
huter
hCF
hp
AXRI
AcNe
bayw
J
J
Romun- Empire
0,0257
0.0255
-8.095
0.0585
0.7781
0.1300
0,0000
0,0000
0,0000
0,9887
0.1519
Amazon Ratings
0,1146
0.1192
24.3967
0.6159
0.5976
1.0000
0.9992
0.0253
1.0000
1.0079
0.0080
Minesweeper
0,3330
0.3332
00.430
0.1856
0.0930
0.5000
1.0000
1.0000
1.0000
1.0533
0.6042
Tolokers
0,8093
0.7705
0.2957
0.1099
0.2228
1.0000
0.9982
0.0000
0.0000
1.0768
0.2814
Questions
0,4267
0.5544
-0.1423
0.0050
0,9060
0,7100
0.0000
0.6304
1.0000
1,1122
0.7210
Squireel
0,0138
0.0219
-0,1155
0.0007
-0.41133
0.0000
1.0000
1.0000
0.0000
1.0000
0.0481
Chameleon
0.0141
0.0135
-0.5673
0.0006
0.0819
0.0000
0.9893
1.00000
0.0000
1,0000
0.0272
Actor
0,1594
0.1566
-0,6630
0.0011
0,0229
0.0000
0.00000
0.0000
0.0000
1.0000
0.0289
Texas
0,3487
0.3448
0.1400
0.0008
0.00266
0.0000
0.0000
0.0000
1.0000
100000
0.1415
Cornell
0,3322
0.3391
-0,1455
0.0009
0.1393
0.0000
0.00000
0.0000
1.0000
1.0000
0.0782
Wisconsin
0.3414
0.3373
00.144
0.0009
0.2975
0.0000
0.0000
0.0000
1.0000
1.0000
0.0553
Cora
0,1677
0,1780
0.3338
0.0066
0.1410
0.1500
1,00000
1.0000
1.0000
1.0216
0,6881
CoraFull
0.1447
0.1604
.0.2263
0.0037
0,0052
0.0000
1.0000
1.0000
0.0000
1.0000
0.3069
CiteSeer
0.1906
0.2229
0.2208
0.0067
0,1487
0.7700
0.0000
1.00000
0.0000
1.0935
0.4090
PubMed
0.2719
0.2658
.0.2384
0.0099
0.2326
1.0000
0.0000
0.0000
0.0000
1,1443
0.5139
Flickr
0.3815
0.4084
0.0950
0.0027
0.0924
0,3000
0.00000
0.0000
0.0000
1.0000000000
0,9982
0.0007
Amazon-Photo
0.4878
0.4450
.0.0843
0.0016
0.1062
0.9100
0.0000
0.0000
0.0034
1,1435
0.9500
Amazon-Computer
0.4897
0.4402
-0.0829
0.0015
0.0337
1,0000
0.0000
0.0000
1.0000
1.1413
0.8955
Coauhor-CS
0.2944
0.3194
10.3
0.0056
0.2355
0.4400
0.0000
0.0000
1.0000
1.0644
0.8 0.8288
ConuthorPhysscs
0,3513
0.3723
-0.2160
0.0069
0.3741
0.8800
0.0000
0.0000
1,0000
1.1704
1.0292
WikiCS
0,3342
0.3916
-277.1482
0.0209
0.9998
1.0000
0.0000
0.0000
0.0000
1.0980
0.4899
Blog-Catalog
0.1223
0.1228
-0.1818
0.0001
-0.0430
0.0000
0.0000
0.0000
0.0000
1.0000
0.0249
Ogba-Araiv
0.8389
0.8649
-0.0546
0.0028
0.2352
1.0000
0.0057
0.0000
0.0000
1.0974
0.4470
Genius
0.6656
0.5909
002162
0.1585
0.1898
0.7500
0.0001
0.0000
0.0000
1.0521
0.1059
Twitch-DE
0,1961
0.1919
-0.2860
0.0006
0.0782
0.0000
0.0390
0.9831
0.0000
1.0000
0.3217
Twitch ENGB
0.2101
0.2001
-0.2836
0.0232
0.0000
0.0571
0.9191
0.0231
1.0000
0.1350
Twitch.FS
0,2039
0.1976
.0,2939
0.0007
0.0278
0.0000
0.3051
0.9999
0.0001
1.0000
0.2505
Twith&FR
0.2251
0.2117
.0,2850
0.0716
0.0000
0.9968
0.2459
0.0000
1.0000
0.2304
Twitch-PrrR
0,2135
0.2030
-0.2860
0.0009
0.0911
0.0000
0.3399
0.9971
0.0009
1.0000
0.2396
Twitch-RU
0.1925
0.1902
-0.2829
0.0006
0.0256
0.0000
0.9293
0.0307
0.4450
1,0000
0.3195
twitch-TW
0,1893
0.1914
.030887
0.0010
0.0271
0.0000
0,3110
0.0705
0.0001
1.0000
0.1935
Table 3: Graph homophily metrics and graph performance metrics on real-world datasets
23

---

MLP
GCN
GraphSage
GAT
Dataset
Acc-t Std
Acc-t Std
Acct Std
Acc Std
Roman-Fimpire
65.47+00.66
78.76+00.66
83.74+0.52
83.79++0.65
Amazon-Ratings
07.3
50.67++0.75
53.21+0066
51.72++0.59
Minesweeper
51.06:+0.92
90.16+0..99
90.74+0.57
90.55+0.67
Tolokers
73.52:10.90
84.5510.65
83.21
84.28
Questions
71.36:0..9
76.35+10.3
76.8410.97
77.83+0.75
Squirrel
1..1
4..24
40.37
40.06:13.12
Chameleon
41.47=13.38
43.10+2.73
41.88+4.32
41.70+5.99
Actor
35.97=11008
35.10=1.005
35.52+0.92
35.51
texas
75.26+44.61
72.28+7.41
79.60+5.47
74.72+4.27
Cornell
42.93+44.90
67.84+5..90
73.24+4.31
69.19+5.73
Wisconsin
80.98++4.81
78.2445.43
83.53+3.94
79.41+6.49
Cora
71.57+1.56
86.36+0.93
87.10+1.43
87.26+1.51
CoraFull
59.18+0.68
68.7440.76
69.06+0.71
70.12+t0.69
CiteSeer
1..36:11.30
76.44110779
77.07
16.96=1111
PubMed
87.26:10.24
89.1211.38
89.30=1.228
89.26::044
Flickr
46.83+1033
52.8010.43
52.41
53.52+0.37
Amazon-Phon
91.28=#0.1
95.16+0.54
95.72+0.35
95.59+0.24
Amazon Computerr
83.99=0.55
91.58=0.61
91.17=0.56
91.75=0.54
Coauthor- CS
94.5410.32
95.6810.23
95.53+0.22
95.58+0.24
Coauthor-Physice
95.18+0..7
9..93+0.25
96.83+0.30
96.73+0.28
WikiCS
81.38++0.51
85.20+-0.28
85.71+0.47
85.89+0.48
Blog-Catalog
93.95+00.70
96.07+0.57
96.49+0.64
96.02+0.544
Ogbn-Arxiv
58.02-10.30
73.91
73.39+0.25
73.82+:0.14
Genius
86.5310.07
90.5910.22
90.9910.17
81.92:44.75
Twitch-DE
67.65:10.93
7..26+1.00
70.14
1..46-L1.14
Twitch-ENGB
61.47=1.11
62.8
61.96
62.50
Twitch-ES
61.59+1..4
6..58+1.64
62.80+1.58
66.71
Twitch-FR
60.93:11664
64.8411.79
61.82+1.94
64.7742.29
TWiR
63.61+2.74
66.9011.58
65.05+1.98
1..60
Twitch-RU
50.34+1.94
53.7443.21
50.88+1.51
53.00+2.50
Twitch-TW
59.84+2.11
61.89+22.25
60.68+1.79
63.73+1.84
Table 4: Node classification performance on real-world datasets.
numerical results, showing the effectiveness of J in measuring the performance of M under the influences three types of homophily.
E.5 Numerical Results of Tri-Hom with Three types of Homophily
We show how the label homophily hL, structural homophily hs, and feature homophily he collec- tively influence the J and Th Figure in more general case, where the x-axis, y-axis, and z-axis denotes æ1, hr, and hy. A lighter color (close to yellow) indicates a larger J, 9 or Jh. which also implies better model performance. These numerical results align well with theoretical results of the individual impact on J J with respect to hL. hg, or hp. Furthermore, by observing the gradients in Figure 4 we can know how these three homophily metrics influence the model performance collectively.
E.6 Influences of A Single Type of Homophily on Synthetic Datasets
To verify our theoretical results, we show how the performances GCN and MLP are affected by three types of homophily individually in Figure 5 which shows the influences of label homophily h structural homophily his, and feature homophily hF on the node classification accuracy of GCN and MLP synthetic datasets. First, the top 3 subfigures show the influences of hG, under different hi and hs. With the increase hr, the accuracy of GCN first decreases and then increases with pitfall on medium-level of homophily, and the accuracy of MLP is dependent on the sign of hyp leading to

---

Ag
9,
M
19
0.8
0.
6.8
100
1.00
100
0.76
-10 A
10 6000
-1.0 0.000
0.30
18 0206
0.30
Ay
0100
by
6.0
0100
(a) Numerical results of Tri-Hom
MIP, Ap 0.2
MIP, Ag 0.4
MI.P, ho 00
MLP,, As 0.8
100
0.8
0.
100
1.00
L20
05
10
0.45
1.30
-10
-1.00-hm
0.0000
05
0.25
0.501
-1.
0.5
0.20
0.50
-10
05
100
0.26
0.50
(b) Model Performance on synthetic datascts
Figure 3: We measure the impact of label homophily hLs feature homophily hr, and structural homophily byg through numerical results of Tri-Hom Jn"" and simulation results the node classifi- cation accuracy with MLP on synthetic datasets.
84
14
16
(a) Graph-agnostic Models
(b) Graph-aware Models
Figure 4: The Influences of label homophily h,, structural homophily hs, and feature homophily hi graph-agnostic models and graph-aware models
the same results as in Theorem 1 and 3.1. Second, the medium 3 subfigures show the influences of lr. With the increases of hv, the accuracy of both of the GCN and MLP will decreases with low hr, increases with high li,,, and increases first and then decreases with a medium hr. The result also aligns well with Theorem 2.3 and 3.3. Last, the bottom 3 subfigures show the influences of hg. Even if the influences under different hy he would slightly vary, increase of fgg generally improves the performance of both the GCN and MLP, aligning well with Thcorem 2.2 and 3.2.
E.7 Visualization Real-world Dataset with Three Types of Homophily
To better visualize the impact of hr, hs, and he to graph-aware models M on real-world datasets, we show the performance of GCN on all the datasets with these homophily metrics Figure where ht, hr. and hy are shown as the x-axis, y-axis, and the size of the scatter respectively. Generally, the correlation of three homophily metrics with the performance of GCN is similar to our theoretical results in Figure 2a With the increase of fı, the performance of GCN decreases first and then
25

---

hp=-0.8, h2=0.9
h==0.0, My=00.9
h==0.8, 0,
1.0
1.0
1.0
0.9
0.9
0.9
Accuracy
0.8
Accuracy
0.8
Accuracy
0.8
0.7
0.7
0.7
0.6
GCN
0.6
GCN
0.6
GON
MLP
MLP
0.5
0.5
0.5
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1,00
0.00
0.25
0.50
0.75
1.00
hn
hr
1, hy=
=0=033 h0=
h1=0.9, =00
1.0
0.9
Accuracy
0.8
Accurscy
0.8
Accuracy
0.8
0.7
0.7
0.7
0.6
GCN
0.6
GCN
0.6
GON
MLP
MLP
MLP
0.5
0.5
0.5
-0.5
0.0
0.5
-0.5
0.0
0.5
-0.5
0.0
0.5
h,=0.1, -0.
h2=0.9, h.=
0,=0.9, h.=0.8
1.0
1.0
1.0
0.9
0.9
0.9
Accurccy
0.8
Accuracy
0.8
Accuracy
0.8
0.7
GCN
0.6
GCN
MLP
MLP
MLP
0.5
0.5
0.5
0.25
0.50
1.00
0.00
0.50
0.75
1.00
0.00
0.50
0.75
1.00
hg
lis
hs
Figure 5: The impact of label homophily h2, feature homophily hr, and structural homophily hs on the accuracy of node classification using MLP and GCN.
increases, with pitfall (as shown by datasets of Actor, Squirrel, and Chameleon). We also see that higher hi leads to a better performance when we fix hF and (as shown by datasets of Question with Amazon-phote and Cora with Coauthor-CS) As for the hp, since its influence is not so obvious compared with hy and hg as shown in Figure and the scarcity of real-world datasets, it is hard to see its influence in real-world datasets.
E.8 Influences of Class-wised Structural Homophily on Real-world Datasets
As shown in Figure 7 we investigate more nuanced influences of structural homophily hy without the interference of 1 and hp on real-world datasets with respect to each class. Specifically, we calculate node classification accuracy with respect to each class inside one dataset and show the alignment of the class-wised accuracy and class wised structural homophily hg. The results show for some of the datasets such as Citeseer, Amazon-ratings, and Coauthor-physics, we can clearly observe the accuracy increases with hg while for datasets such Corafull and Coauthor-CS, the general tendency of alignment with noises. We speculate that for Corafull and Coauthor CS, the hg is not as uniform as other datasets for the nodes in one class, leading to the noises.
can only
E.9 Correlation of Metrics with Performance Gap of GNNs and MLP
To investigate when GNNs are better than MI.,, we show the differences in the performance between GNNs and MLP in Figure 5 The results indicate that, among the statistic-based homophily metrics,
26

---

Arxi
1.0
Amazon-Ratings
WikiCS
0.9
Genius Tolokers
PubMed
0.8
Amazon Computer
0.8
Amazon-Photo
Questions
0.6
Flickr
0.7
CiteSeer
0.4
Minesweepet
Coauthor-Physics
Coauthor-CS Cora
0.6
0.2
Roman-Empire
Twitch-TW TTBR
Wisconsin
Twitch-FR
Twitch-DE
Twitch-Ri RU
0.5
Cornell texas
Actor
Twitch-ENGe
CoraFull
Twitch-ES
0.0
Blog-Catalog
Squirre
Chameleon
0.2
0.4
0.6
0.8
hl
Figure 6: Label, feature, and structural homophily metrics real-world datasets shown the x-axis, y-axis, and the size of the seatter respectively. The classification performance of GCN is denoted by the color of the scatters.
CiteSeer
Amazon-Ratings
Amazon-Photo
1.0
0.8
Accuracy
Accurocy
0.9
0.6
0.8
0.4
0.2
0.7
GCN
GCM
0.0
0.2
0.3
0.4
0.475
0.500
0.525
0.550
0.575
0.65
0.70
0.75
0.80
0.85
hs
hs
CoraFull
Coauthor-CS
Coauthor- Physics
1.0
0.98
Accuracy
Accuracy
0.9
Accuracy
0.96
0.94
0.8
GCN
0.7
GCN
0.6
0.7
0.8
0.60
0.65
0.70
0.75
0.80
0.65
0.70
0.75
0.80
hs
hg
Figure The influences of structural homophily to both the GCN and MLP for each class on real-world datasets.
27

---

GCN-MLP
GraphSage-MLI
GAT-MLP
Metric
Rank
Cor.
p-value
Cor.
p-value
Cor.
p-value
Bedge
0.2937
0.1087
0.1189
0.5242
0.2073
0.2632
8.00
Anode
0.2930
0.1097
0.1155
0.5362
0.2316
0.2099
8.33
Belass
0.0454
0.8084
0.0075
0.9678
0.0459
0.8064
19.67
hadj
0.1420
0.4461
0.0500
0.7896
0.1101
0,5555
16.00
hden
0.3164
0.0829
0.1096
0,5572
0.2537
0.1685
7.33
h2hop
0.1722
0.3543
0.0925
0.6208
0,0932
0.6178
15.67
hnei
0.2055
0.2675
0.1615
0.3854
0.1367
0.4632
11.33
LI
0.1338
0,4729
0.0012
0.9948
0.0674
0.7186
18.33
hNs
0.1716
0.3561
0.1585
0.3945
0.1736
0.3503
11.00
hagg
0.1220
0.5132
0.2497
0.1755
0.1542
0.4076
9.67
hg
0.3040
0.0964
0.2356
0.2020
0.4001
0.0257
2.33
hGE
0.2096
0.2577
0.2011
0.2779
0.1102
0.5550
11.00
hLS-cos
0,2130
0.2500
0.2080
0.2614
0.1299
0.4862
9.67
hLS-euc
-0.0299
0,8733
-0.0197
0.9160
-0,0159
0,9323
21.00
hattr
-0.2137
0.2484
-0.6644
0.1506
-0.1781
0.3376
22.00
hCF
0.0897
0.6313
0.1657
0.3730
0.1398
0,4531
13.00
hF
0,2338
0.2056
0.2224
0.2292
0.1701
0.3604
7.67
hKR
0.3582
0.0478
0.2650
0.1497
0.3336
0.0667
1.33
hGNB
0,2740
0.1357
0.1721
0.3546
0.2689
0.1435
6.67
hsv 0.0825
0.6590
0.2281
0.2171
0.1211
0.5162
12.67
J-9 0.1407
0,4503
0.1086
0.5610
0.0954
0.6096
16.00
JG
0,2903
0.1131
0.2333
0.2065
0.2860
0.1188
4.33
Table 5: Pearson correlation with p-value of all the metrics with the performance differences of GNNs with MLP of node classification on real-world datasets.
the structural homophily hg shows a strong correlation with the differences in the performance between GNNs and MLP. This is because hs measure the consistency of the structural information of nodes within the same class, thereby reflecting the differences in the performance between GNNs and MLP. We also observe that the lRR has the highest correlation with differences, confirming the effectiveness of the classifier-based metries measuring the differences in the performance between GNNs and MIP [39].
E.10 Other Types of Correlation
In our experiments on real-world datasets, we explore the correlation between all the metries and model performance. In addition to the widely used Pearson correlation, we employ Kendall's 's Tau rank correlation assess these relationships. Let æ and y be two observed variables with æ, y E R.. the Pearson correlation can be calculated as
ΣM (x. Z) 7)
P
(44)
(x; 2)2 EN (yi ))
where & and ÿ the means of and y respectively.
Kendall's Tau rank correlation 4 T can be calculated as
concordant pairs| |discordant pairs)
(45)
N(N 1)
where concordant pairs occur when the ranks of both variables agree, while discordant pairs oceur when they disagree.
Pearson correlation measures linear correlation between two variables, which is widely used and easy to interpret. Kendall's Tau rank correlation measures the similarity ranking between two variables, which has assumptions of the data distribution and are robust to outliers.
28

---

Metric
MI.P
GCN
GraphSage
GAT
GCN-MEP
GraphSage-MLP
GAT-MLP
p-value
p-valae
p-value
p-value
Coc.
p-value
Cur.
p-value
p-value
Rodav
0.0033
0.4839
0.3462
0.2129
B.3204
0.0100
0.400
00004
0.4065
0.0111
0.4634
0,0002
0.3161
00122
0.1878
0.1545
0.3118
0.0155
Aaless
0.3925
0.0016
0.194
0.0077
0.4022
0.0012
0.4237
0.0006
0.1570
0.2231
0.1785
0.1647
0.2387
0.0611
hadi
0.3892
0.0018
0.4667
0.001
0.4325
0.0005
0.4538
0,0002
0.2731
0.0314
0.2602
0,0407
0.2602
0.0407
Aasn
0.2430
0,0565
0.3634
0.037
0.3548
0.0047
0.3677
0.0033
0.2559
0.0422
0.2158
0,0770
0,2430
0.0565
0.3892
0.0018
0,4066
0.011
0.3720
0.0099
0.3935
0,0016
0.1785
0.1647
0.1742
0.1754
0.088
0.4578
0.0073
00029
0.3462
0.3591
0,0042
0.1871
0.2086
0.1031
0,1054
0.4178
LI
0.3462
0.0058
0.4753
0.0001
0.4609
0.0001
0.5054
0.0000
0.3505
0.0052
0.2774
0.0287
0.3204
0.0110
0.3720
0,0029
0.158]
0.002
0.1409
0.0091
0.1710
0.0001
0.2473
0.052]
0.1237
0.0006
0.2258
0.0770
hape
0.3849
0.0020
0.4452
0.0003
0.4624
0.00012
0.4495
0.0003
0.0022
1.00000
0.2129
0.0960
0.0525
0.8135
0.0667
0.6130
0.2387
0.0111
0.2129
0.0950
0.2744
0.0287
0.2172
0.0893
0,1613
0.2104
0.3075
0.0149
0.0073
0.0733
0.3247
0.1641
0,2860
0,0624
0.6369
0.3677
0.0033
0.359]
0.0422
0.3505
0.0052
0.3462
0.0058
0.1570
0.223]
0.3075
0.0149
0,0753
0 3666-
h1.5-aar
-0.2089
0.0181
-1.2387
D0611
-0.2550
0.0422
-0.2172
0.0893
0.04099
0.7616
-0.15 0.1527
0,2366
0.066K
0.478
-0.1183
0.3617
-0.2903
0,0218
-0.2817
0.0263
-0.2688
0.0343
0,2688
0.0243
-0.1666
0,0004
-0.2387
0.0611
her
0.2860
0,0240
0.2946
0.0199
0.3032
0.0161
0.3075
0.0149
0.1699
0,1865
0.3118
0.0135
0.1742
0.1754
0.0365
0.3071
0.4169
0.0399
hann
-0.4186
0.0010
.0.12%6
0.0107
10.44%
0,0059
-0.3279
0.0097
0.2416
0.0734
0.5631
0.2201
0.008
-0.2929
0.0222
-0.2317
0.0701
-0.2580
0.0440
-022361
0.0653
0.1093
0.3935
000874
0.9918
0.1487
0.2158
havar
0.1531
0.2364
0.1176
0,3631
0.139k
0.2797
0.1309
0.3114
-0.1753
0.1755
-0.0067
0,9589
-0.0688
0. 0.5948
J
0.4106
0.0024
0.4693
0.0005
0.4546
0.0008
0.4790
0.0001
0.1369
0.3108
0,2004
0.1378
0.1027
0.4472
0.3290
0.0090
0.5097
0.0000
0.4753
0.0001
0.5398
0.0000
0.2473
0.0521
0.2344
0.0661
0.2002
0.0407
Table Kendall's Tau rank correlation of all the metries with model performance of node classifica- tion on real-world datasets
The correlation of all the metries with model performance measured by Kendall's Tau rank correlation is shown in Table 6 which is similar as the results in Pearson correlation. Our Tri-Hom Te still shows the highest correlation with GNNs performance compared with other types of metrics, which confirms the necessity of disentangling graph homophily.
E.11 Correlation of Homophily Metries
To investigate the similarity of the information contained in graph homophily metrics and GNNs performance metrics, show the Pearson correlation of these metrics real-world datasets in Figure 8 We can see a high correlation among the homophily on label aspect (including hedges bnode helass: Radyy hddes hgmop- and hnes). These metries measure the label consistency across the graph topology, sharing a similar characteristic. This also holds for the homophily on the structural aspect (including LI, hNC. hagg. and lı), since these metrics measure how informative the neighbors are for the node labels. However, the Pearson correlation among the homophily on feature aspect (hGE. hLS-cos. hLS-coss hatty, hcF, and hF) is low. We speculate that this is because different types of feature aspect (hGE, hCF, and h2) or different similarity measurements (hLs and h could vary lot for real-world datasets.
F Future Directions
Each of the disentangled graph homophily, including label homophily, structural homophily, or feature homophily, derives many interesting directions for future research. In this section, we introduce these potential future directions from the perspective of model design and applications.
F1 Model Design
A. Label homophily
We discussed how label homophily influences GCN and MLP, providing both theoretical proof and empirical experiments. Our results show that GCN performs better than MLP in conditions of extremely low homophily (good heterophily [46)), but significantly worse than MLP in medium levels of homophily (mid-homophily pitfall (9)). This suggests that GCNs sometimes fail to extract effective topological information. To mitigate this weakness, it is preferable to add a residual connection to GNNs introduce a learnable parameter that allows the model to balance graph- and studies 666 45 52
information. The necessity of residual connections has been verified in previous
In addition to model design at the graph level, we can also consider a One-grained approach at the node level. Our results indicate that GCN does not always outperform MLP, suggesting that different
29

---

Nodg
1.0 0.38 0.68
0.77
0.58
0.81
0.71 0.79 0.47
0.18
0.28
0.37 0.4
-0.07
-0.07
0.16
0.58
-0005
0.12
0.08
0.72 0.81
Aunde
0.99
1.0
0.69
0.77
0.57
0.79
0.69
0.79
0.47
0.16
0.36
0:33 0.36
-0.08
0.18
0.55
-0.0
0.14
0.1
0.71 0.63
Natuxe
0.68
0.69
1.0 0.96
0.33
0.43
0.36
0.82
0.61
0.73
0.42 0.17 0.19 0.18-0.188..1
0.55
-55.0.9--0009
0.15
0.73 0.79
0.77
0.96 1.0
0.51
0.43
0.35
0.87
0.06 0.63
0.4
0.23 0. 0.13
-016
0.01
0.73 0.77
0.57
0.33
0.51
1.0
0.11 0.02
0.38
0.18
-0. 0.19
-..0 0.01 -011 0.09 0.19
0.09
0.12
0.34
0.27
Nohap
0.81 0.79
0.43
0.43
0.11
1.0
0.97
0.51 0.3
0.01
0.01
0.46 0.48
0.16 -0.05 0.11 0.44
-0.05
0.1 0.36 0.61 0.69
0.71 0.69 0.36 0.35
0.02
0.97
1.0
0.38 0.26
0.03
00.7
0.45 0.47 0.22 0.0
0.11
0.41
-0.03
0.12
0.4 0.55 0.62
LI
0.79
0.79 0.82 0.87
0.38
0.51
0.38
1.0
0.67
0.48
0.55
0:36 0.37 111115.01-00000 0.53
-0.06
0.08
0.7 0.78
Ays-
0.47
0.47 0.61 0.66
0.18
0.3
0.26
0.67
1.0
0.52
0.43
0.37 0.43 0.02 -0.16
0.16
0.36 -0.14-0.06
0.2
0.47 0.59
Nagg
0.63
0.52
-0.
00.01
-0.29
0.3
bs
0.28 0.36 0.42 0.4 0.19 0.01
-0.07
0.55
0.43
0.3
1.0 -..8-00.5
-0.1 -0.14-0
0..4400.3
0.07
0.21
0.04
0.2 0.21 0.52
Roe
0.37 0.33 0.17 0.2 -0.0 0.48 0:45 0.36 0.37
0.07
0.08
1.0
0.99
0.99-0.01
0.01
0.00
0.15
0.62
0.26 0 0.08 0.54 0.32
hgs--oo
0.4 0.36 0.19 0.23 0.01 0.48 0.47 0.37 0.43 0.06 0 0.99
1.0
0.07
0.03
0.24
0.63
0.28 -0.4 0.12 0.57 0.35
Ar.--m
-0.07-0.08-0.1
00.1-0.11111 -0.1 0.16 0.22 -0. 15 0.02 17 -0.1 -0.01 -0.07
1.0
0.01
0.01-0.56-0
0.56-...9
0.11
15 0.11
-0.070007
Ratts
-..07-0.09-0.168
-0.00 0.07-0..19
her
0.16 0.18
0.13
0.15 0.19 0.11 01 00.04 0.16 0.15 0.03 0.15 0.24
-0.56
0.26
1.0
2.28-0.26-00
0.29
0.21
0.34 0.24
hp
0.58
0.55
0.55
0.6 0.3 0.44 0.41 0.53 0.36 0.36
0.07
0.62
0.63
-0.29
0.35
0.48
1.0
-0.18
0.13
0.86 0.56
kgr
-0.05
-0.0
-0.19-0.16
1 0.09 -0.05 -..03 0.-00.06-0000 00.0061106000000 14 44.2999 0.21 0.266-0.2
0.11
0.35
0.26
1.0
0.41
0.01
0.01-0.33
-0.33 0.
haNu
0.12
0.14 -0.0900.00000 0.12 0.1 0.12 -0.06
-0.2 0.04 -0.42 -0.4 0.15 -0.11 0..99.0.36
0.41
1.0
0.15-0.2660000
havar aa
0.08
0.15 0.01 -..34
0.08
0.2 0.3
0.12 0.11 0.26 0.21
0015
1.0
0.18
0.72 0.71
0.73 0.73 0. 0.56 0.7 0.47 0.42 0.21 0.57 - 1.17....07. 0.07 0.34 0 0.33 0.26
0.
1.0
0.81
0.81 0.83 0.79 0.77 0.3 0.69 0.62 0.78 0.59 0.46 0.52 0.32 0.35 -0.07 -0.19 0.24 0.56 -0.1 -0.00 0.38
0.81
1.0
hader
hasde
hotera
bad)
highep
Barr
LI
byg
hapa
bi
here
la eose
Ivss Ale
hatte hop
he
hgn
hova
Bav
Figure 8: Pearson correlation between all the metrics, Each cell refers to the correlation between two metrics measured on 31 real-world datasets.
models could be applied to nodes with varying levels of label homophily. This type of personalized design has been explored in current GNN research on heterophilic graphs [2] 11], yet it holds significant potential for improving overall model performance.
B. Structural homophily
As mentioned in Theorem 2.2, the performance of graph-aware models improves with an increase in structural homophily. This leads to a crucial question: how can we deal with graphs exhibiting enhance current GNNs using
varying levels of structural homophily? To address this issue, passagg-passing calibration and graph rewiring.
4 and For the message passing calibration, several methods, such as GPRGNN g FB-GNNs
ACM-GNNs [38], propose adding an additional high-pass filter to capture local variations and details in the graph structure. When structural homophily is low, the high-pass filter captures the diversification of individual nodes. Along with a low-pass filter, these methods perform well on graphs with varying levels of homophily. However, the high-pass filters used in these methods cannot capture more complicated structural information. Since S(.) in structural homophily can be any measurement of structural homophily, this metric can evaluate more complex graph structures. In the
30

---

future, it is promising to design novel filters based on structural homophily to capture more intricate structural information and improve model performance.
For the graph rewiring, many methods (MVGCN 663. GloGNN 31, WRGNN [56] propose deriving new graph topology based node features embeddings. This operation improves the connectivity of nodes with similar semantic contexts, thereby enhancing model performance. However, this rewiring could connect nodes from different classes, which impedes GNN performance. To resolve this, we can measure class-wise structural homophily as shown in Eq. (2) and design adaptations for different classes, which will be particularly beneficial for glass-imbalancee graphs, such as in bot detection and fraud detection. Furthermore, we can adapt the structural measurement function S()). Since most current rewiring methods do not evaluate the informativeness of their rewiring basis (node embeddings with structural information), the proposed structural homophily can serve as a metric to evaluate which types of rewiring basis to select. For example, Geom-GNY (50) uses structural node embeddings to construct new neighbors of nodes and empirically determines the best approach. Our structural homophily could identify the most effective embedding approach before training GNNs. Therefore, structural homophily provides a guideline for graph rewiring methods.
C. Feature homophily
The feature homophily proposed in this paper measures how node features are influenced by their neighbors. To our knowledge, only few GNNs [55] consider these feature dependencies in their design. There is significant potential to explore how feature dependencies function in graphs. For instance, in social networks, people's opinions are affected by those around them. Identifying different user types while filtering out the noise introduced by their neighbors remains an open question. Both our theoretical results (Theorem 2.3) and empirical results (Figure 4) demonstrate the synergy between feature homophily and label homophily in enhancing model performance. Based on these findings, future work could focus on designing various graph filters optimize the objective in Eq. (8) by considering both label and feature homophily. Furthermore, feature homophily can explain the presence of node features, making it worthwhile investigate how much features are influenced by their neighbors, particularly in temporal graphs.
F22 Applications
Current real-world applications of graph homophily only focus on label homophily, which cannot align well with GNNs performance as shown in this paper and other studies [46, (39. To address this weakness, our findings provide a comprehensive view of 3 types of homophily, which could be applied in many real-world applications, such as social networks, recommendation, and urban computing.
A. Social Networks
In social networks, homophily is defined as the tendency for people to seek out or be drawn to others who are similar to themselves [24]. This definition primarily explains the consistency of certain characteristics of people within the network topology. Our proposed concepts of structural homophily and feature homophily offer additional insights into social networks.
Structural homophily refers to the similarity of the local neighbors of individuals of the same type, which can be used to analyze the friend circles of specific user groups. For instance, in fraud detection on social media, fraudsters often target older individuals who are more vulnerable to scams, resulting in high level of structural homophily. Therefore, we can identify potential fraudsters based on their structural connections. However, structural information can vary and may not always be informative. If fraudsters randomly select users to contact, identifying them through their neighbors becomes challenging, leading to low level of structural homophily. Future research could focus on measuring the level of structural homophily in social networks to better understand user behaviors.
Feature homophily, on the other hand, describes how individuals are influenced by their neighbors. Different types of networks exhibit varying levels of feature homophily. When people discuss similar events online, their opinions may be influenced by those they follow, leading to higher similarity in features with their neighbors, indicating a high level of feature homophily. Conversely, during online arguments, individuals connect with those holding different opinions. After such interactions, they may reinforce their original viewpoints, resulting in greater dissimilarity with their neighbors, indicating a low level of feature homophily. Investigating user behavior through feature homophily
31

---

can reveal underlying intentions and improve model performance. Furthermore, feature homophily provides valuable insights into the extent to which users are influenced by their neighbors.
B. Recommendation
Previous studies [22 22 recommendation systems using graph homophily have primarily focused on label homophily, which may result in misalignment with model performance, similar to what occurs in purely homogeneous graphs. To address this issue, it would be beneficial to define structural homophily within recommendation systems. For instance, we can measure the structural information of users within the same community by assessing the consistency of the items they have purchased. This approach allows us to determine whether this topological information can effectively predict links between users and specific items.
C. Urban Computing
recent study [65] proposes a method to measure spatial graph homophily in urban computing using spatial diversity score with direction-aware and distance-aware partitions. However, this metric focuses solely on label homophily, leaving a significant opportunity to explore structural homophily. Structural homophily involves measuring the consistency of geographic information among similar types of locations. For example, bookstores are often surrounded by coffee shops, where customers can enjoy coffee while reading books 44, indicating high level of structural homophily. Conversely, convenience stores might be located near a high-end fashion boutique, fast-food restaurant, or an office building. Since geographic information does not reliably indicate the presence of convenience store, it exhibits a low level of structural homophily. Future research could explore structural homophily in urban graphs to analyze the behaviors of various urban objects, aiding in better city planning.
G Proof of Theorems
We first specify the ranges of three types of homophily and spectral radius of an adjacency matrix, which are used for the approximation partial derivative process:
hy [0, 1], hy [0, |hpl (-1, 1), and p(A) >>
(46)
G.1 Proof of Theorem
Theorem 1. In CSBM-3H, the ratio of the expectation of intra-class distance to the expectation of inter-class distance of node representations for graph-agnostic models M 9 and graph-aware models M is:
J-8 = INJ, and === (1+ JNJR -1 respectively,
(47)
1- (he he may P0o L- 1 J2 a- +( (
where IN Er.r,, (20
IAY MY 11
J
0-
0-1
play
and Jh
(cl ( 2 للوطي ووميي Jn
Proof. We have the objective
J = Dintra (H)
Ey, =Y,.e
[H, H1.l2
(48)
Dinter H)
E Ey
|H 1111
Then, we derive the objective for graph-agnostic models M and graph- models M respec- tively as follows
We consider the spectral radius from general case in graph. Here the specified range is further confirmed by the values of p(A) in real- world datasets shown in Table 2
32

---

G.1.1 Graph-agnostic Models
For the graph-agnostic models, we let H. = Xu. The structural-agnoste feature m in class sampled from a Gaussian distribution Ne,m(eemm of o. We use N E RCxM to denote the distributions of structural-aware for all the classes with mean μ E RRCM and standard deviation o² IRCxM in the matrix form.
For the structural-awan feature m of node u, we have
X Xum
[Ic
Yi.
20
Σ (wS)**
N.m
(49)
Yu
(
hy + E)lc + (hz
1- 1-
7
C-1 /C
N N
Yn
Next, to simplify the expression, we let pi = 0-I
L-he + c and po = hr
1-44
C-1
X umm
whth
wile
+ + Nom
Y
Σ
1c) (c N'N
k==
i=0
Yu
k
(p1) --i (po)'1g Io
(50)
k=0
i=U
Y
k
Σ
polc -
Σ
k
(p)
) (po) (
N
k=ll
k=0
Yu
20
Σ
wh
[p - p (Cp) + po) Nom
Y,
[11 wpo) N + [[1 w(Cpi + po)) (1-wpo) -1] 1 NcNmm
Then have the feature distribution of node
Xu,m N (pu,, 0 pmm)
(51)
where
uyy,. = (1 wpo) -1 Ny., + C [(1 wCCpi + po)) po)) (1-wpo) 11 mm
(52)
of = =(1 - ---=-"p----- -00 + + [(1 w²((p + 16))= (1 - w²pp)) -1] ?
When two nodes and share same labels, i.e., Yu = Y... have
Xu,m Xu, N N(0, oy + oz
(53)
Then the expectation of intra-class distance of X can be expressed
M Σ
Ey Ey,=Y,,e ||x_ - xx,13
Ey. =Y..
(Xumm Xo,m)²
Lm=0
(54)
Ey, [Xu,m X2,m)
(1 (CE x()) 02
"Instead of deriving structural- aware features from an adjacency matrix, we sample aggregated distributions of features following previous studies (39 60) The binarization and symmetrization operations result in compound probability distributions, which make the analysis complex and almost unsolvable.
33

---

When two nodes and share different labels, i.e. F Yu, we have
Xu.m Xum ~ N(u..,, m 0% Ra.m + 0% x..m)
(55)
Then the expectation of inter-class distance of X be expressed
BY, |xx
x.11?]
BY..Y..
Σ
(Xam Xum) )2
Lm=0
M
= EyutY.n [(Xum - x2mm)
(56)
= 20 (1 - (C [pi] + pī))
022
+ [C(C - 1)) wPo)= -2
Σ
| uy.,:
Yu YY
Then, we come back to the objective by combining Eq. (54) and Eq. (56)
J By,,Y
H H ||
By,,Y
|H H 1|
By,,Yy,,e
|x, - X
(57)
Ey,
| X.
-(1+ Exety, (20 - py..
uy...l? (1 (CTE, [pi] + pŁ))
C-1
(1 wpu)?
Then we take back po. Pl, and w with hr, hss and hp
h1 C -
p
1 1- 11
(1 - h(s)
E, [ii
(58)
C-1
C
hF
w p(A)
So have
( (p(er)
PCC 2 c(1
+ (haC-113)
(1 ? (CE, [p + p())
C-1
C-1
(59)
w
hr
) (
p(A)
Then, we can rewrite the objective as
-1++1I
(60)
where
JN Ey.dy [20 | MY...
C-1 02
(p(A) ) (' 1-h1.) C (1-hg)² (1xC-112))
(61)
g,
C-1
( p(A) ) (2
2
34

---

G.1.2
Graph-aware Models
For graph-aware models, we have H D. EvEA(a) X., where X is the structural-aware features as in Section G.1.1 For the representation m in node u, we have
s
Hum
N
N.m
Ic - wS
Y
wwi WS - Ic + Ic
(62)
N
Ic WS
Yuu
w [[T - NN.
N m.m Y,
We take the result of (Ic wSw -1 N m, as shown in Eq. (50)
Then have
Ham [[(1 wpo)- 1 1)w INN + [(1 w(Cpi pol)
wpo) 10 1olw-o11o r.
(63)
Then we have the distribution of the representation of node u
Hu,m NPuum G )mmm)
(64)
where
iuy,,. = w (1 wpo) 1) + w (11 wCpp + +po)) (1 - w 14
oy.,. = w 2 w² (6) 1)0k.... mm + w- [[1 - (Cpt + +n)) (1 - w²pr) -1
(65)
When two nodes and share same labels, ie.YY, Y,,, we have
Humm Hum (0, of .... + o% m,
(66)
Then the expectation of intra-class distance of H can be expressed
By, [ H.ll3] BY,=Y,,e Haam H Hummll
(67)
22 ((1 w² (CEpp) + 16)) 1] -
When two nodes and share different labels, i.e., F Ye, we have
Hum Hom ~ N(jy uu..,,, o%.. + 03
(68)
Then the expectation of inter-class distance of H can be expressed
Ey.yYei [H,, H
Ey Yu.r
Humm Hnmml!
2w -2 0
w² (CE/pp) + -1 1] 1
(69)
mm
m PC(C -wpo) 112 Σ
|
Py,..ll
Yx
Then, come back to the objective
J Ey,=Yr.e H H
Eyn
H Th.-H.1l
H
-1 (70)
= -(1+ Σr.gr, -0)C-11)--
IAY.: my..:11
[11 wpo) 1
C-1 1o2
[(1 - w po + p())
35

---

Let's consider the term
(11 wPp) 1]
Pg
(1
(C + pŁ))
(71)
(L (CE + pε)) --1] (C pil + pb)
(1-wpo)
(CEpp In thereby we simplify the expression as
We notice the second term
(1-wpo)
[(1 wP 1]2
pό (CE
Tnd
(72)
(1 - (CR + 16))
+ P
Then we take back po. Pl, and w with hr, hs. and hp as in Eq.
58
(1 wpo) - 112 (1 (CE + -6)) (C( (0(T-1) ) C
-
h,C CCC1 )
c-1
J
(73)
- hzl²
/
)2)
C-1
Then, we can rewrite the objective as
J = =1+ (N+JNN
(74)
where
IN SYuXY;10C(C 1)]-1
my
mYmil
C-1 r2
(75)
1xC-1)²
Jh (C(1-AA + C (1-)
T
hs)²
(h,C (kxC-1)2)
C-1
C-1
G.2
Proof of Theorem 3.1
Theorem 3.1. The partial derivative J. with respect to label homophily by satisfies,
0J,9 << 0, hf E (-1,0)
(76)
ahg 2 0,
if (0,
Proof. For the graph-agnostic models, we take the partial derivative of J-9 with respect to hy
OJ,- 0 - h ( h-)(- (2) 20 11) 1)) Thg
- (-h+ Tr.UU
(77)
Th.
OJ.
Take the approximations of Tr,UP and DOWNOWN are given Eq. back to
we have Ohh
aJ,"* Thg
-2Ch h-) + (heC +)] 2Ch 2Chh(((()(()(CCCCC (((A)(C - 1)]2
(78)
20
hF
p(AA(C- 1)]
It is casy to see
20
> 0, so the sign of
aJ,79 Ob, is solely depend on hg. Therefore, have
OJ,99
< 0.
if (-1,0)
(79)
Thg
N 0, if hr [0,
36

---

G.3 Proof of Theorem 3.2
Theorem 3.2. The partial derivative of The with respect structural homophily hg satisfies,
0J h Ohs
2 0
(80)
Proof. We take the partial derivative of Jn" 9 with respect to hg
0J
20
(AA)
2 1 (1
hs)
0hs
1 - p(A)) (
C,
(81)
C-1
From Eq.
(46). we have
(A
>0, h3 2 0, and (1 - his) 2 0
(82)
P(A) (
((
aJ,00 8hg
Therefore, we can approximate
that satisfies
0J,-
2 0
(83)
0hs
G.4 Proof of Theorem 3.3
Theorem 3.3. The partial derivative Jp with respect to feature homophily he satisfies,
< 0, hf e (0, h, E (h7, ht,) and hF E (hr, 1) > 0, if hf E (ht 1]; E (hī, ht) and hF h-1 if hf E (h7, ht) and hp hF
0J Öhr
(84)
0,
where < hī < ht
and < hr <
Proof.
We take the partial derivative of J,," with respect to hy
05.99 OhF
- (C(0-b))*+(CC-I)((--n) (hapl C11
+2
Th.up
T K.DOWN
(85)
where
Tr,UP ((A))(C - 1)2 (1 hs)² (hLC - 1)²)
(86)
T DOWNO
- 11)
Next, we approximate TH,UP and Tr.DOWN with Eq. (46)
TH.UP & (p(A)(C 1)}²
(87)
To.DOWN p(A)(C
Then take back to Eq. (86)
OJr 4
2hF (O12-11 + C (1h + (x(-))2))
+2
0-1 p(A)
OhF
(²(A)
(88)
2(hr hF)
(c(L + - h2)2 + Ax(-1)3) -1
((A))
37

---

where
hrC-1 p(A)
hF C(L c-1 hi)²
C-1
(89)
(
aJ Dhy
As result, the sign of satisfies the following conditions:
0, if hr < hr
0J, ş
0,
hp hF
(90)
Ohr
0,
hF hF
Then discuss the influence of hr this case, we have
aJ The
If
1, then
85, ShF
0 holds vhr (-1, 1, 1). In
-ca h1 C c c-1 -
hs)² + hrC
C /
-1
C >0
C (()
(91)
The solution of this condition for 1ı [0, is h2 ht. where
ht 4C+0(C 1)p(A)
1)p(()) -C----C----NNCC-----DD0---------
2C(C+1)
(92)
Conversely, If hf -1, then
05 Ohe
holds vhr (-1, 1). In this case, we have
(al c c C
h
C
(1 hg) + hr ArC | +
C₂C
C C-1
C-1 >
(93)
The solution of this condition for h2 [0, is h2 h where
h 4C--ICC-DA(AA+//C---C---- 10--A//00C00-1111---11101-1-1--0 hs
20(C+1)
(94)
is easy to show that < hī < hy So far, we already know that Ohr > when h2 > h
05,
and -J.=0 Thi < 0 when hr, < by for all hp (-), Then, for hy < kh, < h the sign of
05
The is
dependent on hr as shown in Eq. 88
In conclusion, we have
< 0, hr E (0, hz E (hī, hi) and hr E (hr, 1)
OJ," Ohf
> 0,
hr E (ht, h|; E (h7, bi) and he E h-1,hr)
(95)
0, if E ht) and hr hr
G.5 Proof Theorem 2.1
Theorem 2.1. The partial derivative of Th with respect to label homophily hg satisfies,
aTk < 0, if hr. E [o. t Th 2 0, hf E [
(96)
Proof. For the graph-aware models, approximate the J with Eq. 46
(1 [
be )(C + ((= 2
Jg
(C(L-hg + c(l- + ( 1
p(A) ) (
(97)
C-1
(C(1-he)) 2 0 1g) (b(C)1)2)
0-1
38

---

Then we take the partial derivative with respect to h
0Jh
(1 (2
1)h2
+
hL
thg
(C- -) (C 2) h₂)²
(C 1)a
(98)
(C 1I4
We that the first term monotonically increases with respect hr and the second term is always positive for h E [0, 1). So we have
aJk << 0, if hr [0, )) 1h, 2 0, if hr E [ 1]
(99)
G.6 Proof of Theorem 2.2
Theorem 2.2. The partial derivative of Jh with respect structural homophily hs satisfies,
0J 2 0
(100)
ahs
Proof. We take the partial derivative of Jh with respect to hF
0JH
h2C C-1 hg)
Jn"
Öhs
(C(1-14-)
CLLhho + (
(101)
h
0J
(C(1-11) + (1-b8)²
C-1 + h1 (x)))
Öhg
C-1
From Eq. (46). we have
hrC-112
2C (1 hs)
by h,C-1p )²
C-1
2 0 and
20
(C 1-h1 hr. 2 + C 11
(2
(C( ) C (- (x(_))12)
C-1
C-1
(102)
Together with J and
0J, Ohg
2 0, we can approximate
a 8ky
a
2 0
(103)
Ohs
G.7 Proof of Theorem 2.3
Theorem 2.3. The partial derivative Te with respect feature homophily hp satisfies.
aJR Thg
< 0,
hr E (0, hz E ht) and he E EhF, 1) hr. E (h 1|:hr E (17, hit and hp E (-1, if = - hr E (h7,, 17)) and hp hr
aJk
>
0,
(104)
DhF
where 0 < hī < <ht < and -1 < hhr 1. The expressions and detailed caleulation of h7, ht. and he are shown in Appendix G.4
Proof. For the graph-aware models, take the partial derivative of Th with respect hr
0Jg
h,C-1 )
a5.9
C-1
(105)
Ohp
(C(1-44)
C (1-ke) hg)2
(b
ÖhF
C-1
39

---

0, the sign of a5g
a ahs is the determined by the
Since the term (0l - (ا6ممم)
except for h2 = J. which leads to the similar results as graph-aware models
agh < 0,
if hy E (0,h hy E (h h() and he E Ehp,1) 1) 0,
Dhg
a3h. >
hf (hī. 11: hy E (h ht) and hp E h-) hf = t hr E (hī, k and hp hF
(106)
Tbg
a3h -0
40

---

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]
Justification: We accurately answered the claims and contributions in the abstract and introduction, including why we shouldn't t discard label homophily and the superiority of disentangled homophily.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
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 of the work performed by the authors?
Answer:
[Yes]
Justification:
We discussed the limitations in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiattinn 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 the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, 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 faimesss.
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 complete (and correct) proof?
41

---

Answer:
[Yes]
Justification:
We provided the necessary assumptions for our proofs.
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 proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
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 not)?
Question:
Answer: [Yes]
Justification: We provide the reproducible code of our experiments, including node classifi- cation and homophily metrics.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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, descríbing 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, 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.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or 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., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
42

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the datasets used in this paper public. Our provided codes well reproduce the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc.
aablic/guudees/Cddeubbbisss www.sssinnooiiilloooooo for more details.
While encourage the release of code and data, 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 NeurlPS code and data submission guidelines (https
/ wwtps/cccppplgguuuiiaeeeae
Stteee///ooSSSSeissSioica www.ssssiicgcyy 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 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 experimental settings are shown Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the accuracy and standard deviation of the node classification performance with 10 runs with random splits. We report the p-value for the Pearson correlation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
43

---

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 the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [No]
Justification: We only provide computer resources used in our experiments. We didn't report the memory and time of execution because the main focus of this paper is to disentangle graph homophily instead of proposing a new method.
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 of 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 it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: All the data used in this paper is public and the research doesn't 't violate the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on improving homophily measurement, which irrelevant to societal impacts.
44

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper focuses on disentangling graph homophily, which is more concep- tual and has no such risks.
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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We provided the necessary references for all the data used in this paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
45

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular 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 it has changed) should be provided.
If this information is 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: [NA]
Justification:
We didn't release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper doesn't 't involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not 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.
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper doesn't 't involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
46

---

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 to 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.
47


Reviews:
[{"review_id": "oo1DkVEczd", "reviewer": "Reviewer_SC6h", "summary": "This paper evaluates graph homophily from the perspectives of label, structure, and feature, which disentangle the dependencies of these three aspects. The theoretical analysis and experimental evaluations demonstrate the effectiveness of Tri-Hom.", "questions": "None", "limitations": "please check the weaknesses.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is innovative and significant in evaluating graph properties from their central components, namely, label, feature, and structure.\n2. This paper highlight the missing component on evaluating the graph homophily, marking it as novel compared to existing methods for designing graph learning methods and new evaluation metrics.\n3. There have been extensive experiments conducted on synthetic and real-world datasets.", "weaknesses": "1. This paper lacks suggestions for designing models. New metrics are provided for evaluating graph homophily properties. However, as new models are continually proposed, it would be beneficial if the authors could provide some guidelines for designing models when tackling new datasets. \n\n2. The connections and distinctions between the proposed metrics and the existing metrics from the label, feature, and structure perspectives need further clarification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Part 1/2\n\n## Q1: Suggestions for designing models.\n## RQ1\n\nThanks for your positive rating and constructive suggestions. It is interesting to see how our conclusions can guide the model design. Due to the page limitation, we did not share suggestions in model design. Here we show some guidelines for model designs and future directions from 3 perspectives: label homophily, structural homophily, and feature homophily as follows:\n\n### A. Label homophily\n\nWe discussed how label homophily influences GCN and MLP, providing both theoretical proof (Theorem 2.1 in Line 232) and empirical experiments (the three sub-figures in the first row of Figure 4 in Appendix D.6). Our results show that GCN performs better than MLP in conditions of extremely low homophily (good heterophily [1]), but significantly worse than MLP in medium levels of homophily (mid-homophily pitfall [2]). This suggests that GCNs sometimes fail to extract effective topological information. To mitigate this weakness, it is preferable to add a residual connection to GNNs or introduce a learnable parameter that allows the model to balance graph-aware and graph-agnostic information. The necessity of residual connections has been verified in previous studies [3, 4, 5].\n\nIn addition to model design at the graph level, we can also consider a fine-grained approach at the node level. Our results indicate that GCN does not always outperform MLP, suggesting that different models could be applied to nodes with varying levels of label homophily. To our knowledge, this type of personalized design has rarely been explored in current GNN research on heterophilic graphs, yet it holds significant potential for improving overall model performance.\n\n### B. Structural homophily\n\nAs mentioned in Theorem 2.2, the performance of graph-aware models improves with an increase in structural homophily. This leads to a crucial question: how can we deal with graphs exhibiting varying levels of structural homophily (i.e., the consistency of structural information among intra-class nodes)? To address this issue, we can enhance current GNNs using two approaches: message-passing calibration and graph rewriting.\n\nFor the message passing calibration, several methods, such as GPRGNN [13], FB-GNNs [14], and ACM-GNNs [15], propose adding an additional high-pass filter to capture local variations and details in the graph structure. When structural homophily is low, the high-pass filter captures the diversification of individual nodes. Along with a low-pass filter, these methods perform well on graphs with varying levels of homophily. However, the high-pass filters used in these methods cannot capture more complicated structural information. Since $\\mathcal{S}(\\cdot)$ in structural homophily can be any measurement of structural homophily, this metric can evaluate more complex graph structures. In the future, it is promising to design novel filters based on structural homophily to capture more intricate structural information and improve model performance.\n\nFor the graph structure rewriting, many methods (MVGCN [6], GloGNN [7], WRGNN [8]) propose deriving a new graph topology based on node features or embeddings. This operation improves the connectivity of nodes with similar semantic contexts, thereby enhancing model performance. However, this rewriting could connect nodes from different classes, which impedes GNN performance. To resolve this, we can measure class-wise structural homophily as shown in Eq. (2) and design adaptations for different classes, which will be particularly beneficial for class-imbalanced graphs, such as in bot detection and fraud detection. Furthermore, we can adapt the structural measurement function $\\mathcal{S}(\\cdot)$. Since most current structural rewriting methods do not evaluate the informativeness of their rewriting basis (node embeddings with structural information), the proposed structural homophily can serve as a metric to evaluate which types of rewriting basis to select. For example, Geom-GNN [9] uses Isomap [10], Poincare embedding [11], and struc2vec [12] to construct new neighbors of nodes and empirically determines the best approach. Our structural homophily could identify the most effective embedding approach before training GNNs. Therefore, structural homophily provides a guideline for graph rewriting methods.\n\n### C. Feature homophily\n\nIn Appendix B, we thoroughly discuss the motivation behind feature homophily, where feature dependencies measure how node features are influenced by their neighbors. To our knowledge, only a few GNNs [16] consider these feature dependencies in their design. There is significant potential to explore how feature dependencies function in graphs. For instance, in social networks, people's opinions are affected by those around them. Identifying different user types while filtering out the noise introduced by their neighbors remains an open question. Both our theoretical results (Theorem 2.3) and empirical results (Figure 4) demonstrate the synergy between feature homophily and label homophily in enhancing model performance. Based on these findings, future work could focus on designing various graph filters to optimize the objective in Eq. (8) by considering both label and feature homophily. Furthermore, feature homophily can explain the presence of node features, making it worthwhile to investigate how much features are influenced by their neighbors, particularly in temporal graphs.\n\nIn conclusion, our findings offer valuable insights for designing models. Compared with previous studies that only analyze the single factor of label homophily [1, 2], structural homophily [17], or feature homophily [18] on GNNs, our work consider the synergy of all 3 types of homophily. We validated our theoretical results using both synthetic and real-world datasets. We believe this work represents a significant advancement on graph homophily and provides numerous intriguing directions for future research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zhs1uTS4B2", "reviewer": "Reviewer_bySE", "summary": "The paper proposes a novel approach to understanding graph homophily by disentangling it into label, structural, and feature homophily. The introduction of the Tri-Hom metric combines these aspects to provide a more comprehensive measure of GNN performance. CSBM-3H is used to study the impact of these types of homophily. Extensive experimental results on synthetic and real-world datasets show the effectiveness of the findings.", "questions": "1. The definitions of structural and feature homophily are somewhat abstract. Could you provide more concrete examples or case studies to illustrate these concepts?\n2. How to translate the finding to real-world applications?", "limitations": "Lack concrete examples for readers’ understanding.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper takes a comprehensive thought on graph homophily and provides with a more detailed understanding of homophily.\n2. The introduction of Tri-Hom metric as well as and the CSBM-3H model which is based on the metric is novel.\n3. The paper includes both theoretical analysis and empirical validation through synthetic and real-world datasets.", "weaknesses": "The introduction of multiple new concepts and metrics might be overwhelming for readers who are not well-versed in graph theory and GNNs. Simplifying explanations or providing more intuitive examples could help.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Q1 The definitions of structural and feature homophily are somewhat abstract. Could you provide more concrete examples or case studies to illustrate these concepts?\n\n## RQ1\n\nThanks for your valuable suggestions. In line 116 and 146, we show the differences of structural and feature homophily respectively. To help better understand these definitions, in author rebuttal PDF, we add diagrams of 3 types of homophily and visualize how these homophily metrics influences graphs generated by CSBM-3H. As shown in Figure 1, label homophily measures the label consistency along the graph topology, structural homophily measures the consistency of neighbor distribution of intra-class nodes, and feature homophily measures the feature dependencies along the graph topology. Each of the homophily shows a unique aspect. For example, in social networks, label homophily measures how likely the same types (age, hobby, and so on) of people are connected, structural homophily measures the consistency of the neighbors of certain type of people, and feature homophily measures how much the features of people are affected by their neighbors. For more concrete examples or explanations, please refer to the RQ2 of your second question.\n\n## Q2 How to translate the finding to real-world applications?\n\n## RQ2\n\nCurrent real-world applications of graph homophily only focus on label homophily, which cannot align well with GNNs performance as shown in this paper and other studies [1, 2]. To address this weakness, our findings provide a comprehensive view from 3 types of homophily, which could be applied in many real-world applications, such as social networks, recommendation, and urban computing. \n\n### A. Social Networks\n\nIn social networks, homophily is defined as the tendency for people to seek out or be drawn to others who are similar to themselves [3]. This definition primarily explains the consistency of certain characteristics of people within the network topology. Our proposed concepts of structural homophily and feature homophily offer additional insights into social networks.\n\nStructural homophily refers to the similarity of the local neighbors of individuals of the same type, which can be used to analyze the friend circles of specific user groups. For instance, in fraud detection on social media, fraudsters often target older individuals who are more vulnerable to scams, resulting in a high level of structural homophily. Therefore, we can identify potential fraudsters based on their structural connections. However, structural information can vary and may not always be informative. If fraudsters randomly select users to contact, identifying them through their neighbors becomes challenging, leading to a low level of structural homophily. Future research could focus on measuring the level of structural homophily in social networks to better understand user behaviors.\n\nFeature homophily, on the other hand, describes how individuals are influenced by their neighbors. Different types of networks exhibit varying levels of feature homophily. When people discuss similar events online, their opinions may be influenced by those they follow, leading to a higher similarity in features with their neighbors, indicating a high level of feature homophily. Conversely, during online arguments, individuals connect with those holding different opinions. After such interactions, they may reinforce their original viewpoints, resulting in greater dissimilarity with their neighbors, indicating a low level of feature homophily. Investigating user behavior through feature homophily can reveal underlying intentions and improve model performance. Furthermore, feature homophily provides valuable insights into the extent to which users are influenced by their neighbors.\n\n### B. Recommendation\n\nPrevious studies [4, 5] on recommendation systems using graph homophily have primarily focused on label homophily, which may result in misalignment with model performance, similar to what occurs in purely homogeneous graphs. To address this issue, it would be beneficial to define structural homophily within recommendation systems. For instance, we can measure the structural information of users within the same community by assessing the consistency of the items they have purchased. This approach allows us to determine whether this topological information can effectively predict links between users and specific items.\n\n### C. Urban Computing\n\nA recent study [7] proposes a method to measure spatial graph homophily in urban computing using a spatial diversity score with direction-aware and distance-aware partitions. However, this metric focuses solely on label homophily, leaving a significant opportunity to explore structural homophily. Structural homophily involves measuring the consistency of geographic information among similar types of locations. For example, bookstores are often surrounded by coffee shops, where customers can enjoy coffee while reading books [6], indicating a high level of structural homophily. Conversely, convenience stores might be located near a high-end fashion boutique, a fast-food restaurant, or an office building. Since the geographic information does not reliably indicate the presence of a convenience store, it exhibits a low level of structural homophily. Future research could explore structural homophily in urban graphs to analyze the behaviors of various urban objects, aiding in better city planning.\n\nThank you for your constructive suggestions. We have revised the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5yo5cEjRmJ", "reviewer": "Reviewer_JQBx", "summary": "The paper combines three different metrics (label, structural, and feature) for homophily proposing a Contextual Stochastic Block Model (CSBM-3H) describing these three types of homophily. By doing so it can control the topology and feature generation based on these three homophily metrics. Furthermore, there exists an extensive theoretical analysis of CSBM-3H, also defining new composite metric, named Tri-Hom, that considers all three homophily aspects and overcomes the limitations of the previously proposed and conventional homophily metrics. Importantly, they validate the correlation of model performance (under node classification) based on experimental set-up including 31 real-world benchmark datasets, outperforming various baseline metrics.", "questions": "Would it be possible to visualize the generated SBM networks under different levels of homophily and observe the resulting block structures with respect to all different types of homophily?", "limitations": "The authors should discuss limitations of their paper and proposed method.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The paper is interesting, and combining all three homophily metrics into one unified metric is novel.\n\n2) The theoretical analysis of the proposed method is robust. The paper introduces three theorems that establish connections to important aspects verified in the literature, thereby unifying multiple works under a single framework.\n\n3) The proposed Contextual Stochastic Block Model, which incorporates three types of homophily, is innovative and could be highly useful for benchmarking general models under varying types and levels of homophily.\n\n4) The experimental section is extensive, including 31 datasets, and yields promising results.", "weaknesses": "1) The paper validates performance only under the node classification task. It would be very interesting to also validate Tri-Hom for the task of link prediction.\n\n2) A minor weakness is that some results in Table 1 for certain baselines are quite close, with only marginal improvements. Could the authors comment on this phenomenon? Why might this be the case, and could it indicate that for some models or networks, having only one homophily metric would be sufficient?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Part 1/2\n## W1: The paper validates performance only under the node classification task. It would be very interesting to also validate Tri-Hom for the task of link prediction.\n\n## RW1\n\nThanks for your valuable suggestions. It is a good topic to evaluate Tri-Hom and other homophily metrics for link prediction. We only include the results on node classifications in the paper because it is the most classical task on GNNs and most previous studies focus on node classification. Further more, other than space limitation, to validate Tri-Hom for link prediction, there are several challenges that we need to tackle:\n\n**Missing of node labels.** Not all the graphs for the task of link prediction are associated with node labels. However, most of the homophily metrics, as well as our proposed Tri-Hom, are measured based on node labels. It is infeasible to directly apply these metrics on these graphs without labels and more task-oriented adaptations are needed.\n\n**Task Goal.** The goal of node classification is to learn distinguishable node representations, while the goal of link prediction is to predict the likelihood of future or missing links by leveraging reliable structural representations of the graph. This requires an understanding of existing connections and patterns within the graph. Therefore, it is hard to directly apply Tri-Hom on link prediction regarding the different goals in the task.\n\nApart from that, the main contribution of this paper is disentangling the graph homophily from 3 aspects. Previous theoretical studies [1, 2 ,3 ,4] of graph homophily analysis only consider a single aspect of node classification, while we measure the synergy of 3 types of homophily and successfully validate the theoretical results on both the synthetic and real-world datasets. Considering the challenges in link prediction, here we only measure Tri-Hom with node classification since it is the most widely explored task for GNN performance. In the future, we will explore the Tri-Hom with adaptions to deal with challenges in other types of graph tasks such as link prediction and graph clustering.\n\n\n## W2: A minor weakness is that some results in Table 1 for certain baselines are quite close, with only marginal improvements. Could the authors comment on this phenomenon? Why might this be the case, and could it indicate that for some models or networks, having only one homophily metric would be sufficient?\n\n## RW2\n\nAs shown in Table 1, the strongest baseline is class homophily ($h_{class}$), which underperforms our proposed Tri-Hom for graph-aware models $\\mathcal{J}_h^{\\mathcal{G}}$ on GNNs by an average gap of 4\\%. It is not surprising that these label-based homophily metrics show strong performance because node labels contain the most important information for the task of node classification on graphs. Label-based homophily metrics outperform all other structural-based or feature-based metrics. The improvement of our metrics comes from the full consideration of all three aspects of graph homophily.\n\nAlthough we measure performance on 31 real-world datasets, this number is insufficient to fully demonstrate the importance of feature homophily or structural homophily. As shown in Table 5, the distribution of these datasets across the three types of homophily does not vary significantly. Additionally, the Twitch datasets collected by [4] and some heterophilic graphs (Wisconsin, Cornell, Texas, Squirrel, Actor, Chameleon) collected by [5] exhibit high similarity in homophily levels. Therefore, more real-world datasets with varying levels of homophily, particularly for structural and feature homophily, are needed to test the effectiveness of homophily metrics comprehensively. We have attempted to mitigate the impact of limited dataset availability by testing on 31 different datasets.\n\nDue to the scarcity of real-world datasets, we validate the performance of Tri-Hom on synthetic datasets, which offer a diverse range of homophily levels. As shown in Figure 1, the performance surface of Tri-Hom closely mirrors that of GNNs. It is evident that other types of homophily, based on a single factor, underperform compared to Tri-Hom in synthetic datasets, as they respond to only one type of homophily..\n\nFurthermore, other studies [1, 2] that focus on homophily analysis only report results on 9 datasets, evaluating 'good' or 'bad' homophily on a case-by-case basis. Our work represents a significant advancement by fairly comparing homophily metrics across 31 real-world datasets with statistical significance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "60zefstrqT", "reviewer": "Reviewer_9nLU", "summary": "This paper analyzes graph homophily and distinguishes three types of homophily: label, structural, and feature homophily. Theoretical analysis is based on CSBM-3H (contextual stochastic block model with three types of homophily).  Based on this analysis, a new combined measure Tri-Hom is proposed. The relation between GNN performance and three types of homophily is empirically analyzed on CSBM-3H. Then, the agreement of Tri-Hom with GNN performance is analyzed using several real datasets. It is shown that the proposed homophily measure better agrees with the GNN performance than other existing measures.", "questions": "1. In Section 3.1, many label homophily measures are introduced. Which one is chosen by the authors?\n\n2. In equation (2), how exactly $\\sigma_{max}$ is computed?\n\n3. Could you give more details/motivation about the difference between label and structural homophily (in general)? Since both are expected to describe the relation between structure and labels.\n\n4. In equation (5), it would be useful to discuss whether the obtained values $h$ are comparable across features of different natures. In particular, how these values behave when we do certain feature transformations: shifts, scaling, or changing variance. These would give more intuition about the proposed form of feature homophily.\n\n5. How performance is measured in Table 1?", "limitations": "Some of the limitations are discussed in Section 6. I agree with the authors that societal impact is irrelevant for this type of work.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The proposed model CSBM-3H is more flexible and models more complicated relations between graph structure, node features, and node labels than other typically used models. Such a model can be used as a synthetic benchmark in research papers.\n\n2. Theoretical analysis shows how different homophily aspects relate to the distinguishability of aggregated and non-aggregated node features.", "weaknesses": "1. There seems to be a terminological inconsistency in the text. In the abstract, it is written that \"graph homophily refers to the phenomenon that connected nodes tend to share similar characteristics.\" However, structural homophily introduced in Section 3.2 is about a different phenomenon: nodes from the same class tend to have similar neighbors (but they can be not connected). In some previous papers, e.g. in [31], these concepts are distinguished, and LI is not called a homophily measure.\n\n2. The particular form of structural homophily (2) is not motivated. In Section 3.2, it is written that there are several existing structural homophily measures, but they are not chosen. Why the proposed expression (2) is better?\n\n3. Similarly, there is not much motivation for the feature homophily proposed in (3). More motivation on why this diffusion process is supposed to reflect homophily would be helpful. In particular, (3) seems to assume a particular form of feature propagation. It is unclear how limiting this assumption is.\n\n4. Throughout the paper, the class sizes are assumed to be balanced. In line 192, it is written that this is done without loss of generality, but it is not clear why so. In particular, several papers previously discussed that node/edge homophily is not a suitable measure for class-imbalanced datasets. In other words, class balance plays a crucial role for homophily measures and thus considering only balanced classes is a significant limitation. One of the examples where class balance seems to be critical is Theorem 2.2: here the threshold 1/C holds only for balanced classes.\n\nSome typos:\n- Line 12: \"element\" -> \"elements\"\n- Line 61: \"i.i.d.assumption\" — missing space\n- Line 62: \"Compared previous\" -> \"Compared to the previous\"\n- Line 69: \"In addition, Our\" -> \"In addition, our\"\n- Line 82: It is written that $I_E$ is a matrix, in this case, it should be from $R^{E\\times E}$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful reviews. We have fixed the typos and revised our manuscripts accordingly. Here are our responses to your concerns.\n\n## Part 1/4\n\n## W1: Terminological inconsistency of graph homophily and structural homophily. \n\n## RW1: \n\nGraph homophily is a general concept that describes the phenomenon of connected nodes tending to have similar characteristics. However, in the current graph community, the concept of homophily can sometimes be generalized to describe relations beyond connected nodes, such as Aggregation homophily [9], Coleman's  homophily [10], and Preference-aware homophily [11]. The proposed structural homophily measures the consistency of structural information within intra-class nodes, which is crucial for the disentanglement of graph homophily. There indeed exists potential confusion and we will clarify their relations in the revised version.\n\n\n## W2: 1) The particular form of structural homophily (2) is not motivated. 2) Why not choose other existing structural homophily measures and 3) why the proposed expression (2) is better? \n\n## RW2: \n\n1) As mentioned in Line 109, Section 3.1, label homophily focuses solely on the consistency of label information for connected nodes, while neglecting structural information. This limitation leads to a partial understanding of graph homophily and results in the misalignment of label homophily with GNNs’ performance [1]. To address this, we propose structural homophily $h_S$ in Section 3.2.\n\n2) The proposed $h_S$ in Eq. (2) is based on the sampling process, unlike the existing structural-based metric  [7,8]. This enables $h_S$ to be incorporated into CSBM-3H to analyze the impact on graph-aware models. Furthermore, $h_S$ provides a general form that can be applied to broad settings. For example, to extend $h_S$ to multi-hop neighbors, we can revise $\\mathcal{S}(\\cdot)$ in Eq. (2), a flexibility not available with other metrics.\n\n3) In our experiments, the effectiveness of the proposed Eq. (2) is demonstrated in Table 5 in Appendix D.9, where we measure the correlation of metrics with the performance gap between GNNs and MLPs. $h_S$ shows the best correlation compared with other structural-based homophily metrics. Additionally, we explore how $h_S$ influences accuracy on graphs with respect to each class in Figure 6. The findings indicate a general tendency of increased accuracy with higher $h_S$. \n\n\n## W3: 1) The motivation for the feature homophily proposed in (3). 2) Why this diffusion process is supposed to reflect homophily would be helpful. 3) In particular, Eq. (3) seems to assume a particular form of feature propagation. It is unclear how limiting this assumption is.\n\n## RW3: \n\n1) We would like to clarify the motivation for feature homophily $h_F$ in the paper. In Section 3.3, we list all the current feature-based homophily metrics, which cannot disentangle themselves from label homophily, leading to redundancy and a decrease in useful information within the feature aspect. Based on this motivation, we propose $h_F$ to fully disentangle the feature aspect. The $h_F$ is invariant with respect to both label and structural homophily, thereby dissociating it from these two types of homophily. This is part of our main contributions, which disentangles graph homophily from three aspects, better aligns with GNN performance, and helps explain other interesting but under-explored phenomena of graph homophily in previous studies [1, 2, 3].\n\n2) In Line 152, we explain the meaning of $h_F$ through the sign of $\\omega$. A positive, negative, or zero $\\omega$ corresponds to an attractive relation, a repulsive relation, or independence of the nodes with their neighbors, respectively. Specifically, consider a case in social networks where people interact with each other. A positive $h_F$ refers to users influencing their neighbors to adopt the same opinions as theirs. A negative $h_F$ refers to users arguing with each other while more strongly holding their opinions to oppose others. A zero $h_F$ indicates that interactions among users do not change their opinions. This process in social networks is generally referred to as a diffusion process [4], which could reflect the $h_F$ defined in Eq. (3).\n\n3) In Appendix B, we discuss why the assumption of a diffusion process makes sense. In Eq. (28), we show that the structural-aware features are updated by $\\frac{\\partial\\boldsymbol{X}(t)}{\\partial t}$, which contains $\\boldsymbol{X}(0)$ (ego-node features) and $(\\mathcal{F}(\\boldsymbol{A}) - \\boldsymbol{I})\\boldsymbol{X}(t-1)$ (influences of the graph topology). We use linear dependency to model this feature dependency function $\\mathcal{F}(\\boldsymbol{X}) = \\omega\\boldsymbol{A}$ following [5] to analyze graph homophily with GNN performance. To the best of our knowledge, we are the first to consider feature dependencies to analyze GNN performance under CSBMs. In contrast, previous studies [1, 2, 3, 6], which assume no feature dependencies during graph modeling, oversimplify by completely ignoring feature dependency.\n\n## W4: Throughout the paper, the class sizes are assumed to be balanced. In line 192, it is written that this is done without loss of generality, but it is not clear why so. \n\n## RW4:\n\nThis paper aims to disentangle graph homophily from three aspects and investigate its overall impact at the graph level. While in-balanced classes do influence the graph, this influence does not affect the impact of graph homophily, as shown in previous studies [2, 6]. Consequently, the class-balanced assumption has little effect on our findings and doesn't hurt our main contributions. Our observations on CSBM-3H also show the setting of in-balanced class sizes doesn't give us extra information.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their valuable feedback. In this author rebuttal PDF, we provide diagrams and visualizations to help better understand our proposed definitions.

Figure 1 shows the definition of three types of homophily. Label homophily $h_L$ measures the label consistency along the graph topology, structural homophily $h_S$ measures the consistency of structural information within intra-class nodes, and feature homophily $h_F$ represents the feature dependencies along the graph topology. Each type of homophily represents a unique perspective towards the concept of graph homophily. In our paper, we disentangle the concept of graph homophily and investigate the synergy of these three types of homophily in Graph Neural Networks (GNNs) through theorems, simulations, and real-world experiments, providing a better understanding of graph homophily.

Figure 2 visualizes the impact of the three types of homophily in CSBM-3H: **1. Label homophily.** As label homophily ($h_L$) increases, nodes are more likely to connect with others sharing the same label, with high $h_L$ (Figure 2(c)) providing clearer class boundaries. Medium $h_L$ (Figure 2(b)) is less informative than very low $h_L$ (Figure 2(a)). **2. Structural homophily.** As shown in Figure 2(d), (e), and (f), when structural homophily ($h_S$) increases, neighbor distributions become more consistent, and high $h_S$ captures effective structural information. Besides, a higher $h_S$ makes a graph resemble planar and periodic graphs, suggesting stable structural information leads to regular patterns. **3. Feature homophily.** Figures 2(g), (h), and (i) show different levels of feature homophily ($h_F$) in the same graph topology. Medium positive $h_F$ (Figure 2(h)) causes boundary node features to resemble neighboring classes. Higher positive $h_F$ (Figure 2(i)) increases feature dependencies, especially near class boundaries. In real-world scenarios, positive $h_F$ causes entities to show dependencies with neighbors, like people influenced by friends. Negative $h_F$ makes nodes dissimilar from neighbors, creating distinct class boundaries and varied shades within the same class (Figure 2(g)). This "repulsive force" leads to reinforced original opinions after interactions, akin to online arguments.

Meta-review: The paper proposes a method to understanding graph homophily by disentangling it into label, structural, and feature homophily. It introduces Tri-Hom metric that combines these aspects to provide a more comprehensive measure of GNN performance. Extensive experimental results on synthetic and real-world datasets show the effectiveness of the findings.
Decision: Accept (poster)