# Localized Graph Contrastive Learning

Hengrui Zhang
University of Illinois, Chicago
<EMAIL_ADDRESS>&Qitian Wu
Shanghai Jiao Tong University
<EMAIL_ADDRESS>&Yu Wang
University of Illinois, Chicago
<EMAIL_ADDRESS>Shaofeng Zhang
Shanghai Jiao Tong University
<EMAIL_ADDRESS>&Junchi Yan
Shanghai Jiao Tong University
<EMAIL_ADDRESS>&Philip S. Yu
University of Illinois, Chicago
<EMAIL_ADDRESS>Corresponding author.

###### Abstract

Contrastive learning methods based on InfoNCE loss are popular in node
representation learning tasks on graph-structured data. However, its reliance
on data augmentation and its quadratic computational complexity might lead to
inconsistency and inefficiency problems. To mitigate these limitations, in
this paper, we introduce a simple yet effective contrastive model named
Localized Graph Contrastive Learning (Local-GCL in short). Local-GCL consists
of two key designs: 1) We fabricate the positive examples for each node
directly using its first-order neighbors, which frees our method from the
reliance on carefully-designed graph augmentations; 2) To improve the
efficiency of contrastive learning on graphs, we devise a kernelized
contrastive loss, which could be approximately computed in linear time and
space complexity with respect to the graph size. We provide theoretical
analysis to justify the effectiveness and rationality of the proposed methods.
Experiments on various datasets with different scales and properties
demonstrate that in spite of its simplicity, Local-GCL achieves quite
competitive performance in self-supervised node representation learning tasks
on graphs with various scales and properties.

##  1 Introduction

Self-supervised learning has achieved remarkable success in learning
informative representations without using costly handcrafted labels (van den
Oord et al., 2018; Devlin et al., 2019; Banville et al., 2021; He et al.,
2020; Chen et al., 2020; Grill et al., 2020; Zhang et al., 2021; Gao et al.,
2021). Among current self-supervised learning paradigms, InfoNCE loss (van den
Oord et al., 2018) based multi-view contrastive methods (He et al., 2020; Chen
et al., 2020; Gao et al., 2021) are recognized as the most widely adopted
ones, due to their solid theoretical foundations and strong empirical results.
Generally, contrastive learning aims at maximizing the agreement between the
latent representations of two views (e.g. through data augmentation) from the
same input, which essentially maximizes the mutual information between the two
representations (Poole et al., 2019). Inheriting the spirits of contrastive
learning on vision tasks, similar methods have been developed to deal with
graphs and bring up promising results on common node-level classification
benchmarks (Velickovic et al., 2019; Hassani & Ahmadi, 2020; Zhu et al.,
2020b; 2021).

The challenge, however, is that prevailing contrastive learning methods rely
on predefined augmentation techniques for generating positive pairs as
informative training supervision. Unlike grid-structured data (e.g., images or
sequences), it is non-trivial to define well-posed augmentation approaches for
graph-structured data Zhu et al. (2021); Zhang et al. (2021). The common
practice adopted by current methods resorts to random perturbation on input
node features and graph structures (You et al., 2020), which might
unexpectedly violate the underlying data generation and change the semantic
information (Lee et al., 2021). Such an issue plays as a bottleneck limiting
the practical efficacy of contrastive methods on graphs. Apart from this, the
InfoNCE loss function computes all-pair distance for in-batch nodes as
negative pairs for contrasting signals (Zhu et al., 2020b; 2021), which
induces quadratic memory and time complexity with respect to the batch size.
Given that the model is preferred to be trained in a full-graph manner (i.e.,
batch size = graph size) since the graph structure information might be
partially lost through mini-batch partition, such a nature heavily constrains
contrastive methods for scaling to large graphs.

Some recent works seek negative-sample-free methods to resolve the scalability
issue by harnessing asymmetric structures (Thakoor et al., 2021) or feature-
level decorrelation objectives (Zhang et al., 2021). However, these methods
either lack enough theoretical justification (Thakoor et al., 2021) or
necessitate strong assumptions on the data distributions (Zhang et al., 2021).
Moreover, they still require data augmentations to generate two views of the
input graph, albeit non-contrastive and free from negative sampling. Some
other works construct positive examples using the target’s $k$-nearest-
neighbors (kNN) in the latent space (Dwibedi et al., 2021; Koohpayegani et
al., 2021; Lee et al., 2021). Nonetheless, the computation of nearest
neighbors could be cumbersome, time-consuming, and, therefore hard to scale.

Presented Work. To cope with the dilemmas above, in this paper we introduce
Localized Graph Contrastive Learning (Local-GCL in abbreviation), a light and
augmentation-free contrastive model for self-supervised node-level
representation learning on graphs. Local-GCL benefits from two key designs.
First, it does not rely on data augmentation to construct positive pairs.
Instead, inspired by the graph homophiliy theory (McPherson et al., 2001), it
directly treats the first-order neighboring nodes as the positive examples of
the target node. This not only increases the number of positive examples for
each node but also helps our model get rid of complicated data augmentations.
Besides, the computation of positive pairs can be performed in linear time and
space complexity w.r.t the graph size, bringing no additional cost for the
model. Second, to deal with the quadratic complexity curse of contrastive loss
(i.e., InfoNCE loss (van den Oord et al., 2018)), we propose a surrogate loss
function in place of the negative loss term in the vanilla InfoNCE loss, which
could be efficiently and accurately approximated within linear time and space
complexity (Rahimi et al., 2007; Liu et al., 2020; Yu et al., 2016). Such a
design greatly improves the efficiency of our model.

We evaluate the proposed methods on seven public node classification
benchmarks with various scales. The empirical results demonstrate that though
not using any graph augmentations, our method achieves state-of-the-art
performance on six of seven datasets. On the challenging Ogbn-Arxiv dataset,
our method can also give a competitive performance with a much training speed
compared with other scalable models. Experiments on three heterophily graphs
demonstrate that besides homophily graphs, Local-GCL can also perform well on
graphs with low homophily ratios.

We summarize the highlights of this paper as follows:

  * 1)

We introduce Local-GCL, a simple model for contrastive learning on graphs,
where the positive example is fabricated using the first-order neighborhood of
each node. This successfully frees node-level contrastive learning methods
from unjustified graph augmentations.

  * 2)

To overcome the quadratic complexity curse of contrastive learning, we propose
a kernelized contrastive loss computation that can precisely approximate the
original loss function within linear complexity w.r.t. graph size. This
significantly reduces the training time and memory cost of contrastive
learning on large graphs.

  * 3)

Experimental results show that without data augmentation and other cumbersome
designs Local-GCL achieves quite competitive results on a variety of graphs of
different scales and properties. Furthermore, Local-GCL demonstrates a better
balance of model performance and efficiency than other self-supervised
methods.

##  2 Background and Related Works

###  2.1 Contrastive Representation Learning

Inspired by the great success of contrastive methods in learning image
representations (van den Oord et al., 2018; Hjelm et al., 2019; Tian et al.,
2020; He et al., 2020; Chen et al., 2020), recent endeavors develop similar
strategies for node-level tasks in graph domain (Velickovic et al., 2019;
Hassani & Ahmadi, 2020; Zhu et al., 2020b; 2021). Among graph contrastive
learning methods, the most popular methods should be those based on the
InfoNCE loss (van den Oord et al., 2018) due to their simple concepts and
better empirical performance. InfoNCE-based graph contrastive learning
methods, including GRACE (Zhu et al., 2020b) and GCA (Zhu et al., 2021) aim to
maximize the similarity of positive node-node (or graph-graph) pairs (e.g.,
two views generated via data augmentation) and minimize the similarity of
negative ones (e.g., other nodes/graphs within the current batch). However,
they require well-designated data augmentations that could positively inform
downstream tasks (Tsai et al., 2021). The quadratic complexity also limits
their applications to larger batch sizes/datasets.

###  2.2 Augmentation-Free Self-supervised Learning on Graphs

Besides graph contrastive learning (Zhu et al., 2020b; 2021) and the similar
two-branched models (Thakoor et al., 2021; Zhang et al., 2021) that use graph
augmentations to create positive pairs, there is another line of work
exploring the rich structure information in the graph to create self-
supervised signals. Graph AutoEncoders (Kipf & Welling, 2016), for example,
learn node embeddings unsupervisedly through reconstructing the adjacency
matrix, while GMI (Peng et al., 2020) maximizes the mutual information of both
features and edges between inputs and outputs. Inspired by the success of
contrastive learning, some recent work explores constructing positive pairs
using reliable graph information instead of data augmentations. For example,
SUGRL (Mo et al., 2022) employs two encoder models: one is a GCN, and the
another is an MLP, to generate two sets of node embedding from different
sources. Then for each node, the positive pair can be constructed using its
GCN output and MLP output. AFGRL (Lee et al., 2021) and AF-GCL (Wang et al.,
2022) treat nodes in the target node’s multi-hop neighborhood as candidate
positive examples and use well-designed similarity measures to select the most
similar nodes as positive examples. Local-GCL, by contrast, treats all
neighbors equally without discrimination. This not only simplifies the model
design but also offers a theoretical guarantee for the effectiveness of the
proposed model. Empirical results also demonstrate that our method can achieve
better performance than theirs.

###  2.3 Random Fourier Features

Though InfoNCE-loss-based based methods are successful in self-supervised node
representation learning, their quadratic time and memory complexity with
respect to the graph size prevent them from being applied to graphs with tens
of thousands of nodes. This paper seeks to address this issue by optimizing a
surrogate loss function with Random Fourier Features (RFF or Random Features
in short) (Rahimi et al., 2007; Liu et al., 2020). RFF is an effective
technique for enhancing the scalability of kernel methods such as SVM, ridge
regression (Avron et al., 2017) and independence test (Zhang et al., 2018; Li
et al., 2021). Also, recently, RFF has been adopted to develop linear
Transformers by approximating the softmax attention (Choromanski et al., 2020;
Peng et al., 2021). Given $d$-dimensional vectors $\bm{x}$ and $\bm{y}$ and a
shift-invariant kernel $\kappa(\cdot)$, RFF constructs an explicit mapping
$\psi$: $\mathbb{R}^{d}\rightarrow\mathbb{R}^{D}$, such that
$\kappa(\bm{x},\bm{y})\approx\psi(\bm{x})^{\top}\psi(\bm{y})$, which reduces
the quadratic computation cost of the kernel matrix to a linear one w.r.t data
size. Generally, given a positive definite shift-invariant kernel
$\kappa(\bm{x},\bm{y})=f(\bm{x}-\bm{y})$, the Fourier transform $p$ of kernel
$\kappa$ is $p(\bm{\omega})=\frac{1}{2\pi}\int
e^{-j\bm{\omega}^{\prime}\Delta}k(\Delta)\mathrm{d}\Delta$, where
$\Delta=\bm{x}-\bm{y}$. Then we could draw $D$ i.i.d. samples
$\bm{\omega}_{1},\cdots,\bm{\omega}_{D}\in\mathbb{R}^{d}$ from $p$, and
$\psi(\bm{x})$ is given by:

$\displaystyle\psi(\bm{x})=\frac{\left[\cos(\bm{\omega}_{1}^{\top}\bm{x}),\cdots,\cos(\bm{\omega}_{D}^{\top}\bm{x}),\sin(\bm{\omega}_{1}^{\top}\bm{x}),\cdots,\sin(\bm{\omega}_{D}^{\top}\bm{x})\right]^{\top}}{\sqrt{D}}.$
(1)

Let $\bm{W}=[\bm{\omega}_{1},\cdots,\bm{\omega}_{D}]\in\mathbb{R}^{d\times D}$
be a linear transformation matrix, one may realize that the computation of Eq.
1 entails computing $\bm{W}^{\top}\bm{x}$. Specifically, when $\kappa(\cdot)$
is a standard Gaussian kernel (a.k.a., RBF kernel), each entry of $\bm{W}$ can
be directly sampled from a standard Gaussian distribution. The improved
variants of RFF mainly concentrate on different ways to build the
transformation matrix $\bm{W}$, so as to further reduce the computational cost
(Le et al., 2013) or lower the approximation variance (Yu et al., 2016).

##  3 Contrastive Learning on Graphs with InfoNCE Loss

The InfoNCE (van den Oord et al., 2018) loss has been employed in various
areas and has shown great power in learning informative representations in a
self-supervised manner. Given the embedding of a target data point
$\bm{z}_{i}$, together with one positive embedding $\bm{z}_{i}^{+}$ and a set
of negative embeddings $\\{\bm{z}_{j}^{-}\\}_{j=1}^{M-1}$, the InfoNCE loss
aims at discriminating the positive pair $(\bm{z}_{i},\bm{z}_{i}^{+})$ from
the negative pairs $\\{(\bm{z}_{i},\bm{z}_{j}^{-})\\}_{j=1}^{M-1}$ via the
following contrastive objective function:

$\mathcal{L}_{\rm{InfoNCE}}(i)=-\log\frac{\exp({f(\bm{z}_{i},\bm{z}_{i}^{+})/\tau})}{\exp({f(\bm{z}_{i},\bm{z}_{i}^{+})/\tau})+\sum\limits_{j=1}^{M-1}\exp({f(\bm{z}_{i}^{+},\bm{z}_{j}^{-})}/\tau)},$
(2)

