# When Do Graph Neural Networks Help with Node Classification? Investigating
the Impact of Homophily Principle on Node Distinguishability

Sitao Luan1,2, Chenqing Hua1,2, Minkai Xu4, Qincheng Lu1, Jiaqi Zhu1,
Xiao-Wen Chang1,†, Jie Fu2,5,†, Jure Leskovec4,†, Doina Precup1,2,3,†
{sitao.luan@mail, chenqing.hua@mail, qincheng.lu@mail, jiaqi.zhu@mail,
chang@cs,
<EMAIL_ADDRESS>{minkai<EMAIL_ADDRESS><EMAIL_ADDRESS>
1McGill University; 2 Mila - Quebec Artificial Intelligence Institute; 3Google
DeepMind;
4Stanford University; 5HKUST; † Corresponding Authors

###### 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 [38]. 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.

##  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, 36, 23], and have been shown to outperform
traditional neural networks (NNs) 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 principle (assumption) [42],
which states that connected nodes tend to have similar attributes [18],
providing extra useful information to the aggregated features over the
original node features. Such relational inductive bias is thought to be a
major contributor to the superiority of GNNs over NNs on 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 [57, 55, 37]. Numerous models have been proposed to address
the heterophily challenge lately [46, 57, 55, 37, 5, 32, 7, 54, 21, 34, 31,
51, 35].

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 [38, 35,
37]. For example, the authors in [38] 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 [35] studied homophily/heterophily from post-
aggregation node similarity perspective and found that heterophily is not
always harmful, which is consistent with [38]. Besides, the authors in [37]
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 [46, 57, 32]. 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 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-based 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 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 levels, alongside class variance
parameters to control intra-class ND, and node degree parameters which are
important to study homophily [38, 54]; 3. To quantify ND of CSBM-H, we propose
and compute two ND metrics, Probabilistic Bayes Error (PBE) and Negative
Generalized Jeffreys Divergence ($D_{\text{NGJ}}$), for the optimal Bayes
classifier of CSBM-H. Based on the metrics, we can analytically study how
intra- and inter-class ND impact ND together. We visualize the relationship
between PBE, $D_{\text{NGJ}}$ 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), a 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-aware models over
graph-agnostic.

##  2 Preliminaries

We use bold font for vectors (e.g.,$\bm{v}$) and define a 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$. $D$ is the diagonal
degree matrix of the graph, with $D_{i,i}=d_{i}=\sum_{j}A_{i,j}$. The
neighborhood set $\mathcal{N}_{i}$ of node $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_{h}}$ to denote the feature matrix, whose
columns are graph signals and $i$-th row ${X_{i,:}}=\bm{x}_{i}^{\top}$ is the
feature vector of node $i$ (i.e., the full-pass (FP) filtered signal). The
label encoding matrix is $Z\in\mathbb{R}^{N\times C}$, where $C$ is the number
of classes, and its $i$-th row $Z_{i,:}$ is the one-hot encoding of the label
of node $i$. We denote
$z_{i}=\operatorname*{arg\,max}_{j}Z_{i,j}\in\\{1,2,\dots C\\}$. The indicator
function $\bm{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}$.

###  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]; A
network that does not use graph structure information 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-1 is
coupled with MLP-1 as below,

$\displaystyle\textbf{GCN:
}Y=\text{Softmax}(\hat{A}_{\text{sym}}\;\text{ReLU}(\hat{A}_{\text{sym}}{X}W_{0})\;W_{1}),\;\;\textbf{MLP-2:
}Y=\text{Softmax}(\text{ReLU}({X}W_{0})\;W_{1})$ (1)
$\displaystyle\textbf{SGC-1:
}Y=\text{Softmax}(\hat{A}_{\text{sym}}{X}W_{0}),\;\;\textbf{MLP-1:
}Y=\text{Softmax}({X}W_{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,\dots 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 [19]. 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
[38, 35].

To address the heterophily challenge, high-pass (HP) filter [14], such as
$I-\hat{A}_{\text{rw}}$, is often used to replace low-pass (LP) filter [39]
$\hat{A}_{\text{rw}}$ in GCN [5, 7, 35]. In this paper, we use
$\hat{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
$\bm{h}_{i}=(H_{i,:})^{\top},\bm{h}_{i}^{\text{HP}}=(H_{i,:}^{\text{HP}})^{\top}$.

To measure how likely the G-aware model can 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 a way to describe the relationship between node labels
and graph structure. We introduce five commonly used homophily metrics: edge
homophily [1, 57], node homophily [46], class homophily [32], generalized edge
homophily [26] and aggregation homophily [35], adjusted homophily [47] and
label informativeness [47] as follows:

$\displaystyle\leavevmode\resizebox{441.57083pt}{}{$\text{H}_{\text{edge}}(\mathcal{G})=\frac{\big{|}\\{e_{uv}\mid
e_{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\mid
u\in\mathcal{N}_{v},Z_{u,:}=Z_{v,:}\\}\big{|}}{d_{v}},$}$ (2)
$\displaystyle\leavevmode\resizebox{441.57083pt}{}{$\text{H}_{\text{class}}(\mathcal{G})\\!=\\!\frac{1}{C\\!-\\!1}\sum_{k=1}^{C}\bigg{[}h_{k}\\!-\\!\frac{\big{|}\\{v\\!\mid\\!Z_{v,k}\\!=\\!1\\}\big{|}}{N}\bigg{]}_{+},\;\text{where
}h_{k}\\!=\\!\frac{\sum_{v\in\mathcal{V},Z_{v,k}=1}\big{|}\\{u\\!\mid\\!u\in\mathcal{N}_{v},Z_{u,:}\\!=\\!Z_{v,:}\\}\big{|}}{\sum_{v\in\\{v|Z_{v,k}=1\\}}d_{v}},$}$
$\displaystyle\leavevmode\resizebox{441.57083pt}{}{$\text{H}_{\text{GE}}(\mathcal{G})=\frac{\sum\limits_{(i,j)\in\mathcal{E}}\text{cos}(\bm{x}_{i},\bm{x}_{j})}{|\mathcal{E}|},\;\text{H}_{\text{agg}}(\mathcal{G})=\frac{1}{\left|\mathcal{V}\right|}\times\left|\left\\{v\,\big{|}\,\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}^{Z_{u,:}=Z_{v,:}}\\}\big{)}\geq\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}^{Z_{u,:}\neq
Z_{v,:}}\\}\big{)}\right\\}\right|,$}$
$\displaystyle\text{H}_{\text{adj}}=\frac{\text{H}_{\text{edge}}-\sum_{c=1}^{C}\bar{p}_{c}^{2}}{1-\sum_{k=1}^{C}\bar{p}_{c}^{2}},\;\text{LI}=-\frac{\sum_{c_{1},c_{2}}p_{c_{1},c_{2}}\log\frac{p_{c_{1},c_{2}}}{\bar{p}_{c_{1}}\bar{p}_{c_{2}}}}{\sum_{c}\bar{p}_{c}\log\bar{p}_{c}}=2-\frac{\sum_{c_{1},c_{2}}p_{c_{1},c_{2}}\log
p_{c_{1},c_{2}}}{\sum_{c}\bar{p}_{c}\log\bar{p}_{c}}$

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 [32];
$\mathrm{Mean}_{u}\left(\\{\cdot\\}\right)$ takes the average over $u$ of a
given multiset of values or variables and
$S(\hat{A},Z)=\hat{A}Z(\hat{A}Z)^{\top}$ is the post-aggregation node
similarity matrix;
$D_{c}=\sum_{v:z_{v}=c}d_{v},\bar{p}_{c}=\frac{D_{c}}{2|\mathcal{E}|}$,
$p_{c_{1},c_{2}}=\sum_{(u,v)\in\mathcal{E}}\frac{\bm{1}\left\\{z_{u}=c_{1},z_{v}=c_{2}\right\\}}{2|\mathcal{E}|},c,c_{1},c_{2}\in\\{1,\dots,C\\}$.

These metrics all fall within the range of $[0,1]$, with a value closer to $1$
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, feature-independent metrics
which cannot provide a 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.

Figure 1: Example of intra- and inter-class node distinguishability.

##  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" [38, 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 is 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 4. 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.

###  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 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 [49, 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/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
intra-class ND. We then derive the optimal Bayes classifier
($\text{CL}_{\text{Bayes}}$) and negative generalized Jeffreys divergence for
CSBM-H, based on which we can quantify and investigate ND for CSBM-H.

CSBM-H($\bm{\mu}_{0},\bm{\mu}_{1},\sigma_{0}^{2}I,\sigma_{1}^{2}I,{d}_{0},{d}_{1},h$)111This
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. 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 $\bm{x}_{i}$ generated from
$N(\bm{\mu}_{0},\sigma_{0}^{2}I)$ and $\bm{x}_{j}$ generated from
$N(\bm{\mu}_{1},\sigma_{1}^{2}I)$, where
$\bm{\mu}_{0},\bm{\mu}_{1}\in\mathbb{R}^{F_{h}}$ and ${F_{h}}$ is the
dimension of the embeddings. The degree 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 222To avoid unnecessary confusion: we relax $hd_{0}$ and $(1-h)d_{0}$ to
be continuous values so that the visualization in the following sections are
more readable and intuitive, especially to show the intersections of the
curves.. The neighbors of $j\in\mathcal{C}_{1}$ are generated in the same way.
As a result, the FP (full-pass), LP and HP filtered features are generated as
follows,

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

