What Is Missing For Graph Homophily? Disentangling Graph Homophily For Graph Neural Networks

Authors: yilun  zheng
sitao  luan
lihui  chen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 05:59:45

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.

Main paper: 
 introduction: 
 Graph Neural Networks (GNNs) have been widely used in processing non-Euclidean data due to their superiority in extracting topological relations [10, 13, 26, 41, 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 on node-level tasks, is closely related to the homophily assumption [47, 72, 38, 43, 36, 71] , 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-homophily/heterophily scenario, GNNs fail to capture the useful neighbor information and even underperform Multilayer perceptrons (MLPs) [37] . Several homophily metrics, such as edge homophily [72, 1] 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] .However, recent studies [46, 39, 51, 40] show that the conventional homophily metrics [72, 1, 50] are insufficient to measure the performance of GNNs: Luan et al. [38] show that the homophily metrics cannot tell if GNNs work well under heterophily. Ma et al. [46] reveals that homophily is not a 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?In this paper, we fill the missing parts by investigating different perspectives of the "node similarity". Conventional homophily metrics 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: label, structural, and node feature information. The ignorance of structural and feature information leads to insufficient understanding and unsatisfactory alignment between homophily metrics 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 "similarity" 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 Homophily (CSBM-3H). The node feature generation process in CSBM-3H breaks the i.i.d. assumption in previous studies [46, 39] , which is closer to real-world scenarios [14, 59, 61] . With the three metrics, CSBM-3H enables a 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, 38] and the impact of feature shuffling on GNNs [29] . 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-Hom than the other 17 existing metrics that focus only on a single homophily aspect. This implies that Tri-Hom can complete the absent parts in existing homophily metrics.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 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 in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
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 ∈ R N ×N . We use A uv = 1 or e uv ∈ E to denote the existence of an edge between node u and v, otherwise A uv = 0 or e uv / ∈ E. Node degree vector is denoted as D ∈ R N where D u is the degree of node u. Node label vector is denoted as Y ∈ R N and its one-hot encoding matrix is Z ∈ R N ×C . The number of nodes in class c is denoted as N c = |{u|Y u = c, u ∈ V}|. The neighbor set of node u is denoted as N u = {v|e uv ∈ E}. The features of all the nodes is denoted as X ∈ R N ×M , where X v,: are the features of node v with M dimensions. We use I E ∈ R E×E and 1 E ∈ R E×E 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, 72] and node homophily [50] are 2 most commonly used metrics and are defined as follows,EQUATIONThese 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 a 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 M G and graph-agnostic models M ¬G refer to the models that either utilize structure information or do not, respectively. For example, baseline graph-aware models M G , such as 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 ¬G are the Multilayer Perceptrons (MLPs), which only encode node features [39] .Structural-agnostic features refer to the node features X that are conditionally independent of graph topology A given Y , i.e.,(X ⊥ ⊥ A|Y ); structural-aware features indicate (X ̸⊥ ⊥ A|Y ).Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: We discussed the limitations in Section 6Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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, in the next section, we will introduce how they collectively impact the performance of GNNs.3.1 Label Homophily Definition 1. Label homophily is defined as the consistency of node labels across the topology. Label homophily is the most widely used conventional metric of graph homophily and it qualifies the similarity between connected nodes u and v using an indicator function 1(Y u = Y v ).Most of the conventional homophily metrics focus on label homophily, including edge homophily [1, 72] , node homophily [50] , class homophily [33] , adjusted homophily [51] , densityaware homophily [30] , 2-hop neighbor class homophily [5] , and neighbor homophily [15] .However, label homophily only focuses on the consistency of label information for connected nodes while neglecting structural and feature information, which are two indispensable components of graph data. Hence, it offers only a partial understanding of graph homophily, which cannot always align well with the performance of GNNs [46, 38, 39] . To capture the missing structural and feature information and better understand graph homophily, we give the definitions of structural and feature homophily in the following 2 subsections.For structural homophily, the "atom" information of a node is structural information instead of the label. It is meaningless to define the structural homophily using the consistency across the graph topology as in the label homophily because the structural information already contains the information from the graph topology. Therefore, we define the structural information as the consistency of structural information among the nodes from the same classes 1 , which better disentangles itself from the label homophily. Definition 2. Structural homophily is defined as the consistency of structural information of nodes within the same class. The structural homophily in a graph is defined as:EQUATIONwhere h S,c is the class-wise structural homophily for class c, function S(•) measures structural information, σ denotes standard deviation of structural information, and σ max denotes the maximum value of σ.In this paper, we quantify the structural information for node u through neighbor distribution (the class distribution of local neighbors) D N u = [p u,1 , p u,2 , . . . , p u,c ], where p u,k = |{Yv=k|v∈Nu}| |Nu| is the proportion of neighbors of node u that belong to class c. 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 a 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.Previous feature-based graph homophily metrics, such as generalized edge homophily [23] , local similarity [7] , 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 on 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 a 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-based homophily metrics 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 structural-agnostic unobserved feature X(0) and the observed structural-aware feature X that satisfy the following relationEQUATIONThe detailed process of this relation is given in Appendix B. Here ω ∈ (-1 ρ(A) , 1 ρ(A)) is a parameter that controls the feature dependencies, where a positive, negative, or zero value corresponds to an attractive relation, repulsive relation, or independence of the nodes with their neighbors in graphs [55, 64] . The feature dependencies (ωA) t of t-order neighbors are introduced to structuralagnostic 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, ω will remain unaffected. To disentangle feature homophily from label homophily and structural homophily, we define the feature homophily based on ω 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 satisfiesEQUATIONwhere ρ(A) is the spectral radius of A, X(0) ∼ p(X|Y ) are the unseen structural-agnostic node features, and X ∼ p(X|Y , A) is the observed structural-aware node features. The feature homophily for the whole graph is the averaged feature homophily for all the featuresEQUATIONNote that it is easy to control the feature homophily in the generation of synthetic graphs. However, since both h F,m and X :,m (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 :,m (0) are small. This case holds in lots of real-world scenarios [38, 39] and we can utilize this property to estimate h F,m without solving X :,m (0). Specifically, the feature homophily h F,m for feature m can be estimated with the following optimization processEQUATIONThe estimation of feature homophily is invariant to the operations of feature shifts, scaling, or changing variance, where the proof is shown in Appendix C. This estimation process will be used in Section 5.2 for calculation. Remark To better understand the definitions of three types of graph homophily, Figure 1 (f), the neighbor distributions of intra-class nodes become more consistent. Therefore, a high h S is expected to capture effective structural information with message aggregation. Interestingly, we also find that a higher h S makes a graph resemble planar graphs [3] and periodic graphs [9] . We hypothesize this phenomenon occurs because stable structural information leads to more regular and meaningful patterns, which would be interesting to explore the connection between h S and these geometric properties of graphs in the future. 3) Feature homophily. Figures 1(g), (h), and (i) illustrate different levels of feature homophily (h F ) within the same graph topology. Figure 1 (h) demonstrates that under a medium positive h F , 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 h F (Figure 1 (i)) increases feature dependencies, particularly affecting more nodes closer to class boundaries. In social networks, a positive h F indicates that people's opinions are influenced by their friends, resulting in similar characteristics. Conversely, a negative h F causes nodes to become more dissimilar from their neighbors. As shown in Figure 1 (g), a negative h F creates a distinct boundary between classes. Additionally, for the intra-class nodes in Figure 1 (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 a negative h F . 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 a negative h F .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
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 [51, 29, 39, 46] 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 i.e.,(X ⊥ ⊥ A|Y ), which is uncommon in real-world scenarios where interactions influence the attributes of connected nodes [61, 14, 59] . Therefore, we propose a Contextual Stochastic Block Model with three types of Homophily (CSBM-3H), a random graph generative model that integrates the three types of homophily (Section 4.1), where the newly proposed structural homophily h S and feature homophily h F 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-agnostic 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).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 h L to control the label consistency across the graph topology and h S to control the consistency of neighbor distribution D N of nodes within the same classes. Then, the neighbor distribution can be expressed as:EQUATIONwhere D N ∈ R N ×C is the neighbor distribution for all the nodes, S ∈ R C×C is a class-sampling matrix, and ϵ ∈ R C×C is a noise matrix. Each entry of ϵ is a noise of neighbor sampling that follows a Gaussian distribution N (0, (1-h S )2 c-1 ). The class-sampling matrix S should be legal in practice [60] i.e., S u,v > 0 and v S u,v = 1. Then an adjacency matrix A can be sampled from a neighborhood sampling matrix A p = Cd N D N Z T , where E[A uv = 1] = (A p ) uv for each pair of nodes u, v. In this way, we control the label homophily h L and structural homophily h S in a graph.Node Feature Generation. For any node u in a graph, we first sample its structural-agnostic features X u (0) ∈ R F from a class-wised Gaussian distribution X u (0) ∼ N Yu (µ Yu , Σ Yu ) with µ Yu ∈ R F and Σ Yu ∈ R F ×F . We also assume each dimension of the feature vector is independent of each other, thereby Σ Yu ∈ R F ×F is a diagonal matrix. Then the observed structural-aware features can be generated by the unseen structure-agnostic feature as described in Eq. (4).Suppose we have the representations of node u as H u: = 1 d v∈Nu X v: for graph-aware models M G and H u: = X u: for graph-agnostic models M ¬G . Inspired by the principles of neural collapse [28, 27] and node distinguishability [39] , we quantify the impact of the aforementioned homophily metrics on both the graph-aware models M G and graph-agnostic models M ¬G by measuring the ratio of intra-class node distance to inter-class distance. To ideally distinguish nodes from different classes, a smaller intra-class distance D intra (H) and larger inter-class distance D intra (H) is preferred because this will reduce boundary nodes and increase the margins among classes. The metric is defined as follows,EQUATIONA 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 h L , h S , and h F on M ¬G and M G 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 ¬G and graph-aware models M G is:EQUATIONwhereJ N = Yu̸ =Yv [2C(C-1)] -1 ∥µ Yu -µ Yv ∥ 2 C -1 |σ 2 | , J ¬G h = 1-( h F ρ(A) ) 2 (C( 1-h L C-1 ) 2 +C (1-h S ) 2 C-1 +( h L C-1 C-1 ) 2 ) 1-( h F ρ(A) )( h L C-1 C-1 ) 2 , and J G h = ( h L C-1 C-1 ) 2 C( 1-h L C-1 ) 2 +C (1-h S ) 2 C-1 +( h L C-1 C-1 ) 2 J ¬G h .(See the proof in Appendix G.1.) From Theorem 1 we can see that, J N is a normalized distance term which is a constant given the distribution of structural-agnostic features and is irrelevant with graph information; J ¬G h and J G h are controlled by the three types of homophily, which can reflect the influence of graph homophily on model performance. We name J ¬G h and J G h as Tri-Hom for M ¬G and M G . To study the effect of Tri-Hom in more detail, we take the partial derivative of J G h with respect to h S , h F , and h L to show the analytical results of their influences 2 . (See calculation in Appendix G.5, G.6, and G.7.) Theorem 2.1. The partial derivative of J G h with respect to label homophily h L satisfies,EQUATIONFrom Theorem 2.1 we can see that, the worst performance of M G is reached when h L = 1 C , 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] .Theorem 2.2. The partial derivative of J G h with respect to structural homophily h S satisfies,EQUATIONFrom Theorem 2.2 we can see that, a larger h S consistently improves the performance of M G . This is intuitive for M G because more consistent intra-class neighbor distributions will lead to closer intra-class node representations after feature aggregation. This conclusion is also shown in Wang et al. [60] , where the topological noise (which is inversely proportional to h S ) has a detrimental impact on node separability.Theorem 2.3. The partial derivative of J G h with respect to feature homophily h F satisfies,EQUATIONwhere 0 < h - L < h + L < 1 and -1 < ĥF < 1. The expressions and detailed calculation of h - L , h + L , and ĥF are shown in Appendix G.7.From Theorem 2.3 we can see that, when h L is high in a graph, nodes with the same labels tend to be connected, thereby a larger h F makes the intra-class nodes share more similar representations and positively affect M G ; when h L is low in a graph, nodes with the different labels tend to be connected, thereby a larger h F makes the inter-class nodes share more similar representations and negatively affect M G ; when h L is on a medium level i.e., h L ∈ (h - L , h + L ), an increase of h F will first improve and then reduces the performance of M G with the cut-off point at h F = ĥF . There the ĥF is influenced by h L , h S , C, and ρ(A), and the h - L and h + L are influenced by h S , C, and ρ(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, e.g., 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 to the fact that the model performance is influenced by a combination of h L , h F , and h S , instead of h L alone. When the h L is low, the graph-aware models can still achieve good performance with a high h S or a low h F ; 2) feature shuffling is due to the existence of the structural-aware features of nodes. When h F > 0, nodes are positively dependent on their neighbors. In this case, the nodes at 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 to 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: 
 In Section 5.1, 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 L , structural h S , and feature homophily h F and test whether Tri-Hom J G h can reflect GNN performance. In Section 5.2, we evaluate the effectiveness of Tri-Hom on real-world benchmark datasets to test how well it can predict the model performance in real-world scenarios. In 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.To verify our theoretical results in a more general case, we measure the performance of GCN on synthetic datasets, where we can easily control h L , h S , and h F . Specifically, We measure the impact of label homophily h L , feature homophily h F , and structural homophily h S through numerical results of Tri-Hom J G h and simulation results of the node classification accuracy with GCN on synthetic datasets.We generate the synthetic graphs using CSBM-3H with a given tuple (h L , h S , h F ), where h L ∈ {0, 0.1, . . . , 0.9, 1}, h S ∈ {0, 0.1, . . . , 0.9, 1} and h F ∈ {-0.8, 0.6, . . . , 0.6, 0.8}. For each (h L , h S , h F ), we generate 1000 nodes with three balanced classes and the node degrees are sampled from a uniform distribution [1, 10] . For node features, we first sample the structural-agnostic features from class-specific Gaussian distributions, then we use Eq. (4) to propagate these features across the graph topology with feature homophily h F to generate the observed structural-aware 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 (h L , h S , h F ) 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.1.1.h can reflect the behavior of GCN, we 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.The results are shown in Figure 2 . For a better demonstration, we only show the results for h S = {0.2, 0.4, 0.6, 0.8} and each subfigure is a slice of h S that visualizes the impact of h L and h F on GCN and Tri-Hom. From the comparison of Figure 2a and 2b, we have two main observations: 1) Overall, the impact of h L , h S , and h F on synthetic datasets aligns well with the numerical results of Tri-Hom J G h . The only difference is that h F seems to 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 theoretical analysis, leading to the difference3 . 2) Our theoretical analysis of the impact of h L , h F and h S on Tri-Hom is consistent with GCN's behavior in Figure 2b : Theorem 2.1 shows the worst performance of M G is reached when h L = 1 C , corresponding to the ravine in Figure 2b for h L ; Theorem 2.2 shows an increase of h S consistently improves the performance of M G , corresponding to the overall increases of the accuracy in Figure 2b from the left to the right; Theorem 2.3 shows the influences of h F to M G is determined by the h L . Even if this is not obvious in Figure 2b , we show more detailed figures of the individual impact of h L , h S , and h F in Appendix E.6, confirming the impact of h F in Theorem 2.3.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 on real-world graph data. Experimental Settings To verify the effectiveness of our proposed Tri-Hom and compare with existing metrics, we train baseline models, MLP 4 , GCN [26] , GraphSage [16] , GAT [57] and estimate metrics, J ¬G h , J G h , h F , h S , and h L (we use h node in our experiments), on 31 real-world heterophilic and homophilic datasets. These datasets include Roman-Empire, 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-Computer, Coauthor-CS, and Coauther-Physics from [54] ; Flickr from [70] ; WikiCS from [48] ; Blog-Catalog from [68] ; Ogbn-Arxiv from [19] ; Genius, Twitch-DE, Twitch-ENGB, Twitch-ES, Twitch-FR, Twitch-PTBR, Twitch-RU, and Twitch-TW from [32] 5 . Besides, we also calculate other graph homophily and performance metrics on the benchmark datasets, the metrics include label-based homophily: h edge [72] , h node [50] , h class [33] , h adj [51] , h den [30] , h 2hop [5] , h nei [15] ; structuralbased homophily: LI [51] , h NS [46] , h agg [38] ; feature-based homophily: h GE [23] , h LS-cos [7] , h LS-euc [7] , h attr [67] , h CF [29] ; and classifier-based homophily metrics [39] : h KR , h GNB , h SVM on these datasets. The detailed definitions of these metrics are summarized in Appendix A and the details of all estimations are shown in Appendix E. Correlations with Model Performance To find out which metric can better align with the performance of GNNs on graphs with different properties, in Table 1 , we show Pearson correlation between all the metrics and model performance on the 31 real-world datasets 6 . For example, to show how well h edge align with the performance of GCN, we measure the values of h edge (in Table 3 ) and GCN performance (in Table 4 ) 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.The results show that: 1) J G h 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 h L , h S , h F into account, providing a comprehensive understanding of graph homophily; 2) J ¬G h , the Tri-Hom for M ¬G , 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. 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 metrics 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-3H 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 metrics. 
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 heterophily-oriented GNNs mostly focus on label homophily, neglecting structural homophily h S and feature homophily h F , that also influence GNN performance. For h S , 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 h F , it will be interesting to propose new approaches to identify how node features are influenced by their neighbors from both the global and local perspectives and then design new methods to treat the graphs or nodes differently according to h F . Please refer to Appendix F.1 for more detailed explanations of the future directions on model designs For the applications, such as social networks, recommendation systems, or urban computing, our 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 h F or low h F , causing them more likely or less likely to buy specific items. Please refer to Appendix F.2 for more details on the applications of the disentangled graph homophily. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [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, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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 is irrelevant to societal impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: This paper focuses on disentangling graph homophily, which is more conceptual and has no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: We provided the necessary references for all the data used in this paper. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset 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. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper doesn'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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere 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. 
 
 Appendix: In general, graph homophily metrics can be categorized as either statistic-based metrics or classifierbased metrics. The former can be further classified into the homophily on label, structural, or feature aspect. The definitions of these metrics are introduced as follows.Edge homophily [72] measures the graph homophily at the edge level, which is defined as the fraction of edges in a graph that connects nodes with the same labels:EQUATIONNode homophily [50] 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:EQUATIONClass 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:EQUATIONAdjusted homophily [51] considers the probability of an edge endpoint connecting to a node with a particular class and adjusts the edge homophily using node degrees, which is defined as:EQUATIONwhere D c represents the total degree of class c, i.e.,Dk = {e uv |Y u = c or Y v = c, e uv ∈ E} .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 is defined as:EQUATIONwhere ζ k is the edge density of the subgraph formed by intra-class edges of class k and ζk is the maximum intra-class edge density of class k. [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 to 2-hop, which is defined as:EQUATIONwhere N(2)u = { v∈Nu N v }\{u} represents the two-hop neighbors of node u.Neighbor Homophily [15] is proposed to address the "good" and "bad" heterophily issue by considering the dominant neighbors. The homophily score for any given node u is based on the number of nodes in which its class holds dominance among its k-hop neighbors. The definition of neighbor homophily in a graph is defined as:EQUATIONwhereN (k) vrepresents the k-hop neighbors of node u.Label informativeness [51] measures the informativeness of a neighbor's label for a node's label using condition entropy:EQUATIONwhereEQUATIONrepresents mutual distribution for a randomly sampled edge from class c 1 to class c 2 and pc = Dc 2|E| 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 distinguishable [46] . Therefore, the ratio of inter-class to intra-class neighborhood similarity could reflect the performance of GNNs7 EQUATIONwhereN (k) vis the k-hop neighbors of node u.Aggregation homophily [38] measures the ratio of nodes in a graph that has a higher intra-class aggregation similarity than inter-class aggregation similarity. The aggregation similarity of node u and u is the multiplication of their neighbor distribution i.e.,D N u D N v . The definition of aggregation homophily is given as:EQUATIONA.3 Homophily on Feature Aspect Generalized edge homophily [23] defines the feature homophily in graphs as the feature consistency across the graph topology:EQUATIONThe 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 u = Y v }, to a similarity measurement of node features, i.e., sim(X u , X v ).Local Similarity [7] measures feature homophily at the node level based on the hypothesis that nodes with similar features are likely to belong to the same class. The definition is given based on either cosine similarityEQUATIONor Euclidean similarity.EQUATIONAttribute homophily [67] considers the homophily with respect to each feature, which is defined as:EQUATIONwhere h attr represents the attribute homophily for the whole graph and h attr,m represents the attribute homophily for feature m.Class-controlled feature homophily [29] considers the interplay between graph topology and feature dependence through the disparity of nodes' expected distances to random nodes with their neighbors, which is defined as:h CF (G, X, Y ) = 1 |V| u∈V 1 d u v∈Nu d(v, V\{u}) -d(v, {u}) d(u, V ′ ) = 1 |V ′ | v∈V ′ ∥(X u |Y ) -(X v |Y )∥ X u |Y = X u - Yu=Yv X v |{v|Y u = Y v , v ∈ V}| (27)where X u |Y represents class-controlled features and d(•) denotes a distance function.Classifier-based homophily [39] uses a classifier to capture the feature-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 on the original feature X and the aggregated features H, as shown below: 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 [39] , which correspond to the metrics h GN B , h KR , and h SV M in this paper.This section explores the impact of graph topology on 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-aware i.e.,(X ̸⊥ ⊥ A|Y ). To model the feature dependencies of nodes in graphs, we follow [55] and adopt a graph diffusion process [6] , which is shown as followsX(t) = X(0) + T 0 ∂X(t) ∂t dt,whereEQUATIONHere the structural-agnostic node features X(0) ∼ p(X|Y ) are sampled from the distributions with respect to each class, while the structural-aware node features X(t > 0) ∼ p(X|Y , A) are generated through the diffusion process. In ∂X(t) ∂t , the first term describes how the dependencies are introduced with a feature dependency function F : (A) → R N ×N and the second term X(0) preserves the node distinguishability. Then, based on the Eq. ( 28), we haveEQUATIONWe can also interpret the process as an interactive particle system [55] where all node features collapse into an equilibrium eventually. The equilibrium requires Eq. ( 29) to have a closed form when t → ∞, implying the spectral radius of the adjacency matrix ρ(F(A)) < 1. This constraint also implies that|F(A)| k ≥ |F(A)| k-1for k > 0, which aligns with the common relations in graphs that nodes are likely to have higher dependencies with their closer neighbors than with farther neighbors.For simplicity and a better understanding of feature dependencies, we consider a linear case as in [6, 55] and use a parameter ω to control the feature dependencies i.e.,F(A) = ωA with a range of (-1 ρ(A) , 1 ρ(A) ). Then we can represent the structural-aware features asEQUATIONWe 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 a graph G = {V, E} with N nodes, there are node labels Y and node features X :,m in dimension m. We can estimate the feature homophily h * F,m for feature X :,m in dimension m as:EQUATIONThen we prove the estimation of feature homophily is invariant to the operations of feature shifts, scaling, or changing variance.Let's consider a shift of node features X :,m by a constant vector C:EQUATIONThen we have structural-agnostic features asEQUATIONThen a new estimation of h ′ F,m under this feature shift can be expressed asEQUATION)Since C is a constant vector, we haveEQUATIONTherefore, we proved the estimation of feature homophily is invariant to the operation of feature shifts.Let's consider scaling node features X :,m by a constant α:EQUATIONThen we have structural-agnostic features asEQUATIONThen a new estimation of h ′ F,m under this feature shift can be expressed asEQUATIONSince arg min x (•) is invariant to the scaling, e.g. arg min x (cf (x)) = arg min x (f (x)), we haveEQUATIONTherefore, we proved the estimation of feature homophily is invariant to the operation of feature scaling.Changing the variance of X :,m can be seen as the combination of scaling and shifts. Assume node features follow a Gaussian distribution N (µ, σ 2 ), after the operation of changing the variance from σ 2 to βσ 2 , we have new node features asEQUATIONwhere X ′ :,m is calculated by deducing µ, multiplying √ β, and adding µ. We already show the estimation of feature homophily is invariant to the operations of feature shifts and scaling. Since the operation of variance changing is a combination of scaling and shifts, we can conclude that the estimation of feature homophily is invariant to the variance changing.In addition to the impact of label homophily h L , structural homophily h S , and feature homophily h F on Graph-aware models as discussed in Section 4.2, we further discuss the impact on Graph-agnostic models through J ¬G h in this section. Specifically, we compute the partial derivative of J ¬G h with respect to h S , h F , and h L to reveal the analytical influences. (See calculation in Appendix G.2, G.3, and G.4.) Theorem 3.1. The partial derivative of J ¬G h with respect to label homophily h L satisfies,EQUATIONFrom Theorem 3.1 we can see that, under a positive h F i.e.,the features of connected nodes become similar, the increase of h L makes the features of intra-class nodes more distinguishable, thereby improving the performance of M ¬G . Conversely, under a negative h F i.e.,the features of connected nodes become dissimilar, the increase of h L makes the features of intra-class nodes more indistinguishable, resulting in a degradation of the performance of M ¬G .Theorem 3.2. The partial derivative of J ¬G h with respect to structural homophily h S satisfies,EQUATIONFrom Theorem 3.2 we can see that, since the existence of feature dependencies, a larger h S makes the structural-aware features more distinguishable among different classes, improving the performance of M ¬G .Theorem 3.3. The partial derivative of J ¬G h with respect to feature homophily h F satisfies,EQUATIONwhere 0 < h * ,-L < h * ,+ L < 1 and -1 < h * F < 1.From Theorem 3.3 we can see, how the impact of h F on M ¬G is determined by h L . This result is similar to the Theorem 2.3 in the case of M G . The increase of h F makes node features more similar to their neighbors. As a result, under a high h L , features of intra-class nodes become more similar, thereby improving the performance of M ¬G ; under a low h L , features of intra-class nodes becomes more similar, thereby reducing the performance of M ¬G . Initialize node features X, node labels Y , withX ∈ R N ×M , Y ∈ R N . Set random seed ϕ. for n = 0 to N do ▷ Sample node labels k ∼ ⌊Uniform(0, C)⌋ Y n ← k end for Z ← One-hot(Y ) ▷ One-hot encoding of node labels S ← h L I C + 1-h L C-1 (1 C -I C ) ▷ Introduce label homophily h L D N ← ZS ▷ Construct neighbor distribution for D N u,c ∈ D N do ϵ ∼ Normal(0, (1-h S ) 2 C-1 ) ▷ Introduce structural homophily h S D N u,c ← D N u,c + ϵ end for D ← diag(D) A p ∼ C N D-1 2 D N D-1 2 Z T ▷ Construct neighbor sampling matrix with node degrees A p ← max(0, min(1, A p )) ▷ Bound with [0, 1] before sampling A ←< Sym • Binarize > (A p )▷ Binarization sampling and symmetrize adjacency matrixfor n = 0 to N do ▷ Sample Structural-agnostic node features X n,: ∼ Normal(µ Yn , Σ Yn ) end for X ← (I C -h F σ(A) A) -2 X ▷ Introduce feature homophily h F return A, X, YThen 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 to the nodes with different classes are uniform, which lacks diversity. Second, the sampled node features are independent with their structures i.e.,(X ⊥ ⊥ A|Y ), which is uncommon in real-world scenarios where interactions influence the attributes of connected nodes [61, 14, 59] . Our proposed CSBM-3H well address these drawbacks by considering h S and h F , thereby providing a more comprehensive and realistic model.We conduct our experiments on 31 real-world datasets: Roman-Empire, Amazon-Ratings, Mineweeper, Tolokers, and Questions from [52] ; 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-CS, and Coauther-Physics from [54] ; Flickr from [70] ; WikiCS from [48] ; Blog-Catalog from [68] ; Ogbn-Arxiv from [19] ; Genius, Twitch-DE, Twitch-ENGB, 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 us to evaluate the model performance in a general case. For these datasets, we show basic statistics in Table 2 and the graph homophily metrics or model performance metrics in Table 3 .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 a learning rate of 0.001. [18] 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 a 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: {1e-3, 1e-4, 1e-5}.Table 4 shows 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 G outperform graph-agnostic models M ¬G 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-filtered, and Flickr. Consequently, relying solely on label homophily is insufficient to determine the performance of M G , which aligns with previous studies [46, 39] E.4 Tri-Hom for Graph-agnostic ModelsWe show the numerical results of Tri-Hom J ¬G h for graph-agnostic models M ¬G in Figure 3a , where each subfigure is a slicer of h S that visualizes the influences of h L and h F on J G h . For the impact of h L , h F , and h S individually, we can get the same conclusions as in Theorem 3.1, 3.2, and 3.3. To validate our theoretical results of M ¬G in a more general case, we further show the impact of three types of homophily with MLP on synthetic datasets in Figure 3b . The results correlate well with our in measuring the performance of M ¬G under the influences of three types of homophily.We show how the label homophily h L , structural homophily h S , and feature homophily h F collectively influence the J ¬G h and J G h in Figure 4 in a more general case, where the x-axis, y-axis, and z-axis denotes h L , h F , and h N . A lighter color (close to yellow) indicates a larger J ¬G h or J G h , which also implies a better model performance. These numerical results align well with our theoretical results of the individual impact on J ¬G h or J G h with respect to h L , h S , or h F . Furthermore, by observing the gradients in Figure 4 , we can know how these three homophily metrics influence the model performance collectively.To verify our theoretical results, we show how the performances of GCN and MLP are affected by three types of homophily individually in Figure 5 , which shows the influences of label homophily h L , structural homophily h S , and feature homophily h F on the node classification accuracy of GCN and MLP on synthetic datasets. First, the top 3 subfigures show the influences of h L under different h F and h S . With the increase of h L , the accuracy of GCN first decreases and then increases with a pitfall on a medium-level of homophily, and the accuracy of MLP is dependent on the sign of h F , leading to the same results as in Theorem 2.1 and 3.1. Second, the medium 3 subfigures show the influences of h F . With the increases of h F , the accuracy of both of the GCN and MLP will decreases with a low h L , increases with a high h L , and increases first and then decreases with a medium h L . The result also aligns well with Theorem 2.3 and 3.3. Last, the bottom 3 subfigures show the influences of h S . Even if the influences under different h L or h F would slightly vary, an increase of h S generally improves the performance of both the GCN and MLP, aligning well with Theorem 2.2 and 3.2.To better visualize the impact of h L , h S , and h F to graph-aware models M G on real-world datasets, we show the performance of GCN on all the datasets with these homophily metrics in Figure 6 , where h L , h F , and h S 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 h L , the performance of GCN decreases first and then increases, with a pitfall (as shown by datasets of Actor, Squirrel, and Chameleon). We also see that a higher h S leads to a better performance when we fix h F and h L (as shown by datasets of Question with Amazon-photo, and Cora with Coauthor-CS). As for the h F , since its influence is not so obvious compared with h L and h S as shown in Figure 5 and the scarcity of real-world datasets, it is hard to see its influence in real-world datasets.As shown in Figure 7 , we investigate more nuanced influences of structural homophily h S without the interference of h L and h F 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 h S . The results for some of the datasets such as Citeseer, Amazon-ratings, and Coauthor-physics, we can clearly observe the accuracy increases with h S while for datasets such as Corafull and Coauthor-CS, we can only see the general tendency of alignment with noises. We speculate that for Corafull and Coauthor-CS, the h S is not as uniform as other datasets for the nodes in one class, leading to the noises.To investigate when GNNs are better than MLP, we show the differences in the performance between GNNs and MLP in the structural homophily h S shows a strong correlation with the differences in the performance between GNNs and MLP. This is because h S measure the consistency of the structural information of nodes within the same class, thereby reflecting the differences in the performance between and MLP. We also observe that the h KR has the highest correlation with differences, confirming the effectiveness of the classifier-based metrics in measuring the differences in the performance between GNNs and MLP [39] .In our experiments on real-world datasets, we explore the correlation between all the metrics and model performance. In addition to the widely used Pearson correlation, we employ Kendall's Tau rank correlation to assess these relationships. Let x and y be two observed variables with x, y ∈ R N , the Pearson correlation ρ can be calculated asEQUATIONwhere x and ȳ are the means of x and y respectively.Kendall's Tau rank correlation [4] τ can be calculated asEQUATIONwhere concordant pairs occur when the ranks of both variables agree, while discordant pairs occur 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 no assumptions of the data distribution and are robust to outliers. The correlation of all the metrics 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 J G h still shows the highest correlation with GNNs performance compared with other types of metrics, which confirms the necessity of disentangling graph homophily.To investigate the similarity of the information contained in graph homophily metrics and GNNs performance metrics, we show the Pearson correlation of these metrics on real-world datasets in Figure 8 . We can see a high correlation among the homophily on label aspect (including h edge , h node , h class , h adj , h den , h 2hop , and h nei ). These metrics measure the label consistency across the graph topology, sharing a similar characteristic. This also holds for the homophily on the structural aspect (including LI, h N C , h agg , and h S ), since these metrics measure how informative the neighbors are for the node labels. However, the Pearson correlation among the homophily on feature aspect (h GE , h LS-cos , h LS-cos , h attr , h CF , and h F ) is low. We speculate that this is because different types of feature aspect (h GE , h CF , and h F ) or different similarity measurements (h LS-cos and h LS-cos ) could vary a lot for real-world datasets.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.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 [39] ). 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 [66, 45, 52] .In 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. This type of personalized design has been explored in current GNN research on heterophilic graphs [62, 11] , yet it holds significant potential for improving overall model performance.h C F h F h K R h G N B h S V M J ¬ G h J G h h edge h node h class h adj h den h 2hop h nei LI h N S h agg h S h GE h LS-cos h LS-euc h attr h CF h F h KR h GN B h SV M J ¬G h J GAs 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? To address this issue, we can enhance current GNNs using message-passing calibration and graph rewiring.For the message passing calibration, several methods, such as GPRGNN [8] , FB-GNNs [43] , and 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 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 [63] , GloGNN [31] , WRGNN [56] ) 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 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 class-imbalanced 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-GNN [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.The feature homophily proposed in this paper measures how node features are influenced by their neighbors. To our knowledge, only a 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 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.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.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 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.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 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.Previous studies [22, 12] 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.A recent study [65] 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 [44] , 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.We first specify the ranges of three types of homophily and spectral radius8 of an adjacency matrix, which are used for the approximation in partial derivative process:EQUATIONG.1 Proof of Theorem 1Theorem 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 ¬G and graph-aware models M G is:EQUATIONwhereJ N = Yu ̸ =Yv [2C(C-1)] -1 ∥µ Yu -µ Yv ∥ 2 C -1 |σ 2 | , J ¬G h = 1-( h F ρ(A) ) 2 (C( 1-h L C-1 ) 2 +C (1-h S ) 2 C-1 +( h L C-1 C-1 ) 2 ) 1-( h F ρ(A) )( h L C-1 C-1 ) 2 ,andJ G h = ( h L C-1 C-1 ) 2 (C( 1-h L C-1 ) 2 + (1-h S ) 2 C-1 +( h L C-1 C-1 ) 2 ) J ¬G h .Proof. We have the objectiveEQUATIONThen, we derive the objective for graph-agnostic models M ¬G and graph-aware models M G respectively as followsFor the graph-agnostic models, we let H u = X u . The structural-agnostic feature m in class c is sampled from a Gaussian distribution N c,m (µ c,m , σ 2 c,m ). We use N ∈ R C×M to denote the distributions of structural-aware for all the classes with mean µ ∈ R C×M and standard deviation σ 2 ∈ R C×M in the matrix form.For the structural-aware feature m of node u, we have9 EQUATIONNext, to simplify the expression, we letEQUATIONThen we have the feature distribution of node u X u,m ∼ N (μ u,m , σ2 u,m )where μYu,m = (1EQUATIONWhen two nodes u and v share same labels, i.e.,Y u = Y v , we haveEQUATIONThen the expectation of intra-class distance of X can be expressed asEQUATIONWhen two nodes u and v share different labels, i.e.,Y u ̸ = Y v , we haveEQUATIONThen the expectation of inter-class distance of X can be expressed asE Yu̸ =Yv,ϵ ∥X u -X v ∥ 2 = E Yu̸ =Yv,ϵ M m=0 (X u,m -X v,m ) 2 = M m=0 E Yu̸ =Yv,ϵ (X u,m -X v,m ) 2 = 2C -1 (1 -ω 2 (CE ϵ [p 2 1 ] + p 2 0 )) -1 σ 2 + [C(C -1)] -1 (1 -ωp 0 ) -2 Yu̸ =Yv ∥µ Yu,: -µ Yv,: ∥ 2 (56)Then, we come back to the objective by combining Eq. ( 54) and Eq. ( 56)EQUATIONThen we take back p 0 , p 1 , and ω with h L , h S , and h FEQUATIONSo we haveEQUATIONThen, we can rewrite the objective asEQUATIONwhereEQUATIONFor graph-aware models, we have H u = 1 Du v∈N (u) X v , where X is the structural-aware features as in Section G.1.1. For the representation m in node u, we haveEQUATIONWe take the result of (I C -ωS) -1 N :,m as shown in Eq. ( 50). Then we haveEQUATIONThen we have the distribution of the representation of node uEQUATIONwhereEQUATIONWhen two nodes u and v share same labels, i.e.,Y u = Y v , we haveEQUATIONThen the expectation of intra-class distance of H can be expressed asEQUATIONWhen two nodes u and v share different labels, i.e.,Y u ̸ = Y v , we haveEQUATIONThen the expectation of inter-class distance of H can be expressed asEQUATIONThen, we come back to the objectiveEQUATIONLet's consider the termEQUATIONWe notice the second term(1-ω 2 (CE[p 2 1 ]+p 2 0 )) (1-ωp0) 2 = J ¬Gh , thereby we simplify the expression asEQUATIONThen we take back p 0 , p 1 , and ω with h L , h S , and h F as in Eq. ( 58)[(1 -ωp 0 ) -1 -1] 2 [(1 -ω 2 (CE[p 2 1 ] + p 2 0 )) -1 -1] = ( h L C-1 C-1 ) 2 (C( 1-h L C-1 ) 2 + C (1-h S ) 2 C-1 + ( h L C-1 C-1 ) 2 ) J ¬G h (73)Then, we can rewrite the objective asEQUATIONwhereEQUATIONG.2 Proof of Theorem 3.1Theorem 3.1. The partial derivative of J ¬G h with respect to label homophily h L satisfies,EQUATIONProof. For the graph-agnostic models, we take the partial derivative ofEQUATIONTake the approximations of T h,UP and T h,DOWN are given in Eq. (87) back toEQUATIONIt is easy to see 2C [ρ(A)(C-1)] > 0, so the sign of ∂J ¬G h ∂h L is solely depend on h F . Therefore, we haveEQUATIONG. EQUATIONFrom Eq. ( 46), we have 2C ρ 2 (A)(C-1) 1 -( h F ρ(A) )( h L C-1 C-1 ) 2 > 0, h 2 F ≥ 0,EQUATIONwhere 0 < h - L < h + L < 1 and -1 < ĥF < 1.Proof. We take the partial derivative ofEQUATIONwhereEQUATIONNext, we approximate T h,UP and T h,DOWN with Eq. ( 46)EQUATIONThen take back to Eq. ( 86)EQUATIONwhereEQUATIONAs a result, the sign of ∂J ¬G h ∂h F satisfies the following conditions:EQUATIONThen we discuss the influence of h L toEQUATION). In this case, we haveEQUATIONThe solution of this condition for hEQUATIONConversely, If ĥF ≤ -1, thenEQUATION). In this case, we haveEQUATIONThe solution of this condition for hEQUATIONIt is easy to show that 0 < h - L < h + L < 1. So far, we already know that∂J ¬G h ∂h F > 0 when h L > h + L and ∂J ¬G h ∂h F < 0 when h L < h - L for all h F ∈ (-1, 1). Then, for h - L < h L < h + L , the sign of ∂J ¬G h∂h F is dependent on h F as shown in Eq. (88). In conclusion, we haveEQUATIONG.5 Proof of Theorem 2.1Theorem 2.1. The partial derivative of J G h with respect to label homophily h L satisfies,EQUATIONProof. For the graph-aware models, we approximate the J G h with Eq. ( 46)EQUATIONThen we take the partial derivative with respect to hEQUATIONWe can see that the first term monotonically increases with respect to h L and the second term is always positive for h L ∈ [0, 1]. So we haveEQUATIONG.6 Proof of Theorem 2.2Theorem 2.2. The partial derivative of J G h with respect to structural homophily h S satisfies,EQUATIONProof. We take the partial derivative ofEQUATIONFrom Eq. ( 46), we have EQUATIONEQUATIONwhere 0 < h - L < h + L < 1 and -1 < ĥF < 1. The expressions and detailed calculation of h - L , h + L , and ĥF are shown in Appendix G.4.Proof. For the graph-aware models, we take the partial derivative ofEQUATIONSince the term( h L C-1 C-1 ) 2 (C( 1-h L C-1 ) 2 +C (1-h S ) 2 C-1 +( h L C-1 C-1 ) 2 ) ≥ 0, the sign of ∂J G h ∂h F is the determined by ∂J ¬G h ∂h F except for h L = 1C , which leads to the similar results as graph-aware modelsEQUATIONNeurIPS Paper ChecklistJustification: All the data used in this paper is public and the research doesn't violate the NeurIPS 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).There we do not consider the inter-class structural information because the structural homophily represents a property of a graph instead of the node distinguishability[39]. The detailed discussion of the node distinguishability is shown in Section 4.2.We also calculate the partial derivative of J ¬G h and discuss the impact of three types of homophily on M ¬G in Appendix D.We also show the detailed influences of hL, hS, and hF individually to MLP or GCN in Appendix E.6, which correlates well with our theoretical results of the homophily impact.We measure the performance of MLP to verify the effectiveness our proposed J ¬G h and compare the performance gap between GNNs and MLP.See the dataset statistics, training details and model performance on node classification in Appendix E.1.2, E.2 and E.3, respectively.In addition to the Pearson correlation, we show Kendall's Tau rank correlation[4] in Appendix E.10. Besides, we show the correlations between the metrics with performance gaps between GNNs and MLP in Appendix E.9.Processing & Management, 60(2):103209, 2023. [62] K. Wang, G. 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.This definition is not directly given in the original paper[46]. We define this ratio based on the proposition[46] that a high intra-class neighborhood similarity and a low inter-class neighborhood similarity improves GNN performance.We consider the spectral radius from a general case in a graph. Here the specified range is further confirmed by the values of ρ(A) in real-world datasets as shown in Table2.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. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

