When Do Graph Neural Networks Help with Node Classification?
  Investigating the Impact of Homophily Principle on Node Distinguishability
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.
Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao-Wen Chang, Jie Fu, Jure Leskovec, Doina Precup
When Do Graph Neural Networks Help with Node Classification: Investigating the Homophily Principle on Node Distinguishability

###### 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 node-based 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 [34]. However, this argument only considers intra-class Node Distinguishability (ND) and neglects inter-class ND, which provides incomplete understanding of homophily. In this paper, we first demonstrate the aforementioned insufficiency 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, 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, through which we can find how intra- and inter-class ND influence ND together. We visualize the results and give detailed analysis. Through experiments, we verified that the superiority of GNNs is indeed closely related to both intra- and inter-class ND regardless of homophily levels, based on which we propose a new performance metric beyond homophily, which is non-linear and feature-based. Experiments indicate it significantly more effective than the existing homophily metrics on revealing the advantage and disadvantage of GNNs 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 [24; 17; 42; 32; 21], and have been shown to outperform traditional neural networks in tasks such as node classification (**NC**), graph classification, link prediction and graph generation. The success of GNNs is believed to be rooted in the homophily assumption [38], which states that connected nodes tend to have similar attributes [16], providing extra useful information to the aggregated features over the original node features. This relational inductive bias is thought to be a major contributor to the superior performance of GNNs over traditional neural networks in various tasks [4]. 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 [48; 47; 33]. Numerous models have been proposed to address the heterophily challenge lately [40; 48; 47; 33; 5; 28; 7; 46; 19; 30; 27; 43; 31].

Recently, both empirical and theoretical studies indicate that the relationship between homophily and GNN performance is more complicated than "homophily wins, heterophily loses" [34; 31]. For example, the authors in [34] stated that, as long as nodes within the same class share similar neigh
borhood 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 [31] studied homophily/heterophily from post-aggregation node similarity perspective and found that heterophily is not always harmful, which is consistent with [34]. Besides, the authors have proposed to use high-pass filter to address some heterophily cases, which is adopted in [7; 5] as well. They have also proposed aggregation homophily, which is a linear feature-independent performance metric and is verified to be better at revealing the performance advantages and disadvantages of GNNs than the existing homophily metrics [40; 48; 28]. Moreover, [6] has investigated heterophily from a neighbor 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 literatures on studying homophily principle provide the profound insights, they are still deficient: 1. [34; 6] only consider intra-class node distinguishability (**ND**), but ignore inter-class ND; 2. [31] does not show when and how high-pass filter can help with heterophily problem; 3. There is a lack of a non-linear, feature-based performance metric which can leverage richer information to provide an **accurate 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 intra- and inter-class ND together and an ideal case is 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, alongside class variance parameters to control intra-class ND, and node degree parameters which are important [34; 46]; 3. To quantify ND of CSBM-H, we propose Probabilistic Bayes Error (**PBE**) and Negative Generalized Jeffreys Divergence (\(D_{\text{NGJ}}\)), through which we can analytically study how intra- and inter-class ND impact ND together. We visualize PBE and \(D_{\text{NGJ}}\) of original features, low-pass (**LP**) filtered features and high-pass (**HP**) filtered features at different homophily levels, discuss how class variances and node degree will influence ND in details; 4. In practice, we verify 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, we propose Classifier-based Performance Metric (CPM), a new non-linear feature-based metric that can provide statistical threshold. Experiments show that CPM is significantly more effective than the existing homophily metrics on predicting the performance of GNNs versus NNs.

## 2 Preliminaries

We use **bold** font for vectors (_e.g._,\(\mathbf{v}\)) and define an undirected connected graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}\) is the set of nodes with a total of \(N\) elements, \(\mathcal{E}\) is the set of edges without self-loops. \(A\) is the symmetric adjacency matrix with \(A_{i,j}=1\) if there is an edge between nodes \(i\) and \(j\), otherwise \(A_{i,j}=0\). We also define \(D\) as the diagonal degree matrix of the graph, with \(D_{i,i}=d_{i}=\sum_{j}A_{i,j}\). The neighborhood set of a node \(i\), denoted as \(\mathcal{N}_{i}\), is defined as \(\mathcal{N}_{i}=\{j:e_{ij}\in\mathcal{E}\}\). A graph signal is a vector in \(\mathbb{R}^{N}\), whose \(i\)-th entry is a feature of node \(i\). Additionally, we use \(X\in\mathbb{R}^{N\times F}\) to denote the feature matrix, whose columns are graph signals and whose \(i\)-th row \(X_{i,:}=\mathbf{x}_{i}^{T}\) is the feature vector of node \(i\). The label encoding matrix \(Z\in\mathbb{R}^{N\times C}\), where \(C\) is the number of classes, has its \(i\)-th row \(Z_{i,:}\) as the one-hot encoding of the label of node \(i\). We denote \(z_{i}=\operatorname*{arg\,max}_{j}Z_{i,j}\in\{1,2,\ldots C\}\). The indicator function \(\mathbf{1}_{B}\) equals 1 when event \(B\) happens and 0 otherwise.

For nodes \(i,j\in\mathcal{V}\), if \(z_{i}=z_{j}\), then they are considered as _intra-class nodes_; if \(z_{i}\neq z_{j}\), then they are considered to be _inter-class nodes_. Similarly, an edge \(e_{i,j}\in\mathcal{E}\) is considered to be an _intra-class edge_ if \(z_{i}=z_{j}\), and an _inter-class edge_ if \(z_{i}\neq z_{j}\).

