# New Benchmarks for Learning on Non-Homophilous Graphs

Derek Lim<EMAIL_ADDRESS>0000-0001-8408-9484 Cornell UniversityUSA ,
Xiuyu Li<EMAIL_ADDRESS>Cornell UniversityUSA ,  Felix Hohne
<EMAIL_ADDRESS>Cornell UniversityUSA and  Ser-Nam Lim<EMAIL_ADDRESS>Facebook AIUSA

(2021)

###### Abstract.

Much data with graph structures satisfy the principle of homophily, meaning
that connected nodes tend to be similar with respect to a specific attribute.
As such, ubiquitous datasets for graph machine learning tasks have generally
been highly homophilous, rewarding methods that leverage homophily as an
inductive bias. Recent work has pointed out this particular focus, as new non-
homophilous datasets have been introduced and graph representation learning
models better suited for low-homophily settings have been developed. However,
these datasets are small and poorly suited to truly testing the effectiveness
of new methods in non-homophilous settings. We present a series of improved
graph datasets with node label relationships that do not satisfy the homophily
principle. Along with this, we introduce a new measure of the presence or
absence of homophily that is better suited than existing measures in different
regimes. We benchmark a range of simple methods and graph neural networks
across our proposed datasets, drawing new insights for further research. Data
and codes can be found at https://github.com/CUAI/Non-Homophily-Benchmarks.

datasets, graphs, neural networks, homophily

††copyright: rightsretained††journalyear: 2021††conference: WWW ’21: The Web
Conference; April 19–23, 2021; Ljubljana, Slovenia.††booktitle: Workshop on
Graph Learning Benchmarks, WWW ’21, April 19–23, 2021, Ljubljana,
Slovenia.††submissionid:

##  1\. Introduction

Various types of real-world data have natural graph structures, in which
objects (nodes) and relationships (edges) are encoded as a graph $G$. As a
result, numerous types of models have been developed for machine learning
tasks on graph data. Much recent work in graph representation learning
(Hamilton, 2020) has focused on using both node features and graph structure,
especially in the general family of graph neural network (GNN) models.

To generate predictions, graph learning methods can leverage complex inductive
biases relating to the topology of the graph (Battaglia et al., 2018). One
common property of real-world graphs that is often leveraged as a strong
inductive bias is homophily, which means that connected nodes tend to be
similar in certain attributes (McPherson et al., 2001; Altenburger and
Ugander, 2018). Here, we refer to a graph as homophilous if connected nodes
are much more likely to have the same class label than if edges were
independent of labels. In a non-homophilous graph, connected nodes are not
significantly more likely to have the same class label, and may even be less
likely to have the same class label than if edges were independent of labels.
For instance, nodes may have little to no preference for connecting to any
particular class in aggregate (e.g. in friendship networks where the classes
represent gender (Laniado et al., 2016; Altenburger and Ugander, 2018)); or,
nodes of a certain class may only be connected to a subset of the other
classes (e.g. in citation networks where class labels are the year of
publication of a paper).

Many GNNs explicitly assume homophily in their construction, and even those
models that do not may perform poorly in non-homophilous graph settings (Zhu
et al., 2020b; Jia and Benson, 2020). While some GNNs have been developed that
work better in non-homophilous settings, their evaluation is often limited to
a few graph datasets introduced by Pei et al. (2019) that have certain
undesirable properties such as small size, narrow range of application areas,
and synthetic classes (Zhu et al., 2020b; Liu et al., 2020; Zhu et al., 2020a;
Chien et al., 2021; Chen et al., 2020; Yan et al., 2021).

In this work, we summarize issues with the non-homophilous graph datasets that
are used in prior work and propose improved non-homophilous graph datasets
that are substantially larger, span wider application areas, and capture
different types of complex label-topology relationships. As previously-used
homophily metrics have various shortcomings, we introduce a new metric that
detects the presence or absence of homophily in graphs, and use it to analyze
these graph datasets. We reintroduce strong simple methods for learning on
graphs that have been overlooked in recent non-homophilous GNN work. Finally,
we benchmark these simple methods along with general GNNs and non-homophilous
GNNs on our proposed datasets. Our stronger empirical evaluation setup allows
for a better understanding of graph learning methods in diverse settings.

##  2\. Prior Work

###  2.1. Graph Representation Learning

Graph neural networks (Hamilton et al., 2017; Kipf and Welling, 2017;
Veličković et al., 2018) have demonstrated their utility on a variety of graph
machine learning tasks. Most GNNs are constructed by stacking graph neural
network layers that propagate transformed node features and then aggregate
them via different mechanisms. The neighborhood aggregation used in many
existing GNNs implicitly leverage homophily, so they often fail to generalize
on non-homophilous graphs (Zhu et al., 2020b; Balcilar et al., 2021). Indeed,
a wide range of GNNs operate as low-pass graph filters (Nt and Maehara, 2019;
Wu et al., 2019; Balcilar et al., 2021) that smooth features over the graph
topology, which produces similar representations and thus similar predictions
for neighboring nodes.

Due in part to the most common graph learning benchmarks exhibiting strong
homophily, various graph representation learning methods have been developed
that explicitly make use of an assumption of homophily in the data (Wu et al.,
2019; Huang et al., 2021; Deng et al., 2020; Klicpera et al., 2019b;
Bojchevski et al., 2020). By leveraging this assumption, several simple,
inexpensive models are able to achieve state-of-the-art performance on
homophilic datasets (Wu et al., 2019; Huang et al., 2021).

###  2.2. Non-Homophilous Methods

Various GNNs have been proposed to achieve higher performance in low-homophily
settings. For instance, Geom-GCN (Pei et al., 2019) introduces a geometric
aggregation scheme, MixHop (Abu-El-Haija et al., 2019) uses a graph
convolutional layer that mixes powers of the adjacency matrix, GPR-GNN (Chien
et al., 2021) uses learnable weights that can be positive and negative in
feature propagation, and H2GCN (Zhu et al., 2020b) shows that separation of
ego and neighbor embeddings, aggregation in higher-order neighborhoods, and
the combination of intermediate representations improves GNN performance in
low-homophily. Also, various methods that only depend on graph topology have
been proposed for non-homophilous settings, which are based on label
propagation or supervised learning models (Peel, 2017; Altenburger and
Ugander, 2018; Chin et al., 2019; Zheleva and Getoor, 2009). There are several
recurring design decisions across these methods that appear to strengthen
performance in non-homophilous settings: using higher-order neighborhoods,
decoupling neighbor information from ego information, and combining graph
information at different scales.

###  2.3. Real-world Datasets

Recently, the Open Graph Benchmark (Hu et al., 2020) has provided a series of
datasets and leaderboards that improve the quality of evaluation in graph
representation learning; however, most of the node classification datasets
tend to be homophilous, as noted in past work (Zhu et al., 2020b) and expanded
upon in Appendix A.1. A comparable set of high-quality benchmarks to evaluate
non-homophilous methods does not currently exist.

The most widely used datasets to evaluate non-homophilous graph representation
learning methods were presented by (Pei et al., 2019) (see our Appendix Table
4); however, these datasets have fundamental issues. First, they are very
small — the Cornell, Texas, and Wisconsin datasets have between 180-250 nodes,
and the largest of these datasets has 7,600 nodes. In analogy to certain
pitfalls of graph neural network evaluation on small (homophilic) datasets
discussed in (Shchur et al., 2018), evaluation on the datasets in (Pei et al.,
2019) is plagued by high variance across different train/test splits (see
results in (Zhu et al., 2020b)). Also, the small size of these datasets may
make models more prone to overfitting (Dwivedi et al., 2020), and does not
allow for experiments in scalability of GNNs designed for performance in non-
homophilous settings. As a result, they are not satisfactory for evaluating
the performance of node classification models for non-homophilous graphs, and
larger, real-world datasets are necessary.

Peel (2017) also studies node classification on network datasets with various
types of relationships between edges and labels. However, they only study
methods that act on node labels, and thus their datasets do not necessarily
have node features. We take inspiration from their work, by testing on Pokec
and Facebook networks with node features that we define, and by introducing
other year-prediction tasks on citation networks that have node features.

###  2.4. Synthetic Data

Synthetically generated or synthetically modified non-homophilous graph data
may also be used for evaluation of graph machine learning methods. Past works
have taken various approaches to this (Karimi et al., 2018; Abu-El-Haija et
al., 2019; Zhu et al., 2020b; Kim and Oh, 2021; Chien et al., 2021). When
generating the graph, they control homophily through modifications of some
generative models over graphs (Barabási and Albert, 1999; Abbe, 2017;
Deshpande et al., 2018). They tend to either sample node feature vectors from
a real graph or draw them from multivariate Gaussian distributions. While
synthetic data are useful for investigating properties of models in controlled
settings, we focus on benchmarks from real-world data that exhibit diverse
types of complex structure.

