#  Contrastive Learning under Heterophily

Wenhan Yang<EMAIL_ADDRESS>Department of Computer Science,
University of California, Los Angeles and  Baharan Mirzasoleiman
<EMAIL_ADDRESS>Department of Computer Science,
University of California, Los Angeles

(2018)

###### Abstract.

Graph Neural Networks are powerful tools for learning node representations
when task-specific node labels are available. However, obtaining labels for
graphs is expensive in many applications. This is particularly the case for
large graphs. To address this, there has been a body of work to learn node
representations in a self-supervised manner without labels. Contrastive
learning (CL), has been particularly popular to learn representations in a
self-supervised manner. In general, CL methods work by maximizing the
similarity between representations of augmented views of the same example, and
minimizing the similarity between augmented views of different examples.
However, existing graph CL methods cannot learn high-quality representations
under heterophily, where connected nodes tend to belong to different classes.
This is because under heterophily, augmentations of the same example may not
be similar to each other. In this work, we address the above problem by
proposing the first graph CL method, HLCL, for learning node representations,
under heterophily. HLCL uses a high-pass and a low-pass graph filter to
generate different views of the same node. Then, it contrasts the two filtered
views to learn the final node representations. Effectively, the high-pass
filter captures the dissimilarity between nodes in a neighborhood and the low-
pass filter captures the similarity between neighboring nodes. Contrasting the
two filtered views allows HLCL to learn rich node representations for graphs,
under heterophily and homophily. Empirically, HLCL outperforms state-of-the-
art graph CL methods on benchmark heterophily datasets and large-scale real-
world datasets by up to 10%.

Graph Neural Networks, Contrastive Learning, Graph Filters

††copyright: acmcopyright††journalyear: 2023††doi:
XXXXXXX.XXXXXXX††conference: ; August 06–10, 2023; Long Beach, CA, USA††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Computing methodologies Neural
networks††ccs: Mathematics of computing Graph Algorithms

##  1\. Introduction

Graph neural networks (GNNs) are powerful tools for learning graph-structured
data in various domains, including social networks, biological compound
structures, and citation networks (Kipf and Welling, 2016; Hamilton et al.,
2017; Veličković et al., 2017). In general, GNNs leverage the graph’s
adjacency matrix to update the node representations by aggregating information
from their neighbors. This can be seen as a low-pass filter that smooths the
graph signals and produces similar node representations (Nt and Maehara,
2019). GNNs have achieved great success in supervised and semi-supervised
learning, where task-specific labels are available. However, obtaining high-
quality labels is very expensive in many domains, specially as graphs grow
larger in size. This has motivated a recent body of work on self-supervised
learning on graphs that learn the representations in an unsupervised manner
(Velickovic et al., 2019; Peng et al., 2020; Qiu et al., 2020; Hassani and
Khasahmadi, 2020; Zhu et al., 2020c).

Among the self-supervised methods, Contrastive Learning (CL) has shown a great
success (Chen et al., 2020; Zhu et al., 2020b; Velickovic et al., 2019; Peng
et al., 2020). Contrastive learning obtains representations by maximizing the
agreement between different augmented views of the same example, and
minimizing agreement between differently augmented views of different
examples. CL has been recently applied to graphs to learn node and graph
representations (Velickovic et al., 2019; Peng et al., 2020; Qiu et al., 2020;
Hassani and Khasahmadi, 2020; Zhu et al., 2020c). Graph CL methods work by
first explicitly augmenting the input graph by altering the node features or
the graph topology. Then, they learn representations by contrasting the
augmented views of the graph encoded with a GNN-based encoder. Despite being
successful on graphs with homophily, where neighboring nodes tend to share the
same label, existing graph CL methods cannot learn high-quality
representations for graphs with heterophily, where connected nodes often
belong to different classes and have dissimilar features (Zhu et al., 2020c).

Learning self-supervised node representations under heterophily is indeed very
challenging. When labels are available, they can be leveraged to learn how the
neighborhood information can be aggregated to achieve a superior
classification performance (Bo et al., 2021; Luan et al., 2020; Pei et al.,
2020; Wang et al., 2019; Zhu et al., 2020a). However, without the label
information it is not clear how the neighborhood information should be
aggregated. Besides, explicit graph augmentation methods, such as topology and
feature augmentation, allow better capturing the node similarities under
homophily. In doing so, they can effectively boost the performance of graph CL
under homophily. However, under heterophily, it is crucial to also leverage
dissimilarities of nodes with their neighborhood to learn rich
representations. Explicit graph augmentations cannot help capturing such
dissimilarities.

Figure 1. Our proposed HLCL framework leverages a high-pass graph filter in
the encoder to generate a non-smooth graph view, and contrast it with its
smooth counterparts generated by the same encoder.

In this work, we address the above challenges by proposing the first graph CL
method under heterophily. The key idea of our proposed method, HLCL, is to
leverage a high-pass graph filter in a typical GNN encoder to capture
dissimilarities of nodes with their neighborhood and generate non-smooth node
representations. The non-smooth representations are then contrasted with their
smooth counterparts generated by the same encoder. This results in learning
rich representations based on a combination of smooth and non-smooth
components. More specifically, we use the normalized Lapcalian matrix as the
high-pass filter in the GNN encoder to aggregate the node representations. The
Laplacian matrix magnifies the differences in the node features in a
neighborhood and makes the representations distinct. In contrast, a typical
GNN encoder uses the normalized adjacency matrix as a low-pass filter to
aggregate the node features with those of their neighbors, and enforce similar
representations for the nodes in the same neighborhood. Maximizing the
agreement between the high-pass and low-pass filtered representations enables
incorporating both smooth and non-smooth components while learning the final
representations. HLCL obtains state-of-the-art performance under heterophily
without the need for explicit augmentation. At the same time, it can leverage
explicit topology and feature augmentations to also obtain a superior
performance on graphs with homophily.

We show the effectiveness of our HLCL framework through extensive experiments
on graphs with heterophily and homophily for unsupervised representations
learning, under the linear evaluation protocol. Our results demonstrate that,
on five popular public benchmark datasets, our framework can outperform
existing graph CL methods by up to 10% for representation learning on graphs
with heterophily, while ensuring a comparable performance to state-of-the-art
graph CL methods on graphs with homophily. We also show that HLCL can easily
scale to large real-world graphs, including Penn94, twitch-gamers, pokec, and
genius, and outperform existing graph CL methods by up to 6%.

##  2\. Preliminaries