where
$\tilde{\bm{\mu}}_{0}={h}(\bm{\mu}_{0}-\bm{\mu}_{1})+\bm{\mu}_{1},\;\tilde{\bm{\mu}}_{1}={h}(\bm{\mu}_{1}-\bm{\mu}_{0})+\bm{\mu}_{0},\;\tilde{\bm{\mu}}_{0}^{\text{HP}}=(1-{h})(\bm{\mu}_{0}-\bm{\mu}_{1}),\;\tilde{\bm{\mu}}_{1}^{\text{HP}}=(1-{h})(\bm{\mu}_{1}-\bm{\mu}_{0}),\;\tilde{\sigma}_{0}^{2}=\frac{({h}(\sigma_{0}^{2}-\sigma_{1}^{2})+\sigma_{1}^{2})}{{d}_{0}},\;\tilde{\sigma}_{1}^{2}=\frac{({h}(\sigma_{1}^{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
$\bm{x}_{i}\in{\cal C}_{0}$ for $i\in{\cal C}_{0}$ and $\bm{x}_{j}\in{\cal
C}_{1}$ for $j\in{\cal C}_{1}$.

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

  * Theorem1.

Suppose $\sigma_{0}^{2}\neq\sigma_{1}^{2}$ and
$\sigma_{0}^{2},\sigma_{1}^{2}>0$, the prior distribution for $\bm{x}$ is
$\mathbb{P}(\bm{x}\in{\cal C}_{0})=\mathbb{P}(\bm{x}\in{\cal C}_{1})=1/2$,
then the optimal Bayes Classifier ($\text{CL}_{\text{Bayes}}$) for CSBM-H
($\bm{\mu}_{0},\bm{\mu}_{1},\sigma_{0}^{2}I,\sigma_{1}^{2}I,{d}_{0},{d}_{1},{h}$)
is

$\text{CL}_{\text{Bayes}}(\bm{x})=\left\\{\begin{aligned} 1,\;\eta(\bm{x})\geq
0.5\\\
0,\;\eta(\bm{x})<0.5\end{aligned}\right.,\;\eta(\bm{x})=\mathbb{P}(z=1|\bm{x})=\frac{1}{1+\exp{\left(Q(\bm{x})\right)}},$

where $Q(\bm{x})=a\bm{x}^{\top}\bm{x}+\bm{b}^{\top}\bm{x}+c,\
a=\frac{1}{2}\left(\frac{1}{\sigma_{1}^{2}}-\frac{1}{\sigma_{0}^{2}}\right),\bm{b}=\frac{\bm{\mu}_{0}}{\sigma_{0}^{2}}-\frac{\bm{\mu}_{1}}{\sigma_{1}^{2}},c=\frac{\bm{\mu}_{1}^{\top}\bm{\mu}_{1}}{2\sigma_{1}^{2}}-\frac{\bm{\mu}_{0}^{\top}\bm{\mu}_{0}}{2\sigma_{0}^{2}}+\ln{\left(\frac{\sigma_{1}^{F_{h}}}{\sigma_{0}^{F_{h}}}\right)}$
333The Bayes classifier for multiple categories ($>2$) can be computed by
stacking multiple expectation terms using similar methods as in [12, 15]. We
do not discuss the more complicated settings in this paper.. See the proof in
Appendix A.

Advantages of $\text{CL}_{\text{Bayes}}$ Over the Fixed Linear Classifier in
[38] The decision boundary in [38] is defined as
$P=\\{\bm{x}|\bm{w}^{\top}\bm{x}-\bm{w}^{\top}(\bm{\mu}_{0}+\bm{\mu}_{1})/2\\}$
where $\bm{w}=(\bm{\mu}_{0}-\bm{\mu}_{1})/||\bm{\mu}_{0}-\bm{\mu}_{1}||_{2}$
is a fixed parameter. This classifier only depends on
$\bm{\mu}_{0},\bm{\mu}_{1}$ and is 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 $\sigma_{0}^{2},\sigma_{1}^{2}$ and node degrees $d_{0},d_{1}$
affect ND with the fixed classifier in [38].

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 be used together
to analyze ND.

###  3.3 Measure Node Distinguishability of CSBM-H

The Bayes error rate (BE) of the data distribution is the probability of a
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 $\text{CL}_{\text{Bayes}}$ is defined as follows,

######  Definition 1 (Bayes Error Rate).

The Bayes error rate [20] for $\textup{CL}_{\textup{Bayes}}$ is defined as

BE
$\displaystyle=\mathbb{E}_{\bm{x}}[\mathbb{P}(z|\textup{CL}_{\textup{Bayes}}(\bm{x})\neq
z)]=\mathbb{E}_{\bm{x}}[1-\mathbb{P}(\textup{CL}_{\textup{Bayes}}(\bm{x})=z|\bm{x})]$

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

$\displaystyle\leavevmode\resizebox{441.57083pt}{}{$\text{BE}=\mathbb{P}\left(\bm{x}\in\mathcal{C}_{0}\right)\left(1-\mathbb{P}(\text{CL}_{\text{Bayes}}(\bm{x})=0|\bm{x}\in\mathcal{C}_{0})\right)+\mathbb{P}(\bm{x}\in\mathcal{C}_{1})\left(1-\mathbb{P}(\text{CL}_{\text{Bayes}}(\bm{x})=1|\bm{x}\in\mathcal{C}_{1})\right).$}$
(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
$\bm{x}$ is independently normally distributed. As a result, $Q(\bm{x})$
defined in Theorem 1 follows a generalized $\chi^{2}$ distribution [9, 10](See
the calculation in Appendix C). Specifically,

$\displaystyle\text{For
}\bm{x}_{i}\in\mathcal{C}_{0},\;Q(\bm{x}_{i})\sim\tilde{\chi}^{2}(w_{0},F_{h},\lambda_{0})+\xi;\;\bm{x}_{j}\in\mathcal{C}_{1},\;Q(\bm{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{\bm{\mu}_{0}}{\sigma_{0}}+\frac{\bm{b}}{2a\sigma_{0}})^{\top}(\frac{\bm{\mu}_{0}}{\sigma_{0}}+\frac{\bm{b}}{2a\sigma_{0}}),\;\lambda_{1}=(\frac{\bm{\mu}_{1}}{\sigma_{1}}+\frac{\bm{b}}{2a\sigma_{1}})^{\top}(\frac{\bm{\mu}_{1}}{\sigma_{1}}+\frac{\bm{b}}{2a\sigma_{1}})\;\text{
and }\xi=c-\frac{\bm{b}^{\top}\bm{b}}{4a}\;$. Then, by using the Cumulative
Distribution Function (CDF) of $\tilde{\chi}^{2}$, we can calculate the
predicted probabilities directly as,

$\displaystyle\leavevmode\resizebox{469.75499pt}{}{$\mathbb{P}(\text{CL}_{\text{Bayes}}(\bm{x})=0|\bm{x}\in\mathcal{C}_{0})=1-\text{CDF}_{\tilde{\chi}^{2}(w_{0},F_{h},\lambda_{0})}(-\xi),\
\mathbb{P}(\text{CL}_{\text{Bayes}}(\bm{x})=1|\bm{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}(\bm{x}\in\mathcal{C}_{0})=\mathbb{P}(\bm{x}\in\mathcal{C}_{1})=1/2$.
Then, PBE is,

$\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 for LP and HP filtered
embeddings, we just need to replace
$\left(\bm{\mu}_{0},\sigma_{0}^{2},\bm{\mu}_{1},\sigma_{1}^{2}\right)$ by
$\left(\tilde{\bm{\mu}}_{0},\tilde{\sigma}_{0}^{2},\tilde{\bm{\mu}}_{1},\tilde{\sigma}_{1}^{2}\right)$
and
$\left(\tilde{\bm{\mu}}_{0}^{\text{HP}},(\tilde{\sigma}_{0}^{\text{HP}})^{2},\tilde{\bm{\mu}}_{1}^{\text{HP}},(\tilde{\sigma}_{1}^{\text{HP}})^{2}\right)$
as equation 3.

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

######  Definition 2 (Generalized Jeffreys Divergence).

For a random variable $\bm{x}$ which has either the distribution $P(\bm{x})$
or the distribution $Q(\bm{x})$, the generalized Jeffreys divergence
444Jeffreys divergence [25] is originally defined as
$D_{\text{KL}}(P||Q)+D_{\text{KL}}(Q||P)$ is defined as

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

With $\mathbb{P}(\bm{x}\sim P)=\mathbb{P}(\bm{x}\sim Q)=1/2$ 555We provide an
open-ended discussion of imbalanced prior distributions in Appendix D., the
negative generalized Jeffreys divergence for the two-normal setting in CSBM-H
can be computed by (See Appendix B for the calculation)

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

where
$d_{X}^{2}=(\bm{\mu}_{0}-\bm{\mu}_{1})^{\top}(\bm{\mu}_{0}-\bm{\mu}_{1})$ is
the squared Euclidean distance between centers;
$\rho=\frac{\sigma_{0}}{\sigma_{1}}$ and since we assume
$\sigma_{0}^{2}<\sigma_{1}^{2}$, we have $0<\rho<1$. For $\bm{h}$ and
$\bm{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}}$ the CSBM-H has, the more distinguishable the
embeddings are.

From equation 5, we can see that $D_{\text{NGJ}}$ implies that ND 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}}$ 666See two more metrics, negative squared Wasserstein
distance and Hellinger distance, in Appendix E.3.. Specifically, we set the
standard CSBM-H as
$\bm{\mu}_{0}=[-1,0],\bm{\mu}_{1}=[0,1],\sigma_{0}^{2}=1,\sigma_{1}^{2}=2,d_{0}=5,d_{1}=5$.
And as shown in Figure 2, its PBE and $D_{\text{NGJ}}$ curves for LP filtered
feature $\bm{h}$ are bell-shaped 777This is consistent with the empirical
results found in [35] that the relationship between the prediction accuracy of
GNN and homophily value is a U-shaped curve.. 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 as the mid-
homophily pitfall.

The PBE and $D_{\text{NGJ}}$ curves for $\bm{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 $\bm{x}$,
$\bm{h}$, and $\bm{h}^{\text{HP}}$ will get the lowest PBE and
$D_{\text{NGJ}}$ 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 888This verifies the conjecture made in [35] saying that high-pass
filter cannot address all kinds of heterophily and only works well for certain
heterophily cases., 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.

(a) PBE (b) $D_{\text{NGJ}}$ (c) ENND (d) NVR

Figure 2:  Visualization of CSBM-H
$\left(\bm{\mu}_{0}=[-1,0],\bm{\mu}_{1}=[0,1],\sigma_{0}^{2}=1,\sigma_{1}^{2}=2,\right.$
$\left.d_{0}=5,d_{1}=5\right)$

###  3.4 Ablation Study on CSBM-H

(a) PBE (b) $D_{\text{NGJ}}$ (c) ENND (d) NVR

Figure 3: Comparison of CSBM-H with $\sigma^{2}_{0}=1,\sigma^{2}_{1}=5$.

(a) PBE (b) $D_{\text{NGJ}}$ (c) ENND (d) Negative Variance Ratio

Figure 4: Comparison of CSBM-H with $\sigma^{2}_{0}=1.9,\sigma^{2}_{1}=2$.

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 regimes and the expansion of the FP regime indicates that
the original features are more robust to imbalanced variances especially in
the low homophily area. From Figure 3 (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 2 curves. This implies that the HP curve exhibits
less sensitivity to $\rho$ within the area of low homophily.

Increase the Variance of Low-variation Class
($\sigma_{0}^{2}=1.9,\sigma_{1}^{2}=2$) As shown in Figure 4, 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 regimes almost stays the same because
the magnitude of NVR becomes too small that it almost has no effect to ND as
shown in Figure 4 (d).

Interestingly, we found the change of variances cause less differences of the
3 regimes in ENND than that in NVR 999To verify this, we increase
$\sigma_{0}^{2}$ and $\sigma_{1}^{2}$ proportionally. From Figure 10 in
Appendix F, relative sizes of the FP, LP, and HP areas remain similar. and HP
filter is less sensitive to $\rho$ changes in low homophily area than LP and
FP filters. This insensitivity will have significant impact to the 3 regimes
when $\rho$ is close to $0$ and have trivial effect when $\rho$ is close to
$1$ because the magnitude of NVR is too small.

Increase the Node Degree of High-variation Class ($d_{0}=5,d_{1}=25$) From
Figure 5, 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 regime and shrinkage of FP
and HP regime. 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 6, we have the similar observation as when we increase the node degree
of high-variation class. The difference is that the expansion of LP regime and
shrinkage of FP and HP regimes 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 aggregated
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.

(a) PBE (b) $D_{\text{NGJ}}$ (c) ENND (d) NVR

Figure 5: Comparison of CSBM with different $d_{0}=5,d_{1}=25$ setups.

(a) PBE (b) $D_{\text{NGJ}}$ (c) ENND (d) NVR

Figure 6: Comparison of CSBM with different $d_{0}=25,d_{1}=5$ setups.

###  3.5 More General Theoretical Analysis

Besides the toy example, in this subsection, we aim to gain a deeper
understanding of how LP and HP filters affect ND in a broader context beyond
the two-normal settings. To be consistent with previous literature, we follow
the assumptions outlined in [38], which are: 1. The features of node $i$ are
sampled from distribution $\mathcal{F}_{z_{i}}$, i.e.,,
$\bm{x}_{i}\sim\mathcal{F}_{z_{i}}$, with mean
$\bm{\mu}_{z_{i}}\in\mathbb{R}^{F_{h}}$; 2. Dimensions of $\bm{x}_{i}$ are
independent to each other; 3. Each dimension in feature $\bm{x}_{i}$ is
bounded, i.e., $a\leq\bm{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}=\\{1,\dots,C\\}$
and $(b-a)^{2}$ reflects how variation the features are. The authors in [38]
analyze the distance between the aggregated node embedding and its
expectation, i.e.,
$\left\lVert\bm{h}_{i}-\mathbb{E}(\bm{h}_{i})\right\rVert_{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.

  * Theorem2.

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 nodes $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

$\displaystyle\leavevmode\resizebox{328.82706pt}{}{$\mathbb{P}\left(\left\lVert\bm{x}_{i}-\bm{x}_{j}\right\rVert_{2}\geq\left\lVert\bm{x}_{i}-\bm{x}_{v}\right\rVert_{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)},$}$
(6)
$\displaystyle\leavevmode\resizebox{328.82706pt}{}{$\mathbb{P}(\left\lVert\bm{h}_{i}-\bm{h}_{j}\right\rVert_{2}\geq\left\lVert\bm{h}_{i}-\bm{h}_{v}\right\rVert_{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)},$}$
$\displaystyle\leavevmode\resizebox{328.82706pt}{}{$\mathbb{P}(\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{j}^{\text{HP}}\right\rVert_{2}\geq\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{v}^{\text{HP}}\right\rVert_{2}+t_{\text{HP}})\leq
2F_{h}\exp{\left(-\frac{\left(D_{\text{HP}}(v,j)-\frac{t_{\text{HP}}}{\sqrt{F_{h}}}\right)^{2}}{V_{\text{HP}}(v,j)}\right)},$}$

See the proof in Appendix G

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

Figure 7: Demonstration of how HP filter captures the relative center
distance.

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 together rather than
intra-class ND only, which is consistent with CSBM-H.

Table 1: P-values, homophily values and classifier-based performance metrics
on 9 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 1 of the 2 tests. We use 0.5 as the threshold value of the
homophily metrics.

|  | Cornell | Wisconsin | Texas | Film | Chameleon | Squirrel | Cora | CiteSeer | PubMed
---|---|---|---|---|---|---|---|---|---|---
| $\text{H}_{\text{edge}}$ | 0.5669 | 0.4480 | 0.4106 | 0.3750 | 0.2795 | 0.2416 | 0.8100 | 0.7362 | 0.8024
| $\text{H}_{\text{node}}$ | 0.3855 | 0.1498 | 0.0968 | 0.2210 | 0.2470 | 0.2156 | 0.8252 | 0.7175 | 0.7924
Baseline | $\text{H}_{\text{class}}$ | 0.0468 | 0.0941 | 0.0013 | 0.0110 | 0.0620 | 0.0254 | 0.7657 | 0.6270 | 0.6641
Homophily | $\text{H}_{\text{agg}}$ | 0.8032 | 0.7768 | 0.694 | 0.6822 | 0.61 | 0.3566 | 0.9904 | 0.9826 | 0.9432
Metrics | $\text{H}_{\text{GE}}$ | 0.31 | 0.34 | 0.35 | 0.16 | 0.0152 | 0.0157 | 0.17 | 0.19 | 0.27
| $\text{H}_{\text{adj}}$ | 0.1889 | 0.0826 | 0.0258 | 0.1272 | 0.0663 | 0.0196 | 0.8178 | 0.7588 | 0.7431
| LI | 0.0169 | 0.1311 | 0.1923 | 0.0002 | 0.048 | 0.0015 | 0.5904 | 0.4508 | 0.4093
Classifier-based | $\text{KR}_{\text{NNGP}}$ | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00
Performance Metrics | GNB | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00
SGC v.s. MLP-1 | p-value | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
ACC SGC | 70.98 $\pm$ 8.39 | 70.38 $\pm$ 2.85 | 83.28 $\pm$ 5.43 | 25.26 $\pm$ 1.18 | 64.86 $\pm$ 1.81 | 47.62 $\pm$ 1.27 | 85.12 $\pm$ 1.64 | 79.66 $\pm$ 0.75 | 85.5 $\pm$ 0.76
ACC MLP-1 | 93.77 $\pm$ 3.34 | 93.87 $\pm$ 3.33 | 93.77 $\pm$ 3.34 | 34.53 $\pm$ 1.48 | 45.01 $\pm$ 1.58 | 29.17 $\pm$ 1.46 | 74.3 $\pm$ 1.27 | 75.51 $\pm$ 1.35 | 86.23 $\pm$ 0.54
Diff Acc | -22.79 | -23.49 | -10.49 | -9.27 | 19.85 | 18.45 | 10.82 | 4.15 | -0.73
GCN v.s. MLP-2 | p-value | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.00
ACC GCN | 82.46 $\pm$ 3.11 | 75.5 $\pm$ 2.92 | 83.11 $\pm$ 3.2 | 35.51 $\pm$ 0.99 | 64.18 $\pm$ 2.62 | 44.76 $\pm$ 1.39 | 87.78 $\pm$ 0.96 | 81.39 $\pm$ 1.23 | 88.9 $\pm$ 0.32
ACC MLP-2 | 91.30 $\pm$ 0.70 | 93.87 $\pm$ 3.33 | 92.26 $\pm$ 0.71 | 38.58 $\pm$ 0.25 | 46.72 $\pm$ 0.46 | 31.28 $\pm$ 0.27 | 76.44 $\pm$ 0.30 | 76.25 $\pm$ 0.28 | 86.43 $\pm$ 0.13
Diff Acc | -8.84 | -18.37 | -9.15 | -3.07 | 17.46 | 13.48 | 11.34 | 5.14 | 2.47

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

###  4.1 Hypothesis Testing 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 101010Authors in [33] 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 [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 111111A 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 as significantly distinguishable. This second statistical test is
necessary to avoid noisy nodes. In practice, we noticed that the ratio of
intra-class node distance to inter-class node distance is roughly 1 for lots
of nodes. This is 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 want to take account
these ”marginal nodes” into the comparison of Prop values and we found that
using another hypothesis test would be helpful. e.g., we obtain
$\text{Prop}(\text{GCN})$ for GCN. We use Prop to quantify ND and we train the
models multiple times for samples to conduct the following hypothesis tests:

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/test sets with a
ratio of 60%/20%/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 1 (See more
experimental tests on state-of-the-art model in Appendix H).

It is observed that, in most cases (except for GCN vs. MLP-2 on PubMed
121212We discuss this special case in Appendix H.4, together with some similar
inconsistency instances found on large-scale datasets.), 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 vs. 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.

###  4.2 Towards A Better Metric Beyond Homophily: Classifier-based
Performance Metric

A qualified classifier should not require iterative training. In this paper,
we choose Gaussian Naïve Bayes (GNB)[20] and Kernel Regression (KR) with
Neural Network Gaussian Process (NNGP) [30, 2, 16, 41] to capture the feature-
based linear or non-linear information.

To get the p-value efficiently, we first randomly sample 500 labeled 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 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, we compute the p-value of the following hypothesis testing,

$\displaystyle\text{H}_{0}:\text{Acc}(\text{Classifier}(H))\geq\text{Acc}(\text{Classifier}(X));\
\text{H}_{1}:\text{Acc}(\text{Classifier}(H))<\text{Acc}(\text{Classifier}(X))$

The p-value can provide a statistical threshold value, such as 0.05, to
indicate whether $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 H for
more details on classifier-based performance metrics, experiments on synthetic
datasets, more detailed comparisons on small-scale and large-scale datasets,
discrepancy between linear and non-linear models, results for symmetric
renormalized affinity matrix and running time.)

Table 2: Property comparisons of performance metrics

Performance | Linear or | Feature | Sparse | Statistical
---|---|---|---|---
Metrics | Non-linear | Dependency | Labels | Threshold
$\text{H}_{\text{node}}$ | linear | ✗ | ✗ | ✗
$\text{H}_{\text{edge}}$ | linear | ✗ | ✗ | ✗
$\text{H}_{\text{class}}$ | linear | ✗ | ✗ | ✗
$\text{H}_{\text{agg}}$ | linear | ✗ | ✓ | ✗
$\text{H}_{\text{GE}}$ | linear | ✓ | ✓ | ✗
$\text{H}_{\text{adj}}$ | linear | ✗ | ✗ | ✗
LI | linear | ✗ | ✗ | ✗
Classifier | both | ✓ | ✓ | ✓

##  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 graph
filters, class variances and node degree distributions will influence the PBE
and $D_{\text{NGJ}}$ 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 filter 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 a non-
linear feature-based metric and can provide statistical threshold value.

##  6 Reproducibility and Blogs

  * •

Code: https://github.com/SitaoLuan/When-Do-GNNs-Help.

  * •

Blog in English (on Medium): https://medium.com/SitaoLuan/when-should-we-use-
graph-neural-networks-for-node-classification-8ce77a772085.

  * •

Blog in Chinese (on Zhihu): https://zhuanlan.zhihu.com/p/653631858.

##  7 Acknowledgements

This work was partially supported by the Natural Sciences and Engineering
Research Council of Canada (NSERC) Grant RGPIN-2023-04125, 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-El-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan, G. Ver Steeg, and A. Galstyan.  Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing.  In international conference on machine learning, pages 21–29. PMLR, 2019.
  * [2] S. Arora, S. S. Du, W. 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, R. Faulkner, et al.  Relational inductive biases, deep learning, and graph networks.  arXiv preprint arXiv:1806.01261, 2018.
  * [5] D. Bo, X. Wang, C. Shi, and H. Shen.  Beyond low-frequency information in graph convolutional networks.  arXiv preprint arXiv:2101.00797, 2021.
  * [6] J. Chen, S. Chen, J. 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, J. 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 as 155: The distribution of a linear combination of $\chi$ 2 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 B. Landau.  The fréchet distance between multivariate normal distributions.  Journal of multivariate analysis, 12(3):450–455, 1982.
  * [14] V. N. Ekambaram.  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.  IEEE Transactions on Information Theory, 39(4):1146–1151, 1993\.
  * [16] A. Garriga-Alonso, C. E. Rasmussen, and L. Aitchison.  Deep convolutional networks as shallow gaussian processes.  arXiv preprint arXiv:1808.05587, 2018.
  * [17] C. R. Givens and R. M. Shortt.  A class of wasserstein metrics for probability distributions.  Michigan Mathematical Journal, 31(2):231–240, 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, abs/1706.02216, 2017.
  * [20] T. Hastie, R. Tibshirani, J. H. Friedman, and 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 learning1.  The Annals of Statistics, 36(3):1171–1220, 2008.
  * [23] C. Hua, G. Rabusseau, and J. Tang.  High-order pooling for graph neural networks with tensor decomposition.  arXiv preprint arXiv:2205.11691, 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):453–461, 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.13953, 2022.
  * [27] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  arXiv, abs/1609.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 preprint arXiv:1711.00165, 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 arXiv:2205.07308, 2022.
  * [32] D. Lim, X. Li, F. Hohne, and S.-N. Lim.  New benchmarks for learning on non-homophilous graphs.  arXiv preprint arXiv:2104.01404, 2021.
  * [33] S. Luan, C. Hua, Q. Lu, J. Zhu, X.-W. Chang, and D. Precup.  When do we 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 heterophily a real nightmare for graph neural networks to do node classification?  arXiv preprint arXiv:2109.05641, 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: Stronger multi-scale deep graph convolutional networks.  Advances in neural information processing systems, 32, 2019.
  * [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 NeurIPS 2022 Workshop: New Frontiers in Graph Learning, 2022\.
  * [38] Y. Ma, X. Liu, N. Shah, and J. Tang.  Is homophily a necessity for graph neural networks?  arXiv preprint arXiv:2106.06134, 2021.
  * [39] T. Maehara.  Revisiting graph neural networks: All we have is low-pass filters.  arXiv preprint arXiv:1905.09550, 2019.
  * [40] P. Massart.  Concentration inequalities and model selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII-2003.  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:1804.11271, 2018.
  * [42] M. McPherson, L. Smith-Lovin, and J. M. Cook.  Birds of a feather: Homophily in social networks.  Annual review of sociology, 27(1):415–444, 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 Algebra and its Applications, 48:257–263, 1982.
  * [45] L. Pardo.  Statistical inference based on divergence measures.  CRC press, 2018.
  * [46] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang.  Geom-gcn: Geometric graph convolutional networks.  arXiv preprint arXiv:2002.05287, 2020.
  * [47] O. Platonov, D. Kuznedelev, A. Babenko, and L. Prokhorenkova.  Characterizing graph datasets for node classification: Beyond homophily-heterophily dichotomy.  arXiv preprint arXiv:2209.06177, 2022.
  * [48] J. Tanton.  Encyclopedia of mathematics.  Facts On File, Inc, 2005.
  * [49] A. Tsitsulin, B. Rozemberczki, J. Palowitch, and B. Perozzi.  Synthetic graph generation to benchmark 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, J. Jia, A. R. Benson, and P. Li.  Understanding non-linearity in graph neural networks from the bayesian-inference perspective.  arXiv preprint arXiv:2207.11311, 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:1902.07153, 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 arXiv:2102.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] J. 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 11168–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.

##  Appendix A Proof of Theorem 1

  * Theorem1.

Suppose $\sigma_{0}^{2}\neq\sigma_{1}^{2}$ and
$\sigma_{0}^{2},\sigma_{1}^{2}>0$, the prior distribution for $\bm{x}_{i}$ is
$\mathbb{P}(\bm{x}_{i}\in{\cal C}_{0})=\mathbb{P}(\bm{x}_{i}\in{\cal
C}_{1})=1/2$, then the optimal Bayes Classifier ($\text{CL}_{\text{Bayes}}$)
for CSBM-H
($\bm{\mu}_{0},\bm{\mu}_{1},\sigma_{0}^{2}I,\sigma_{1}^{2}I,{d}_{0},{d}_{1},{h}$)
is

$\text{CL}_{\text{Bayes}}(\bm{x}_{i})=\left\\{\begin{aligned}
1,\;\eta(\bm{x}_{i})\geq 0.5\\\
0,\;\eta(\bm{x}_{i})<0.5\end{aligned}\right.,\;\eta(\bm{x}_{i})=\mathbb{P}(z_{i}=1|\bm{x}_{i})=\frac{1}{1+\exp{\left(Q(\bm{x}_{i})\right)}},$

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

###### Proof.

Since the prior distribution for $\text{CL}_{\text{Bayes}}$ is

$\displaystyle\mathbb{P}(\bm{x}_{i}\in{\cal
C}_{0})=\mathbb{P}(\bm{x}_{i}\in{\cal C}_{1})=\frac{1}{2}$
$\displaystyle\text{CL}_{\text{Bayes}}(z_{i}=1|\bm{x}_{i})=\frac{\mathbb{P}(z_{i}=1,\bm{x}_{i})}{\mathbb{P}(\bm{x}_{i})}=\frac{\mathbb{P}(z_{i}=1)\mathbb{P}(\bm{x}_{i}|z_{i}=1)}{\mathbb{P}(z_{i}=0)\mathbb{P}(\bm{x}_{i}|z_{i}=0)+\mathbb{P}(z_{i}=1)\mathbb{P}(\bm{x}_{i}|z_{i}=1)}$
$\displaystyle=\frac{1}{1+\frac{\mathbb{P}(z_{i}=0)\mathbb{P}(\bm{x}_{i}|z_{i}=0)}{\mathbb{P}(z_{i}=1)\mathbb{P}(\bm{x}_{i}|z_{i}=1)}}=\frac{1}{1+\frac{(2\pi)^{-F_{h}/2}\det{\left(\sigma_{0}^{2}I\right)}^{-1/2}\exp{\left(-\frac{1}{2\sigma_{0}^{2}}(\bm{x}_{i}-\bm{\mu}_{0})^{\top}(\bm{x}_{i}-\bm{\mu}_{0})\right)}}{(2\pi)^{-F_{h}/2}\det{\left(\sigma_{1}^{2}I\right)}^{-1/2}\exp{\left(-\frac{1}{2\sigma_{1}^{2}}(\bm{x}_{i}-\bm{\mu}_{1})^{\top}(\bm{x}_{i}-\bm{\mu}_{1})\right)}}}$
$\displaystyle=\frac{1}{1+\frac{\sigma_{0}^{-F_{h}}}{\sigma_{1}^{-F_{h}}}\exp{\left(-\frac{1}{2\sigma_{0}^{2}}(\bm{x}_{i}-\bm{\mu}_{0})^{\top}(\bm{x}_{i}-\bm{\mu}_{0})+\frac{1}{2\sigma_{1}^{2}}(\bm{x}_{i}-\bm{\mu}_{1})^{\top}(\bm{x}_{i}-\bm{\mu}_{1})\right)}}$
$\displaystyle=\frac{1}{1+\frac{\sigma_{0}^{-F_{h}}}{\sigma_{1}^{-F_{h}}}\exp{\left(-\frac{1}{2\sigma_{0}^{2}}(\bm{x}_{i}^{\top}\bm{x}_{i}-2\bm{\mu}_{0}^{\top}\bm{x}_{i}+\bm{\mu}_{0}^{\top}\bm{\mu}_{0})+\frac{1}{2\sigma_{1}^{2}}(\bm{x}_{i}^{\top}\bm{x}_{i}-2\bm{\mu}_{1}^{\top}\bm{x}_{i}+\bm{\mu}_{1}^{\top}\bm{\mu}_{1})\right)}}$
$\displaystyle=\frac{1}{1+\exp{\left((\frac{1}{2\sigma_{1}^{2}}-\frac{1}{2\sigma_{0}^{2}})\bm{x}_{i}^{\top}\bm{x}_{i}+(\frac{\bm{\mu}_{0}}{\sigma_{0}^{2}}-\frac{\bm{\mu}_{1}}{\sigma_{1}^{2}})^{\top}\bm{x}_{i}+\frac{\bm{\mu}_{1}^{\top}\bm{\mu}_{1}}{2\sigma_{1}^{2}}-\frac{\bm{\mu}_{0}^{\top}\bm{\mu}_{0}}{2\sigma_{0}^{2}}+\ln{\left(\frac{\sigma_{1}^{F_{h}}}{\sigma_{0}^{F_{h}}}\right)}\right)}}$

For the more general case where $\mathbb{P}(\bm{x}_{i}\in{\cal
C}_{0})=\frac{n_{0}}{n_{0}+n_{1}},\ \mathbb{P}(\bm{x}_{i}\in{\cal
C}_{1})=\frac{n_{1}}{n_{0}+n_{1}}$, the results for $a,\bm{b}$ are the same
and
$c=\frac{\bm{\mu}_{1}^{\top}\bm{\mu}_{1}}{2\sigma_{1}^{2}}-\frac{\bm{\mu}_{0}^{\top}\bm{\mu}_{0}}{2\sigma_{0}^{2}}+\ln{\left(\frac{n_{0}\sigma_{1}^{F_{h}}}{n_{1}\sigma_{0}^{F_{h}}}\right)}$.
∎

##  Appendix B Generalized Jeffreys Divergence

Suppose we have

$\displaystyle P(\bm{x})=N(\bm{\mu}_{0},\sigma_{0}^{2}I),\
Q(\bm{x})=N(\bm{\mu}_{1},\sigma_{1}^{2}I)$

Then, the KL-divergence between $P(\bm{x})$ and $Q(\bm{x})$ is

$\displaystyle D_{\text{KL}}(P||Q)=\int
P(\bm{x})\ln{\frac{P(\bm{x})}{Q(\bm{x})}}d\bm{x}=\mathbb{E}_{\bm{x}\sim
P(\bm{x})}\ln{\frac{P(\bm{x})}{Q(\bm{x})}}$
$\displaystyle=\mathbb{E}_{\bm{x}\sim
P(\bm{x})}\ln{\left(\frac{\sigma_{1}^{F_{h}}}{\sigma_{0}^{F_{h}}}\exp\left(-\frac{1}{2}{\sigma}_{0}^{-2}(\bm{x}-\bm{\mu}_{0})^{\top}(\bm{x}-\bm{\mu}_{0})+\frac{1}{2}{\sigma}_{1}^{-2}(\bm{x}-\bm{\mu}_{1})^{\top}(\bm{x}-\bm{\mu}_{1})\right)\right)}$
$\displaystyle=F_{h}\ln{\frac{\sigma_{1}}{\sigma_{0}}}+\mathbb{E}_{\bm{x}\sim
P(\bm{x})}\left(-\frac{1}{2}{\sigma}_{0}^{-2}(\bm{x}-\bm{\mu}_{0})^{\top}(\bm{x}-\bm{\mu}_{0})+\frac{1}{2}{\sigma}_{1}^{-2}(\bm{x}-\bm{\mu}_{1})^{\top}(\bm{x}-\bm{\mu}_{1})\right)$
$\displaystyle=F_{h}\ln{\frac{\sigma_{1}}{\sigma_{0}}}-\frac{F_{h}}{2}+\mathbb{E}_{\bm{x}\sim
P(\bm{x})}\left(\frac{1}{2}{\sigma}_{1}^{-2}(\bm{x}-\bm{\mu}_{1})^{\top}(\bm{x}-\bm{\mu}_{1})\right)$
$\displaystyle=F_{h}\ln{\frac{\sigma_{1}}{\sigma_{0}}}-\frac{F_{h}}{2}+F_{h}\frac{\sigma_{0}^{2}}{2\sigma_{1}^{2}}+\frac{(\bm{\mu}_{0}-\bm{\mu}_{1})^{\top}(\bm{\mu}_{0}-\bm{\mu}_{1})}{2\sigma_{1}^{2}}$
$\displaystyle=F_{h}\ln{\frac{\sigma_{1}}{\sigma_{0}}}-\frac{F_{h}}{2}+F_{h}\frac{\sigma_{0}^{2}}{2\sigma_{1}^{2}}+\frac{d_{X}^{2}}{2\sigma_{1}^{2}}$

where $d_{X}^{2}$ is the squared Euclidean distance. In the same way, we have

$\displaystyle
D_{\text{KL}}(Q||P)=F_{h}\ln{\frac{\sigma_{0}}{\sigma_{1}}}-\frac{F_{h}}{2}+F_{h}\frac{\sigma_{1}^{2}}{2\sigma_{0}^{2}}+\frac{d_{X}^{2}}{2\sigma_{0}^{2}}$

Suppose $\mathbb{P}(\bm{x}\sim P)=\mathbb{P}(\bm{x}\sim Q)=\frac{1}{2}$, then
we have

$\displaystyle D_{\text{NGJ}}(\text{CSBM-H})$
$\displaystyle=-\mathbb{P}(\bm{x}\sim P)\mathbb{E}_{\bm{x}\sim
P}\left[\ln{\frac{P(\bm{x})}{Q(\bm{x})}}\right]-\mathbb{P}(\bm{x}\sim
Q)\mathbb{E}_{\bm{x}\sim Q}\left[\ln{\frac{Q(\bm{x})}{P(\bm{x})}}\right]$
$\displaystyle=-\frac{F_{h}}{4}(\rho^{2}+\frac{1}{\rho^{2}}-2)-d_{X}^{2}(\frac{1}{4\sigma_{1}^{2}}+\frac{1}{4\sigma_{0}^{2}})$

##  Appendix C Calculation of Probabilistic Bayes Error (PBE)

###  C.1 An Introduction

#### Noncentral $\chi^{2}$ distribution

Let $\left(X_{1},X_{2},\dots,X_{i},\ldots,X_{k}\right)$ be $k$ independent,
normally distributed random variables with means $\mu_{i}$ and unit variances.
Then the random variable

$\sum_{i=1}^{k}X_{i}^{2}\sim\chi^{\prime 2}(k,\lambda)$

is distributed according to the noncentral $\chi^{2}$ distribution. It has two
parameters $(k,\lambda)$: $k$ which specifies the number of degrees of freedom
(i.e., the number of $X_{i}$ ), and $\lambda$ which is the sum of the squared
mean of the random variables $X_{i}$:

$\lambda=\sum_{i=1}^{k}\mu_{i}^{2}.$

$\lambda$ is sometimes called the noncentrality parameter.

#### Generalized $\chi^{2}$ distribution

The generalized $\chi^{2}$ variable can be written as a linear sum of
independent noncentral $\chi^{2}$ variables and a normal variable:

$\xi=\sum_{i}w_{i}Y_{i}+X,\quad Y_{i}\sim\chi^{\prime
2}\left(k_{i},\lambda_{i}\right),\quad X\sim N\left(m,s^{2}\right)$

Here the parameters are the weights $w_{i}$, the degrees of freedom $k_{i}$
and non-centralities $\lambda_{i}$ of the constituent $\chi^{2}$, and the
normal parameters $m$ and $s$.

###  C.2 Quadratic Function

For $i\in\mathcal{C}_{0}$, we rewrite
$\bm{x}_{i}=\sigma_{0}\bm{y}_{i}+\bm{\mu}_{0}$ where $\bm{y}_{i}$ is the
standard normal variable. The quadratic function of $Q(\bm{x}_{i})$ satisfies

$\displaystyle Q(\bm{x}_{i})$
$\displaystyle=a\bm{x}_{i}^{\top}\bm{x}_{i}+\bm{b}^{\top}\bm{x}_{i}+c$
$\displaystyle=a\Big{(}\bm{x}_{i}+\frac{\bm{b}}{2a}\Big{)}^{\top}\Big{(}\bm{x}_{i}+\frac{\bm{b}}{2a}\Big{)}+c-\frac{\bm{b}^{\top}\bm{b}}{4a}$
$\displaystyle=a\Big{(}\sigma_{0}\bm{y}_{i}+\bm{\mu}_{0}+\frac{\bm{b}}{2a}\Big{)}^{\top}\Big{(}\sigma_{0}\bm{y}_{i}+\bm{\mu}_{0}+\frac{\bm{b}}{2a}\Big{)}+c-\frac{\bm{b}^{\top}\bm{b}}{4a}$
$\displaystyle=a\sigma_{0}^{2}\Big{(}\bm{y}_{i}+\frac{\bm{\mu}_{0}}{\sigma_{0}}+\frac{\bm{b}}{2a\sigma_{0}}\Big{)}^{\top}\Big{(}\bm{y}_{i}+\frac{\bm{\mu}_{0}}{\sigma_{0}}+\frac{\bm{b}}{2a\sigma_{0}}\Big{)}+c-\frac{\bm{b}^{\top}\bm{b}}{4a}$
$\displaystyle=w_{0}{y}_{i}^{\prime}+c-\frac{\bm{b}^{\top}\bm{b}}{4a}\sim\tilde{\chi}^{2}(w_{0},F_{h},\lambda_{0})+c-\frac{\bm{b}^{\top}\bm{b}}{4a}$

where
${y}_{i}^{\prime}=(\bm{y}_{i}+\frac{\bm{\mu}_{0}}{\sigma_{0}}+\frac{\bm{b}}{2a\sigma_{0}})^{\top}(\bm{y}_{i}+\frac{\bm{\mu}_{0}}{\sigma_{0}}+\frac{\bm{b}}{2a\sigma_{0}})\sim\chi^{\prime
2}(F_{h},\lambda_{0})$ is distributed as non-central $\chi^{2}$ distribution,
the degree of freedom is $F_{h}$,
$\lambda_{0}=(\frac{\bm{\mu}_{0}}{\sigma_{0}}+\frac{\bm{b}}{2a\sigma_{0}})^{\top}(\frac{\bm{\mu}_{0}}{\sigma_{0}}+\frac{\bm{b}}{2a\sigma_{0}})$,
the weight $w_{0}=a\sigma_{0}^{2}$. Then, the cumulative distribution function
(CDF) of $Q(\bm{x}_{i})$ can be calculated as follows,

$\displaystyle\text{CDF}(x)$ $\displaystyle=\mathbb{P}(Q(\bm{x}_{i})\leq
x)=\mathbb{P}(\tilde{\chi}^{2}(w_{0},F_{h},\lambda_{0})\leq
x-c+\frac{\bm{b}^{\top}\bm{b}}{4a})=\text{CDF}_{\tilde{\chi}^{2}(w_{0},F_{h},\lambda_{0})}(x-\xi)$

where $\xi=c-\frac{\bm{b}^{\top}\bm{b}}{4a}$. For $j\in\mathcal{C}_{1}$ and
$\bm{h}_{i},\bm{h}_{j}$, we can apply the same computation. And since

$\displaystyle\mathbb{P}(\text{CL}_{\text{Bayes}}(\bm{x})=0|\bm{x}\in\mathcal{C}_{0})=\mathbb{P}(Q(\bm{x})>0|\bm{x}\in\mathcal{C}_{0})=1-\text{CDF}_{\tilde{\chi}^{2}(w_{0},F_{h},\lambda_{0})}(-\xi),$
$\displaystyle\mathbb{P}(\text{CL}_{\text{Bayes}}(\bm{x})=1|\bm{x}\in\mathcal{C}_{1})=\mathbb{P}(Q(\bm{x})\leq
0|\bm{x}\in\mathcal{C}_{1})=\text{CDF}_{\tilde{\chi}^{2}(w_{1},F_{h},\lambda_{1})}(-\xi).$

where
$w_{1}=a\sigma_{1}^{2},\lambda_{1}=(\frac{\bm{\mu}_{1}}{\sigma_{1}}+\frac{\bm{b}}{2a\sigma_{1}})^{\top}(\frac{\bm{\mu}_{1}}{\sigma_{1}}+\frac{\bm{b}}{2a\sigma_{1}})$.
Then from equation 4 and with $\mathbb{P}(\bm{x}\sim P)=\mathbb{P}(\bm{x}\sim
Q)=1/2$, the PBE for the two normal settings can be calculated 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}$

For a special case where $\sigma_{0}^{2}=\sigma_{1}^{2}\neq 0$, we have $a=0$
and $Q(\bm{x}_{i})=\bm{b}^{\top}\bm{x}_{i}+c$ follows a normal distribution:

$\displaystyle Q(\bm{x}_{i})\sim
N(\bm{b}^{\top}\bm{\mu}_{0}+c,\sigma_{0}^{2}\bm{b}^{\top}\bm{b})$

Then

$\displaystyle\text{CDF}(x)$ $\displaystyle=\mathbb{P}(Q(\bm{x}_{i})\leq
x)=\mathbb{P}(\bm{b}^{\top}\bm{\mu}_{0}+c+\sqrt{\sigma_{0}^{2}\bm{b}^{\top}\bm{b}}x^{\prime}\leq
x)$
$\displaystyle=\mathbb{P}(x^{\prime}\leq\frac{x-(\bm{b}^{\top}\bm{\mu}_{0}+c)}{\sqrt{\sigma_{0}^{2}\bm{b}^{\top}\bm{b}}})$

where $x^{\prime}\sim N(0,1)$ and the PBE becomes

$\frac{\text{CDF}_{N(0,1)}\left(\frac{-(\bm{b}^{\top}\bm{\mu}_{0}+c)}{\sqrt{\sigma_{0}^{2}\bm{b}^{\top}\bm{b}}}\right)+\left(1-\text{CDF}_{N(0,1)}\left(\frac{-(\bm{b}^{\top}\bm{\mu}_{1}+c)}{\sqrt{\sigma_{1}^{2}\bm{b}^{\top}\bm{b}}}\right)\right)}{2}$

##  Appendix D A Discussion of (Imbalanced) Prior Distribution

In this section, we provide an open-ended discussion on how the prior
distribution (i.e., imbalanced datasets) will influence the ND of CSBM-H,
which can possibly lead to some interesting future works.

Let
${\mathbb{P}}(\bm{x}\sim\mathcal{C}_{0})=\frac{n_{0}}{n_{1}+n_{0}}=p_{0},\;{\mathbb{P}}(\bm{x}\sim\mathcal{C}_{1})=\frac{n_{1}}{n_{1}+n_{0}}=p_{1},p_{0}+p_{1}=1$
and $\rho=\frac{\sigma_{0}}{\sigma_{1}}$, which is the ratio of standard
deviation and $0\leq\rho\leq 1$, then $D_{\text{NGJ}}$ is

$\displaystyle D_{\text{NGJ}}(\text{CSBM-H})$
$\displaystyle=-p_{0}D_{\text{KL}}(P||Q)-p_{1}D_{\text{KL}}(Q||P)$
$\displaystyle=F_{h}\ln{\rho}(p_{1}-p_{0})+\frac{F_{h}}{2}(p_{0}\rho^{2}+\frac{p_{1}}{\rho^{2}}-1)+d_{X}^{2}(\frac{p_{0}}{2\sigma_{1}^{2}}+\frac{p_{1}}{2\sigma_{0}^{2}})$

where
$d_{X}^{2}=(\bm{\mu}_{0}-\bm{\mu}_{1})^{\top}(\bm{\mu}_{0}-\bm{\mu}_{1})$,
which is the square Euclidean distance between the means of the two
distributions.

And the PBE of CSBM-H becomes

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

(a) PBE (b) $D_{\text{NGJ}}$

(c) ENND (d) Negative Variance Ratio

Figure 8: Comparison of CSBM-H with $n_{0}=500,n_{1}=100$.

(a) PBE (b) $D_{\text{NGJ}}$

(c) ENND (d) Negative Variance Ratio

Figure 9: Comparison of CSBM-H with $n_{0}=100,n_{1}=500$.

From Figure 8 (b) we can find that, as the size of the low-variation class
increases, the LP regime expands and HP regime shrinks at the low homophily
area in terms of $D_{\text{NGJ}}$. This is because in ENND, the normalization
term $\frac{p_{0}}{2\sigma_{1}^{2}}$ gets higher weight, making the curve for
LP filters move down and HP filter move up, which leads to the expansion of LP
regime.

However, we can also observe that the changes of PBE and $D_{\text{NGJ}}$
curves show inconsistent results. As the size of the low-variation class
increases, the LP regime shrinks and HP regime expands in PBE, while the LP
regime expands and HP regime shrinks in $D_{\text{NGJ}}$. In Figure 9, we
observe the similar inconsistency between PBE and $D_{\text{NGJ}}$ curves.
This discrepancy reminds us that the performance of LP and HP filters on
imbalanced datasets might be under-explored. We do not have a conclusion for
this challenge in this paper and we encourage more researchers to study the
connection among the prior distribution, the performance of LP and HP filters
and ND.

##  Appendix E More About CSBM-H

###  E.1 Directed or Undirected Graphs?

#### Question

Why not generated an undirected graph.

#### Answer

If we impose undirected assumption in CSBM-H, we have to not only discuss the
node degree from intra-class edges, but also discuss degree from inter-class
edges 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, we 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 existing
work mainly keep the discussion within the directed setting [38].

Actually, when CSMB-H was firstly 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 picture of the effect of homophily from 0 to 1, like the
figures in Section 3.4.

###  E.2 Extend CSBM-H to More General Settings

The CSBM-H can be extended to more general settings: 1. The two-normal setting
can be expanded to multi-class classification problems with different sets of
$(\bm{\mu},\sigma^{2}\bm{I},d)$ parameters for each class; 2. The degrees of
nodes can be generalized to different degree distributions; 3. The scalar
homophily parameter $h$ can be generalized to matrix $H\in\mathbb{R}^{C\times
C}$, where $H_{c_{1},c_{2}}$ represents the probability of nodes in class
$\mathcal{C}_{1}$ connecting to nodes in class $\mathcal{C}_{2}$, which is the
compatibility matrix used in [56]. Furthermore, we can also define the local
homophily value $H_{v,c}$ for each node, where $H_{v,c}$ indicates the
proportion of neighbors of $v$ that connect to nodes from class
$\mathcal{C}_{c}$. To demonstrate and visualize the effect of homophily
intuitively and easily, we use the CSBM-H settings in this paper as stated
above. Although the settings are simple, insightful results can still be
obtained. The more complicated variants will be left for future work.

###  E.3 Two More Metrics of ND: Negative Squared Wasserstein Distance and
Hellinger Distance

#### Original Definition

In general, the Wasserstein distance between two Gaussians is
$d=W_{2}\left({N}\left(\bm{\mu}_{0},\Sigma_{0}\right);{N}\left(\bm{\mu_{1}},\Sigma_{1}\right)\right)$
and we have [17, 28, 44, 13]

$d^{2}=\left\|\bm{\mu}_{0}-\bm{\mu}_{1}\right\|_{2}^{2}+\text{Tr}\left(\Sigma_{0}+\Sigma_{1}-2\left(\Sigma_{0}^{1/2}\Sigma_{1}\Sigma_{0}^{1/2}\right)^{1/2}\right)$

The squared Hellinger distance between two Gaussians is [45]

$H^{2}({N}\left(\bm{\mu}_{0},\Sigma_{0}\right);{N}\left(\bm{\mu_{1}},\Sigma_{1}\right))=1-\frac{\text{det}\left(\Sigma_{0}\right)^{1/4}\text{det}\left(\Sigma_{1}\right)^{1/4}}{\text{det}\left(\frac{\Sigma_{0}+\Sigma_{1}}{2}\right)^{1/2}}\exp\left\\{-\frac{1}{8}\left(\bm{\mu}_{0}-\bm{\mu}_{1}\right)^{\top}\left(\frac{\Sigma_{0}+\Sigma_{1}}{2}\right)^{-1}\left(\bm{\mu}_{0}-\bm{\mu}_{1}\right)\right\\}$

Wasserstein distance is a distance function defined between probability
distributions and Hellinger distance is a type of $f$-divergence which is used
to quantify the similarity between two probability distributions [48, 24].
These two metrics can be used to study the ND of CSBM-H and we will introduce
them in the following subsection.

#### Calculation for CSBM-H

The negative squared Wasserstein distance (NSWD) for CSBM-H is

$\displaystyle\text{NSWD}=-\left\|\bm{\mu}_{0}-\bm{\mu}_{1}\right\|_{2}^{2}-F_{h}(\sigma_{0}-\sigma_{1})^{2}$

The negative squared Hellinger distance (NSHD) for CSBM-H is

NSHD
$\displaystyle=-1+\frac{\text{det}\left(\sigma_{0}^{2}I\right)^{1/4}\text{det}\left(\sigma_{1}^{2}I\right)^{1/4}}{\text{det}\left(\frac{\sigma_{0}^{2}I+\sigma_{1}^{2}I}{2}\right)^{1/2}}\exp\left\\{-\frac{1}{8}\left(\bm{\mu}_{0}-\bm{\mu}_{1}\right)^{\top}\left(\frac{\sigma_{0}^{2}+\sigma_{1}^{2}}{2}\right)^{-1}\left(\bm{\mu}_{0}-\bm{\mu}_{1}\right)\right\\}$
$\displaystyle=-1+\frac{\sigma_{0}^{F_{h}/2}\sigma_{1}^{F_{h}/2}}{(\frac{\sigma_{0}^{2}+\sigma_{1}^{2}}{2})^{F_{h}/2}}\exp\left\\{-\frac{1}{8}\left(\bm{\mu}_{0}-\bm{\mu}_{1}\right)^{\top}\left(\frac{\sigma_{0}^{2}+\sigma_{1}^{2}}{2}\right)^{-1}\left(\bm{\mu}_{0}-\bm{\mu}_{1}\right)\right\\}$
$\displaystyle=-1+\left(\frac{2}{\rho^{2}+1/\rho^{2}}\right)^{F_{h}/2}\exp\left\\{-\frac{d_{X}^{2}}{4\left(\sigma_{0}^{2}+\sigma_{1}^{2}\right)}\right\\}$

Although defining the distance in different ways, both NSWD and NSHD indicate
that the ND of CSBM-H depends on both intra- and inter-class ND, which is
consistent with our conclusions in main paper. Besides, NSWD and NSHD provide
analytic expressions for ND, which can be good tools for future research.

##  Appendix F More Figures of CSBM-H

(a) PBE (b) $D_{\text{NGJ}}$

(c) ENND (d) Negative Variance Ratio

Figure 10: Comparison of CSBM-H with $\sigma^{2}_{0}=2.5,\sigma^{2}_{1}=5$.

##  Appendix G Proof of Theorem 2

To prove theorem 2, we need the following two lemmas.

  * Lemma1.

Let $\bm{x}_{i}=X_{i,:}$ and suppose each dimension of $\bm{x}_{i}$ are
independent, then for
$\bm{x}_{i},\bm{h}_{i}=(H_{i,:})^{\top},\bm{h}_{i}^{\text{HP}}=(H_{i,:}^{\text{HP}})^{\top}$
we have

$\displaystyle\mathbb{P}\left(\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|_{2}\geq
t\right)\leq\sum_{k=1}^{F_{h}}\mathbb{P}\left(\left|\mathbf{x}_{i,k}-\mathbf{x}_{j,k}\right|\geq\frac{t}{\sqrt{F_{h}}}\right)$
$\displaystyle\mathbb{P}\left(\left\|\mathbf{h}_{i}-\mathbf{h}_{j}\right\|_{2}\geq
t\right)\leq\sum_{k=1}^{F_{h}}\mathbb{P}\left(\left|\mathbf{h}_{i,k}-\mathbf{h}_{j,k}\right|\geq\frac{t}{\sqrt{F_{h}}}\right)$
$\displaystyle\mathbb{P}\left(\left\|\bm{h}_{i}^{\text{HP}}-\bm{h}_{j}^{\text{HP}}\right\|_{2}\geq
t\right)\leq\sum_{k=1}^{F_{h}}\mathbb{P}\left(\left|\mathbf{h}^{\text{HP}}_{i,k}-\mathbf{h}^{\text{HP}}_{j,k}\right|\geq\frac{t}{\sqrt{F_{h}}}\right)$

###### Proof.

If $\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|_{2}\geq t$, then at least for
one $k\in\\{1,\ldots,F_{h}\\}$, the inequality
$\left|\mathbf{x}_{i,k}-\mathbf{x}_{j,k}\right|\geq\frac{t}{\sqrt{F_{h}}}$
holds. Therefore, we have

$\displaystyle\mathbb{P}\left(\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|_{2}\geq
t\right)$
$\displaystyle\leq\mathbb{P}\left(\bigcup_{k=1}^{F_{h}}\left\\{\left|\mathbf{x}_{i,k}-\mathbf{x}_{j,k}\right|\geq\frac{t}{\sqrt{F_{h}}}\right\\}\right)$
$\displaystyle\leq\sum_{k=1}^{F_{h}}\mathbb{P}\left(\left|\mathbf{x}_{i,k}-\mathbf{x}_{j,k}\right|\geq\frac{t}{\sqrt{F_{h}}}\right)$

The results for $\bm{h}_{i},\bm{h}_{i}^{\text{HP}}$ can be proved by analogy.
∎

  * Lemma2.

(Heoffding Lemma) Let $X$ be any real-valued random variable such that $a\leq
X\leq b$ almost surely, i.e., with probability one. Then, for all
$\lambda\in\mathbb{R}$,

$\mathbb{E}\left[e^{\lambda
X}\right]\leq\exp{\Big{(}}\lambda\mathbb{E}[X]+{\frac{\lambda^{2}(b-a)^{2}}{8}}{\Big{)}}$

###### Proof.

See [40] ∎

  * Theorem2.

For nodes $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

$\displaystyle\mathbb{P}\left(\left\lVert\bm{x}_{i}-\bm{x}_{j}\right\rVert_{2}\geq\left\lVert\bm{x}_{i}-\bm{x}_{v}\right\rVert_{2}+t_{x}\right)\leq
2F_{h}\exp{\left(-\frac{(D_{x}(i,j)-\frac{t_{x}}{\sqrt{F_{h}}})^{2}}{V_{x}(i,j)}\right)},$
(7)
$\displaystyle\mathbb{P}(\left\lVert\bm{h}_{i}-\bm{h}_{j}\right\rVert_{2}\geq\left\lVert\bm{h}_{i}-\bm{h}_{v}\right\rVert_{2}+t_{h})\leq
2F_{h}\exp{\left(-\frac{(D_{h}(i,j)-\frac{t_{h}}{\sqrt{F_{h}}})^{2}}{V_{h}(i,j)}\right)},$
$\displaystyle\mathbb{P}(\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{j}^{\text{HP}}\right\rVert_{2}\geq\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{v}^{\text{HP}}\right\rVert_{2}+t_{\text{HP}})\leq
2F_{h}\exp{\left(-\frac{\left(D_{\text{HP}}(i,j)-\frac{t_{\text{HP}}}{\sqrt{F_{h}}}\right)^{2}}{V_{\text{HP}}(i,j)}\right)},$

where

$\displaystyle
D_{x}(i,j)=\left\lVert\bm{\mu}_{z_{i}}-\bm{\mu}_{z_{j}}\right\rVert_{2},\;V_{x}(i,j)=(b-a)^{2},$
$\displaystyle
D_{h}(i,j)=\left\lVert\tilde{\bm{\mu}}_{z_{i}}-\tilde{\bm{\mu}}_{z_{j}}\right\rVert_{2},V_{h}(i,j)=\left(\frac{1}{2d_{i}}+\frac{1}{2d_{j}}\right)(b-a)^{2},$
$\displaystyle
D_{\text{HP}}(i,j)=\left\lVert\bm{{\mu}}_{z_{i}}-\bm{\tilde{\mu}}_{z_{i}}-\left(\bm{{\mu}}_{z_{j}}-\bm{\tilde{\mu}}_{z_{j}}\right)\right\rVert_{2},$
$\displaystyle
V_{\text{HP}}(i,j)=\left(1+\frac{1}{2d_{i}}+\frac{1}{2d_{j}}\right)(b-a)^{2},$
$\displaystyle\bm{\tilde{\mu}}_{z_{i}}=\sum\limits_{\begin{subarray}{c}v\in\mathcal{N}(i)\end{subarray}}\mathbb{E}_{\begin{subarray}{c}z_{v}\sim\mathcal{D}_{z_{i}},\\\
\mathbf{x}_{v}\sim\mathcal{F}_{z_{v}}\end{subarray}}\left[\frac{1}{d_{i}}\bm{x}_{v}\right].$

The proof of Theorem 2 will be splitted into three parts for
$\bm{x}_{i},\bm{h}_{i}$ and $\bm{h}_{i}^{\text{HP}}$, respectively.

###  G.1 Proof for Original (Full-pass Filtered) Features

###### Proof.

Since we have

$\left\lVert\bm{x}_{i}-\bm{x}_{j}\right\rVert_{2}-\left\lVert\bm{x}_{i}-\bm{x}_{v}\right\rVert_{2}\leq\left\lVert\bm{x}_{i}-\bm{x}_{j}-(\bm{x}_{i}-\bm{x}_{v})\right\rVert_{2}=\left\lVert\bm{x}_{v}-\bm{x}_{j}\right\rVert_{2}$

then

$\displaystyle\mathbb{P}$
$\displaystyle\left(\left\lVert\bm{x}_{i}-\bm{x}_{j}\right\rVert_{2}\geq\left\lVert\bm{x}_{i}-\bm{x}_{v}\right\rVert_{2}+t_{x}\right)=\mathbb{P}\left(\left\lVert\bm{x}_{i}-\bm{x}_{j}\right\rVert_{2}-\left\lVert\bm{x}_{i}-\bm{x}_{v}\right\rVert_{2}\geq
t_{x}\right)$
$\displaystyle\leq\mathbb{P}\left(\left\lVert\bm{x}_{i}-\bm{x}_{j}-(\bm{x}_{i}-\bm{x}_{v})\right\rVert_{2}\geq
t_{x}\right)=\mathbb{P}\left(\left\lVert\bm{x}_{v}-\bm{x}_{j})\right\rVert_{2}\geq
t_{x}\right)$

We will calculate the upper bound of
$\mathbb{P}\left(\left\lVert\bm{x}_{v}-\bm{x}_{j}\right\rVert_{2}\geq
t_{x}\right)$ in the following part. To do this, we first compute the upper
bound of $\mathbb{P}\left(\bm{x}_{v,k}-\bm{x}_{j,k}\geq t\right)$. For
$t\geq\left\lVert\bm{{\mu}}_{z_{v}}-\bm{{\mu}}_{z_{j}}\right\rVert$ and any
$s\geq 0$, we have

$\displaystyle\ \ \mathbb{P}\left(\bm{{x}}_{v,k}-\bm{{x}}_{j,k}\geq
t\right)=\mathbb{P}\left(\exp{\left(s(\bm{{x}}_{v,k}-\bm{{x}}_{j,k})\right)}\geq\exp{\left(st\right)}\right)$
$\displaystyle\leq$
$\displaystyle\exp{\left(-st\right)}\mathbb{E}\left[\exp{\left(s(\bm{{x}}_{v,k}-\bm{{x}}_{j,k})\right)}\right]\;(\text{Markov
Inequality})$ $\displaystyle=$
$\displaystyle\exp{\left(-st\right)}\mathbb{E}\left[\exp{\left(s\bm{x}_{v,k}\right)}\right]\mathbb{E}\left[\exp{\left(-s\bm{x}_{j,k}\right)}\right]\;(\text{Independency})$
$\displaystyle\leq$
$\displaystyle\exp{\left(-st\right)}\exp{\left(s\mathbb{E}\left[\bm{x}_{v,k}\right]+\frac{(b-a)^{2}s^{2}}{8}\right)}\times\exp{\left(-s\mathbb{E}\left[\bm{x}_{j,k}\right]+\frac{(b-a)^{2}s^{2}}{8}\right)}\;(\text{Hoeffding's
lemma})$ $\displaystyle=$
$\displaystyle\exp{\left(\frac{(b-a)^{2}}{4}s^{2}+(\bm{{\mu}}_{z_{v},k}-\bm{{\mu}}_{z_{j},k}-t)s\right)}$
$\displaystyle\leq$
$\displaystyle\exp{\left(\frac{(b-a)^{2}}{4}s^{2}+(\left|\bm{{\mu}}_{z_{v},k}-\bm{{\mu}}_{z_{j},k}\right|-t)s\right)}$

Since
$t\geq\left\lVert\bm{{\mu}}_{z_{v}}-\bm{{\mu}}_{z_{j}}\right\rVert\geq\left|\bm{{\mu}}_{z_{v},k}-\bm{{\mu}}_{z_{j},k}\right|$
for any $k$, so when
$s=-\frac{(\left|\bm{{\mu}}_{z_{v},k}-\bm{{\mu}}_{z_{j},k}\right|-t)}{\frac{(b-a)^{2}}{2}}\geq
0$, we get the tightest bound of the above inequality and

$\exp{\left(-\frac{(\left|\bm{{\mu}}_{z_{v},k}-\bm{{\mu}}_{z_{j},k}\right|-t)^{2}}{(b-a)^{2}}\right)}\leq\exp{\left(-\frac{(\left\lVert{\bm{\mu}}_{z_{v}}-{\bm{\mu}}_{z_{j}}\right\rVert_{2}-t)^{2}}{(b-a)^{2}}\right)}$

With the same steps, we have

$\mathbb{P}\left(\bm{{x}}_{v,k}-\bm{{x}}_{j,k}\leq-t\right)=\mathbb{P}\left(\bm{{x}}_{j,k}-\bm{{x}}_{v,k}\geq
t\right)\leq\exp{\left(-\frac{(\left\lVert{\bm{\mu}}_{z_{v}}-{\bm{\mu}}_{z_{j}}\right\rVert_{2}-t)^{2}}{(b-a)^{2}}\right)}$

Combined together we have

$\mathbb{P}\left(\big{|}\bm{{x}}_{v,k}-\bm{{x}}_{j,k}\big{|}\geq t\right)\leq
2\exp{\left(-\frac{(\left\lVert{\bm{\mu}}_{z_{v}}-{\bm{\mu}}_{z_{j}}\right\rVert_{2}-t)^{2}}{(b-a)^{2}}\right)}$

Since
$\frac{t_{x}}{\sqrt{F_{h}}}\geq\left\lVert\bm{{\mu}}_{z_{v}}-\bm{{\mu}}_{z_{j}}\right\rVert$,
then from Lemma 1 we have

$\displaystyle\mathbb{P}\left(\left\lVert\bm{{x}}_{v}-\bm{{x}}_{j}\right\rVert_{2}\geq
t_{x}\right)\leq\sum_{k=1}^{F_{h}}\mathbb{P}\left(\left|\mathbf{x}_{v,k}-\mathbf{x}_{j,k}\right|\geq\frac{t_{x}}{\sqrt{F_{h}}}\right)\leq
2F_{h}\exp{\left(-\frac{(\left\lVert{\bm{\mu}}_{z_{v}}-{\bm{\mu}}_{z_{j}}\right\rVert_{2}-\frac{t_{x}}{\sqrt{F_{h}}})^{2}}{(b-a)^{2}}\right)}$
(8)

∎

###  G.2 Proof for Low-pass Filter

###### Proof.

Part for LP filter:

Let
$\bm{{h}}_{i,k}=\frac{1}{d_{i}}\sum\limits_{\begin{subarray}{c}u\in\mathcal{N}(i),\\\
z_{u}\sim\mathcal{D}_{z_{i}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u},k}\end{subarray}}\bm{x}_{u,k}$ and
$\bm{\tilde{\mu}}_{z_{i},k}=\mathbb{E}\left[\bm{{h}}_{i,k}\right]=\mathbb{E}\left[\frac{1}{d_{i}}\sum\mathbf{x}_{u,k}\right]$.
Since we have

$\left\lVert\bm{h}_{i}-\bm{h}_{j}\right\rVert_{2}-\left\lVert\bm{h}_{i}-\bm{h}_{v}\right\rVert_{2}\leq\left\lVert\bm{h}_{i}-\bm{h}_{j}-(\bm{h}_{i}-\bm{h}_{v})\right\rVert_{2}=\left\lVert\bm{h}_{v}-\bm{h}_{j}\right\rVert_{2}$

then

$\displaystyle\mathbb{P}$
$\displaystyle\left(\left\lVert\bm{h}_{i}-\bm{h}_{j}\right\rVert_{2}\geq\left\lVert\bm{h}_{i}-\bm{h}_{v}\right\rVert_{2}+t_{h}\right)=\mathbb{P}\left(\left\lVert\bm{h}_{i}-\bm{h}_{j}\right\rVert_{2}-\left\lVert\bm{h}_{i}-\bm{h}_{v}\right\rVert_{2}\geq
t_{h}\right)$
$\displaystyle\leq\mathbb{P}\left(\left\lVert\bm{h}_{i}-\bm{h}_{j}-(\bm{h}_{i}-\bm{h}_{v})\right\rVert_{2}\geq
t_{h}\right)=\mathbb{P}\left(\left\lVert\bm{h}_{v}-\bm{h}_{j})\right\rVert_{2}\geq
t_{h}\right)$

We will calculate the upper bound of
$\mathbb{P}\left(\left\lVert\bm{h}_{v}-\bm{h}_{j}\right\rVert_{2}\geq
t_{h}\right)$ in the following part. To do this, we first compute the upper
bound of $\mathbb{P}\left(\bm{h}_{v,k}-\bm{h}_{j,k}\geq t\right)$. For
$t\geq\left\lVert\bm{\tilde{\mu}}_{z_{v}}-\bm{\tilde{\mu}}_{z_{j}}\right\rVert$
and any $s\geq 0$, we have

$\displaystyle\ \ \mathbb{P}\left(\bm{{h}}_{v,k}-\bm{{h}}_{j,k}\geq
t\right)=\mathbb{P}\left(\exp{\left(s(\bm{{h}}_{v,k}-\bm{{h}}_{j,k})\right)}\geq\exp{\left(st\right)}\right)$
$\displaystyle\leq$
$\displaystyle\exp{\left(-st\right)}\mathbb{E}\left[\exp{\left(s(\bm{{h}}_{v,k}-\bm{{h}}_{j,k})\right)}\right]\;(\text{Markov
Inequality})$ $\displaystyle=$
$\displaystyle\exp{\left(-st\right)}\mathbb{E}\left[\exp{\left(\frac{s}{d_{v}}\sum\limits_{\begin{subarray}{c}u\in\mathcal{N}(v),\\\
z_{u}\sim\mathcal{D}_{z_{v}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u},k}\end{subarray}}\bm{x}_{u,k}\right)}\right]\mathbb{E}\left[\exp{\left(\frac{-s}{d_{j}}\sum\limits_{\begin{subarray}{c}u\in\mathcal{N}(j),\\\
z_{u}\sim\mathcal{D}_{z_{j}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u},k}\end{subarray}}\bm{x}_{u,k}\right)}\right]\;(\text{Independency})$
$\displaystyle=$
$\displaystyle\exp{\left(-st\right)}\prod\limits_{\begin{subarray}{c}u\in\mathcal{N}(v),\\\
z_{u}\sim\mathcal{D}_{z_{v}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u},k}\end{subarray}}\mathbb{E}\left[\exp{\left(\frac{s}{d_{v}}\bm{x}_{u,k}\right)}\right]\prod\limits_{\begin{subarray}{c}u\in\mathcal{N}(j),\\\
z_{u}\sim\mathcal{D}_{z_{j}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u},k}\end{subarray}}\mathbb{E}\left[\exp{\left(\frac{-s}{d_{j}}\bm{x}_{u,k}\right)}\right]\;(\text{Independency})$
$\displaystyle\leq$
$\displaystyle\exp{\left(-st\right)}\prod\limits_{\begin{subarray}{c}u\in\mathcal{N}(v),\\\
z_{u}\sim\mathcal{D}_{z_{v}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u},k}\end{subarray}}\exp{\left(\frac{s}{d_{v}}\mathbb{E}\left[\bm{x}_{u,k}\right]+\frac{(b-a)^{2}s^{2}}{8d_{v}^{2}}\right)}$
$\displaystyle\ \
\times\prod\limits_{\begin{subarray}{c}u\in\mathcal{N}(j),\\\
z_{u}\sim\mathcal{D}_{z_{j}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u,k}}\end{subarray}}\exp{\left(\frac{-s}{d_{j}}\mathbb{E}\left[\bm{x}_{u,k}\right]+\frac{(b-a)^{2}s^{2}}{8d_{j}^{2}}\right)}\;(\text{Hoeffding's
lemma})$ $\displaystyle=$
$\displaystyle\exp{\left(-st\right)}\exp{\left(\frac{(b-a)^{2}s^{2}}{8d_{v}}\right)}\exp{\left(s\mathbb{E}\left[\frac{1}{d_{v}}\sum\limits_{\begin{subarray}{c}u\in\mathcal{N}(v),\\\
z_{u}\sim\mathcal{D}_{z_{v}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u},k}\end{subarray}}\bm{x}_{u,k}\right]\right)}$
$\displaystyle\ \
\times\exp{\left(\frac{(b-a)^{2}s^{2}}{8d_{j}}\right)}\exp{\left(-s\mathbb{E}\left[\frac{1}{d_{j}}\sum\limits_{\begin{subarray}{c}u\in\mathcal{N}(j),\\\
z_{u}\sim\mathcal{D}_{z_{j}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u},k}\end{subarray}}\bm{x}_{u,k}\right]\right)}\;$
$\displaystyle=$
$\displaystyle\exp{\left(\Big{(}\frac{(b-a)^{2}}{8d_{v}}+\frac{(b-a)^{2}}{8d_{j}}\Big{)}s^{2}+(\bm{\tilde{\mu}}_{z_{v},k}-\bm{\tilde{\mu}}_{z_{j},k}-t)s\right)}$
$\displaystyle\leq$
$\displaystyle\exp{\left(\Big{(}\frac{(b-a)^{2}}{8d_{v}}+\frac{(b-a)^{2}}{8d_{j}}\Big{)}s^{2}+(\left|\bm{\tilde{\mu}}_{z_{v},k}-\bm{\tilde{\mu}}_{z_{j},k}\right|-t)s\right)}$