2. The connections and distinctions between the proposed metrics and the existing metrics from the label, feature, and structure perspectives need further clarification.
questions: questions: None
limitations: limitations: please check the weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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?
2. How to translate the finding to real-world applications?
limitations: limitations: Lack concrete examples for readers’ understanding.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2) 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?
questions: 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: limitations: The authors should discuss limitations of their paper and proposed method.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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?

3. 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.

4. 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.

Some typos:
- Line 12: "element" -> "elements"
- Line 61: "i.i.d.assumption" — missing space
- Line 62: "Compared previous" -> "Compared to the previous"
- Line 69: "In addition, Our" -> "In addition, our"
- Line 82: It is written that $I_E$ is a matrix, in this case, it should be from $R^{E\times E}$
questions: questions: 1. In Section 3.1, many label homophily measures are introduced. Which one is chosen by the authors?

2. In equation (2), how exactly $\sigma_{max}$ is computed?

3. 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.

4. 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.

5. How performance is measured in Table 1?
limitations: 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.

Comments: title: Reply 2 nd rebuttal
reply to your concerns
Thanks
Rebuttal - 2nd Response
Thank you
Comment for the response
Part 4/4
Part 3/4
Part 2/4
Part 2/2
References
Part 2/2
comment: Please let me know if my responses have addressed your concerns. Thank you!
Please let me know if our responses have addressed your concerns. Thank you!
Thank you for your positive rating and valuable suggestions.
I appreciate the author for addressing my questions. The "Diagrams of 3 types of homophily" you provide in the rebuttal pdf helps me to understand your model better. I will maintain my positive score.
## W4
Could you please provide more details on why class-balanced assumption does not affect the results and conclusions? In particular, could you please clarify whether the following is true: “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”?