Notations. We denote by $\mathcal{G}=(\mathcal{V},\mathcal{E})$ an undirected
graph, where $\mathcal{V}=\\{v_{1},v_{2},\dots,v_{N}\\}$ represents the node
set, and $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ represents the
edge set. We denote by $\boldsymbol{A}\in\\{0,1\\}^{N\times N}$ the symmetric
adjacency matrix of graph $\mathcal{G}$. That is, $\boldsymbol{A}_{ij}=1$ if
and only if $(v_{i},v_{j})\in\mathcal{E}$, and $\boldsymbol{A}_{ij}=0$
otherwise. We also denote the feature matrix by $\boldsymbol{X}$, where
$\boldsymbol{X}_{i.}\in\mathbb{R}^{m}$ is the feature vector of the $i^{th}$
node, and $\boldsymbol{x}\in\mathbb{R}^{N}$ is a column of the matrix and
represents a graph signal. $\boldsymbol{D}$ is the degree matrix of the graph,
with $\boldsymbol{D}_{ii}=\sum_{j}\boldsymbol{A}_{ij}$, and
$\mathcal{N}_{i}=\\{j:\boldsymbol{A}_{ij}=1\\}$ is the neighborhood of node
$i$. $\boldsymbol{L}$ is the Laplacian matrix of the graph, defined as
$\boldsymbol{L}=\boldsymbol{D}-\boldsymbol{A}$. The normalized Laplacian
matrix is denoted by
$\boldsymbol{L}_{sym}=\boldsymbol{D}^{-\frac{1}{2}}\boldsymbol{LD}^{-\frac{1}{2}}$,
and the normalized adjacency matrix is defined in a similar fashion:
$\boldsymbol{A}_{sym}=\boldsymbol{D}^{-\frac{1}{2}}\boldsymbol{AD}^{-\frac{1}{2}}$.
Here, we use the renormalized version of the adjacency matrix
$\boldsymbol{\hat{A}}_{sym}=\boldsymbol{\tilde{D}}^{-\frac{1}{2}}\boldsymbol{\tilde{A}}\boldsymbol{\tilde{D}}^{-\frac{1}{2}}$
as introduced in (Kipf and Welling, 2016), where
$\boldsymbol{\tilde{A}}=\boldsymbol{A}+\boldsymbol{I}$,
$\boldsymbol{\tilde{D}}=\boldsymbol{D}+\boldsymbol{I}$, and
$\hat{A}_{sym}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$.
Similarly, the renormalized Laplacian matrix is defined as
$\boldsymbol{\hat{L}}_{sym}=\boldsymbol{I}-\boldsymbol{\hat{A}}_{sym}$.
$\boldsymbol{\hat{L}}_{sym}$ is a real symmetric matrix, with orthonormal
eigenvectors $\\{\boldsymbol{u}_{i}\\}^{n}_{l=1}\in\mathbb{R}^{n}$, and
corresponding eigenvalues $\lambda_{i}\in[0,2)$ (Chung, 1997). For
$\boldsymbol{\hat{A}}_{sym}$ we have
$\lambda_{i}(\boldsymbol{\hat{A}}_{sym})\in(-1,1]$.

###  2.1. Graph CL under Homophily

State-of-the-art graph CL methods work by explicitly augmenting the input
graph using feature or topology augmentations, encoding the augmented graphs
using a GNN-based encoder, and contrasting the encoded node representations
(Zhu et al., 2020b, 2021b; Velickovic et al., 2019; Thakoor et al., 2021).
Below, we discuss each of these steps in more detail.

Graph Augmentation. First, the input graph is explicitly augmented, by
altering its topology or node features. Topology augmentation methods remove
or add nodes or edges, and feature augmentation methods alter the node
features by masking particular columns, dropping features at random, or
randomly shuffling the node features (Zhu et al., 2020b, 2021b; Velickovic et
al., 2019; Thakoor et al., 2021). Explicit graph augmentation methods help to
better capture the similarity between the nodes. Effectively, if two nodes
have similar augmentations, their representations are pulled together by the
contrastive loss.

GNN Encoder. The augmented graphs are then passed through a GNN-based encoder
to obtain the augmented node views. The GNN encoder produces node
representations by aggregating the node features in a neighborhood as follows:

(1)
$\boldsymbol{H}^{l}=\sigma(\boldsymbol{\tilde{A}}_{sym}\boldsymbol{H}^{l-1}\boldsymbol{W}^{l-1}),\quad\boldsymbol{H}^{0}=\boldsymbol{X},$

where $\boldsymbol{H}^{l}_{L}$ is the node representations at layer $l$ of the
encoder, $\boldsymbol{W}^{l}\in\mathbb{R}^{d_{l}\times d_{l-1}}$ is the weight
matrix in layer $l$ of the encoder, and $\sigma$ is the activation function.
Crucially, the Adjacency matrix $\boldsymbol{\tilde{A}}_{sym}$ aggregates
every node’s features with the features of nodes in its immediate
neighborhood. For a multi-layer graph encoder, it iteratively aggregates
features in a multi-hop neighborhood of every node to learn its
representation. Hence, it smooths out the node representations and produces
similar representations for the nodes within the same multi-hop neighborhood.

Contrastive Loss. Finally, the contrastive loss distinguishes the
representations of the same node in two different augmented views from other
node representations. For example the commonly used InfoNCE loss (Oord et al.,
2018) is:

(2)
$\begin{split}l(\boldsymbol{u}_{i},\boldsymbol{v}_{i})\\!=\\!-\log\\!\frac{e^{\text{sim}(\boldsymbol{u}^{i},\boldsymbol{v}^{i})/\tau}}{e^{\text{sim}(\boldsymbol{u}^{i},\boldsymbol{v}^{i})/\tau}\\!+\\!\sum_{\begin{subarray}{c}k\neq
i\end{subarray}}e^{\text{sim}(\boldsymbol{u}^{i},\boldsymbol{u}^{k})/\tau}\\!+\\!\sum_{\begin{subarray}{c}k\neq
i\end{subarray}}e^{\text{sim}(\boldsymbol{v}^{i},\boldsymbol{v}^{k})/\tau}},\end{split}$

where $\boldsymbol{u}_{i},\boldsymbol{v}_{i}$ are representations of two
different augmented views of node $i$,
$\text{sim}(\boldsymbol{v}^{i},\boldsymbol{v}^{k})=s(g(\boldsymbol{u}),g(\boldsymbol{v}))$
where $s(.,.)$ is the cosine similarity and $g(.)$ is a nonlinear projection
to enhance the expression power and $\tau$ is a temperature parameter.

Intuitively, existing graph CL methods capture the similarity between nodes in
a graph. Under homophily, nodes in a neighborhood have similar labels and
features. Such nodes have similar augmented views. Therefore, the contrastive
loss pulls the representations of the nodes in the same class together and
distinguishes them from other classes.

###  2.2. Graphs under Heterophily

Under heterophily, connected nodes may have different class labels and
dissimilar features. For example, in a dating network, most people tend to
connect with people of the opposite gender, while in protein structures,
different amino acid types are more likely to connect to each other (Zhu et
al., 2020c).

Homophily Ratio. To quantify how likely nodes with similar labels are
connected in the graph, homophily ratio, $\beta$,, is defined as follows (Pei
et al., 2020):

$\beta=\cfrac{1}{|V|}\sum\limits_{v\in V}\cfrac{\text{Number of }v\text{’s
neighbors who have the same label as }v}{\text{Number of }v\text{’s
neighbors}}$

For larger values of $\beta$, it is more likely that nodes with the same
labels are connected together.

Existing graph CL methods have a very poor performance under heterophily, or
low homophily ratio, and cannot learn high-quality representations, as we will
discuss next.

##  3\. Graph CL under Heterophily

In this section, we first discuss the challenges of graph CL under heterophily
or low homophily. Then, we present our approach to overcome these challenges
and learn high-quality representations.

Challenges. Learning high-quality representations under heterophily, without
having access to labels, is very challenging. First, under heterophily, nodes
in a neighborhood have different class labels and dissimilar features. In this
setting, aggregating features of nodes in a neighborhood using a GNN encoder
fades out the dissimilarity between representations of nodes in different
classes and makes them indistinguishable. Indeed, under heterophily, it is
crucial to leverage both similarities and dissimilarities of a node to its
neighborhood to obtain high-quality representations. However, without having
access to the labels, it is not clear how the node features should be
aggregated. In fact, even the homophily ratio cannot be calculated without
having access to the labels. Second, under heterophily, explicit graph
augmentations leveraged by existing graph CL methods may not be helpful in
learning high-quality representations. In particular, topology augmentations
such as edge drop that are most effective under homophily (Zhu et al., 2021b),
may drastically harm the performance under heterophily (see Table 1). This is
because nodes in a neighborhood have similar labels under homophily, but may
have different labels under heterophily. Hence, while the two augmented
versions of the same node with dropped edges are similar under homophily,
augmented versions of the same node may not be similar under heterophily as
the dropped edges may be connected to different labels. In this setting,
maximizing the similarity between representations of the dissimilar
augmentations results in a poor performance.