##  3\. Datasets and Metrics

###  3.1. Measuring Homophily

Various metrics have been proposed to measure the homophily of a graph in a
single scalar quantity. However, these metrics are sensitive to the number of
classes and the number of nodes in each class. Thus, we introduce a metric
that better captures the presence or absence of homophily. Our metric does not
distinguish between different non-homophilous settings (such as heterophily or
independent edges); we argue that there are too many degrees of freedom in
non-homophilous settings for a single scalar quantity to be able to
distinguish them all.

Let $G=(V,E)$ be a graph with $n$ nodes, none of which are isolated. Further
let each node $x\in V$ have a class label $k_{x}\in\\{0,1,\ldots,C-1\\}$ for
some number of classes $C$, and denote by $C_{k}$ the set of nodes in class
$k$. In recent non-homophilous graph representation learning work, the edge
homophily (Zhu et al., 2020b) has been defined as the proportion of edges that
connect two nodes of the same class:

(1) $h=\frac{|\\{(x,v)\in E\mathrel{\mathop{\mathchar
58\relax}}k_{x}=k_{v}\\}|}{|E|}.$

Another related measure is what we call the node homophily (Pei et al., 2019),
defined as $\frac{1}{|V|}\sum_{x\in V}\frac{d_{x}^{(k_{x})}}{d_{x}}$, in which
$d_{x}$ is the number of neighbors of node $x$, and $d_{x}^{(k_{x})}$ is the
number of neighbors of $x$ that have the same class label. We focus on the
edge homophily (1) in this work, but find that node homophily tends to have
similar qualitative behavior in experiments.

The sensitivity of edge homophily to the number of classes and size of each
class limits its utility. Note that if edges were rewired randomly
independently of node labels, a node $x\in V$ would be expected to have
$d_{x}^{(k_{x})}/d_{x}\approx|C_{k}|/n$ as the proportion of nodes of the same
class that they connect to (Altenburger and Ugander, 2018). For a dataset with
$C$ balanced classes, we would thus expect the edge homophily to be around
$\frac{1}{C}$, so the interpretation of the measure depends on the number of
classes. Also, if classes are imbalanced, then the edge homophily may be
misleadingly large. For instance, if 99% of nodes were of one class, then most
edges would likely be within that same class, so the edge homophily would be
high.

We define a homophily measure that alleviates these shortcomings. Our measure
is given as:

(2)
$\hat{h}=\frac{1}{C-1}\sum_{k=0}^{C-1}\left[h_{k}-\frac{|C_{k}|}{n}\right]_{+},$

where $[a]_{+}=\max(a,0)$, and $h_{k}$ is the class-wise homophily metric

(3) $h_{k}=\frac{\sum_{x\in C_{k}}d_{x}^{(k_{x})}}{\sum_{x\in C_{k}}d_{x}}.$

Note that $\hat{h}\in[0,1]$, with a fully homophilous graph (in which every
node is only connected to nodes of the same class) having $\hat{h}=1$. Since
each class-wise homophily metric $h_{k}$ only contributes positive deviations
from the null expected proportion $|C_{k}|/n$, the class-imbalance problem is
substantially mitigated. Also, graphs in which edges are independent of node
labels are expected to have $\hat{h}\approx 0$, for any number of classes. Our
measure $\hat{h}$ measures presence of homophily, but does not distinguish
between the many types of possibly non-homophilous relationships. This is
reasonable given the diversity of non-homophilous relationships. For example,
non-homophily can imply independence of edges and classes, extreme
heterophily, connections only among subsets of classes, or certain chemically
/ biologically determined relationships. Indeed, these relationships are very
different, and are better captured by more than one scalar quantity, such as
the compatibility matrices that are discussed in Appendix A. Figure 1 compares
our measure $\hat{h}$ with the edge homophily ratio $h$.

On certain datasets where previous measures are misleading, our measure shows
its advantages. For example, some of our proposed datasets are class-
imbalanced (e.g. YelpChi and ogbn-proteins), so they have high edge homophily,
but our measure $\hat{h}$ captures that they are indeed non-homophilous (Table
1). Moreover, as seen in Appendix Table 4, the edge homophily of Chameleon,
Actor, and Squirrel are approximately the same, but the graph structures
(Appendix Figure 5) and performance of different methods on these datasets
vary significantly (Zhu et al., 2020b). According to our measure, Chameleon is
more homophilous than Squirrel, which is in turn more homophilous than Actor,
and past work has shown that models tend to perform better on Chameleon than
Squirrel and better on Squirrel than Actor (Zhu et al., 2020b; Chien et al.,
2021; Pei et al., 2019). Our measure suggests one possible axis of variation
that may help explain this divergence, but we emphasize that there are many
possible confounders. Further discussion is given in Appendix A.

Table 1. Statistics of our proposed non-homophilous graph datasets. # C is the number of distinct node classes. # G/T is the number of different graphs or tasks. When there are multiple graphs or tasks, the minimum and maximum statistics are listed, with a hyphen “-” in between. Dataset | # G/T | # Nodes | # Edges | # Node Feat. | # C | Class types | Edge hom. |  $\hat{h}$ (ours)
---|---|---|---|---|---|---|---|---
Twitch-explicit | 7 | 1,912 - 9,498 | 31,299 - 153,138 | 2,545 | 2 | explicit content | .556 - .632 | .049-.146
YelpChi | 1 | 45,954 | 3,846,979 | 32 | 2 | fake reviews | .773 | .052
deezer-europe | 1 | 28,281 | 92,752 | 31,241 | 2 | gender | .525 | .030
FB100 | 100 | 769-41,536 | 16,656-1,590,655 | 5 | 2 | gender | .434 - .917 | .000 - .246
Pokec | 1 | 1,632,803 | 30,622,564 | 65 | 2 | gender | .445 | .000
ogbn-proteins | 112 | 132,534 | 39,561,252 | 8 | 2 | function | .623 - .940 | .090 - .260
arXiv-year | 1 | 169,343 | 1,166,243 | 128 | 5 | pub year | .222 | .272
snap-patents | 1 | 2,923,922 | 13,975,788 | 269 | 5 | time granted | .073 | .100

|
---|---
|
|

(a) $h=1$, $\hat{h}=1$ (b) $h=0$, $\hat{h}=0$

(c) $h=.5$, $\hat{h}=0$ (d) $h=.33$, $\hat{h}=0$

(e) $h=.53$, $\hat{h}=.07$ (f) $h=.66$, $\hat{h}=.04$

Figure 1. Examples of graphs with different label-topology relationships and
comparison of our measure $\hat{h}$ with the edge homophily ratio $h$. The
node classes are labeled by color. Pink edges link nodes of the same class,
while purple edges link nodes of different classes. (a,b) Pure homophily and
pure heterophily. Both measures equal $1$ in homophily and $0$ in heterophily.
(c,d) Graphs where each node is connected to one member of each class. Edge
homophily depends on the number of classes, while our measure $\hat{h}$ does
not. (e,f) Random Erdős Rényi graphs in which edges are independent of labels.
Edge homophily is sensitive to class imbalance, while our measure $\hat{h}$ is
not.

###  3.2. Proposed Datasets

Here, we detail the non-homophilous datasets that we propose for graph machine
learning evaluation. These datasets come from a variety of contexts, and some
have been used for evaluation of graph machine learning models in past work;
in certain cases, we make adjustments such as modifying node labels and adding
node features. We define node features for Facebook100, Pokec, and snap-
patents, while we redefine node labels for arXiv-year and snap-patents. Basic
dataset statistics are given in Table 1. The datasets are as follows:

Twitch-explicit contains 7 networks where Twitch users are nodes, and mutual
friendships between them are edges (Rozemberczki et al., 2019). Node features
are games liked, location and streaming habits. Each graph is associated to
users of a particular region. The class labels denote whether a streamer uses
explicit language. We solely train and test on Twitch-DE, which has 9,498
nodes, 76,569 edges, edge homophily of .632, and $\hat{h}$ of .142.

YelpChi (Mukherjee et al., 2013) is a graph in which the nodes are reviews for
hotels and restaurants in the Chicago area, and the class labels are
fraudulent reviews and recommended reviews. The 32 node features are taken
from (Rayana and Akoglu, 2015). We take the topology from (Dou et al., 2020);
while there are different relations captured by edges, we treat them all as
the same single edge type.

deezer-europe (Rozemberczki and Sarkar, 2020) is a social network of users on
Deezer from European countries, where edges represent mutual follower
relationships. The node features are based on artists liked by each user.
Nodes are labeled with reported gender.