## RW4 - 2nd

Thank you for your additional review comments. You are correct that the $\frac{1}{C}$ factor in Theorem 2.2 is derived under the assumption of balanced datasets, as many current studies do not adequately address the challenges posed by unbalanced data [1, 2, 3, 7, 8]. Given that handling unbalanced data is not the primary focus of our current work and the absence of a standard benchmark for imbalanced data in heterophilous graphs, we conducted a preliminary experiment using synthetic datasets with imbalanced data. The experimental results, presented in the table below, suggest that the conclusions of Theorem 2.2 remain valid and are not significantly impacted by data imbalance. However, we agree that addressing unbalanced data will be crucial in future work, particularly for model design.

The table below illustrates how varying $h_L$ impacts GCN performance on a node classification task. We examine a scenario with 3 classes and 1,000 nodes, reporting the accuracy and standard deviation across 5 random runs. The cases are: 1) balanced classes (33\%/33\%/33\%), 2) imbalanced classes case 1 (60\%/30\%/10\%), and 3) imbalanced classes  case 2 (80\%/10\%/10\%).

| $h_L$ | 0.0 | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0 | 
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 
| Balanced | 87.44±4.14 |74.32±4.83 |60.72±6.77 |**53.44±6.90** |58.56±4.53 |72.56±3.69 |81.12±2.36 |90.08±4.13 |96.80±1.47 |98.00±1.36 |99.36±0.61 |
| In-balanced 1 | 90.16±3.18 |83.12±3.50 |71.60±7.81 |**63.28±4.06** |68.24±5.21 |76.88±4.11 |83.04±2.91 |88.80±3.31 |92.56±2.63 |94.64±2.27 |97.84±1.69 |
| In-balanced 2 | 80.92±3.98 |80.00±1.62 |**77.12±0.52** |78.96±2.52 |79.36±2.66 |80.36±2.94 |82.68±4.54 |85.76±5.37 |92.80±2.67 |94.12±2.45 |96.40±1.90 |

