# Beyond Smoothing: Unsupervised Graph Representation Learning
with Edge Heterophily Discriminating

Yixin Liu1, Yizhen Zheng1, Daokun Zhang1, Vincent CS Lee1, Shirui Pan2

###### Abstract

Unsupervised graph representation learning (UGRL) has drawn increasing
research attention and achieved promising results in several graph analytic
tasks. Relying on the homophily assumption, existing UGRL methods tend to
smooth the learned node representations along all edges, ignoring the
existence of heterophilic edges that connect nodes with distinct attributes.
As a result, current methods are hard to generalize to heterophilic graphs
where dissimilar nodes are widely connected, and also vulnerable to
adversarial attacks. To address this issue, we propose a novel unsupervised
Graph Representation learning method with Edge hEterophily discriminaTing
(GREET) which learns representations by discriminating and leveraging
homophilic edges and heterophilic edges. To distinguish two types of edges, we
build an edge discriminator that infers edge homophily/heterophily from
feature and structure information. We train the edge discriminator in an
unsupervised way through minimizing the crafted pivot-anchored ranking loss,
with randomly sampled node pairs acting as pivots. Node representations are
learned through contrasting the dual-channel encodings obtained from the
discriminated homophilic and heterophilic edges. With an effective
interplaying scheme, edge discriminating and representation learning can
mutually boost each other during the training phase. We conducted extensive
experiments on 14 benchmark datasets and multiple learning scenarios to
demonstrate the superiority of GREET.

## Introduction

Unsupervised graph representation learning (UGRL) aims to learn low-
dimensional representations from graph-structured data without costly labels
(Kipf and Welling 2016; Hamilton, Ying, and Leskovec 2017; Veličković et al.
2019). Such representations can benefit myriads of downstream tasks, including
node classification, link prediction and node clustering (Zhang, Yin, and
Philip 2022; Pan et al. 2018). In recent years, UGRL has attracted increasing
research attention and been applied to diverse applications, such as
recommender systems (Ge et al. 2020), traffic prediction (Jenkins et al.
2019), and drug molecular modeling (Wang et al. 2021).

Most of the UGRL methods are designed based on the homophily assumption, i.e.,
linked nodes tend to share similar attributes with each other (Hamilton 2020).
Depending on such an assumption, they utilize low-pass filter-like graph
neural networks (GNNs) (Wu et al. 2019; Kipf and Welling 2017; Li et al. 2019)
to smooth the representations of adjacent nodes. Meanwhile, to provide
supervision signals for representation learning, they often use objectives
that preserve local smoothness, i.e., encouraging the representations of nodes
within the same edge (Kipf and Welling 2016; Peng et al. 2020), random walk
(Hamilton, Ying, and Leskovec 2017; Perozzi, Al-Rfou, and Skiena 2014), or
subgraph (Qiu et al. 2020) to have higher similarity to each other. As a
result, all the nodes are forced to have similar representations to their
neighbors. As shown in Fig. 1(a), all the connected nodes are pushed to be
closer in the representation space, even if some of them have moderate feature
similarities that are comparable to randomly sampled node pairs.

With such a representation smoothing mechanism, existing UGRL methods cannot
always generate optimal representations, since real-world graph data are
likely to violate the homophily assumption (Zhu et al. 2020a; Bo et al. 2021).
Actually, apart from homophilic edges that connect similar nodes, there widely
exist heterophilic edges in real-world graphs, which otherwise link dissimilar
nodes. Take social networks as an example, a person may have the same hobby
with some friends, but also have quite different interests with other friends.
Moreover, in a special type of graphs named heterophilic graphs (e.g., Web
Knowledge Base graph Texas, as shown in Fig. 1(b)), heterophilic edges are far
more than homophilic ones (Pei et al. 2020). Besides, graphs in reality
inevitably contain noisy links caused by the uncertain factors in real-world
systems or even adversarial attacks (Zhao et al. 2021a; Chang et al. 2021). In
this situation, smoothing the information along all edges can lead to
indistinguishable node representations, hindering the generalization ability
and robustness of UGRL methods.

(a) Cora (homophilic dataset)

(b) Texas (heterophilic dataset)

Figure 1: The distribution of pair-wise cosine similarity of connected node
pairs (CNP) and randomly sampled node pairs (RNP). (a) The similarity w.r.t.
raw features and representations learned by three UGRL methods (i.e., GAE
(Kipf and Welling 2016), DGI (Veličković et al. 2019), and GRACE (Zhu et al.
2020b)) on Cora dataset. (b) The similarity w.r.t. raw features and
representations learned by GRACE (Zhu et al. 2020b) on Texas dataset.

Considering the existence of homophilic and heterophilic edges, a natural
question can be raised: (Q1) Is it possible to distinguish between two types
of edges in an unsupervised manner? In supervised scenarios, edge
discriminating can be designed as a built-in component in node classification
models, with labels providing direct evidence (Zhao et al. 2021b).
Nevertheless, in unsupervised scenarios, it is hard to discriminate edge types
through only node features and graph structure, especially for the widely
existing edges that connect node pairs with moderate similarities. Even though
a workable unsupervised edge discriminating strategy can be developed, we have
to be faced with a follow-up challenge: (Q2) How to effectively couple edge
discriminating with representation learning into an integrated UGRL model? On
the one hand, for learning informative node representations, we have to make
the best of the discriminated homophilic and heterophilic edges, which
inevitably involve some errors. On the other hand, we shall find a good
interplaying scheme to make edge discriminating and representation learning
mutually boost each other.

To answer both of the aforementioned questions, in this paper, we propose a
novel unsupervised Graph Representation learning method with Edge hEterophily
discriminaTing (GREET). Our theme is to devise an effective unsupervised edge
discriminating component, and integrate it with a dual-channel graph encoding
component into an end-to-end UGRL framework. More concretely, to answer (Q1),
for edge discriminating, we design a trainable edge discriminator with node
features and structural encodings, and learn it in an unsupervised manner. To
provide robust supervision, we design a pivot-anchored ranking loss, which
uses the similarities of random node pairs as pivots, and evaluates the pivot-
relative offside extent delivered by the end-node similarities of
discriminated homophilic and heterophilic edges. Through minimizing the pivot-
anchored ranking loss, we can effectively alleviate the misleading supervision
caused by the ambiguous homophilic/heterophilic edges with moderate
similarities. To answer (Q2), with the discriminated homophilic and
heterophilic edges, we design a dual-channel graph encoding component to
generate node representations, with each channel playing an essential role on
the corresponding edge type view. A robust cross-channel contrasting mechanism
is developed to learn informative node representations. To make the
representation learning well integrated with edge discriminating, we use the
learned node representations to measure node similarities for training the
edge discriminator. Performed with a closed-loop interplay, edge
discriminating and representation learning can increasingly promote each other
during the model training phase. We conduct extensive experiments on 14
benchmark datasets, and the results demonstrate the superior effectiveness and
robustness of our proposed GREET over state-of-the-art methods.

## Related Work

In this section, we briefly review two related research directions. A more
detailed review is available in Appendix A.

Graph Neural Networks (GNNs) aim to model graph-structured data via graph
convolution based on spectral theory (Bruna et al. 2014; Kipf and Welling
2017; Wu et al. 2019) or spatial information aggregation (Hamilton, Ying, and
Leskovec 2017; Veličković et al. 2018; Xu et al. 2019). From the perspective
of graph signal processing, most GNNs can be viewed as low-pass graph filters
that smooth features over graph topology, resulting in similar representations
between adjacent nodes (Nt and Maehara 2019; Wu et al. 2019). This property,
unfortunately, hinders the capability of GNNs in heterophilic graphs where
dissimilar nodes tend to be connected (Lim et al. 2021). Some recent GNNs try
to tackle this issue with novel designs (Zheng et al. 2022a), such as advanced
aggregation functions (Pei et al. 2020; Bo et al. 2021; Jin et al. 2021) and
network architecture (Zhu et al. 2020a; Chien et al. 2021; Suresh et al.
2021). However, they mainly focus on semi-supervised learning, leaving works
on unsupervised learning unexplored.

Unsupervised Graph Representation Learning (UGRL) aims to learn low-
dimensional node representations on graphs. Early methods learn by maximizing
the representation similarity among proximal nodes (within the same random
walk (Perozzi, Al-Rfou, and Skiena 2014; Grover and Leskovec 2016) or same
edge (Kipf and Welling 2016; Pan et al. 2018)). Recent efforts apply
contrastive learning (Chen et al. 2020) to UGRL, which optimize models by
maximizing the agreement between two augmented graph views (Hassani and
Khasahmadi 2020; Zhu et al. 2021, 2020b; Veličković et al. 2019; Qiu et al.
2020; Liu et al. 2022a, b, 2023). However, due to their low-pass filtering GNN
encoders (Kipf and Welling 2017; Wu et al. 2019) and smoothness-increasing
learning objectives (Perozzi, Al-Rfou, and Skiena 2014; Kipf and Welling 2016;
Peng et al. 2020; Qiu et al. 2020), existing UGRL methods tend to smooth the
representations of every connected node pair, leading to their sub-optimal
performance, especially on noisy or heterophilic graphs. Another line of
methods aims to learn representations from multiple edge-based pre-defined
graph views (Qu et al. 2017; Park et al. 2020; Li et al. 2020b; Lee et al.
2020). Differently, GREET learns homophilic and heterophilic from graphs with
a single edge type, which is more challenging.

## Problem Definition

Notation. Define a graph as $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{v_{1},\cdots,v_{n}\\}$ represents the node set and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ represents the edge set.
The edge connecting node $v_{i}$ and $v_{j}$ is denoted as $e_{i,j}$. The
numbers of nodes and edges are denoted as $|\mathcal{V}|=n$ and
$|\mathcal{E}|=m$, respectively. Let $\mathbf{X}\in\mathbb{R}^{n\times d_{f}}$
denote the feature matrix, where the $i$-th row $\mathbf{x}_{i}$ represents
the $d_{f}$-dimensional feature vector of node $v_{i}$. We denote the
adjacency matrix of $\mathcal{G}$ as $\mathbf{A}\in\mathbb{R}^{n\times n}$,
where $\mathbf{A}_{ij}=1$ if $e_{i,j}\in\mathcal{E}$ and $\mathbf{A}_{ij}=0$
otherwise. Using the feature matrix and adjacency matrix, the graph can also
be written as $\mathcal{G}=(\mathbf{A},\mathbf{X})$. The symmetric normalized
adjacency matrix is denoted as
$\tilde{\mathbf{A}}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$, where
$\mathbf{D}$ is the diagonal degree matrix such that
$\mathbf{D}_{ii}=\sum_{j}\mathbf{A}_{ij}$. The Laplacian matrix of the graph
is defined as $\mathbf{L}=\mathbf{D}-\mathbf{A}$, and the symmetric normalized
Laplacian matrix is $\tilde{\mathbf{L}}=\mathbf{I}-\tilde{\mathbf{A}}$.

Problem Description. We aim to solve the node-level unsupervised graph
representation learning (UGRL) problem. The objective is to learn a
representation mapping function $\mathcal{F}:\mathbb{R}^{n\times
d_{f}}\times\mathbb{R}^{n\times n}\rightarrow\mathbb{R}^{n\times d_{r}}$ to
compute a representation matrix
$\mathcal{F}(\mathbf{X},\mathbf{A})=\mathbf{H}$, where the $i$-th row
represents $\mathbf{h}_{i}$, the low-dimensional (i.e., $d_{r}\ll d_{f}$)
representation of node $v_{i}$. These representations can be saved and
utilized for downstream tasks, such as node classification.

## Methodology

This section details our proposed method termed GREET. As illustrated in Fig.
2, GREET is mainly composed of two components: edge discriminating module that
discriminates the homophilic and heterophilic edges, and dual-channel
representation learning module that leverages both types of edges to generate
informative node representations. In edge discriminating module, the edges are
separated into homophilic and heterophilic edges by an edge discriminator. In
dual-channel representation learning module, node representations are
constructed through applying a dual-channel encoding component to perform
graph convolution with low-pass and high-pass filters on the two dicriminated
views respectively. The two main components are trained in a mutually boosting
manner, with a pivot-anchored ranking loss used to train the edge
discriminator, a robust dual-channel contrastive loss employed to learn
informative node representations, and an effective alternating training
strategy leveraged to make the the training on the two components increasingly
reinforce each other.