where $f(\cdot,\cdot)$ is a similarity measure, usually implemented as the
simple dot product $f(\bm{x},\bm{y})=\bm{x}^{\top}\bm{y}$ (He et al., 2020;
Chen et al., 2020), and $\tau$ is the temperature hyperparameter. Note that
$\bm{z}_{i},\bm{z}_{i}^{+}$ and $\bm{z}_{i}^{-}$ are all $\bm{\ell}_{2}$
normalized to have a unit norm, i.e., $\|\bm{z}_{i}\|_{2}^{2}=1$. In the
context of node-level contrastive learning, each $\bm{z}_{i}$ denotes the
embedding of node $i$, which is the output of an encoder model which takes the
node feature $\bm{x}_{i}$ and the graph structure as input. As demonstrated in
Eq. 2, the InfoNCE loss is composed of two terms: 1) the numerator term on the
positive pair that maximizes the similarity between positive pairs (positive
term); 2) the denominator term on $M-1$ negative pairs and one positive pair
(for simplicity, we call all the $M$ terms in the denominator "negative
terms") that encourages the embeddings of negative pairs to be distinguished
(negative term). Like the study of contrastive learning on vision and
language, recent node-level contrastive learning research mainly focuses on
how to construct/select more informative positive and negative examples.

The most popular method for constructing positive examples on graphs is
through data augmentation. For example, MVGRL (Hassani & Ahmadi, 2020) uses
graph diffusion to generate a fixed, augmented view of the studied graph. GCC
(Qiu et al., 2020) resorts to random walk to sample subgraphs of the anchored
node as positive examples. GRACE (Zhu et al., 2020b) and GCA (Zhu et al.,
2021) employ random graph augmentation–feature masking and edge removing to
generate two views of the input graph before every training step. However,
recent studies have shown that existing graph augmentations might unexpectedly
change or lose the semantic information (Lee et al., 2021; Wang et al., 2022)
of the target node, hurting the learned representation. This motivates us to
investigate the possibility of constructing positive examples without using
random, ambiguous graph augmentations.

Compared with the construction of positive examples, negative examples are
much easier to select. A common adopted and effective practice is to use all
other nodes in the graph as negative examples (Zhu et al., 2020b; 2021; Zhang
et al., 2021). However, the computation of the negative term of InfoNCE has
$\mathcal{O}(|\mathcal{V}|^{2}d)$ time complexity and
$\mathcal{O}(|\mathcal{V}|^{2})$ memory complexity, where $|\mathcal{V}|$ is
the number of nodes and $d$ is the embedding dimension. Note that the real-
world graphs are usually very large, Eq. 2 can hardly be used in a full-graph
training manner. One plausible remedy is to use down-sampling to zoom in on a
fraction of negative samples for once feedforward computation. However,
theoretical analysis demonstrates InfoNCE loss benefits from a large number of
negative examples (Poole et al., 2019), and empirical observations show that
reducing the number of negative examples leads to worse performance on
downstream tasks (Thakoor et al., 2021) (also see our experiments in Sec.
5.3). As a result, it would be promising to devise an efficient and scalable
computation method for the contrastive loss above, without reducing the number
of negative examples.

In the next section, we propose Localized Graph Contrastive Learning with
Kernel Approximation (Local-GCL in short) to mitigate the above issues. Local-
GCL distinguishes itself from previous contrastive methods in the following
two aspects: 1) instead of constructing positive examples for target nodes
using data augmentations or other techniques, we directly treat all the first-
order neighbors of each target node as its positive examples; 2) we introduce
a Gaussian kernelized surrogate loss function, which could be accurately and
efficiently approximated with linear time and memory complexity in place of
the vanilla InfoNCE loss.

##  4 Methodology

###  4.1 Anchoring Node Contrastive Learning on Topology

Contrastive learning is firstly investigated in unsupervised visual
representation learning where the data points are i.i.d. sampled from the data
distribution, and the ground-truth labels are unknown during training. As a
result, we have to employ well-defined augmentations to create two views of
the same image that are likely to share the same ground-truth label. Different
from images or texts where each input data is often assumed i.i.d. generated
from a certain distribution and there is no explicit prior knowledge about the
relationship among different instances, in the graph domain, nodes within the
same graph are highly inter-dependent given the input graph structure. That
is, the graph structure could provide additional information that reflects the
affinity of node pairs. Furthermore, in network (graph) science, it is widely
acknowledged that many real-world graphs (such as social networks (Wu et al.,
2019; McPherson et al., 2001) and citation networks (Ciotti et al., 2016))
conform with the homophily phenomenon that similar nodes may be more likely to
attach than dissimilar ones (Zhu et al., 2003; McPherson et al., 2001). Such a
phenomenon also inspires the core principle followed by the designs of modern
graph neural networks, i.e., connected nodes should have similar embeddings in
the latent space (Zhu et al., 2020a). This motivates us to directly treats all
the first-order neighboring nodes of the target node as positive examples.
Formally, the loss for the positive pairs of node $i$ can be written as

$\mathcal{L}_{\rm
pos}(i)=-\log\sum\limits_{j\in\mathcal{N}(i)}\exp(\bm{z}_{i}^{\top}\bm{z}_{j}/\tau)/|\mathcal{N}(i)|.$
(3)

For the negative term, we can directly use all nodes in the graph as negative
examples. Then the loss for the negative pairs of node $i$ can be formulated
as:

$\mathcal{L}_{\rm
neg}(i)=\log\sum\limits_{k\in\mathcal{V}}\exp(\bm{z}_{i}^{\top}\bm{z}_{k}/\tau).$
(4)

The overall loss function is simply the sum of $\mathcal{L}_{\rm pos}$ and
$\mathcal{L}_{\rm neg}$, then averaged over all nodes:

$\mathcal{L}_{\rm{\sc{Local-
GCL}}}=-\frac{1}{|\mathcal{V}|}\sum\limits_{i=1}^{N}\log\frac{\sum\limits_{j\in\mathcal{N}(i)}\exp(\bm{z}_{i}^{\top}\bm{z}_{j}/\tau)/|\mathcal{N}(i)|}{\sum\limits_{k\in\mathcal{V}}\exp(\bm{z}_{i}^{\top}\bm{z}_{k}/\tau)}.$
(5)

Then we’d like to provide a theoretical analysis of the effectiveness of
constructing positive examples directly with the first-order neighbors. First,
let’s introduce some notations that will be used in the following analysis. We
denote a graph by $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$
is the node st and $\mathcal{E}$ is the edge set. The adjacency matrix and
degree matrix are denoted by $\bm{A}$ and $\bm{D}$, respectively. Let
$\tilde{\bm{A}}=\bm{D}^{-1/2}\bm{A}\bm{D}^{-1/2}$ be the symmetric normalized
adjacency matrix, and $\bm{L}=\bm{I}-\tilde{\bm{A}}$ be the symmetric
normalized graph Laplacian matrix. Denote the eigenvalues of $\bm{L}$ in Zn
ascending order by $\\{\lambda_{i}\\}_{i=1}^{|\mathcal{V}|}$. Finally we
denote the node embedding matrix
$\bm{Z}=\\{\bm{z}_{i}\\}_{i=1}^{|\mathcal{V}|}\in\mathbb{R}^{|\mathcal{V}|\times
d}$ and the one-hot label matrix by
$\bm{Y}=\\{\bm{y}_{i}\\}_{i=1}^{|\mathcal{V}|}\in\mathbb{R}^{|\mathcal{V}|\times
c}$. Without loss of generality we assume $d\leq|\mathcal{V}|$.

We then give a formal definition of graph homophily ratio $\phi$:

######  Definition 1.

(Graph Homophily Ratio) For a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$
with adjacency matrix $\bm{A}$, its homophily ratio $\phi$ is defined as the
probability that two connected nodes share the same label:

$\phi=\frac{\sum_{i,j\in\mathcal{V}}A_{ij}\cdot\mathbbm{1}[{\bm{y}_{i}=\bm{y}_{j}}]}{\sum_{i,j\in\mathcal{V}}A_{ij}}=\frac{\sum_{i,j\in\mathcal{V}}A_{ij}\cdot\mathbbm{1}[{\bm{y}_{i}=\bm{y}_{j}}]}{|\mathcal{E}|}$
(6)

With the conclusions in Balestriero & LeCun (2022) and HaoChen et al. (2021),
which build connections between contrastive loss and spectral method, the
following theorem guarantees the linear classification error of the embeddings
learned from Local-GCL:

######  Theorem 1.

Let $\bm{Z}^{*}$ be the global minimizer of Eq. 5, then for any labeling
function $\hat{y}:\mathbb{V}\rightarrow\mathbb{R}^{c}$ with graph homophily
$\phi$, there exists a linear classifier $\bm{B}^{*}\in\mathbb{R}^{d\times c}$
with norm $\|\bm{B}^{*}\|_{F}\leq 1/(1-\lambda_{d})$ such that

$\mathbb{E}_{i\in\mathcal{V}}\left[\|\hat{\mathop{y}}(i)-{\bm{B}^{*}}^{\top}\bm{z}_{i}^{*}\|_{2}^{2}\right]\leq\frac{1-\phi}{\lambda_{d+1}}$
(7)

See proof in Appendix A.1. Theorem 1 demonstrates that the linear
classification accuracy of the learned embeddings through Local-GCL is bounded
by the homophily ratio $\phi$ and the $d+1$ smallest eigenvalue
$\lambda_{d+1}$. Specifically, the larger the homophily ratio, the smaller the
prediction error. Besides, Eq. 7 indicates that a larger embedding dimension
can lead to better classification accuracy, which is also validated
empirically in Sec. 5.

###  4.2 Fast and Efficient Approximation for the Negative Loss

We next probe into how to reduce the computation complexity of the negative
loss term $\mathcal{L}_{\rm neg}=\sum\limits_{i\in\mathcal{V}}\mathcal{L}_{\rm
neg}(i)$, for which the $|\mathcal{V}|^{2}$ pair-wise similarities can be
efficiently and precisely approximated with efficient computation methods for
kernel functions (Rahimi et al., 2007; Liu et al., 2020).

We notice that the pair-wise similarity (in dot-product format) in Eq. 4 is
essentially a Gaussian kernel function, i.e.,

$\exp(\bm{z}_{i}^{\top}\bm{z}_{j}/\tau)=\exp(\frac{2-\|\bm{z}_{i}-\bm{z}_{j}\|_{2}^{2}}{2\tau})=e*\exp(\frac{-\|\bm{z}_{i}-\bm{z}_{j}\|}{2\tau})=e\cdot\kappa^{G}(\bm{z}_{i},\bm{z}_{k};\sqrt{\tau)},$
(8)

where $\kappa^{G}(\bm{z}_{i},\bm{z}_{k};\sqrt{\tau)}$ is the Gaussian kernel
function with bandwidth $\sqrt{\tau}$. This motivates us to seek for a
projection function ${\psi}(\bm{x})(\mathbb{R}^{d}\rightarrow\mathbb{R}^{2D})$
such that
$\kappa^{G}(\bm{x},\bm{y};\sqrt{\tau})\approx{\psi}(\bm{x})^{\top}{\psi}(\bm{y})$.
Then we are able to use a surrogate negative loss function as a remedy of the
previous one:

$\mathcal{L}_{{neg}}\triangleq\frac{1}{|\mathcal{V}|}\sum_{i\in\mathcal{V}}\left(\log{\sum_{j\in\mathcal{V}}{\psi}(\bm{h}_{i})^{\top}{\psi}(\bm{h}_{j})}\right)=\frac{1}{|\mathcal{V}|}\sum_{i\in\mathcal{V}}\left(\log\left({{\psi}(\bm{h}_{i})^{\top}\sum_{j\in\mathcal{V}}{\psi}(\bm{h}_{j})}\right)\right).$
(9)

Once we obtain all the projected vectors
$\\{\bm{\psi}(\bm{h}_{i})\\}_{i=1}^{|\mathcal{V}|}$, the summation term
$\sum_{j\in\mathcal{V}}{\psi}(\bm{h}_{j})$ in Eq. 9 could be calculated within
$\mathcal{O}(|\mathcal{V}|D)$ in advance (where $D$ is the dimension of
projected vectors). In addition to the $\mathcal{O}(|\mathcal{V}|D)$ cost for
computing the loss, the overall computational cost will be
$\mathcal{O}(|\mathcal{V}|D+|\mathcal{V}|D)=\mathcal{O}(VD)$, which is linear
to the number of nodes. Then we discuss how to formulate the projection
function ${\psi}(\cdot)$ below.

##### Linear-Order Projection

The theory of Random Fourier Features (Rahimi et al., 2007) introduced in Sec.
2.3 demonstrates that a Gaussian kernel function
$\kappa^{G}(\bm{x},\bm{y};\sqrt{\tau})$ could be unbiasedly estimated with
$\psi(\bm{x})^{\top}{\psi}(\bm{y})$, and the projection function
$\psi(\bm{x})$ is defined as follows:

$\psi(\bm{x})=\frac{[\cos(\bm{W}^{\top}\bm{x}),\sin(\bm{W}^{\top}\bm{x})]}{\sqrt{D}}=\frac{\left[\cos(\bm{\omega}_{1}^{\top}\bm{x}),\cdots,\cos(\bm{\omega}_{D}^{\top}\bm{x}),\sin(\bm{\omega}_{1}^{\top}\bm{x}),\cdots,\sin(\bm{\omega}_{D}^{\top}\bm{x})\right]^{\top}}{\sqrt{D}}.$
(10)