Facebook100 (Traud et al., 2012) consists of 100 Facebook friendship network
snapshots from 2005, each of which has as nodes the Facebook users from a
given American university. Each node is labeled with the reported gender of
the user. The node features are major, second major/minor, dorm/house, year,
and high school. We solely train and test on Penn94, which has 41,554 nodes,
1,362,229 edges, edge homophily of .470, and $\hat{h}$ of .046.

Pokec is the friendship graph of a Slovak online social network, where nodes
are users and edges are directed friendship relations (Leskovec and Krevl,
2014). Nodes are labeled with reported gender. The node features are derived
from profile information, such as geographical region, registration time, and
age.

ogbn-proteins (Hu et al., 2020) has proteins as nodes and different biological
relationships between proteins as edges. There are 112 tasks, in which each
protein is given a binary label. Also, there are no separate node features —
instead, the means of incoming edge features give 8 dimensional node features.

arXiv-year (Hu et al., 2020) is the ogbn-arxiv network with class labels given
by the year that the paper is posted, instead of by subject areas. The nodes
are arXiv papers, and directed edges connect a paper to other papers that it
cites. The node features are averaged word2vec token features of both the
title and abstract of the paper. The five classes are chosen by partitioning
the posting dates so that class ratios are approximately balanced: 2013 and
prior, 2014-2015, 2016-2017, 2018, and 2019-2020.

snap-patents (Leskovec et al., 2005; Leskovec and Krevl, 2014) is a dataset of
utility patents granted between 1963 to 1999 in the US. Each node is a patent,
and edges connect patents that cite each other. Node features are derived from
patent metadata. The task is to predict the time at which a patent was
granted. The five classes are: 1971 and prior, 1972-1980, 1981-1988,
1989-1994, and 1995-1999.

###  3.3. General Non-homophilous Settings

Different settings in which non-homophilous relationships are prevalent have
been identified in the literature and are represented by our proposed
datasets:

  * •

Gender relations in social or interaction networks (Altenburger and Ugander,
2018; Chin et al., 2019; Jia and Benson, 2020) (deezer, FB100, Pokec).

  * •

Biological structures such as in food webs (Gatterbauer, 2014) and protein
interactions (Newman, 2003) (ogbn-proteins).

  * •

Technological and internet relationships, such as in web page connections
(Newman, 2003; Pei et al., 2019).

  * •

Malicious or fraudulent nodes, such as in auction networks (Chau et al., 2006;
Pandit et al., 2007) (YelpChi).

  * •

Publication time in citation networks (Peel, 2017) (arXiv-year, snap-patents).

While not all example graph data from these contexts are non-homophilous, a
diverse range are. In order to succeed in future applications in these
contexts, it may be important to develop methods that are able to handle non-
homophilous structures.

##  4\. Experiments

Table 2. Experimental results. Test accuracy is displayed for most datasets, while Twitch-DE, YelpChi, and ogbn-proteins display test ROC AUC$\dagger$. Standard deviations are over 5 train/val/test splits, except for ogbn-proteins, which has a fixed split. The three best results per dataset are highlighted in blue. (M) denotes some (or all) hyperparameter settings run out of memory. |  Twitch-DE$\dagger$ |  YelpChi$\dagger$ | deezer | Penn94 (FB100) | pokec |  ogbn-proteins$\dagger$ | arXiv-year | snap-patents
---|---|---|---|---|---|---|---|---
MLP | $69.20\pm 0.62$ | $87.94\pm 0.52$ | $66.55\pm 0.72$ | $73.61\pm 0.40$ | $62.37\pm 0.02$ | $73.43\pm 0.12$ | $36.70\pm 0.21$ | $31.34\pm 0.05$
L Prop (1 hop) | $71.00\pm 1.01$ | $63.64\pm 0.73$ | $56.50\pm 0.41$ | $63.21\pm 0.39$ | $53.09\pm 0.05$ | $75.14\pm 0.00$ | $43.42\pm 0.17$ | $30.28\pm 0.09$
L Prop (2 hop) | $72.27\pm 0.78$ | $62.34\pm 0.78$ | $56.96\pm 0.26$ | $74.13\pm 0.46$ | $76.76\pm 0.03$ | $65.79\pm 0.00$ | $46.07\pm 0.15$ | $38.61\pm 0.07$
LINK | $72.42\pm 0.57$ | $63.44\pm 1.07$ | $57.71\pm 0.36$ | $80.79\pm 0.49$ | $80.54\pm 0.03$ | $63.49\pm 0.02$ | $53.97\pm 0.18$ | $60.39\pm 0.07$
SGC (1 hop) | $72.30\pm 0.22$ | $58.62\pm 0.85$ | $59.73\pm 0.12$ | $66.79\pm 0.27$ | $53.61\pm 0.17$ | $50.58\pm 1.08$ | $32.83\pm 0.13$ | $30.31\pm 0.06$
SGC (2 hop) | $73.65\pm 0.40$ | $57.18\pm 0.75$ | $61.56\pm 0.51$ | $76.09\pm 0.45$ | $62.81\pm 1.42$ | $49.48\pm 1.45$ | $32.27\pm 0.06$ | $29.09\pm 0.09$
C&S (1 hop) | $68.54\pm 1.25$ | $87.47\pm 0.50$ | $64.60\pm 0.57$ | $72.55\pm 0.63$ | $63.23\pm 0.07$ | $71.13\pm 0.69$ | $42.08\pm 0.27$ | $37.41\pm 0.07$
C&S (2 hop) | $69.39\pm 0.85$ | $87.40\pm 0.44$ | $64.52\pm 0.62$ | $72.47\pm 0.73$ | $77.22\pm 0.61$ | $69.31\pm 0.62$ | $42.17\pm 0.27$ | $44.62\pm 0.14$
GCN | $74.07\pm 0.68$ | $63.62\pm 1.00$ | $62.23\pm 0.53$ | $82.47\pm 0.27$ | $75.45\pm 0.17$ | $72.03\pm 0.32$ | $46.02\pm 0.26$ | $45.65\pm 0.04$
GAT | $73.13\pm 0.29$ |  $81.42\pm 2.12$ (M) | $61.09\pm 0.77$ | $81.53\pm 0.55$ |  $71.77\pm 6.18$ (M) | (M) | $46.05\pm 0.51$ |  $45.37\pm 0.44$ (M)
GCN+JK | $70.57\pm 2.22$ | $64.35\pm 0.86$ | $60.99\pm 0.14$ | $81.63\pm 0.54$ | $77.00\pm 0.14$ | $76.88\pm 0.48$ | $46.28\pm 0.29$ | $46.88\pm 0.13$
GAT+JK | $73.06\pm 0.49$ |  $90.04\pm 0.61$ (M) | $59.66\pm 0.92$ | $80.69\pm 0.36$ |  $71.19\pm 6.96$ (M) | (M) | $45.80\pm 0.72$ |  $44.78\pm 0.50$ (M)
APPNP | $72.20\pm 0.73$ | $86.66\pm 0.64$ | $67.21\pm 0.56$ | $74.95\pm 0.45$ | $62.58\pm 0.08$ | $68.96\pm 0.09$ | $38.15\pm 0.26$ | $32.19\pm 0.07$
H2GCN | $72.67\pm 0.65$ | $88.48\pm 0.21$ | $67.22\pm 0.90$ | (M) | (M) | (M) | $49.09\pm 0.10$ | (M)
MixHop | $73.23\pm 0.99$ | $87.02\pm 0.50$ | $66.80\pm 0.58$ | $83.47\pm 0.71$ | $81.07\pm 0.16$ | $75.60\pm 0.85$ | $51.81\pm 0.17$ |  $52.16\pm 0.09$ (M)
GPR-GNN | $73.84\pm 0.69$ | $86.57\pm 0.89$ | $66.90\pm 0.50$ | $84.59\pm 0.29$ | $78.83\pm 0.05$ | (M) | $45.07\pm 0.21$ | $40.20\pm 0.03$

###  4.1. Experimental Setup

We include both methods that are graph-agnostic and node-feature-agnostic as
simple baselines; the node-feature-agnostic models of two-hop label
propagation (Peel, 2017) and LINK (logistic regression on the adjacency
matrix) (Zheleva and Getoor, 2009) have been found to perform well in various
non-homophilous settings, but they have often been overlooked by recent graph
representation learning work. Also, we include SGC (Wu et al., 2019) and C&S
(Huang et al., 2021) as simple methods that perform well on homophilic
datasets. We include a two-hop propagation variant of C&S in analogy with two-
step label propagation. In addition to representative general GNNs, we also
include three GNNs recently proposed for non-homophilous settings. The full
list of methods is:

  * •

Models that only use node features: MLP (Goodfellow et al., 2016).

  * •

Models that only use the graph topology: label propagation (standard and two-
hop) (Zhou et al., 2004; Peel, 2017), LINK (Zheleva and Getoor, 2009).

  * •