Due to the above reasons, existing graph CL methods that contrast different
explicitly augmented views of a node obtained using a GNN encoder cannot yield
separable representations for different classes, under heterophily. This
yields a poor generalization performance for the downstream classifier, as we
confirm by our experiments. Next, we discuss how we overcome the above
challenges.

###  3.1. Graph CL via Graph Filters

As discussed, under heterophily, it is crucial to leverage both similarities
and dissimilarity between the node features in a neighborhood to be able to
learn high-quality representations. However, without having access to the
labels, it is not clear how the node features in a neighborhood should be
aggregated. To address the above challenges, our key idea is to generate two
filtered representations for every node using the same encoder. In particular,
the first (non-smooth) representation is generated using a high-pass filter
which captures the dissimilarity of the node feature to its neighborhood. The
second (smooth) representation is generated using a low-pass filter which
captures the similarity of the node feature to its neighborhood. We note that
the smooth representation is similar to the representation learned by a
typical GNN-based encoder. Then, we learn the final node representations by
contrasting the smooth and non-smooth representations. In doing so, we can
learn rich node representation based on a combination of the smooth and non-
smooth components.

Next, we introduce high-pass and low-pass graph filters, and discuss how they
can be leveraged to learn smooth and non-smooth node representations.

###  3.2. High-pass and Low-pass graph filters

The adjacency and Laplacian matrices can be leveraged to filter the smooth and
non-smooth graph components, and capture similarity and dissimilarity of node
features to their neighborhoods.

Specifically, multiplication of Laplacian with a graph signal
$\boldsymbol{\hat{L}}_{sym}\boldsymbol{x}=\sum_{i}\lambda_{i}\boldsymbol{u}_{i}\boldsymbol{u}_{i}^{T}\boldsymbol{x}$,
acts as a filtering operation over $\boldsymbol{x}$, adjusting the scale of
the components of $\boldsymbol{x}$ in the frequency domain. The entries of
every eigenvector, $\boldsymbol{u}_{i}$ aligns with a cluster of connected
nodes in the graph. For the Laplacian matrix, a smaller eigenvalue
$\lambda_{i}$ corresponds to a smoother eigenvector $\boldsymbol{u}_{i}$, and
corresponds to a larger cluster of connected nodes. On the other hand, a
larger $\lambda_{i}$ corresponds to non-smooth eigenvectors
$\boldsymbol{u}_{i}$, which identify smaller clusters of closely connected
nodes in the graph. A Laplacian filter magnifies the part of the signal that
aligns well with basis functions corresponding to large eigenvalues
$\lambda_{i}\in(1,2)$ and suppresses the part the signal that aligns with
basis functions corresponding to small eigenvalues $\lambda_{i}\in[0,1]$. That
means, for the small clusters of nodes that have a large alignment with
$\boldsymbol{u}_{i}$ corresponding to $\lambda_{i}>1$, the projection
$\lambda_{i}\boldsymbol{u}_{i}\boldsymbol{u}_{i}^{T}\boldsymbol{x}$ amplifies
$\boldsymbol{x}$ within the cluster and consequently magnifies the difference
in $\boldsymbol{x}$ among the nodes within that cluster. On the other hand,
for the larger clusters that align well with $\boldsymbol{u}_{i}$
corresponding to $\lambda_{i}<1$, the projection
$\lambda_{i}\boldsymbol{u}_{i}\boldsymbol{u}_{i}^{T}\boldsymbol{x}$ suppresses
$\boldsymbol{x}$ within the cluster and reduces the differences in
$\boldsymbol{x}$ among the nodes within that cluster. Hence the Laplacian
matrices can be generally regarded as high-pass filters (Ekambaram, 2014),
that enlarge the differences in node features over small clusters, and smooths
out the differences over larger clusters in the graph. On the other hand,
affinity matrices, such as the normalized adjacency matrix, can be treated as
low-pass filters (Nt and Maehara, 2019), which suppress and filter out non-
smooth components of the signals. This is because all of the eigenvalues of
the affinity matrices are smaller than 1, i.e., $\lambda_{i}\in(-1,1]$.

On the node level, left multiplying $\boldsymbol{\hat{L}}_{sym}$ and
$\boldsymbol{\hat{A}}_{sym}$ filters with $\boldsymbol{x}$ can be understood
as diversification and aggregation operations, respectively (Luan et al.,
2020). In particular, a typical GNN filters smooth graph frequencies by
aggregating the node representations with those of their neighbors, using the
adjacency matrix, i.e.

(3)
$\displaystyle(\boldsymbol{\hat{A}}_{sym}\boldsymbol{x})_{i}=\sum_{j\in\mathcal{N}_{i}}\frac{1}{\boldsymbol{D}_{ii}}\boldsymbol{x}_{j}.$

Hence, it results in similar representations for the nodes in a neighborhood.
In contrast, the high-pass filter only preserves the high-pass frequencies,
using the Laplacian matrix, i.e.

(4)
$\displaystyle(\boldsymbol{\hat{L}}_{sym}\boldsymbol{x})_{i}=\sum_{j\in\mathcal{N}_{i}}\frac{1}{\boldsymbol{D}_{ii}}(\boldsymbol{x}_{i}-\boldsymbol{x}_{j}).$

In doing so, it magnifies the dissimilarities between the nodes and make the
representations of nodes in a neighborhood distinguishable.

Since $\boldsymbol{\hat{L}}_{sym}+\boldsymbol{\hat{A}}_{sym}=\boldsymbol{I}$,
both filters capture complementary information and their combination using a
contrastive loss allow learning richer representations, as we discuss next.

###  3.3. Generating Graph Views via Graph Filters

As discussed, the key idea of our HLCL framework is to leverages a high-pass
filter to generate diverse and distinguishable node representations, and
contrast them with smooth and similar node representations generated by a low-
pass filter. To do so, we leverage the normalized Laplacian matrix
$\boldsymbol{\hat{L}}_{sym}$ and adjacency matrix $\boldsymbol{\hat{A}}_{sym}$
as the diversification and aggregation operations in Eq. (3), (4). We note
that other types of high-pass and low-pass filters can be used in a similar
way in our framework.

More specifically, we input the graph $\boldsymbol{X}$ into a graph encoder,
and apply a high-pass filter $\boldsymbol{F}_{HP}=\boldsymbol{\hat{L}}_{sym}$
and a low-pass filter $\boldsymbol{F}_{LP}=\boldsymbol{\hat{A}}_{sym}$ to the
encoder to generate high-pass node representations $\boldsymbol{H}_{H}$ and
low-pass node representations $\boldsymbol{H}_{L}$ as follows:

(5) $\displaystyle\boldsymbol{H}_{H}^{l}$
$\displaystyle=\sigma(\boldsymbol{F}_{HP}\boldsymbol{H}^{l-1}_{H}\boldsymbol{W}^{l-1}),$
(6) $\displaystyle\boldsymbol{H}_{L}^{l}$
$\displaystyle=\sigma(\boldsymbol{F}_{LP}\boldsymbol{H}^{l-1}_{L}\boldsymbol{W}^{l-1}),$

where $\boldsymbol{H}^{l}_{L}$, and $\boldsymbol{H}^{l}_{H}$ are the low-pass
filtered and high-pass filtered representations at layer $l$ of the encoder,
$\boldsymbol{W}^{l}\in\mathbb{R}^{d_{l}\times d_{l-1}}$ is the weight matrix
in layer $l$ of the encoder, $\sigma$ is the activation function, and we have
$\boldsymbol{H}^{0}_{L}=\boldsymbol{H}^{0}_{H}=\boldsymbol{X}$.