Since
$t\geq\left\lVert\bm{\tilde{\mu}}_{z_{v}}-\bm{\tilde{\mu}}_{z_{j}}\right\rVert\geq\left|\bm{\tilde{\mu}}_{z_{v},k}-\bm{\tilde{\mu}}_{z_{j},k}\right|$
for any $k$, so when
$s=-\frac{(\left|\bm{\tilde{\mu}}_{z_{v},k}-\bm{\tilde{\mu}}_{z_{j},k}\right|-t)}{\frac{(b-a)^{2}}{4d_{v}}+\frac{(b-a)^{2}}{4d_{j}}}\geq
0$, we get the tightest bound of the above inequality and

$\exp{\left(-\frac{(\left|\bm{\tilde{\mu}}_{z_{v},k}-\bm{\tilde{\mu}}_{z_{j},k}\right|-t)^{2}}{\frac{(b-a)^{2}}{2d_{v}}+\frac{(b-a)^{2}}{2d_{j}}}\right)}\leq\exp{\left(-\frac{(\left\lVert\tilde{\bm{\mu}}_{z_{v}}-\tilde{\bm{\mu}}_{z_{j}}\right\rVert_{2}-t)^{2}}{\frac{(b-a)^{2}}{2d_{v}}+\frac{(b-a)^{2}}{2d_{j}}}\right)}$