Simple methods: SGC (Wu et al., 2019), C&S (Huang et al., 2021), two-hop
variants.

  * •

General GNNs: GCN (Kipf and Welling, 2017), GAT (Veličković et al., 2018),
jumping knowledge networks (GCN+JK, GAT+JK) (Xu et al., 2018), and APPNP
(Klicpera et al., 2019a).

  * •

Non-homophilous GNNs: H2GCN (Zhu et al., 2020b), MixHop (Abu-El-Haija et al.,
2019), and GPR-GNN (Chien et al., 2021).

Following other works in non-homophilous graph learning evaluation, we take a
high proportion of training nodes (Zhu et al., 2020b; Pei et al., 2019; Yan et
al., 2021); we run each method on the same five random 50/25/25 train/val/test
splits for each dataset, besides ogbn-proteins, for which we use the original
Open Graph Benchmark splits (Hu et al., 2020). All methods requiring gradient-
based optimization are run for 500 epochs, with test performance reported for
the learned parameters of highest validation performance. We use ROC-AUC as
the metric for the class-imbalanced Twitch-DE (60.5% of nodes in majority
class), YelpChi (85.5% of nodes in majority class), and ogbn-proteins datasets
(52.7% to 98.0% in majority, depending on task). For other datasets, we use
classification accuracy as the metric. Further experimental details can be
found in Appendix B.

###  4.2. Experimental Results

Table 2 lists the results of each method across the datasets that we propose.
Our new measure and new datasets reveal several important properties of non-
homophilous node classification. Firstly, both methods that only use node
features and methods that only use graph topology appear to perform better
than random, thus demonstrating the quality of our datasets. Secondly, the
stability of performance across runs is better for our datasets than those of
Pei et al. (2019) (see (Zhu et al., 2020b) results). Moreover, as suggested by
prior theory and experiments (Zhu et al., 2020b; Abu-El-Haija et al., 2019;
Chien et al., 2021), the non-homophilous GNNs usually do well — though not
necessarily on every dataset.

The core assumption of homophily in SGC and C&S that enables them to be simple
and efficient does not hold on these non-homophilous datasets, and thus the
performance of these methods is typically relatively low. Nevertheless, 2-hop
C&S still achieves high performance on some datasets. Indeed, our results
indicate that simple 2-hop modifications of learning methods often improve
performance in low-homophily, though we note that 1-hop label propagation
performs much better than expected on ogbn-proteins, possibly due to some
implementation nuance. LINK, a frequently ignored baseline that in some sense
acts on two-hop neighborhoods of each node (Altenburger and Ugander, 2018),
performs well on many datasets — despite not using node feature information.

Finally, one consequence of using larger datasets for benchmarks is that the
tradeoff between scalability and learning performance of non-homophilous
methods has become starker, with some methods facing memory issues. This
tradeoff is especially important to consider in light of the fact that many
scalable graph learning methods rely on implicit or explicit homophily
assumptions (Wu et al., 2019; Huang et al., 2021; Deng et al., 2020;
Bojchevski et al., 2020), and thus face issues when used in non-homophilous
settings.

##  5\. Conclusion

In this paper, we introduce a measure of the presence of homophily that
alleviates issues with existing measures, propose new, high-quality non-
homophilous graph learning datasets, and benchmark simple baselines and
representative graph representation learning methods across our datasets. We
hope that these contributions will provide researchers of non-homophilous
graph learning methods with better tools to test their models and evaluate the
utility of new techniques. While we benchmark on transductive node
classification, the datasets we propose could be adapted to benchmark link
prediction, clustering tasks, and inductive node classification in the case of
Twitch-explicit and Facebook100. Future work could study these other tasks in
low-homophily settings, reformulate current understandings of homophily that
are most natural in node classification, and introduce new benchmarks for a
wider range of applications.

###### Acknowledgements.

We thank Austin Benson and Horace He for insightful discussions. We also thank
the rest of Cornell University Artificial Intelligence for their support and
discussion. This research was supported by Facebook AI.