The high-pass filter $\boldsymbol{F}_{H}$ filters out the low-frequency
signals and preserves the high-frequency signals. In doing so, it captures the
difference between features of every node with the features of the nodes in
its neighborhood. Using a high-pass encoder within a multi-layer encoder
iteratively captures the difference between features of the nodes in a multi-
hop neighborhood of a node. Hence, it makes the representations of nodes that
have different features from their neighbors distinct in their multi-hop
neighborhood.

On the other hand, the low-pass filter, $\boldsymbol{F}_{L}$, resembles a
typical GNN, which only preserves the low-frequency signals by aggregating
every node’s features with the features of nodes in its immediate
neighborhood. Using the low-pass filter within a multi-layer graph encoder, it
iteratively aggregates features in a multi-hop neighborhood of every node to
learn its representation. Hence, it smooths out the node representations and
produces similar representations for the nodes within the same multi-hop
neighborhood.

While the low-pass filter is essential for learning good representations in
smooth graphs, it cannot produce distinguished representations for graphs that
are non-smooth, especially under heterophily. For such graphs, the high-pass
filter is crucial to provide distinct representations. The combinations of
both filters provide complementary information and allow learning both smooth
and non-smooth components of the graphs simultaneously. Hence, it enables
learning richer representations, particularly under heterophily.

Scalability via Message Passing. The high-pass and low-pass filtered
representations can be obtained through message passing in an inductive
manner, according to Eq. (3), (4), without the need to explicitly calculate
the Laplacian matrix. In particular, the high-pass filtered representations
can be obtained by iteratively differentiating the representations of a node
and those of its neighbors, and the low-pass filtered representations can be
obtained by aggregating the node’s representation with those of its neighbors.
Formally:

(7) $\displaystyle\boldsymbol{\hat{h}}_{i}^{l}$
$\displaystyle=\sigma(\boldsymbol{W}^{l-1}\boldsymbol{h}_{i}^{l-1}),$ (8)
$\displaystyle(\boldsymbol{h}_{i}^{l})_{L}$
$\displaystyle=\Sigma_{j\in\\{\mathcal{N}_{i}\cup\\{i\\}\\}}(\boldsymbol{\hat{h}}_{i}^{l}+\boldsymbol{\hat{h}}_{j}^{l}),$
(9) $\displaystyle(\boldsymbol{h}_{i}^{l})_{H}$
$\displaystyle=\Sigma_{j\in\\{\mathcal{N}_{i}\cup\\{i\\}\\}}(\boldsymbol{\hat{h}}_{i}^{l}-\boldsymbol{\hat{h}}_{j}^{l}).$

This is the same approach used to train common GNNs on large graphs. Hence,
our method will have the same complexity as conducting a normal GNN message
passing with an additional message being passed. This makes our method
scalable to large graphs, as we also confirm in our experiments.

Explicit graph augmentation. We note that the graph $\boldsymbol{X}$ can be
optionally explicitly augmented before entering the encoder. While explicit
augmentation do not provide a considerable benefit and can even be harmful
under heterophily, it is crucial for graphs with homophily. We will study in
details the effect of explicit augmentation under homophily and heterophily,
in our experiments.

Our HLCL framework is demonstrated in Fig. 1.

Algorithm 1 Contrastive Learning with Graph Filters (HLCL)

1:for epoch=1,2,3,… do

2: Input graph $\mathcal{G}$ into the shared graph Encoder $f(\cdot)$

3: Generate high-frequency-signal node embeddings: $\boldsymbol{H}_{H}^{l}$ =
$\sigma(\boldsymbol{F}_{HP}\boldsymbol{H}^{l-1}_{H}\boldsymbol{W}^{l-1})$

4: Generate low-frequency-signal node embeddings:
$\boldsymbol{H}_{L}^{l}=\sigma(\boldsymbol{F}_{LP}\boldsymbol{H}^{l-1}_{L}\boldsymbol{W}^{l-1})$

5: Compute the contrastive objective $\mathcal{L}$ with Eq. (11)

6: Update parameters by applying stochastic gradient ascent to minimize
$\mathcal{L}$

7:end for

###  3.4. The Contrastive Learning Framework

After generating the low-pass and high-pass filtered graph views, we pass them
through a shared non-linear projection head and employ a contrastive objective
that enforces the filtered representations of each node in the two views to
agree with each other.

(a) Chameleon - GRACE

(b) Cora - GRACE

(c) Chameleon - HLCL

(d) Cora - HLCL

Figure 2. t-SNE visualization of final representations of chameleon and cora
generated by HLCL and GRACE.

Non-linear projection head. Before contrasting the high-pass and low-pass
filtered representations, we pass them to a non-linear projection head
$g(\cdot)$, which maps the filtered views to another latent space where the
contrastive loss is calculated. This has been shown to improve the performance
(Chen et al., 2020; You et al., 2020; Zhu et al., 2020b, a), and we also
confirm its effect in our experiment. In our setting, we use a two-layer
perceptron network to obtain $\boldsymbol{z}_{h}\\!=\\!g(\boldsymbol{H}_{H})$
and $\boldsymbol{z}_{l}\\!=\\!g(\boldsymbol{H}_{L})$. We use the projection
head only during the contrastive training, and use the low-pass filtered
representations $\boldsymbol{H}_{L}$ in the downstream task.

Contrastive loss. For every node $i$, its projected representation generated
by the low-pass filter, $\boldsymbol{z}_{l}^{i}$, is treated as the anchor,
and the one generated by the high-pass filter, $\boldsymbol{z}_{l}^{i}$, is
treated as the corresponding positive sample. Formally, we have:

(10)
$l(\boldsymbol{z}_{l}^{i},\boldsymbol{z}_{h}^{i})={\text{sim}(\boldsymbol{z}_{l}^{i},\boldsymbol{z}_{h}^{i})/\tau},$

where $\text{sim}(\boldsymbol{z}_{l}^{i},\boldsymbol{z}_{h}^{i})$ is the
cosine similarity between $\boldsymbol{z}_{l}^{i}$ and
$\boldsymbol{z}_{h}^{i}$, and $\tau$ is a temperature parameter.

Notably, the high-pass filter alleviates the need for using negative pairs in
the contrastive loss, by automatically producing dissimilar representations
for different nodes. Empirically, we also observed no improvement in the
performance by incorporating the negative pairs, in presence of the high-pass
filter.

Since two views are symmetric, the loss for another view,
$l(\boldsymbol{z}_{h}^{i},\boldsymbol{z}_{l}^{i})$, is defined in a similar
fashion. The overall objective to be maximized is then defined as the average
over all positive pairs. Formally, we minimize:

(11)
$\vspace{-2mm}\mathcal{L}=-\frac{1}{2N}\sum_{i=1}^{N}[l(\boldsymbol{z}_{l}^{i},\boldsymbol{z}_{h}^{i})+l(\boldsymbol{z}_{h}^{i},\boldsymbol{z}_{l}^{i})].$

Effectively, maximizing the agreement between the low-pass and high-pass views
pulls away the representation of nodes with different features from their
neighborhood, and allows them to be distinguished from their neighbors.

Final representations. After minimizing the contrastive loss in Eq. (11), we
use the output of the low-pass filter (the typical GNN) as the final
representation. Note that the parameters of the encoder are learned by
contrasting the low-pass representation with high-pass representations. Hence,
the output of the low-pass encoder is different than that of existing graph CL
methods that only use GNN-based (low-pass) encoders during contrastive
learning. Indeed, we do not need to rely on the high-pass filter during the
inference. The pseudocode is illustrated in Alg. 1.

###  3.5. Effect of HP and LP Filters under Different Homophily Ratios