where $\bm{W}=[\bm{\omega}_{1}^{\top},\cdots,\bm{\omega}_{D}^{\top}]$, and
each $\bm{\omega}_{i}$ is sampled from the Gaussian distribution
$p(\bm{\omega})=\mathcal{N}(\bm{0},\tau\bm{I})$. $D$ is the number of total
samples. Usually, the larger the sampling number $D$ is, the more accurate the
approximation will be:

######  Theorem 2.

Let $\\{\bm{\omega}_{i}\\}_{i=1}^{D}$ be i.i.d samples from Gaussian
distribution $\mathcal{N}(\bm{0},\tau\bm{I})$, and $\psi(\bm{x})$ is given by
Eq. 10, then with probability at least $1-\varepsilon$, the approximation
error
$\Delta=|{\psi}(\bm{h}_{i})^{\top}{\psi}(\bm{h}_{j})-\kappa^{G}(\bm{h}_{i},\bm{h}_{j})|$
will be bounded by
$\mathcal{O}\left({\frac{1-\exp(-4/\tau)}{\sqrt{2D\varepsilon}}}\right)$.

Theorem 2 suggests that the Gaussian kernel function could be accurately
approximated with Random Fourier Features as long as we sample enough number
of linear transformation vectors $\bm{\omega}$ (i.e., $D$ should be large
enough). Note that the computation of linear projection $\bm{W}\bm{h}_{i}$
($i=1\in\mathcal{V}$) requires additional $\mathcal{O}(|\mathcal{V}|dD)$ time.
A large number of the projection dimension $D$ makes the computation of Eq. 9
still expensive for high-dimensional data.

##### Log-Order Projection

To handle the above issues, we resort to Structured Orthogonal Random Features
(SORF) (Yu et al., 2016), another Random Feature technique that imposes
structural and orthogonality on the linear transformation matrix $\bm{W}$.
Different from the vanilla RFF which directly samples linear transformation
vectors $\bm{\omega}$ form normal distribution to construct the transformation
matrix $\bm{W}_{\rm
rff}=[\bm{\omega}_{1}^{\top},\cdots,\bm{\omega}_{D}^{\top}]\in\mathbb{R}^{d\times
D}$, SORF assumes $D=d$ and constructs a structured orthogonal transformation
matrix through the continued product of a series of structured matrixes
$\bm{W}_{\rm{sorf}}=\frac{\sqrt{d}}{\sigma}\bm{HD}_{1}\bm{HD}_{2}\bm{HD}_{3}$,
where $\bm{D}_{i}\in\mathbb{R}^{d\times d},i=1,2,3$, are diagonal “sign-
flipping” matrices, with each diagonal entry sampled from the Rademacher
distribution, and $\bm{H}\in\mathbb{R}^{d\times d}$ is the normalized Walsh-
Hadamard matrix. By this definition, the projected dimension is restricted to
$d$, but could be extended to any dimension by concatenating multiple
independently generated features or simply using a proportion of them. The
stand-out merit of SORF is that it can be computed in
$\mathcal{O}(|\mathcal{V}|D\log d)$ time using fast Hadamard transformation
(Fino & Algazi, 1976), and hardly requires extra memory cost using in-place
operations (Yu et al., 2016). This further reduces its complexity and endows
our method with desirable scalability to not only larger dataset sizes but
also larger embedding dimensions. If not specified, in the following section,
the term Local-GCL denotes our method equipped with SORF to approximate the
negative loss.

##  5 Experiments

We conduct experiments to evaluate the proposed method by answering the
following questions:

  * •

RQ1: How does Local-GCL perform compared with other self-supervised learning
methods on graphs with different properties?

  * •

RQ2: How do the specific designs of Local-GCL, such as the embedding dimension
and projection dimension, affect its performance?

  * •

RQ3: What’s the empirical memory and time consumption of Local-GCL compared
with prior works? Is Local-GCL able to scale to real-world large-scale graphs
with satisfying performance?

###  5.1 Experimental Setups

##### Datasets.

We evaluate Local-GCL on various datasets with different scales and
properties. Following prior works (Zhu et al., 2020b; Zhang et al., 2021) on
self-supervised node representation learning, we adopt the $7$ common small-
scale benchmarking graphs: Cora, Citeseer, Pubmed, Amazon-Computer, Amazon-
Photo, Coauthor-CS, and Coauthor-Physics. To evaluate the performance and
scalability of Local-GCL on larger graphs, we also adopt Ogbn-Arxiv with about
170k nodes, on which a lot of methods fail to scale due to memory issues.
Furthermore, we adopt three widely used heterophily graphs, Chameleon,
Squirrel, and Actor to evaluate the generalization ability of Local-GCL on
graphs where the graph homophily assumption does not hold. The detailed
introduction and statistics of these datasets are presented in Appendix C.1

##### Baselines.

We consider representative prior self-supervised models for comparison. We
classify previous methods into two types: 1) Augmentation-based, which uses
data augmentations to generate positive or negative pairs. 2) Augmentation-
free, which uses other information rather than any form of data augmentation
to create self-supervised signals. For augmentation-based baselines, we
consider DGI (Velickovic et al., 2019), MVGRL (Hassani & Ahmadi, 2020), GRACE
(Zhu et al., 2020b), GCA Zhu et al. (2021), BGRL (Thakoor et al., 2021) and
CCA-SSG (Zhang et al., 2021). For augmentation-free baselines, we consider GMI
(Peng et al., 2020), SUGRL (Mo et al., 2022), AFGRL (Lee et al., 2021), AF-GCL
(Wang et al., 2022).

##### Evaluation Protocols.

We follow the linear evaluation scheme in previous works (Velickovic et al.,
2019; Hassani & Ahmadi, 2020; Zhu et al., 2021; Zhang et al., 2021): For each
dataset, i) we first train the model on all the nodes in a graph without
supervision by optimizing the objective in Eq. 5; ii) after the training ends,
we freeze the parameters of the encoder and obtain all the nodes’ embeddings,
which are subsequently fed into a linear classifier (i.e., a logistic
regression model) to generate a predicted label for each node. In the second
stage, only nodes in the training set are used for training the classifier,
and we report the classification accuracy on testing nodes.

##### Implementation Details.

The model is implemented with PyTorch and DGL (Wang et al., 2019). All
experiments are conducted on an NVIDIA V100 GPU with 16 GB memory unless
specified. We adopt structure-
net111https://github.com/HazyResearch/structured-nets to do fast Walsh-
Hadamard transformation, which enables much faster forward and backward
computation with CUDA accelerations. We use the Adam optimizer (Kingma & Ba,
2015) for both self-supervised pretraining training and linear evaluation
using logistic regression. Following previous works (Zhu et al., 2021; Zhang
et al., 2021; Thakoor et al., 2021; Wang et al., 2022), we the random 1:1:8
split for Amazon-Computer, Amazon-Photo, Coauthor-CS and Amazon-Computer, and
use the public recommended split for the remaining datasets. For each
experiment, we report the average test accuracy with the standard deviation
over 20 random initialization. If not specified, we use a two-layer GCN model
as the encoder to generate node embeddings. More detailed hyperparameter
settings for each dataset can be found in Appendix C.2

###  5.2 Numerical Results

##### Results on common graphs.

We first report the results of node classification tasks on small-scale
citation networks and social networks in Table 1. We see that although not
relying on data augmentations or other complicated operations to create self-
supervised signal, Local-GCL performs competitively with our self-supervised
baselines, achieving state-of-the-art performance in 6 out of 7 datasets. It
is worth noting that the competitive InfoNCE-loss based contrastive methods
GRACE and GCA suffer from OOM on Coauthor-Physics datasets due to the
$\mathcal{O}(|\mathcal{V}|^{2}d)$ space complexity, while Local-GCL can avoid
such an issue thanks to the linear approximation of the negative loss.

Table 1: Comparison of self-supervised methods on benchmarking graphs. We
group each method according to whether it relies on graph augmentation.

| Methods | Cora | Citeseer | Pubmed | Computer | Photo | CS | Physics
---|---|---|---|---|---|---|---|---
Aug-based | DGI | 82.3$\pm$0.6 | 71.8$\pm$0.7 | 76.8$\pm$0.6 | 83.95$\pm$0.47 | 91.61$\pm$0.22 | 92.15$\pm$0.63 | 94.51$\pm$0.52
MVGRL | 83.5$\pm$0.4 | 73.3$\pm$0.5 | 80.1$\pm$0.7 | 87.52$\pm$0.11 | 91.74$\pm$0.07 | 92.11$\pm$0.12 | 95.33$\pm$0.03
GRACE | 81.9$\pm$0.4 | 71.2$\pm$0.5 | 80.6$\pm$0.4 | 86.25$\pm$0.25 | 92.15$\pm$0.24 | 92.93$\pm$0.01 | OOM∗
GCA | 82.3$\pm$0.4 | 72.1$\pm$0.4 | 80.7$\pm$0.5 | 87.85$\pm$0.31 | 92.49$\pm$0.09 | 93.10$\pm$0.01 | OOM
BGRL | 82.7$\pm$0.6 | 71.1$\pm$0.8 | 79.6$\pm$0.5 | 89.69$\pm$0.37 | 93.07$\pm$0.28 | 92.59$\pm$0.17 | 95.48$\pm$0.08
CCA-SSG | 84.2$\pm$0.4 | 73.1$\pm$0.3 | 81.6$\pm$0.4 | 88.74$\pm$0.28 | 93.14$\pm$0.14 | 93.31$\pm$0.22 | 95.38$\pm$0.06
Aug-free | GMI | 82.4$\pm$0.6 | 71.7$\pm$0.2 | 79.3$\pm$1.0 | 84.22$\pm$0.52 | 90.73$\pm$0.24 | OOM | OOM
SUGRL | 83.4$\pm$0.5 | 73.0$\pm$0.4 | 81.9$\pm$0.3 | 88.93$\pm$0.21 | 93.07$\pm$0.15 | 92.83$\pm$0.23 | 95.38$\pm$0.11
AFGRL | 81.3$\pm$0.2 | 68.7$\pm$0.3 | 80.6$\pm$0.4 | 89.88$\pm$0.33 | 93.22$\pm$0.28 | 93.27$\pm$0.17 | OOM
AF-GCL | 83.2$\pm$0.2 | 72.0$\pm$0.4 | 79.1$\pm$0.8 | 89.68$\pm$0.19 | 92.49$\pm$0.31 | 91.92$\pm$0.10 | 95.12$\pm$0.15
Local-GCL | 84.5$\pm$0.4 | 73.6$\pm$0.4 | 82.1$\pm$0.5 | 88.81$\pm$0.37 | 93.25$\pm$0.40 | 94.90$\pm$0.19 | 96.33$\pm$0.13

  * $*$

OOM indicates out-of-memory on an NVIDIA-V100 GPU of 16G memory.

Table 2: Performance on Ogbn-Arxiv dataset. As recommended, we report both the
validation accuracy and test accuracy.

Methods | Validation | Test
---|---|---
DGI | 71.21$\pm$0.23 | 70.32$\pm$0.25
GMI | OOM | OOM
MVGRL | OOM | OOM
GRACE | OOM | OOM
GCA | OOM | OOM
BGRL | 72.71$\pm$0.22 | 71.54$\pm$0.17
CCA-SSG | 72.31$\pm$0.18 | 71.21$\pm$0.20
AFGRL | OOM | OOM
Local-GCL | 72.29$\pm$0.25 | 71.34$\pm$0.25

Figure 1: Test accuracy and training time comparison of Local-GCL, BGRL, CCA-
SSG and GRACE with subsampling.

##### Results on Ogbn-Arxiv.

Then, we evaluate the effectiveness and scalability of Local-GCL on large-
scale graphs taking Ogbn-Arxiv as an example. Following the practice in
Thakoor et al. (2021), we expand the encoder to a 3-layer GCN model. We report
the validation and test accuracy of baseline models and ours in Table 2. As
demonstrated, many baseline methods cannot run in a full graph manner (on a
GPU with 16GB memory). Compared with other scalable methods, Local-GCL can
give a competitive performance on Ogbn-Arxiv.

##### More empirical results and ablation studies.

We conduct further experiments and present the results in Appendix C.3 due to
the space limit: 1) the performance on heterophilic graphs (Appendix C.3.1);
2) the effect of reweighting the importance of positive examples (Appendix
C.3.2); 3) applying the positive example construction strategy to non-
contrastive methods (Appendix C.3.3); 4) combining with hard-negative sampling
methods (Appendix C.3.4).

###  5.3 Scalability Comparison

To evaluate the scalability of Local-GCL on real-world datasets, we compare
the total training time and accuracy with state-of-the-art scalable methods
BGRL (Thakoor et al., 2021) and CCA-SSG (Zhang et al., 2021) on Arxiv dataset.
To further justify the necessity of adopting a large number of negative
examples, we additionally adopt GRACE (Zhu et al., 2020b), a powerful non-
scalable contrastive model. We use sub-sampling strategy to randomly sample a
fixed number of negative examples every epoch so that the GRACE model could be
fit into a GPU with 16G memory. In Fig. 1 we plot the model’s performance and
the corresponding training time of different methods. We can see that compared
with scalable methods CCA-SSG and BGRL, Local-GCL achieves comparable
performance but with the least training time. We can also observe that
although reducing the number of negative examples ($k$ in Fig. 1) can enable
the model to be trained much faster, the performance drop is significant,
which cannot make up for the efficiency benefit. Furthermore, if we continue
to use an even larger number of negative examples, GRACE will soon run out of
memory. This result demonstrates that Local-GCL can better balance the
training efficiency and model performance.