### 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 [24], SGC-1 [45]; A network that does not use graph structure is called graph-agnostic (**G-agnostic**) model, such as Multi-Layer Perceptron with 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, _e.g.,_ GCN is coupled with MLP-2 and SGC is coupled with MLP-1 as shown below,

\[\text{GCN: }Y=\text{softmax}(\hat{A}_{\text{sym}}\text{ ReLU}(\hat{A}_{\text{sym}}XW_{0})\ W_{1}),\ \ \text{MLP-2: }Y=\text{softmax}(\text{ReLU}(XW_{0})\ W_{1}), \tag{1}\] \[\text{SGC-1: }Y=\text{softmax}(\hat{A}_{\text{sym}}XW_{0}),\ \ \text{MLP-1: }Y=\text{softmax}(XW_{0}),\]
where \(\hat{A}_{\text{sym}}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\), \(\tilde{A}\equiv A+I\) and \(\tilde{D}\equiv D+I\); \(W_{0}\in\mathbb{R}^{F_{0}\times F_{1}}\) and \(W_{1}\in\mathbb{R}^{F_{1}\times O}\) are learnable parameter matrices. For simplicity, we denote \(y_{i}=\operatorname*{arg\,max}_{j}Y_{i,j}\in\{1,2,\ldots C\}\). The random walk renormalized matrix \(\hat{A}_{\text{rw}}=\tilde{D}^{-1}\tilde{A}\) can also be applied to GCN, which is essentially a mean aggregator commonly used in some spatial-based GNNs [17]. To bridge spectral and spatial methods, we use \(\hat{A}_{\text{rw}}\) in the theoretical analysis, but **self-loops are not added to the adjacency matrix** to maintain consistency with previous literature [34; 31].

To address the heterophily challenge, high-pass (HP) filter [13], such as \(I-\hat{A}_{\text{rw}}\), is often used to replace low-pass (LP) filter [35]\(\hat{A}_{\text{rw}}\) in GCN [5; 7; 31]. In this paper, we use \(\tilde{A}_{\text{rw}}\) and \(I-\hat{A}_{\text{rw}}\) as the LP and HP operators, respectively. The LP and HP filtered feature matrices are represented as \(H=\hat{A}_{\text{rw}}X\) and \(H^{\text{HP}}=(I-\hat{A}_{\text{rw}})X\). For simplicity, we denote \(\mathbf{h}_{i}=(H_{i,:})^{T},\mathbf{h}_{i}^{\text{HP}}=(H_{i,:}^{\text{HP}})^{T}\).

**To measure if the G-aware models can outperform its coupled G-agnostic model without training**, a lot of homophily metrics have been proposed and we will introduce the most commonly used ones in the following subsection.

### Homophily Metrics

The homophily metric is a way to describe the relation between node labels and graph structure. We introduce five commonly used homophily metrics: edge homophily [1; 48], node homophily [40], class homophily [28], generalized edge homophily [23] and aggregation homophily [31] as follows:

\[\text{H}_{\text{edge}}(\mathcal{G})=\frac{\big{|}\{\epsilon_{uv}| \epsilon_{uv}\in\mathcal{E},Z_{u},:=Z_{v,:}\}\big{|}}{|\mathcal{E}|},\text{H}_ {\text{node}}(\mathcal{G})=\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}\text {H}_{\text{node}}^{v}=\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}\frac{ \big{|}\{\{u|u\in\mathcal{N}_{v},Z_{u},:=Z_{v,:}\}\big{|}\}}{d_{v}},\\ \text{H}_{\text{class}}(\mathcal{G})\!=\!\frac{1}{C\!-\!1}\sum_{k=1}^{C} \bigg{[}h_{k}\!-\!\frac{\big{|}\{i\!+\!2_{v,:}\neq\!1\}}{N}\bigg{]}_{+},\text { where }h_{k}\!=\!\frac{\sum_{v\in\mathcal{V}}\{u\!+\!2_{v,:}\neq\!1,u\in\mathcal{N}_{v },Z_{u},:=Z_{v,:}\}\big{|}}{\sum_{v\in\{v|x_{v,k}=1\}}d_{v}},\\ \text{H}_{\text{def}}(\mathcal{G})=\frac{\sum\limits_{(i,j)\in \mathcal{E}}\cos(\mathbf{x},\mathbf{x}_{i})}{|\mathcal{E}|},\,\text{H}_{\text{agg}}( \mathcal{G})=\frac{1}{|\mathcal{V}|}\times\Big{|}\{\{v\,|\operatorname{Mean} _{u}\big{(}\{S(\hat{A},Z)_{v,u}^{Z_{u},:=Z_{v,:}\}\}\big{)}\geq\operatorname{ Mean}_{u}\big{(}\{S(\hat{A},Z)_{v,u}^{Z_{u},:=Z_{v,:}\}\}\big{)}\}\Big{|}} \tag{2}\]

where \(\text{H}_{\text{node}}^{v}\) is the local homophily value for node \(v\); \([a]_{+}=\max(0,a)\); \(h_{k}\) is the class-wise homophily metric [28]; \(\operatorname{Mean}_{u}\big{(}\{\cdot\}\big{)}\) takes the average over \(u\) of a ghost multiset of values or variables and \(S(\hat{A},Z)=\hat{A}Z(\hat{A}Z)^{T}\) is the post-aggregation node similarity matrix.