In general, contrasting the high-pass filtered view with its low-pass
counterpart pushes away the representations of nodes that have dissimilar
features to the other nodes in their neighborhood, and allows them to be
distinguished better. In particular, the high-pass filter is essential for
separating the classes under heterophily, and the low-pass filter is essential
for learning high-quality representations under homophily. Nevertheless, real-
world networks often have neighborhoods with medium homophily ratio (see Table
2, 3). In such cases, both filters are essential for learning rich
representations. Here, we discuss the effect of high-pass and low-pass filters
in neighborhoods with different homophily ratios, and explain why contrasting
the filtered representations does not result in a significant harm in high- or
low-homophily neighborhoods.

Heterophily. Under medium or low homophily ratio, a fraction of nodes in the
neighborhood have different labels and dissimilar features to the rest of the
nodes in the same neighborhood. As long as homophily ratio is not nearly zero,
both filters are essential to obtain rich and separable representations. In
particular, the low-pass filter is required to aggregate features of similar
nodes, and the high-pass filter is required to distinguish features of
dissimilar nodes in the same neighborhood. By contrasting the high-pass and
low-pass filtered features, HLCL is able to learn rich and distinguishable
class representations under heterophily. Note that structural augmentation can
drastically harm the performance under heterophily, as it reduces the
effectiveness of the graph filters (see Table 4). Additional feature
augmentation, in particular on the low-pass filter can slightly boost the
performance.

Homophily. Under high homophily ratio, the low-pass filter aggregates the node
features in a neighborhood and makes their representations similar to each
other. On the other hand, the high-pass filter magnify the dissimilarity
between node features in a neighborhood. In this case, explicit structural
graph augmentations, in particular dropping edges or nodes, effectively
alleviate the adverse effect of the high-pass filter and considerably boost
the performance, as can be seen in Table 4. Additional features and structural
augmentation on the low-pass filter can further improve the quality of the
learned representations, as also confirmed by prior work (Zhu et al., 2021b).

Fig. 2 compares t-SNE visualization of the learned representations with HLCL
compare to GRACE, which is a state-of-the-art Graph CL method. We see that
under heterophily (Chameleon), HLCL representations of every class form
smaller compact clusters, which allows the downstream linear model to separate
the classes. In contrast, GRACE representations are spread out and classes are
not easily separable. In addition, under homophily (Cora), the high-pass
filter combined with explicit graph augmentations allows HLCL to obtain
separable high-quality class representations. Effectively, HLCL achieves
nearly the same downstream performance as GRACE under homophily, as we confirm
by our experiments.

##  4\. Experiments

In this section, we evaluate the node representations learned with HLCL, under
linear probe. We compare HLCL with existing graph CL methods, and conduct an
extensive ablation study to evaluate the effect of each of HLCL’s components.

Datasets. We conduct our experiments on five widely-used public benchmark
datasets with different levels of homophily ratios, $\beta$. We show the
statistics of the datasets including $\beta$, the number of nodes, edges, and
classes, in table 2. For graphs with homophily, we use the citation networks
including Cora and Citeseer (Yang et al., 2016). For graphs with heterophily,
we use the Wikipedia network and the web page networks including Chameleon,
Squirrel, and Texas (Rozemberczki et al., 2021; Pei et al., 2020). In
addition, to illustrate the scalability of HLCL, we apply it to large-scale
real-world datasets recently provided by (Lim et al., 2021). The statistics of
the datasets are shown in Table 3. We repeat the experiments 10 times for
smaller benchmark datasets, and 3 times for large real-world datasets, using
early-stopping, and report the average accuracy as the final result. For each
run, following CPGNN (Zhu et al., 2020a) and GRACE (Zhu et al., 2020b), we
randomly select 10% nodes for training, 10% nodes for validation, and 80%
nodes for testing.

Table 1. Existing graph augmentation methods are highly ineffective for graph CL under heterophily. HLCL achieves up to 10% improvement, over the best graph augmentation.  |  | Chameleon | Squirrel | Texas
---|---|---|---|---
| HLCL (no-aug) |  48.03 $\pm$ 3.1 |  33.44 $\pm$ 1.7 |  64.21 $\pm$ 11.2
Topo | ER |  34.23 $\pm$ 3.8 |  25.14 $\pm$ 2.3 |  52.63 $\pm$ 10.7
ND |  36.02 $\pm$ 1.9 |  26.70 $\pm$ 1.8 |  50.53 $\pm$ 12.2
EA |  38.20 $\pm$ 3.1 |  26.92 $\pm$ 1.6 |  54.73 $\pm$ 9.7
RWS |  35.63 $\pm$ 3.3 |  24.59 $\pm$ 13.5 |  56.84 $\pm$ 11.7
PPR |  34.14 $\pm$ 3.5 |  24.43 $\pm$ 2.9 |  50.00 $\pm$ 6.7
Feat | FM |  37.55 $\pm$ 3.6 |  25.58 $\pm$ 1.1 |  58.42 $\pm$ 14.21
FD |  36.81 $\pm$ 3.9 |  25.75 $\pm$ 2.7 |  50.52 $\pm$ 6.7
Table 2. HLCL achieves state-of-the-art under heterophily, and a comparable performance under homophily when combined with explicit graph augmentation. | Homophily | Heterophily
---|---|---
| Cora | CiteSeer | Chameleon | Squirrel | Texas
Hom.($\beta$) | $0.83\pm.086$ | $0.71\pm.16$ | $0.25\pm.052$ | $.22\pm.038$ | $.06\pm.032$
Nodes | 2708 | 3327 | 2277 | 5201 | 183
Edges | 5278 | 4676 | 31421 | 198493 | 295
Classes | 6 | 7 | 5 | 5 | 5
HLCL |  82.34 $\pm$ 2.7 |  71.35 $\pm$ 1.4 |  49.78 $\pm$ 1.8 |  34.11 $\pm$ 1.9 |  65.26 $\pm$ 7.8
HLCL (no-aug) |  77.09 $\pm$ 1.7 |  64.34 $\pm$ 1.5 |  48.04 $\pm$ 3.1 |  33.44 $\pm$ 1.7 |  64.21 $\pm$ 11.2
Raw feature | 64.8 | 64.6 | 31.61 | 24.43 | 52.63
DeepWalk |  75.7 $\pm$ 1.7 |  50.5 $\pm$ 1.6 |  27.51 $\pm$ 3.1 |  25.47 $\pm$ 2.4 |  40.00 $\pm$ 15.9
DeepWalk + features |  73.1 $\pm$ 2.3 |  47.6 $\pm$ 1.5 |  36.21 $\pm$ 4.6 |  26.23 $\pm$ 1.8 |  53.68 $\pm$ 10.2
DGI |  82.60 $\pm$ 0.4 |  68.80 $\pm$ 0.7 |  40.48 $\pm$ 1.9 |  27.95 $\pm$ 0.9 |  60.00 $\pm$10.8
BGRL |  74.67 $\pm$ 0.6 |  64.25 $\pm$ 2.4 |  38.20 $\pm$ 1.4 |  26.03 $\pm$ 0.9 |  61.05 $\pm$ 11.1
GRACE |  83.30 $\pm$ 0.4 |  72.10 $\pm$ 0.5 |  37.37 $\pm$ 0.6 |  28.67 $\pm$ 0.9 |  62.6 $\pm$ 7.2
MixHop |  85.34 $\pm$ 0.4 |  73.23 $\pm$ 0.5 |  46.84 $\pm$ 3.5 |  36.42 $\pm$ 3.4 |  62.15 $\pm$ 2.5