Figure 2: The overall pipeline of GREET. In the edge discriminating module, an
edge discriminator is built to estimate the homophily probability of edges; in
the dual-channel representation learning module, a dual-channel encoding
component generates node representations from the discriminated homophilic and
heterophilic edge views. The edge discriminator and encoding component are
trained by minimizing a pivot-anchored ranking loss and a robust dual-channel
contrastive loss, respectively.

### Edge Discriminating

In order to distinguish the homophilic and heterophilic edges, we construct an
edge discriminator that learns to estimate the homophily probability of each
edge. Given two adjacent nodes, their homophily probability is essentially
related to two critical factors: node features which incorporate their
semantic contents and structural characteristics which reflect their
topological roles. A direct tool to integrate both structure and feature
information is GNN (Kipf and Welling 2017); however, as we discussed before,
GNN tends to smooth the features and then lose the heterophily-related
knowledge. Thus, we consider an alternative solution, that is, modeling the
structural characteristics with vectorial structural encoding (a.k.a.
positional encoding) (Li et al. 2020a; Dwivedi et al. 2022; Tan et al. 2023).
In this way, the effective evidence can be preserved through concatenating
node structural encodings with raw features. Specifically, we employ a random
walk diffusion process-based structural encoding (Dwivedi et al. 2022) to
capture structural information. The $d_{s}$-dimensional structural encoding
$\mathbf{s}_{i}$ of node $v_{i}$ can be computed by $d_{s}$-step random walk-
based graph diffusion:

$\mathbf{s}_{i}=\left[{\mathbf{T}}_{ii},{\mathbf{T}}_{ii}^{2},\cdots,{\mathbf{T}}_{ii}^{d_{s}}\right]\in\mathbb{R}^{d_{s}},$
(1)

where ${\mathbf{T}}=\mathbf{A}\mathbf{D}^{-1}$ is the random walk transition
matrix. Taking the raw features and structural encodings as input, the edge
discriminator estimates the homophily probability with two MLP layers:

$\displaystyle\mathbf{h}^{\prime}_{i}$
$\displaystyle=\mathrm{MLP}_{1}([\mathbf{x}_{i}\|\mathbf{s}_{i}]),\;\mathbf{h}^{\prime}_{j}=\mathrm{MLP}_{1}([\mathbf{x}_{j}\|\mathbf{s}_{j}]),$
(2) $\displaystyle\theta_{i,j}$
$\displaystyle=\big{(}\mathrm{MLP}_{2}([\mathbf{h}^{\prime}_{i}\|\mathbf{h}^{\prime}_{j}])+\mathrm{MLP}_{2}([\mathbf{h}^{\prime}_{j}\|\mathbf{h}^{\prime}_{i}])\big{)}\big{/}2,$

where $[\cdot\|\cdot]$ denotes the concatenation operation,
$\mathbf{h}^{\prime}_{i}$ is an intermediate embedding of node $v_{i}$, and
$\theta_{i,j}$ is the estimated homophily probability for $e_{i,j}$. To make
the estimation not affected by the direction of edges, we apply the second MLP
layer on the different orders of embedding concatenations.

With the estimated probability $\theta_{i,j}$, our purpose is to sample a
binary homophily indicator ${w}_{{i,j}}$ for edge $e_{i,j}$ from the Bernoulli
distribution ${w}_{{i,j}}\sim\mathrm{Bernoulli}(\theta_{i,j})$, with
${w}_{{i,j}}=1$ indicating homophily and ${w}_{{i,j}}=0$ indicating
heterophily. However, the sampling is non-differentiable, making the
discriminator hard to train. To address this issue, we approximate the binary
indicator ${w}_{{i,j}}$ with Gumbel-Max reparametrization trick (Jang, Gu, and
Poole 2017; Maddison, Mnih, and Teh 2017). Specifically, the discrete
homophily indicator ${w}_{{i,j}}$ is relaxed to a continuous homophily weight
$\hat{w}_{{i,j}}$, which is computed by:

$\hat{w}_{{i,j}}=\mathrm{Sigmoid}\Big{(}\big{(}\theta_{i,j}+\mathrm{log}\delta-\mathrm{log}(1-\delta)\big{)}/\tau_{g}\Big{)},$
(3)

where $\delta\sim\mathrm{Uniform}(0,1)$ is the sampled Gumbel random variate
and $\tau_{g}>0$ is the temperature hyper-parameter. $\hat{w}_{{i,j}}$ tends
to be sharper (closer to $0$ or $1$) with $\tau_{g}$ closer to $0$.

With the estimated edge homophily indicators, we discriminate the original
graph $\mathcal{G}=(\mathbf{A},\mathbf{X})$ into the homophilic and
heterophilic graph views, $\mathcal{G}^{(hm)}=(\mathbf{A}^{(hm)},\mathbf{X})$
and $\mathcal{G}^{(ht)}=(\mathbf{A}^{(ht)},\mathbf{X})$. To make the edge
discriminating trainable, instead of explicitly separating edges into
homophilic and heterophilic categories, we assign a soft weight for each edge
when it works on the homophilic/heterophilic view:

$\mathbf{A}^{(hm)}_{i,j}=\hat{w}_{{i,j}},\;\mathbf{A}^{(ht)}_{i,j}=1-\hat{w}_{{i,j}},\;\mathrm{for}\;e_{i,j}\in\mathcal{E}.$
(4)

### Dual-Channel Encoding

To learn informative representations from homophilic and heterophilic graph
views, we design two different encoders that respectively perform low-pass and
high-pass graph filtering on two distinct views. Our key motivation is to
capture the shared information among similar nodes according to homophilic
edges, while filtering out irrelevant information from dissimilar neighbors
according to heterophilic edges.

Concretely, on the homophilic view where similar nodes are connected to each
other, we smooth the node features along the homophilic structure with a low-
pass graph filter (Yang et al. 2021). The low-pass filtering can capture the
low-frequency information in graph signals and then preserve the shared
knowledge of similar nodes. In GREET, a simple low-pass GNN, SGC (Wu et al.
2019), serves as the low-pass graph filter, which is expressed as:

$\mathbf{H}_{0}^{(hm)}=\mathrm{MLP}^{(hm)}(\mathbf{X}),\;\mathbf{H}_{l}^{(hm)}=\tilde{\mathbf{A}}^{(hm)}\mathbf{H}_{l-1}^{(hm)},$
(5)

where $\tilde{\mathbf{A}}^{(hm)}$ is the symmetric normalized homophilic
adjacency matrix, $l\in\\{1,\cdots,L\\}$ is the layer index, and the final
output $\mathbf{H}_{L}^{(hm)}$ forms the homophilic representation matrix
$\mathbf{H}^{(hm)}$.

Different from the homophilic view, the heterophilic view contains edges
connecting dissimilar nodes. In this view, smoothing features with low-pass
filtering would confuse the information of different nodes and lead to the
loss of discriminative node properties (Bo et al. 2021). To better leverage
the heterophilic edges, we use high-pass graph filtering, the inverse
operation of low-pass filtering, to sharpen the node features along edges and
preserve high-frequency graph signals. In this way, the representations of
dissimilar but connected nodes can be distinguished from each other. From the
perspective of graph signal processing, graph Laplacian operator (i.e.,
multiplying the graph Laplacian matrix $\mathbf{L}$) has been proved to be
effective to capture high-frequency components (Dong et al. 2021; Ma et al.
2021). Accordingly, we design a simple GNN, namely Lap-SGC, to perform high-
pass filtering on the heterophilic view:

$\mathbf{H}_{0}^{(ht)}=\mathrm{MLP}^{(ht)}(\mathbf{X}),\;\mathbf{H}_{l}^{(ht)}=\tilde{\mathbf{L}}^{(ht)}\mathbf{H}_{l-1}^{(ht)},$
(6)

where $l\in\\{1,\cdots,L\\}$, and
$\tilde{\mathbf{L}}^{(ht)}=\mathbf{I}-\alpha\tilde{\mathbf{A}}^{(ht)}$ is the
symmetric normalized Laplacian matrix of heterophilic view with $\alpha$ being
a hyper-parameter to control the strength of high-pass filtering. We take the
final output of Lap-SGC $\mathbf{H}^{(ht)}_{L}$ as the heterophilic
representation matrix $\mathbf{H}^{(ht)}$.

Using two distinct encoders (i.e., SGC and Lap-SGC), now we acquire two groups
of representations that capture low-frequency and high-frequency information
respectively. Final node representations are obtained through concatenating
the representations constructed from both views:
$\mathbf{H}=[\mathbf{H}^{(hm)}\|\mathbf{H}^{(ht)}]$$\in\mathbb{R}^{n\times
d_{r}}$ with its $i$-th row $\mathbf{h}_{i}\in\mathbb{R}^{d_{r}}$ being the
representation vector of node $v_{i}$.

### Model Training

To jointly learn edge distinction and node representations, we carefully
design the learning objectives and training strategy for GREET. Specifically,
we design a pivot-anchored ranking loss to train the edge discriminator, and
construct a robust dual-channel contrastive loss to train the representation
encoders. We also introduce an alternating training strategy to iteratively
optimize two components.

Pivot-Anchored Ranking Loss. The target of the edge discriminator is to
distinguish between homophilic edges (connecting similar nodes) and
heterophilic edges (connecting dissimilar nodes), which is not a trivial task
in an unsupervised scenario. The main challenge is to find the boundary
between “similar” and “dissimilar”. To this end, we propose to use the
randomly sampled node pairs as “pivots” for similarity measurement. Based on
them, we introduce a pivot-anchored ranking loss to make sure that node pairs
connected by homophilic edges are significantly more similar than the pivot
node pairs, while the node pairs connected by heterophilic edges are markedly
more different than the pivot node pairs. In detail, for each
homophilic/heterophilic edge $e_{i,j}\in\mathcal{E}$, its homophilic pivot-
anchored ranking loss $\mathcal{R}^{(hm)}(e_{i,j})$ and heterophilic pivot-
anchored ranking loss $\mathcal{R}^{(ht)}(e_{i,j})$ are respectively defined
as:

$\displaystyle\mathcal{R}^{(hm)}(e_{i,j})$
$\displaystyle=[s_{v_{i^{\prime}},v_{j^{\prime}}}-s_{e_{i,j}}+\gamma^{(hm)}]_{+},\;$
(7) $\displaystyle\mathcal{R}^{(ht)}(e_{i,j})$
$\displaystyle=[s_{e_{i,j}}-s_{v_{i^{\prime}},v_{j^{\prime}}}+\gamma^{(ht)}]_{+},$

where $[x]_{+}=\max(x,0)$ denotes only the positive case of $x$ is considered;
$s_{e_{i,j}}=\cos(\mathbf{h}_{i},\mathbf{h}_{j})$ and
$s_{v_{i^{\prime}},v_{j^{\prime}}}=\cos(\mathbf{h}_{i^{\prime}},\mathbf{h}_{j^{\prime}})$
are respectively the representation-level cosine similarity between the node
pair connected by edge $e_{i,j}$ and the cosine similarity between two
randomly sampled nodes $v_{i^{\prime}}$ and $v_{j^{\prime}}$; $\gamma^{(hm)}$
and $\gamma^{(ht)}$ are respectively the margin parameters for the homophilic
and heterophilic pivot-anchored ranking losses, which can force the similarity
difference to reach a significant level.

Table 1: Results in terms of classification accuracies (in percent $\pm$
standard deviation) on homophilic benchmarks. “*” indicates that results are
borrowed from the original papers. OOM indicates Out-Of-Memory on a 24GB GPU.
The best and runner-up results are highlighted with bold and underline,
respectively.