These metrics all fall within the range of \([0,1]\), with a value closer to \(1\) indicating strong homophily and imply that G-aware models are more likely to outperform its coupled G-agnostic model, and vice versa. However, the current homophily metrics are all linear, feature-independent metrics which fail to give an accurate indication of the superiority of G-aware models and cannot provide a threshold value [31] for the superiority.

## 3 Analysis of Homophily on Node Distinguishability (ND)

### Motivation

The Problem in Current LiteratureRecent 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" [34; 6]. For example, in Figure 1, nodes {1,2} are from class blue and both have the same heterophilic neighborhood patterns. As a result, their aggregated features will still be similar and they can be classified into the same class.

However, this is only partially true for ND if we forget to discuss inter-class ND, _e.g.,_ node 3 in Figure 1 are from class green and also has the same neighborhood pattern 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 4.

Figure 1: Example of intra- and inter-class node distinguishability.
### CSBM-H and Optimal Bayes Classifier

In order to have more control over the assumptions made about the node embeddings, we consider the Contextual Stochastic Block Model (CSBM) [11]. It is 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 [41, 3, 44]. To investigate the impact of homophily on ND, the authors in [34] simplify CSBM to the two-normal setting, where the node features \(X\) and 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 variances 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/Heterophily (CSBM-H), which is a variation of CSBM that incorporates an explicit homophily parameter \(h\) for the two-normal setting and also has class variance parameters \(\sigma_{0}^{2},\sigma_{1}^{2}\) to describe the inner-class ND. We then derive the the optimal Bayes classifier (\(\text{CL}_{\text{Bayes}}\)) and negative generalized Jeffreys divergence for CSBM-H, based on which we can quantify ND for CSBM-H.

**CSBM-H(\(\mathbf{\mu}_{0},\mathbf{\mu}_{1},\sigma_{0}^{2}I,\sigma_{1}^{2}I,d_{0},d_{1},h\))** The generated graph consists of two disjoint sets of nodes, \(i\in\mathcal{C}_{0}\) and \(j\in\mathcal{C}_{1}\), corresponding to the two classes. The features of each node are generated independently, with \(\mathbf{x}_{i}\) generated from \(N(\mathbf{\mu}_{0},\sigma_{0}^{2}I)\) and \(\mathbf{x}_{j}\) generated from \(N(\mathbf{\mu}_{1},\sigma_{1}^{2}I)\), where \(\mathbf{\mu}_{0},\mathbf{\mu}_{1}\in\mathbb{R}^{F_{h}}\) and \(F_{h}\) is the dimension of the embeddings. The degrees of nodes in \(\mathcal{C}_{0}\) and \(\mathcal{C}_{1}\) are \(d_{0},d_{1}\in\mathbb{N}\) respectively. For \(i\in\mathcal{C}_{0}\), its neighbors are generated by independently sampling from \(h\cdot d_{0}\) intra-class nodes and \((1-h)\cdot d_{0}\) inter-class nodes. The neighbors of \(j\in\mathcal{C}_{1}\) are generated in the same way. As a result, the FP, LP and HP filtered features are generated as follows,

\[\begin{split}& i\in\mathcal{C}_{0}:\mathbf{x}_{i}\sim N(\mathbf{\mu}_{0}, \sigma_{0}^{2}I);\ \mathbf{h}_{i}\sim N(\tilde{\mathbf{\mu}}_{0},\tilde{\sigma}_{0}^{2}I),\ \mathbf{h}_{i}^{\text{HP}}\sim N\left(\tilde{\mathbf{\mu}}_{0}^{ \text{HP}},(\tilde{\sigma}_{0}^{\text{HP}})^{2}I\right),\\ & j\in\mathcal{C}_{1}:\mathbf{x}_{j}\sim N(\mathbf{\mu}_{1},\sigma_{1}^{2 }I);\ \mathbf{h}_{j}\sim N(\tilde{\mathbf{\mu}}_{1},\tilde{\sigma}_{1}^{2}I),\ \mathbf{h}_{j}^{ \text{HP}}\sim N\left(\tilde{\mathbf{\mu}}_{1}^{\text{HP}},(\tilde{\sigma}_{1}^{ \text{HP}})^{2}I\right),\end{split} \tag{3}\]

where \(\tilde{\mathbf{\mu}}_{0}=h(\mathbf{\mu}_{0}-\mathbf{\mu}_{1})+\mathbf{\mu}_{1}\), \(\tilde{\mathbf{\mu}}_{1}=h(\mathbf{\mu}_{1}-\mathbf{\mu}_{0})+\mathbf{\mu}_{0}\), \(\tilde{\mathbf{\mu}}_{0}^{\text{HP}}=(1-h)(\mathbf{\mu}_{0}-\mathbf{\mu}_{1})\), \(\tilde{\mathbf{\mu}}_{1}^{\text{HP}}=(1-h)(\mathbf{\mu}_{1}-\mathbf{\mu}_{0})\), \(\tilde{\mathbf{\sigma}}_{0}^{2}=\frac{(h(\sigma_{0}^{2}-\sigma_{0}^{2})+\sigma_{1} ^{2})}{d_{0}}\), \(\tilde{\sigma}_{1}^{2}=\frac{(h(\sigma_{0}^{2}-\sigma_{0}^{2})+\sigma_{0}^{2} )}{d_{1}}\), \((\tilde{\sigma}_{0}^{\text{HP}})^{2}=\sigma_{0}^{2}+\frac{(h(\sigma_{0}^{2}- \sigma_{1}^{2})+\sigma_{1}^{2})}{d_{0}}\), \((\tilde{\sigma}_{1}^{\text{HP}})^{2}=\sigma_{1}^{2}+\frac{(h(\sigma_{1}^{2}- \sigma_{0}^{2})+\sigma_{0}^{2})}{d_{1}}\). If \(\sigma_{0}^{2}<\sigma_{1}^{2}\), we refer to \(\mathcal{C}_{0}\) as the low variation class and \(\mathcal{C}_{1}\) as the high variation class. The variance of each class can reflect the intra-class ND. We abuse the notation \(\mathbf{x}_{i}\in\mathcal{C}_{0}\) for \(i\in\mathcal{C}_{0}\) and \(\mathbf{x}_{j}\in\mathcal{C}_{1}\) for \(j\in\mathcal{C}_{1}\).