## References

  * (1)
  * Abbe (2017) Emmanuel Abbe. 2017\.  Community detection and stochastic block models: recent developments.  _The Journal of Machine Learning Research_ 18, 1 (2017), 6446–6531.
  * Abu-El-Haija et al. (2019) Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. 2019.  MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing. In _International Conference on Machine Learning_. 21–29.
  * Akiba et al. (2019) Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. 2019.  Optuna: A Next-generation Hyperparameter Optimization Framework.  arXiv:1907.10902 [cs.LG]
  * Altenburger and Ugander (2018) Kristen M Altenburger and Johan Ugander. 2018.  Monophily in social networks introduces similarity among friends-of-friends.  _Nature human behaviour_ 2, 4 (2018), 284–290.
  * Balcilar et al. (2021) Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. 2021\.  Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=-qh0M9XWxnv
  * Barabási and Albert (1999) Albert-László Barabási and Réka Albert. 1999.  Emergence of scaling in random networks.  _science_ 286, 5439 (1999), 509–512.
  * Battaglia et al. (2018) Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. 2018\.  Relational inductive biases, deep learning, and graph networks.  _arXiv preprint arXiv:1806.01261_ (2018).
  * Bojchevski et al. (2020) Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. 2020\.  Scaling graph neural networks with approximate pagerank. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 2464–2473.
  * Chau et al. (2006) Duen Horng Chau, Shashank Pandit, and Christos Faloutsos. 2006\.  Detecting fraudulent personalities in networks of online auctioneers. In _European conference on principles of data mining and knowledge discovery_. Springer, 103–114.
  * Chen et al. (2020) Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020.  Simple and deep graph convolutional networks. In _International Conference on Machine Learning_. PMLR, 1725–1735.
  * Chien et al. (2021) Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2021\.  Adaptive Universal Generalized PageRank Graph Neural Network. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=n6jl7fLxrP
  * Chin et al. (2019) Alex Chin, Yatong Chen, Kristen M. Altenburger, and Johan Ugander. 2019.  Decoupled smoothing on graphs. In _The World Wide Web Conference_. 263–272.
  * Clevert et al. (2015) Djork-Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter. 2015.  Fast and accurate deep network learning by exponential linear units (elus).  _arXiv preprint arXiv:1511.07289_ (2015).
  * Deng et al. (2020) Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. 2020.  GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=r1lGO0EKDH
  * Deshpande et al. (2018) Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. 2018.  Contextual stochastic block models. In _Advances in Neural Information Processing Systems_. 8581–8593.
  * Dou et al. (2020) Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng, and Philip S Yu. 2020.  Enhancing graph neural network-based fraud detectors against camouflaged fraudsters. In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_. 315–324.
  * Dwivedi et al. (2020) Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2020\.  Benchmarking graph neural networks.  _arXiv preprint arXiv:2003.00982_ (2020).
  * Erdős and Rényi (1960) Paul Erdős and Alfréd Rényi. 1960.  On the evolution of random graphs.  _Publ. Math. Inst. Hung. Acad. Sci_ 5, 1 (1960), 17–60.
  * Gatterbauer (2014) Wolfgang Gatterbauer. 2014\.  Semi-supervised learning with heterophily.  _arXiv preprint arXiv:1412.3100_ (2014).
  * Goodfellow et al. (2016) Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. 2016.  _Deep learning_. Vol. 1.  MIT press Cambridge.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs. In _Advances in neural information processing systems_. 1024–1034.
  * Hamilton (2020) William L. Hamilton. 2020\.  Graph Representation Learning.  _Synthesis Lectures on Artificial Intelligence and Machine Learning_ 14, 3 (2020), 1–159.
  * Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020\.  Open graph benchmark: Datasets for machine learning on graphs.  _arXiv preprint arXiv:2005.00687_ (2020).
  * Huang et al. (2021) Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. 2021.  Combining Label Propagation and Simple Models out-performs Graph Neural Networks. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=8E1-f3VhX1o
  * Ioffe and Szegedy (2015) Sergey Ioffe and Christian Szegedy. 2015.  Batch normalization: Accelerating deep network training by reducing internal covariate shift. In _International conference on machine learning_. PMLR, 448–456.
  * Jia and Benson (2020) Junteng Jia and Austion R Benson. 2020.  Residual Correlation in Graph Neural Network Regression. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 588–598.
  * Karimi et al. (2018) Fariba Karimi, Mathieu Génois, Claudia Wagner, Philipp Singer, and Markus Strohmaier. 2018\.  Homophily influences ranking of minorities in social networks.  _Scientific reports_ 8, 1 (2018), 1–12.
  * Kim and Oh (2021) Dongkwan Kim and Alice Oh. 2021.  How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=Wi5KUNlqWty
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-Supervised Classification with Graph Convolutional Networks.  arXiv:1609.02907 [cs.LG]
  * Klicpera et al. (2019a) Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. 2019a.  Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=H1gL-2A9Ym
  * Klicpera et al. (2019b) Johannes Klicpera, Stefan Weiß enberger, and Stephan Günnemann. 2019b.  Diffusion Improves Graph Learning. In _Advances in Neural Information Processing Systems_ , Vol. 32.
  * Laniado et al. (2016) David Laniado, Yana Volkovich, Karolin Kappler, and Andreas Kaltenbrunner. 2016.  Gender homophily in online dyadic and triadic relationships.  _EPJ Data Science_ 5 (2016), 1–23.
  * Leskovec et al. (2005) Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005\.  Graphs over time: densification laws, shrinking diameters and possible explanations. In _Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining_. 177–187.
  * Leskovec and Krevl (2014) Jure Leskovec and Andrej Krevl. 2014.  SNAP Datasets: Stanford Large Network Dataset Collection.  http://snap.stanford.edu/data.
  * Liu et al. (2020) Meng Liu, Zhengyang Wang, and Shuiwang Ji. 2020.  Non-Local Graph Neural Networks.  arXiv:2005.14612 [cs.LG]
  * Loshchilov and Hutter (2018) Ilya Loshchilov and Frank Hutter. 2018.  Decoupled Weight Decay Regularization. In _International Conference on Learning Representations_.
  * McPherson et al. (2001) Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001\.  Birds of a feather: Homophily in social networks.  _Annual review of sociology_ 27, 1 (2001), 415–444.
  * Mukherjee et al. (2013) Arjun Mukherjee, Vivek Venkataraman, Bing Liu, and Natalie Glance. 2013.  What yelp fake review filter might be doing?. In _Proceedings of the International AAAI Conference on Web and Social Media_ , Vol. 7.
  * Newman (2003) Mark EJ Newman. 2003\.  Mixing patterns in networks.  _Physical review E_ 67, 2 (2003), 026126.
  * Nt and Maehara (2019) Hoang Nt and Takanori Maehara. 2019.  Revisiting graph neural networks: All we have is low-pass filters.  _arXiv preprint arXiv:1905.09550_ (2019).
  * Pandit et al. (2007) Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. 2007.  Netprobe: a fast and scalable system for fraud detection in online auction networks. In _Proceedings of the 16th international conference on World Wide Web_. 201–210.
  * Peel (2017) Leto Peel. 2017\.  Graph-based semi-supervised learning for relational networks. In _Proceedings of the 2017 SIAM International Conference on Data Mining_. SIAM, 435–443.
  * Pei et al. (2019) Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2019.  Geom-GCN: Geometric Graph Convolutional Networks. In _International Conference on Learning Representations_.
  * Rayana and Akoglu (2015) Shebuti Rayana and Leman Akoglu. 2015.  Collective opinion spam detection: Bridging review networks and metadata. In _Proceedings of the 21th acm sigkdd international conference on knowledge discovery and data mining_. 985–994.
  * Rozemberczki et al. (2019) Benedek Rozemberczki, Carl Allen, and Rik Sarkar. 2019.  Multi-scale attributed node embedding.  _arXiv preprint arXiv:1909.13021_ (2019).
  * Rozemberczki and Sarkar (2020) Benedek Rozemberczki and Rik Sarkar. 2020.  Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models. In _Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM ’20)_. ACM, 1325–1334.
  * Shchur et al. (2018) Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018\.  Pitfalls of graph neural network evaluation.  _arXiv preprint arXiv:1811.05868_ (2018).
  * Sloane (2007) Neil JA Sloane. 2007\.  The on-line encyclopedia of integer sequences.  In _Towards mechanized mathematical assistants_. Springer, 130–130.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: a simple way to prevent neural networks from overfitting.  _The journal of machine learning research_ 15, 1 (2014), 1929–1958.
  * Traud et al. (2012) Amanda L Traud, Peter J Mucha, and Mason A Porter. 2012\.  Social structure of facebook networks.  _Physica A: Statistical Mechanics and its Applications_ 391, 16 (2012), 4165–4180.
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018.  Graph Attention Networks. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=rJXMpikCZ
  * Wu et al. (2019) Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019\.  Simplifying graph convolutional networks. In _International conference on machine learning_. PMLR, 6861–6871.
  * Xu et al. (2018) Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018.  Representation learning on graphs with jumping knowledge networks. In _International Conference on Machine Learning_. PMLR, 5453–5462.
  * Yan et al. (2021) Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. 2021.  Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks.  _arXiv preprint arXiv:2102.06462_ (2021).
  * Yang et al. (2016) Zhilin Yang, William Cohen, and Ruslan Salakhudinov. 2016\.  Revisiting semi-supervised learning with graph embeddings. In _International conference on machine learning_. PMLR, 40–48.
  * Zheleva and Getoor (2009) Elena Zheleva and Lise Getoor. 2009.  To join or not to join: the illusion of privacy in social networks with mixed public and private user profiles. In _Proceedings of the 18th international conference on World wide web_. 531–540.
  * Zhou et al. (2004) Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. 2004\.  Learning with local and global consistency.  (2004).
  * Zhu et al. (2020a) Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. 2020a.  Graph Neural Networks with Heterophily.  _arXiv preprint arXiv:2009.13566_ (2020).
  * Zhu et al. (2020b) Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020b.  Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs.  _Advances in Neural Information Processing Systems_ 33 (2020).

##  Appendix A Compatibility Matrices and Statistics

|  |
---|---|---
|  |
|  |
Figure 2. Compatibility matrices of our proposed datasets. These datasets from
a variety of different contexts exhibit a wide range of non-homophilous
structures. We choose 2 of the 112 ogbn-proteins tasks to display.

Following previous work (Zhu et al., 2020b), for a graph $G$ with $C$ node
classes we define the $C\times C$ compatibility matrix $\mathbf{H}$ by

(4) $\mathbf{H}_{kl}=\frac{|(u,v)\in E\mathrel{\mathop{\mathchar
58\relax}}k_{u}=k,\;k_{v}=l|}{|(u,v)\in E\mathrel{\mathop{\mathchar
58\relax}}k_{u}=k|}$

This captures finer details of label-topology relationships in graphs than
single scalar metrics (like edge homophily and our $\hat{h}$) capture. For
classes $k$ and $l$, the entry $\mathbf{H}_{kl}$ measures the proportion of
edges from nodes of class $k$ that are connected to nodes of class $l$.
Compatibility matrices for our proposed datasets are shown in Figure 2. As
evidenced by the different patterns, the proposed datasets show interesting
types of label-topology relationships besides homophily. For instance, the
citation datasets arXiv-year and snap-patents have primarily lower-triangular
structure, since most citations reference past work. The Penn94 matrix is
mostly uniform, so there is little to no gender preference in aggregate,
though past work has shown other useful signals in the social structure of
gender (Altenburger and Ugander, 2018). In Twitch-DE, while streamers that use
explicit content (class 1) often connect to other streamers of class 1,
streamers that do not use explicit content (class 0) also often connect to
streamers of class 1, thus giving an overall non-homophilous structure. In
Pokec, there is some heterophily, in that one gender has some preference for
friends of another gender.

###  A.1. Homophilous Data Statistics

Table 3. Statistics for homophilic graph datasets. # C is the number of node classes. Dataset | # Nodes | # Edges | # C | Edge hom. |  $\hat{h}$ (ours)
---|---|---|---|---|---
Cora | 2,708 | 5,278 | 7 | .81 | .766
Citeseer | 3,327 | 4,552 | 6 | .74 | .627
Pubmed | 19,717 | 44,324 | 3 | .80 | .664
ogbn-arXiv | 169,343 | 1,166,243 | 40 | .66 | .416
ogbn-products | 2,449,029 | 61,859,140 | 47 | .81 | .459
oeis | 226,282 | 761,687 | 5 | .50 | .532

In contrast to the different compatibility matrix structures of our proposed
non-homophilous datasets, much other graph data have primarily homophilous
relationships, as can be seen in Figure 4 and Table 3. The Cora, CiteSeer,
PubMed, ogbn-arxiv, and ogbn-products datasets are widely used as benchmarks
for node classification (Yang et al., 2016; Hu et al., 2020), and are highly
homophilous, as can be seen by the diagonally dominant structure of the
compatibility matrices and by the high edge homophily and $\hat{h}$.

We collected the oeis dataset displayed in the bottom right of Figure 4. The
nodes are entries in the Online Encyclopedia of Integer Sequences (Sloane,
2007), and directed edges link an entry to any other entry that it cites. In
analogy to arXiv-year and snap-patents, the node labels are the time of
posting of the sequence. However, in this case the graph relationships are
homophilous, even as we vary the number of distinct classes (time periods).
This is in part due to differences between posting in this online encyclopedia
and publication of academic papers or patents. For instance, there is less
overhead to posting an entry in the OEIS, so users often post separate related
entries and variants of these entries in rapid succession. Also, an entry in
the encyclopedia often inspires other people to work on similar entries, which
can be created in much less time than an academic follow-up work to a given
paper. These related entries tend to cite each other, which contributes to
homophilic relationships over time. Thus, the data here does not follow the
special temporal citation structure of academic publications and patents.