HLCL setup. We employ a two-layer GNN (Kipf and Welling, 2016) as our low-pass
encoder, and consider an additional high-pass channel with
$\boldsymbol{\hat{L}}_{sym}$ as the message passing filter to capture the
high-frequency signals from the graphs. The high-pass channel generates
augmented node representations to be contrasted with those encoded by the GNN.
The high-pass channel shares the same weight parameters with the GNN, but
generate representations with different filters. The final representations is
generated by the GNN encoder.

Linear Probe Evaluation. We follow the evaluation protocol used in (Zhu et
al., 2020b). Models are first trained in a self-supervised manner without
labels. Then, we fed the final node embeddings into a $l_{2}$-regularized
logistic regression classifier to fit the labeled data.

###  4.1. Graph CL under Heterophily

HLCL vs Explicit Augmentation. First, we compare HLCL with a state-of-the-art
graph CL method, namely GRACE (Zhu et al., 2020b) with different explicit
graph augmentations, under heterophily. We consider topology augmentation
methods including Edge Removing (ER), Node Dropping (ND), Edge Adding (EA),
Subgraph with Random Walk (RWS), and Personalized PageRank (PPR), as well as
feature augmentation method including Feature Masking (FM) and Feature
Dropping (FD) for generating different graph augmentations. We compare these
methods with HLCL. Except for the proposed high-pass filter, we do not use any
other explicit graph augmentation.

Table 1 shows that our method achieves a remarkable boost of up to 10%
compared to the best graph augmentation method. This confirms the necessity of
utilizing the non-smooth graph components under heterophily. Note that even
though topology and feature augmentation methods benefit the homophily graphs,
they are highly ineffective for graph CL under heterophily.

Table 3. HLCL achieves a noticeably higher accuracy on realistic large-scale datasets compared to other GCL methods. HLCL outperforms SOTA Graph CL methods by up to 6%. | Penn94 | Twitch-Gamers | Pokec | Genius
---|---|---|---|---
Hom.($\beta$) | $0.48\pm.042$ | $0.55\pm.040$ | $0.42\pm.10$ | $0.48\pm.21$
Nodes | 41,554 | 168,114 | 1,632,803 | 421,961
Edges | 1,362,229 | 6,797,557 | 1,632,803 | 984,979
Classes | 2 | 2 | 2 | 2
HLCL |  68.12 $\pm$ 3.5 |  66.96 $\pm$ 0.9 |  56.50 $\pm$ 1.7 |  85.39 $\pm$ 2.4
DGI |  62.86 $\pm$ 0.37 |  62.47 $\pm$ 2.8 |  54.56 $\pm$ 0.6 |  83.45 $\pm$ 1.8
BGRL |  58.82 $\pm$ 0.6 |  55.09 $\pm$ 2.3 |  53.53 $\pm$ 1.2 |  76.38 $\pm$ 2.6
GRACE |  62.52 $\pm$ 0.15 |  57.08 $\pm$ 0.11 |  53.61 $\pm$ 0.59 |  79.58 $\pm$ 2.9

HLCL vs Self-supervised Baselines. Next, we compare HLCL with existing
baselines for self-supervised representation learning. We consider traditional
representation learning methods like DeepWalk (Perozzi et al., 2014), deep
learning methods including DGI (Velickovic et al., 2019), BGRL (Thakoor et
al., 2021), and GRACE (Zhu et al., 2020b), and other popular representation
learning baselines like Raw Features and DeepWalk + Raw Features as baselines.
We also include MixHop (Abu-El-Haija et al., 2019) in our experiments as the
supervised learning baseline. Table 2 compares the performance of HLCL when
used on its own, HLCL (no-aug), and when it is applied to the graphs that are
augmented with Edge Removing (ER) on the graphs with homophily and Feature
Masking (FM) on the graphs with heterophily. We see that HLCL shows a
significant boost on graphs with heterophily and a comparable performance on
the graphs with homophily. Even without explicit augmentation, HLCL surpasses
other baselines on graphs with heterophily, which confirms the effectiveness
of the high-pass channel. Importantly, applying HLCL to graphs that are
explicitly augmented achieves a comparable performance under homophily. Thus,
the high-pass filter combined with explicit augmentations does not harm the
performance on such graphs. Compared to supervised learning model such as
MixHop trained in an end-to-end manner, HLCL achieves a comparable or superior
performances. This, demonstrates the effectiveness of our design.

Large-scale Experiments Next, to confirm effectiveness and scalability of
HLCL, we apply it to large-scale real-world datasets. Table 3 shows that HLCL
achieves up to 6% higher accuracy on large-scale datasets compared to
baselines, and easily scales to large graphs.

###  4.2. Ablation Studies