To quantify the ND of CSBM-H, we first compute the optimal Bayes classifier in the following theorem. The theorem is about \(\mathbf{x}\), but the results are applicable to \(\mathbf{h}\) and \(\mathbf{h}^{\text{HP}}\) when the parameters are replaced according to Equation 3.

**Theorem 1**.: Suppose \(\sigma_{0}^{2}\neq\sigma_{1}^{2}\) and \(\sigma_{0}^{2},\sigma_{1}^{2}>0\), the prior distribution for \(\mathbf{x}_{i}\) is \(\mathbb{P}(\mathbf{x}_{i}\in\mathcal{C}_{0})=\mathbb{P}(\mathbf{x}_{i}\in\mathcal{C}_{1 })=1/2\), then the optimal Bayes Classifier (\(\text{CL}_{\text{Bayes}}\)) for CSBM-H (\(\mathbf{\mu}_{0},\mathbf{\mu}_{1},\sigma_{0}^{2}I,\sigma_{1}^{2}I,d_{0},d_{1},h\)) is1

Footnote 1: The Bayes classifier for multiple categories (\(>2\)) can be computed by stacking multiple expectation terms using similar methods as in [12, 14]. We do not discuss the more complicated settings in this paper.

\[\text{CL}_{\text{Bayes}}(\mathbf{x}_{i})=\begin{cases}1,\ \eta(\mathbf{x}_{i})\geq 0.5\\ 0,\ \eta(\mathbf{x}_{i})<0.5\end{cases},\ \ \text{and}\ \ \eta(\mathbf{x}_{i})=\mathbb{P}(z_{i}=1|\mathbf{x}_{i})=\frac{1}{1+\exp \left(Q(\mathbf{x}_{i})\right)},\]

where \(Q(\mathbf{x}_{i})=a\mathbf{x}_{i}^{T}\mathbf{x}_{i}+\mathbf{b}^{T}\mathbf{x}_{i}+c\), \(a=\frac{1}{2}\left(\frac{1}{\sigma_{1}^{2}}-\frac{1}{\sigma_{0}^{2}}\right),\bm {b}=\frac{\mathbf{\mu}_{0}}{\sigma_{0}^{2}}-\frac{\mathbf{\mu}_{1}}{\sigma_{1}^{2}},c= \frac{\mu_{1}^{T}\mathbf{\mu}_{1}}{2\sigma_{1}^{2}}-\frac{\mu_{2}^{T}\mathbf{\mu}_{0}}{2 \sigma_{0}^{2}}+\ln\left(\frac{\sigma_{1}^{F_{h}}}{\sigma_{0}^{F_{h}}}\right)\).

Proof.: See Appendix A. 

**Advantages of \(\text{CL}_{\text{Bayes}}\) Over the Fixed Linear Classifier in [34]** The classifier proposed in [34] is fixed and depends only on the two centers \(\mathbf{\mu}_{0},\mathbf{\mu}_{1}\). The data centers will shift as \(h\) changes. However, the fixed the classifier cannot capture such distribution movement and thus, is not qualified to measure ND for different \(h\). Besides, we cannot investigate how variances \(\sigma_{0}^{2}\) and \(\sigma_{1}^{2}\) and node degrees \(d_{0}\) and \(d_{1}\) affect ND with the fixed classifier in [34].

In the following subsection, we will define two methods to quantify ND of CSBM-H, one is based on \(\text{CL}_{\text{Bayes}}\), which is a 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 also be used together to analyze ND.
### Measure Node Distinguishability of CSBM-H

The Bayes error rate (BE) is the probability of a node being mis-classified when the true class probabilities given the predictors are known [18]. It can be used to measure the distinguishability of node embeddings and the BE for \(\text{CL}_{\text{Bayes}}\) is defined as follows,

**Definition 1** (Bayes Error Rate).: _The Bayes error rate [18] for \(\text{CL}_{\text{Bayes}}\) is defined as_

\[\text{BE}=\mathbb{E}_{\mathbf{x}}[\mathbb{P}(z|\text{CL}_{\text{Bayes}}(\mathbf{x}) \neq z)]=\mathbb{E}_{\mathbf{x}}[1-\mathbb{P}(\text{CL}_{\text{Bayes}}(\mathbf{x}))].\]

Specifically, the BE for CSBM-H can be written as

\[\text{BE}=\mathbb{P}\left(\mathbf{x}\in\mathcal{C}_{0}\right)(1-\mathbb{P}(\text{ CL}_{\text{Bayes}}(\mathbf{x})=0|\mathbf{x}\in\mathcal{C}_{0}))+\mathbb{P}(\mathbf{x}\in \mathcal{C}_{1})\left(1-\mathbb{P}(\text{CL}_{\text{Bayes}}(\mathbf{x})=1|\mathbf{x} \in\mathcal{C}_{1})\right). \tag{4}\]