Methods |  Cora |  CiteSeer |  PubMed |  Wiki-CS |  Amz. Comp. |  Amz. Photo |  Co. CS |  Co. Physics
---|---|---|---|---|---|---|---|---
GCN* |  ${81.5}$ |  ${70.3}$ |  ${79.0}$ |  $76.89{\scriptstyle\pm 0.37}$ |  $86.34{\scriptstyle\pm 0.48}$ |  $92.35{\scriptstyle\pm 0.25}$ |  $93.10{\scriptstyle\pm 0.17}$ |  $95.54{\scriptstyle\pm 0.19}$
GAT* |  ${83.0}$ |  ${72.5}$ |  ${79.0}$ |  $77.42{\scriptstyle\pm 0.19}$ |  $87.06{\scriptstyle\pm 0.35}$ |  $92.64{\scriptstyle\pm 0.42}$ |  $92.41{\scriptstyle\pm 0.27}$ |  $95.45{\scriptstyle\pm 0.17}$
MLP |  $56.11{\scriptstyle\pm 0.34}$ |  $56.91{\scriptstyle\pm 0.42}$ |  $71.35{\scriptstyle\pm 0.05}$ |  $72.02{\scriptstyle\pm 0.21}$ |  $73.88{\scriptstyle\pm 0.10}$ |  $78.54{\scriptstyle\pm 0.05}$ |  $90.42{\scriptstyle\pm 0.08}$ |  $93.54{\scriptstyle\pm 0.05}$
DeepWalk |  $69.47{\scriptstyle\pm 0.55}$ |  $58.82{\scriptstyle\pm 0.61}$ |  $69.87{\scriptstyle\pm 1.25}$ |  $74.35{\scriptstyle\pm 0.06}$ |  $85.68{\scriptstyle\pm 0.06}$ |  $89.44{\scriptstyle\pm 0.11}$ |  $84.61{\scriptstyle\pm 0.22}$ |  $91.77{\scriptstyle\pm 0.15}$
node2vec |  $71.24{\scriptstyle\pm 0.89}$ |  $47.64{\scriptstyle\pm 0.77}$ |  $66.47{\scriptstyle\pm 1.00}$ |  $71.79{\scriptstyle\pm 0.05}$ |  $84.39{\scriptstyle\pm 0.08}$ |  $89.67{\scriptstyle\pm 0.12}$ |  $85.08{\scriptstyle\pm 0.03}$ |  $91.19{\scriptstyle\pm 0.04}$
GAE |  $71.07{\scriptstyle\pm 0.39}$ |  $65.22{\scriptstyle\pm 0.43}$ |  $71.73{\scriptstyle\pm 0.92}$ |  $70.15{\scriptstyle\pm 0.01}$ |  $85.27{\scriptstyle\pm 0.19}$ |  $91.62{\scriptstyle\pm 0.13}$ |  $90.01{\scriptstyle\pm 0.71}$ |  $94.92{\scriptstyle\pm 0.07}$
VGAE |  $79.81{\scriptstyle\pm 0.87}$ |  $66.75{\scriptstyle\pm 0.37}$ |  $77.16{\scriptstyle\pm 0.31}$ |  $75.63{\scriptstyle\pm 0.19}$ |  $86.37{\scriptstyle\pm 0.21}$ |  $92.20{\scriptstyle\pm 0.11}$ |  $92.11{\scriptstyle\pm 0.09}$ |  $94.52{\scriptstyle\pm 0.00}$
DGI |  $82.29{\scriptstyle\pm 0.56}$ |  $71.49{\scriptstyle\pm 0.14}$ |  $77.43{\scriptstyle\pm 0.84}$ |  $75.73{\scriptstyle\pm 0.13}$ |  $84.09{\scriptstyle\pm 0.39}$ |  $91.49{\scriptstyle\pm 0.25}$ |  $91.95{\scriptstyle\pm 0.40}$ |  $94.57{\scriptstyle\pm 0.38}$
GMI |  $82.51{\scriptstyle\pm 1.47}$ |  $71.56{\scriptstyle\pm 0.56}$ |  $79.83{\scriptstyle\pm 0.90}$ |  $75.06{\scriptstyle\pm 0.13}$ |  $81.76{\scriptstyle\pm 0.52}$ |  $90.72{\scriptstyle\pm 0.33}$ |  OOM |  OOM
MVGRL |  $\underline{83.03{\scriptstyle\pm 0.27}}$ |  $\underline{72.75{\scriptstyle\pm 0.46}}$ |  $79.63{\scriptstyle\pm 0.38}$ |  $77.97{\scriptstyle\pm 0.18}$ |  $87.09{\scriptstyle\pm 0.27}$ |  $92.01{\scriptstyle\pm 0.13}$ |  $91.97{\scriptstyle\pm 0.19}$ |  $95.53{\scriptstyle\pm 0.10}$
GRACE |  $80.08{\scriptstyle\pm 0.53}$ |  $71.41{\scriptstyle\pm 0.38}$ |  $80.15{\scriptstyle\pm 0.34}$ |  $79.16{\scriptstyle\pm 0.36}$ |  $87.21{\scriptstyle\pm 0.44}$ |  $92.65{\scriptstyle\pm 0.32}$ |  $92.78{\scriptstyle\pm 0.23}$ |  $95.39{\scriptstyle\pm 0.32}$
GCA |  $80.39{\scriptstyle\pm 0.42}$ |  $71.21{\scriptstyle\pm 0.24}$ |  $\mathbf{80.37{\scriptstyle\pm 0.75}}$ |  $\underline{79.35{\scriptstyle\pm 0.12}}$ |  $87.84{\scriptstyle\pm 0.27}$ |  $92.78{\scriptstyle\pm 0.17}$ |  $\underline{93.32{\scriptstyle\pm 0.12}}$ |  $\underline{95.87{\scriptstyle\pm 0.15}}$
BGRL |  $81.08{\scriptstyle\pm 0.17}$ |  $71.59{\scriptstyle\pm 0.42}$ |  $79.97{\scriptstyle\pm 0.36}$ |  $78.74{\scriptstyle\pm 0.22}$ |  $\mathbf{88.92{\scriptstyle\pm 0.33}}$ |  $\mathbf{93.24{\scriptstyle\pm 0.29}}$ |  ${93.26{\scriptstyle\pm 0.36}}$ |  $95.76{\scriptstyle\pm 0.38}$
GREET |  $\mathbf{83.81{\scriptstyle\pm 0.87}}$ |  $\mathbf{73.08{\scriptstyle\pm 0.84}}$ |  $\underline{80.29{\scriptstyle\pm 1.00}}$ |  $\mathbf{80.68{\scriptstyle\pm 0.31}}$ |  $\underline{87.94{\scriptstyle\pm 0.35}}$ |  $\underline{92.85{\scriptstyle\pm 0.31}}$ |  $\mathbf{94.65{\scriptstyle\pm 0.18}}$ |  $\mathbf{96.13{\scriptstyle\pm 0.12}}$

Through performing expectation over all homophilic and heterophilic edges
respectively, we can obtain the expected homophilic and heterophilic pivot-
anchored ranking losses $\mathcal{L}_{r}^{(hm)}$ and $\mathcal{L}_{r}^{(ht)}$
as:

$\displaystyle\mathcal{L}_{r}^{(hm)}=\mathop{{\mathbb{E}}}\limits_{e_{i,j}\sim\Pi(\hat{w}_{i,j})}\mathcal{R}^{(hm)}(e_{i,j})$
$\displaystyle=\frac{1}{\hat{W}^{(hm)}}\sum_{e_{i,j}\in\mathcal{E}}\hat{w}_{i,j}\mathcal{R}^{(hm)}(e_{i,j}),$
(8)
$\displaystyle\mathcal{L}_{r}^{(ht)}=\mathop{{\mathbb{E}}}\limits_{e_{i,j}\sim\Pi(1-\hat{w}_{i,j})}\mathcal{R}^{(ht)}(e_{i,j})$
$\displaystyle=\frac{1}{\hat{W}^{(ht)}}\sum_{e_{i,j}\in\mathcal{E}}(1-\hat{w}_{i,j})\mathcal{R}^{(ht)}(e_{i,j}),$

where $\Pi(\hat{w}_{i,j})$ and $\Pi(1-\hat{w}_{i,j})$ are the multinomial
distributions parameterized by homophilic and heterophilic edge weights
$\hat{w}_{i,j}$ and $1-\hat{w}_{i,j}$; $\hat{W}^{(hm)}$ and $\hat{W}^{(ht)}$
are the normalization terms which are respectively obtained by summing over
all homophilic edge weights $\hat{w}_{i,j}$ and heterophilic edge weights
$1-\hat{w}_{i,j}$. Through summing up the two expected losses, the overall
pivot-anchored ranking loss to be minimized can be obtained as:

$\mathcal{L}_{r}=\mathcal{L}_{r}^{(hm)}+\mathcal{L}_{r}^{(ht)}.$ (9)

Robust Dual-Channel Contrastive Loss. To provide supervision for node
representation learning, we use a robust contrasting mechanism that forces our
model to generate semantically consistent representations from two distinct
graph views. More importantly, such a learning target can effectively combat
negative impacts caused by the small amounts of false discriminated edges,
through implicitly using the generated representations to reconstruct feature-
level similarity. Specially, for each node $v_{i}\in\mathcal{V}$, we first
find another node $v_{j}$ within $v_{i}$’s top-$k$ similar node set measured
by features, $\mathcal{N}_{i}=\mathrm{kNN}(v_{i},k)$, then compare their
representations across homophilic and heterophilic views. To provide a fair
similarity measure, we project node representations delivered by two views
into a latent space with two learnable MLPs respectively, then use the
similarity between the projections in the latent space as node representation
similarity measuring metric. Inspired by the InfoNCE contrastive loss (Chen et
al. 2020; Zhu et al. 2020b), the robust cross-channel contrastive loss is
defined as:

$\displaystyle\mathcal{L}_{c}=-\frac{1}{n}\sum_{v_{i}\in\mathcal{V}}\bigg{[}\frac{1}{2|\mathcal{N}_{i}|}\sum_{v_{j}\in\mathcal{N}_{i}}\bigg{(}\log\frac{e^{\cos\left(\mathbf{z}^{(hm)}_{i},\mathbf{z}^{(ht)}_{j}\right)/\tau_{c}}}{\sum_{v_{k}\in\mathcal{V}\backslash
v_{i}}e^{\cos\left(\mathbf{z}^{(hm)}_{i},\mathbf{z}^{(ht)}_{k}\right)/\tau_{c}}}$
(10)
$\displaystyle+\log\frac{e^{\cos\left(\mathbf{z}^{(ht)}_{i},\mathbf{z}^{(hm)}_{j}\right)/\tau_{c}}}{\sum_{v_{k}\in\mathcal{V}\backslash
v_{i}}e^{\cos\left(\mathbf{z}^{(ht)}_{i},\mathbf{z}^{(hm)}_{k}\right)/\tau_{c}}}\bigg{)}\bigg{]},$

where $\mathbf{z}^{(hm)}_{i}$ and $\mathbf{z}^{(ht)}_{i}$ are respectively the
projections of $v_{i}$’s homophilic-view and heterophilic-view representations
in the latent space, $\tau_{c}$ is a temperature hyper-parameter for
contrastive learning and $\cos(\cdot,\cdot)$ is cosine similarity. In
practice, we calculate contrastive loss in an mini-batch manner (Chen et al.
2020) for large graph datasets.

Training Strategy. In our method, the training of edge discriminating module
relies on node representations to measure node similarity; the representation
learning module, in turn, generates representations from the two views
delivered by edge discriminating. To train two components effectively, we
utilize an alternating training strategy to optimize edge discriminating and
node representation learning alternately, with the two components boosting
each other increasingly. To sum up, the overall optimization objective can be
written as $\mathcal{L}=\mathcal{L}_{r}+\mathcal{L}_{c}$. To improve the
generalization ability of the representation learning module, we adopt data
augmentation that increases the diversity of data for model training (You et
al. 2020). Concretely, we employ two simple but effective augmentation
strategies, feature masking and edge dropping (Zhu et al. 2020b; You et al.
2020), to perturb the features and structures of both views. We present the
algorithmic description in Appendix B.

Scalability Extension. To improve the scalability of GREET, we introduce the
following mechanisms. (1) For structural encoding computation, we use sparse
matrix multiplication to calculate graph diffusion, which avoids
$\mathcal{O}(n^{3})$ time complexity. (2) To find similar nodes in
$\mathcal{L}_{c}$, we use locality-sensitive approximation algorithm (Fatemi,
Asri, and Kazemi 2021) to obtain kNN nodes. (3) We calculate $\mathcal{L}_{c}$
within a mini-batch of nodes instead of all nodes, reducing the time
complexity from $\mathcal{O}(n^{2})$ to $\mathcal{O}(nb)$, where $b$ is the
size of mini-batch. Note that the structural encodings and kNN nodes can be
pre-computed at once before model training. Experiments on CoAuthor Physics
dataset verify that GREET is able to learn on graphs with over 34k nodes and
495k edges. Detailed complexity analysis of GREET can be found in Appendix C.

## Experiments

### Experimental Settings

