When Do Graph Neural Networks Help with Node Classification? Investigating the Homophily Principle on Node Distinguishability
Authors: Sitao Luan
Chenqing Hua
Minkai Xu
Qincheng Lu
Jiaqi Zhu
Xiao-Wen Chang
Jie Fu
Jure Leskovec
Doina Precup
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Neural Networks
Homophily
Heterophily
Low-pass filter
High-pass filter
Node Distinguishability
Metrics

Abstract: Homophily principle, i.e., nodes with the same labels are more likely to be connected, has been believed to be the main reason for the performance superiority of Graph Neural Networks (GNNs) over Neural Networks on node classification tasks. Recent research suggests that, even in the absence of homophily, the advantage of GNNs still exists as long as nodes from the same class share similar neighborhood patterns. However, this argument only considers intra-class Node Distinguishability (ND) but neglects inter-class ND, which provides incomplete understanding of homophily on GNNs. In this paper, we first demonstrate such deficiency with examples and argue that an ideal situation for ND is to have smaller intra-class ND than inter-class ND. To formulate this idea and study ND deeply, we propose Contextual Stochastic Block Model for Homophily (CSBM-H) and define two metrics, Probabilistic Bayes Error (PBE) and negative generalized Jeffreys divergence, to quantify ND. With the metrics, we visualize and analyze how graph filters, node degree distributions and class variances influence ND, and investigate the combined effect of intra- and inter-class ND. Besides, we discovered the mid-homophily pitfall, which occurs widely in graph datasets. Furthermore, we verified that, in real-work tasks, the superiority of GNNs is indeed closely related to both intra- and inter-class ND regardless of homophily levels. Grounded in this observation, we propose a new hypothesis-testing based performance metric beyond homophily, which is non-linear, feature-based and can provide statistical threshold value for GNNs' the superiority. Experiments indicate that it is significantly more effective than the existing homophily metrics on revealing the advantage and disadvantage of graph-aware modes on both synthetic and benchmark real-world datasets.