In order to estimate the above value, we define Probabilistic Bayes Error (PBE).

**Probabilistic Bayes Error (PBE)** The random variable in each dimension of \(\mathbf{x}_{i}\) is independently normally distributed. As a result, \(Q(\mathbf{x}_{i})\) defined in Theorem 1 follows a generalized \(\chi^{2}\) distribution [9, 10](See the calculation in Appendix D). Specifically,

\[\text{For }\mathbf{x}_{i}\in\mathcal{C}_{0},\ Q(\mathbf{x}_{i})\sim\tilde{\chi}^{2}(w_{0},F_{h},\lambda_{0})+\xi;\ \mathbf{x}_{j}\in\mathcal{C}_{1},\ Q(\mathbf{x}_{j})\sim\tilde{\chi}^{2}(w_{1},F_{h}, \lambda_{1})+\xi,\]

where \(w_{0}=a\sigma_{0}^{2},w_{1}=a\sigma_{1}^{2}\), the degree of freedom is \(F_{h}\), \(\lambda_{0}=(\frac{\mathbf{\mu}_{0}}{\sigma_{0}}+\frac{\mathbf{b}}{2a\sigma_{0}})^{T} (\frac{\mathbf{\mu}_{0}}{\sigma_{0}}+\frac{\mathbf{b}}{2a\sigma_{0}}),\ \lambda_{1}=(\frac{\mathbf{\mu}_{1}}{\sigma_{1}}+\frac{\mathbf{b}}{2a\sigma_{1}})^{T} (\frac{\mathbf{\mu}_{1}}{\sigma_{1}}+\frac{\mathbf{b}}{2a\sigma_{1}})\)  and \(\xi=c-\frac{\mathbf{b}^{T}\mathbf{b}}{4a}\). Then, by using the Cumulative Distribution Function (CDF) of \(\tilde{\chi}^{2}\), we can calculate the predicted probabilities directly as,

\[\mathbb{P}(\text{CL}_{\text{Bayes}}(\mathbf{x})=0|\mathbf{x}\in\mathcal{C}_{0})=1- \text{CDF}_{\tilde{\chi}^{2}(w_{0},F_{h},\lambda_{0})}(-\xi),\ \mathbb{P}(\text{CL}_{\text{Bayes}}(\mathbf{x})=1|\mathbf{x}\in \mathcal{C}_{1})=\text{CDF}_{\tilde{\chi}^{2}(w_{1},F_{h},\lambda_{1})}(-\xi).\]

Suppose we have a balanced prior distribution \(\mathbb{P}(\mathbf{x}\in\mathcal{C}_{0})=\mathbb{P}(\mathbf{x}\in\mathcal{C}_{1})=1/2\). Then, the PBE is computed as,

\[\frac{\text{CDF}_{\tilde{\chi}^{2}(w_{0},F_{h},\lambda_{0})}(-\xi)+\left(1- \text{CDF}_{\tilde{\chi}^{2}(w_{1},F_{h},\lambda_{1})}(-\xi)\right)}{2}\]

To investigate the impact of homophily on the ND of LP filtered and HP filtered embeddings, we just need to replace \(\left(\mathbf{\mu}_{0},\sigma_{0}^{2},\mathbf{\mu}_{1},\sigma_{1}^{2}\right)\) with \(\left(\tilde{\mathbf{\mu}}_{0},\tilde{\sigma}_{0}^{2},\tilde{\mathbf{\mu}}_{1},\tilde{ \sigma}_{1}^{2}\right)\) and \(\left(\tilde{\mathbf{\mu}}_{0}^{\text{HP}},(\tilde{\sigma}_{0}^{\text{HP}})^{2}, \tilde{\mathbf{\mu}}_{1}^{\text{HP}},(\tilde{\sigma}_{1}^{\text{HP}})^{2}\right)\) as equation 3. PBE can be numerically calculated and visualized to show the relation between \(h\) and ND precisely. However, we do not have an analytic expression for PBE, which makes it 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 a statistical measure of how a probability distribution \(P\) is different from another distribution \(Q\)[8]. It offers us a tool to define an explainable ND measure, generalized Jeffreys divergence, as follows.

**Definition 2** (Generalized Jeffreys Divergence).: _For a random variable \(\mathbf{x}\) which has either the distribution \(P(\mathbf{x})\) or the distribution \(Q(\mathbf{x})\), the generalized Jeffreys divergence 2 is defined as_

Footnote 2: Jeffreys divergence [22] is defined as \(D_{\text{KL}}(P||Q)+D_{\text{KL}}(Q||P)\)

\[D_{\text{GJ}}(P,Q)=\mathbb{P}(\mathbf{x}\sim P)\mathbb{E}_{\mathbf{x}\sim P}\left[ \ln\frac{P(\mathbf{x})}{Q(\mathbf{x})}\right]+\mathbb{P}(\mathbf{x}\sim Q)\mathbb{E}_{\bm {x}\sim Q}\left[\ln\frac{Q(\mathbf{x})}{P(\mathbf{x})}\right]\]

With \(\mathbb{P}(\mathbf{x}\sim P)=\mathbb{P}(\mathbf{x}\sim Q)=1/2\), the negative generalized Jeffreys divergence for the two-normal setting in CSBM-H can be computed by (See Appendix C for the calculation)