With the same steps, we have

$\mathbb{P}\left(\bm{{h}}_{v,k}-\bm{{h}}_{j,k}\leq-t\right)=\mathbb{P}\left(\bm{{h}}_{j,k}-\bm{{h}}_{v,k}\geq
t\right)\leq\exp{\left(-\frac{(\left\lVert\tilde{\bm{\mu}}_{z_{v}}-\tilde{\bm{\mu}}_{z_{j}}\right\rVert_{2}-t)^{2}}{\frac{(b-a)^{2}}{2d_{v}}+\frac{(b-a)^{2}}{2d_{j}}}\right)}$

Combined together we have

$\mathbb{P}\left(\big{|}\bm{{h}}_{v,k}-\bm{{h}}_{j,k}\big{|}\geq t\right)\leq
2\exp{\left(-\frac{(\left\lVert\tilde{\bm{\mu}}_{z_{v}}-\tilde{\bm{\mu}}_{z_{j}}\right\rVert_{2}-t)^{2}}{\frac{(b-a)^{2}}{2d_{v}}+\frac{(b-a)^{2}}{2d_{j}}}\right)}$

Since
$\frac{t_{h}}{\sqrt{F_{h}}}\geq\left\lVert\bm{\tilde{\mu}}_{z_{v}}-\bm{\tilde{\mu}}_{z_{j}}\right\rVert$,
then from Lemma 1 we have