Table 4. The result on combining HLCL with different graph view augmentations. HP represents augmentation on the high-pass channel only, LP represents augmentation on the low-pass channel only, HL represents augmentation on both channels. Both topology and feature augmentations are included in the experiments. The worst results are highlighted in gray.  |  | Homophily | Heterophily
---|---|---|---
|  | Cora | CiteSeer | Chameleon | Squirrel | Texas
|  HLCL (no-aug) |  77.09 $\pm$ 1.7 |  64.34 $\pm$ 1.5 |  48.03 $\pm$ 3.1 |  33.44 $\pm$ 1.7 |  64.21 $\pm$ 11.2
HP Topo | ER |  80.80 $\pm$ 3.0 |  71.20 $\pm$ 1.3 |  36.11 $\pm$ 4.1 |  26.26 $\pm$ 2.3 |  57.36 $\pm$ 8.90
ND |  78.42 $\pm$ 2.0 |  70.24 $\pm$ 2.0 |  35.80 $\pm$ 2.7 |  26.79 $\pm$ 1.6 |  61.05 $\pm$ 12.0
| EA |  74.04 $\pm$ 2.9 |  65.75 $\pm$ 3.2 |  35.81 $\pm$ 3.3 |  26.79 $\pm$ 2.0 |  60.53 $\pm$ 7.90
HP Feat | FM |  77.13 $\pm$ 2.9 |  64.67 $\pm$ 1.3 |  49.08 $\pm$ 3.8 |  33.80 $\pm$ 1.7 |  62.63 $\pm$ 9.8
FD |  77.94 $\pm$ 2.6 |  66.05 $\pm$ 1.8 |  47.07 $\pm$ 4.0 |  32.71 $\pm$ 2.0 |  61.57 $\pm$ 6.2
LP Topo | ER |  77.94 $\pm$ 3.1 |  65.18 $\pm$ 1.9 |  37.07 $\pm$ 3.4 |  25.36 $\pm$ 2.0 |  57.37 $\pm$ 7.60
ND |  75.66 $\pm$ 1.6 |  61.28 $\pm$ 2.6 |  36.15 $\pm$ 2.0 |  26.53 $\pm$ 1.6 |  59.47 $\pm$ 8.50
| EA |  80.73 $\pm$ 2.2 |  68.35 $\pm$ 2.0 |  39.08 $\pm$ 2.0 |  26.75 $\pm$ 1.5 |  61.05 $\pm$ 11.8
LP Feat | FM |  78.46 $\pm$ 2.4 |  66.68 $\pm$ 1.7 |  49.78 $\pm$ 1.8 |  34.11 $\pm$1.9 |  65.26 $\pm$ 7.8
FD |  78.42 $\pm$ 2.7 |  67.75 $\pm$ 1.7 |  47.46 $\pm$ 3.2 |  33.65 $\pm$ 1.7 |  63.15 $\pm$ 7.4
HL Topo | ER |  82.34 $\pm$ 2.7 |  71.35 $\pm$ 1.4 |  37.29 $\pm$ 2.6 |  25.60 $\pm$ 1.6 |  57.37 $\pm$ 8.3
ND |  76.10 $\pm$ 2.6 |  65.90 $\pm$ 2.6 |  35.81 $\pm$ 1.8 |  25.39 $\pm$ 1.5 |  61.58 $\pm$ 8.8
| EA |  81.02 $\pm$ 2.5 |  70.02 $\pm$ 3.6 |  37.46 $\pm$ 1.8 |  26.12 $\pm$ 1.7 |  60.53 $\pm$ 7.9
HL Feat | FM |  78.60 $\pm$ 2.3 |  66.08 $\pm$ 2.0 |  49.52 $\pm$ 3.6 |  33.90 $\pm$ 1.5 |  63.68 $\pm$ 8.9
FD |  77.50 $\pm$ 3.0 |  66.59 $\pm$ 1.7 |  48.42 $\pm$ 4.0 |  33.49 $\pm$ 1.8 |  63.68 $\pm$ 6.8
Table 5. HLCL with different graph filters in the final encoder. HP Concatenate LP represents using both high-pass filters and concatenating the output representations; HP Aggregate LP represents using both high-pass filters and aggregating the output representations. | Homophily | Heterophily
---|---|---
| Cora | CiteSeer | Chameleon | Squirrel | Texas
LP |  77.09 $\pm$ 1.7 |  64.34 $\pm$ 1.5 |  48.04 $\pm$ 3.1 |  33.44 $\pm$ 1.7 |  64.21 $\pm$ 11.2
HP |  51.94 $\pm$ 2.9 |  36.22 $\pm$ 2.5 |  35.58 $\pm$ 3.1 |  29.83 $\pm$ 1.6 |  65.26 $\pm$ 10.3
HP Concatenate LP |  66.47 $\pm$ 3.6 |  55.96 $\pm$ 2.6 |  41.09 $\pm$ 3.6 |  30.86 $\pm$ 1.9 |  65.21 $\pm$ 9.4
HP Aggregate LP |  65.33 $\pm$ 2.8 |  53.47 $\pm$ 3.1 |  38.77 $\pm$ 3.4 |  28.00 $\pm$ 1.5 |  63.15 $\pm$ 11.7
Table 6. Using high-pass filter in existing Graph CL methods. Significant performance drops are highlighted in gray. | Homophily | Heterophily
---|---|---
| Cora | CiteSeer | Chameleon | Squirrel | Texas
HLCL |  82.34 $\pm$ 2.7 |  71.35 $\pm$ 1.4 |  49.78 $\pm$ 1.8 |  34.11 $\pm$ 1.9 |  65.26 $\pm$ 7.8
DGI:low |  82.60 $\pm$ 0.4 |  68.80 $\pm$ 0.7 |  40.48 $\pm$ 1.9 |  27.95 $\pm$ 0.9 |  60.00 $\pm$10.8
DGI:high |  31.95 $\pm$ 2.8 |  30.54 $\pm$ 1.7 |  38.38 $\pm$ 3.5 |  29.57 $\pm$ 1.2 |  62.11 $\pm$ 10.2
BGRL:low |  74.67 $\pm$ 0.6 |  64.25 $\pm$ 2.4 |  38.20 $\pm$ 1.4 |  26.03 $\pm$ 0.9 |  61.05 $\pm$ 11.1
BGRL:high |  29.63 $\pm$ 2.8 |  24.99 $\pm$ 3.1 |  35.41 $\pm$ 3.4 |  29.57 $\pm$ 1.1 |  65.26 $\pm$ 8.2
GRACE:low |  83.30 $\pm$ 0.4 |  72.10 $\pm$ 0.5 |  37.37 $\pm$ 0.6 |  28.67 $\pm$ 0.9 |  62.6 $\pm$ 7.2
GRACE:high |  32.46 $\pm$ 2.0 |  26.55 $\pm$ 3.1 |  39.65 $\pm$ 2.9 |  33.05 $\pm$ 2.1 |  72.63 $\pm$ 9.3

HLCL with Explicit Augmentation Next, we study the effect of explicit graph
augmentation methods applied to both high-pass and the typical low-pass GNN
channels of HLCL, under different homophily ratios. We include Edge Removing
(ER), Node Dropping (ND), Edge Adding (EA), Feature Masking (FM), and Feature
Dropout (FD) as graph augmentation methods. Table 4 shows that combined with
HLCL, feature and topology augmentations considerably benefit the performance
on graphs with homophily. Topology augmentation, however, may not be helpful
under heterophily.

Output Encoder with Different Graph Filters In our experiments, we use low-
pass graph filter in our GNN encoder as the final representation encoder. To
illustrate the effectiveness of our structural design, we present an ablation
study on using different filters or combinations of filters in our final
encoder. The result is shown in table 5. We see that on most datasets low-pass
encoder achieves the highest accuracy with a large gap, and variation
involving the high-pass encoder has worse performances across all datasets
except Texas, which has a nearly zero homophily ratio. This demonstrates the
ineffectiveness of using high-pass filter directly in the representation
encoder.

Existing Graph CL methods with high-pass encoders Finally, we illustrate the
importance of our contrastive structure. We show that the main accuracy gains
on heterophily datasets are from contrasting the low- and high-pass filtered
graph views, instead of the introduction of the high-pass filter alone.
Indeed, the high-pass filter alone cannot provide high-quality representations
under heterophily, as different combinations of low-pass and high-pass filters
are required to provide good representations for different graphs. Table 6
shows that by replacing low-pass filter with high-pass filter in other graph
CL methods, such methods are able to achieve a better accuracy on some
heterophily datasets like Squirrel and Texas. However, their performances
deteriorate significantly under homophily cases, where aggregation among
neighborhoods are desired. Indeed, when using high-pass or low-pass alone, the
model cannot achieve good performance.

##  5\. Related Work

(Semi-)supervised learning on graphs. In recent years, GNNs have become one of
the most prominent tools for processing graph-structured data. In general,
GNNs utilize the adjacency matrix to learn the node representations, by
aggregating information within every node’s neighborhood (Defferrard et al.,
2016; Kipf and Welling, 2016). Existing variants, including GraphSAGE
(Hamilton et al., 2017), Graph Attention (GAT) (Veličković et al., 2017),
MixHop (Abu-El-Haija et al., 2019), SGC (Nt and Maehara, 2019), GAT
(Velickovic et al., 2019), and GIN (Xu et al., 2018), learn a more general
class of neighborhood mixing relationships, by aggregating weighted
information within a multi-hop neighborhood of every node. GNNs can be
generally seen as applying a fix, or a parametric and learnable (e.g. GAT)
low-pass graph filter to graph signals. Those with trainable parameters can
adapt to a wider range of frequency levels on different graphs. However, they
still have a higher emphasis on lower-frequency signals and discard the high-
frequency signals in a graph. While the aggregation operation makes GNNs
powerful tools for semi-supervised learning, it can make the learned node
representations indistinguishable in a neighborhood (Nt and Maehara, 2019). As
a result, typical GNNs and their variants have been long criticized for their
poor generalization performance under heterophily (Balcilar et al., 2020).

(Semi-)supervised learning under heterophily. To address over-smoothing issue
of GNNs, recent methods propose to use other types of aggregation that better
fit graphs with heterophily. Geom-GCN uses geometric aggregation in place of
the typical aggregation (Pei et al., 2020), H2GCN uses several special model
designs including separate aggregation and higher-neighborhood aggregation to
train the model for handling graphs with heterophily, and CPGNN trains a
compatibility matrix to model the heterophily level (Zhu et al., 2020a). More
recently, (Wang et al., 2019) proposed to learn an aggregation filter for
every graph from a set of based filters designed based on different ways of
normalizing the adjacency matrix. Most recently, GGCN introduced degree
corrections and signed message passing on GCN to address both oversmoothing
problems and the model’s poor performances on heterophily graphs (Yan et al.,
2021). (Zhu et al., 2021a) analyzed and designed a uniform framework for GNNs
propagations and proposed GNN-LF and GNN-HF that preserve information of
different frequency separately by using different filtering kernels with
learnable weights. FAGCN (Bo et al., 2021) and FBGNN (Luan et al., 2020) train
two separate encoders to capture the high-pass and low-pass graph signals
separately. Then they rely on labels to learn relatively complex mechanisms to
combine the outputs of the encoders. However, learning how to combine the
encoder outputs is highly sensitive to having high-quality labels. This makes
such methods highly impractical for unsupervised contrastive learning, where
the label information is not available.