\[D_{\text{NGJ}}(\text{CSBM-H})=\ \ \begin{subarray}{c}-d_{X}^{2}(\frac{1}{4\sigma_{1}^{2}}+ \frac{1}{4\sigma_{0}^{2}})\\ \text{Negative Normalized Distance}\end{subarray}\underbrace{-\frac{F_{h}}{4}(\rho^{2}+ \frac{1}{\rho^{2}}-2)}_{\text{Negative Variance Ratio}}\end{subarray} \tag{5}\]

where \(d_{X}^{2}=(\mathbf{\mu}_{0}-\mathbf{\mu}_{1})^{T}(\mathbf{\mu}_{0}-\mathbf{\mu}_{1}),\rho= \frac{\sigma_{0}}{\sigma_{1}}\) is the squared Euclidean distance between centers and since we assume \(\sigma_{0}^{2}<\sigma_{1}^{2}\), we have \(0<\rho<1\). For \(\mathbf{h}\) and \(\mathbf{h}^{\text{HP}}\), we have \(d_{H}^{2}=(2h-1)^{2}d_{X}^{2},d_{\text{HP}}^{2}=4(1-h)^{2}d_{X}^{2}\). The smaller \(D_{\text{NGJ}}\) a CSBM-H has, the more distinguishable the node embeddings are.