###  5.4 Sensitivity to embedding/projection dimensions

Figure 2: Sensitivity analysis of embedding dimension $d$ and projection
dimension $D$.

As demonstrated in Theorem 1 and Sec. 4.2, the embedding dimension $d$ and
projection dimension $D$ should be two critical hyperparameters affecting the
model’s performance. In this section, we test Local-GCL’ sensitivities with
respect to them in Fig. 2. The observations are two-fold: 1) Similar to other
self-supervised learning models (Hassani & Ahmadi, 2020; Zhu et al., 2021;
Zhang et al., 2021; Lee et al., 2021), Local-GCL that benefit from a large
embedding dimension (e.g., $512$), Local-GCL’s performance also grows as we
increase the embedding dimension $d$. However, the optimal embedding dimension
for Local-GCL is even larger, e.g., $2048$ on Cora and Citeseer (note that
other methods do not benefit from such a large embedding dimension). This
could be justified by our analysis in Theorem 1, which demonstrates that with
a larger embedding dimension, the bound of the prediction error will become
lower (because the target eigenvalue $\lambda_{d+1}$ becomes larger). 2)
Increasing the projection dimension can lead to better but minimal
improvement. This indicates that in practice, Local-GCL can perform quite well
without using a huge projection $D$.

##  6 Conclusions

In this paper, we have presented Local-GCL, a simple, light-weighted yet
effective contrastive model for self-supervised node representation learning.
Local-GCL incorporates two orthogonal techniques to address two key issues in
contrastive learning on graph data: reliance on data augmentation and
scalability, respectively. The former involves a new definition of positive
examples such that the model is free from data augmentation whose design could
be more difficult than its counterparts in vision and text, and calls for
careful customization for different graph data and tasks. The latter devises
an approximated contrastive loss, which reduces the quadratic complexity of
traditional contrastive learning to linearity in terms of the graph size.
Extensive experimental results on seven public graph benchmarks show its
efficiency and efficacy.

## References

  * Avron et al. (2017) Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh.  Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees.  In _ICML_ , pp. 253–262, 2017.
  * Balestriero & LeCun (2022) Randall Balestriero and Yann LeCun.  Contrastive and non-contrastive self-supervised learning recover global and local spectral embedding methods.  _arXiv preprint arXiv:2205.11508_ , 2022.
  * Banville et al. (2021) Hubert Banville, Omar Chehab, Aapo Hyvärinen, Denis-Alexander Engemann, and Alexandre Gramfort.  Uncovering the structure of clinical eeg signals with self-supervised learning.  _Journal of Neural Engineering_ , 18(4):046020, 2021.
  * Bo et al. (2021) Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen.  Beyond low-frequency information in graph convolutional networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pp. 3950–3957, 2021.
  * Chen et al. (2020) Ting Chen, Simon Kornblith ands Mohammad Norouzi, and Geoffrey E. Hinton.  A simple framework for contrastive learning of visual representations.  In _ICML_ , pp. 1597–1607, 2020.
  * Choromanski et al. (2020) Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al.  Rethinking attention with performers.  In _ICLR_ , 2020.
  * Ciotti et al. (2016) Valerio Ciotti, Moreno Bonaventura, Vincenzo Nicosia, Pietro Panzarasa, and Vito Latora.  Homophily and missing links in citation networks.  _EPJ Data Sci._ , 5(1):7, 2016.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  In _NAACL_ , pp. 4171–4186, 2019.
  * Dwibedi et al. (2021) Debidatta Dwibedi, Yusuf Aytar, Jonathan Tompson, Pierre Sermanet, and Andrew Zisserman.  With a little help from my friends: Nearest-neighbor contrastive learning of visual representations.  _arXiv preprint arXiv:2104.14548_ , 2021.
  * Fino & Algazi (1976) Bernard J. Fino and V. Ralph Algazi.  Unified matrix treatment of the fast walsh-hadamard transform.  _IEEE Transactions on Computers_ , 25(11):1142–1146, 1976.
  * Gao et al. (2021) Tianyu Gao, Xingcheng Yao, and Danqi Chen.  Simcse: Simple contrastive learning of sentence embeddings.  _arXiv preprint arXiv:2104.08821_ , 2021.
  * Grill et al. (2020) Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Ávila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko.  Bootstrap your own latent - A new approach to self-supervised learning.  In _NeurIPS_ , 2020.
  * HaoChen et al. (2021) Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma.  Provable guarantees for self-supervised deep learning with spectral contrastive loss.  _NeurIPS_ , 34:5000–5011, 2021.
  * Hassani & Ahmadi (2020) Kaveh Hassani and Amir Hosein Khas Ahmadi.  Contrastive multi-view representation learning on graphs.  In _ICML_ , 2020.
  * He et al. (2020) Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick.  Momentum contrast for unsupervised visual representation learning.  In _CVPR_ , pp. 9726–9735, 2020.
  * Hjelm et al. (2019) R. Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Philip Bachman, Adam Trischler, and Yoshua Bengio.  Learning deep representations by mutual information estimation and maximization.  In _ICLR_ , 2019.
  * Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec.  Open graph benchmark: Datasets for machine learning on graphs.  In _NeurIPS_ , 2020.
  * Kalantidis et al. (2020) Yannis Kalantidis, Mert Bülent Sariyildiz, Noé Pion, Philippe Weinzaepfel, and Diane Larlus.  Hard negative mixing for contrastive learning.  In _NeurIPS_ , 2020.
  * Kingma & Ba (2015) Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _ICLR_ , 2015.
  * Kipf & Welling (2016) Thomas N. Kipf and Max Welling.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ , 2016.
  * Koohpayegani et al. (2021) Soroush Abbasi Koohpayegani, Ajinkya Tejankar, and Hamed Pirsiavash.  Mean shift for self-supervised learning.  In _ICCV_ , pp. 10326–10335, 2021.
  * Le et al. (2013) Quoc Le, Tamás Sarlós, Alex Smola, et al.  Fastfood-approximating kernel expansions in loglinear time.  In _ICML_ , pp. 244–252, 2013.
  * Lee et al. (2021) Namkyeong Lee, Junseok Lee, and Chanyoung Park.  Augmentation-free self-supervised learning on graphs.  _arXiv preprint arXiv:2112.02472_ , 2021.
  * Li et al. (2021) Yazhe Li, Roman Pogodin, Danica J. Sutherland, and Arthur Gretton.  Self-supervised learning with kernel dependence maximization.  _arXiv preprint arXiv:2106.08320_ , 2021.
  * Liu et al. (2020) Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens.  Random features for kernel approximation: A survey on algorithms, theory, and beyond.  _arXiv preprint arXiv:2004.11154_ , 2020.
  * Liu et al. (2022) Nian Liu, Xiao Wang, Deyu Bo, Chuan Shi, and Jian Pei.  Revisiting graph contrastive learning from the perspective of graph spectrum.  _arXiv preprint arXiv:2210.02330_ , 2022.
  * Ma et al. (2022) Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang.  Is homophily a necessity for graph neural networks?  In _ICLR_ , 2022.
  * McAuley et al. (2015) Julian J. McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel.  Image-based recommendations on styles and substitutes.  In _SIGIR_ , pp. 43–52, 2015.
  * McPherson et al. (2001) Miller McPherson, Lynn Smith-Lovin, and James M Cook.  Birds of a feather: Homophily in social networks.  _Annual review of sociology_ , 27(1):415–444, 2001.
  * Mo et al. (2022) Yujie Mo, Liang Peng, Jie Xu, Xiaoshuang Shi, and Xiaofeng Zhu.  Simple unsupervised graph representation learning.  In _AAAI_ , pp. 7797–7805, 2022.
  * Namata et al. (2012) Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU.  Query-driven active surveying for collective classification.  In _10th International Workshop on Mining and Learning with Graphs_ , volume 8, 2012.
  * Pei et al. (2020) Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang.  Geom-gcn: Geometric graph convolutional networks.  In _ICLR_ , 2020.
  * Peng et al. (2021) Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A Smith, and Lingpeng Kong.  Random feature attention.  In _ICLR_ , 2021.
  * Peng et al. (2020) Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang.  Graph representation learning via graphical mutual information maximization.  In _WWW_ , pp. 259–270, 2020.
  * Poole et al. (2019) Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker.  On variational bounds of mutual information.  In _ICML_ , pp. 5171–5180, 2019.
  * Qiu et al. (2020) Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang.  GCC: graph contrastive coding for graph neural network pre-training.  In _KDD_ , pp. 1150–1160, 2020.
  * Rahimi et al. (2007) Ali Rahimi, Benjamin Recht, et al.  Random features for large-scale kernel machines.  In _NIPS_ , pp. 1177–1884, 2007.
  * Robinson et al. (2021) Joshua David Robinson, Ching-Yao Chuang, Suvrit Sra, and Stefanie Jegelka.  Contrastive learning with hard negative samples.  In _ICLR_ , 2021.
  * Rozemberczki et al. (2021) Benedek Rozemberczki, Carl Allen, and Rik Sarkar.  Multi-Scale Attributed Node Embedding.  _Journal of Complex Networks_ , 9(2), 2021.
  * Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  _AI magazine_ , 29(3):93–93, 2008.
  * Sinha et al. (2015) Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Paul Hsu, and Kuansan Wang.  An overview of microsoft academic service (MAS) and applications.  In _WWW_ , pp. 243–246, 2015.
  * Thakoor et al. (2021) Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Velickovic, and Michal Valko.  Bootstrapped representation learning on graphs.  _arXiv preprint arXiv:2102.06514_ , 2021.
  * Tian et al. (2020) Yonglong Tian, Dilip Krishnan, and Phillip Isola.  Contrastive multiview coding.  In _ECCV_ , pp. 776–794, 2020.
  * Tsai et al. (2021) Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency.  Self-supervised learning from a multi-view perspective.  In _ICLR_ , 2021.
  * van den Oord et al. (2018) Aäron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_ , 2018.
  * Velickovic et al. (2019) Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm.  Deep graph infomax.  In _ICLR_ , 2019.
  * Wang et al. (2022) Haonan Wang, Jieyu Zhang, Qi Zhu, and Wei Huang.  Augmentation-free graph contrastive learning with performance guarantee.  _arXiv Preprint arXiv:2204.04874_ , abs/2204.04874, 2022.
  * Wang et al. (2019) Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, Ziyue Huang, Qipeng Guo, Hao Zhang, Haibin Lin, Junbo Zhao, Jinyang Li, Alexander J. Smola, and Zheng Zhang.  Deep graph library: Towards efficient and scalable deep learning on graphs.  _arXiv_ , 1909.01315, 2019.
  * Wu et al. (2019) Qitian Wu, Hengrui Zhang, Xiaofeng Gao, Peng He, Paul Weng, Han Gao, and Guihai Chen.  Dual graph attention networks for deep latent representation of multifaceted social effects in recommender systems.  In _WWW_ , pp. 2091–2102. ACM, 2019.
  * Xia et al. (2022) Jun Xia, Lirong Wu, Ge Wang, Jintao Chen, and Stan Z. Li.  Progcl: Rethinking hard negative mining in graph contrastive learning.  In _ICML_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 24332–24346. PMLR, 2022.
  * You et al. (2020) Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen.  Graph contrastive learning with augmentations.  In _NeurIPS_ , 2020.
  * Yu et al. (2016) Felix Xinnan X Yu, Ananda Theertha Suresh, Krzysztof M Choromanski, Daniel N Holtmann-Rice, and Sanjiv Kumar.  Orthogonal random features.  In _NIPS_ , pp. 1975–1983, 2016.
  * Zhang et al. (2021) Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu.  From canonical correlation analysis to self-supervised graph neural networks.  In _NeurIPS_ , 2021.
  * Zhang et al. (2018) Qinyi Zhang, Sarah Filippi, Arthur Gretton, and Dino Sejdinovic.  Large-scale kernel methods for independence testing.  _Statistics and Computing_ , 28(1):113–130, 2018\.
  * Zhang et al. (2022) Shaofeng Zhang, Meng Liu, Junchi Yan, Hengrui Zhang, Lingxiao Huang, Xiaokang Yang, and Pinyan Lu.  M-mix: Generating hard negatives via multi-sample mixing for contrastive learning.  In _KDD_ , pp. 2461–2470. ACM, 2022.
  * Zhu et al. (2020a) Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra.  Beyond homophily in graph neural networks: Current limitations and effective designs.  In _NeurIPS_ , 2020a.
  * Zhu et al. (2003) Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty.  Semi-supervised learning using gaussian fields and harmonic functions.  In _ICML_ , pp. 912–919, 2003.
  * Zhu et al. (2020b) Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Deep graph contrastive representation learning.  _arXiv preprint arXiv:2006.04131_ , 2020b.
  * Zhu et al. (2021) Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Graph contrastive learning with adaptive augmentation.  In _WWW_ , 2021.

##  Appendix A Proofs

###  A.1 Proof for Theorem 1

###### Proof.

To prove Theorem 1, we first introduce a lemma that shows the optimal
representations learned from InfoNCE-like loss function (e.g., Eq. 5) derived
from Balestriero & LeCun (2022):

######  Lemma 1.

Denote the eigendecomposition of the normalized graph adjacency matrix by
$\tilde{\bm{A}}=\bm{U\Lambda}\bm{U}^{\top}$, where $\bm{U}$ and $\bm{\Lambda}$
are the eigenvectors and eigenvalues of $\tilde{\bm{}}$ respectively. Assume
node embeddings are free vectors, then a global minimizer of the loss function
in Eq. 5 is given by:

$\bm{Z}^{*}=(\bm{U}\bm{\Lambda}^{1/2})_{:,1:d},$ (11)

up to permutations of the eigenvector associated with the same eigenvalue.
$1:d$ in Eq. 11 indicates the largest $d$ eigenvalues and the associated
eigenvectors.

Besides, HaoChen et al. (2021) has presented the following theoretical
guarantee for the model learned with the matrix factorization loss:

######  Lemma 2.

For a graph $\mathcal{G}$ with symmetric normalized graph adjacency matrix and
Laplacian matrix $\tilde{\bm{A}}$ and $\tilde{\bm{L}}$, let
$f^{*}_{mf}\in\mathop{\arg\min}_{f_{mf}:\mathcal{V}\rightarrow\mathbb{R}^{d}}$
be a minimizer of the matrix factorization loss: $\mathcal{L}_{\rm
mf}(\bm{F})=\|(\bm{I}-\tilde{\bm{L}}-\bm{F}\bm{F}^{\top})\|_{F}^{2}$, where
$\bm{F}$ is the embedding matrix. Then, for any labeling function
$\hat{y}:\mathcal{V}\rightarrow[r]$, there exists a linear classifier
$\bm{B}^{*}\in\mathbb{R}^{d\times c}$ with norm $\|B^{*}\|_{F}\leq
1/(1-\lambda_{d+1})$ such that:

$\mathbb{E}_{v\in\mathcal{V}}\left[\|\mathop{y}\limits^{\rightarrow}(v)-\bm{B}^{*}f^{*}(v)\|_{2}^{2}\right]\leq\frac{1-\phi}{\lambda_{d+1}},$
(12)

where $\phi$ is the graph homophily ratio defined in Eq. 6.

Then we just need to connect $\bm{Z}^{*}$ in Eq. 11 with the optimal solution
of the rthe matrix factorization loss $\mathcal{L}_{\rm
mf}(\bm{F})=\|\bm{I}-\tilde{\bm{L}}-\bm{F}\bm{F}^{\top}\|_{F}^{2}=\|\tilde{\bm{A}}-\bm{F}\bm{F}^{\top}\|$.
According to Eckart–Young–Mirsky theorem, the optimal $\bm{F}\bm{F}^{\top}$ is
$\bm{F}\bm{F}^{\top}=\bm{U}_{:,1:d}\Lambda_{:,1:d}\bm{U}_{:,1:d}^{\top}$ As a
result, $\bm{F}^{*}=\bm{Z}^{*}=(\bm{U}\Lambda^{1/2})_{:,1:d}$ is exactly the
global minimizer of $\mathcal{L}_{mf}(\bm{F})$. Then the proof is complete.

∎

###  A.2 Proof for Theorem 2

###### Proof.

To prove Theorem 2, we first introduce the following lemma given by Lemma 1 in
(Yu et al., 2016).

######  Lemma 3.

The Random Fourier Estimation $K_{RFF}(\bm{x},\bm{y})$ is an unbiased
estimator of the Gaussian kernel, i.e.,
$\mathbb{E}_{\bm{\omega}}(\psi(\bm{x})^{\top}\psi(\bm{y}))=e^{{-\|\bm{x}-\bm{y}\|^{2}_{2}}/{2{\tau}}}$.
Let $z=\|\bm{x}-\bm{y}\|_{2}/\sqrt{\tau}$, then the variance of
$K_{RFF}(\bm{x},\bm{y})$ is
$\mathbb{V}_{\bm{\omega}}(\psi(\bm{x})^{\top}\psi(\bm{y}))=(1-e^{-z^{2}})^{2}/{2D}$.

The lemma shows that the Random Fourier Features can achieve an unbiased
approximation for the Gaussian kernel with a quantified variance.

Back to our main theorem, we can derive the following probability using the
Chebyshev’s inequality:

$\mathbb{P}(\Delta<{\frac{1-\exp(-4/\tau)}{\sqrt{2D\varepsilon}}})\geq
1-\frac{\mathbb{V}_{\bm{\omega}}(\psi(\bm{h}_{i})^{\top}\psi(\bm{\bm{h}_{j}}))*2D\varepsilon}{{(1-\exp(-4/\tau))^{2}}}$
(13)

where
$\Delta=|{\psi}(\bm{h}_{i})^{\top}{\psi}(\bm{h}_{j})-\kappa^{G}(\bm{h}_{i},\bm{h}_{j})|$
denotes the deviation of the kernel approximation. Using the result in Lemma
3, we can further obtain that the RHS of Eq. 13 is

$1-\frac{(1-e^{-z^{2}})^{2}*\varepsilon}{(1-\exp(-4/\tau))^{2}}$ (14)

As both $\bm{h}_{i}$ and $\bm{h}_{j}$ are $\ell_{2}$-normalized, we have
$z^{2}=\|\bm{h}_{i}-\bm{h}_{j}\|^{2}_{2}/{\tau}\leq 4/\tau$, so we can
conclude the stated result:

$\mathbb{P}(\Delta<{\frac{1-\exp(-4/\tau)}{\sqrt{2D\varepsilon}}})\geq
1-\frac{(1-e^{-z^{2}})^{2}*\varepsilon}{(1-\exp(-4/\tau))^{2}}\geq
1-\varepsilon$ (15)

∎

##  Appendix B Advantages of Local-GCL over Prior Methods

We provide a systematic comparison for the proposed Local-GCL with previous
typical methods self-supervised node representation learning, including DGI
(Velickovic et al., 2019), MVGRL (Hassani & Ahmadi, 2020), GRACE (Zhu et al.,
2020b), GCA (Zhu et al., 2021), BGRL (Thakoor et al., 2021), CCA-SSG (Zhang et
al., 2021) and AFGRL (Lee et al., 2021).

###  B.1 Totally augmentation-free with single branch

Most of previous self-supervised learning models (Velickovic et al., 2019;
Hassani & Ahmadi, 2020; Zhu et al., 2020b; 2021; Thakoor et al., 2021; Zhang
et al., 2021) require carefully-defined graph augmentations to obtain positive
pairs. However, as noted above, it is hard and costly to design task and
dataset-specific graph augmentations. Our method Local-GCL naturally avoids
data augmentation by using the first-order neighborhood information of each
node. Moreover, different from all previous methods that have two branches of
models (double amounts of inputs, hidden variables, outputs, etc.), our
approach only requires a single branch, which makes our method light-weighted.

###  B.2 Projector/Predictor/Discriminator-free

Most of the previous methods require additional components besides the basic
encoder for decent empirical results (Zhu et al., 2020b; 2021), to break
symmetries to avoid trivial solutions (Thakoor et al., 2021; Lee et al., 2021)
or to estimate some score functions in their final objectives (Velickovic et
al., 2019; Hassani & Ahmadi, 2020). Compared with them, Local-GCL is much
simpler, in both conceptual and practical senses, without using any
parameterized model but the basic encoder.

###  B.3 Theoretically grounded with linear complexity

Empirically, InfoNCE-based contrastive methods (Zhu et al., 2020b; 2021) often
show better performance than DIM-based methods (Velickovic et al., 2019;
Hassani & Ahmadi, 2020) yet suffer from the scalability issue. Recent non-
contrastive methods (Thakoor et al., 2021; Lee et al., 2021) could maintain
decent performance with linear model complexity through asymmetric structures,
while the rationale behind their success still remains unclear (Zhang et al.,
2021). As a contrastive model, Local-GCL is theoretically grounded (through
maximizing the mutual information between the target node’s embedding and its
neighbor’s embeddings), and its kernelized approximation of negative loss
enables it to scale to large graphs with linear time and memory complexity
with respect to the graph size.

##  Appendix C Experiment Details and Additional Empirical Results

###  C.1 Datasets

The statistics of the used datasets are presented in Table 3, and a brief
introduction and settings are as follows:

Table 3: Statistics of benchmark datasets. Dataset | #Nodes | #Edges | #Classes | #Features | $\phi$
---|---|---|---|---|---
Cora | 2,708 | 10,556 | 7 | 1,433 | 0.810
Citeseer | 3,327 | 9,228 | 6 | 3,703 | 0.736
Pubmed | 19,717 | 88,651 | 3 | 500 | 0.802
Coauthor-CS | 18,333 | 327,576 | 15 | 6,805 | 0.808
Coauthor-Physics | 34,493 | 991,848 | 5 | 8,451 | 0.931
Amazon-Computer | 13,752 | 574,418 | 10 | 767 | 0.777
Amazon-Photo | 7,650 | 287,326 | 8 | 745 | 0.827
Ogbn-Arxiv | 169,343 | 2,332,386 | 40 | 128 | 0.655
Chameleon | 2,277 | 36,101 | 5 | 2,325 | 0.235
Squirrel | 5,201 | 217,073 | 5 | 2,089 | 0.224
Actor | 7,600 | 33,544 | 5 | 931 | 0.219

Cora, Citeseer, Pubmed are three widely used node classification benchmarks
(Sen et al., 2008; Namata et al., 2012). Each dataset consists of one citation
network, where nodes represent papers and edges represent a citation
relationship from one node to another. We use the public split, where each
class has fixed $20$ nodes for training, another fixed $500$ nodes and $1000$
nodes for validation/test, respectively for evaluation.

Coauthor-CS, Coauthor-Physics are co-authorship graphs based on the Microsoft
Academic Graph from the KDD Cup 2016 challenge (Sinha et al., 2015). Nodes are
authors that are connected by an edge if they co-authored a paper; node
features represent paper keywords for each author’s papers, and class labels
indicate the most active fields of study for each author. As there is no
public split for these datasets, we randomly split the nodes into
train/validation/test (10%/10%/80%) sets.

Amazon-Computer, Amazon-Photo are segments of the Amazon co-purchase graph
(McAuley et al., 2015), where nodes represent goods, edges indicate that two
goods are frequently bought together; node features are bag-of-words encoded
product reviews, and class labels are given by the product category. We also
use a 10%/10%/80% split for these two datasets.

For simplicity, we use the processed version of these datasets provided by
Deep Graph Library (Wang et al.,
2019)222https://docs.dgl.ai/en/0.6.x/api/python/dgl.data.html. One can easily
acquire these datasets using the api provided by DGL.

Ogbn-Arxiv is a directed graph, representing the citation network between all
Computer Science (CS) arXiv papers (Hu et al., 2020). Each node is an arXiv
paper and each directed edge indicates that one paper cites another one. Each
paper comes with a 128-dimensional feature vector obtained by averaging the
embeddings of words in its title and abstract. The embeddings of individual
words are computed by running the skip-gram over the MAG corpus. All papers
are also associated with the year that the corresponding paper was published.
We use the official split in our experiments.

Chameleon and Squirrel (Rozemberczki et al., 2021) are Wikipedia networks
introduced. Nodes represent web pages, and edges represent hyperlinks between
them. Node features represent several informative nouns in the Wikipedia
pages. The task is to predict the average daily traffic of the web page.

Actor is the actor-only induced subgraph of the film-director-actor-writer
network used in Pei et al. (2020). Each node corresponds to an actor, and the
edge between two nodes denotes co-occurrence on the same Wikipedia page. Node
features correspond to some keywords in the Wikipedia pages. The task is to
classify the nodes into five categories in term of words of actor’s Wikipedia.

For Chameleon, Squirrel and Actor, we use the raw data provided by the Geom-
GCN (Pei et al., 2020) paper333https://github.com/graphdml-uiuc-jlu/geom-gcn,
and we use the 10-fold split provided.

Table 4: Details of hyper-parameters of the experimental results in Table 1 Dataset | Local-GCL
---|---
Encoder | # Steps | # layers | lr | wd | $d$ | $D$ | $\tau$
Cora | GCN | 50 | 2 | 5e-4 | 1e-6 | 2048 | 8192 | 0.5
Citeseer | GCN | 20 | 1 | 1e-3 | 1e-4 | 2048 | 4096 | 0.5
Pubmed | GCN | 50 | 2 | 5e-4 | 0 | 1024 | 8192 | 0.5
Amazon-Computer | GCN | 50 | 2 | 5e-4 | 0 | 1024 | 8192 | 0.8
Amazon-Photo | GCN | 50 | 2 | 5e-4 | 1e-6 | 2048 | 8192 | 0.5
Coauthor-CS | MLP | 50 | 2 | 5e-4 | 1e-4 | 1024 | 4096 | 0.5
Coauthor-Physics | MLP | 50 | 2 | 5e-4 | 0 | 1024 | 4096 | 0.7

###  C.2 Hyper-parameters

We provide detailed hyper-parameters on the seven benchmarks in Table 4. All
hyper-parameters are selected through a small grid search, and the search
space is provided as follows:

  * •

Training steps: {20, 50}

  * •

Number of layers: {1, 2}

  * •

Embedding dimension $d$: {512, 1024, 2048}

  * •

Projection dimension $D$: {2048, 4096, 8192}

  * •

Temperature $\tau$: {0.5, 0.6, 0.7, 0.8, 0.9, 1.0}

  * •

Learning rate: {5e-4, 1e-3, 5e-3}

  * •

Weight decay: {0, 1e-6, 1e-4}

###  C.3 Extensive empirical studies

We further extend Local-GCL with other designs of positive example
construction, negative example selection, and self-supervised objective
functions to evaluate the effectiveness of each single component of the
proposed method.

####  C.3.1 Results on heterophilic graphs