The results demonstrate that as $h_L$ increases, GCN performance initially declines and then improves across both balanced and imbalanced datasets. This trend aligns with the conclusions of Theorem 2.2, which describe that GNN performance reaches its lowest point at mid-level values of $h_L$. Therefore, under the in-balanced classes, the conclusions from Theorem 2.2 still hold.

## Q4
Thanks for the detailed response! Just to clarify – is it true that this invariance holds for the estimate (6) but may not hold for the original definition (or it is hard to prove it there)?

## RQ4 - 2nd

Yes, it is hard to prove the original definition. As indicated in line 167, both $h_{F,m}$ and $\boldsymbol{X_{:,m}(0)}$ are unknown, making it impossible to measure homophily directly from Eq. (4). To overcome this challenge, we minimize Eq. (6) to estimate $h_{F,m}$, leveraging the fact that the intra-class distances of $\boldsymbol{X_{:,m}(0)}$ are small.

To address the concern about the accuracy of the estimation in Eq. (6), an experiment has been conducted to evaluate the accuracy of this estimation on synthetic datasets. For a given original $h_F$, the estimated $h_F^*$ using Eq. (6) and report the differences $|h_F - h_F^*|$ are tabulated below.

| Original $h_F$ | -1.00 | -0.80 | -0.60 | -0.40 | -0.20 | 0.00 | 0.20 | 0.40 | 0.60 | 0.80 | 1.00 | 
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 
| Estimated $h_F*$ | -0.95 | -0.80 | -0.62 | -0.42 | -0.21 | -0.01 | 0.20 | 0.41 | 0.61 | 0.86 | 1.00 | 
| Differences $\|h_F-h_F*\|$ | 0.05 | 0.00 | 0.02 | 0.02 | 0.01 | 0.01 | 0.00 | 0.01 | 0.01 | 0.06 | 0.00 