Datasets. We take transductive node classification as the downstream task to
evaluate the effectiveness of the learned representations. Our experiments are
conducted on 14 commonly used benchmark datasets, including 8 homophilic graph
datasets (i.e., Cora, CiteSeer, PubMed, Wiki-CS, Amazon Computer, Amazon
Photo, CoAuthor CS, and CoAuthor Physics (Sen et al. 2008; Mernyei and Cangea
2020; Shchur et al. 2018)) and 6 heterophilic graph datasets (i.e., Chameleon,
Squirrel, Actor, Cornell, Texas, and Wisconsin (Pei et al. 2020)). We split
all datasets following the public splits (Yang, Cohen, and Salakhudinov 2016;
Kipf and Welling 2017; Pei et al. 2020) or commonly used splits (Zhu et al.
2021; Thakoor et al. 2022). The details of datasets are summarized in Appendix
D.

Baselines. We compare GREET with three groups of baseline methods: (1)
supervised/semi-supervised learning methods (i.e., GCN (Kipf and Welling
2017), GAT (Veličković et al. 2018), and MLP), (2) conventional UGRL methods
(i.e., node2vec (Grover and Leskovec 2016), DeepWalk (Perozzi, Al-Rfou, and
Skiena 2014), GAE, and VGAE (Kipf and Welling 2016)), and (3) contrastive UGRL
methods (i.e., DGI (Veličković et al. 2019), GMI (Peng et al. 2020), MVGRL
(Hassani and Khasahmadi 2020), GRACE (Zhu et al. 2020b), GCA (Zhu et al.
2021), and BGRL (Thakoor et al. 2022)). For the experiments on heterophilic
graphs, we further consider 4 heterophily-aware GNNs as baselines, including
Geom-GCN (Pei et al. 2020), H2GCN (Zhu et al. 2020a), FAGCN (Bo et al. 2021),
and GPR-GNN (Chien et al. 2021). We further equip GRACE with FAGCN encoder
(termed GRACE-FA) for comparison.

Table 2: Results in terms of classification accuracies (in percent) on
heterophilic benchmarks. “*” indicates that results are borrowed from the
original papers. The best and runner-up results are highlighted with bold and
underline, respectively. Results with standard deviation are in Appendix G.

Methods | Cham. | Squ. | Actor | Cor. | Texas | Wis.
---|---|---|---|---|---|---
GCN | $59.63$ | $36.28$ | $30.83$ | $57.03$ | $60.00$ | $56.47$
GAT | $56.38$ | $32.09$ | $28.06$ | $59.46$ | $61.62$ | $54.71$
MLP | $46.91$ | $29.28$ | $35.66$ | $81.08$ | $81.62$ | $84.31$
Geom-GCN* | ${60.90}$ | ${38.14}$ | ${31.63}$ | ${60.81}$ | ${67.57}$ | ${64.12}$
H2GCN* | $59.39$ | $37.90$ | $\underline{35.86}$ | $\underline{82.16}$ | $\underline{84.86}$ | $\mathbf{86.67}$
FAGCN | $\underline{63.44}$ | $\underline{41.17}$ | $35.74$ | $81.35$ | $84.32$ | $83.33$
GPR-GNN | $61.58$ | $39.65$ | $35.27$ | $81.89$ | $83.24$ | $84.12$
DeepWalk | $47.74$ | $32.93$ | $22.78$ | $39.18$ | $46.49$ | $33.53$
node2vec | $41.93$ | $22.84$ | $28.28$ | $42.94$ | $41.92$ | $37.45$
GAE | $33.84$ | $28.03$ | $28.03$ | $58.85$ | $58.64$ | $52.55$
VGAE | $35.22$ | $29.48$ | $26.99$ | $59.19$ | $59.20$ | $56.67$
DGI | $39.95$ | $31.80$ | $29.82$ | $63.35$ | $60.59$ | $55.41$
GMI | $46.97$ | $30.11$ | $27.82$ | $54.76$ | $50.49$ | $45.98$
MVGRL | $51.07$ | $35.47$ | $30.02$ | $64.30$ | $62.38$ | $62.37$
GRACE | $48.05$ | $31.33$ | $29.01$ | $54.86$ | $57.57$ | $50.00$
GRACE-FA | $52.68$ | $35.97$ | $32.55$ | $67.57$ | $64.05$ | $63.73$
GCA | $49.80$ | $35.50$ | $29.65$ | $55.41$ | $59.46$ | $50.78$
BGRL | $47.46$ | $32.64$ | $29.86$ | $57.30$ | $59.19$ | $52.35$
GREET | $\mathbf{63.64}$ | $\mathbf{42.29}$ | $\mathbf{36.55}$ | $\mathbf{85.14}$ | $\mathbf{87.03}$ | $\underline{84.90}$

Experimental details.  For GREET and the unsupervised baselines, we follow the
evaluation protocol that is widely used in previous UGRL methods (Zhu et al.
2020b, 2021). Specifically, in training phase, the model are trained without
supervision; then, in evaluation phase, the learned representations are frozen
and used to train and test with a logistic regression classifier. For the
superivsed/semi-supervised baselines, we directly train the models in an end-
to-end fashion where labels are available for representation learning, and
perform evaluation with the trained models. For all datasets, we report the
averaged test accuracy and standard deviation over 10 runs of experiments. We
conduct grid search to choice the best hyper-parameters on validation set. We
also search the best hyper-parameter for baseline methods during reproduction.
Specific hyper-parameter settings and more implementation details are in
Appendix E. The experiments that investigate the parameter sensitivity of
GREET are demonstrated in Appendix F. The code of GREET is available at
https://github.com/yixinliu233/GREET.

### Experimental Results

Performance Comparison.  The node classification results on 8 homophilic
datasets and 6 heterophilic datasets are presented in Table 1 and Table 2,
respectively. First of all, we observe that GREET outperforms all baseline
methods in 10 out of 14 benchmarks and achieves the runner-up performance on
the rest 4 benchmarks. The superior performance indicates the distinction and
exploitation of homophilic and heterophilic edges can universally benefit
representation learning, since two types of edges widely exist in diverse
real-world graph data. In Table 2, we find that GREET significantly
outperforms conventional and contrastive UGRL methods. The main reason is that
these UGRL methods constantly smooth the representations along heterophilic
edges, making the representations indistinguishable. In contrast, GREET
detects the heterophilic edges and sharpens the representations along them
with a high-pass graph filter, leading to even better performance than semi-
supervised GNNs for heterophilic graphs. Notably, equipping contrastive UGRL
methods with heterophily-aware encoders (e.g., GRACE-FA) only yields minor
performance gain, indicating that adapting URGL methods to heterophilic graphs
needs crafted designs rather than simply modifying the encoder.

(a) Random (Cora) (b) Random (Citeseer)

(c) Metattack (Cora) (d) Metattack (Citeseer)

Figure 3: Results of different models under random attack (a,b) and Metattack
(c,d).

Robustness Analysis.  In this experiment, we verify the robustness of GREET on
graph data under adversarial attack. We perturb the graph structure with two
non-targeted adversarial attack methods, i.e., random attack (randomly adding
noisy edges to the original topology) and Metattack (Zügner and Günnemann
2019), and test the node classification accuracy on the representations
learned from perturbed graphs. The node classification results under different
perturbation rates are shown in Fig. 3. From the figure, we can witness that
GREET consistently outperforms the baselines by a large margin. Moreover, with
the increase of perturbation rate, the advantage of our method becomes more
significant. The experimental results demonstrate the strong robustness of
GREET against adversarial attack on graph strutures.

Table 3: Performance of GREET and its variants.

Variants | Cornell | Texas | Cora | CiteSeer
---|---|---|---|---
GREET | ${85.14{\scriptstyle\pm 4.87}}$ | ${87.03{\scriptstyle\pm 2.36}}$ | $83.81{\scriptstyle\pm 0.87}$ | $73.08{\scriptstyle\pm 0.84}$
w/o Eg. Dis. | $82.16{\scriptstyle\pm 6.64}$ | $82.97{\scriptstyle\pm 5.80}$ | $82.19{\scriptstyle\pm 0.74}$ | $72.18{\scriptstyle\pm 0.58}$
w/o Du. Enc. | $77.57{\scriptstyle\pm 6.05}$ | $80.54{\scriptstyle\pm 4.32}$ | $80.81{\scriptstyle\pm 0.54}$ | $72.24{\scriptstyle\pm 0.55}$
GNN Dis. | $82.97{\scriptstyle\pm 6.05}$ | $82.97{\scriptstyle\pm 5.68}$ | $83.62{\scriptstyle\pm 0.74}$ | $72.58{\scriptstyle\pm 0.93}$
w/o Pivot | $79.19{\scriptstyle\pm 4.99}$ | $82.16{\scriptstyle\pm 5.01}$ | $82.84{\scriptstyle\pm 0.76}$ | $72.54{\scriptstyle\pm 0.69}$
NCE Loss | $77.57{\scriptstyle\pm 6.17}$ | $80.00{\scriptstyle\pm 6.75}$ | $82.48{\scriptstyle\pm 0.49}$ | $70.00{\scriptstyle\pm 1.18}$
Hom. Rep. | $75.95{\scriptstyle\pm 4.43}$ | $67.57{\scriptstyle\pm 4.52}$ | $83.16{\scriptstyle\pm 0.71}$ | $70.60{\scriptstyle\pm 2.04}$
Het. Rep. | $82.97{\scriptstyle\pm 5.55}$ | $83.78{\scriptstyle\pm 5.67}$ | $66.77{\scriptstyle\pm 3.02}$ | $68.76{\scriptstyle\pm 1.44}$

Ablation Study.  To examine the contributions of each component and key design
in GREET, we conduct experiments on several variants of GREET and the results
are shown in Table 3. We first remove the key components, i.e. edge
discriminator (w/o Eg. Dis.) and dual-channel encoding (w/o Du. Enc.), to
investigate their effects. The results show that both components are critical
to GREET, and the dual-channel encoding seems to contribute more. Then, we
discuss the effects of three key designs (i.e., structural encoding in Eq.(2),
pivot-anchored ranking loss, and robust dual-channel contrastive loss) by
replacing them with alternative designs (i.e., GNN-based discriminator without
structural encodings, ranking loss between homophilic and heterophilic edges
without pivot, and InfoNCE (Chen et al. 2020) loss) respectively. We can
witness that GREET consistently outperform three variants, which demonstrates
the superiority of the our designs. Finally, we investigate the quality of the
representations generated from homophily view (Hom. Rep.) and heterophilic
view (Het. Rep.). As expected, the homophilic representations are more
effective on homophilic graphs (i.e., Cora and CiteSeer), while the
heterophilic representations favor heterophilic graphs (i.e., Cornell and
Texas). Jointly considering the representations from two views can produce the
best results, because both of them contain critical and distinctive
information from different perspectives.

(a) Cora

(b) Cora-RA

(c) Texas

Figure 4: The distribution of pair-wise cosine similarity of connected node
pairs (CNP) and randomly sampled node pairs (RNP) w.r.t. the representations
learned by GREET on (a) Cora dataset, (b) Cora dataset under random attack
with $50\%$ perturbation rate, and (c) Texas dataset.

Visualization.  To investigate the property of the representations learned by
GREET, we visualize the pair-wise representation similarity of Cora dataset,
perturbed Cora dataset, and Texas dataset. As shown in Fig. 4(a), for most
edges in Cora dataset, the representations of end nodes are similar; notably,
for a small fraction of edges that are identified to be heterophilic, GREET
forces their similarities to be close to $0$. Such observation proves that
GREET can separate homophilic and heterophilic edges and generate
distinguishable representations accordingly. In the perturbed Cora dataset
(Fig. 4(b)), a considerable part of edges are detected to be heterophilic and
then have dissimilar end node representations. Thanks to such a capability of
identifying the noisy edges, GREET shows a strong robustness against
structural attack in Fig. 3(a). A similar phenomenon can be found in the
heterophilic dataset Texas (Fig. 4(c)) where the bulk of edges are recognized
as heterophilic edges. The separation of two types of edges brings more
informative representations, resulting in the superior performance of GREET on
heterophilic graphs.

## Conclusion

In this paper, we propose a novel method named GREET for unsupervised graph
representation learning (UGRL). Our core idea is to discriminate and leverage
homophilic and heterophilic edges to generate high-quality node
representations. We employ an edge discriminator to distinguish two types of
edges, and construct a dual-channel encoding component to generate
representations according to edge distinction. We carefully design a pivot-
anchored ranking loss and robust dual-channel contrastive loss for model
training, with an alternating strategy to train both components in a mutually
boosting manner. Extensive experiments reveal the effectiveness and robustness
of our method.

## Acknowledgements

The corresponding author is Shirui Pan. This work was supported by ARC Future
Fellowship (No. FT210100097).