Figure 3. Comparison of edge homophily $h$ and our measure $\hat{h}$ on random
class-imbalanced graph data with edges independent of node labels. Three
standard deviations are shaded. Our measure is mostly constant as the classes
become more imbalanced, while edge homophily increases.

###  A.2. Previous Non-Homophilous Data

Dataset | # Nodes | # Edges | # Node Feat. | # C | Context | Edge hom. |  $\hat{h}$ (ours)
---|---|---|---|---|---|---|---
Chameleon | 2,277 | 36,101 | 2,325 | 5 | Wiki pages | .23 | .062
Cornell | 183 | 295 | 1,703 | 5 | Web pages | .30 | .047
Actor | 7,600 | 29,926 | 931 | 5 | Actors in movies | .22 | .011
Squirrel | 5,201 | 216,933 | 2,089 | 5 | Wiki pages | .22 | .025
Texas | 183 | 309 | 1,703 | 5 | Web pages | .11 | .001
Wisconsin | 251 | 499 | 1,703 | 5 | Web pages | .21 | .094
Table 4. Statistics for datasets from Pei et al. (2019). #C is the number of
node classes.

For the six datasets in Pei et al. (2019) often used in evaluation of graph
representation learning methods in non-homophilous regimes (Zhu et al.,
2020b), basic statistics are listed in Table 4 and compatibility matrices are
displayed in Figure 5. We propose many more datasets (including the 100 graphs
from Facebook100) that have up to orders of magnitude more nodes and edges and
come from a wider range of contexts. There are several cases of class-
imbalance in these datasets, which may make the edge homophily misleading. As
discussed in Section 3.1, our measure may be able to alleviate issues with
edge homophily in measuring homophily of these datasets, and offers a way to
distinguish between the Chameleon, Actor, and Squirrel datasets that all have
similar edge homophily.

###  A.3. Class-Imbalance and Metrics

In this section, we present experiments that demonstrate an instance in which
our metric is not affected by imbalanced classes, while edge homophily is. We
generate graphs in which node labels are independent of edges by randomly
choosing node labels and generating graph edges by the Erdős-Rényi random
graph model (Erdős and Rényi, 1960). In particular, we fix the number of
classes to two, the number of nodes to 100, and the probability of edge
formation as .25 between every pair of nodes. Then we generate 100 samples of
these random graphs, and compute the mean and standard deviation of both edge
homophily $h$ and our measure $\hat{h}$. As seen in Figure 3, our measure
$\hat{h}$ is constantly near zero as we increase the size of the majority
class, while the edge homophily $h$ increases as the size of majority class
increases.

|  |
---|---|---
|  |
Figure 4. Compatibility matrices of homophilic datasets. The diagonal dominance indicates strong homophily. |  |
---|---|---
|  |
Figure 5. Compatibility matrices of datasets in Pei et al. (2019). The “film”
dataset is also referred to as “Actor”. Note that there are no edges leading
out of the nodes of class 1 in the Cornell dataset, so there is an empty row
in its matrix.

##  Appendix B Experimental Details

For gradient-based optimization, we use the AdamW optimizer (Kingma and Ba,
2014; Loshchilov and Hutter, 2018) with weight decay .001 and learning rate
$.01$ by default, unless we tune the optimizer for a particular method (as
noted below in B.1). In all cases, we use full batch gradient descent across
the entire graph dataset. Hyperparameter tuning is conducted using grid search
for most methods. Tuning for C&S is done as in the original paper (Huang et
al., 2021), which uses Optuna (Akiba et al., 2019) for Bayesian hyperparameter
optimization. GCN and GCN-JK on ogbn-proteins use the hyper-parameters of
methods on the Open Graph Benchmark leaderboards (Hu et al., 2020). All graphs
are treated as undirected besides arXiv-year and snap-patents, in which the
directed nature of the edges capture useful temporal information; however, we
find that label propagation and C&S (which builds on label propagation)
perform better with undirected graphs in these cases, so we keep the graphs as
undirected for these methods.

Simple methods are run on a Nvidia 2080 Ti with 11 GB GPU memory. In cases
where the Nvidia 2080Ti did not provide enough memory, we re-ran experiments
on a Nvidia Titan RTX with 24GB GPU memory, reporting (M) in Table 2 if the
GPU memory was still insufficient.

###  B.1. Hyperparameters

Experimental results are reported on the hyperparameter settings below, where
we choose the settings that achieve the highest performance on the validation
set. We choose hyperparameter grids that do not necessarily give optimal
performance, but hopefully cover enough regimes so that each model is
reasonably evaluated on each dataset. Unless otherwise stated, each GNN has
dropout of .5 (Srivastava et al., 2014) and BatchNorm (Ioffe and Szegedy,
2015) in each layer. The hyperparameter grids for the different methods are:

  * •

MLP: hidden dimension $\in\\{16,32,64,128,256\\}$, number of layers
$\in\\{2,3\\}$. We use ReLU activations.

  * •

Label propagation: $\alpha\in\\{.01,.1,.25,.5,.75,.9,.99\\}$. We use 50
propagation iterations.

  * •

LINK: weight decay $\in\\{.001,.01,.1\\}$.

  * •

SGC: weight decay $\in\\{.001,.01,.1\\}$.

  * •

C&S: Normalized adjacency matrix A1, A2
$\in\\{D^{-\frac{1}{2}}AD^{-\frac{1}{2}},\\\ D^{-1}A,AD^{-1}\\}$ for the
residual propagation and label propagation, where $A$ is the adjacency matrix
of the graph and $D$ is the diagonal degree matrix;
$\alpha_{1},\alpha_{2}\in(0.0,1.0)$ for the two propagations. Both Autoscale
and FDiff-scale were used for all experiments, and scale $\in(0.1,10.0)$ was
searched in FDiff-scale settings. The base predictor is chosen as the best MLP
model for each dataset.

  * •

GCN: lr $\in\\{.1,.01,.001\\}$, hidden dimension $\in\\{4,8,16,32,64\\}$,
except for snap-patents and pokec, where we omit hidden dimension = 64, and
ogbn-proteins, where we use the experimental setup of Hu et al. (2020). Each
activation is a ReLU. 2 layers were used for all experiments except for ogbn-
proteins.

  * •

GAT: lr $\in\\{.1,.01,.001\\}$. For snap-patents and pokec: hidden channels
$\in\\{4,8,12\\}$ and gat heads $\in\\{2,4\\}$. For all other datasets: hidden
channels $\in\\{4,8,12,32\\}$ and gat heads $\in\\{2,4,8\\}$. We use the ELU
activation (Clevert et al., 2015). 2 layers were used for all experiments.

  * •

GCN-JK: Identical for GCN, also including JK Type
$\in\\{\text{cat},\text{max}\\}$.

  * •

GAT-JK: Identical for GAT, also including JK Type
$\in\\{\text{cat},\text{max}\\}$.

  * •

APPNP: MLP hidden dimension $\in\\{16,32,64,128,256\\}$, learning rate
$\in\\{.01,.05,.002\\}$, $\alpha\in\\{.1,.2,.5,.9\\}$. We truncate the series
at the $K=10$th power of the adjacency. We also try networks with and without
BatchNorm.

  * •

H2GCN: hidden dimension $\in\\{8,16,32,64\\}$, number of layers
$\in\\{1,2\\}$, dropout $\in\\{0,.5\\}$. The architecture follows Section 3.2
of (Zhu et al., 2020b).

  * •

MixHop: hidden dimension $\in\\{8,16,32\\}$, number of layers $\in\\{2,3\\}$.
Each layer has uses the 0th, 1st, and 2nd powers of the adjacency and has ReLU
activations. The last layer is a linear projection layer, instead of the
attention output mechanism in (Abu-El-Haija et al., 2019).

  * •

GPR-GNN: The basic setup and grid is the same as that of APPNP. We use their
Personalized PageRank weight initialization.

## Version Notes

arXiv v2 (July 2021): added batch normalization to the APPNP and GPR-GNN
hyperparameter grids, as this sometimes really affects performance —
especially on larger graphs.


# Analysis of Impulsive Interference in Digital Audio Broadcasting Systems in
Electric Vehicles