We also investigate the performance on non-homophily graphs, a much more
challenging task as directly using first-order neighbors as positive examples
without discriminating might be harmful to non-homophily graphs. The results
on the three heterophily graphs are presented in Table 5.

Table 5: Performance on Heterophily graphs. Results of baseline methods are
taken from Wang et al. (2022)

Methods | Chameleon | Squirrel | Actor
---|---|---|---
DGI | 60.27$\pm$0.70 | 42.22$\pm$0.63 | 28.30$\pm$0.76
GMI | 52.81$\pm$0.63 | 35.25$\pm$1.21 | 27.28$\pm$0.87
MVGRL | 53.81$\pm$1.09 | 38.75$\pm$1.32 | 32.09$\pm$1.07
GRACE | 61.24$\pm$0.53 | 41.09$\pm$0.85 | 28.27$\pm$0.43
GCA | 60.94$\pm$0.81 | 41.53$\pm$1.09 | 28.89$\pm$0.50
BGRL | 64.86$\pm$0.63 | 46.24$\pm$0.70 | 28.80$\pm$0.54
AF-GCL | 65.28$\pm$0.53 | 52.10$\pm$0.67 | 28.94$\pm$0.69
Local-GCL | 68.74$\pm$0.49 | 52.94$\pm$0.88 | 33.91$\pm$0.57

Although a little bit counter-intuitive, our method can achieve quite good
results on heterophilic graphs. This is probably due to the following reasons:
1) Even though connected nodes may not share the same label, as long as the
neighborhood distributions for different classes are different, Local-GCL is
able to recognize the neighborhood patterns of different classes and make the
node embeddings for different classes distinguishable. This is also justified
in one recent work showing that a GCN model can still perform well on
heterophily graphs (Ma et al., 2022). 2) Data augmentation-based methods tend
to keep the low-frequency information while discarding the high-frequency one
(Wang et al., 2022; Liu et al., 2022), while high-frequency information is
much more important for classification on heterophilic graphs (Bo et al.,
2021). By contrast, edge-wise positive pairs enable Local-GCL to learn the
differences between connected nodes better, thus benefiting heterophilic
graphs.

####  C.3.2 Different strategies for constructing positive examples using
neighborhoods

In addition to treating each neighboring node equally as positive examples, we
further explore two other positive sampling strategies: 1) computing the
similarities between neighboring nodes and using the most similar one as the
positive example (we term it Local-GCL-max); 2) reweighting the importance of
different neighboring nodes according to their similarities, where more
similar neighboring node should be assigned a larger weight (we term it Local-
GCL-weight).

For Local-GCL-max, we first its the nearest neighbor:

$\bm{s}_{i}=\mathop{\arg\min}_{\bm{z}_{j},j\in\mathcal{N}(i)}\left\|\frac{\bm{z}_{j}}{\|\bm{z}_{j}\|_{2}^{2}}-\frac{\bm{z}_{i}}{\|\bm{z}_{i}\|_{2}^{2}}\right\|^{2},$
(16)

and the objective function is

$\mathcal{L}_{LocalGCL-
max}=-\frac{1}{|\mathcal{V}|}\sum\limits_{i=1}^{|\mathcal{V}|}\log\frac{\exp(\bm{z}_{i}^{\top}\bm{s}_{i}/\tau)}{\sum\limits_{k\in\mathcal{V}}\exp(\bm{z}_{i}^{\top}\bm{z}_{k}/\tau)}.$
(17)

For LocalGCL-weight, we first compute the pair-wise similarities of
neighboring nodes:

$\text{sim}_{ij}=\bm{A}_{i,j}\cdot\frac{\bm{z}_{i}^{\top}\bm{z}_{j}}{\|\bm{z}_{i}\|_{2}^{2}\|\bm{z}_{j}\|_{2}^{2}}.$
(18)

Then, for a target node $i$, it softmax the scores of its neighboring nodes as
the weights:

$w_{i}(j)=\text{softmax}[\text{sim}_{ij}]_{j\in\mathcal{N}(i)}.$ (19)

The objective function of LocalGCL-weight is consequently defined as

$\mathcal{L}_{LocalGCL-
weight}=-\frac{1}{|\mathcal{V}|}\sum\limits_{i=1}^{|\mathcal{V}|}\log\frac{\sum\limits_{j\in\mathcal{N}(i)}w_{i}(j)\exp(\bm{z}_{i}^{\top}\bm{z}_{j}/\tau)/|\mathcal{N}(i)|}{\sum\limits_{k\in\mathcal{V}}\exp(\bm{z}_{i}^{\top}\bm{z}_{k}/\tau)}.$
(20)

The results of Local-GCL-max and Local-GCL-weight, together with the original
Local-GCL is presented in Table 6:

Table 6: Performance variation when using different strategies of constructing positive examples from neighboring nodes. | Cora | Citeseer | Pubmed
---|---|---|---
Local-GCL (origin) | 84.5 $\pm$ 0.4 | 73.6 $\pm$ 0.4 | 82.1 $\pm$ 0.5
Local-GCL-max | 83.6 $\pm$ 0.5 | 73.7 $\pm$ 0.5 | 81.7 $\pm$ 0.5
Local-GCL-weight | 84.9 $\pm$ 0.4 | 73.7 $\pm$ 0.4 | 82.2 $\pm$ 0.5

From this table, we can observe that using the nearest neighboring node as the
only one positive example is likely harmful (except on Citeseer) to the
performance, this should be because this operation can discard a lot of useful
information in the local neighborhood. Besides, Local-GCL-weight improves the
performance on Cora significantly but makes little difference on Citeseer and
Pubmed. This might be because, without supervision, a higher similarity in the
latent space does not necessarily indicate a higher probability of sharing the
same label. Considering that Local-GCL-weight requires additional
computational cost for computing the weights, and the performance of the
original Local-GCL is already quite good, we just treat every neighboring node
equally in this work.

####  C.3.3 Combining with negative-sample-free self-supervised learning
methods

using the target node’s first-order neighbors as positive examples) could also
benefit non-contrastive methods, like BGRL and CCA-SSG. Note that both BGRL
and CCA-SSG use the exact same data augmentations methods proposed in GRACE (a
contrastive method). As a result, we can simply replace the positive examples
in BGRL, and on-diagonal terms in CCA-SSG with the ones used in this paper,
thus making them free from data augmentations. In such as a case, the models
do not require two-viewed data as inputs, so the size of inputs, intermediate
variables, and outputs can be reduced by half. To better demonstrate this
point, we further extend our method with BGRL and CCA-SSG.

For BGRL, denote the target embedding of node $i$ by $\bm{h}_{i}$ and the
corresponding prediction by $\bm{z}_{i}$, our BGRL-Local optimizes the
following loss function:

$\mathcal{L}_{BGRL-
Local}=-\frac{2}{N}\sum\limits_{i\in\mathcal{V}}\sum\limits_{j\in\mathcal{N}(i)}\frac{\bm{z}_{j}\cdot\bm{h}_{i}}{\|\bm{z}_{j}\|_{2}^{2}\|\bm{h}_{i}\|_{2}^{2}}$
(21)

For CCA-SSG, denote the embedding of node $i$ by $\bm{h}_{i}$, we first
compute the local summary of node $i$ by
$\bm{z}_{i}=\frac{1}{|\mathcal{N}(i)|}\sum\limits_{j\in\mathcal{N}(i)}\bm{h}_{j}$.
Then we compute two standardized embedding matrices by:

$\tilde{\bm{H}}=\frac{\bm{H}-\mu(\bm{H})}{\sigma(\bm{H})*\sqrt{|\mathcal{V}|}},\tilde{\bm{Z}}=\frac{\bm{Z}-\mu(\bm{Z})}{\sigma(\bm{Z})*\sqrt{|\mathcal{V}|}}.$
(22)

Finally, CCA-SSG-Local optimizes the following loss function:

$\mathcal{L}_{CCA-SSG-
Local}=\left\|\tilde{\bm{H}}-\tilde{\bm{Z}}\right\|_{F}^{2}+\lambda\left(\left\|\tilde{\bm{H}}^{\top}\tilde{\bm{H}}-\bm{I}\right\|_{F}^{2}+\left\|\tilde{\bm{Z}}^{\top}\tilde{\bm{Z}}-\bm{I}\right\|_{F}^{2}\right).$
(23)

We report the performance of BGRL-Local and CCA-SSG-Local compared with the
original BGRL and CCA-SSG on CS and Physics, together with their training
time/memory cost in Table 7 (We didn’t choose the three citation networks as
BGRL performs really bad on them).

Table 7: Test accuracy, training time cost and memory cost when using the positive pair constructing method in this paper compared with using data augmentation for BGRL and CCA-SSG. | Coauthor-CS | Coauthor-Physics
---|---|---
Acc | Time | Memory | Acc | Time | Memory
BGRL | 92.59 $\pm$ 0.17 | 30.4 min | 2.9G | 95.48 $\pm$ 0.08 | 57.7 min | 5.6G
BGRL-Local | 92.98 $\pm$ 0.23 | 18.2 min | 1.8G | 95.82 $\pm$ 0.11 | 32.3 min | 3.7G
CCA-SSG | 93.31 $\pm$ 0.22 | 1.1 min | 3.5G | 95.38 $\pm$ 0.06 | 5.9 min | 7.1G
CCA-SSG-Local | 94.08 $\pm$ 0.19 | 0.7 min | 2.2G | 95.69 $\pm$ 0.09 | 4.3 min | 4.4G

(BGRL takes much longer time for training, because it does require a lot of
training epochs to converge.) As demonstrated in the table. The performance of
BGRL and CCA-SSG both get improved after adopting neighboring nodes as
positive examples, which highlights the value of graph structure information
as self-supervised learning signals. Besides, it also reduces the training
time and memory cost because it gets rid of the two-branch architecture caused
by data augmentations.

####  C.3.4 Combining with hard negative sampling methods

Furthermore, one important advantage of contrastive learning is that it can be
incorporated with hard negative sampling techniques (Robinson et al., 2021;
Kalantidis et al., 2020; Zhang et al., 2022; Xia et al., 2022). These works
either assign weights to different negative samples so that true negative
examples are more important than false negative examples, or use mix-up
methods to generate even harder negative examples. With these techniques, the
performance of contrastive learning can be greatly boosted. To demonstrate
this point, we further combine our method with the hard negative mining
strategy ProGCL-mix proposed in Xia et al. (2022), and we report the
performance comparison on Cora, Citeseer and Pubmed in Table 8:

Table 8: Effect of combining Local-GCL with hard-negative sampling methods. | Cora | Citeseer | Pubmed
---|---|---|---
Local-GCL (origin) | 84.5 $\pm$ 0.4 | 73.6 $\pm$ 0.4 | 82.1 $\pm$ 0.5
Local-GCL +ProGCL-mix | 84.9 $\pm$ 0.5 | 74.2 $\pm$ 0.4 | 82.3 $\pm$ 0.5

The improvement is prominent (especially on Citeseer) thanks to the hard-
negative sampling strategy(however, ProGCL-mix is not our contribution so we
cannot include it in our method in this paper). Besides, we notice that the
improvement on Pubmed is smaller than that on the other two datasets, we guess
this is because there are only 3 classes of nodes on Pubmed, so it is less
effective to mine hard negatives than 7 classes on Cora and 6 on Citeseer.


# Is $K_{1}/K^{*}$ enhancement in heavy ion collisions a signature of chiral
symmetry restoration?

Haesom Sung<EMAIL_ADDRESS>Department of Physics and Institute of
Physics and Applied Physics, Yonsei University, Seoul 03722, Korea  Cyclotron
Institute, Texas $A\&M$ University, College Station, TX 77843, USA  Sungtae
Cho<EMAIL_ADDRESS>Division of Science Education, Kangwon National
University, Chuncheon 24341, Korea  Che Ming Ko<EMAIL_ADDRESS>Cyclotron
Institute, Texas $A\&M$ University, College Station, TX 77843, USA  Department
of Physics and Astronomy, Texas $A\&M$ University, College Station, TX 77843,
USA  Su Houng Lee<EMAIL_ADDRESS>Department of Physics and Institute of
Physics and Applied Physics, Yonsei University, Seoul 03722, Korea  Sanghoon
Lim<EMAIL_ADDRESS>Department of Physics, Pusan National University,
Pusan, Republic of Korea

###### Abstract

We extend the recent study of $K_{1}/K^{*}$ enhancement as a signature of
chiral symmetry restoration in heavy ion collisions at the Large Hadron
Collider (LHC) via the kinetic approach to include the effects due to non-
unity hadron fugacities during the evolution of produced hadronic matter and
the temperature-dependent $K_{1}$ mass. Although the effect of non-unity
fugacity only slightly reduces the $K_{1}/K^{*}$ enhancement due to chiral
symmetry restoration, the inclusion of the temperature-dependent $K_{1}$ mass
leads to a substantial reduction in the $K_{1}/K^{*}$ enhancement. However,
the final $K_{1}/K^{*}$ ratio in peripheral collisions still shows a more than
factor of two enhancement compared to the case without chiral symmetry
restoration and thus remains a good signature for chiral symmetry restoration
in the hot dense matter produced in relativistic heavy ion collisions.

##  I Introduction