Unlike the above supervised methods, we leverage the high-pass filter in the
same encoder to generate augmented graph views that are contrasted with their
low-pass counterparts to learn unsupervised representations. This is in
contrast to learning the best combination of filtered signals of different
encoders based on labels.

Contrastive learning on graphs. For contrastive learning on graphs, global
graph-level and local node-level data are augmented and contrasted in
different ways. DGI (Velickovic et al., 2019) and GMI (Peng et al., 2020)
contrast graph and node representations within one augmented view of the
original graph. More recent methods contrast global and local representations
in two augmented views. GraphCL generates graph augmentations by subgraph
sampling, node dropping, and edge perturbation and contrasts the augmented
graph representations. GCC samples and contrasts subgraphs of the original
graph (Qiu et al., 2020). MVGRL leverages node diffusion to augment the graph
and contrasts the node representations (Hassani and Khasahmadi, 2020). More
recently, contrasting the local node representations has been shown to achieve
state-of-the-art. GRACE contrasts the node representations in two graph views
augmented with feature masking and edge removal (Zhu et al., 2020b). GCA
extends this by dropping the less important edges and features, based on node
centrality and feature importance metrics (Zhu et al., 2021c). A thorough
empirical study on the combinatorial effect of different augmentations has
been conducted by (Zhu et al., 2021b). Due to the complexity of collecting
negative samples in graph data, negative-samples-free contrastive objectives
have been also studied. Among existing methods, BGRL that uses the
Bootstrapping Latent loss (Thakoor et al., 2021), and GBT uses Barlow Twins
loss (Bielak et al., 2021) are the most successful. Existing graph CL methods
explicitly augment the input graph and contrast the augmented graph
representations obtained with low-pass GNN-based encoders. In doing so, they
only capture the similarity of nodes in a neighborhood. Hence, they perform
poorly on graphs with heterophily. In contrast, we leverage low-pass and high-
pass graph filters in the same GNN-based encoder to capture and contrast
similarity and dissimilarity of nodes with their neighborhood. This allows
achieving state-of-the-art under heterophily.

##  6\. Conclusion

We proposed HLCL, a contrastive learning framework that leverages a high-pass
graph filter to generate non-smooth augmented representations to be contrasted
with their smooth counterparts, generated using the same encoder. This is
particularly beneficial for graphs with heterophily, where existing graph CL
methods are highly ineffective. Through extensive experiments, we demonstrated
that our proposed framework achieves up to 10% boost in the performance for
representation learning under the linear probe, for various graphs under
heterophily. At the same time, it provides a comparable performance on graphs
with homophily. We believe our work provides an important direction for future
work on contrastive learning under heterophily.

## References

  * (1)
  * 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_. PMLR, 21–29.
  * Balcilar et al. (2020) Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. 2020\.  Analyzing the expressive power of graph neural networks in a spectral perspective. In _International Conference on Learning Representations_.
  * Bielak et al. (2021) Piotr Bielak, Tomasz Kajdanowicz, and Nitesh V Chawla. 2021\.  Graph Barlow Twins: A self-supervised representation learning framework for graphs.  _arXiv preprint arXiv:2106.02466_ (2021).
  * Bo et al. (2021) Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. 2021\.  Beyond low-frequency information in graph convolutional networks. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 35. 3950–3957.
  * Chen et al. (2020) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. 2020.  A simple framework for contrastive learning of visual representations. In _International conference on machine learning_. PMLR, 1597–1607.
  * Chung (1997) Fan RK Chung. 1997\.  _Spectral graph theory_. Vol. 92.  American Mathematical Soc.
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016.  Convolutional neural networks on graphs with fast localized spectral filtering.  _Advances in neural information processing systems_ 29 (2016).
  * Ekambaram (2014) Venkatesan Nallampatti Ekambaram. 2014\.  _Graph-structured data viewed through a Fourier lens_.  University of California, Berkeley.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ 30 (2017).
  * Hassani and Khasahmadi (2020) Kaveh Hassani and Amir Hosein Khasahmadi. 2020.  Contrastive multi-view representation learning on graphs. In _International Conference on Machine Learning_. PMLR, 4116–4126.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ (2016).
  * Lim et al. (2021) Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. 2021.  Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods.  _Advances in Neural Information Processing Systems_ 34 (2021), 20887–20902.
  * Luan et al. (2020) Sitao Luan, Mingde Zhao, Chenqing Hua, Xiao-Wen Chang, and Doina Precup. 2020.  Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks.  _arXiv preprint arXiv:2008.08844_ (2020).
  * 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).
  * Oord et al. (2018) Aaron van den Oord, Yazhe Li, and Oriol Vinyals. 2018.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_ (2018).
  * Pei et al. (2020) Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020.  Geom-gcn: Geometric graph convolutional networks.  _arXiv preprint arXiv:2002.05287_ (2020).
  * Peng et al. (2020) Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. 2020.  Graph representation learning via graphical mutual information maximization. In _Proceedings of The Web Conference 2020_. 259–270.
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  Deepwalk: Online learning of social representations. In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_. 701–710.
  * Qiu et al. (2020) Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. 2020\.  Gcc: Graph contrastive coding for graph neural network pre-training. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 1150–1160.
  * Rozemberczki et al. (2021) Benedek Rozemberczki, Carl Allen, and Rik Sarkar. 2021.  Multi-scale attributed node embedding.  _Journal of Complex Networks_ 9, 2 (2021), cnab014.
  * Thakoor et al. (2021) Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. 2021.  Large-scale representation learning on graphs via bootstrapping.  _arXiv preprint arXiv:2102.06514_ (2021).
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ (2017).
  * Velickovic et al. (2019) Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. 2019.  Deep Graph Infomax.  _ICLR (Poster)_ 2, 3 (2019), 4.
  * Wang et al. (2019) Yewen Wang, Ziniu Hu, Yusong Ye, and Yizhou Sun. 2019\.  Demystifying graph neural network via graph filter assessment.  (2019).
  * Xu et al. (2018) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018\.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ (2018).
  * 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.
  * You et al. (2020) Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. 2020\.  Graph contrastive learning with augmentations.  _Advances in Neural Information Processing Systems_ 33 (2020), 5812–5823.
  * 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), 11168–11176.
  * Zhu et al. (2020c) Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020c.  Beyond homophily in graph neural networks: Current limitations and effective designs.  _Advances in Neural Information Processing Systems_ 33 (2020), 7793–7804.
  * Zhu et al. (2021a) Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. 2021a.  Interpreting and unifying graph neural networks with an optimization framework. In _Proceedings of the Web Conference 2021_. 1215–1226.
  * Zhu et al. (2021b) Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. 2021b.  An empirical study of graph contrastive learning.  _arXiv preprint arXiv:2109.01116_ (2021).
  * Zhu et al. (2020b) Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. 2020b.  Deep graph contrastive representation learning.  _arXiv preprint arXiv:2006.04131_ (2020).
  * Zhu et al. (2021c) Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. 2021c.  Graph contrastive learning with adaptive augmentation. In _Proceedings of the Web Conference 2021_. 2069–2080.