1st Chin-Hung Chen  Electrical Engineering
Eindhoven University of Technology
Eindhoven, The Netherlands
<EMAIL_ADDRESS>2nd Wen-Hung Huang  Electrical Engineering
Eindhoven University of Technology
Eindhoven, The Netherlands
<EMAIL_ADDRESS>3rd Boris Karanov  Electrical Engineering
Eindhoven University of Technology
Eindhoven, The Netherlands
<EMAIL_ADDRESS>4th Alex Young  NXP Semiconductors
Eindhoven, The Netherlands
<EMAIL_ADDRESS>5th Yan Wu  NXP Semiconductors
Eindhoven, The Netherlands
<EMAIL_ADDRESS>6th Wim van Houtum  Electrical Engineering
Eindhoven University of Technology
NXP Semiconductors
Eindhoven, The Netherlands
<EMAIL_ADDRESS>
###### Abstract

Recently, new types of interference in electric vehicles (EVs), such as
converters switching and/or battery chargers, have been found to degrade the
performance of wireless digital transmission systems. Measurements show that
such an interference is characterized by impulsive behavior and is widely
varying in time. This paper uses recorded data from our EV testbed to analyze
the impulsive interference in the digital audio broadcasting band. Moreover,
we use our analysis to obtain a corresponding interference model. In
particular, we studied the temporal characteristics of the interference and
confirmed that its amplitude indeed exhibits an impulsive behavior. Our
results show that impulsive events span successive received signal samples and
thus indicate a bursty nature. To this end, we performed a data-driven
modification of a well-established model for bursty impulsive interference,
the Markov-Middleton model, to produce synthetic noise realization. We
investigate the optimal symbol detector design based on the proposed model and
show significant performance gains compared to the conventional detector based
on the additive white Gaussian noise assumption.

###### Index Terms:

Impulsive noise, Wireless communication, Machine learning, Electric vehicles

##  I Introduction

(a) I component

(b) Q component

(c) Magnitude

(d) Zoomed-in magnitude

Figure 1: (a) Real part, (b) Imaginary part, (c) magnitude, and (d) roomed in
magnitude of the noise and interference measurements from our EV testbed. The
green rectangular in (c) represents the captured bursty events with impulsive
decision threshold marked with dashed red line

Electric Vehicles (EVs) represent a significant advancement towards
sustainable transportation. However, integrating EVs into the broader mobility
landscape introduces new challenges, particularly in the domain of
electromagnetic interference (EMI) [1, 2]. In particular, the power devices in
a DC-DC converter are inevitable to generate EMI and cause undesirable
interference to the wireless communication systems [3, 4]. One critical area
affected by EMI is the Digital Audio Broadcasting (DAB) system [5]. The
emergence of EVs has underscored the need to understand and mitigate
interference in DAB systems to ensure uninterrupted and high-quality
broadcasting to these vehicles. To overcome the limitation imposed by the EMI
and design an optimal receiver scheme, an accurate interference model is
necessary.

The Middleton impulsive noise model [6, 7] is a common tool for EMI analysis.
More recently, to describe the bursty nature of the interference, the Markov-
Middleton model was proposed in [8, 9], which introduces a correlation between
the impulse events. Moreover, the authors of [8] described an optimal symbol
detector scheme for such a model based on the Bahl-Cocke-Jelinek-Raviv (BCJR)
algorithm [10].

Nevertheless, the modeling of EV-induced interference has been largely
unexplored. Crucially, due to the lack of simple and tractable models, optimal
receiver designs for DAB systems have not been thoroughly investigated. In
this study, we focused on characterizing via field test recordings and
simulating via a modified impulsive interference model, the EMI generated by
EVs, particularly emphasizing on the interference encountered in DAB systems.
By analyzing the interference signatures, we found that the bursty impulsive
EMI behavior is similar to the noise realizations from the Markov-Middleton
model. We adopt a data-driven approach to estimate the key parameters for the
Markov-Middleton model.

Our work establishes a comprehensive connection between the field-recorded EV
interference in the DAB band and a well-established model using statistical
analysis and machine learning tools. In more detail, we used the K-means
algorithms to cluster the bursty events into background noise and multiple
impulsive noise groups. After the algorithm has detected bursty events through
an adaptive threshold over the field test data, we estimate the parameters for
the modified Markov-Middleton model. Finally, we demonstrate how the inferred
parameters can be used to design an optimal receiver for such an interference
model.

The paper is organized as follows: Sec. II describes the experiment setup and
received data characteristics. Sec. III introduces the Markov-Middleton model
for communication over bursty impulsive channels. Sec. IV details the methods
for impulse detection, burst capture, clustering, and model parameter
estimation from the measurements. Sec. V presents a modified Markov-Middleton
model and numerical results for such a model. Sec. VI summarize the paper.

##  II Experiment setup and impulsive noise measurements

###  II-A EV testbed

We employed a DAB signal recorder mounted on an EV with a dual antenna
configuration installed on top of the vehicle to measure the EV interference
within the DAB band. This recorder is operated at a $2.6$ MHz sampling rate,
where the carrier frequency can be adjusted from $174.928$ MHz to $239.2$ MHz
depending on the desired DAB channel. After down-converting the received
signal to baseband, the output data from the recorder is in IQ format, which
represents the complex number. In our testbed, we also include a Global
Positioning System (GPS) and an On-board Diagnostics (OBD) module to record
the location and status of the car. These tools assist us in selecting the
proper dataset for analyzing EV-induced internal interference.

###  II-B Impulsive noise charateristics

For illustration purposes, we assume our received signal as

$Y=X+N+I,$ (1)

where $X$ is the transmitted DAB signal, and $Y$ is the noisy received signal
from our IQ recorder. Here, we assume $N$ is the thermal noise, which follows
a zero mean Gaussian distribution and is independent of the transmitted signal
$X$. $I$ represents an additive EV interference. We specifically choose an
empty DAB channel ($X=0$) recording to focus on the analysis of the EV
interference.

The time-domain data of our measurement, shown in Fig. 1, demonstrate a bursty
impulsive behavior, where the sequence of impulsive noise samples is composed
of correlated impulse events. This type of impulsive interference causes an
elevated noise floor in the frequency domain due to its wideband
characteristics, significantly affecting the detection capability of an
Orthogonal Frequency Division Multiplexing (OFDM) system such as the DAB
receiver. By looking into the consecutive impulsive samples in Fig. 1(d), we
found that each impulsive event is separated by a fixed duration of $10$
$\mu$s, likely generated by power electronic devices operated with $100$ kHz.

##  III Markov-Middleton model

This section summarizes the Markov-Middleton model initially proposed for
powerline communications [8]. This model addresses the statistical nature of
bursty impulsive noise by incorporating the hidden Markov process into the
notable Middleton Class A model. The measurement from our EV testbed shares
similar time domain structures with this model, as illustrated in Fig. 1,
offering a promising framework for modeling the bursty behavior of EV
interference.

$S_{0}$$S_{1}$$S_{2}$$S_{3}$$P_{00}$$P_{01}$$P_{02}$$P_{03}$$P_{10}$$P_{11}$$P_{12}$$P_{13}$$P_{22}$$P_{20}$$P_{21}$$P_{23}$$P_{30}$$P_{33}$$P_{31}$$P_{32}$

Figure 2: State diagram representation of a 4-state Markov-Middleton model

(a) I component

(b) Q component

Figure 3: Histograms of (a) I component and (b) Q component of the background
noise from the measurements Figure 4: Histogram of the magnitude of the
identified bursty events from the measurements. Three clusters based on the
K-mean algorithm with blue, orange, and yellow bars, attributed to State-1,
State-2, and State-3, respectively

This model offers a tractable probability density function for the noise
sample $z$ as

$p(z)=\sum_{m=0}^{M-1}\frac{p_{m}}{\sigma_{m}\sqrt{2\pi}}\exp{\left(-\frac{z^{2}}{2\sigma^{2}_{m}}\right)},$
(2)

where

$p_{m}=\frac{e^{-A}A^{m}/m!}{\sum_{m=0}^{M-1}e^{-A}A^{m}/m!}$ (3)

and

$\sigma^{2}_{m}=\sigma^{2}\frac{m/A+\Gamma}{1+\Gamma},$ (4)

with $M$ denoting the total number of noise states, including the background
noise. Note that in this model, the noise sample $z$ represents the joint
effect of the thermal noise $N$ and interference $I$ in (1). The model
parameters $A$, $\Gamma$, and $\sigma^{2}$ represent the impulsive index, the
background-to-impulse noise ratio, and the total power of $z$, respectively.
Moreover, the Markov-Middleton model includes a parameter $r\in[0,1]$ that
establishes a correlation between noise samples. Then, the state transition
matrix can be constructed as

$P_{ij}=\begin{cases}r+(1-r)p_{j},&i=j\\\
(1-r)p_{j},&\text{otherwise}.\end{cases}$ (5)

The state transition diagram for a 4-state noise model is shown in Fig. 2,
where the state $S_{0}$ is denoted as the background noise. Given the state
transition probability in (5), we can derive the mean duration (in samples) of
each state as