When Do Graph Neural Networks Help with Node Classification? Investigating the Impact of Homophily Principle on Node Distinguishability
Sitao Luan 1.2, Chenging 2 Minkai Xu", Qincheng Lu', , Zhu', Xiao-Wed Chang /5, 1, Jie Fu .Jure Juur Leskovec* Doina Doina Precup 1.2.3,t
(sitao.luan @ mail, chenqing.hua @ mail, gincheng. Iu mail, ziaqi.zzuu @ mail, chang @cs, dprecup cs) |megill.ca (minkai. jure] [ccc] wec.sssaaforr.com jiefu @ ust.hk
McGiil University: 2 Mila- Quebec Artificial Intelligence Institute; 'Google DeepMind; Sttanford University; SHKUST; Corresponding Authors
Abstract
Homophily principle, i.e., nodes with the same labels are more likely be con- nected, has been believed to be the main reason for the performance superiority of Graph Neural Networks (GNNs) over Neural Networks on node classification tasks. Recent research suggests that, even in the absence of homophily, the advantage of GNNs still exists as long as nodes from the same class share similar neighborhood patterns [38]. However, this argument only considers intra-class Node Distinguisha- bility (ND) but neglects inter-class ND, which provides incomplete understanding of homophily on GNNs. In this paper, we first demonstrate such deficiency with examples and argue that an idcal situation for ND is to have smaller intra-class ND than inter-class ND. To formulate this idea and study ND deeply. propose Con- textual Stochastic Block Model for Homophily (CSBM-H) and define two metrics, Probabilistic Bayes Error (PBE) and negative generalized Jeffreys divergence, quantify ND. With the metrics, we visualize and analyze how graph filters, node degree distributions and class variances influence ND, and investigate the combined effect of intra- and inter-class ND. Besides, we discovered the mid-homophily pitfall, which occurs widely in graph datasets. Furthermore, we verified that, in real-work tasks, the superiority of GNNs is indeed closely related to both intra- and inter-class ND regardless of homophily levels. Grounded in this observation, we propose a new sypothesis-testing based performance metric beyond homophily, which is non-linear, feature-based and can provide statistical threshold value for GNNs' the superiority. Experiments indicate that it is significantly more effective than the existing homophily metrics on revealing the advantage and disadvantage of graph- aware modes on both synthetic and benchmark real- world datasets.
1 Introduction
Graph Neural Networks (GNNs) have gained popularity in recent years as a powerful tool for graph- based machine learning tasks. By combining graph signal processing and convolutional neural networks, various GNN architectures have been proposed [27 19 50 3n 233, and have been shown outperform traditional neural networks (NNs) in tasks such node classification (NC), graph classification, link prediction and graph generation. The success of GNNs helieved to be rooted in the homophily principle (assumption) [42). which states that connected nodes tend have similar attributes [T. providing extra useful information to the aggregated features over the original node features. Such relational inductive bias thought to be a major contributor to the superiority of GNNs over NNs on various tasks [ On the other hand, the lack of homophily, i.e., heterophily, is considered as the main cause of the inferiority of GNNs on heterophilic graphs, because nodes from different classes are connected and mixed, which can lead to indistinguishable node embeddings,
making the classification task more difficult for GNNs 57
55
37| Numerous models have been
proposed to address the heterophily challenge lately 46
55
7
21
6ll
511 351
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Recently, both empirical and theoretical studies indicate that the relationship between homophily principle and GNN performance is much more complicated than "homophily wins, heterophily loses" and the existing homophily metrics cannot accurately indicate the superiority of GNNs For example, the authors in (88 stated that, as long as nodes within the same class share similar neighborhood patterns, their embeddings will be similar after aggregation. They provided experimental evidence and theoretical analysis, and concluded that homophily may not be necessary for GNNs to distinguish nodes. The paper [5 studied homophily/heterophii from post-aggregation node similarity perspective and found that heterophily is not always harmful, which is consistent with
38 R5
38 Besides, the authors in 3 have proposed to use high-pass filter to address some heterophily cases, which is adopted in as well. They have also proposed aggregation homophily, which is a
linear Sreature-indepndeer performance metric and is verified to be better at revealing the performance
advantages and disadvantages of GNNs than the existing homophily metrics [46 55 [2]. Moreover, 66 has investigated heterophily from neighhor identifiable perspective and stated that heterophily can be helpful for NC when the neighbor distributions of intra-class nodes are identifiable.
Inspite that the current literature on studying homophily principle provide the profound insights, they are still deficient: 1. 38 6 only consider intra-class node distinguishability (ND), but ignore inter-class ND; 2. 35 does not show when and how high-pass filter can help with heterophily problem; 3. There is a lack of a non-linear, feature- performance metric which can leverage richer information to provide an accurate statistical threshold value to indicate whether GNNs are really needed on certain task or not.
To address those issues, in this paper: 1. We show that, to comprehensively study the impact of homophily on ND, one needs to consider both intra- and inter-class ND and an ideal case to have smaller intra-class ND than inter-class ND; 2. To formulate this idea, we propose Contextual Stochastic Block Model for Homophily (CSBM-H) as the graph generative model. It incorporates an explicit parameter to manage homophily levels, alongside class variance parameters to control intra-class ND. and node degree parameters which are important to study homophily 38 S 3. To quantify ND of CSBM-H, we propose and compute two ND metrics, Probabilistic Bayes Error (PBE) and Negative Generalized Jeffreys Divergence (DNGJ), for the optimal Bayes classifier of CSBM-H. Based the metrics, we analytically study how intra- and inter-class ND impact ND together. We visualize the relationship between PBE, DNCI and homophily levels and discuss how different graph filters (full-, low- and high-pass filters), class variances and node degree distributions will influence ND in details; 4. In practice, we verify through hypothesis testing that the performance superiority of GNNs is indeed related to whether intra-class ND is smaller than inter-class ND, regardless of homophily levels. Based on this conclusion and the p-values of hypothesis testing, we propose Classifier-based Performance Metric (CPM), new non-linear feature-based metric that can provide statistical threshold values. Experiments show that CPM is significantly more effective than the existing homophily metrics on predicting the superiority of graph awarr- models over graph-agnostic.
2 Preliminaries
We use bold font for vectors (e.g.,v) and define connected graph G = (V,E), where is the set of nodes with a total of N elements, adjacency matrix with A., 1 if there is an edge between nodes i and j. otherwise Ar, 0. D is the diagonal degree matrix of the graph, with D., = di = Σ, Arj. The neighborhood set Ng of node i is defined as M₁ = -j eij E E}. A graph signal is vector in R-V, whose i-th entry is feature of node i. Additionally, we use X E NxF to denote the feature matrix, whose columns are graph signals and i-th row X;, = 2. is the feature vector of node i (i.e., the full-pass (FP) filtered signal). The label encoding matrix is E R.C.C where C' is the number of classes, and its i-th row Zi, is the one-hot encoding of the label of node i. We denote z; arg max, Zi, E 21,2,... .).. The indicator function 1 equals when event B happens and 0 otherwise.
the set of edges without self-loops.
the symmetric
For nodes j.j E V, if 2; = zj. then they are considered as intra-class nodes; if z; # zj. then they are considered to be inter-class nodes. Similarly, an edge et, E E is considered to be an intra-class edge if 2 = Zj. and an inter-class edge if z; # Zj.
2.1 Graph-aware Models and Graph-agnostic Models
A network that includes the feature aggregation step according to graph structure is called graph- aware (G-aware) model, e.g., GCN 27], SGC [53]; network that does not use graph structure information is called graph-agnostic (G-agnostic) model, such as Multi-Layer Perceptron with 2
2

---

layers (MLP-2) and MLP-1, A G-aware model is often coupled with a G-agnostic model because when we remove the aggregation step in G-aware model, it becomes exactly the same as its coupled G-agnostic model, egg. GCN is coupled with MLP-2 and SGC-I is coupled with 1IP-1 as below,
XW)) Wi), MLP-2: Y Soltmax(ReLU(XWo)) Wi) SGC-1: Y = Softmax (Aym X Wo), MLP-1: Y = Softmax(X Wo)
GCN: Y Paltmax(AAgin
where Agm- D-1/2A À A and ń D= D + I; Wo E RExE and W1 E RFix (1) learnable parameter matrices. For simplicity, we denote = arg max, Yi E (1,2,....0) C). The random walk renormalized matrix An 1-1 Á can also be applied GCN, which essentially a mean aggregator commonly used in some spatial-base GNNs [19] To bridge spectral and spatial methods, we use Anw in the theoretical analysis, but self-loops are not added to the adjacency matrix to maintain consistency with previous literature 88 351
To address the heterophily challenge, high-pass (HP) filter replace low-pass (LP) filter (39 Anw in GCN 55
such I A... is often used to 7 35) In this paper, we use Anw and I- Arw as the LP and HP operators, respectively. The LP and HP filtered feature matrices are represented as
H = Ar X and HHP = - ) X. For simplicity, we denote h. (H...) hh (H
To measure how likely the G-aware model outperform its coupled G-agnostic model before training them (i.e., if the aggregation step according to graph structure is helpful for node classification or not), a lot of homophily metrics have been proposed and we will introduce the most commonly used ones in the following subsection.
2.2 Homophily Metrics
The homophily metric is way to describe the relationship between node labels and graph structure. We introduce five commonly used homophily metries: edge homophily [15]], node homophily [6]. class homophily (32). generalized edge homophily [26] and aggregation homophily [35], adjusted
homophily [47] and label informativeness
47 as follows:
(fuvlese 68,7...
IwInEN, Z...
Hodge (9)
Hande (9) TD7 Evey Hiode NV Ever
[21
Helass (g)
Eg C-
hg
11 N
where h EnEri =1 (uquENs.
Euclulzo, -1) do
(2)
)) conten,,a))) Wufiee
(g)
(G) = B x (( Mean (1S(A, 2) - 2 Meau, ((S(A, 2) #2 1)}//
[21
Hedge
C 1== P
Eesoz Per oz log e2
Be, = Ea Pei log Poree
Hadj
E. Pe log
Ee Pe log
where Hy is the local homophily value for node v; [a]+ = max(0, a): he is the class-wise homophily metric [32] Mean,, ((-)) takes the average over of a given multiset of values or variables
and ((,, Z) = ÁZ(ZZ is the post-aggregation node similarity matrix; D. Eme, du Pe
De 2 Pen,2 (u,))e 1fs==o)...00) c, C1, C2 E C}.
2|
These metrics all fall within the range of [o, 1J. with value closer indicating strong homophily and implying that G-aware models are more likely to outperform its coupled G-agnostic model, and vice versa. However, the current homophily metrics are almost all linear, indeeeeden metries which cannot provide threshold value (35) for the superiority of G-aware model and fail to give an accurate measurement of node distinguishability (ND). In the following section, we focus on quantifying the ND of graph models with with homophily levels and analyzing their relations.
3
Analysis of Homophily on Node Distinguishability (ND)
3.1
Motivation
The Problem in Current Literature Recent research has shown that heterophily does not always negatively impact the embeddings of intra-class nodes, as long as their neighborhood patterns "corrupt in the same way" [X d same heterophilic neighborhood patterns. As result, their aggregated features will still be similar and they can be classified into the same class.
For example, in Figure D nodes {1.2] } are from class blue and both have the
3

---

However, this is only partially true for ND if we forget to discuss inter-class ND, e.g., node 3 in Figure i from class green and has the same neighborhood pattern (1/3 orange, 1/3 yellow and 1/3 green) as nodes (1,2), which means the inter-class ND will be lost after aggregation. This highlights the necessity for careful consideration of both intra- and inter-class ND when evaluating the impact of homophily on the performance of GNNs and an ideal case for NC would be node {1,2,4), where we have smaller intra-class "distance" than inter-class "distance". We will formulate the above idea in this section and verify if it really relates to the performance of GNNs in section g In the following subsection, we will propose a toy graph model, on which we can study the relationship between homophily and ND directly and intuitively, and analyze intra- and inter-class ND analytically.
Node I (Cass Bluc)
Node 2 (Clsss Blue)
Node 3 (Class Green)
Node 4 (Class Gram)
Figure 1: Example of intra- and inter-class node distinguishability.
3.2 CSBM-H and Optimal Bayes Classifier
In order to have more control over the assumptions on the node embeddings, we consider the Contextual Stochastic Block Model (CSBM) 11] It a generative model that is commonly used to create graphs and node features, and it has been widely adopted to study the behavior of GNNs 40 3 52 To investigate the impact of homophily on ND, the authors in [38 simplify CSBM to the two-normal setting, where the node features X are assumed to be sampled from two normal distributions and intra- and inter-class edges are generated according to two separate parameters. This simplification does not lose much information about CSBM, but 1. it does not include an explicit homophily parameter to study homophily directly and intuitively; 2. it does not include class variance parameters to study intra-class ND; 3. the authors do not rigorously quantify ND.
In this section, we introduce the Contextual Stochastic Block Model for Homophily/Heerrohhly (CSBM-H), which a variation of CSBM that incorporates an explicit homophily parameter h for the two-normal setting and also has class variance parameters o of to describe the intra-class ND. We then derive the optimal Bayes classifier (CLBayes) and negative generalized Jeffreys divergence for CSBM-H, based on which we can quantify and investigate ND for CSBM-H.
CSBM-H(QQ. ft, oid. pr, I, do, d1, K The generated graph consists of two disjoint sets of nodes, i E Co and j E Ct. corresponding to the two classes. The features of each node are generated independently, with x; generated from N N(Ho og.) and x, generated from N(H,, 1)1,, where No: 111 R and F3 is the dimension of the embeddings. The degree of nodes in Cu and C₁ are do, d1 E N respectively. For i E Co. its neighbors are generated by independently sampling from h- dg intra-class nodes and (1 - h) do inter-class nodes f the same way. As result, the FP (full-pass). LP and HP filtered features are generated as follows,
The neighbors of j C1 are generated in
i E Co : ~ og11; h4 N N og.), h: ~ N (Et (
(3)
j E Ci : 2j ~ N(1, o; hj ~ N 1), h, ~ N (ATT. (o!1)²1),
where Ao MPo m1) + ML, j h(m 1o) + po: p (1 h)0
11), a1 (1- h) -M),, oā (M(o)-o of (
(ō!P)²
di
of + (M())-of44of), (oHP)2- of + (00)) If og < of. we refer to Co as the low do variation class and C1 as the high variation class. The variance of each class can reflect the intra-class ND. We abuse the notation x; E Co for i E Co and xj E C1 for j E C1.
di
To quantify the ND of CSBM-H, we first compute the optimal Bayes classifier in the following theorem. The theorem is about the original features, but the results are applicable to the filtered features when the parameters are replaced according to equation 5
Theorem 1. Suppose of * of and og. of > O. the prior distribution for x is P( E Co) = P(x e G)) = 1/2, then the optimal Bayes Classifier (CLBayes) for CSBM-H (Ho, 1l, p1, o31, do, d1, h) is
'This implies that we generate undirected graphs. See Appendix E.1 for the discussion of directed vs. undirected graphs. See E.2 for the discussion on how to extend CSBM-H to more general settings. "To avoid unnecessary confusion: we relax 'dd and (1 (1-h)ed hi)da to be continuous values so that the visualization in the following sections more readable and intuitive, especially show the intersections of the curves.

---

1, nTx))= 2 0.5
ClBayes (z)
10, 17(x) < 0.5 (( = P(= =1/x)
exp (Q(x:))
where Q(x)) ax x b c.
of o ) ,
o of
c
pi mn 20
140 Mo
20
In
9 Fhi
See the proof in Appendix
Advantages of Bayes Over the Fixed Linear Classifier in 38 The decision boundary in [38 is defined as P = {
w (Ho + 41)/2} where parameter. This classifier only depends on μ4: μ and independent of h. However, as h changes, the "separability" of the two normal distributions should be different. The fixed classifier cannot capture this difference, and thus is not qualified to measure ND for different h. Besides, we cannot investigate how variances og of and node degrees do, d1 affect ND with the fixed classifier in [38]
(0 - pp)/1l M1ll2 is a fixed
In the following subsection, we will define two methods to quantify ND of CSBM-H, one based on CLyayes. which is precise measure but hard to be explainable; another is based on KL-divergence, which can give us more intuitive understanding of how intra- and inter-class ND will impact ND at different homophily levels. These two measurements can be used together to analyze ND.
3.3 Measure Node Distinguishability of CSBM-H
The Bayes error rate (BF) of the data distribution is the probability of node being mis-classified when the true class probabilities are known given the predictors [20). It can be used to measure the distinguishability of node embeddings and the BE for Clayays is defined as follows,
Definition (Bayes Error Rate). The Buyes error rale [20] for Cl is defined as
BE E. [P(2 CLayyes + =)] Ex [1 P(CLnayes (x) = 2 =|(=)]
Specifically, the BE for CSBM-H can be written as
BE P (x E Co) (1 Bay (x) = O| E Co)) + P(x E (1-P = 1 | E C.)) (4)
To estimate the above value, we compute Probabilistic Bayes Error (PBE) for CSBM-H as follows.
Probabilistic Bayes Error (PBE) The random variable in each dimension of æ is independently
normally distributed. a result, Q(x) defined in Theorem follows a generalized x² distribution 10 (See the calculation in Appendix C Specifically,
9
For v; Co. Q(x;) (wo, Ao) + E: my E C1, Q(x;) x (w1, Fr, A1)
where Wn = ao wi = aof the degree of freedom Fr. Ao = - 2age
no + Zado A
[41 + 2nor
b ) (#) + 2007 and & = c
b
b Then, by using the Cumulative Distribution Function 4a
(CDF) of 2 we can calculate the predicted probabilities directly as, P(C (CyTBayys(r)) O/a E Co)
CDF ( -). P(CT (x) 1/ C1) = (or. -
Suppose we have a balanced prior distribution P( Co) P(x C1) 1/2. Then, PBE CDF (W + CDF (DD))(m)
To investigate the impact of homophily on the ND for LP and HP filtered embeddings, we just need to replace (Ho, ob. of) by (Po.08. f1. of) and (ī ( ( as equation
PBE can be numerically calculated and visualized to show the relationship between h and ND precisely. However, we do not have an analytic expression for PBE, which makes less explainable and intuitive. To address this issue, we define another metric for ND in the following paragraphs.
Generalized Jeffreys Divergence The KL-divergence is statistical measure of how a probability distribution P is different from another distribution Q [ It offers us a tool to define an explainable ND measure, generalized Jeffreys divergence.
Definition 2 (Generalized Jeffreys Divergence). For random variable x which has either the
distribution P(z) or the distribution Q(x),, the generalized Jeffreys divergence is defined as
Dai P. Q) = P(x ~ PT In P(x)
+ PP(x ~ E. In (()
((x)
P(x)
3 'The Bayes classifier for multiple categories (> 2) can computed by stacking multiple expectation terms
using similar methods as in 122 [5] We do not discuss the more complicated settings in this paper.
JJeffrey divergence 2 is originally defined DxL, (PIIQ) + (xl(P]
5

---

With P(æ ~ P) = P(x ~ Q) 1/2 the negative generalized Jeffreys divergence for the two-normal setting in CSBM-H can be computed by (See Appendix for the calculation)
Fh
1
DNCI (CSB-C)
(5)
40
p
Negative Normalized Distance
Negative Variance Ratio
where d3 - (N0 -11) - (140- 11) is the squared Euclidean distance between centers; p = Sa and since we assume o < o7. we have 0 < < 1. For h and HPP we have di (2h 1) dHp
4(1-A) 4(1-h)3d3 d) The smaller DNGI the CSBM-H has, the more distinguishable the embeddings are.
From equation 5 we can see that DNGI implies that ND relies on two terms, Expected Negative Normalized Distance (ENND) and the Negative Variance Ratio (NVR): ENND depends how large is the inter-class ND d compared with the normalization term 477 + 1_, which is determined by intra-class ND (variances oo. 1)); ); NVR depends on how different the two intra-class NDs are, i.e., when the intra-class ND of high-variation class is significantly larger than that of low-variation class (p is close 0). NVR small which means the nodes are more distinguishable and vice versa.
To
Now, we can investigate the impact of homophily on ND through the lens of PBE and DNGI Specifically, set the standard CSBM-H 140 1-1, 0J. μ41 [0, 1]. o of 2, do 5, d1 = And as shown in Figure 2 its PBE and DNG curves for LP filtered feature h are bell- shaped This indicates that, contrary to the prevalent belief that heterophily has the most negative impact on ND, a medium level of homophily actually has a more detrimental effect on ND than extremely low levels of homophily. We refer to this phenomenon the mid-homophily pitfall.
The PBE and DNCI curves for H² are monotonically increasing, which means that the high-pass filter works better in heterophily areas than in homophily areas. Moreover, it is observed that h, and HP will get the lowest PBE and DNGs in different homophily intervals, which we refer to as the "FP regime (black)", "LP regime (green)", and "HP regime (red)" respectively. This indicates that LP filter works better at very low and very high homophily intervals (two ends), HP filter works better at low to medium homophily interval the original (i.e., full-pass or FP filtered) features works betters at medium to high homophily area.
Researchers have always been interested in exploring how node degree relates to the effect of homophily 38 54.. In the upcoming subsection, besides node degree, we will also take a deeper look at the impact of class variances via the homophily-ND curves and the FP, LP and HP regimes.
Sunget Cone
PBE
(b) DNEI
(c) ENND
(d) NVR
Figure 2: Visualization of CSBM-H =
2, do = 5, d1 5)
3.4 Ablation Study on CSBM-H
Increase the Variance of variatari Class 11 From Figure 3 it is observed that the variance in C₁ increases and the variance between Co and C₁ becomes more imbalanced, the PBE and DNG of the three curves go up which means the node embeddings become less distinguishable under HP, LP and FP filters. The significant shrinkage of the HP regimes and the expansion of the FP regime indicates that the original features are more robust to imbalanced variances
'We provide an open-ended discussion of imbalanced prior distributions in Appendix D 'See two more metrics, negative squared Wasserstein distance and Hellinger distance, in Appendix "This is consistent with the empirical results found in [35] that the relationship between the prediction accuracy GNN and homophily value a U-shaped curve.
E.3
'This verifies the conjecture made in [35] saying that high-pas. filter cannot address all kinds of heterophily and only works well for certain heterophily cases.

---

(a) PBE
(b) DAG
(c) ENND
(d) NVR
Figure 3: Comparison of CSBM-H with oî = 1, =5
(a) PBE
(b) DNGI
(c) ENND
(d) Negative Variance Ratio
Figure 4: Comparison of CSBM-H with of 1.9, =
especially in the low homophily area. From Figure 5 (d), we can see that the main cause is that the NVR of the 3 curves all move down but the HP curve moves less in low homophily area than other curves. This implies that the HP curve exhibits less sensitivity to within the area of low homophily,
Increase the Variance of Low-variation Class (ag = 1.9, of = 2) As shown in Figure 4 when the variance in Co increases and the variance between Co and C1 becomes more balanced, PBE and DNGI curves go up, which means the node embeddings become less distinguishable. The LP. HP and the FP regimes almost stays the same because the magnitude of NVR becomes too small that almost has effect to ND as shown in Figure (d).
Interestingly, we found the change of variances cause less differences of the 3 regimes in ENND than that in NVR and HP filter is less sensitive to changes in low homophily area than LP and FP filters. This insensitivity will have sigmificant impact the 3 regimes when p close and have trivial effect when is close to because the magnitude of NVR is too small.
Increase the Node Degree of High-variation Class (dg d1 25) From Figure 5 it can be observed that as the node degree of the high-variation class increases, the PBE and DNGI curves of FP and HP filters almost stay the same while the curves of LP filters go down with a large margin. This leads to a substantial expansion of LP regime and shrinkage of FP and HP regime. This is mainly due the decrease of ENND of LP filters and the decrease of its NVR in low homophily area also plays an important role.
Increase the Node Degree of Low-variation Class (dg = 25, d1 5) From Figure 6 have the similar observation as when we increase the node degree of high-variation class. The difference is that the expansion of L.P regime and shrinkage of FP and HP regimes not significant as before.
From 03: of we can see that increasing node degree can help LP filter reduce variances of the aggregated features that the ENND will decrease, especially for high-variation class while HP filter is less sensitive to the change of variances and node degree.
3.5 More General Theoretical Analysis
Besides the toy example, in this subsection, we aim to gain a deeper understanding how LP and HP filters affect ND in broader context beyond the two mormollll settings. To be consistent with previous literature, we follow the assumptions outlined in [8 which are: 1. The features of node i sampled from distribution F., i.e... x; ~ Fe., with mean μ4, R 2. Dimensions of æ; are independent to each other; 3. Each dimension in feature x; is bounded, i.e., a I X; I 6; 4. For node i, the labels of its neighbors are independently sampled from neighborhood distribution
To verify this, we increase o² and of proportionally. From Figure 10 in Appendix LP, and HP areas remain similar.
relative sizes of the FP,
7

---

-44
(a) PBE
(b) DXGI
(c) ENND
(d) NVR
Figure 5: Comparison of CSBM with different do 5, d1 25 setups.
12
(a) PBE
(b) DNGI
(c) ENND
(d) NVR
Figure 6: Comparison of CSBM with different do 25, d1 5 setups.
Dr, and repeated for di times. We refer to a graph that follows the above assumptions as G (V, (Fe. C}: [Da. c E C}} . C f1.....C C} and (b- a)² reflects how variation the features are. The authors in 38 analyze the distance between the aggregated node embedding and its expectation, i.e., ||h - E(h,)ll which only considers the intra-class ND and has been shown to be inadequate for a comprehensive understanding of ND). Instead, we investigate how significant the intra-class embedding distance is smaller than the inter-class embedding distance in the following theorem, which is a better way to understand ND.
Theorem 2. Suppose graph g E, (Fe,CE)) (De, E C}) meets all the above assump- tions (1-4). For nodes j, E V, suppose 2 & 2j and 2, Zu. then for constants tz, th. tHp that
satisfy l 2 Dr la 2 VF (1,5), tнр 2 (i. j) we have
(D)) vPh
P (| 2اا12 2 || æ.l12 + tx) s 2F, exp
V.(V.))
(Da(u))-
P[[| hell2 2 142-2wl1 + (n) < 2F, exp
(6)
Auy Dur(m)))
P(|IA - 11 2 |! 11 + fue) S F exp
Vio(on))
where D,(v.)) = |1 M Va(u,5) = (b a)², Di(v,,)- ll,e, M aall: Vu(v.
20,
+ 2t))
(b aj?
Di = |r: PA. (M,, m.)) Vir(u,)) (1+ zd. 23,
1 (b o)2, Prs
E
BaND... [xx
ueN(() xo-Fis
See the proof in Appendix
We see that, the probability upper bound mainly depends distance term (inter-class ND) and normalized variance term (intra-class ND). The normalized variance term of HP filter is less sensitive to the changes of node degree than that of LP filter because there is additional in the constant term. Moreover, we show that the distance term of HP filter actually depends on the relative center distance, which novel discovery. As shown in Figure when homophily decreases, the aggregated centers will move away from the original centers, and the relative center distance (purple) will get larger which means the embedding distance of nodes from different classes will have larger probability to be big. This explains how HP filter work for some heterophily cases. Overall, in more general setting with weaker assumptions, we can see that ND is also described by the intra- and inter-class ND terms together rather than intra-class ND only, which is consistent with CSBM-H.
4 Empirical Study of Node Distinguishability
8

---

Comell
Wiscossi
Tesus
Chuneleon
Squinel
Cieseee
PulMed
035699
0.4480
04106
0,750
0,2795
0.7362
6.855
0.1490
0.0888
0.2310
0:3450
0.2156
0.8233
0.7155
0.794
Beadinc
Hass
0,6458
0.041
00001
00:10
0,0620
01054
0.7657
0,8200
0.641
Homopally
Hur
0,032
0,7708
0080
00522
0.1
0.3566
0,9904
0.9626
03432
Maras
Hai
0.31
0.34
0.33
0.66
00132
0.0.57
0.17
0119
0,27
Hay
M1R26
00219
01272
00063
000100
0,17%
9.75
0.1431
0.0159
0.1311
0.1923
0.4993
Cheatfis-huoal
0000
0.00
0.00
1.00
Performance Metrics
GNB
000
0.00
1.00
1,00
p. valie
0000
0.00
0.00
0.00
1.00
1.00
1.00
1.00
0.00
ADC SEK
70.8
8.39
2.85
63:06
5.43
25.36
1.18
64 86
1881
47.02 +: 1.27
K5.12 1.64
79.66
0.75
85.5
0.76
ACC MIP
93.77
3.34
93.80
3.33
93.77
4.3.4
34,53
1.48
45001 =:
29.17 +: 1.46
74,3 1
75,51
2: 1.35
$6.23
0.54
-22
-23.49
-10.49
10.92
-0.73
0.00
0.00
0.00
1.00
NCC CCN
3.2
0.99
64.18
44.76
57.75
81.39
25.9
GCN Ks. 2
ABC MLP
0.70
3.35
26.26
46.73
76
76.25
0.13
DilT
-8.44
-19.37
-0.15
-3.00
17.46
15.45
11:34
5.14
2.47
Table 1: P-values homophily values and classifier-based performance metrics on real-world benchmark datasets. Cells marked by grey are incorrect results for both SGC v.s. MLP-1 and GCN v.s. MLP-2 and cells marked by blue are incorrect for of the 2 tests. We use 0.5 as the threshold value of the homophily metrics.
Besides theoretical analysis, in this section, we will conduct experiments to verify whether the effect of homophily on the performance of GNNs really relates to its effect on ND. If strong relation can be verified, then indicates that we can design new training-free ND>based performance metrics beyond homophily metrics, to evaluate the superiority and inferiority of G-aware models against its coupled G-agnostic models.
M4 + 14
(Ro + 14)
Ho + P
Po + P1
Ho
Po
P4
4.1 Hypothesis Testing on Real-world Datasets
Figure 7: Demonstration of how HP filter captures the relative center distance.
To test whether "intra-class embedding distance is smaller than the inter-class embedding distance" strongly relates to the superiority of G-aware models to their coupled G-agnostic models in practice, we conduct the following hypothesis testing
Experimental Setup We first train two G-aware models GCN, SGC-1 and their coupled G-agnostic models MLP-2 and MLP-1 I with fine-tuned hyperparameters provided by [35] For each trained model, we calculate the pairwise Euclidean distance of the node embeddings in output layers. Next, we compute the proportion of nodes whose intra-class node distance is significantly smaller than inter-class node distance leg.. we obtain Prop(GCN) (GCN) for GCN. We use Prop to quantify ND and we train the models multiple times for samples to conduct the following hypothesis tests:
Hg Prop(G G-aawre model) 2 Prop(G-agnostic model); H₃ Prop(G-aware G-aware model) < Prop(G-agnostic model)
Specifically, we compare GCN vs. MLP-2 and SGC-1 vs. MLP-1 on 9 widely used benchmark datasets with different homophily values for 100 times. In each time, we randomly split the data into training/validation
sets with ratio of 60% 00%%/200/20%. For the 100 samples, we conduct T-test for the means of two independent samples of scores, and obtain the corresponding p-values. The test results and model performance comparisons are shown in Table (See more experimental tests on tfte-oof-the-ar model Appendix Hp.
Authors in 33 also conduct hypothesis testing to find out when GNNs for node classification, but they test the differences between connected nodes and unconnected nodes instead of intra- and inter-class nodes.
i1 A node is considered as "significantly smaller" when the p-value for its intra-class node distance being smaller than inter-class node distance is smaller than 0.05. In other words, this node is considered significantly distinguishable. This second statistical test necessary avoid noisy nodes. In practice, we noticed that the ratio of intra-class node distance to inter-clase node distance is roughly for lots of nodes. This particularly evident when the labels are sparse and when we use sampling method. It will not only cause instability of the outputs, but also result in false results sometimes. Thus, we don't 't want to take account these "marginal nodes" into the comparison of Prop values and we found that using another hypothesis test would be helpful.

---

It is observed that, in most cases (except for GCN vs, MLP-2 on PubMed when H1 significantly holds, G-aware models will underperform the coupled G-agnostic models and vice versa. This supports our claim that the performance of G-aware models is closely related to "intra-class vs. inter-class node embedding distances", no matter the homophily levels. reminds us that the p-value can be a better performance metric for GNNs beyond homophily. Moreover, the p-value can provide a statistical threshold, such as p < 0.05. This property is not present in existing homophily metrics.
However, it is required to train and fine-tune the models to obtain the p-values, which make it less practical because of computational costs. To overcome this issue, in the next subsection, we propose a classifier based performance metric that can provide p-values without training.
4.2
Towards A Better Metric Beyond Homophily: Classifier- based Performance Metric
A qualified classifier should not require iterative training. In this paper, choose Gaussian Naive Bayes (GNB) [20] and Kernel Regression (KR) with Neural Network Gaussian Process (NNGP)
3C
to capture the feature-based linear or non-linear information.
To get the p-value efficiently, we first randomly sample 500 labeled nodes from and splits them into 60%/40% "training" and "test" data. The original features X and aggregated features H of the sampled training and test nodes can be calculated and are then fed into a given classifier. The predicted results and prediction accuracy of the test nodes will be computed directly with feedforward method. We repeat this process for 100 times to get 100 samples of prediction accuracy for X and H. Then, for the given classifier, compute the p-value of the following hypothesis testing,
Ho Acc(Classifier( H)) 2 Acc(Classifier(X)) H1 Acc(Classifier ()) Acc(Classifier( X))
The p-value can provide statistical threshold value, such as 0.05, to indicate whether H is sig- nificantly better than X for node classification. As seen in Table D KR and GNB based metrics significantly outperform the existing homophily metrics, reducing the errors from at least down to just 1 out of 18 cases. Besides, we only need small set of the labels to calculate the p-value, which makes it better for sparse label scenario. Table summarizes its advantages over the existing metrics. (See Appendix H for more details on classifier-bass performance metries, experiments synthetic datasets, more detailed comparisons on small- and large-scale datasets, discrepancy between linear and non-linear models, results for symmetric renormalized affinity matrix and running time.)
5 Conclusions
In this paper, we provide complete under- standing of homophily by studying intra- and inter-class ND together. To theoret- ically investigate ND, we study the PBE and DNG of the proposed CSBM-H and analyze how graph filters, class variances and node degree distributions will influence the PBE and DNGI curves and the FP, LP, HP regimes. We extend the investigation to broader settings with weaker assumptions and theoretically prove that ND is indeed affected by both intra- and inter-class ND. We also discover that the effect of HP fil- ter depends on the relative center distance. Empirically, through hypothesis testing, we corroborate that the performance of GNNs versus NNs is closely related to whether intra-class node embedding "distance" is smaller than inter-class node embedding "distance". We find that the p-value is a much more effective performance metric beyond homophily metrics on revealing the advantage and disadvantage of GNNs. Based on this observation, we propose classifier-based performance metric, which is non-linear feature-based metric and can provide statistical threshold value.
Performance Metries
Lineur
Feature Dependeacy
Sparse Labels
Statistccal Threshold
Non-linear
Hade
linear
x
X
X
Hage
linear
x
X
Hass
linear
X
x
X
Hag
linear
X
/
X
Hog
linear
/
X
Has
linear
X
LI
lineur
X
X
Classifier
both
Table 2: Property comparisons of performance metrics
We discuss this special case in Appendix H.4 together with some similar inconsistency instances found on large-scale datasets.
10

---

Reproducibility and Blogs
Code: http:////..aattoooo/s/aoaaaaaaa/
Blog
in
English (on
Medium): http:///neddun..com/Sttto.aaaal
Then-should-ee we- use http://wwww.............oo..o...
Blog in Chinese (on Zhihu); httpt:://htutaa/aaaea http:://hhaaalnnn..h.a...ooo//// 2hihu.cco/pp6533331555
7 Acknowledgements
This work was partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) Grant RGPPN--223-041111 RGPIN 2389 and Canadian Institute for Advanced Research (CIFAR) Grant CIFAR FS20-126, CIFAR 10450. Minkai Xu thanks the generous support of Sequoia Capital Stanford Graduate Fellowship.
References
[1] S. Abu-EI-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan, G. Ver Steeg, and A. Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference machine learning, pages 21-29. PMLR, 2019.
[2] Arora, S. S. Du, Hu, Z. Li, R. R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 32, 2019.
[3] A. Baranwal, K. Fountoulakis, and A. Jagannath. Graph convolution for semi-supervised classification: Improved linear separability and out-of-distribution generalization. arXiv preprint arXiv:2102.06966 2021.
[4] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 11X..0/806.0/261 2018.
[5] D. Bo, X. Wang, C. Shi, and H. Shen. Beyond cow-frequency information in graph convolutional networks. arXiv preprint arXiv:2101.0072 2021.
[6] Chen, S. Chen, Gao, Z. Huang, J. Zhang, and J. Pu. Exploiting neighbor effect: Conv- agnostic gnn framework for graphs with heterophily. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[7] E. Chien, Peng, P. Li, and O. Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations. https://openreview. net/forum, 2021.
[8] I. Csiszár. I-divergence geometry of probability distributions and minimization problems. The annals of probability, pages 146-158, 1975.
[9] R. B. Davies. Numerical inversion of a characteristic function. Biometrika, 60(2):415-417, 1973.
[10] R. B. Davies. Algorithm 155: The distribution of linear combination of x random variables. Applied Statistics, pages 323-333, 1980.
[11] Y. Deshpande, S. Sen, A. Montanari, and E. Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems, 31, 2018.
[12] L. Devroye, L. Györfi, and G. Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013.
[13] D. Dowson and Landau. The fréchet distance between multivariate normal distributions. Journal of multivariate analysis, 12(3):450-455 455, 1982.
[14] V. N. Fkambaram. Graph structured data viewed through a fourier lens. University of California, Berkeley, 2014.
[15] A. Faragó and G. Lugosi. Strong universal consistency of neural network classifiers. IFEE Transactions Information Theory, 1964)11146-1151, 1993.

---

[16] A. Garriga-Alonse C. E. Rasmussen, and L. Aitchison, Deep convolutional networks as shallow gaussian processes. arXiv preprint (XXiv:8808.05587, 2018.
[17] C. R. Givens and R. M. Shortt. A class of wasserstein metrics for probability distributions. Michigan Mathematical Journal, 31 31(2):33-224,, 1984.
[18] W. L. Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and
Machine Learning, 14(3):1-159 2020.
[19] W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. arXiv, 0as//706.02216 2017.
[20] T. Hastie, R. Tibshirani, J. H. Friedman, J. H. Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
[21] M. He. Z. Wei, H. Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 34, 2021.
[22] T. Hofmann, B. Schölkopf, and A. J. Smola. Kernel methods in machine learningl. The Annals of Statistics, (6(3):1171-113
2008.
[23] C. Hua, G. Rabusseau, and J. Tang. High High-order order pooling for graph neural networks with tensor decomposition. arXiv preprint arXiv:2205. 1691, 2022.
[24] H. Jeffreys. An invariant form for the prior probability in estimation problems. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 186(1007)4433-46, 1946.
[25] H. Jeffreys. The theory of probability. OuP Oxford, 1998.
[26] D. Jin, R. Wang, M. Ge, D. He, X. Li, W. Lin, and W. Zhang. Raw-gnn: Random walk aggregation based graph neural network. arXiv preprint arXiv:2206.13955 2022.
[27] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv, abs/1 609.02907, 2016.
[28] M. Knott and C. S. Smith. On the optimal mapping of distributions. Journal of Optimization Theory and Applications, 43:39 49, 1984.
[29] K. Koutroumbas and S. Theodoridis. Pattern recognition. Academic Press, 2008
[30] J. Lee, Y. Bahri, R. Novak, S. S. Schoenholz, J. Pennington, and J. Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprini /Tti:://11.00066. 2017.
[31] X. Li, R. Zhu, Y. Cheng, C. Shan, S. Luo, D. Li, and W. Qian. Finding global homophily in graph neural networks when meeting heterophily. arXiv preprint arXivv2205.073300 2022.
[32] D. Lim, X. Li, F. Hohne, and S.-N. Lim. New benchmarks for learning on non-homophilous graphs. arXiv preprint arXiv:2104. 04400440, 2021.
[33] S. Luan, C. Hua, Q. Lu, J. Zhu, X.-W. Chang, and D. Precup. When do need graph neural networks for node classification? International Conference on Complex Networks and Their Applications. 2023.
[34] S. Luan, C. Hua, Q. Lu, J. Zhu, M. Zhao, S. Zhang, X.-W. Chang, and D. Precup. Is het- erophily a real nightmare for graph neural networks to do node classification? arXiv preprint arXiv:2109.0566
2021.
[35] S. Luan, C. Hua, Q Lu, J. Zhu, M. Zhao, S. Zhang, X.-W. Chang, and D. Precup. Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35:1362- 1375, 2022.
[36] S. Luan, M. Zhao, X.-W. Chang, and D. Precup. Break the ceiling: graph convolutional networks. Advances in neural information processing systems, 32, 2019.
Stronger multi-scale deep
[37] S. Luan, M. Zhao, C. Hua, X.-W. Chang, and D. Precup. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. In NeurlPS 2022 Workshop: New Frontiers in Graph Learning, 2022.
[38] Y. Ma. X. Liu, N. Shah, and J. Tang. Is homophily necessity for graph neural networks? arXiv preprint (.X.x:220060666 34, 2021.
[39] Maehara. Revisiting graph neural networks: All we have low-pass filters, arXiv preprint 10X 2019.
12

---

[40] P. Massart. Concentration inequalities and model selection: Ecole d' Eté de Probabilités de Saint-F Flour XXXIII-20053 Springer, 2007.
[41] A. G. d. G. Matthews, M. Rowland, J. Hron, R. E. Turner, and Z. Ghahramani. Gaussian process behaviour in wide deep neural networks. arXiv preprint arXiv:/804 /804.1127,, 2018.
[42] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. Anmual review of sociology, 27(1):415-44) 2001.
[43] M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of machine learning. MIT press, 2018.
[44] I. Olkin and F. Pukelsheim. The distance between two random vectors with given dispersion matrices. Linear Algebru and its Applications, 48:257-263, 1982.
[45] L. Pardo. Statistical inference based on divergence measures. CRC press, 2018.
[46] H. Pei, B. Wei, C.-C. Chang, Y. Lei, and B. Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint 2002:2002.002877, 2020.
[47] O. Platonov, D. Kuznedelev, A. Babenko, and L. Prokhorenkova. Characterizing graph datasets for node classification: Beyond homophily-hhetrrphhily dichotomy. arXiv preprint 1eXiv:220900617 2022.
[48] Tanton. Encyclopedia of mathematics. Facts On File, Inc, 2005.
[49] A. Tsitsulin, B. Rozemberezki, Palowitch, and Perozzi. Synthetic graph generation to benehmark graph learning. arXiv preprint arXiv:2204.01376, 2022.
[50] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv, abs/1710. 10903, 2017.
[51] Y. Wang, K. Yi, X. Liu, Y. G. Wang, and S. Jin. Acmp: Allen-cahn message passing for graph neural networks with particle phase transition. arXiv preprint arXiv:2206.05437 2022.
[52] R. Wei, H. Yin, Jia, R. Benson, and Li. Understanding non con-iinerrty in graph neural networks from the bayesian-inference perspective. arXiv preprint arXiv:2207.13311, 2022.
[53] F. Wu, T. Zhang, A. H. d. Souza Jr, C. Fifty, T. Yu, and K. Q. Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv: 2902.07155 2019.
[54] Y. Yan, M. Hashemi, K. Swersky, Y. Yang, and D. Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint 102iv22102.06462, 2021.
[55] J. Zhu, R. A. Rossi, A. Rao, T. Mai, N. Lipka, N. K. Ahmed, and D. Koutra, Graph neural networks with heterophily, arXiv preprint arXiv:2009. 13566, 2020.
[56] Zhu, R. A. Rossi, A. Rao, T. Mai, N. Lipka, N. K. Ahmed, and D. Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 11116-11176, 2021.
[57] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra. Beyond homophily in graph
neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
13


Reviews:
[{"review_id": "cymFvutyDi", "reviewer": "Reviewer_RYrF", "summary": "The paper delves deeper into the topic of GNNs' superiority in node classification tasks. The authors conduct experiments to show that GNNs do better due to inter and intra class node distinguishability regardless of homophily levels as suggest by current research. They propose a new metric that sheds more light on how GNNs work.", "questions": "1. Anything special about the PubMed dataset causing incorrect guesses? Also, Chameleon and Squirrel datasets have more incorrect guesses than other \"less homophilic\" datasets. Any way to visualize ND to pin point where the difference is coming from?\n\n2. Any comment on the time complexity trade-offs between homophily metrics and classifier based ones?\n\nMinor:\nline 18: \"it is significantly\" instead of \"it significantly\" \nline 321: \"split\" instead of \"splits\"", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "GNNs are a hot topic and studying how they work and what settings are conducive for GNNs to be more effective is important. This paper does that and proposes a new metric to that end. ", "weaknesses": "1. Since the crux of the paper is about node distinguishability (ND), it would be nice to see inter and intra ND visualizations of the datasets used similar to Figure 1 (toy example).\n\n2. I'm not sure the claim \"superiority of GNNs is indeed closely related to both intra- and inter-class ND regardless of homophily levels\" is sufficiently backed by the evidence in Table 1. For example, setting a different threshold than 0.5 for homophily metrics could make them look better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1: \nSince the crux of the paper is about node distinguishability (ND), it would be nice to see inter and intra ND visualizations of the datasets used similar to Figure 1 (toy example).\n\n### R1: \nThanks for your suggestion. Actually, we do include the option to visualize CSBM-H at different homophily levels in our code in thesupplementary material. We will add some visualization in the revised version.\n\n### Q2:\nI'm not sure the claim \"superiority of GNNs is indeed closely related to both intra- and inter-class ND regardless of homophily levels\" is sufficiently backed by the evidence in Table 1. For example, setting a different threshold than 0.5 for homophily metrics could make them look better.\n\n### R2:\nThis is a good question. For the threshold problem, we would like to emphasize the following points: 1. 0.5 is a commenly used threshold value  in homophily/heterophily community to seperate homophilic and heterophilic graphs. It is not a randomly picked value and it has mathematical meaning: homophily, i.e. metric greater than 0.5, means the proportion of edges that connect nodes from the same class is larger than that from different classes in some way, and vice versa. Other threshold should have statistical or mathematical meaning and we cannot arbitrarily choose one. This property is also one of the advantages of our proposed metrics over the existing metrics. 2. We cannot manually pick different threshold values for different homophily metrics to make them \"look better\" on certain set of graphs. This will cause \"overfitting\" problem, i.e. when you use this cherry-picked threshold on other unseen datasets, it might perform badly.\n\nThus, our claim is properly backed by the results from Tables 1. Besides, we provide additional experimental evidence in Appendix G to support our claim.\n\n### Q3:\nAnything special about the PubMed dataset causing incorrect guesses? Also, Chameleon and Squirrel datasets have more incorrect guesses than other \"less homophilic\" datasets. Any way to visualize ND to pin point where the difference is coming from?\n\n### R3: \nThanks for going through Table 1 carefully and this is a very good question. From the experimental results on large-scale datasets reported in Table 4 in Appendix G.4, we observe that, for linear and non-linear G-aware models, there exists inconsistency between their comparison with their coupled G-agnostics models. For example, for $\\textit{Penn94, pokec, snap-patents}$ and $\\textit{twitch-gamers}$, SGC-1 underperforms MLP-1 but GCN outperforms MLP-2. In fact, $\\textit{PubMed}$ also belongs to this family of datasets. We do not have a proved theory to explain this phenomenon for now. But there is obviously a synergy between homophily/heterophily and non-linearity that cause this discrepancy together. And we think on this spectial subset of heterophilic graphs, we shoud develop theoretical analysis to discuss the interplay between graph structure and feature non-linearity, and how they affect node distinguishability together.\nThe current homophily values (including the proposed metrics) are not able to explain the phenomenon associated with this group of datasets. \nWe keep it as an open question and encourage people from the GNN community to study it in the future. We will add the above discussion to the revised version of this paper.\n\n\nThe visualization of ND for Chameleon and Squirrel is a good point. We will try to add this to the revised version.\n\n### Q4: \nAny comment on the time complexity trade-offs between homophily metrics and classifier based ones?\n\n### R4: \nIn Table 9 in Appendix G.5 (in supplementary material), we provide the running time of CPMs on small- and large-scale datasets. The running time of  CPM is short - it takes several minutes with 1 NVIDIA V100 even on large-scale datasets such as pokec and snap-patents, which contain  millons of nodes and tens of millions of edges. In comparison, training GCN on these datasets will take several hours. It takes even days for SOTA models, e.g. ACM-GCNs, to train on them."}, {"review_id": "xEEeF6mnW5", "reviewer": "Reviewer_FryU", "summary": "Recent research indicates that Graph Neural Networks (GNNs) maintain their advantage even in the absence of homophily, as long as nodes from the same class exhibit similar neighborhood patterns. This argument, however, primarily considers intra-class Node Distinguishability (ND) while overlooking inter-class ND, thus providing an incomplete understanding of homophily. Therefore, the authors in this paper propose that an ideal ND scenario entails smaller intra-class ND relative to inter-class ND. To substantiate this, the authors introduce the Contextual Stochastic Block Model for Homophily (CSBM-H) and define two ND metrics: Probabilistic Bayes Error (PBE) and negative generalized Jeffreys divergence. Experimental results reveal that the supremacy of GNNs is indeed closely tied to both intra- and inter-class ND, irrespective of homophily levels.\n", "questions": "\nN/A", "limitations": "While I do not consider myself an expert in this area, I appreciate the content of this paper. It addresses a highly significant issue, and proposes that an ideal ND scenario would have smaller intra-class ND compared to inter-class ND. To formulate this idea, the authors introduce the Contextual Stochastic Block Model for Homophily (CSBM-H) and define two ND metrics: Probabilistic Bayes Error (PBE) and negative generalized Jeffreys divergence. The proof is robust and the paper appears to be strongly grounded in the subject matter.\n", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "\n1. The paper addresses a highly significant issue.\n2. The proposed CSBM-H and the defined metrics illustrate that the superiority of GNNs is indeed closely linked with both intra- and inter-class ND, regardless of homophily levels. The results are interesting.\n3. The paper is solidly grounded in its field.\n", "weaknesses": "\nN/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks so much for your nice review and strong recognition to our contributions."}, {"review_id": "D7OVruErgd", "reviewer": "Reviewer_GCuM", "summary": "The authors analyze the node distinguishability in attributed graphs under the prism of homophily. They consider the binary CSBM model. They compute the classification error rate on the original features and of low- and high-frequency filters; they study the influence of inter- and intra-class variance on their performances. The authors propose new metrics based on these variances and on the comparison between GNN and NN.\n", "questions": "A few remarks:\n\nL. 75 are the features in R or R^F? and l. 154, in F_h?\n\nL. 157 what is FP? In eq. 3 the authors could remind what are the FP and LP filters among the many quantities.\n\nTheorem 1: I would not call it the optimal Bayes classifier since it is restricted to the features only; it does not take in account the graph of the CSBM. Also, this is just the optimal classifier for a binary Gaussian mixture; maybe it is not worth a theorem.\n", "limitations": "The authors did not discuss possible limitations.", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "I am not very familiar with the literature needed to assess the originality of this article.\n\nIt is well written.", "weaknesses": "For me it seems the article mainly studies the separability of a binary Gaussian mixture. The principle it derives (l. 347, whether intra-class node embedding \"distance\" is smaller than inter-class node embedding \"distance\") just means the two Gaussians do not overlap.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1: \nFor me it seems the article mainly studies the separability of a binary Gaussian mixture. The principle it derives (l. 347, whether intra-class node embedding \"distance\" is smaller than inter-class node embedding \"distance\") just means the two Gaussians do not overlap.\n\n### R1: \nThanks for carefully going through our paper, but we think you might oversimplify our results and would like to clarify the contributions of our paper. The main goal of Section 3 is not \"studies the separability of a binary Gaussian mixture\". Instead, we are actually interested in how the separability (node distinguishability) changes as homophily level $h$ changes from 0 to 1 and how to use a curve to show the whole picture. We are also interested in how the curves for different graph filters intersect with each other. Researchers are intrigued by these topics, but these problems remain underexplored and not well-understood in the current GNN community. \nAlso, the simplified two-normal setting is widely used to study various tasks on graphs, including classification on heterophilic graphs [2], as mentioned at the beginning in section 3.2.\n\nIn addition, rather than derived from the two-normal setting, the principle is motivated from the example in Figure 1 as stated in Section 3.1. We use CSBM-H to formulate the principle as stated in line 134.\n\nFurthermore, the two-normal setting is a toy example to study the principle intuitively and  the principle does not just mean \"two Gaussians do not overlap\". In fact, its importance lays in that it provides a new way to develop metrics beyond homophily values, e.g. classifier-based performance metrics, to quantify node distinguishability (ND). Those metrics are verified to be better than homophily values, however, this principle has never been studied for understanding the effect of homophily. Our paper fills the gap and we believe it can provide new tools for researchers to explore heterophily in the future. Thus, we hope you can re-evaluate the contribution and novelty of our paper.\n\n### Q2: \nL. 75 are the features in R or R^F? and l. 154, in F_h?\n\n### R2: \nWe use $R^F$ because section 2 just gives a  general introduction of graph. But from your feedback, we found that this might cause some unnecessary confusion. Thus, we decide to use $R^{F_h}$ in the revised version.\n\n### Q3: \nL. 157 what is FP? In eq. 3 the authors could remind what are the FP and LP filters among the many quantities.\n\n### R3: \nFP is for Full-pass. Thanks for the suggestion and we will add explaination to FP, LP and HP before equation 3 in the revised version.\n\n### Q4: \nTheorem 1: I would not call it the optimal Bayes classifier since it is restricted to the features only; it does not take in account the graph of the CSBM. Also, this is just the optimal classifier for a binary Gaussian mixture; maybe it is not worth a theorem.\n\n### R4: \nThanks for the suggestion. As mentioned in line 163-165, the theorem is about $x$ (feature-only), but the results are applicable to $h$ and $h^{HP}$ (i.e. the graph information of the CSBM-H is included in $h$ and $h^{HP}$) when the parameters are replaced according to Equation 3. Thus, the optimality will be kept for graphs with different homophily levels and with different filters. We will emphasize this sentence in case other readers miss it. About the naming problem, please refer to [1]. \n\nThe result from theorem 1 is important to quantify the node distinguishability of CSBM-H and is firstly proposed to study homophily. When people try to study more complicated variants of CSBM-H in the future, theorem 1 is also a crucial tool. Thus, we think it's worth a theorem.\n\n\n[1] https://en.wikipedia.org/wiki/Bayes_classifier\n\n[2] Is Homophily a Necessity for Graph Neural Networks?. In International Conference on Learning Representations."}, {"review_id": "6JBBjUNj6U", "reviewer": "Reviewer_NHN6", "summary": "This paper studies when Graph Neural Networks (GNNs) can help with node classification tasks. The authors first focus on a variant of the Contextual Stochastic Block Model (CSBM) and propose new metrics for node distinguishability based on this model. The authors carry out comprehensive experiments and empirically characterize the regimes when original, low-pass filtered and high-pass filtered features are more helpful. In addition, the authors propose two additional hypothesis testing based metrics for deciding if GNNs are helpful, and empirically verify the effectiveness of the new metrics over real data. The experiments show that the new metrics are more indicative of whether GNNs can lead to better classification accuracy over baseline graph-agnostic models (i.e. MLPs).", "questions": "- For Figure 2, since d_0 = d_1 = 5, how did you obtain the plot at h=0.5? It's fine to apply some smooth interpolation but the middle point is important since it is the peak for LP. Maybe d_0 = d_1 = 10 is a better choice for the base setting.", "limitations": "I could not find where the authors addressed the limitations of this work.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The effect of graph homophily/heterophily to the performance of GNNs is an important topic which has received a lot of interests. This paper provides a more comprehensive perspective to the subject.\n\n- The experiments are carefully designed and reasonably comprehensive. The empirical results provide a good support to the main claims of the paper.\n\n- Overall, the paper is well organized.", "weaknesses": "- I think the overall writing can be improved. I did not feel excited when reading the paper up to and including page 5. This is just my feeling and it does not mean the paper is not good. Moreover, I find myself sometimes lost focus when reading the first 5 pages. Maybe adding 1-2 sentences describing the emphasis of each section at the beginning of the section can be helpful.\n\n- It seems to me that Section 3 and Section 4 study completely different things and under different settings. Although they are related. I think the results of Section 3 and Section 4 can be considered as two separate contributions of the paper. It might be a good idea to make this clear from the beginning. Currently, this gap between the two sections is not clear from neither the abstract nor the introduction.\n\n- There are a few typos in the paper. For example:\n  - Line 18: it significantly -> it is significantly\n  - Line 112, the authors claim that \"the current homophily metrics are all ... feature independent\", however, the generalized edge homophily is feature dependent.\n  - Line 148: inner-class ND -> intra-class ND. Better be consistent since you used intra-class everywhere else.\n  - Most figures involving PBE, e.g. Figure 2a, 3a, have a different naming in the legend than others. Better to have a consistent naming in figure legend.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1: \nI think the overall writing can be improved. I did not feel excited when reading the paper up to and including page 5. This is just my feeling and it does not mean the paper is not good. Moreover, I find myself sometimes lost focus when reading the first 5 pages. Maybe adding 1-2 sentences describing the emphasis of each section at the beginning of the section can be helpful.\n\n### R1: \nThanks for your helpful suggestions. We will modify our paper to make it more reader-friendly.\n\n### Q2: \nIt seems to me that Section 3 and Section 4 study completely different things and under different settings. Although they are related. I think the results of Section 3 and Section 4 can be considered as two separate contributions of the paper. It might be a good idea to make this clear from the beginning. Currently, this gap between the two sections is not clear from neither the abstract nor the introduction.\n\n### R2: \nThanks for your suggestion. This is a very important and implementable feedback. We will elaborate the relation between the contributions of Section 3 and Section 4 in abstract and introduction.\n\nBoth Section 3 and 4 are motivated by the same principle that node distinguishability is related to \"intra-class 'distance v.s. inter- class 'distance'\". Section 3 directly studies this principle with CSBM-H, which is a toy example. Section 4 verifies whether this principle really relates to the performance of GNNs and derives new performance metrics based on it.\n\n### Q3: \nThere are a few typos in the paper.\n\n### R3: \nThanks for carefully going through our paper and point out those typos. We have corrected them in the revised version.\n\n### Q4: \nLine 112, the authors claim that \"the current homophily metrics are all ... feature independent\", however, the generalized edge homophily is feature dependent.\n\n### R4: \nThanks for your suggestion. We will modify it to \"...almost all homophily metrics...\"  in the revised version.\n\n\n### Q5: \nFor Figure 2, since d_0 = d_1 = 5, how did you obtain the plot at h=0.5? It's fine to apply some smooth interpolation but the middle point is important since it is the peak for LP. Maybe d_0 = d_1 = 10 is a better choice for the base setting.\n\n### R5: \nThanks for your suggestion. We relax $hd_0$ and $hd_1$ to be continuous values so that the curves in figures in Section 3.4 are more readable and intuitive, especially to show the intersections of the 3 zones. We will add comments to clarify this point for CSBM-H to avoid unnecessary confusion. We will try $d_0 = d_1 = 10$ setting as you suggest in the revised version."}, {"review_id": "GSxWvDW7WZ", "reviewer": "Reviewer_7wh2", "summary": "This paper addresses the question: when do graph-aware models outperform graph-agnostic ones on node classification tasks? First, theoretical analysis is conducted. Most of the analysis assumes the two-class CSBM-H model – a generalization of the standard stochastic block model, where node features are sampled from normal distributions (with parameters depending on class labels), and parameter $h$ controls the homophily level. Then, Probabilistic Bayes Error and negative generalized Jeffreys divergence are used to quantify node distinguishability for several node representations: the original node features, aggregated node features (one step of random walk-based aggregation), and high-pass filtered features (after one step of the corresponding aggregation). The analysis shows that different representations are beneficial for different homophily regimes.\n\nIn the experiments, it is first shown that if a model has more distinguishable representation, then it usually performs better (Section 4.1). In Section 4.2, it is proposed to predict whether graph-aware models are better than graph-agnostic ones by training a simple classifier on original and aggregated features.", "questions": "The pipeline in Section 4.1 seems overcomplicated. There are two statistical tests, and one is used to define Prop(GCN). It seems that here one can compute the proportion of nodes whose average intra-class node distance is smaller than the inter-class node distance. Would this work or statistical test on this step is necessary?", "limitations": "Limitations are not discussed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The theoretical analysis of PBE and Jeffreys divergence for the CSBM-H and the discussion in Section 3.4 are intuitive and allow one to understand why different aggregation types are helpful for different homophily regimes.", "weaknesses": "- The analysis assumes a particular aggregation (random walk), and it is not clear whether conclusions may change for other aggregations.\n- The paper is limited to heterophilous datasets known to have certain drawbacks [1,2].\n- The proposed measure (Section 4.2) is quite straightforward: it suggests predicting the relative performance of a GNN by training its simplified variant.\n- The paper is hard to follow in several places.\n\nI also have the following comments and questions.\n\n1. On the definition of CSBM-H. According to the definition, $h \\cdot d_0$ and $h \\cdot d_1$ have to be integer. Also, possible values of $d_0$ and $d_1$ depend on the class sizes (the number of outgoing edges should be equal for two classes). This would not be necessary if the graphs are assumed to be directed, but this is not the case according to Section 2.\n\n2. There is another simple measure called Label Informativeness [3] that is known to better agree with GNN performance than homophily [3].\n\n3. The explanation in lines 168-172 was unclear to me; a more detailed explanation would help.\n\nMinor:\n- Definition of $h_k$ in (2): $Z_{v,k}$ does not depend on $u$, so it can be moved to the subscript of the sum.\n- L112: it is written that all homophily measures are feature-independent, but $H_{GE}$ depends on features.\n- Definition 1: notation $P(CL_{Bayes}(x))$ is not clear.\n\nSome typos:\n- L48: “Literatures”\n- L100: inconsistency of singular and plural\n- L111: “imply” → “implying”\n- L120 and below: quotes are typed incorrectly, it should be ``like this'' in latex\n- L149: “the the”\n- L170: “the fixed the classifier”\n\n[1] Lim D. et al. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. NeurIPS 2021.\n\n[2] Platonov O. et al. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? ICLR 2023.\n\n[3] Platonov O. et al. Characterizing graph datasets for node classification: Beyond homophily-heterophily dichotomy. ArXiv:2209.06177, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1: \nThe paper is limited to heterophilous datasets known to have certain drawbacks [1,2].\n\n### R1: \nAlthough our paper studies the effect of heterophily, our analysis and experiments are not limited to heterophilous datasets. In fact, the analysis in Section 3 investigate the impact of graph structures under different homophily levels (from high to low, or $h$ from 1 to 0) comprehensively. For the experimental part in Section 4, the real-world benchmark datasets include both homophilic ($\\textit{Cora, CiteSeer, PubMed}$) and heterophilic ($\\textit{Cornell, Wisconsin, Texas, Film, Chameleon, Squirrel}$) graphs. Additionally in Appendix G.4, we test performance metrics on large-scale benchmark datasets, which also cover both homophilic and heterophilic datasets.\n\n### Q2: \nThe proposed measure (Section 4.2) is quite straightforward: it suggests predicting the relative performance of a GNN by training its simplified variant.\n\n### R2: \nWe would like to clarify and restate the contributions of the proposed metric: 1. As mentioned in Section 4.2, instead of \"training its simplified variant\", we emphasized that the qualified classifier should not require \"training\"; 2. The main contribution of the proposed metric is not only using an 'untrained' classifier, but also leveraging the proposed principle \"intra-class embedding distance is smaller than the inter-class embedding distance\" to construct it. The new metrics based on the above principle can provide accurate statistical threshold value to predict the superiority of G-aware models and is verified to be effective. In addition, we are the first to introduce hypothesis testing to construct performance metric and also the first to show that it is a feasible way besides homophily metrics to derive better metrics. We believe this new direction can help the community to develop metrics with better properties in the future.\n\n### Q3: \nOn the definition of CSBM-H. According to the definition, $hd_0$ and $hd_1$ have to be integer. Also, possible values of $d_0$ and $d_1$ depend on the class sizes (the number of outgoing edges should be equal for two classes). This would not be necessary if the graphs are assumed to be directed, but this is not the case according to Section 2.\n\n### R3: \nIn practice, $hd_0$ and $hd_1$ need to be interger values. \nBut we relax them to be continuous values in figures in Section 3.4 because we want to make the curves more readable and intuitive, especially to show the intersections of the 3 zones. We will add comments to clarify this point for CSBM-H to avoid unnecessary confusion in the revised version.\n\nThanks for bringing up the discussion of the \"possible values of $d_0$ and $d_1$\", here are our thoughts: If we impose undirected assumption in CSBM-H, we have to not only discuss \nthe node degree from intra-class edges, but also discuss degree from inter-class edges (as you said) and control their relations with the corresponding homophily level. This will inevitably add more parameters to CSBM-H and make the model much more complicated. However,\nwe find that this complication does not bring us extra benefit for understanding the effect of homophily, which deviate the main goal of our paper. And we guess this might be one of the reasons that the exisiting work mainly keep the discussion within the directed setting [1]. \n\nActually, when CSMB-H was first designed, we would like to only have one \"free parameter\" $h$ in it to make it simple, because in this way, we are able to show the whole piciture of the effect of homophily from 0 to 1 like the figures in Section 3.4.\n\nAll in all, we find your suggestion interesting. We will add discussion in the revised version and encourage the GNN community to think about more CSMB-H variants with more complicated  assumptions, e.g. with different class homophily, different node local homophily distributions, different node degree and class variance distributions and the undirected assuption as you proposed, etc..\n\n### Q4: \nThe explanation in lines 168-172 was unclear to me; a more detailed explanation would help.\n\n### R4: \nThe decision boundary in [1] is defined as $P= \\\\{ x|w^Tx-w^T(\\mu_0+\\mu_1)/2 \\\\}$ where $w= (\\mu_0-\\mu_1)/||\\mu_0-\\mu_1||$ is a fixed parameter. This classifier only depends on $\\mu_0, \\mu_1$ and is fixed for different homophily levels $h$. However, as $h$ changes, the distributions of the two normal distributions will change and the \"seperability\" of the two normals will be different as well. Thus, the fixed classifier used in [1] is not qualified to quantify the node distinguishability of CSBM-H or any two-normal model with homophily. \nHope this explanation is helpful.\n\n### Q5: \nThe analysis assumes a particular aggregation (random walk), and it is not clear whether conclusions may change for other aggregations.\n\n### R5: \nIn Appendix G.6 (in supplementary material), we report the results for classifier-based performance metrics with symmetric renormalized affinity matrix and compare them with the existing metrics. We observed similar performance advantages as the random walks renormalized matrix.\n\nThe analysis in Section 3.2 and Section 3.3 will be the same. And for the ablation study in 3.4, we re-draw the figures for symmetric renormalized affinity matrix. We observed the similar results for the 3 curves and 3 zones, and thus the conclusions will remain the same. We will add the results and discussion for symmetric renormalized affinity matrix to the revised version.\n\nBesides, as mentioned in line 94-95, random walk aggregation is commenly used in GNN community to study heterophily [1] and we keep consistent with the current literature in our paper.\n\n### Q6: \n... Label Informativeness ...\n\n### R6: \nThanks for point it out. Please see the Author Rebuttal box for the results and comparisons of Label Informativeness and adjusted homophily.\n\n[1] Is Homophily a Necessity for Graph Neural Networks?. In International Conference on Learning Representations."}]

Author rebuttal:
In this part, we will provide experimental results of Label Informativeness (LI) and adjusted homophily ($H_\text{adj}$) on small- and large-scale datasets and compare them with the proposed metrics. Before discussing the results, we would like to introduce 2 threshold values for classifier-based performance metrics (you can find it in Appendix G.2)

Typically, the threshold for homophily and heterophily graphs is set at 0.5. For classifier-based performance metrics, we establish two benchmark thresholds as below,
 • Normal Threshold 0.5 (NT0.5): Although not indicating statistical significance, we are still comfortable to set 0.5 as a loose threshold. A value exceeding 0.5 suggests that the G-aware model is not very likely to underperform their coupled G-agnostic model on the tested graph and vice versa. (Error cases with regard to NT0.5 are marked by grey)
 • Statistical Significant Threshold 0.05 (SST0.05): Instead of offering an ambiguous statistical interpretation, SST0.05 will provide a clear statistical meaning. A value smaller than 0.05 implies that the G-aware model significantly underperforms their coupled G-agnostic model and a value greater than 0.95 suggests a high likelihood of G-aware model outperforming their coupled G-agnostic model. Besides, a value ranging from 0.05 to 0.95 indicates no significant performance distinction between G-aware model and its G-agnostic model. SST0.05 is a more strict threshold than NT0.5. Therefore, we will observe more error cases under SST0.05 than NT0.5. (Error cases with regard to SST0.05 are marked by red)

We can see that, no matter on small- or large-scale datasets, the classifier-based performance metrics (CPMs) are significantly better than the existing metrics on revealing the advantages and disadvantages of GNNs, decreasing the overall error rate from at least 0.34 to 0.13 (at most 0.19 under SST0.05).

Meta-review: The paper studies the question of when graph-aware models outperform the corresponding graph-agnostic (non-GNN) models for node classification (motivated by past work observing that graph-agnostic methods outperform GNNs on certain heterophilic graphs, and a follow-up work discussing that GNNs can still perform well under heterophily). 

Their main insight is that while existing work mainly considers intra-class Node Distinguishability (ND), inter-class ND also has to be jointly considered. To support this idea, they conduct theoretical analysis using the two-class CSBM-H model, a variant of contextual stochastic blockmodels parametrized by the homophily level. They then define metrics (PBE and Jeffreys divergence) to quantify node distinguishability, showing how intra- and inter-class ND relate. They also conduct an empirical study on ND, finding that intra- vs inter-class node distance is well correlated with whether the graph-aware model outperforms graph-agnostic models. 

Reviewer scores are borderline to positive, with 1 negative review. The main strengths raised include the significance of the issue, and insights about intra-class and inter-class ND with good theoretical and empirical support. 

The main weaknesses raised by the review (with score of 3) include concerns about the significance of the results based on the two-Gaussian setting and whether they are too limited / simple, or its relation to separability of Gaussians. The authors responded, e.g. mentioning the effect of graph filters, that the heterophily issue is significant and not well-understood in the GNN community, and how the two-Gaussian setting leads to their insights of the "3 zones" and new metrics. In my view, the paper's analysis indeed captures the effect of graph structure under different homophily levels (using the CSBM model), high/low-pass filters, and studies them using metrics proposed in the paper, providing some insights that are (in my view) not well known in the graph learning community.

Also, the author response helped to satisfactorily address some of the other raised issues, e.g. adding new baselines (Label Informativeness and adjusted homophily). Overall, the reviewers and AC overall find that the paper addresses an important issue, provide novel and interesting insights supported by convincing theoretical and empirical analysis. Hence, I recommend acceptance.

Authors are requested to note the suggested improvements / action items arising from discussion with the reviewers, such as adding the new empirical results and plots to the final manuscript, and other improvements to the paper (e.g. writing issues) arising from reviewer discussion.
Decision: Accept (poster)