$\displaystyle\mathbb{P}\left(\left\lVert\bm{{h}}_{v}-\bm{{h}}_{j}\right\rVert_{2}\geq
t_{h}\right)\leq\sum_{k=1}^{F_{h}}\mathbb{P}\left(\left|\mathbf{h}_{v,k}-\mathbf{h}_{j,k}\right|\geq\frac{t_{h}}{\sqrt{F_{h}}}\right)\leq
2F_{h}\exp{\left(-\frac{(\left\lVert\tilde{\bm{\mu}}_{z_{v}}-\tilde{\bm{\mu}}_{z_{j}}\right\rVert_{2}-\frac{t_{h}}{\sqrt{F_{h}}})^{2}}{\frac{(b-a)^{2}}{2d_{v}}+\frac{(b-a)^{2}}{2d_{j}}}\right)}$
(9)

∎

###  G.3 Theoretical Results for High-pass Filter

###### Proof.

The proof for HP filter is similar to that of LP filter.

Let $\bm{{h}}_{i}^{\text{HP}}=\bm{x}_{i}-\bm{{h}}_{i}$, which is the HP
filtered signal. Since we have

$\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{j}^{\text{HP}}\right\rVert_{2}-\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{v}^{\text{HP}}\right\rVert_{2}\leq\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{j}^{\text{HP}}-(\bm{h}_{i}^{\text{HP}}-\bm{h}_{v}^{\text{HP}})\right\rVert_{2}=\left\lVert\bm{h}_{v}^{\text{HP}}-\bm{h}_{j}^{\text{HP}}\right\rVert_{2}$