The results show that the average difference is less than 2\%. In our view, this is an acceptable estimation.

## Q5
Here my question was about “model performance” – which measure is used here?

## RQ5 - 2nd

Thank you for clarifying this with us. We use the **accuracy** for datasets with more than two classes and the **AUC-ROC** for binary-class datasets to evaluate the model performance on the node classification. This measurement has been widely used for assessing GNN performance [1, 2, 3, 6, 7, 8].

Thank you for your valuable suggestions! We will revise our paper accordingly.
Thank you for your detailed response! I have several questions to clarify.

W4. Could you please provide more details on why class-balanced assumption does not affect the results and conclusions? In particular, could you please clarify whether the following is true: “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”?

Q4. Thanks for the detailed response! Just to clarify – is it true that this invariance holds for the estimate (6) but may not hold for the original definition (or it is hard to prove it there)?

Q5. Here my question was about “model performance” – which measure is used here?
We are grateful for your recognition and solid support of our paper. Your insightful suggestions have greatly improved it.
I would like to thank the authors for their effort in addressing the concerns and questions raised by me and my fellow reviewers. All of my issues/questions have been adequately addressed. I will therefore increase my score to accept.
**C. Variance Changing**

Changing the variance of $\boldsymbol{X_{:,m}}$ can be seen as the combination of scaling and shifts. Assume node features follow a Gaussian distribution $N(\mu,\sigma^2)$, after the operation of changing the variance from $\sigma^2$ to $\beta\sigma^2$, we have new node features as