$d_{m}=\frac{1}{(1-r)(1-p_{m})},\quad m=0,\ldots,M-1.$ (6)

As suggested in [8], the correlation parameter $r$ is derived by measuring the
average number of impulse-free consecutive samples. For $m=0$ in (6), we can
derive $r$ as

$r=1-\frac{1}{d_{0}(1-p_{0})}.$ (7)

##  IV Parameter Estimation

Figure 5: Time domain synthetic bursty impulsive noise samples generated from
the modified Markov-Middleton model with parameters in Table I

The optimal receiver based on the Markov-Middleton model assumption requires
accurate parameter estimation. To obtain this, we employed a data-driven
approach and selected a representative dataset consisting of bursty events
extracted from our measurements. We used this dataset to conduct a
comprehensive statistical analysis, which enabled us to explore the connection
with the Markov-Middleton model.

###  IV-A Impulsive noise detection

To statistically analyze impulsive noise, we must separate it from background
noise. To this end, we establish an adaptive threshold as

$th=\alpha\cdot W_{rms},$ (8)

where $W_{rms}$ is the root mean square value of the received signal, and
$\alpha$ represents a scaling factor. The effectiveness of the selected
threshold value $th$ is assessed by analyzing the histogram of the IQ
component of the determined background noise presented in Fig. 3. We observed
that the histogram shape conforms reasonably well to a Gaussian distribution.

TABLE I: Estimated parameters from the measurements State | 0 | 1 | 2 | 3
---|---|---|---|---
$\hat{d}_{m}$ | 105 | 57 | 69 | 186
$\hat{p}_{m}$ | 0.54 | 0.13 | 0.11 | 0.22
$\hat{\sigma}_{m}$ | 0.010 | 0.066 | 0.112 | 0.183
$\hat{r}$ | 0.979

###  IV-B Bursty event detection

As was shown in Fig. 1, the EV-induced impulsive noise has a bursty nature,
where impulses with a similar amplitude appear to occur over a consecutive
time interval. In this study, we define a bursty event as a period of time
where the signal amplitude surpasses the predefined threshold in (8). Such
events are cataloged through the sequence of indices corresponding to the
impulse samples. This study sets the minimum consecutive time for bursty
events detection to $0.5$ ms. In addition, the bursty event decision process
allows a tolerance margin of $0.3$ $\mu$s for a non-impulsive period. As a
result, we detected approximately $3600$ bursty events within an $8$-second
recording time. These events are visually denoted by green rectangles in Fig.
1(c).

###  IV-C K-mean clustering

After identifying all the bursty events in our dataset, we can group them into
a set of finite states for further parameter estimation for the Markov-
Middleton model. Here, we use the one-dimensional K-mean clustering algorithm
to differentiate the bursts into $M-1=3$ impulsive groups based on their
average power. The resulting clusters are presented in Fig. 4, with the
centroids of these clusters indicated by black dashed lines. We also observe
that the magnitude distribution of the bursty events is similar to the
exponential distribution found in [11]. After the clustering phase, every
bursty event is labeled with a unique cluster ID, effectively differentiating
the events based on their mean power. This process facilitates the analysis of
impulsive noise in the measurements under the Markov-Middleton model framework
by capturing its statistical properties.

$-19$$-18$$-17$$-16$$-15$$-14$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$SINR
(dB)BERAWGN detectorIN detector

Figure 6: BER performance of coded BPSK system with different detectors for
the channel with 4-state bursty impulsive noise

###  IV-D Model parameter estimation

To infer the probability of occurrence $\hat{p}_{m}$ for each state from our
measurements, we divide the count of bursty events attributed to each state by
the total samples of the recording. The estimated mean duration $\hat{d}_{m}$
of each state is obtained by counting the average number of samples in the
bursts. It is important to note that the background noise ($S_{0}$) exhibits
the highest probability of occurrence. However, among the interference states,
State-3 ($S_{3}$) is the most probable, which we found to be different than
the Markov-Middleton probability distribution in (3). This mainly results from
the fact that the strongest interference state $S_{3}$ also had the longest
mean duration compared to the other impulsive states. Note that such an
observation was also made by the authors of [11] regarding their power station
measurements, and thus, it’s not unusual in real-world EMI scenarios. Given
the estimated mean duration $\hat{d}_{0}$ and state probability $\hat{p}_{0}$,
we can then calculate the correlation parameter $\hat{r}$ using (7). We also
compute the sample variance for each state from our measurements. The
estimated parameters are listed in Table I.

##  V Optimal Detector Performance

###  V-A Modified Markov-Middleton model

Given the parameters inferred from Sec. IV-D, we can now use the model to
generate the synthetic bursty impulsive noise data. It is important to note
that here, we use the data-inferred parameters $\hat{p}_{m}$,
$\hat{\sigma}_{m}$, and $\hat{r}$ to compute the probability density function
in (2) for each of the impulsive noise states. In contrast, in the original
model, the density functions are calculated based on (3) and (4). The
synthetic bursty impulsive noise output sample generated from our modified
Markov-Middleton model is shown in Fig. 5.

###  V-B Optimal Detector Design

Based on the modified Markov-Middleton model, an optimal maximum a-posterior
detector can be designed to take the interference states into account [8, 9].
This subsection evaluates the bit-error rate for an LDPC-coded binary phase-
shift keying ($X\in\\{-1,1\\}$) system. The codeword length is $64800$, and
the code rate is $1/2$. This communication system setting was also used in
[8]. Results from Fig. 6 show that the IN detector, which incorporates the
modified Markov-Middleton noise states, significantly outperforms the
conventional AWGN detector that only considers the background noise state.

##  VI Conclusions

In this study, we employed a wideband recorder mounted in an EV to capture the
interference plus noise signal in an empty DAB channel. By comprehensively
analyzing the measurements, we identified the bursty impulsive nature of the
interference and proposed a modified Markov-Middleton model with the
parameters estimated from our recordings. This research contributes to
providing a systematic analysis of EV-induced interference, thereby
facilitating the development of robust receiver design. This study aims to
bridge the gap between simple theoretical models and the real-world phenomena
of EV interference.

## Acknowledgment

This work was funded by the RAISE collaboration framework between Eindhoven
University of Technology and NXP, including a PPS-supplement from the Dutch
Ministry of Economic Affairs and Climate Policy

## References

  * [1] K. Pliakostathis, “Research on EMI from modern electric vehicles and their recharging systems,” in _2020 International Symposium on Electromagnetic Compatibility - EMC EUROPE_ , 2020, pp. 1–6.
  * [2] A. Maouloud, M. Klingler, and P. Besnier, “A test setup to assess the impact of EMI produced by on-board electronics on the quality of radio reception in vehicles,” _IEEE Transactions on Electromagnetic Compatibility_ , vol. 63, no. 6, pp. 1844–1855, 2021.
  * [3] X. Gao, D. Su, and Y. Li, “Study on electromagnetic interference of DC/DC converter used in the EV,” in _2015 Asia-Pacific Symposium on Electromagnetic Compatibility (APEMC)_ , 2015, pp. 258–261.
  * [4] M. A. Sakka, J. V. Mierlo, and H. Gualous, “DC/DC converters for electric vehicles,” in _Electric Vehicles_ , S. Soylu, Ed. Rijeka: IntechOpen, 2011, ch. 13. [Online]. Available: https://doi.org/10.5772/17048
  * [5] W. J. van Houtum, “Time-division spatial interference rejection (TDSIR)- procedure.” U.S. Patent 11722197B2, 2022\.
  * [6] D. Middleton, “Statistical-physical models of electromagnetic interference,” _IEEE Transactions on Electromagnetic Compatibility_ , vol. EMC-19, no. 3, pp. 106–127, 1977.
  * [7] ——, “Non-Gaussian noise models in signal processing for telecommunications: new methods an results for class A and class B noise models,” _IEEE Transactions on Information Theory_ , vol. 45, no. 4, pp. 1129–1149, 1999.
  * [8] G. Ndo, F. Labeau, and M. Kassouf, “A Markov-Middleton model for bursty impulsive noise: Modeling and receiver design,” _IEEE Transactions on Power Delivery_ , vol. 28, no. 4, pp. 2317–2325, 2013.
  * [9] D. Fertonani and G. Colavolpe, “On reliable communications over channels impaired by bursty impulse noise,” _IEEE Transactions on Communications_ , vol. 57, no. 7, pp. 2024–2030, 2009.
  * [10] L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate (corresp.),” _IEEE Transactions on Information Theory_ , vol. 20, no. 2, 1974.
  * [11] F. Sacuto, F. Labeau, and B. L. Agba, “Wide band time-correlated model for wireless communications under impulsive noise within power substation,” _IEEE Transactions on Wireless Communications_ , vol. 13, no. 3, pp. 1449–1461, 2014.