then

$\displaystyle\mathbb{P}$
$\displaystyle\left(\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{j}^{\text{HP}}\right\rVert_{2}\geq\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{v}^{\text{HP}}\right\rVert_{2}+t_{\text{HP}}\right)=\mathbb{P}\left(\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{j}^{\text{HP}}\right\rVert_{2}-\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{v}^{\text{HP}}\right\rVert_{2}\geq
t_{\text{HP}}\right)$
$\displaystyle\leq\mathbb{P}\left(\left\lVert\bm{h}_{i}^{\text{HP}}-\bm{h}_{j}^{\text{HP}}-(\bm{h}_{i}^{\text{HP}}-\bm{h}_{v}^{\text{HP}})\right\rVert_{2}\geq
t_{\text{HP}}\right)=\mathbb{P}\left(\left\lVert\bm{h}_{v}^{\text{HP}}-\bm{h}_{j}^{\text{HP}})\right\rVert_{2}\geq
t_{\text{HP}}\right)$

We will calculate the upper bound of
$\mathbb{P}\left(\left\lVert\bm{h}_{v}^{\text{HP}}-\bm{h}_{j}^{\text{HP}}\right\rVert_{2}\geq
t\right)$ in the following part. To do this, we first compute the upper bound
of $\mathbb{P}\left(\bm{h}_{v,k}^{\text{HP}}-\bm{h}_{j,k}^{\text{HP}}\geq
t\right)$.

For
$t\geq\left\lVert\bm{{\mu}}_{v}-\bm{\tilde{\mu}}_{v}-\left(\bm{{\mu}}_{j}-\bm{\tilde{\mu}}_{j}\right)\right\rVert_{2}$
and $s\geq 0$, we have

$\displaystyle\mathbb{P}\left(\bm{{h}}_{v,k}^{\text{HP}}-\bm{{h}}_{j,k}^{\text{HP}}\geq
t\right)=\mathbb{P}\left(\bm{x}_{v,k}-\bm{{h}}_{v,k}-\bm{x}_{j,k}+\bm{{h}}_{j,k}\geq
t\right)$
$\displaystyle=\mathbb{P}\left(\exp{\left(s(\bm{x}_{v,k}-\bm{{h}}_{v,k}-\bm{x}_{j,k}+\bm{{h}}_{j,k})\right)}\geq\exp{\left(st\right)}\right)$
$\displaystyle\leq\exp{\left(-st\right)}\mathbb{E}\left[\exp{\left(s(\bm{x}_{v,k}-\bm{{h}}_{v,k}-\bm{x}_{j,k}+\bm{{h}}_{j,k})\right)}\right]\;(\text{Markov
Inequality})$
$\displaystyle=\exp{\left(-st\right)}\times\mathbb{E}\left[\exp{\left(s\bm{x}_{v,k}\right)}\right]\times\mathbb{E}\left[\exp{\left(-s\bm{x}_{j,k}\right)}\right]\times$
$\displaystyle\mathbb{E}\left[\exp{\left(-\frac{s}{d_{v}}\sum\limits_{\begin{subarray}{c}u\in\mathcal{N}(v),\\\
z_{u}\sim\mathcal{D}_{z_{v}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u},k}\end{subarray}}\bm{x}_{u,k}\right)}\right]\mathbb{E}\left[\exp{\left(\frac{s}{d_{j}}\sum\limits_{\begin{subarray}{c}u\in\mathcal{N}(j),\\\
z_{u}\sim\mathcal{D}_{z_{j}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u,k}}\end{subarray}}\bm{x}_{u,k}\right)}\right]\;(\text{Independency})$
$\displaystyle\leq\exp{\left(-st\right)}\mathbb{E}\left[\exp{\left(s\bm{x}_{v,k}\right)}\right]\mathbb{E}\left[\exp{\left(-s\bm{x}_{j,k}\right)}\right]$
$\displaystyle\prod\limits_{\begin{subarray}{c}u\in\mathcal{N}(v),\\\
z_{u}\sim\mathcal{D}_{z_{v}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u},k}\end{subarray}}\mathbb{E}\left[\exp{\left(\frac{-s}{d_{v}}\bm{x}_{u,k}\right)}\right]\prod\limits_{\begin{subarray}{c}u\in\mathcal{N}(j),\\\
z_{u}\sim\mathcal{D}_{z_{j}},\\\
\mathbf{x}_{u,k}\sim\mathcal{F}_{z_{u,k}}\end{subarray}}\mathbb{E}\left[\exp{\left(\frac{s}{d_{j}}\bm{x}_{u,k}\right)}\right]$
$\displaystyle\leq\exp{\left(-st\right)}\exp{\left(s\bm{{\mu}}_{v,k}+\frac{(b-a)^{2}s^{2}}{8}\right)}\exp{\left(-s\bm{{\mu}}_{j,k}+\frac{(b-a)^{2}s^{2}}{8}\right)}$
$\displaystyle\prod\exp{\left(\frac{-s}{d_{v}}\mathbb{E}[\bm{x}_{u,k}]+\frac{(b-a)^{2}s^{2}}{8d_{v}^{2}}\right)}\prod\exp{\left(\frac{s}{d_{j}}\mathbb{E}[\bm{x}_{u,k}]+\frac{(b-a)^{2}s^{2}}{8d_{j}^{2}}\right)}\;(\text{Hoeffding's
lemma})$
$\displaystyle=\exp{\left((\frac{(b-a)^{2}}{4}+\frac{(b-a)^{2}}{8d_{v}}+\frac{(b-a)^{2}}{8d_{j}})s^{2}+\left(\bm{{\mu}}_{v,k}-\bm{{\mu}}_{j,k}-\left(\bm{\tilde{\mu}}_{v,k}-\bm{\tilde{\mu}}_{j,k}\right)-t\right)s\right)}$
$\displaystyle\leq\exp{\left((\frac{(b-a)^{2}}{4}+\frac{(b-a)^{2}}{8d_{v}}+\frac{(b-a)^{2}}{8d_{j}})s^{2}+\left(\left|\bm{{\mu}}_{v,k}-\bm{{\mu}}_{j,k}-\left(\bm{\tilde{\mu}}_{v,k}-\bm{\tilde{\mu}}_{j,k}\right)\right|-t\right)s\right)}$

Since
$t\geq\left\lVert\bm{{\mu}}_{v}-\bm{\tilde{\mu}}_{v}-\left(\bm{{\mu}}_{j}-\bm{\tilde{\mu}}_{j}\right)\right\rVert_{2}$,
then when
$s=-\frac{\left|\bm{{\mu}}_{v,k}-\bm{{\mu}}_{j,k}-\left(\bm{\tilde{\mu}}_{v,k}-\bm{\tilde{\mu}}_{j,k}\right)\right|-t}{(\frac{(b-a)^{2}}{2}+\frac{(b-a)^{2}}{4d_{v}}+\frac{(b-a)^{2}}{4d_{j}})}>0$,
we get the tightest bound and

$\exp{\left(-\frac{\left(\left|\bm{{\mu}}_{v,k}-\bm{{\mu}}_{j,k}-\left(\bm{\tilde{\mu}}_{v,k}-\bm{\tilde{\mu}}_{j,k}\right)\right|-t\right)^{2}}{(1+\frac{1}{2d_{v}}+\frac{1}{2d_{j}})(b-a)^{2}}\right)}\leq\exp{\left(-\frac{\left(\left\lVert\bm{{\mu}}_{v}-\bm{\tilde{\mu}}_{v}-\left(\bm{{\mu}}_{j}-\bm{\tilde{\mu}}_{j}\right)\right\rVert_{2}-t\right)^{2}}{(1+\frac{1}{2d_{v}}+\frac{1}{2d_{j}})(b-a)^{2}}\right)}$

Then

$\mathbb{P}\left(\big{|}\bm{{h}}_{v,k}^{\text{HP}}-\bm{{h}}_{j,k}^{\text{HP}}\big{|}\geq
t\right)\leq
2\exp{\left(-\frac{\left(\left\lVert\bm{{\mu}}_{v}-\bm{\tilde{\mu}}_{v}-\left(\bm{{\mu}}_{j}-\bm{\tilde{\mu}}_{j}\right)\right\rVert_{2}-t\right)^{2}}{(1+\frac{1}{2d_{v}}+\frac{1}{2d_{j}})(b-a)^{2}}\right)}$

Since
$\frac{t_{\text{HP}}}{\sqrt{F_{h}}}\geq\left\lVert\bm{{\mu}}_{v}-\bm{\tilde{\mu}}_{v}-\left(\bm{{\mu}}_{j}-\bm{\tilde{\mu}}_{j}\right)\right\rVert_{2}$,
then from Lemma 1, we have

$\displaystyle\mathbb{P}\left(\left\lVert\bm{{h}}_{v}^{\text{HP}}-\bm{{h}}_{j}^{\text{HP}}\right\rVert_{2}\geq
t_{\text{HP}}\right)$
$\displaystyle\leq\sum_{k=1}^{F_{h}}\mathbb{P}\left(\left|\mathbf{h}_{v,k}^{\text{HP}}-\mathbf{h}_{j,k}^{\text{HP}}\right|\geq\frac{t_{\text{HP}}}{\sqrt{F_{h}}}\right)$
(10) $\displaystyle\leq
2F_{h}\exp{\Bigg{(}-\frac{\left(\left\lVert\bm{{\mu}}_{v}-\bm{\tilde{\mu}}_{v}-\left(\bm{{\mu}}_{j}-\bm{\tilde{\mu}}_{j}\right)\right\rVert_{2}-\frac{t_{\text{HP}}}{\sqrt{F_{h}}}\right)^{2}}{(1+\frac{1}{2d_{v}}+\frac{1}{2d_{j}})(b-a)^{2}}\Bigg{)}}$

$\left\lVert\bm{{\mu}}_{v}-\bm{\tilde{\mu}}_{v}-\left(\bm{{\mu}}_{j}-\bm{\tilde{\mu}}_{j}\right)\right\rVert_{2}$
is essentially the relative center movement.

∎

##  Appendix H Detailed Discussion of Performance Metrics and More
Experimental Results

###  H.1 Hypothesis Testing of ACM-GNNs vs. GNNs

To more comprehensively validate if "intra-class embedding distance is smaller
than the inter-class embedding distance" closely correlates to the superiority
of a given model versus another model, we choose the SOTA model ACM-GNNs and
conduct the following hypothesis testing of ACM-GNNs [35] versus GNNs and ACM-
GNNs versus MLPs. From the results in table 3 we can see that the above
statements hold except in ACM-SGC-1 vs. SGC-1 on Squirrel and ACM-GCN vs. GCN
on CiteSeer. This again verifies that the relationship between intra- and
inter-class embedding distance strongly relates to the model performance.

Table 3: Hypothesis testing results of ACM-GNNs v.s. GNNs: The cells marked by
orange are the cases that the p-values significantly indicate the opposite
direction as the trained results (ground truth).

|  | Cornell | Wisconsin | Texas | Film | Chameleon | Squirrel | Cora | CiteSeer | PubMed
---|---|---|---|---|---|---|---|---|---|---
| p-value | 1.00 | 1.00 | 1.00 | 1.00 | 0.19 | 1.00 | 1.00 | 1.00 | 1.00
ACM-SGC-1 | ACC ACM-SGC-1 | 93.77 $\pm$ 1.91 | 93.25 $\pm$ 2.92 | 93.61 $\pm$ 1.55 | 39.33 $\pm$ 1.25 | 63.68 $\pm$ 1.62 | 46.4 $\pm$ 1.13 | 86.63 $\pm$ 1.13 | 80.96 $\pm$ 0.93 | 87.75 $\pm$ 0.88
v.s. SGC-1 | ACC SGC-1 | 70.98 $\pm$ 8.39 | 70.38 $\pm$ 2.85 | 83.28 $\pm$ 5.43 | 25.26 $\pm$ 1.18 | 64.86 $\pm$ 1.81 | 47.62 $\pm$ 1.27 | 85.12 $\pm$ 1.64 | 79.66 $\pm$ 0.75 | 85.5 $\pm$ 0.76
| Diff Acc | 22.79 | 22.87 | 10.33 | 14.07 | -1.18 | -1.22 | 1.51 | 1.30 | 2.25
| p-value | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.41 | 0.00 | 1.00
ACM-GCN | ACC ACM-GCN | 94.75 $\pm$ 3.8 | 95.75 $\pm$ 2.03 | 94.92 $\pm$ 2.88 | 41.62 $\pm$ 1.15 | 69.04 $\pm$ 1.74 | 58.02 $\pm$ 1.86 | 88.62 $\pm$ 1.22 | 81.68 $\pm$ 0.97 | 90.66 $\pm$ 0.47
v.s. GCN | ACC GCN | 82.46 $\pm$ 3.11 | 75.5 $\pm$ 2.92 | 83.11 $\pm$ 3.2 | 35.51 $\pm$ 0.99 | 64.18 $\pm$ 2.62 | 44.76 $\pm$ 1.39 | 87.78 $\pm$ 0.96 | 81.39 $\pm$ 1.23 | 88.9 $\pm$ 0.32
| Diff Acc | 12.29 | 20.25 | 11.81 | 6.11 | 4.86 | 13.26 | 0.84 | 0.29 | 1.76
| p-value | 0.10 | 0.00 | 0.50 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.42
ACM-SGC-1 | ACC ACM-SGC-1 | 93.77 $\pm$ 1.91 | 93.25 $\pm$ 2.92 | 93.61 $\pm$ 1.55 | 39.33 $\pm$ 1.25 | 63.68 $\pm$ 1.62 | 46.4 $\pm$ 1.13 | 86.63 $\pm$ 1.13 | 80.96 $\pm$ 0.93 | 87.75 $\pm$ 0.88
v.s. MLP-1 | ACC MLP-1 | 93.77 $\pm$ 3.34 | 93.87 $\pm$ 3.33 | 93.77 $\pm$ 3.34 | 34.53 $\pm$ 1.48 | 45.01 $\pm$ 1.58 | 29.17 $\pm$ 1.46 | 74.3 $\pm$ 1.27 | 75.51 $\pm$ 1.35 | 86.23 $\pm$ 0.54
| Diff Acc | 0.00 | -0.62 | -0.16 | 4.80 | 18.67 | 17.23 | 12.33 | 5.45 | 1.52
| p-value | 0.94 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00
ACM-GCN | ACC ACM-GCN | 94.75 $\pm$ 3.8 | 95.75 $\pm$ 2.03 | 94.92 $\pm$ 2.88 | 41.62 $\pm$ 1.15 | 69.04 $\pm$ 1.74 | 58.02 $\pm$ 1.86 | 88.62 $\pm$ 1.22 | 81.68 $\pm$ 0.97 | 90.66 $\pm$ 0.47
v.s. MLP-2 | ACC MLP-2 | 91.30 $\pm$ 0.70 | 93.87 $\pm$ 3.33 | 92.26 $\pm$ 0.71 | 38.58 $\pm$ 0.25 | 46.72 $\pm$ 0.46 | 31.28 $\pm$ 0.27 | 76.44 $\pm$ 0.30 | 76.25 $\pm$ 0.28 | 86.43 $\pm$ 0.13
| Diff Acc | 3.45 | 1.88 | 2.66 | 3.04 | 22.32 | 26.74 | 12.18 | 5.43 | 4.23

###  H.2 Implementation Details of KR and GNB

Classifier-based performance metrics: we measure the quality of aggregated
features based on the performance of a "training-free" classifier. In this
paper, we take use of kernel regression and naive Bayes classifiers.

#### Kernel Regression

Kernel method utilizes a pairwise similarity function
$K(\bm{x}_{i},\bm{x}_{j})$ to measure how closely related two node embeddings
are, without the need for any training process [29, 22, 43]. A higher value of
$K(\bm{x}_{i},\bm{x}_{j})$ indicates a smaller distance between the embeddings
of nodes $\bm{x}_{i}$ and $\bm{x}_{j}$ and vice versa.

Algorithm 1 Pseudo code for kernel regression

$X,\hat{A},Z,N,N_{S},N_{\text{epochs}}$ $\triangleright$ $N$ is the number of
nodes, $N_{S}$ is the number of samples

for $i$ in $N_{\text{epochs}}$ do

$S\leftarrow\text{sample}(N,N_{S})$