\begin{equation}
    \boldsymbol{X_{:,m}'} = \sqrt{\beta}(\boldsymbol{X_{:,m}}-\mu)+\mu
\end{equation}

where $\boldsymbol{X_{:,m}'}$ is calculated by deducing $\mu$, multiplying $\sqrt{\beta}$, and adding $\mu$. We already show the estimation of feature homophily is invariant to the operations of feature shifts and scaling. Since the operation of variance changing is a combination of scaling and shifts, we can conclude that the estimation of feature homophily is invariant to the variance changing. We will add these proofs to the Appendix later.

## Q5: How performance is measured in Table 1?

## RQ5: 

The measurement of the performance in Table 1 is introduced in Line 330, where we show the Pearson correlation between all the metrics and model performance on the 31 real-world datasets. Specifically, each cell in Table 1 denotes a correlation value, which is calculated using the corresponding homophily metrics and model performance on 31 datasets. For example, for $h_{edge}$ on GCN, we measure the $h_{edge}$ (in Table 3) and the performance of GCN (in Table 4) on 31 datasets. Then, we have 31 values for both the homophily metric and model performance. Finally, we calculate the correlation between these two sets of data, which reflects how well the homophily metric aligns with model performance. We hope this clarification helps in understanding the performance shown in Table 1.

**References**

[1] Ma, Y., Liu, X., Shah, N., Tang, J. Is Homophily a Necessity for Graph Neural Networks? In ICLR, 2022.

[2] Wang, J., Guo, Y., Yang, L., Wang, Y. Understanding Heterophily for Graph Neural Networks. CoRR abs/2401.09125, 2024.

[3] Lee, S. Y., Kim, S., Bu, F., Yoo, J., Tang, J., Shin, K. Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective. CoRR abs/2402.04621, 2024.

[4] Chang, B., Xu, T., Liu, Q., et al. Study on Information Diffusion Analysis in Social Networks and Its Applications. Int. J. Autom. Comput. 15, 377–401, 2018.

[5] Shi, D., Han, A., Lin, L., Guo, Y., Wang, Z., Gao, J. Design Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networks. arXiv:2401.14580, 2024.

[6] Luan, S., Hua, C., Xu, M., Lu, Q., Zhu, J., Chang, X.-W., Fu, J., Leskovec, J., Precup, D. When Do Graph Neural Networks Help with Node Classification? Investigating the Homophily Principle on Node Distinguishability. In NeurIPS, 36, 2024.

[7] S. Luan, C. Hua, Q. Lu, J. Zhu, M. Zhao, S. Zhang, X.-W. Chang, and D. Precup. Revisiting heterophily for graph neural networks. In NeurIPS, 2022.

[8] O. Platonov, D. Kuznedelev, A. Babenko, and L. Prokhorenkova. Characterizing graph datasets for node classification: Homophily-heterophily dichotomy and beyond. In NeurIPS, 2024.

[9] Luan S, Hua C, Lu Q, et al. Revisiting heterophily for graph neural networks[J]. In NeurIPS, 2022.

[10] Coleman J S. Relational analysis: The study of social organizations with survey methods[J]. Human organization, 1958.

[11] Jiang W, Gao X, Xu G, et al. Challenging Low Homophily in Social Recommendation[C], Proceedings of the ACM on Web Conference 2024.
## Q4: In equation (5), how these values behave when we do certain feature transformations: shifts, scaling, or changing variance?

## RQ4:

Thank you for raising the question about the feature transformations on feature homophily in Eq. (5). We need to clarify that the Eq. (4)(5) are the definition of feature homophily and the measurement are introduced in Eq. (6). Then we will prove how this estimation of feature homophily in Eq. (6) is invariant to feature transformation including shifts, scaling, or changing variance as follows.

We first define the problem: In a graph $\mathcal{G}=\{\mathcal{V},\mathcal{E}\}$ with $N$ nodes, there are node labels $\boldsymbol{Y}$ and node features $\boldsymbol{X_{:,m}}$ in dimension $m$. We can estimate the feature homophily $h^*_{F,m}$ for feature in dimension $m$ as:
\begin{equation}
h_{F,m}^{*}(\mathcal{G},\boldsymbol{X_{:,m}},\boldsymbol{Y}) = \text{arg} \min_{h_{F,m}} \sum_{\substack{u,v\in\mathcal{V},\\ Y_u=Y_v}} \left[X_{u,m}(0)-X_{v,m}(0)\right]^2, \; \text{ where } \boldsymbol{X_{:,m}}(0) = \left(\boldsymbol{I}-\frac{h_{F,m}}{\rho(\boldsymbol{A})}\boldsymbol{A}\right)\boldsymbol{X_{:,m}}
\end{equation}
We need to prove the estimation of feature homophily \textbf{is invariant to the operations of feature shifts, scaling, or changing variance.}

**A. Shifts**

Let's consider a shift of node features $\boldsymbol{X_{:,m}}$ by a constant vector $\boldsymbol{C}$:
\begin{equation}
    \boldsymbol{X_{:,m}'} = \boldsymbol{X_{:,m}}+\boldsymbol{C}
\end{equation}

Then we have structural-agnostic features as

$\boldsymbol{X_{:,m}'}(0) 
= \left(\boldsymbol{I}-\frac{h_{F,m}}{\rho(\boldsymbol{A})}\boldsymbol{A}\right)\boldsymbol{X_{:,m}'}$

$= \left(\boldsymbol{I}-\frac{h_{F,m}}{\rho(\boldsymbol{A})}\boldsymbol{A}\right)(\boldsymbol{X_{:,m}}+\boldsymbol{C})$

$=\boldsymbol{X_{:,m}}(0)+\left(\boldsymbol{I}-\frac{h_{F,m}}{\rho(\boldsymbol{A})}\boldsymbol{A}\right)\boldsymbol{C}$

Then a new estimation of $h_{F,m}'$ under this feature shift can be expressed as

$h_{F,m}'(\mathcal{G},\boldsymbol{X_{:,m}'},\boldsymbol{Y}) = \text{arg} \min_{h_{F,m}} \sum_{\substack{u,v\in\mathcal{V},\\ Y_u=Y_v}} \left[X_{u,m}'(0)-X_{v,m}'(0)\right]^2$

$= \text{arg} \min_{h_{F,m}} \sum_{\substack{u,v\in\mathcal{V},\\ Y_u=Y_v}} \left[\left(X_{u,m}(0)+\left(\boldsymbol{I}-\frac{h_{F,m}}{\rho(\boldsymbol{A})}\boldsymbol{A}\right)C_u\right)-\left(X_{v,m}(0)+\left(\boldsymbol{I}-\frac{h_{F,m}}{\rho(\boldsymbol{A})}\boldsymbol{A}\right)C_v\right)\right]^2$

$= \text{arg} \min_{h_{F,m}} \sum_{\substack{u,v\in\mathcal{V},\\ Y_u=Y_v}} \left[\left(X_{u,m}(0)-X_{v,m}(0)\right)+\left(\boldsymbol{I}-\frac{h_{F,m}}{\rho(\boldsymbol{A})}\boldsymbol{A}\right)(C_u-C_v)\right]^2$

Since $\boldsymbol{C}$ is a constant vector, we have $C_u-C_v=0$. Next, we have

$h_{F,m}'(\mathcal{G},\boldsymbol{X_{:,m}'},\boldsymbol{Y}) = \text{arg} \min_{h_{F,m}} \sum_{\substack{u,v\in\mathcal{V},\\ Y_u=Y_v}} \left[\left(X_{u,m}(0)-X_{v,m}(0)\right)\right]^2 = h_{F,m}^{*}(\mathcal{G},\boldsymbol{X_{:,m}},\boldsymbol{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 $\boldsymbol{X_{:,m}}$ by a constant $\alpha$:
\begin{equation}
    \boldsymbol{X_{:,m}'} = \alpha\boldsymbol{X_{:,m}}
\end{equation}

Then we have structural-agnostic features as

$\boldsymbol{X_{:,m}'}(0) 
= \left(\boldsymbol{I}-\frac{h_{F,m}}{\rho(\boldsymbol{A})}\boldsymbol{A}\right)(\alpha\boldsymbol{X_{:,m}'})$

$= \alpha\left(\boldsymbol{I}-\frac{h_{F,m}}{\rho(\boldsymbol{A})}\boldsymbol{A}\right)\boldsymbol{X_{:,m}'}$

$= \alpha\boldsymbol{X_{:,m}}(0)$

Then a new estimation of $h_{F,m}'$ under this feature shift can be expressed as

$h_{F,m}'(\mathcal{G},\boldsymbol{X_{:,m}'},\boldsymbol{Y}) = \text{arg} \min_{h_{F,m}} \sum_{\substack{u,v\in\mathcal{V},\\ Y_u=Y_v}} \left[X_{u,m}'(0)-X_{v,m}'(0)\right]^2$

$= \text{arg} \min_{h_{F,m}} \sum_{\substack{u,v\in\mathcal{V},\\ Y_u=Y_v}} \alpha^2\left[X_{u,m}(0)-X_{v,m}(0)\right]^2$

$= \text{arg} \min_{h_{F,m}} \alpha^2 \sum_{\substack{u,v\in\mathcal{V},\\ Y_u=Y_v}} \left[X_{u,m}(0)-X_{v,m}(0)\right]^2$

Since $\text{arg} \min_{x} (\cdot)$ is invariant to the scaling, e.g. $\text{arg} \min_{x}(cf(x))=\text{arg} \min_{x}(f(x))$, we have

$h_{F,m}'(\mathcal{G},\boldsymbol{X_{:,m}'},\boldsymbol{Y}) = \text{arg} \min_{h_{F,m}} \sum_{\substack{u,v\in\mathcal{V},\\ Y_u=Y_v}} \left[\left(X_{u,m}(0)-X_{v,m}(0)\right)\right]^2 = h_{F,m}^{*}(\mathcal{G},\boldsymbol{X_{:,m}},\boldsymbol{Y})$

Therefore, we proved the estimation of feature homophily is invariant to the operation of feature scaling.
## Q1: In Section 3.1, many label homophily measures are introduced. Which one is chosen by the authors?

## RQ1: 

As described in Footnote 6 on Page 8, we use node homophily as label homophily in our experiments.


## Q2: In equation (2), how exactly is $\sigma_{max}$ computed?

## RQ2:

We measure the standard deviation of structural information in Eq. (2), the value of $\sigma_{max}$ depends on which function of structural information $\mathcal{S}(\cdot)$ is select. As mentioned in Line 127, we use the class distribution of local neighbors $\boldsymbol{D}^{\mathcal{N}}$ as the $\mathcal{S}(\cdot)$. The maximum variance is achieved when $\boldsymbol{D}^{\mathcal{N}}$ is the most diverse for nodes within the same class, which is equal to $\sqrt{\frac{C-1}{C^2}}$ as we used in our experiments. Let me briefly introduce how exactly $\sigma_{max}$ is calculated in this scenario. This question is equal to:

Given $P\in\mathbb{R}^{N\times C}$ is a neighbor sampling probability matrix, where $p_{i,k}\in[0,1]$ and $\sum_{k=1}^C p_{i,k}=1$ for each i, we need to maximize: $\sigma_{max}=\frac{1}{C}\sum_{k=1}^C\sigma(p_{:,k})$.

We first rewrite the $\sigma(p_{:,k})$ as
\begin{equation}
    \sigma(p_{:,k}) = \sqrt{\frac{1}{N}\sum_{i=1}^N p_{i,k}^2 - \mu_k^2}
\end{equation}
where $\mu_k=\frac{1}{N}\sum_{i=1}^N p_{i,k}$

To maximize $\frac{1}{N}\sum_{i=1}^N p_{i,k}^2 - \mu_k^2$, we need the values to be as unequal as possible given the constraint $\sum_{k=1}^C p_{i,k}=1$. To get maximally unequal distribution, we have $p_{:,k}$ has one entry that is $1$ and the rest $0$ for each column $k$.

Then, let $a_k$ be the number of $1$ in column k, we have $\frac{1}{N}\sum_{i=1}^N p_{i,k}^2=\frac{a_k}{N}$ and $\mu_k = \frac{a_k}{N}$. Next, we can express the original expression as
\begin{equation}
    \frac{1}{C}\sum_{k=1}^C\sigma(p_{:,k}) = \frac{1}{C}\sum_{k=1}^C \sqrt{ \frac{a_k}{N} - (\frac{a_k}{N})^2 }
\end{equation}

We observe that this is a non-convex function. According to Jensen’s inequality, we have

\begin{equation}
    \frac{1}{C}\sum_{k=1}^C \sqrt{ \frac{a_k}{N} - (\frac{a_k}{N})^2 } \le \sqrt{ \frac{\frac{1}{C}\sum_{k=1}^Ca_k}{N} - (\frac{\frac{1}{C}\sum_{k=1}^C a_k}{N})^2 } = \sqrt{\frac{1}{C}-\left(\frac{1}{C}\right)^2}= \sqrt{\frac{C-1}{C^2}}
\end{equation}

where we get $\sigma_{max} = \sqrt{\frac{C-1}{C^2}}$ proved.

Note that this $\sigma_{max}$ only applies when using the class distribution of local neighbors, $\boldsymbol{D}^{\mathcal{N}}$, as the function of structural information $\mathcal{S}(\cdot)$. Different functions may yield different values for $\sigma_{max}$.


## Q3: 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.

## RQ3:

We highlight two key differences between label homophily ($h_L$) and structural homophily ($h_S$). First, the "atom" information, as described in line 116, for $h_L$ is the label information $Y$, while for $h_S$ it is the structural information $D^\mathcal{N}$ (where we use neighbor distribution in this paper). Second, the measurement function for $h_L$ is an indicator function of two nodes connected by topology, $\mathbb{1}(Y_u=Y_v)$, where $e_{uv}\in\mathcal{E}$. In contrast, for $h_S$, it is the consistency function between two nodes connected by their classes, $(D^\mathcal{N}_u - D^\mathcal{N}_v)^2$, where $Y_u=Y_v$ (by rewriting Eq. (2)). Each of these metrics reflects a unique aspect that the other cannot capture.

To further illustrate these differences, we provide diagrams and visualizations of three types of homophily in the author rebuttal PDF. Figures 2(a), (b), and (c) show that an increase in $h_L$ enhances the connectivity of intra-class nodes. However, even when $h_L$ is low, sometimes the performance of the GNN can still be satisfactory. This is because $h_L$ does not account for the consistency of structural information among intra-class nodes. To address this, we propose $h_S$, which captures this aspect. Figures 2(d), (e), and (f) demonstrate that an increase in $h_S$ improves the informativeness of the neighbors of intra-class nodes, making the graph resemble planar and periodic graphs.

Thus, $h_L$ and $h_S$ represent graph homophily from label and structural perspectives, respectively. Along with feature homophily ($h_F$), they provide a comprehensive understanding of graph homophily. Additional explanations of $h_L$ and $h_S$ are provided in our responses in RW2 and author rebuttal.
## Q1: 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?

## RQ1: 

Thank you for your constructive suggestions. We added the visualization of the generated graphs by CSBM-3H in Figure 2 of the submitted author rebuttal PDF. Based on this visualization, we draw the following conclusions:

**Label homophily.** As label homophily ($h_L$) increases, as shown in Figures 2(a), (b), and (c), nodes are more likely to connect with others that share the same label. Particularly, a high $h_L$ (Figure 2(c)) results in effective structural information, making it easier to delineate class boundaries. In comparison, a medium $h_L$ (Figure 2(b)) is less informative than an extremely low $h_L$ (Figure 2(a)). For instance, the absence of a red node among a red node's neighbors can help infer its class. This observation aligns with Theorem 2.1 in our paper.

**Structural homophily.** As structural homophily ($h_S$) increases, as shown in Figures 2(d), (e), and (f), neighbor distributions become more consistent. Consequently, a high $h_S$ allows us to capture effective structural information, as suggested by Theorem 2.2. Interestingly, we also find that a higher $h_S$ makes a graph resemble planar graphs [7] and periodic graphs [6]. We hypothesize this phenomenon as stable structural information leads to more regular and meaningful structural patterns. In future work, it would be interesting to explore the connection between $h_S$ and these geometric properties of graphs.

**Feature homophily.** Figure 2 (g), (h), and (i) illustrate different levels of feature homophily ($h_F$) within the same graph topology, where colors represent the distance of node features to various classes. Figure 2 (h) demonstrates that a medium positive $h_F$ causes the features of some boundary nodes to exhibit characteristics of neighboring classes. In contrast, a higher positive $h_F$ (Figure 2 (i)) increases feature dependencies, particularly affecting nodes closer to class boundaries. In real-world scenarios, a positive $h_F$ leads entities in a graph to show dependencies with their surrounding neighbors. For instance, people's opinions are influenced by their friends, resulting in similar characteristics. Conversely, a negative $h_F$ causes nodes to become more dissimilar from their neighbors. As shown in Figure 2 (g), a negative $h_F$ creates a distinct boundary between classes. Additionally, within the same classes in Figure 2 (g), nodes colors are different shades with their neighbors. This is because node features become more dissimilar due to the "repulsive force" rather than the "attractive force" induced by a negative $h_F$. In online media, people are likely to argue with those holding different opinions. After such interactions, individuals may reinforce their original opinions, a phenomenon resulting from the "repulsive force" associated with a negative $h_F$.

Finally, we have revised our manuscript according to your valuable reviews. Thank you.


## References

[1] Ma, Y., Liu, X., Shah, N., Tang, J. Is Homophily a Necessity for Graph Neural Networks? In ICLR, 2022.

[2] Luan, S., Hua, C., Xu, M., Lu, Q., Zhu, J., Chang, X.-W., Fu, J., Leskovec, J., Precup, D. When Do Graph Neural Networks Help with Node Classification? Investigating the Homophily Principle on Node Distinguishability. In NeurIPS, 2023.

[3] Wang, J., Guo, Y., Yang, L., Wang, Y. Understanding Heterophily for Graph Neural Networks. CoRR abs/2401.09125, 2024.

[4] Lee, S. Y., Kim, S., Bu, F., Yoo, J., Tang, J., Shin, K. Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective. CoRR abs/2402.04621, 2024.

[5] Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., Yang, B. Geom-GCN: Geometric Graph Convolutional Networks. In ICLR, 2020.

[6] Cohen, E., Megiddo, N. Recognizing properties of periodic graphs. In Applied Geometry and Discrete Mathematics, pp. 135-146, 1990.

[7] Barthelemy, M. Morphogenesis of Spatial Networks. Cham, Switzerland: Springer International Publishing, 2018.
[1] Ma, Y., Liu, X., Shah, N., Tang, J. Is Homophily a Necessity for Graph Neural Networks? In ICLR, 2022.

[2] Luan, S., Hua, C., Xu, M., Lu, Q., Zhu, J., Chang, X.-W., Fu, J., Leskovec, J., Precup, D. When Do Graph Neural Networks Help with Node Classification? Investigating the Homophily Principle on Node Distinguishability. In NeurIPS, 2023.

[3] Khanam, K. Z., Srivastava, G., Mago, V. The homophily principle in social network analysis: A survey. Multimedia Tools and Applications, 82(6): 8811-8854, 2023.

[4] Jiang, W., Gao, X., Xu, G., et al. Challenging Low Homophily in Social Recommendation. In Proceedings of the ACM on Web Conference, pp. 3476-3484, 2024.

[5] Gholinejad, N., Chehreghani, M. H. Heterophily-Aware Fair Recommendation using Graph Convolutional Networks. arXiv preprint arXiv:2402.03365, 2024.

[6] Niche to Discount: 12 Major Types of Retail Stores \& Retailers, FounderJar, https://www.founderjar.com/types-of-retail-stores/, 2023

[7] Xiao, C., Zhou, J., Huang, J., Xu, T., Xiong, H. Spatial Heterophily Aware Graph Neural Networks. In KDD, pp. 2752-2763, 2023.
## Q2: The connections and distinctions between the proposed metrics and the existing metrics from the label, feature, and structure perspectives need further clarification.

## RQ2
 In lines 116 and 146, we highlight the differences between the proposed structural homophily and feature homophily. These definitions represent the basic elements of a graph: label, structural, and feature information, thereby providing a comprehensive understanding of graph homophily. Label homophily ($h_L$) describes the label consistency along the topology, which has been widely used in previous studies [2, 5, 7]. However, $h_L$ cannot capture the consistency of structural information among intra-class nodes, which also influences GNN performance. To address this limitation, we propose structural homophily ($h_S$) to describe the consistency of structural information among intra-class nodes. Unlike existing structural-based metrics [1, 14], our metric allows for any kind of structural measurement function and can be easily incorporated into CSBM-3H for analysis. Feature homophily ($h_F$) measures the feature consistency of nodes with their neighbors and can be fully disentangled from $h_L$ and $h_S$, something other feature-based metrics [18] cannot achieve (as shown in line 138). Furthermore, we have included diagrams and visualizations of the three types of homophily in the author rebuttal PDF to aid in understanding these definitions. According to your suggestions, we have revised our manuscript. Thank you.

### References

[1] Ma, Y., Liu, X., Shah, N., Tang, J. Is Homophily a Necessity for Graph Neural Networks? In ICLR, 2022.

[2] Luan, S., Hua, C., Xu, M., Lu, Q., Zhu, J., Chang, X.-W., Fu, J., Leskovec, J., Precup, D. When Do Graph Neural Networks Help with Node Classification? Investigating the Homophily Principle on Node Distinguishability. In NeurIPS, 2023.

[3] Luo, Y., Shi, L., Wu, X.-M. Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification. CoRR abs/2406.08993, 2024.

[4] Xu, K., Hu, W., Leskovec, J., Jegelka, S. How Powerful are Graph Neural Networks? In ICLR, 2019.

[5] Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., Prokhorenkova, L. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? In ICLR, 2023.

[6] Wang, Y., Xiang, S., Pan, C. Improving the homophily of heterophilic graphs for semi-supervised node classification. In ICME, 2023.

[7] Li, X., Zhu, R., Cheng, Y., Shan, C., Luo, S., Li, D., Qian, W. Finding Global Homophily in Graph Neural Networks When Meeting Heterophily. In ICML, pp. 13242-13256, 2022.

[8] Suresh, S., Budde, V., Neville, J., Li, P., Ma, J. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In SIGKDD, 2021.

[9] Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., Yang, B. Geom-GCN: Geometric Graph Convolutional Networks. In ICLR, 2020.

[10] Tenenbaum, J. B., De Silva, V., Langford, J. C. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000.

[11] Nickel, M., Kiela, D. Poincare embeddings for learning hierarchical representations. In NeurIPS, 2017.

[12] Ribeiro, L. F. R., Saverese, P. H. P., Figueiredo, D. R. struc2vec: Learning node representations from structural identity. In SIGKDD, 2017.

[13] Chien, E., Peng, J., Li, P., Milenkovic, O. Adaptive universal generalized pagerank graph neural network. In ICLR, 2021.

[14] Luan, S., Zhao, M., Hua, C., Chang, X.-W., Precup, D. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. In NeurIPS 2022 Workshop: New Frontiers in Graph Learning, 2022.

[15] Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., Precup, D. Revisiting heterophily for graph neural networks. In NeurIPS, 2022.

[16] Shi, D., Han, A., Lin, L., Guo, Y., Wang, Z., Gao, J. Design Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networks. CoRR abs/2401.14580, 2024.

[17] Wang, J., Guo, Y., Yang, L., Wang, Y. Understanding Heterophily for Graph Neural Networks. CoRR abs/2401.09125, 2024.

[18] Lee, S. Y., Kim, S., Bu, F., Yoo, J., Tang, J., Shin, K. Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective. CoRR abs/2402.04621, 2024.