## References

  * Bo et al. (2021) Bo, D.; Wang, X.; Shi, C.; and Shen, H. 2021.  Beyond Low-frequency Information in Graph Convolutional Networks.  In _AAAI_ , 3950–3957.
  * Bruna et al. (2014) Bruna, J.; Zaremba, W.; Szlam, A.; and LeCun, Y. 2014.  Spectral networks and locally connected networks on graphs.  In _ICLR_.
  * Chang et al. (2021) Chang, H.; Rong, Y.; Xu, T.; Bian, Y.; Zhou, S.; Wang, X.; Huang, J.; and Zhu, W. 2021.  Not All Low-Pass Filters are Robust in Graph Convolutional Networks.  In _NeurIPS_.
  * Chen et al. (2020) Chen, T.; Kornblith, S.; Norouzi, M.; and Hinton, G. 2020.  A simple framework for contrastive learning of visual representations.  In _ICML_ , 1597–1607. PMLR.
  * Chien et al. (2021) Chien, E.; Peng, J.; Li, P.; and Milenkovic, O. 2021.  Adaptive Universal Generalized PageRank Graph Neural Network.  In _ICLR_.
  * Defferrard, Bresson, and Vandergheynst (2016) Defferrard, M.; Bresson, X.; and Vandergheynst, P. 2016.  Convolutional neural networks on graphs with fast localized spectral filtering.  In _NeurIPS_ , volume 29.
  * Ding et al. (2022) Ding, K.; Xu, Z.; Tong, H.; and Liu, H. 2022.  Data augmentation for deep graph learning: A survey.  _SIGKDD Explorations_.
  * Dong et al. (2021) Dong, Y.; Ding, K.; Jalaian, B.; Ji, S.; and Li, J. 2021.  AdaGNN: Graph Neural Networks with Adaptive Frequency Response Filter.  In _CIKM_ , 392–401.
  * Dwivedi et al. (2022) Dwivedi, V. P.; Luu, A. T.; Laurent, T.; Bengio, Y.; and Bresson, X. 2022.  Graph Neural Networks with Learnable Structural and Positional Representations.  In _ICLR_.
  * Fatemi, Asri, and Kazemi (2021) Fatemi, B.; Asri, L. E.; and Kazemi, S. M. 2021.  SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks.  In _NeurIPS_.
  * Fu et al. (2020) Fu, D.; Xu, Z.; Li, B.; Tong, H.; and He, J. 2020.  A view-adversarial framework for multi-view network embedding.  In _CIKM_ , 2025–2028.
  * Ge et al. (2020) Ge, S.; Wu, C.; Wu, F.; Qi, T.; and Huang, Y. 2020.  Graph enhanced representation learning for news recommendation.  In _WWW_ , 2863–2869.
  * Grover and Leskovec (2016) Grover, A.; and Leskovec, J. 2016.  node2vec: Scalable feature learning for networks.  In _SIGKDD_ , 855–864.
  * Hamilton, Ying, and Leskovec (2017) Hamilton, W.; Ying, Z.; and Leskovec, J. 2017.  Inductive representation learning on large graphs.  In _NeurIPS_.
  * Hamilton (2020) Hamilton, W. L. 2020.  Graph representation learning.  _Synthesis Lectures on Artifical Intelligence and Machine Learning_ , 14(3): 1–159.
  * Hassani and Khasahmadi (2020) Hassani, K.; and Khasahmadi, A. H. 2020.  Contrastive multi-view representation learning on graphs.  In _ICML_ , 4116–4126. PMLR.
  * He et al. (2020) He, K.; Fan, H.; Wu, Y.; Xie, S.; and Girshick, R. 2020.  Momentum contrast for unsupervised visual representation learning.  In _CVPR_ , 9729–9738.
  * Jang, Gu, and Poole (2017) Jang, E.; Gu, S.; and Poole, B. 2017.  Categorical reparameterization with gumbel-softmax.  In _ICLR_.
  * Jenkins et al. (2019) Jenkins, P.; Farag, A.; Wang, S.; and Li, Z. 2019.  Unsupervised representation learning of spatial data via multimodal embedding.  In _CIKM_ , 1993–2002.
  * Jin et al. (2021) Jin, D.; Yu, Z.; Huo, C.; Wang, R.; Wang, X.; He, D.; and Han, J. 2021.  Universal Graph Convolutional Networks.  In _NeurIPS_ , volume 34.
  * Kipf and Welling (2016) Kipf, T. N.; and Welling, M. 2016.  Variational graph auto-encoders.  In _NeurIPS Workshop_.
  * Kipf and Welling (2017) Kipf, T. N.; and Welling, M. 2017.  Semi-Supervised Classification with Graph Convolutional Networks.  In _ICLR_.
  * Lee et al. (2020) Lee, Y.-C.; Seo, N.; Han, K.; and Kim, S.-W. 2020.  Asine: Adversarial signed network embedding.  In _SIGIR_ , 609–618.
  * Li et al. (2020a) Li, P.; Wang, Y.; Wang, H.; and Leskovec, J. 2020a.  Distance encoding: Design provably more powerful neural networks for graph representation learning.  In _NeurIPS_ , volume 33.
  * Li et al. (2019) Li, Q.; Wu, X.-M.; Liu, H.; Zhang, X.; and Guan, Z. 2019.  Label efficient semi-supervised learning via graph filtering.  In _CVPR_ , 9582–9591.
  * Li et al. (2020b) Li, Y.; Tian, Y.; Zhang, J.; and Chang, Y. 2020b.  Learning signed network embedding via graph attention.  In _AAAI_ , volume 34, 4772–4779.
  * Lim et al. (2021) Lim, D.; Hohne, F.; Li, X.; Huang, S. L.; Gupta, V.; Bhalerao, O.; and Lim, S. N. 2021.  Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods.  In _NeurIPS_ , volume 34.
  * Liu et al. (2023) Liu, Y.; Ding, K.; Liu, H.; and Pan, S. 2023.  GOOD-D: On Unsupervised Graph Out-Of-Distribution Detection.  In _WSDM_.
  * Liu et al. (2022a) Liu, Y.; Jin, M.; Pan, S.; Zhou, C.; Zheng, Y.; Xia, F.; and Yu, P. 2022a.  Graph self-supervised learning: A survey.  _IEEE TKDE_.
  * Liu et al. (2021) Liu, Y.; Li, Z.; Pan, S.; Gong, C.; Zhou, C.; and Karypis, G. 2021.  Anomaly detection on attributed networks via contrastive self-supervised learning.  _IEEE TNNLS_.
  * Liu et al. (2022b) Liu, Y.; Zheng, Y.; Zhang, D.; Chen, H.; Peng, H.; and Pan, S. 2022b.  Towards unsupervised deep graph structure learning.  In _WWW_ , 1392–1403.
  * Ma et al. (2021) Ma, Y.; Liu, X.; Zhao, T.; Liu, Y.; Tang, J.; and Shah, N. 2021.  A unified view on graph neural networks as graph signal denoising.  In _CIKM_ , 1202–1211.
  * Ma et al. (2019) Ma, Y.; Wang, S.; Aggarwal, C. C.; Yin, D.; and Tang, J. 2019.  Multi-dimensional graph convolutional networks.  In _SDM_ , 657–665. SIAM.
  * Maddison, Mnih, and Teh (2017) Maddison, C. J.; Mnih, A.; and Teh, Y. W. 2017.  The concrete distribution: A continuous relaxation of discrete random variables.  In _ICLR_.
  * Mernyei and Cangea (2020) Mernyei, P.; and Cangea, C. 2020.  Wiki-cs: A wikipedia-based benchmark for graph neural networks.  _arXiv preprint arXiv:2007.02901_.
  * Ni et al. (2018) Ni, J.; Chang, S.; Liu, X.; Cheng, W.; Chen, H.; Xu, D.; and Zhang, X. 2018.  Co-regularized deep multi-network embedding.  In _WWW_ , 469–478.
  * Nt and Maehara (2019) Nt, H.; and Maehara, T. 2019.  Revisiting graph neural networks: All we have is low-pass filters.  _arXiv preprint arXiv:1905.09550_.
  * Pan et al. (2018) Pan, S.; Hu, R.; Long, G.; Jiang, J.; Yao, L.; and Zhang, C. 2018.  Adversarially regularized graph autoencoder for graph embedding.  In _IJCAI_ , 2609–2615.
  * Park et al. (2020) Park, C.; Kim, D.; Han, J.; and Yu, H. 2020.  Unsupervised attributed multiplex network embedding.  In _AAAI_ , volume 34, 5371–5378.
  * Pei et al. (2020) Pei, H.; Wei, B.; Chang, K. C.-C.; Lei, Y.; and Yang, B. 2020.  Geom-GCN: Geometric Graph Convolutional Networks.  In _ICLR_.
  * Peng et al. (2020) Peng, Z.; Huang, W.; Luo, M.; Zheng, Q.; Rong, Y.; Xu, T.; and Huang, J. 2020.  Graph representation learning via graphical mutual information maximization.  In _WWW_.
  * Perozzi, Al-Rfou, and Skiena (2014) Perozzi, B.; Al-Rfou, R.; and Skiena, S. 2014.  Deepwalk: Online learning of social representations.  In _SIGKDD_.
  * Qiu et al. (2020) Qiu, J.; Chen, Q.; Dong, Y.; Zhang, J.; Yang, H.; Ding, M.; Wang, K.; and Tang, J. 2020.  GCC: Graph contrastive coding for graph neural network pre-training.  In _SIGKDD_.
  * Qu et al. (2017) Qu, M.; Tang, J.; Shang, J.; Ren, X.; Zhang, M.; and Han, J. 2017.  An attention-based collaboration framework for multi-view network representation learning.  In _CIKM_.
  * Sen et al. (2008) Sen, P.; Namata, G.; Bilgic, M.; Getoor, L.; Galligher, B.; and Eliassi-Rad, T. 2008\.  Collective classification in network data.  _AI magazine_ , 29(3): 93–93.
  * Shchur et al. (2018) Shchur, O.; Mumme, M.; Bojchevski, A.; and Günnemann, S. 2018.  Pitfalls of graph neural network evaluation.  In _NeurIPS Workshop_.
  * Sun et al. (2018) Sun, Y.; Bui, N.; Hsieh, T.-Y.; and Honavar, V. 2018.  Multi-view network embedding via graph factorization clustering and co-regularized multi-view agreement.  In _ICDM Workshop_ , 1006–1013. IEEE.
  * Suresh et al. (2021) Suresh, S.; Budde, V.; Neville, J.; Li, P.; and Ma, J. 2021.  Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns.  In _SIGKDD_ , 1541–1551.
  * Tan et al. (2023) Tan, Y.; Liu, Y.; Long, G.; Jiang, J.; Lu, Q.; and Zhang, C. 2023.  Federated Learning on Non-IID Graphs via Structural Knowledge Sharing.  In _AAAI_.
  * Tan et al. (2022a) Tan, Y.; Long, G.; Liu, L.; Zhou, T.; Lu, Q.; Jiang, J.; and Zhang, C. 2022a.  Fedproto: Federated prototype learning across heterogeneous clients.  In _AAAI_ , volume 1, 3.
  * Tan et al. (2022b) Tan, Y.; Long, G.; Ma, J.; Liu, L.; Zhou, T.; and Jiang, J. 2022b.  Federated Learning from Pre-Trained Models: A Contrastive Learning Approach.  In _NeurIPS_.
  * Tang et al. (2015) Tang, J.; Qu, M.; Wang, M.; Zhang, M.; Yan, J.; and Mei, Q. 2015.  Line: Large-scale information network embedding.  In _WWW_ , 1067–1077.
  * Thakoor et al. (2022) Thakoor, S.; Tallec, C.; Azar, M. G.; Azabou, M.; Dyer, E. L.; Munos, R.; Veličković, P.; and Valko, M. 2022.  Large-scale representation learning on graphs via bootstrapping.  In _ICLR_.
  * Veličković et al. (2019) Veličković, P.; Fedus, W.; Hamilton, W. L.; Liò, P.; Bengio, Y.; and Hjelm, R. D. 2019.  Deep Graph Infomax.  In _ICLR_.
  * Veličković et al. (2018) Veličković, P.; Cucurull, G.; Casanova, A.; Romero, A.; Liò, P.; and Bengio, Y. 2018.  Graph Attention Networks.  In _ICLR_.
  * Wang et al. (2021) Wang, Y.; Min, Y.; Chen, X.; and Wu, J. 2021.  Multi-view graph contrastive representation learning for drug-drug interaction prediction.  In _WWW_ , 2921–2933.
  * Wu et al. (2019) Wu, F.; Souza, A.; Zhang, T.; Fifty, C.; Yu, T.; and Weinberger, K. 2019.  Simplifying graph convolutional networks.  In _ICML_ , 6861–6871. PMLR.
  * Wu et al. (2020) Wu, Z.; Pan, S.; Chen, F.; Long, G.; Zhang, C.; and Philip, S. Y. 2020.  A comprehensive survey on graph neural networks.  _IEEE TNNLS_ , 32(1): 4–24.
  * Xu et al. (2019) Xu, K.; Hu, W.; Leskovec, J.; and Jegelka, S. 2019.  How Powerful are Graph Neural Networks?  In _ICLR_.
  * Yang et al. (2021) Yang, L.; Li, M.; Liu, L.; Wang, C.; Cao, X.; Guo, Y.; et al. 2021.  Diverse Message Passing for Attribute with Heterophily.  In _NeurIPS_ , volume 34.
  * Yang, Cohen, and Salakhudinov (2016) Yang, Z.; Cohen, W.; and Salakhudinov, R. 2016.  Revisiting semi-supervised learning with graph embeddings.  In _ICML_ , 40–48. PMLR.
  * You et al. (2020) You, Y.; Chen, T.; Sui, Y.; Chen, T.; Wang, Z.; and Shen, Y. 2020.  Graph contrastive learning with augmentations.  In _NeurIPS_ , volume 33, 5812–5823.
  * Zhang, Yin, and Philip (2022) Zhang, D.; Yin, J.; and Philip, S. Y. 2022.  Link Prediction with Contextualized Self-Supervision.  _IEEE TKDE_.
  * Zhang et al. (2022) Zhang, H.; Wu, B.; Yuan, X.; Pan, S.; Tong, H.; and Pei, J. 2022.  Trustworthy Graph Neural Networks: Aspects, Methods and Trends.  _arXiv preprint arXiv:2205.07424_.
  * Zhao et al. (2021a) Zhao, J.; Wang, X.; Shi, C.; Hu, B.; Song, G.; and Ye, Y. 2021a.  Heterogeneous graph structure learning for graph neural networks.  In _AAAI_.
  * Zhao et al. (2021b) Zhao, T.; Liu, Y.; Neves, L.; Woodford, O.; Jiang, M.; and Shah, N. 2021b.  Data Augmentation for Graph Neural Networks.  In _AAAI_ , volume 35, 11015–11023.
  * Zheng et al. (2022a) Zheng, X.; Liu, Y.; Pan, S.; Zhang, M.; Jin, D.; and Yu, P. S. 2022a.  Graph neural networks for graphs with heterophily: A survey.  _arXiv preprint arXiv:2202.07082_.
  * Zheng et al. (2022b) Zheng, Y.; Pan, S.; Lee, V. C.; Zheng, Y.; and Yu, P. S. 2022b.  Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination.  In _NeurIPS_.
  * Zheng et al. (2022c) Zheng, Y.; Zheng, Y.; Zhou, X.; Gong, C.; Lee, V.; and Pan, S. 2022c.  Unifying Graph Contrastive Learning with Flexible Contextual Scopes.  In _ICDM_.
  * Zhu et al. (2020a) Zhu, J.; Yan, Y.; Zhao, L.; Heimann, M.; Akoglu, L.; and Koutra, D. 2020a.  Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs.  In _NeurIPS_ , volume 33.
  * Zhu et al. (2020b) Zhu, Y.; Xu, Y.; Yu, F.; Liu, Q.; Wu, S.; and Wang, L. 2020b.  Deep Graph Contrastive Representation Learning.  In _ICML Workshop_.
  * Zhu et al. (2021) Zhu, Y.; Xu, Y.; Yu, F.; Liu, Q.; Wu, S.; and Wang, L. 2021.  Graph contrastive learning with adaptive augmentation.  In _WWW_ , 2069–2080.
  * Zügner and Günnemann (2019) Zügner, D.; and Günnemann, S. 2019.  Adversarial Attacks on Graph Neural Networks via Meta Learning.  In _ICLR_.