Get $K_{S}^{X},K_{S}^{H},Z_{S}$ $\triangleright$ $K_{S}^{X},K_{S}^{H}$ are the
kernels for $X$ and $H$ for the sampled nodes

$S_{\text{train}},S_{\text{test}}\leftarrow\text{sample}(S,0.6N_{S},0.4N_{S})$

$f_{K}^{X}\leftarrow\left(K_{S}^{X}[S_{\text{test}},:][:,S_{\text{train}}]\right)\left(K_{S}^{X}[S_{\text{train}},:][:,S_{\text{train}}]\right)^{-1}Z_{S}[S_{\text{train}},:]$

$f_{K}^{H}\leftarrow\left(K_{S}^{H}[S_{\text{test}},:][:,S_{\text{train}}]\right)\left(K_{S}^{H}[S_{\text{train}},:][:,S_{\text{train}}]\right)^{-1}Z_{S}[S_{\text{train}},:]$

Compute
$\text{ACC}^{X}_{i},\text{ACC}^{H}_{i}\leftarrow\text{Accuracy}(f_{K}^{X},Z_{S}[S_{\text{test}},:]),\
\text{Accuracy}(f_{K}^{H},Z_{S}[S_{\text{test}},:]$)

end for

$\text{p-value}\leftarrow\text{ttest}(\text{ACC}^{X},\text{ACC}^{H})$

To capture the feature-based non-linear node similarity, we use Neural Network
Gaussian Process (NNGP) [30, 2, 16, 41]. Specifically, we consider the
activation function $\phi(x)=\text{ReLU}(x)$ and have

$\displaystyle
K_{\text{NL}}(\bm{x}_{i},\bm{x}_{j})=\frac{1}{2\pi}\left(\bm{x}_{i}^{\top}\bm{x}_{j}\left(\pi-\tilde{\phi}\left(\frac{\bm{x}_{i}^{\top}\bm{x}_{j}}{\|\bm{x}_{i}\|_{2}\|\bm{x}_{j}\|_{2}}\right)\right)+\sqrt{\|\bm{x}_{i}\|_{2}^{2}\|\bm{x}_{j}\|_{2}^{2}-\left(\bm{x}_{i}^{\top}\bm{x}_{j}\right)^{2}}\right)$

where $\tilde{\phi}({x})=\arccos({x})$ is the dual activation function of
ReLU. 131313Note that when $\phi({x})=\exp{(i{x})}$, we have
$K(\bm{x}_{i},\bm{x}_{j})=\exp{(-\frac{1}{2}\left\lVert\bm{x}_{i}-\bm{x}_{j}\right\rVert_{2}^{2})}$,
which is closely related to the Euclidean distance of node embeddings tested
in section 4.1, further emphasizing the strong relationship between embedding
distances and kernel similarities.

Furthermore, we observe that there exist some datasets where linear G-aware
models do not have the same performance disparities compared to their coupled
G-agnostic models as non-linear G-aware models, e.g., as the results on PubMed
shown in table 1, SGC-1 underperforms MLPs while GCN outperforms MLP-2. This
implies that relying on a single non-linear metric to assess whether G-aware
models will surpass their coupled G-agnostic models is not enough, we need a
linear metric as well. Thus, we choose the following linear kernel (inner
product) for regression

$\displaystyle
K_{\text{L}}(\bm{x}_{i},\bm{x}_{j})=\frac{\bm{x}_{i}^{\top}\bm{x}_{j}}{\|\bm{x}_{i}\|_{2}\|\bm{x}_{j}\|_{2}}$

.

For Gaussian Naïve Bayes (GNB), we just use the features and aggregated
features of the sampled training nodes to fit two separate classifiers and get
the predicted accuracy for the test nodes. Note that Gaussian Naïve Bayes is
just a linear classifier.

#### Threshold Values

Typically, the threshold for homophily and heterophily graphs is set at 0.5
[57, 55, 54, 35] . 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.

  * •

Statistical Significant Threshold 0.05 (SST0.05): Instead of offering an
ambiguous statistical interpretation, SST0.05 will offer 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.

We show the results of $\text{KR}_{\text{L}},\text{KR}_{\text{NL}}$ and GNB in
section H.3 . Cells marked by grey are errors according to NT0.5 and results
marked by red are incorrect according to SST 0.05. The comparisons with the
existing homophily metrics are shown in section H.4. We can see that, no
matter on small- (table 4 6) or large-scale (table 5 7) datasets, the
classifier-based performance metrics (CPMs) are significantly better than the
existing homophily metrics on revealing the advantages and disadvantages of
GNNs, decreasing the overall error rate from at least 0.34 to 0.13 (table 8).
The running time of CPM is short (table 9), only taking several minutes
1414141 NVIDIA V100 GPU with 16G memory, 8-core CPU with 16G memory even on
large-scale datasets such as pokec and snap-patents, which contains millons of
nodes and tens of millions of edges [32].

###  H.3 Results on Small-scale and Large-scale Datasets

Table 4: Comparison on small datasets

|  | Cornell | Wisconsin | Texas | Film | Chameleon | Squirrel | Cora | CiteSeer | PubMed
---|---|---|---|---|---|---|---|---|---|---
| $\text{H}_{\text{edge}}$ | 0.5669 | 0.4480 | 0.4106 | 0.3750 | 0.2795 | 0.2416 | 0.8100 | 0.7362 | 0.8024
| $\text{H}_{\text{node}}$ | 0.3855 | 0.1498 | 0.0968 | 0.2210 | 0.2470 | 0.2156 | 0.8252 | 0.7175 | 0.7924
Baseline | $\text{H}_{\text{class}}$ | 0.0468 | 0.0941 | 0.0013 | 0.0110 | 0.0620 | 0.0254 | 0.7657 | 0.6270 | 0.6641
Homophily | $\text{H}_{\text{agg}}$ | 0.8032 | 0.7768 | 0.6940 | 0.6822 | 0.61 | 0.3566 | 0.9904 | 0.9826 | 0.9432
Metrics | $\text{H}_{\text{GE}}$ | 0.31 | 0.34 | 0.35 | 0.16 | 0.0152 | 0.0157 | 0.1700 | 0.1900 | 0.27
| $\text{H}_{\text{adj}}$ | 0.1889 | 0.0826 | 0.0258 | 0.1272 | 0.0663 | 0.0196 | 0.8178 | 0.7588 | 0.7431
| LI | 0.0169 | 0.1311 | 0.1923 | 0.0002 | 0.048 | 0.0015 | 0.5904 | 0.4508 | 0.4093
Classifier-based | $\text{KR}_{\text{L}}$ | 1.39 | 0.00 | 0.00 | 0.7834 | 1.00 | 1.00 | 1.00 | 1.00 | 0.8026
Performance Metrics | GNB | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.0000
| ACC SGC | 70.98 $\pm$ 8.39 | 70.38 $\pm$ 2.85 | 83.28 $\pm$ 5.43 | 25.26 $\pm$ 1.18 | 64.86 $\pm$ 1.81 | 47.62 $\pm$ 1.27 | 85.12 $\pm$ 1.64 | 79.66 $\pm$ 0.75 | 85.5 $\pm$ 0.76
SGC v.s. MLP1 | ACC MLP-1 | 93.77 $\pm$ 3.34 | 93.87 $\pm$ 3.33 | 93.77 $\pm$ 3.34 | 34.53 $\pm$ 1.48 | 45.01 $\pm$ 1.58 | 29.17 $\pm$ 1.46 | 74.3 $\pm$ 1.27 | 75.51 $\pm$ 1.35 | 86.23 $\pm$ 0.54
| Diff Acc | -22.79 | -23.49 | -10.49 | -9.27 | 19.85 | 18.45 | 10.82 | 4.15 | -0.73
| $\text{H}_{\text{edge}}$ | 0.5669 | 0.4480 | 0.4106 | 0.3750 | 0.2795 | 0.2416 | 0.8100 | 0.7362 | 0.8024
| $\text{H}_{\text{node}}$ | 0.3855 | 0.1498 | 0.0968 | 0.2210 | 0.2470 | 0.2156 | 0.8252 | 0.7175 | 0.7924
Baseline | $\text{H}_{\text{class}}$ | 0.0468 | 0.0941 | 0.0013 | 0.0110 | 0.0620 | 0.0254 | 0.7657 | 0.6270 | 0.6641
Homophily | $\text{H}_{\text{agg}}$ | 0.8032 | 0.7768 | 0.6940 | 0.6822 | 0.61 | 0.3566 | 0.9904 | 0.9826 | 0.9432
Metrics | $\text{H}_{\text{GE}}$ | 0.31 | 0.34 | 0.35 | 0.16 | 0.0152 | 0.0157 | 0.1700 | 0.1900 | 0.2700
| $\text{H}_{\text{adj}}$ | 0.1889 | 0.0826 | 0.0258 | 0.1272 | 0.0663 | 0.0196 | 0.8178 | 0.7588 | 0.7431
| LI | 0.0169 | 0.1311 | 0.1923 | 0.0002 | 0.048 | 0.0015 | 0.5904 | 0.4508 | 0.4093
Classifier-based | $\text{KR}_{\text{NL}}$ | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00
Performance Metrics | GNB | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00
| ACC GCN | 82.46 $\pm$ 3.11 | 75.5 $\pm$ 2.92 | 83.11 $\pm$ 3.2 | 35.51 $\pm$ 0.99 | 64.18 $\pm$ 2.62 | 44.76 $\pm$ 1.39 | 87.78 $\pm$ 0.96 | 81.39 $\pm$ 1.23 | 88.9 $\pm$ 0.32
GCN v.s. MLP2 | ACC MLP-2 | 91.30 $\pm$ 0.70 | 93.87 $\pm$ 3.33 | 92.26 $\pm$ 0.71 | 38.58 $\pm$ 0.25 | 46.72 $\pm$ 0.46 | 31.28 $\pm$ 0.27 | 76.44 $\pm$ 0.30 | 76.25 $\pm$ 0.28 | 86.43 $\pm$ 0.13
| Diff Acc | -8.84 | -18.37 | -9.15 | -3.07 | 17.46 | 13.48 | 11.34 | 5.14 | 2.47

Table 5: Comparison on large-scale datasets

|  | Penn94 | pokec | arXiv-year | snap-patents | genius | twitch-gamers | Deezer-Europe
---|---|---|---|---|---|---|---|---
| $\text{H}_{\text{edge}}$ | 0.4700 | 0.4450 | 0.2220 | 0.0730 | 0.6180 | 0.5450 | 0.5250
| $\text{H}_{\text{node}}$ | 0.4828 | 0.4283 | 0.2893 | 0.2206 | 0.5087 | 0.5564 | 0.5299
Baseline | $\text{H}_{\text{class}}$ | 0.0460 | 0.0000 | 0.2720 | 0.1000 | 0.0800 | 0.0900 | 0.0300
Homophily | $\text{H}_{\text{agg}}$ | 0.2712 | 0.0807 | 0.7066 | 0.6170 | 0.7823 | 0.4172 | 0.5580
Metrics | $\text{H}_{\text{GE}}$ | 0.3734 | 0.9222 | 0.8388 | 0.6064 | 0.6655 | 0.2865 | 0.0378
| $\text{H}_{\text{adj}}$ | 0.0366 | -0.1132 | 0.0729 | 0.0907 | 0.1432 | 0.1010 | 0.1586
| LI | 0.0851 | 0.0172 | 0.0407 | 0.0243 | 0.0025 | 0.0058 | 0.0007
Classifier-based | $\text{KR}_{\text{L}}$ | 0.00 | 0.03 | 0.98 | 0.19 | 0.00 | 0.25 | 0.00
Performance Metrics | GBN | 0.00 | 0.00 | 1.00 | 1.00 | 0.00 | 1.00 | 0.00
| ACC SGC | 67.06 $\pm$ 0.19 | 52.88 $\pm$ 0.64 | 35.58 $\pm$ 0.22 | 29.65 $\pm$ 0.04 | 82.31 $\pm$ 0.45 | 57.9 $\pm$ 0.18 | 61.63 $\pm$ 0.25
SGC vs MLP1 | ACC MLP-1 | 73.72 $\pm$ 0.5 | 59.89 $\pm$ 0.11 | 34.11 $\pm$ 0.17 | 30.59 $\pm$ 0.02 | 86.48 $\pm$ 0.11 | 59.45 $\pm$ 0.16 | 63.14 $\pm$ 0.41
| Diff Acc | -6.66 | -7.01 | 1.47 | -0.94 | -4.17 | -1.55 | -1.51
| $\text{H}_{\text{edge}}$ | 0.4700 | 0.4450 | 0.2220 | 0.0730 | 0.6180 | 0.5450 | 0.5250
| $\text{H}_{\text{node}}$ | 0.4828 | 0.4283 | 0.2893 | 0.2206 | 0.5087 | 0.5564 | 0.5299
Baseline | $\text{H}_{\text{class}}$ | 0.0460 | 0.0000 | 0.2720 | 0.1000 | 0.0800 | 0.0900 | 0.0300
Homophily | $\text{H}_{\text{agg}}$ | 0.2712 | 0.0807 | 0.7066 | 0.6170 | 0.7823 | 0.4172 | 0.5580
Metrics | $\text{H}_{\text{GE}}$ | 0.3734 | 0.9222 | 0.8388 | 0.6064 | 0.6655 | 0.2865 | 0.0378
| $\text{H}_{\text{adj}}$ | 0.0366 | -0.1132 | 0.0729 | 0.0907 | 0.1432 | 0.1010 | 0.1586
| LI | 0.0851 | 0.0172 | 0.0407 | 0.0243 | 0.0025 | 0.0058 | 0.0007
Classifier-based | $\text{KR}_{\text{NL}}$ | 0.00 | 0.57 | 1.00 | 0.4083 | 0.00 | 1.00 | 0.00
Performance Metrics | GNB | 0.00 | 0.00 | 1.00 | 1.00 | 0.00 | 1.00 | 0.00
| ACC GCN | 82.08 $\pm$ 0.31 | 70.3 $\pm$ 0.1 | 40 $\pm$ 0.26 | 35.8 $\pm$ 0.05 | 83.26 $\pm$ 0.14 | 62.33 $\pm$ 0.23 | 60.16 $\pm$ 0.51
GCN vs MLP2 | ACC MLP-2 | 74.68 $\pm$ 0.28 | 62.13 $\pm$ 0.1 | 36.36 $\pm$ 0.23 | 31.43 $\pm$ 0.04 | 86.62 $\pm$ 0.08 | 60.9 $\pm$ 0.11 | 64.25 $\pm$ 0.41
| Diff Acc | 7.40 | 8.17 | 3.64 | 4.37 | -3.36 | 1.43 | -4.09

###  H.4 Statistics and Comparisons

#### Discrepancy Between Linear and Non-linear Models

From the experimental results on large-scale datasets reported in Table 5, 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, on Penn94, pokec, snap-patents and twitch-gamers, SGC-1
underperforms MLP-1 but GCN outperforms MLP-2. In fact, PubMed in Table 4 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 special subset of heterophilic graphs, we should develop
theoretical analysis to discuss the interplay between graph structure and
feature non-linearity, and how they affect node distinguishability together.

The current homophily values (including the proposed metrics) are not able to
explain the phenomenon associated with this group of datasets. We keep it as
an open question and encourage people from the GNN community to study it in
the future.

Table 6: Statistics on small-scale datasets | Total Error | Error Rate
---|---|---
$\text{H}_{\text{edge}}$ | 7 | 0.39
$\text{H}_{\text{node}}$ | 5 | 0.28
$\text{H}_{\text{class}}$ | 5 | 0.28
$\text{H}_{\text{agg}}$ | 11 | 0.61
$\text{H}_{\text{GE}}$ | 9 | 0.50
$\text{H}_{\text{adj}}$ | 5 | 0.28
LI | 7 | 0.39
KR (NT0.5) | 2 | 0.11
KR (SST0.05) | 1 | 0.06
GNB (NT0.5) | 1 | 0.06
GNB (SST0.05) | 1 | 0.06
Table 7: Statistics on large-scale datasets | Total Error | Error Rate
---|---|---
$\text{H}_{\text{edge}}$ | 9 | 0.64
$\text{H}_{\text{node}}$ | 9 | 0.64
$\text{H}_{\text{class}}$ | 6 | 0.43
$\text{H}_{\text{agg}}$ | 8 | 0.57
$\text{H}_{\text{GE}}$ | 6 | 0.43
$\text{H}_{\text{adj}}$ | 6 | 0.43
LI | 6 | 0.43
KR (NT0.5) | 2 | 0.14
KR (SST0.05) | 5 | 0.36
GNB (NT0.5) | 4 | 0.29
GNB (SST0.05) | 4 | 0.29
Table 8: Overall statistics on small- and large-scale datasets | Total Error | Error Rate
---|---|---
$\text{H}_{\text{edge}}$ | 16 | 0.50
$\text{H}_{\text{node}}$ | 14 | 0.44
$\text{H}_{\text{class}}$ | 11 | 0.34
$\text{H}_{\text{agg}}$ | 19 | 0.59
$\text{H}_{\text{GE}}$ | 15 | 0.47
$\text{H}_{\text{adj}}$ | 11 | 0.34
LI | 13 | 0.41
KR (NT0.5) | 4 | 0.13
KR (SST0.05) | 6 | 0.19
GNB (NT0.5) | 5 | 0.16
GNB (SST0.05) | 5 | 0.16
Table 9: Total running time (seconds/100 samples) of $\text{KR}_{\text{L}}$, $\text{KR}_{\text{NL}}$ and GNB | $\text{KR}_{\text{L}}$ | $\text{KR}_{\text{NL}}$ | GNB
---|---|---|---
Cornell | 0.58 | 0.67 | 1.39
Wisconsin | 0.78 | 0.87 | 1.72
Texas | 0.59 | 0.67 | 1.41
Film | 5.29 | 5.41 | 2.72
Chameleon | 3.97 | 3.95 | 3.81
Squirrel | 5.39 | 5.36 | 4.15
Cora | 3.94 | 4.10 | 3.08
CiteSeer | 4.85 | 5.05 | 6.55
PubMed | 9.35 | 9.41 | 5.27
Penn94 | 18.57 | 18.68 | 12.43
pokec | 84.47 | 86.08 | 50.03
arXiv-year | 7.77 | 7.82 | 4.56
snap-patents | 304.06 | 296.21 | 163.84
genius | 8.20 | 8.12 | 5.30
twitch-gamers | 9.34 | 9.24 | 4.17
Deezer-Europe | 37.41 | 39.49 | 59.84