According to lattice QCD calculations, the quark-gluon plasma (QGP) to
hadronic matter (HM) transition at vanishing baryon chemical potential is a
smooth crossover with a critical temperature $T_{C}$ at about 156 MeV Bazavov
_et al._ (2019). This temperature coincides with the chemical freeze-out
temperature in the statistical model for particle production in relativistic
heavy ion collisions at energies available from the Relativistic Heavy Ion
Collider (RHIC) and the LHC Andronic  _et al._ (2006, 2013); Stachel  _et al._
(2014). Since chiral symmetry is restored above this temperature, masses of
chiral partners are expected to become degenerate near $T_{C}$ as indicated in
studies based on the QCD sum rules for the axial vector meson $K_{1}(1270)$
and vector meson $K^{*}(890)$ masses Lee (2023) as well as the lattice QCD
Skullerud  _et al._ (2022) and the functional renormalization group Jung  _et
al._ (2017) calculations for the axial vector meson $a_{1}(1260)$ and vector
meson $\rho(770)$ masses. Because of the shorter lifetimes of $K_{1}(1270)$
and $K^{*}(890)$, which have vacuum decay widths of 90 MeV and 47 MeV,
respectively, than that of the hadronic stage of relativistic heavy ion
collisions, their yield ratio $K_{1}/K^{*}$ in nuclear reactions is expected
to depend on the degree of chiral symmetry restoration in the produced matter.
A recent study by some of the present authors Sung  _et al._ (2021) has indeed
found this effect in Pb+Pb collisions at $\sqrt{s_{NN}}=5.02$ TeV. Using the
$K_{1}$ number at $T_{C}$ obtained from the statistical hadronization model by
taking the masses of $K_{1}$ and $K^{*}$ to be $m_{K_{1}}=m_{K^{*}}=890$ MeV
according to a QCD sum rule calculation Kim and Lee (2021) and assuming the
$K_{1}$ mass immediately changes to its vacuum mass in the produced hadronic
matter, they have studied the effect of hadronic scatterings on the yield
ratio $K_{1}/K^{*}$ via a kinetic approach. Based on a schematic hydrodynamic
model for the evolution of produced hot dense matter using the lattice
equation of state for the QGP and the resonance hadron gas model for the HM
Song  _et al._ (2011), the time evolution of $K_{1}$ and $K^{*}$ abundances
are studied by taking into account the reactions $K_{1}\pi\leftrightarrow
K\pi$, $K_{1}\pi\leftrightarrow K^{*}\rho$, $K_{1}\rho\leftrightarrow
K^{*}\pi$, and $K_{1}\rho\leftrightarrow K\rho$. Their results show that the
ratio $K_{1}/K^{*}$ is increased by a factor of 3 in mid-central collisions
(40-50% centrality) and by a factor of 6 in peripheral collisions (70-80%
centrality) compared to that without including the effect of chiral symmetry
restoration, although it does not change much in central collisions (0-5%
centrality).

The study in Ref. Sung  _et al._ (2021) has, however, neglected two important
effects, namely, 1) the constancy of effective pion, kaon and nucleon numbers
during the hadronic evolution after including those from resonance decays,
which is supported by the success of the statistical hadonization model that
these effective numbers are fixed at $T_{C}$ when the chemical freeze out
takes place, and 2) the temperature-dependent $K_{1}$ mass in the hadronic
matter Lee (2023). As shown in a study using a multi-phase transport (AMPT)
model Xu and Ko (2017), to maintain the same effective pion, kaon and nucleon
abundance during the hadron evolution, non-unity pion, kaon and nucleon
fugacities are required. In the present study, we include this effect by
keeping the effective pion, kaon and nucleon numbers at any time during the
hadronic evolution to remain unchanged. For the temperature-dependent $K_{1}$
mass given in Ref. Lee (2023), it depends on the temperature dependence of the
quark condensate, which we take from Ref. Weise (2012). Including these two
effects in the kinetic equations and using the same time evolution for the
temperature and volume of the hadronic matter from the schematic hydrodynamic
approach of Ref. Sung  _et al._ (2021), we study here how the yield ratio
$K_{1}/K^{*}$ is affected by these two effects. We note that the entropy is
assumed to be conserved in Ref. Sung  _et al._ (2021), which we follow in the
present study as it has been shown that adding viscosity in the expanding
hadronic matter does not affect much the time evolution of the volume and
temperature of the hadronic matter Song  _et al._ (2011). By considering both
the non-unity fugacity effect and the temperature-dependent mass of $K_{1}$,
we aim to provide a more realistic discription of the variation of the ratio
between $K_{1}$ and $K^{*}$ across different centralities. The result from
present study confirms that the final $K_{1}/K^{*}$ ratio enhancement can
serve as a good signature for the chiral symmetry restoration in the hot dense
matter produced in relativistic heavy ion collisions.

The present paper is organized as follows. We first review in Sec. II the
temperature dependence of $K_{1}$ mass in a hadronic matter at finite
temperature and then use it in Sec. III to calculate the cross sections for
$K_{1}$ and $K^{*}$ reactions with pion and rho meson as well as their thermal
averages. In Sec. IV, we determine the temperature dependence of the pion,
kaon, and nucleon fugacities by requiring the effective pion, kaon and nucleon
numbers, which included those from resonance decays, from the schematic
hydrodynamic model used in Ref. Sung  _et al._ (2021) to remain unchanged
during hadronic evolution. The kinetic equations for the time evolution of the
$K_{1}$ and $K^{*}$ numbers are then given in Sec. V. We further present the
results on the yield ratio $K_{1}/K^{*}$ in Pb+Pb collisions in Sec. VI and
finally give a brief summary in Sec. VII.

##  II Temperature-dependent $K_{1}$ meson mass

Figure 1: Temperature dependence of $K_{1}$ mass. Solid line corresponds to
the QCD sum rule prediction of Ref. Lee (2023), while dotted line is the one
assumed in Ref. Sung  _et al._ (2021) with $T_{C}=156$ MeV.

According to the QCD sum rule study of Ref. Lee (2023), the mass difference
between $K_{1}$ and $K^{*}$ in a hot hadronic matter depends on the quark
condensate $\langle\bar{q}q\rangle_{T}$ as

$m_{K_{1}}^{2}(T)=m_{K^{*}}^{2}+\frac{\langle\bar{q}q\rangle_{T}}{\langle\bar{q}q\rangle_{0}}(m_{K_{1}}^{2}-m_{K^{*}}^{2}).$
(1)

Neglecting the small change of $K^{*}$ mass with temperature Kim and Lee
(2021) and using $m_{K_{1}}$=1.27 GeV, $m_{K^{*}}$=0.892 GeV, and the
temperature-dependent quark condensate from Ref. Weise (2012), the temperature
dependence of $K_{1}$ mass is shown in Fig. 1. It is seen that the $K_{1}$
mass at $T_{C}$ is about 1.1 GeV, instead of the same as the $K^{*}$ free-
space mass of 0.892 GeV assumed in Ref. Song  _et al._ (2011), and then
gradually increases to its free-space value of 1.27 GeV.

##  III $K_{1}$ and $K^{*}$ reaction cross sections

Figure 2: Isospin averaged cross sections for $K_{1}\pi\to K\pi$ (panel (a)),
$K_{1}\pi\to K^{*}\rho$ (panel (b)), $K_{1}\rho\to K\rho$ (panel (c)), and
$K_{1}\rho\to K^{*}\pi$ (panel (d)) as functions of center-of-mass energy
$\sqrt{s}$ with $\sqrt{s_{0}}$ denoting the threshold of a reaction and
temperature.

In this Section, we review the $K_{1}$ and $K^{*}$ reaction cross sections
with pion and rho meson, whose abundance dominate in the hadronic matter.
These reactions include $K_{1}+\pi\to K+\pi$, $K_{1}+\pi\to K^{*}+\rho$,
$K_{1}+\rho\to K+\rho$, and $K_{1}+\rho\to K^{*}+\pi$, and their cross
sections have been calculated in Ref. Sung  _et al._ (2021) using the massive
Yang-Mills approach with a Lagrangian involving spin-0 and spin-1 mesons
Meissner (1988). Shown in Fig. 2 are the center-of-mass energy $\sqrt{s}$ and
temperature dependence of their isospin averaged cross sections. The most
important channel for $K_{1}$ annihilation is the endothermic reaction
$K_{1}+\pi\to K^{*}+\rho$, except near its threshold where other reactions
dominate because of their exothermic nature. In calculating the pion-exchange
$t$-channel diagram in the reaction $K_{1}+\pi\to K^{*}+\rho$, the pion can be
on shell at certain reaction energy. In this case, the reaction $K_{1}+\pi\to
K^{*}+\rho$ is the same as the two-step process of $K_{1}\to K^{*}+\pi$
followed by $\pi+\pi\to\rho$. Since the process $K_{1}\to K^{*}+\pi$ is
explicitly included in the kinetic equations used in our study, we therefore
exclude the contribution of on-shell pion to the pion-exchange $t$-channel
diagram of the reaction $K_{1}+\pi\to K^{*}+\rho$ as in Ref. Song  _et al._
(2011).

Figure 3: Temperature dependence of thermal averaged cross sections
$\langle\sigma v\rangle$ for the reactions $K_{1}\pi\to K\pi$ (dotted line),
$K_{1}\pi\to K^{*}\rho$ (solid line), $K_{1}\rho\to K\rho$ (dash-dash-dot-
dotted line), and $K_{1}\rho\to K^{*}\pi$ (dash-dot-dotted line), and thermal
averaged decay widths $\langle\Gamma\rangle$ of $K_{1}\to K\rho$ (dash-dash-
dotted line) and $K_{1}\to K^{*}\rho$ (dash-dotted line).

The above reactions enter the kinetic equations, which are given in Sec. V,
through their thermal average over the momentum distributions of the particles
in the initial state, i.e.,

$\displaystyle\left<\sigma_{ab\rightarrow cd}v_{ab}\right>$ $\displaystyle=$
$\displaystyle\frac{\int d^{3}{\bf p}_{a}d^{3}{\bf p}_{b}f_{a}({\bf
p}_{a})f_{b}({\bf p}_{b})\sigma_{ab\rightarrow cd}v_{ab}}{\int d^{3}{\bf
p}_{a}d^{3}{\bf p}_{b}f_{a}({\bf p}_{a})f_{b}({\bf p}_{b})}.$ (2)

In the above, $f_{i}({\bf p}_{i})$ is the Boltzman momentum distribution of
particle species $i=a,b$, i.e., $f_{i}(\vec{p}_{i})=e^{-\sqrt{{\bf
p}_{i}^{2}+m_{i}^{2}}/T}$ with $m_{i}$ being the particle mass, which we take
as their vacuum masses for pion, kaon, rho meson, and $K^{*}$ and the
temperature-dependent mass for $K_{1}$. The $v_{ab}$ in the above equation is
the relative velocity between the two initial particles $a$ and $b$. The
temperature-dependent thermal averaged cross sections for $K_{1}$ annihilation
by pion and rho meson are shown in Fig. 3. For the thermal averaged decay
width of $K_{1}$ meson, it is computed as
$\left<\Gamma_{K_{1}}\right>=\Gamma_{K_{1}}(m_{K_{1}})K_{1}(m_{K_{1}}/T)/K_{2}(m_{K_{1}}/T)$,
where $K_{1}(x)$ and $K_{2}(x)$ are modified Bessel functions of first and
second kind, respectively, to take into account its temperature-dependent mass
and the effect of time dilation. For the $K^{*}$ thermal averaged cross
sections by pion and rho meson, we take them from Ref. Cho and Lee (2018).

##  IV Fugacities of pion, kaon and nucleon

Figure 4: Temperature dependence of pion (solid line), kaon (dashed line) and
nucleon (dash-dotted line) fugacities in collisions of Pb+Pb at
$\sqrt{s_{NN}}=5.02$ TeV centrality for the three collision centralities of
0-5 % (top panel), 40-50 % (middle panel), and 70-80 % (bottom panel).

According to the statistical model for particle production in relativistic
heavy ion collisions, particle yields including contributions from resonances
decays, i.e., their effective numbers, are determined at the chemical freeze-
out temperature, which coincides with the QGP to HM phase transition
temperature Andronic  _et al._ (2006, 2013); Stachel  _et al._ (2014). To
maintain the effective pion, kaon and nucleon numbers, which are relevant in
the present study, during the expansion and cooling of the hadronic matter, it
is necessary for them to acquire non-unity fugacity, as shown in Ref. Xu and
Ko (2017). In this case, the pion, kaon and nucleon momentum distributions in
the Boltzmann approximation need to be multiplied by their fugacity $z_{i}$,
i.e., $z_{i}f_{i}({\bf p})$. In terms of the thermally equilibrated number
$N_{i}^{T}=\frac{g_{i}V}{(2\pi)^{3}}\int d^{3}{\bf p}f_{i}({\bf p})$, where
$V$ is the volume of the hadronic matter when it has temperature $T$, the
effective pion number in the hadronic matter is then given by the sum of free
pions and those from resonance decays, i.e.,

$N^{\rm
eff}_{\pi}=z_{\pi}N_{\pi}^{T}+z_{\pi}^{2}N_{\rho}^{T}+z_{\pi}z_{K}N_{K^{*}}^{T}+z_{\pi}z_{N}N_{\Delta}^{T}+\cdots,$
(3)