##  Appendix A A. Related Work in Detail

In this detailed section on related work, we first introduce two types of
conventional GNNs, i.e. spectral-based GNNs and spatial-based GNNs. Then, we
review the recent works of heterophily-aware GNNs. After that, we summarize
the conventional UGRL methods and contrastive UGRL methods. Finally, we
introduce the recent development of multi-view graph representation learning.

Spectral-based GNNs. The spectral-based GNNs perform graph convolution based
on graph spectral theory. As a pioneering study of spectral-based GNNs, (Bruna
et al. 2014) first propose the graph convolutional networks based on spectral
theory. To further reduce the computational cost, Chebyshev filter
(Defferrard, Bresson, and Vandergheynst 2016) is applied to spectral-based
GNNs for graph convolution. Following these works, GCN (Kipf and Welling 2017)
leverages the first-order approximation of Chebyshev filter as the
convolutional operator, which further simplifies the computation. SGC (Wu et
al. 2019) decomposes the graph convolution and feature transformation in
spectral-based GNNs, bringing higher running efficiency. More recent works
(Dong et al. 2021; Ma et al. 2021) try to improve spectral-based GNNs by
introducing adaptive filters or novel convolutional operators.

Spatial-based GNNs. Following the success of spectral-based GNNs, another type
of GNNs, spatial-based GNNs, fastly developed in recent years due to their
flexibility. Different from spectral-based GNNs, the spatial-based GNNs
perform convolution operation by aggregating local information along edges and
then transferring the information (i.e., representations) with learnable
neural networks. Following such a message passing paradigm, various spatial-
based GNNs with unique designs of aggregation functions are developed. For
example, GraphSAGE (Hamilton, Ying, and Leskovec 2017) provides multiple
optional aggregation functions for information propagation, including mean
pooling, max pooling, and LSTM. GAT (Veličković et al. 2018) introduces self-
attention mechanism for aggregation. GIN (Xu et al. 2019) proposes a novel
summation aggregation function to increase the expressive power of GNNs.
Readers may refer to recent survey (Wu et al. 2020; Zhang et al. 2022) for a
comprehensive review.

Heterophily-aware GNNs. To tackle the challenge of heterophily graph learning,
very recently, a family of GNNs focus on learning on graph with heterophilic
properties (Zheng et al. 2022a). For instance, Geom-GCN (Pei et al. 2020) uses
embeddings in a latent space to construct structural neighborhoods for
aggregation. FAGCN (Bo et al. 2021) and GPR-GNN (Chien et al. 2021) use
learnable weights to capture high-frequency patterns. To adapt GCN to graph
with low homophily, H2GCN (Zhu et al. 2020a) incorporates three techniques,
i.e., ego- and neighbor- embedding separation, higher-order neighborhoods, and
combination of intermediate. UGCN (Jin et al. 2021) extends neighbor set by
adding similar but disjunct nodes, such as 2-hop neighboring nodes. DMP (Yang
et al. 2021) considers multiple message passing channels to capture different
graph signals. WRGNN (Suresh et al. 2021) considers proximity and structural
information to perform multi-relational message aggregation. However, all of
these methods require labels to provide supervision signals for representation
learning, while how to learn embeddings for heterophilic graphs in the
unsupervised setting still remains an open problem.

Conventional UGRL. Unsupervised graph representation learning (UGRL, a.k.a.
graph embedding) is an essential task in graph machine learning. A line of
conventional graph embedding methods uses random walk to construct the
proximal neighbors, and then targets to maximize the agreement among the
proximal nodes. For instance, Deepwalk (Perozzi, Al-Rfou, and Skiena 2014)
first builds fix-length random walks and uses a Skip-gram model to learn node
embeddings from the walks. LINE (Tang et al. 2015) considers both first-order
and second-order proximity for graph embedding. Node2vec (Grover and Leskovec
2016) considers breadth-first traversal and depth-first traversal for random
walk generation, and also utilize Skip-gram to learn representations. These is
also a series of works use anto-encoder-like architecture to maximize the
similarities between adjacent nodes. For example, GAE and VGAE (Kipf and
Welling 2016) use a binary cross-entropy objective that reconstructs the graph
structure to train GNN encoders. ARGA (Pan et al. 2018) further introduces the
adversarial mechanism to train the graph auto-encoder model.

Contrastive UGRL. Following the blossom of contrastive learning (He et al.
2020; Chen et al. 2020), some recent efforts apply contrast mechanism to learn
representations on graphs in an unsupervised manner (Liu et al. 2022a; Zheng
et al. 2022b, c). In general, these methods construct two augmented views
(Ding et al. 2022) from original graphs and then employ contrastive learning
objectives (e.g., InfoNCE (Chen et al. 2020) or JS Divergence (Veličković et
al. 2019)) to maximize the agreement between corresponding representations
obtained from two different views. For instance, GRACE (Zhu et al. 2020b) use
edge dropping and feature masking to generate augmented views, and use InfoNCE
for agreement maximization. GCA (Zhu et al. 2021) further introduces adaptive
augmentations to GRACE. GCC (Qiu et al. 2020) establishes graph views by
subgraph sampling for contrast. BGRL (Thakoor et al. 2022) utilizes a
bootstrapping-based learning objective for graph contrastive learning. DGI
(Veličković et al. 2019) and MVGRL (Hassani and Khasahmadi 2020) introduce a
local-global contrastive learning by maximizing the agreement between nodes
and full graph with JS Divergence objectives. GraphCL (You et al. 2020)
explores the application of contrastive learning on graph-level learning
tasks. Besides UGRL tasks, graph contrastive learning has been proved to be
effective on various graph-related tasks, including anomaly detection (Liu et
al. 2021), out-of-distribution detection (Liu et al. 2023), link prediction
(Peng et al. 2020), and federated graph learning (Tan et al. 2022a, b, 2023).

Multi-view Graph Representation Learning. Different from the aforementioned
methods that learn from a single graph, another line of methods termed multi-
view graph representation learning aims to learn representations from multiple
available graph views (Qu et al. 2017; Park et al. 2020; Ma et al. 2019). They
learn node representations through fusing the knowledge from multiple views
with various mechanisms, including attention mechanism (Qu et al. 2017), co-
regularization (Ni et al. 2018; Sun et al. 2018), mutual information
maximization (Park et al. 2020), and adversarial training (Fu et al. 2020).
The representation learning for signed networks has also been explored (Li et
al. 2020b; Lee et al. 2020), which can be regarded as a special case of multi-
view graphs where two edge views are respectively defined by positive and
negative relations. The main difference between these methods and our proposed
method is that, these methods learn representations from graphs with multiple
explicit views (Sun et al. 2018), while our method handles a more challenging
task, i.e., learning to discriminate homophilic and heterophilic edge views
from graphs with a single edge type automatically.

Algorithm 1 Algorithm of GREET

Input: Edge set $\mathcal{E}$, Feature Matrix $\mathbf{X}$.
Parameters: Number of outer iterations $T_{o}$, Number of inner iterations
$T_{i}$, learning rate of representation learning module $\mu_{grl}$, learning
rate of edge discriminator $\mu_{disc}$.
Output: Node representation matrix $\mathbf{H}$.

1: Randomly initialize the parameters of edge discriminator, two encoders and
two project heads.

2: for node $v_{i}\in\mathcal{V}$ do

3: Initialize structural encoding $s_{i}$ via Eq. (1).

4: Initialize the similar node set $\mathcal{N}_{i}=\mathrm{kNN}(v_{i},k)$.

5: end for

6: for outer iteration $1,2,\cdots,T_{o}$ do

7: for inner iteration $1,2,\cdots,T_{i}$ do

8: Calculate $\hat{w}$ with edge discriminator via Eq. (2) and (3).

9: Establish $\mathcal{G}^{(hm)}$ and $\mathcal{G}^{(ht)}$ via Eq. (4).

10: Augment $\mathcal{G}^{(hm)}$ and $\mathcal{G}^{(ht)}$ by edge dropping and
feature masking.

11: Calculate $\mathbf{H}^{(hm)}$, $\mathbf{H}^{(ht)}$ via Eq. (5) and (6).

12: Calculate $\mathbf{Z}^{(hm)}$, $\mathbf{Z}^{(ht)}$ with projection heads.

13: Calculate $\mathcal{L}_{c}$ via Eq. (10).

14: Back-propagate $\mathcal{L}_{c}$ to update encoders and projection heads
with learning rate $\mu_{grl}$.

15: end for

16: Calculate $\hat{w}$ with edge discriminator via Eq. (2) and (3).

17: Establish $\mathcal{G}^{(hm)}$ and $\mathcal{G}^{(ht)}$ via Eq. (4).