###  H.5 Results for Symmetric Renormalized Affinity Matrix

To evaluate if the benefits of classifier-based performance metrics can be
maintained for different aggregation operators, we replace the random walk
renormalized affinity matrix with synmmetric renormalized affinity matrix in
SGC-1, GCN, $\text{KR}_{\text{L}},\text{KR}_{\text{NL}}$ and GNB and report
the results and comparisons as belows.

It is observed that the superiority holds on both small- (table 10, 12) and
large-scale datasets (table 11, 13), reducing the overall error rate from at
least 0.31 to 0.13 (table 14).

Table 10: Results for symmetric renormalized affinity matrix on small-scale
datasets

|  | Cornell | Wisconsin | Texas | Film | Chameleon | Squirrel | Cora | CiteSeer | PubMed
---|---|---|---|---|---|---|---|---|---|---
| $\text{H}_{\text{edge}}$ | 0.5669 | 0.4480 | 0.4106 | 0.3750 | 0.2795 | 0.2416 | 0.8100 | 0.7362 | 0.8024
| $\text{H}_{\text{node}}$ | 0.3855 | 0.1498 | 0.0968 | 0.2210 | 0.2470 | 0.2156 | 0.8252 | 0.7175 | 0.7924
Baseline | $\text{H}_{\text{class}}$ | 0.0468 | 0.0941 | 0.0013 | 0.0110 | 0.0620 | 0.0254 | 0.7657 | 0.6270 | 0.6641
Homophily | $\text{H}_{\text{agg}}$ | 0.8032 | 0.7768 | 0.6940 | 0.6822 | 0.61 | 0.3566 | 0.9904 | 0.9826 | 0.9432
Metrics | $\text{H}_{\text{GE}}$ | 0.31 | 0.34 | 0.35 | 0.16 | 0.0152 | 0.0157 | 0.1700 | 0.1900 | 0.2700
| $\text{H}_{\text{adj}}$ | 0.1889 | 0.0826 | 0.0258 | 0.1272 | 0.0663 | 0.0196 | 0.8178 | 0.7588 | 0.7431
| LI | 0.0169 | 0.1311 | 0.1923 | 0.0002 | 0.048 | 0.0015 | 0.5904 | 0.4508 | 0.4093
Classifier-based | $\text{KR}_{\text{L}}$ | 0.00 | 0.00 | 0.00 | 0.9304 | 1.00 | 1.00 | 1.00 | 1.00 | 0.0003
Performance Metrics | GNB | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00
| ACC SGC | 51.64 $\pm$ 12.27 | 39.63 $\pm$ 5.39 | 30.82 $\pm$ 4.96 | 27.02 $\pm$ 1 | 63.26 $\pm$ 1.98 | 46.03 $\pm$ 1.74 | 84.38 $\pm$ 1.5 | 79.51 $\pm$ 1.04 | 87.24 $\pm$ 0.44
SGC vs MLP1 | ACC MLP-1 | 93.77 $\pm$ 3.34 | 93.87 $\pm$ 3.33 | 93.77 $\pm$ 3.34 | 34.53 $\pm$ 1.48 | 45.01 $\pm$ 1.58 | 29.17 $\pm$ 1.46 | 74.3 $\pm$ 1.27 | 75.51 $\pm$ 1.35 | 86.23 $\pm$ 0.54
| Diff Acc | -42.13 | -54.24 | -62.95 | -7.51 | 18.25 | 16.86 | 10.08 | 4.00 | 1.01
| $\text{H}_{\text{edge}}$ | 0.5669 | 0.4480 | 0.4106 | 0.3750 | 0.2795 | 0.2416 | 0.8100 | 0.7362 | 0.8024
| $\text{H}_{\text{node}}$ | 0.3855 | 0.1498 | 0.0968 | 0.2210 | 0.2470 | 0.2156 | 0.8252 | 0.7175 | 0.7924
Baseline | $\text{H}_{\text{class}}$ | 0.0468 | 0.0941 | 0.0013 | 0.0110 | 0.0620 | 0.0254 | 0.7657 | 0.6270 | 0.6641
Homophily | $\text{H}_{\text{agg}}$ | 0.8032 | 0.7768 | 0.6940 | 0.6822 | 0.61 | 0.3566 | 0.9904 | 0.9826 | 0.9432
Metrics | $\text{H}_{\text{GE}}$ | 0.31 | 0.34 | 0.35 | 0.16 | 0.0152 | 0.0157 | 0.1700 | 0.1900 | 0.2700
| $\text{H}_{\text{adj}}$ | 0.1889 | 0.0826 | 0.0258 | 0.1272 | 0.0663 | 0.0196 | 0.8178 | 0.7588 | 0.7431
| LI | 0.0169 | 0.1311 | 0.1923 | 0.0002 | 0.048 | 0.0015 | 0.5904 | 0.4508 | 0.4093
Classifier-based | $\text{KR}_{\text{NL}}$ | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.98
Performance Metrics | GNB | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00
| ACC GCN | 82.62 $\pm$ 3.04 | 70.38 $\pm$ 3.16 | 82.46 $\pm$ 2.94 | 35.79 $\pm$ 1.09 | 68.95 $\pm$ 1.09 | 52.98 $\pm$ 0.85 | 87.87 $\pm$ 0.99 | 81.79 $\pm$ 1.09 | 89.47 $\pm$ 0.27
GCN vs MLP2 | ACC MLP-2 | 91.30 $\pm$ 0.70 | 93.87 $\pm$ 3.33 | 92.26 $\pm$ 0.71 | 38.58 $\pm$ 0.25 | 46.72 $\pm$ 0.46 | 31.28 $\pm$ 0.27 | 76.44 $\pm$ 0.30 | 76.25 $\pm$ 0.28 | 86.43 $\pm$ 0.13
| Diff Acc | -8.68 | -23.49 | -9.80 | -2.79 | 22.23 | 21.70 | 11.43 | 5.54 | 3.04

Table 11: Results for symmetric renormalized affinity matrix on large-scale
datasets

|  | Penn94 | pokec | arXiv-year | snap-patents | genius | twitch-gamers | Deezer-Europe
---|---|---|---|---|---|---|---|---
| $\text{H}_{\text{edge}}$ | 0.4700 | 0.4450 | 0.2220 | 0.0730 | 0.6180 | 0.5450 | 0.5250
| $\text{H}_{\text{node}}$ | 0.4828 | 0.4283 | 0.2893 | 0.2206 | 0.5087 | 0.5564 | 0.5299
Baseline | $\text{H}_{\text{class}}$ | 0.0460 | 0.0000 | 0.2720 | 0.1000 | 0.0800 | 0.0900 | 0.0300
Homophily | $\text{H}_{\text{agg}}$ | 0.2712 | 0.0807 | 0.7066 | 0.6170 | 0.7823 | 0.4172 | 0.5580
Metrics | $\text{H}_{\text{GE}}$ | 0.3734 | 0.9222 | 0.8388 | 0.6064 | 0.6655 | 0.2865 | 0.0378
| $\text{H}_{\text{adj}}$ | 0.0366 | -0.1132 | 0.0729 | 0.0907 | 0.1432 | 0.1010 | 0.1586
| LI | 0.0851 | 0.0172 | 0.0407 | 0.0243 | 0.0025 | 0.0058 | 0.0007
Classifier-based | $\text{KR}_{\text{L}}$ | 0.00 | 0.02 | 0.32 | 0.46 | 0.00 | 0.01 | 0.00
Performance Metrics | GNB | 0.00 | 0.03 | 1.00 | 1.00 | 0.00 | 0.97 | 0.00
| ACC SGC | 64.63 $\pm$ 0.15 | 51.97 $\pm$ 0.38 | 35.24 $\pm$ 0.14 | 30.32 $\pm$ 0.05 | 81.66 $\pm$ 0.58 | 58.77 $\pm$ 0.18 | 60.2 $\pm$ 0.47
SGC vs MLP1 | ACC MLP-1 | 73.72 $\pm$ 0.5 | 59.89 $\pm$ 0.11 | 34.11 $\pm$ 0.17 | 30.59 $\pm$ 0.02 | 86.48 $\pm$ 0.11 | 59.45 $\pm$ 0.16 | 63.14 $\pm$ 0.41
| Diff Acc | -9.09 | -7.92 | 1.13 | -0.27 | -4.82 | -0.68 | -2.94
| $\text{H}_{\text{edge}}$ | 0.4700 | 0.4450 | 0.2220 | 0.0730 | 0.6180 | 0.5450 | 0.5250
| $\text{H}_{\text{node}}$ | 0.4828 | 0.4283 | 0.2893 | 0.2206 | 0.5087 | 0.5564 | 0.5299
Baseline | $\text{H}_{\text{class}}$ | 0.0460 | 0.0000 | 0.2720 | 0.1000 | 0.0800 | 0.0900 | 0.0300
Homophily | $\text{H}_{\text{agg}}$ | 0.2712 | 0.0807 | 0.7066 | 0.6170 | 0.7823 | 0.4172 | 0.5580
Metrics | $\text{H}_{\text{GE}}$ | 0.3734 | 0.9222 | 0.8388 | 0.6064 | 0.6655 | 0.2865 | 0.0378
| $\text{H}_{\text{adj}}$ | 0.0366 | -0.1132 | 0.0729 | 0.0907 | 0.1432 | 0.1010 | 0.1586
| LI | 0.0851 | 0.0172 | 0.0407 | 0.0243 | 0.0025 | 0.0058 | 0.0007
Classifier-based | $\text{KR}_{\text{NL}}$ | 0.00 | 0.32 | 0.99 | 0.99 | 0.00 | 1.00 | 0.00
Performance Metrics | GNB | 0.00 | 0.29 | 1.00 | 1.00 | 0.00 | 0.97 | 0.00
| ACC GCN | 81.45 $\pm$ 0.29 | 69.55 $\pm$ 0.1 | 40.02 $\pm$ 0.19 | 35.4 $\pm$ 0.04 | 83.02 $\pm$ 0.14 | 62.59 $\pm$ 0.14 | 62.32 $\pm$ 0.44
GCN vs MLP2 | ACC MLP-2 | 74.68 $\pm$ 0.28 | 62.13 $\pm$ 0.1 | 36.36 $\pm$ 0.23 | 31.43 $\pm$ 0.04 | 86.62 $\pm$ 0.08 | 60.9 $\pm$ 0.11 | 64.25 $\pm$ 0.41
| Diff Acc | 6.77 | 7.42 | 3.66 | 3.97 | -3.60 | 1.69 | -1.93

Table 12: Statistics for symmetric renormalized affinity matrix on small-scale datasets | Total Error | Error Rate
---|---|---
$\text{H}_{\text{edge}}$ | 6 | 0.33
$\text{H}_{\text{node}}$ | 4 | 0.22
$\text{H}_{\text{class}}$ | 4 | 0.22
$\text{H}_{\text{agg}}$ | 10 | 0.56
$\text{H}_{\text{GE}}$ | 10 | 0.56
$\text{H}_{\text{adj}}$ | 4 | 0.22
LI | 8 | 0.44
KR (NT0.5) | 2 | 0.11
KR (SST0.05) | 2 | 0.11
GNB (NT0.5) | 0 | 0.00
GNB (SST0.05) | 0 | 0.00
Table 13: Statistics for symmetric renormalized affinity matrix on large-scale datasets | Total Error | Error Rate
---|---|---
$\text{H}_{\text{edge}}$ | 10 | 0.71
$\text{H}_{\text{node}}$ | 10 | 0.71
$\text{H}_{\text{class}}$ | 6 | 0.43
$\text{H}_{\text{agg}}$ | 8 | 0.57
$\text{H}_{\text{GE}}$ | 6 | 0.43
$\text{H}_{\text{adj}}$ | 6 | 0.43
LI | 6 | 0.43
KR (NT0.5) | 3 | 0.21
KR (SST0.05) | 4 | 0.29
GNB (NT0.5) | 4 | 0.29
GNB (SST0.05) | 4 | 0.29
Table 14: Overall statistics for symmetric renormalized affinity matrix on small- and large-scale datasets | Total Error | Error Rate
---|---|---
$\text{H}_{\text{edge}}$ | 16 | 0.50
$\text{H}_{\text{node}}$ | 14 | 0.44
$\text{H}_{\text{class}}$ | 10 | 0.31
$\text{H}_{\text{agg}}$ | 18 | 0.56
$\text{H}_{\text{GE}}$ | 16 | 0.50
$\text{H}_{\text{adj}}$ | 10 | 0.31
LI | 14 | 0.44
$\text{KR}_{\text{NNGP}}$ (NT0.5) | 5 | 0.16
$\text{KR}_{\text{NNGP}}$ (SST0.05) | 6 | 0.19
GNB (NT0.5) | 4 | 0.13
GNB (SST0.05) | 4 | 0.13

###  H.6 Experiments on Synthetic Graphs

To comprehensively investigate and corroborate the correlation between CPMs
and the performance of G-aware models versus their corresponding G-agnostic
models across the entire spectrum of homophily levels, we conduct experiments
with the synthetic graphs. The data generation process is similar to [35].

#### Data Generation & Experimental Setup

We generated a total of $280$ graphs with 28 different levels of edge
homophily, ranging from 0.005 to 0.95, and generated 10 graphs for each
homophily level. Each graph consisted of 5 classes, with 400 nodes in each
class. For nodes in each class, we randomly generated 4000 intra-class edges
and [$\frac{4000}{H_{\text{edge}}(\mathcal{G})}-4000$] inter-class edges, and
assigned features to the nodes using the Cora, CiteSeer, PubMed, Chameleon,
Squirrel, Film datasets. We then randomly split the nodes into
train/validation/test sets in a 60%/20%/20% ratio. We trained GCN, SGC-1,
MLP-2, and MLP-1 models on the synthetic graphs with fine-tuned
hyperparameters as [35]. For each edge homophily level
$H_{\text{edge}}(\mathcal{G})$, we computed the average test accuracy of the 4
models, as well as $\text{KR}_{\text{L}},\text{KR}_{\text{NL}}$ and other
homophily metrics. The comparisons of $\text{KR}_{\text{L}}$,
$\text{KR}_{\text{NL}}$ and the performance of GCN vs. MLP-2, SGC-1 vs. MLP-1
according to edge homophily were shown in Figure 11.

It can be observed in Figure 11 that the points where $\text{KR}_{\text{L}}$
intersects NT0.5 or SST0.05 (green) and the intersections of SGC-1 and MLP-1
performance (red) are perfectly matched and the curve of
$\text{KR}_{\text{L}}$ share the similar U-shape as SGC-1, so do
$\text{KR}_{\text{NL}}$ curve (blue) and GCN and MLP-2 performance curves
(black) 151515We only draw the vertical dot lines for the intersection of
$\text{KR}_{\text{L}}$ and NT0.5 in order to keep the figures clear. The
corresponding x-values for other intersections can be observed from the
figures.. This indicates that the advantages and disadvantages of G-aware
models over G-agnostic models can be better revealed by CPMs at different
homophily levels than the baseline homophily metrics shown in Figure 12.

In Figure 12, we can see that the curves of node homophily (orange), class
homophily (pink), generalized edge homophily (yellow) and adjusted homophily
(blue) are almost linear increasing, which does not reflect the U-shaped
performance curve of GNNs’ performance. Although the curves for aggregation
homophily (purple) and label informativeness (grey) have a rebound in low
homophily area, they are unable to provide a suitable threshold value and
fails to capture the intersection points.

Since the values of CPMs are either (very close to) 0 or (very close to) 1 and
there do not exist enough intermediate values between 0 and 1, we do not plot
the relationship between GNNs performance and CPMs as Figure 2 in [35].

(a) Cora

(b) CiteSeer

(c) PubMed

(d) Chameleon

(e) Squirrel

(f) Film

Figure 11: Results and comparisons of $\text{KR}_{\text{L}}$ and
$\text{KR}_{\text{NL}}$ on synthetic graphs

(a) Cora (b) CiteSeer

(c) PubMed (d) Chameleon

(e) Squirrel (f) Film

Figure 12: Results on Synthetic Graphs