where $\cdots$ denotes other resonances whose decay involve pions in the final
state, if we assume all particles are in thermal and chemical equilibrium.
Using the time evolution of the volume and temperature of produced matter
given in Ref. Sung  _et al._ (2021) for Pb+Pb collision at $\sqrt{s}_{NN}$ =
5.02 TeV, which is obtained from a schematic ideal hydrodynamic model Song
_et al._ (2011), to keep the effective pion, kaon and nucleon numbers
unchanged during hadronic evolution allows us to determine the time dependence
of the pion, kaon and nucleon fugacities in collisions at a given
centralities. These results are shown in Fig. 4 for the three collision
centralities of 0-5 %, 40-50 %, and 70-80%. It is seen that with decreasing
temperature of the hadronic matter, the nucleon fugacity increases
appreciably, particularly in central and mid-central collisions, while the
pion fugacity decreases slightly in all three collision centralities, and the
kaon fugacity increases slightly in central and mid-central collisions but
decreases slightly in peripheral collisions. We note that, while the chemical
freeze-out temperature is 156 MeV in all centralities, which is close to the
critical temperature for the QGP to HM phase transition, the kinetic freeze-
out temperatures for the three centralities are 90 MeV, 108 MeV, and 147 MeV,
respectively. It is also worthwhile to mention that the effective pion, kaon,
and nucleon numbers at kinetic freeze out of our study agree with those
measured by the ALICE Collaboration Acharya  _et al._ (2020).

##  V Kinetic equations for $K_{1}$, $K^{*}$ and $K$

Neglecting the creation and annihilation of strange hadrons, such as the
reaction $\pi\pi\leftrightarrow K\bar{K}$, which has little effect on the
results in the present study, then $N_{0}=N_{K_{1}}+N_{K^{*}}+N_{K}$ is a
constant during the hadronic evolution. In this case, the kinetic equation for
the time evolution of $K_{1}$ number can be written as

$\displaystyle\frac{dN_{K_{1}}}{dt}=\gamma_{K_{1},K_{1}}N_{K_{1}}+\gamma_{K_{1},K^{*}}N_{K^{*}}+\gamma_{K_{1},K}N_{K},$
(4)

where

$\displaystyle\gamma_{K_{1},K_{1}}=-(\langle\sigma_{K_{1}\pi\to
K\pi}\rangle+\langle\sigma_{K_{1}\pi\to K^{*}\rho}v\rangle)z_{\pi}n_{\pi}^{T}$
$\displaystyle\qquad\qquad-(\langle\sigma_{K_{1}\rho\to
K^{*}\pi}v\rangle+\langle\sigma_{K_{1}\rho\to
K\rho}v\rangle)z_{\pi}^{2}n_{\rho}^{T}$
$\displaystyle\qquad\qquad-\langle\Gamma_{K_{1}\to
K^{*}\pi}\rangle-\langle\Gamma_{K_{1}\to K\rho}\rangle,$ (5)
$\displaystyle\gamma_{K_{1},K^{*}}=(\langle\sigma_{K_{1}\pi\to
K^{*}\rho}v\rangle n_{\pi}^{T}+\langle\sigma_{K_{1}\rho\to K^{*}\pi}v\rangle
z_{\pi}n_{\rho}^{T})\frac{z_{\pi}^{2}n_{K_{1}}^{T}}{n_{K^{*}}^{T}}$
$\displaystyle\qquad\qquad+\langle\Gamma_{K_{1}\to
K^{*}\pi}\rangle\frac{z_{\pi}n_{K_{1}}^{T}}{n_{K^{*}}^{T}},$ (6)
$\displaystyle\gamma_{K_{1},K}=(\langle\sigma_{K_{1}\pi\to K\pi}v\rangle
n_{\pi}^{T}+\langle\sigma_{K_{1}\rho\to K\rho}v\rangle
z_{\pi}n_{\rho}^{T})\frac{z_{\pi}^{2}n_{K_{1}}^{T}}{n_{K}^{T}}$
$\displaystyle\qquad\qquad+\langle\Gamma_{K_{1}\to
K\rho}\rangle\frac{z_{\pi}n_{K_{1}}^{T}}{n_{K}^{T}},$ (7)

where $n_{\pi}^{T}$, $n_{\rho}^{T}$, $n_{K}^{T}$, $n_{K^{*}}^{T}$ and
$n_{K_{1}}^{T}$ are, respectively, the thermally equilibrated densities of
$\pi$, $\rho$, $K$, $K^{*}$ and $K^{1}$ mesons. In obtaining above kinetic
equations, we have used the fugacity relations $z_{\rho}=z_{\pi}^{2}$,
$z_{K^{*}}=z_{K}z_{\pi}$ and $z_{K_{1}}=z_{K}z_{\pi}^{2}$, and also expressed
the contributions from the $K_{1}$ regeneration processes in terms of those
from the $K_{1}$ annihilation processes by using the detailed balance
relations.

Similarly, the kinetic equation for the time evolution of $K^{*}$ number is
given by

$\displaystyle\frac{dN_{K^{*}}}{dt}=\gamma_{K^{*},K_{1}}N_{K_{1}}+\gamma_{K^{*},K^{*}}N_{K^{*}}+\gamma_{K^{*},K}N_{K},$
(8)

where

$\displaystyle\gamma_{K^{*},K_{1}}=\langle\sigma_{K_{1}\pi\to
K^{*}\rho}v\rangle z_{\pi}n_{\pi}^{T}+\langle\sigma_{K_{1}\rho\to
K^{*}\pi}v\rangle z_{\pi}^{2}n_{\rho}^{T}$
$\displaystyle\qquad\qquad+\langle\Gamma_{K_{1}\to K^{*}\pi}\rangle,$ (9)
$\displaystyle\gamma_{K^{*},K^{*}}=-\langle\sigma_{K^{*}\pi\to K\rho}v\rangle
z_{\pi}n_{\pi}^{T}-\langle\sigma_{K^{*}\rho\to K\pi}v\rangle
z_{\pi}^{2}n_{\rho}^{T}$
$\displaystyle\qquad\qquad-(\langle\sigma_{K_{1}\pi\to K^{*}\rho}v\rangle
n_{\pi}^{T}+\langle\sigma_{K_{1}\rho\to K^{*}\pi}v\rangle
z_{\pi}n_{\rho}^{T})\frac{z_{\pi}^{2}n_{K_{1}}^{T}}{n_{K^{*}}^{T}}$
$\displaystyle\qquad\qquad-\langle\Gamma_{K^{*}\to
K\pi}\rangle-\langle\Gamma_{K_{1}\to
K^{*}\pi}\rangle\frac{z_{\pi}n_{K_{1}}^{T}}{n_{K^{*}}^{T}},$ (10)
$\displaystyle\gamma_{K^{*},K}=(\langle\sigma_{K^{*}\pi\to K\rho}v\rangle
n_{\pi}^{T}+\langle\sigma_{K^{*}\rho\to K\pi}v\rangle
z_{\pi}n_{\rho}^{T})\frac{z_{\pi}^{2}n_{K^{*}}^{T}}{n_{K}^{T}}$
$\displaystyle\qquad\qquad+\langle\Gamma_{K^{*}\to
K\pi}\rangle\frac{z_{\pi}n_{K^{*}}^{T}}{n_{K}^{T}}.$ (11)

##  VI results

Figure 5: The yield ratio $K_{1}/K^{*}$ in Pb+Pb collisions at
$\sqrt{s_{NN}}=5.02$ TeV at three centralities of 0-5%, 40-50% and 70-80% for
various scenarios.

We solve the kinetic equations in Sec. V using the thermal averaged $K_{1}$
and $K^{*}$ reaction cross sections and $K_{1}$ decay widths given in Sec. III
and the time dependence of the temperature and volume of the hadronic matter
after the QGP to HM phase transition given in Ref. Song  _et al._ (2011) for
Pb+Pb collisions at $\sqrt{s_{NN}}=5.02$ TeV. Results for the yield ratio
$K_{1}/K^{*}$ are shown in Fig. 5 for the three collision centralities of
0-5%, 40-50% and 70-80%. Results including both the effect of non-unity pion
and kaon fugacities as well as the temperature-dependent $K_{1}$ mass are
shown by the solid red line. Compared to the results of Ref. Song  _et al._
(2011), shown by the black dashed line, in which both pion and kaon fugacities
are taken to be one and the $K_{1}$ has free-space mass below $T_{C}$,
although it is taken to have a mass equal to the $K^{*}$ free mass at $T_{C}$,
the final $K_{1}/K^{*}$ ratio from present study is reduced by a factor of 2.8
for 70-80% collision centrality. This yield ratio is, however, still a factor
of 2.3 larger than the case without including the chiral symmetry restoration
effect shown by the black line, indicating that an enhanced $K_{1}/K^{*}$
yield ratio in peripheral relativistic heavy ion collisions remains a good
signature for studying chiral symmetry restoration in these collisions. We
note that the reduced $K_{1}/K^{*}$ ratio in the present study compared to
that in Ref. Song  _et al._ (2011) is mainly due to the use of more realistic
temperature-dependent $K_{1}$ mass. Without the latter effect, the non-unity
pion and kaon fugacities has only a relatively small effect on the
$K_{1}/K^{*}$ ratio as shown by the solid blue line, which is close to that in
Ref. Song  _et al._ (2011). Also shown in Fig. 5 by the dashed cyan line is
the $K_{1}/K^{*}$ ratio from the statistical model, which has a value of about
0.14, independent of the collision centrality.

##  VII Summary

In the present study, we have extended the study of Ref. Song  _et al._ (2011)
on the use of enhanced yield ratio $K_{1}/K^{*}$ in relativistic heavy ion
collisions as a probe for chiral symmetry restoration by including non-unity
pion, kaon and nucleon fugacities as well as the temperature-dependent $K_{1}$
mass in the expanding hadronic matter. Our results show that, although the
effect due to non-unity pion and kaon fugacities slightly reduces the
$K_{1}/K^{*}$ enhancement due to chiral symmetry restoration, the inclusion of
the temperature-dependent $K_{1}$ mass leads to a substantial reduction in the
$K_{1}/K^{*}$ enhancement. However, the final $K_{1}/K^{*}$ ratio in
peripheral collisions still shows a more than factor of two enhancement
compared to the case without chiral symmetry restoration and thus remains a
good signature for chiral symmetry restoration in the hot dense matter
produced in ultra-relativistic heavy-ion collisions.

## ACKNOWLEDGEMENTS

This work was supported by the Korea National Research Foundation under Grant
No. RS-2023-00280831 (S.C.), No. 2023R1A2C300302311 (S.H.L.) and Project No.
NRF-2008-00458 (S.L.), and the U.S. Department of Energy under Award No. DE-
SC0015266 (C.M.K.). S. H. Lee also acknowledges the support from the Samsung
Science and Technology Foundation under Project No. SSTF-BA1901-04. H. Sung
thanks the Cyclotron Institute of Texas A&M University for its hospitality
during her stay as a visiting scholar supported by a graduate fellowship from
the National Research Foundation of Korea under Award No.
NRF-2022K1A3A1A12097807.

## References

  * Bazavov  _et al._ (2019) A. Bazavov _et al._ (HotQCD), Phys. Lett. B 795, 15 (2019), arXiv:1812.08235 [hep-lat] .
  * Andronic  _et al._ (2006) A. Andronic, P. Braun-Munzinger, and J. Stachel, Nucl. Phys. A 772, 167 (2006), arXiv:nucl-th/0511071 .
  * Andronic  _et al._ (2013) A. Andronic, P. Braun-Munzinger, K. Redlich, and J. Stachel, Nucl. Phys. A 904-905, 535c (2013), arXiv:1210.7724 [nucl-th] .
  * Stachel  _et al._ (2014) J. Stachel, A. Andronic, P. Braun-Munzinger, and K. Redlich, J. Phys. Conf. Ser. 509, 012019 (2014), arXiv:1311.4662 [nucl-th] .
  * Lee (2023) S. H. Lee, Symmetry 15, 799 (2023), arXiv:2303.14415 [hep-ph] .
  * Skullerud  _et al._ (2022) J.-I. Skullerud _et al._ , EPJ Web Conf. 274, 05011 (2022), arXiv:2211.13717 [hep-lat] .
  * Jung  _et al._ (2017) C. Jung, F. Rennecke, R.-A. Tripolt, L. von Smekal, and J. Wambach, Phys. Rev. D 95, 036020 (2017), arXiv:1610.08754 [hep-ph] .
  * Sung  _et al._ (2021) H. Sung, S. Cho, J. Hong, S. H. Lee, S. Lim, and T. Song, Phys. Lett. B 819, 136388 (2021), arXiv:2102.11665 [nucl-th] .
  * Kim and Lee (2021) J. Kim and S. H. Lee, Phys. Rev. D 103, L051501 (2021), arXiv:2012.06463 [nucl-th] .
  * Song  _et al._ (2011) T. Song, K. C. Han, and C. M. Ko, Phys. Rev. C 83, 024904 (2011), arXiv:1012.0798 [nucl-th] .
  * Xu and Ko (2017) J. Xu and C. M. Ko, Phys. Lett. B 772, 290 (2017), arXiv:1704.04934 [nucl-th] .
  * Weise (2012) W. Weise, Prog. Part. Nucl. Phys. 67, 299 (2012), arXiv:1201.0950 [nucl-th] .
  * Meissner (1988) U. G. Meissner, Phys. Rept. 161, 213 (1988).
  * Cho and Lee (2018) S. Cho and S. H. Lee, Phys. Rev. C 97, 034908 (2018), arXiv:1509.04092 [nucl-th] .
  * Acharya  _et al._ (2020) S. Acharya _et al._ (ALICE), Phys. Rev. C 101, 044907 (2020), arXiv:1910.07678 [nucl-ex] .