18: Calculate $\mathbf{H}^{(hm)}$, $\mathbf{H}^{(ht)}$ via Eq. (5) and (6).

19: Acquire $\mathbf{H}$ via
$\mathbf{H}=[\mathbf{H}^{(hm)}|\mathbf{H}^{(ht)}]$.

20: Calculate $\mathcal{L}_{r}$ via Eq. (7), (8), and (9).

21: Back-propagate $\mathcal{L}_{r}$ to update edge generator with learning
rate $\mu_{disc}$.

22: end for

23: Calculate $\hat{w}$ with edge discriminator via Eq. (2) and (3).

24: Establish $\mathcal{G}^{(hm)}$ and $\mathcal{G}^{(ht)}$ via Eq. (4).

25: Calculate $\mathbf{H}^{(hm)}$, $\mathbf{H}^{(ht)}$ via Eq. (5) and (6).

26: return $\mathbf{H}=[\mathbf{H}^{(hm)}|\mathbf{H}^{(ht)}]$

##  Appendix B B. Algorithm

The training algorithm of GREET is summarized in Algorithm 1. As we can see,
the structural encodings and similar node sets can be pre-computed in the
initialization phase. In each iteration, we first train the graph
representation learning module (i.e., dual-channel encoders and projection
heads) with the robust dual-channel contrastive loss $\mathcal{L}_{c}$ for
$T_{i}$ steps ($T_{i}$ is a hyper-parameter), while keeping the parameters of
edge discriminator fixed. In this phase, the learned edge distinction is used
to generate graph views, and the contrastive loss trains dual-channel encoders
by maximizing the agreement between the current two views. After that, we fix
the encoders and learn the edge discriminator for one step under the
supervision of pivot-anchored ranking loss $\mathcal{L}_{r}$. In this phase,
the edge discriminator learns better edge distinction according to the latest
learned representations. In such an alternating training procedure, the
discriminator and encoders are mutually enhanced by each other, and finally,
GREET learns the optimal node representations.

Table 4: Statistics of datasets. Dataset | Nodes | Edges | Classes | Features | $\mathcal{H}_{edge}$ | $\mathcal{H}_{node}$ | Train/Val/Test
---|---|---|---|---|---|---|---
Cora | 2,708 | 10,556 | 7 | 1,433 | 0.810 | 0.825 | 140 / 500 / 1,000
CiteSeer | 3,327 | 9,104 | 6 | 3,703 | 0.736 | 0.717 | 120 / 500 / 1,000
PubMed | 19,717 | 88,648 | 3 | 500 | 0.802 | 0.792 | 60 / 500 / 1,000
Wiki-CS | 11,701 | 431,206 | 10 | 300 | 0.654 | 0.677 | 1,170 / 1,171 / 9,360
Amz. Comp. | 13,752 | 491,722 | 10 | 767 | 0.777 | 0.802 | 1,375 / 1,376 / 11,001
Amz. Photo | 7,650 | 238,162 | 8 | 745 | 0.827 | 0.849 | 765 / 765 / 6,120
Co. CS | 18,333 | 163,788 | 15 | 6,805 | 0.808 | 0.832 | 1,833 / 1,834 / 14,666
Co. Physics | 34,493 | 495,924 | 5 | 8,415 | 0.931 | 0.915 | 3,449 / 3,450 / 27,594
Cornell | 183 | 295 | 5 | 1,703 | 0.298 | 0.386 | 87 / 59 / 37
Texas | 183 | 309 | 5 | 1,703 | 0.061 | 0.097 | 87 / 59 / 37
Wisconsin | 251 | 499 | 5 | 1,703 | 0.170 | 0.150 | 120 / 80 / 51
Chameleon | 2,277 | 36,051 | 5 | 2,325 | 0.234 | 0.247 | 1,092 / 729 / 456
Squirrel | 5,201 | 216,933 | 5 | 2,089 | 0.223 | 0.216 | 2,496 / 1,664 / 1,041
Actor | 7,600 | 29,926 | 5 | 932 | 0.216 | 0.221 | 3,638 / 2,432 / 1,520

##  Appendix C C. Complexity Analysis

We discuss time complexity of GREET. In pre-processing phase, the structural
encodings and kNN neighbors can be pre-computed at once. Using sparse matrix
multiplication, the time complexity for structural encoding computation is
$\mathcal{O}(nmd_{s})$. Considering the graphs are often sparse ($m\ll n^{2}$)
and $d_{s}$ can set to be a small value ($d_{s}\leq 20$), the computational
cost here is acceptable. The time complexity of kNN is $\mathcal{O}(n^{2})$
for full graph computation; however, using the locality-sensitive kNN
approximation algorithm (Fatemi, Asri, and Kazemi 2021; Liu et al. 2022b),
this computational cost can be reduce to $\mathcal{O}(nb_{k})$ through
estimating the top-k neighbors among $b_{k}$ nodes instead of all nodes.

In training phase, the time complexity can be discussed for two main
components. In edge discriminator, the complexities of the first MLP layer and
the second MLP layer are $\mathcal{O}(nd_{i}(d_{f}+d_{s}))$ and
$\mathcal{O}(md_{i})$ respectively, where $d_{i}$ is the dimension of
intermediate embeddings. In dual-channel contrastive learning module, the
complexities of encoders and projection heads are
$\mathcal{O}(nd_{f}d_{r}+md_{r}L)$ and $\mathcal{O}(nd_{r}d_{p}L_{p})$, where
$L_{p}$ and $d_{p}$ are the layer number of projection heads and the dimension
of projected latent embeddings, respectively. The complexity of pivot-anchored
ranking loss is $\mathcal{O}(md_{r})$, while the complexity of robust dual-
channel contrastive loss is $\mathcal{O}(nbd_{p})$, where $b$ is the batch
size of contrastive learning.

##  Appendix D D. Datasets

Table 5: Details of the hyper-parameters tuned by grid search. Dataset | $T_{o}$ | $T_{i}$ | ${\mu}_{disc}$ | $\alpha$ | $L_{p}$ | $\gamma^{(hm)}$ | $\gamma^{(ht)}$ | $k$ | $b$ | $p_{f}^{(hm)}$ | $p_{f}^{(ht)}$ | $p_{e}^{(hm)}$ | $p_{e}^{(ht)}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Cora | 400 | 2 | 1e-3 | 0.5 | 1 | 0.5 | 0.5 | 20 | FN | 0.8 | 0.1 | 0.8 | 0.8
CiteSeer | 400 | 2 | 1e-3 | 0.1 | 2 | 0.5 | 0.5 | 30 | FN | 0.1 | 0.1 | 0.8 | 0.1
PubMed | 800 | 2 | 1e-3 | 0.1 | 2 | 0.5 | 0.5 | 0 | 5000 | 0.1 | 0.5 | 0.5 | 0.1
Wiki-CS | 1500 | 2 | 1e-3 | 0.1 | 1 | 0.5 | 0.5 | 30 | 3000 | 0.1 | 0.1 | 0.5 | 0.5
Amz. Comp. | 1500 | 3 | 1e-4 | 0.3 | 1 | 0.1 | 0.5 | 10 | 5000 | 0.1 | 0.1 | 0.5 | 0.1
Amz. Photo | 1500 | 3 | 1e-4 | 0.3 | 1 | 0.5 | 0.5 | 30 | 5000 | 0.1 | 0.1 | 0.8 | 0.5
Co. CS | 1500 | 2 | 1e-3 | 0.5 | 1 | 0.1 | 0.5 | 30 | 5000 | 0.1 | 0.5 | 0.5 | 0.1
Co. Physics | 800 | 2 | 1e-3 | 0.1 | 1 | 0.5 | 0.5 | 25 | 2000 | 0.1 | 0.5 | 0.5 | 0.1
Cornell | 400 | 2 | 1e-3 | 0.3 | 2 | 0.3 | 0.3 | 25 | FN | 0.1 | 0.5 | 0.5 | 0.1
Texas | 400 | 2 | 1e-3 | 0.5 | 2 | 0.5 | 0.5 | 20 | FN | 0.5 | 0.1 | 0.1 | 0.1
Wisconsin | 400 | 2 | 1e-3 | 0.5 | 2 | 0.5 | 0.5 | 25 | FN | 0.1 | 0.1 | 0.1 | 0.5
Chameleon | 600 | 2 | 1e-3 | 0.1 | 1 | 0.5 | 0.5 | 0 | FN | 0.1 | 0.5 | 0.5 | 0.1
Squirrel | 1000 | 2 | 1e-3 | 0.1 | 2 | 0.1 | 0.3 | 0 | FN | 0.1 | 0.1 | 0.1 | 0.8
Actor | 1000 | 2 | 1e-3 | 0.1 | 2 | 0.1 | 0.5 | 20 | FN | 0.1 | 0.5 | 0.5 | 0.8

We evaluate our models on eight homophilic graph benchmarks (i.e., Cora,
CiteSeer, PubMed, Wiki-CS, Amazon Computer, Amazon Photo, CoAuthor CS, and
CoAuthor Physic) and six heterophilic graph benchmarks (i.e., Chameleon,
Squirrel, Actor, Cornell, Texas, and Wisconsin). For Cora, CiteSeer, and
PubMed datasets, we adopt the public splits (Yang, Cohen, and Salakhudinov
2016; Kipf and Welling 2017); for the other 5 homophilic datasets, we adopt a
10%/10%/80% training/validation/testing splits following previous works (Zhu
et al. 2021; Thakoor et al. 2022); for heterophilic graphs, we adopt the
commonly used 48%/32%/20% training/validation/testing splits used in previous
works (Pei et al. 2020; Zhu et al. 2020a). The statistics of datasets are
provided in Table 4, where we further attach the edge homophily
$\mathcal{H}_{edge}$ (Zhu et al. 2020a) and node homophily
$\mathcal{H}_{node}$ (Pei et al. 2020) of each dataset. The details are
introduced as follows:

  * •

Cora, CiteSeer and PubMed (Sen et al. 2008) are three citation network
datasets, where nodes indicate a paper and each edges indicate a citation
relationship between two papers. The features are the bag-of-word
representations of papers, and labels are the research topic of papers.

  * •

Wiki-CS (Mernyei and Cangea 2020) is a reference network extracted from
Wikipedia, where nodes indicate articles about computer science and edges
indicate the hyperlinks between two articles. The features are the average
GloVe word embeddings of the context in the corresponding article, and labels
are different fields of each article.

  * •

Amazon Computers and Amazon Photo (Shchur et al. 2018) are two co-purchase
networks from Amazon. In these networks, each node indicates a good, and each
edge indicates that two goods are frequently bought together. The features is
the bag-of-word representations of product reviews, while the labels are the
category of goods.

  * •

CoAuthor CS and CoAuthor Physics (Shchur et al. 2018) are two co-authorship
networks extracted from Microsoft Academic Graph in KDD Cup 2016 challenge. In
these networks, nodes indicate an author and edges indicate co-authorship
relationships. The features are the bag-of-words embeddings of paper keywords,
and the labels are the research fields of authors.

  * •

Cornell, Texas and Wisconsin (Pei et al. 2020) are three web page networks
from computer science departments of diverse universities, where nodes are web
pages and edges are hyperlinks between two web pages. The features are the
bag-of-words representations of the corresponding page, and the labels are
types of web pages.

  * •

Chameleon and Squirrel (Pei et al. 2020) are two Wikipedia networks where
nodes denote web pages in Wikipedia and edges denote links between two pages.
The features contain the informative nouns in the Wikipedia pages, and labels
stand for the average traffic of the web page.

  * •

Actor (Pei et al. 2020) is an actor co-occurrence network where nodes are
actors and edges indicate two actors have co-occurrence in the same movie. The
features indicate the key word in the Wikipedia pages, and labels are the
words of corresponding actors.

##  Appendix E E. Implementation Details

#### Hyper-parameters.

We select some important hyper-parameters through small grid search, and keep
the rest insensitive hyper-parameters to be fixed values. Specifically, the
searched hyper-parameters for each benchmark dataset are demonstrated in Table
5, and the selection of fixed hyper-parameters are summarized in Table 6. The
grid search is carried out on the following search space:

  * •

Number of outer training iterations $T_{o}$: {400, 600, 800, 1000, 1500}

  * •

Number of inner training iterations $T_{i}$: {1, 2, 3}

  * •

Learning rate of edge discriminator $\mu_{disc}$: {5e-3, 1e-3, 1e-4}

  * •

High-pass filtering strength $\alpha$: {0.1, 0.3, 0.5, 0.7}

  * •