\(D_{\text{NGJ}}\) relies on two terms, Expected Negative Normalized Distance (ENND) and the Negative Variance Ratio (NVR): 1. ENND depends on how large is the inter-class ND \(d_{X}^{2}\) compared with the normalization term \(\frac{1}{4\sigma_{1}^{2}}+\frac{1}{4\sigma_{0}^{2}}\), which is determined by intra-class ND (variances \(\sigma_{0},\sigma_{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 (\(\rho\) is close to 0), NVR is small which means the nodes are more distinguishable and vice versa.

Now, we can investigate the impact of homophily on ND through the lens of PBE and \(D_{\text{NGJ}}\). Specifically, in the standard CSBM-H setting as shown in Figure 2 with \(\mathbf{\mu}_{0}=[-1,0],\mathbf{\mu}_{1}=[0,1],\sigma_{0}^{2}=1,\sigma_{1}^{2}=2,d_{0}= 5,d_{1}=5\), the PBE and \(D_{\text{NGJ}}\) curves for LP filtered feature \(\mathbf{h}\) are bell-shaped 3, indicating that when the homophily value is extremely low or high, the aggregated node embeddings become more distinguishable than at medium levels of homophily. The PBE and \(D_{\text{NGJ}}\) curves for \(\mathbf{h}^{\text{HP}}\) are monotonically increasing, which means that the high-pass filter works better in heterophily areas than in homophily areas. Moreover, it is observed that \(\mathbf{x}\), \(\mathbf{h}\), and \(\mathbf{h}^{\text{HP}}\) will get the lowest PBE and \(D_{\text{NGJ}}\) in different homophily intervals, which we refer to as the "FP zone _(black)_", "LP zone _(green)_", and "HP zone _(red)_". 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 4, the original (_i.e.,_ full-pass or FP filtered) features works betters at medium to high homophily area.

Footnote 3: This is consistent with the empirical results found in [31] that the relation between GNN performance and homophily value is a U-shaped curve.

Footnote 4: This verifies the conjecture made in [31] saying that high-pass filter cannot address all kinds of heterophily and only works well for certain heterophily cases.

Researchers have always been interested in exploring how node degree relate to the effect of homophily [34, 46]. 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 zones.

### Ablation Study on CSBM-H

**Increase the Variance of High-variation Class (\(\sigma_{0}^{2}=1,\sigma_{1}^{2}=5\))**  From Figure 3, it is observed that as the variance in \(\mathcal{C}_{1}\) increases and the variance between \(\mathcal{C}_{0}\) and \(\mathcal{C}_{1}\) becomes more imbalanced, the PBE and \(D_{\text{NGJ}}\) of the three curves all go up which means the node embeddings become less distinguishable under HP, LP and FP filters. The significant shrinkage of the HP zones and the expansion of the \(X\) zone indicates that the original features are more robust to imbalanced variances especially in the low heterophily area, which can be reflected by the NVR in Figure 3 (d).

**Increase the Variance of Low-variation Class (\(\sigma_{0}^{2}=1.9,\sigma_{1}^{2}=2\))**  As shown in Figure 9 in Appendix F, when the variance in \(\mathcal{C}_{0}\) increases and the variance between \(\mathcal{C}_{0}\) and \(\mathcal{C}_{1}\) becomes more balanced, PBE and \(D_{\text{NGJ}}\) curves go up which means the node embeddings become less distinguishable. The LP, HP and the FP zones almost stays the same because the magnitude of NVR becomes too small that it almost has no effect to ND as shown in Figure 9 (d).

Interestingly, we found the change of variances cause little differences of the 3 zones in ENND and the movement of 3 zones mainly comes from NVR 5 and HP filter is less sensitive to \(\rho\) changes in low homophily area. This insensitivity will have significant impact to the 3 zones when \(\rho\) is close to \(0\) and have trivial effect when \(\rho\) is close to \(1\) because the magnitude of NVR is too small.

Figure 3: Comparison of CSBM-H with \(\sigma_{0}^{2}=1,\sigma_{1}^{2}=5\).
**Increase the Node Degree of High-variation Class (\(d_{0}=5,d_{1}=25\))** From Figure 4, it can be observed that as the node degree of the high-variation class increases, the PBE and \(D_{\text{NGJ}}\) 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 zone and shrinkage of FP and HP zone. This is mainly due to 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 (\(d_{0}=25,d_{1}=5\))** From Figure 5, we have the similar observation as when we increase the node degree of high-variation class. The difference is that the expansion of LP zone and shrinkage of FP and HP zones are not as significant as before.

From \(\tilde{\sigma}_{0}^{2},~{}\tilde{\sigma}_{1}^{2}\) we can see that increasing node degree can help LP filter reduce variances of the features so that the ENND will decrease, especially for high-variation class while HP filter is less sensitive to the change of variances and node degree.

### More General Theoretical Analysis

In this subsection, we aim to gain a deeper understanding of how LP and HP affect ND in a broader context beyond the two-normal settings. To be consistent with previous literature, we follow the assumptions outlined in [34], which are: 1. The features of node \(i\) are sampled from distribution \(\mathcal{F}_{z_{i}}\), _i.e._, \(\mathbf{x}_{i}\sim\mathcal{F}_{z_{i}}\), with mean \(\mathbf{\mu}_{z_{i}}\in\mathbb{R}^{F_{h}}\); 2. Dimensions of \(\mathbf{x}_{i}\) are independent to each other; 3. Each dimension in feature \(\mathbf{x}_{i}\) is bounded, _i.e._, \(a\leq\mathbf{x}_{i,k}\leq b\); 4. For node \(i\), the labels of its neighbors are independently sampled from neighborhood distribution \(\mathcal{D}_{z_{i}}\) and repeated for \(d_{i}\) times. We refer to a graph that follows the above assumptions as \(\mathcal{G}=\left\{\mathcal{V},\mathcal{E},\left\{\mathcal{F}_{c},c\in \mathcal{C}\right\},\left\{\mathcal{D}_{c},c\in\mathcal{C}\right\}\right\}, \mathcal{C}=\left\{1,\ldots,C\right\}\) and \((b-a)^{2}\) reflects how variation the features are. The authors in [34] analyze the distance between the aggregated node embedding and its expectation, _i.e._, \(\left\|\mathbf{h}_{i}-\mathbb{E}(\mathbf{h}_{i})\right\|_{2}\), 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 a graph \(\mathcal{G}=\left\{\mathcal{V},\mathcal{E},\left\{\mathcal{F}_{c},c\in \mathcal{C}\right\},\left\{\mathcal{D}_{c},c\in\mathcal{C}\right\}\right\}\) meets all the above assumptions (1-4). For node \(i,j,v\in\mathcal{V}\), suppose \(z_{i}\neq z_{j}\) and \(z_{i}=z_{v}\), then for constants \(t_{x},t_{h},t_{\text{HP}}\) that satisfy \(t_{x}\geq\sqrt{F_{h}D_{x}}(i,j),~{}t_{h}\geq\sqrt{F_{h}}D_{h}(i,j),~{}t_{ \text{HP}}\geq\sqrt{F_{h}}D_{\text{HP}}(i,j)\) we have

\[\mathbb{P}\left(\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|_{2}\geq\left\|\mathbf{x}_{i}- \mathbf{x}_{v}\right\|_{2}+t_{x}\right)\leq 2F_{h}\exp\left(-\frac{(D_{x}(v,j)- \frac{t_{x}}{\sqrt{F_{h}}})^{2}}{V_{x}(v,j)}\right),\]

\[\mathbb{P}(\left\|\mathbf{h}_{i}-\mathbf{h}_{j}\right\|_{2}\geq\left\|\mathbf{h}_{i}-\mathbf{ h}_{v}\right\|_{2}+t_{h})\leq 2F_{h}\exp\left(-\frac{(D_{h}(v,j)-\frac{t_{h}}{ \sqrt{F_{h}}})^{2}}{V_{h}(v,j)}\right), \tag{6}\]

Figure 4: Comparison of CSBM with different \(d_{0}=5,d_{1}=25\) setups.

Figure 5: Comparison of CSBM with different \(d_{0}=25,d_{1}=5\) setups.
where \(D_{x}(v,j)=\left\|\mathbf{\mu}_{x_{v}}-\mathbf{\mu}_{z_{v}}\right\|_{2},\ V_{x}(v,j)=(b-a)^{ 2},\ D_{h}(v,j)=\left\|\mathbf{\hat{\mu}}_{x_{v}}-\mathbf{\hat{\mu}}_{z_{v}}\right\|_{2},V_{x}(v,j)=\left(\frac{1}{2d_{v}}+\frac{1}{2d_{v}}\right)(b-a)^{2},\)

\[D_{\text{HP}}(v,j)=\left\|\mathbf{\mu}_{x_{v}}-\mathbf{\hat{\mu}}_{x_{v}}-\left(\mathbf{ \mu}_{x_{j}}-\mathbf{\hat{\mu}}_{z_{v}}\right)\right\|_{2},\ V_{\text{HP}}(v,j)= \left(1+\frac{1}{2d_{v}}+\frac{1}{2d_{v}}\right)(b-a)^{2},\ \mathbf{\hat{\mu}}_{x_{v}}=\sum_{u\in\mathcal{N}(v)}\mathbb{E}_{x_{v} \sim\mathcal{D}_{x_{v}}^{\sim}}\left[\frac{1}{d_{v}}\mathbf{x}_{u}\right].\]

Proof.: See Appendix B. 

We can see that, the probability upper bound mainly depends on a 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 an additional 1 in the constant term. Moreover, we show that the distance term of HP filter actually depends on the **relative center distance** which is a novel discovery. As shown in Figure 6, 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 a more general setting with weaker assumptions, we can see that ND is also described by the intra- and inter-class ND terms rather than intra-class ND only, which is consistent with CSBM-H.

## 4 Empirical Study of Node Distinguishability

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 a strong relation can be verified, then it indicates that we can design new ND-based performance metrics, beyond homophily metrics, to evaluate the superiority and inferiority of G-aware models against its coupled G-agnostic models without training which saves time and computational costs.

### Tests on Real-world Datasets

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

Footnote 6: [29] also conduct hypothesis testing to find out when to use GNNs for node classification, but they test the differences between connected nodes and unconnected nodes instead of intra- and inter-class nodes.

**Experimental Setup** We first train two G-aware models GCN, SGC-1 and their coupled G-agnostic models MLP-2 and MLP-1 with fine-tuned hyperparameters provided by [31]. 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 7_e.g.,_ we obtain Prop(GCN) for GCN. We use Prop to quantify ND and we

\begin{table}
\begin{tabular}{c|c|c c c c c c c c c} \hline \hline  & & Cornell & Wisconsin & Texas & Film & Chandown & Squier & Corn & Citeseer & PubMed \\ \hline \multirow{3}{*}{Baseline} & H\({}_{\text{tr
train the models multiple times for samples to conduct the following hypothesis tests:

\[\text{H}_{0}:\text{Prop}(\text{G-aware model})=\text{Prop}(\text{G-agnostic model});\ \text{H}_{1}:\text{Prop}(\text{G-aware model})<\text{Prop}(\text{G-agnostic model})\]

Specifically, we compare GCN v.s. MLP-2 and SGC-1 v.s. 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/test sets with a ratio of 60%/20%/20%. With 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 1 (See more experimental tests on state-of-the-art model in Appendix G).

It is observed that, in most cases (except for GCN v.s. MLP-2 on _PubMedMed_), when \(\text{H}_{1}\) 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 v.s. inter-class node embedding distances", no matter the homophily levels. It 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\leq 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.

### Beyond Homophily: Classifier-based Performance Metrics

A qualified classifier should not require iterative training. In this paper, we choose Gaussian Naive Bayes (GNB)[18] and Kernel Regression (KR) with Neural Network Gaussian Process (NNGP) [26; 2; 15; 37] to capture the **feature-based linear or non-linear** information.

To get the p-value, we first randomly sample 500 nodes from \(\mathcal{V}\) and splits them into 60%/40% as 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. We repeat this process for 100 times to get 100 samples of prediction accuracy for \(X\) and \(H\). Then, for the given classifier, we compute the p-value of the following hypothesis testing,

\[\text{H}_{0}:\text{Acc}(\text{Classifier}(H))=\text{Acc}(\text{Classifier}(X ));\ \text{H}_{1}:\text{Acc}(\text{Classifier}(H))<\text{Acc}(\text{Classifier}(X )).\]

The p-values can provide a statistical threshold value, such as 0.05, to indicate whether the \(H\) is significantly better than \(X\) for node classification. As seen in Table 1, KR and GNB based metrics significantly outperform the existing homophily metrics, reducing the errors from at least \(5\) down to just \(1\) out of 18 cases. Besides, we only need a small set of the labels to calculate the p-value, which makes it better for sparse label scenario. Table 2 summarizes its advantages over the existing metrics. (See Appendix G for more details on classifier-based performance metrics, experiments on synthetic datasets, more detailed comparisons on small-scale and large-scale datasets, results for symmetric renormalized affinity matrix and running time.)

## 5 Conclusions

In this paper, we provide a complete understanding of homophily by studying intra- and inter-class ND together. To theoretically investigate ND, we study the PBE and \(D_{\text{NGJ}}\) of the proposed CSBM-H and analyze how class variances and node degree will influence the PBE and \(D_{\text{NGJ}}\) curves and 3 zones of the original, LP and HP filtered features. 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 a non-linear feature-based metric and can provide statistical threshold value.

\begin{table}
\begin{tabular}{l|c c c c} \hline \hline \begin{tabular}{c} Performance \\ Metrics \\ \end{tabular} & \begin{tabular}{c} Linear or \\ Non-linear \\ \end{tabular} & \begin{tabular}{c} Feature \\ Dependency \\ \end{tabular} & \begin{tabular}{c} Sparse \\ Labels \\ \end{tabular} & 
\begin{tabular}{c} Statistical \\ Threshold \\ \end{tabular} \\ \hline \(\text{H}_{\text{data}}\) & linear & \(\mathcal{K}\) & \(\mathcal{K}\) & \(\mathcal{K}\) \\ \(\text{H}_{\text{data}}\) & linear & \(\mathcal{K}\) & \(\mathcal{K}\) & \(\mathcal{K}\) \\ \(\text{H}_{\text{data}}\) & linear & \(\mathcal{K}\) & \(\mathcal{K}\) & \(\mathcal{K}\) \\ \(\text{H}_{\text{data}}\) & linear & \(\mathcal{K}\) & \(\mathcal{V}\) & \(\mathcal{K}\) \\ \(\text{H}_{\text{data}}\) & linear & \(\mathcal{V}\) & \(\mathcal{V}\) & \(\mathcal{K}\) \\ Classifier & both & \(\mathcal{V}\) & \(\mathcal{V}\) & \(\mathcal{V}\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Property comparisons of performance metrics