Number of projection layers $L_{p}$: {1,2}

  * •

Margins of pivot-anchored ranking loss $\gamma^{(hm)}$, $\gamma^{(ht)}$: {0.1,
0.3, 0.5}

  * •

Number of similar node $k$: {0, 5, 10, 15, 20, 25, 30}

  * •

Batch size of contrastive loss $b$: {2000, 3000, 5000, full node (FN)}

  * •

Feature masking rates $p_{f}^{(hm)}$, $p_{f}^{(ht)}$: {0.1 ,0.5, 0.8}

  * •

Edge dropping rates $p_{e}^{(hm)}$, $p_{e}^{(ht)}$: {0.1 ,0.5, 0.8}

Table 6: Details of the fixed hyper-parameters. Hyper-parameter | Value
---|---
Learning rate of encoding module $\mu_{grl}$ | 1e-3
Weight decay coefficient $\lambda$ | 0
Dimension of structural encoding $d_{s}$ | 16
Dimension of intermediate embedding $d_{i}$ | 128
Dimension of representations $d_{r}$ | 128
Dimension of projected embedding $d_{p}$ | 128
Layer number of encoders $L$ | 2
Temperature of Gumbel-Max $\tau_{g}$ | 1
Temperature of contrastive loss $\tau_{c}$ | 0.2

#### Evaluation details.

We follow previous works (Zhu et al. 2020b, 2021) to construct the downstream
classifier for evaluation. To be concrete, we first extract the node
representations learned by the UGRL model. Then, the representations of
training nodes are used to train an L2-regularized logistic regression
classifier from scikit-learn. Finally, the representations of testing nodes
are used to evaluate the classification accuracy based on the learned
classifier.

#### Computing infrastructures.

We implement the proposed GREET with PyTorch 1.11.0 and DGL 0.8.0. All
experiments are conducted on a Linux server with an Intel Xeon E-2288G CPU and
two Quadro RTX 6000 GPUs.

##  Appendix F F. Parameter Study

(a) Sensitivity of $\alpha$

(b) Sensitivity of $k$

Figure 5: Parameter sensitivity of $\alpha$ and $k$.

(a) Cora

(b) CiteSeer

(c) Cornell

(d) Texas

Figure 6: Parameter sensitivity of $\gamma^{(hm)}$ and $\gamma^{(ht)}$. Table
7: Results in terms of classification accuracies (in percent $\pm$ standard
deviation) on heterophilic benchmarks. “*” indicates that results are borrowed
from the original papers. The best and runner-up results are highlighted with
bold and underline, respectively.

Methods |  Chameleon |  Squirrel |  Actor |  Cornell |  Texas |  Wisconsin
---|---|---|---|---|---|---
GCN |  $59.63{\scriptstyle\pm 2.32}$ |  $36.28{\scriptstyle\pm 1.52}$ |  $30.83{\scriptstyle\pm 0.77}$ |  $57.03{\scriptstyle\pm 3.30}$ |  $60.00{\scriptstyle\pm 4.80}$ |  $56.47{\scriptstyle\pm 6.55}$
GAT |  $56.38{\scriptstyle\pm 2.19}$ |  $32.09{\scriptstyle\pm 3.27}$ |  $28.06{\scriptstyle\pm 1.48}$ |  $59.46{\scriptstyle\pm 3.63}$ |  $61.62{\scriptstyle\pm 3.78}$ |  $54.71{\scriptstyle\pm 6.87}$
MLP |  $46.91{\scriptstyle\pm 2.15}$ |  $29.28{\scriptstyle\pm 1.33}$ |  $35.66{\scriptstyle\pm 0.94}$ |  $81.08{\scriptstyle\pm 7.93}$ |  $81.62{\scriptstyle\pm 5.51}$ |  $84.31{\scriptstyle\pm 3.40}$
Geom-GCN* |  ${60.90}$ |  ${38.14}$ |  ${31.63}$ |  ${60.81}$ |  ${67.57}$ |  ${64.12}$
H2GCN* |  $59.39{\scriptstyle\pm 1.98}$ |  $37.90{\scriptstyle\pm 2.02}$ |  $\underline{35.86{\scriptstyle\pm 1.03}}$ |  $\underline{82.16{\scriptstyle\pm 4.80}}$ |  $\underline{84.86{\scriptstyle\pm 6.77}}$ |  $\mathbf{86.67{\scriptstyle\pm 4.69}}$
FAGCN |  $\underline{63.44{\scriptstyle\pm 2.05}}$ |  $\underline{41.17{\scriptstyle\pm 1.94}}$ |  $35.74{\scriptstyle\pm 0.62}$ |  $81.35{\scriptstyle\pm 5.05}$ |  $84.32{\scriptstyle\pm 6.02}$ |  $83.33{\scriptstyle\pm 2.01}$
GPR-GNN |  $61.58{\scriptstyle\pm 2.24}$ |  $39.65{\scriptstyle\pm 2.81}$ |  $35.27{\scriptstyle\pm 1.04}$ |  $81.89{\scriptstyle\pm 5.93}$ |  $83.24{\scriptstyle\pm 4.95}$ |  $84.12{\scriptstyle\pm 3.45}$
DeepWalk |  $47.74{\scriptstyle\pm 2.05}$ |  $32.93{\scriptstyle\pm 1.58}$ |  $22.78{\scriptstyle\pm 0.64}$ |  $39.18{\scriptstyle\pm 5.57}$ |  $46.49{\scriptstyle\pm 6.49}$ |  $33.53{\scriptstyle\pm 4.92}$
node2vec |  $41.93{\scriptstyle\pm 3.29}$ |  $22.84{\scriptstyle\pm 0.72}$ |  $28.28{\scriptstyle\pm 1.27}$ |  $42.94{\scriptstyle\pm 7.46}$ |  $41.92{\scriptstyle\pm 7.76}$ |  $37.45{\scriptstyle\pm 7.09}$
GAE |  $33.84{\scriptstyle\pm 2.77}$ |  $28.03{\scriptstyle\pm 1.61}$ |  $28.03{\scriptstyle\pm 1.18}$ |  $58.85{\scriptstyle\pm 3.21}$ |  $58.64{\scriptstyle\pm 4.53}$ |  $52.55{\scriptstyle\pm 3.80}$
VGAE |  $35.22{\scriptstyle\pm 2.71}$ |  $29.48{\scriptstyle\pm 1.48}$ |  $26.99{\scriptstyle\pm 1.56}$ |  $59.19{\scriptstyle\pm 4.09}$ |  $59.20{\scriptstyle\pm 4.26}$ |  $56.67{\scriptstyle\pm 5.51}$
DGI |  $39.95{\scriptstyle\pm 1.75}$ |  $31.80{\scriptstyle\pm 0.77}$ |  $29.82{\scriptstyle\pm 0.69}$ |  $63.35{\scriptstyle\pm 4.61}$ |  $60.59{\scriptstyle\pm 7.56}$ |  $55.41{\scriptstyle\pm 5.96}$
GMI |  $46.97{\scriptstyle\pm 3.43}$ |  $30.11{\scriptstyle\pm 1.92}$ |  $27.82{\scriptstyle\pm 0.90}$ |  $54.76{\scriptstyle\pm 5.06}$ |  $50.49{\scriptstyle\pm 2.21}$ |  $45.98{\scriptstyle\pm 2.76}$
MVGRL |  $51.07{\scriptstyle\pm 2.68}$ |  $35.47{\scriptstyle\pm 1.29}$ |  $30.02{\scriptstyle\pm 0.70}$ |  $64.30{\scriptstyle\pm 5.43}$ |  $62.38{\scriptstyle\pm 5.61}$ |  $62.37{\scriptstyle\pm 4.32}$
GRACE |  $48.05{\scriptstyle\pm 1.81}$ |  $31.33{\scriptstyle\pm 1.22}$ |  $29.01{\scriptstyle\pm 0.78}$ |  $54.86{\scriptstyle\pm 6.95}$ |  $57.57{\scriptstyle\pm 5.68}$ |  $50.00{\scriptstyle\pm 5.83}$
GRACE-FA |  $52.68{\scriptstyle\pm 2.14}$ |  $35.97{\scriptstyle\pm 1.20}$ |  $32.55{\scriptstyle\pm 1.28}$ |  $67.57{\scriptstyle\pm 4.98}$ |  $64.05{\scriptstyle\pm 7.46}$ |  $63.73{\scriptstyle\pm 6.81}$
GCA |  $49.80{\scriptstyle\pm 1.81}$ |  $35.50{\scriptstyle\pm 0.91}$ |  $29.65{\scriptstyle\pm 1.47}$ |  $55.41{\scriptstyle\pm 4.56}$ |  $59.46{\scriptstyle\pm 6.16}$ |  $50.78{\scriptstyle\pm 4.06}$
BGRL |  $47.46{\scriptstyle\pm 2.74}$ |  $32.64{\scriptstyle\pm 0.78}$ |  $29.86{\scriptstyle\pm 0.75}$ |  $57.30{\scriptstyle\pm 5.51}$ |  $59.19{\scriptstyle\pm 5.85}$ |  $52.35{\scriptstyle\pm 4.12}$
GREET |  $\mathbf{63.64{\scriptstyle\pm 1.26}}$ |  $\mathbf{42.29{\scriptstyle\pm 1.43}}$ |  $\mathbf{36.55{\scriptstyle\pm 1.01}}$ |  $\mathbf{85.14{\scriptstyle\pm 4.87}}$ |  $\mathbf{87.03{\scriptstyle\pm 2.36}}$ |  $\underline{84.90{\scriptstyle\pm 4.48}}$

We conduct a series of experiments to study the sensitivity of GREET w.r.t.
some critical hyper-parameters, including high-Pass filtering strength
$\alpha$, contextual node number $k$, and margins of pivot-anchored ranking
loss $\gamma^{(hm)}$, $\gamma^{(ht)}$.

#### High-Pass Filtering Strength $\alpha$.

In this experiment, we vary $\alpha$ from $0.01$ to $1$ to investigate its
effort in GREET. We plot the classification accuracy w.r.t. different
selection of $\alpha$ in Fig. 5(a). From the figure, we can observe that the
best selection of $\alpha$ for different datasets is quiet different. For
example, the best selection of $\alpha$ is 0.05 for CiteSeer and $0.8$ for
Texas. Besides, a common phenomenon is that the performance consistently
decreases when $\alpha$ is too large. A possible reason is that a high-pass
filtering with over-large strength would lead to the losing of original graph
signals.

#### Similar Node Number $k$.

We study the sensitivity of GREET w.r.t. the similar node number $k$ by
varying $k$ from $0$ to $40$ with an interval of $5$. The experimental results
are shown in Fig. 5(b). As we can see in the figure, the performance of GREET
drops when $k$ is too large or too small, and the best results on these 4
datasets often occur when $k$ is between $20$ and $30$. We conjecture that an
overlarge $k$ would lead to irrelevant contextual nodes, while an extremely
small $k$ may result in the lack of supervision signals.

#### Margins $\gamma^{(hm)}$ and $\gamma^{(ht)}$.

We search the margins for two terms of ranking loss from $0.1$ to $1.0$. Fig.
6 demonstrates the performance under different combinations of $\gamma^{(hm)}$
and $\gamma^{(ht)}$ on four datasets. From the heat maps, we have the
following observations. Firstly, GREET is more sensitive to $\gamma^{(ht)}$
rather than $\gamma^{(hm)}$. This observation shows that the constraint on the
similarity of heterophilic edges is more important than those of homophilic
edges, which demonstrates the significance of detecting heterophilic edges
from graph structures. Secondly, for homophilic graph datasets (i.e., Cora and
CiteSeer), the performance is better when $\gamma^{(hm)}$ is large and
$\gamma^{(ht)}$ is small; for heterophilic graph datasets (i.e., Cornell and
Texas), conversely, the performance is better when $\gamma^{(ht)}$ is large
and $\gamma^{(hm)}$ is small. A possible reason is that homophilic graphs need
tighter constraints for the similarity of homophilic edges since most of the
edges are homophilic; similarly, heterophilic graphs require a stricter rule
for the similarity of heterophilic edges which account for the majority of
edges. Thirdly, when the values of $\gamma^{(hm)}$ and $\gamma^{(ht)}$ are
within certain range (i.e., between $0.3$ and $0.7$), GREET consistently
performs well on all datasets, which shows that the margins should be set to
moderate values.

##  Appendix G G. Detailed Results on Heterophilic Datasets

The experimental results on 6 heterophilic datasets with standard deviation is
demonstrated in Table 7.