# perfect alignment may be poisonous to graph contrastive learning

Jingyu Liu1,Huayi Tang1,Yong Liu1,2
1Gaoling School of Artificial Intelligence, Renmin University of China,
Beijing, China
2Beijing Key Laboratory of Big Data Management and Analysis Methods, Beijing,
China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Corresponding Author.

###### Abstract

Graph Contrastive Learning (GCL) aims to learn node representations by
aligning positive pairs and separating negative ones. However, limited
research has been conducted on the inner law behind specific augmentations
used in graph-based learning. What kind of augmentation will help downstream
performance, how does contrastive learning actually influence downstream
tasks, and why the magnitude of augmentation matters? This paper seeks to
address these questions by establishing a connection between augmentation and
downstream performance, as well as by investigating the generalization of
contrastive learning. Our findings reveal that GCL contributes to downstream
tasks mainly by separating different classes rather than gathering nodes of
the same class. So perfect alignment and augmentation overlap which draw all
intra-class samples the same can not explain the success of contrastive
learning. Then in order to comprehend how augmentation aids the contrastive
learning process, we conduct further investigations into its generalization,
finding that perfect alignment that draw positive pair the same could help
contrastive loss but is poisonous to generalization, on the contrary,
imperfect alignment enhances the model’s generalization ability. We analyse
the result by information theory and graph spectrum theory respectively, and
propose two simple but effective methods to verify the theories. The two
methods could be easily applied to various GCL algorithms and extensive
experiments are conducted to prove its effectiveness.

##  1 Introduction

Graph Neural Networks (GNNs) have been successfully applied in various fields
such as recommendation systems (He et al., 2020b), drug discovery (Liu et al.,
2018), and traffic analysis (Wu et al., 2019), etc. However, most GNNs require
labeled data for training, which may not always be available or easily
accessible. To address this issue, Graph Contrastive Learning (GCL), which
does not rely on labels, has gained popularity as a new approach to graph
representation learning (Veličković et al., 2018; You et al., 2020).

GCL often generates new graph views through data augmentation (Chen et al.,
2020a; Zhu et al., 2020). GCL uses nodes augmented from the same node as
positive samples and other nodes as negative samples, then maximize similarity
between positive samples and minimize similarity between negative ones (Wang &
Isola, 2020; Hassani & Khasahmadi, 2020). Data augmentation can be categorized
into three types (Zhao et al., 2022a): random augmentation (Veličković et al.,
2018; Zhu et al., 2020), rule-based augmentation (Zhu et al., 2021; Wei et
al., 2023; Liu et al., 2022), and learning-based augmentation (Suresh et al.,
2021; Jiang et al., 2019). For instance, Zhu et al. (2020) randomly masks node
attributes and edges in graph data to obtain augmented graphs; Zhu et al.
(2021) uses node degree to measure its importance and mask those unimportant
with higher probability; And Suresh et al. (2021) uses a model to learn the
best augmentation and remove irrelevant information as much as possible.
However, most data augmentation algorithms are designed heuristically, and
there is a lack of theoretical analysis on how these methods will influence
the downstream performance.

Some researchers have explored the generalization ability of contrastive
learning (Arora et al., 2019; Wang & Isola, 2020; Huang et al., 2021). They
propose contrastive learning works by gathering positive pairs and separating
negative samples uniformly. Wang et al. (2022b) argues that perfect alignment
and uniformity alone cannot guarantee optimal performance. They propose that
through stronger augmentation, there will be support overlap between different
intra-class samples, which is called augmentation overlap (Saunshi et al.,
2022; Huang et al., 2021). Thus, the alignment of positive samples will also
cluster all the intra-class samples together, and lead to class-separated
representations due to the limited inter-class overlap. However, Saunshi et
al. (2022) points out that augmentation overlap may be relatively rare despite
the excellent performance of contrastive learning methods. Hence, chances are
that the success of contrastive learning cannot be solely attributed to
alignment and augmentation overlap. It is of vital importance to evaluate how
augmentation works in the contrastive learning process, why the magnitude of
augmentation matters so much and how to perform better augmentation? As data
augmentation on graphs could be more customized and the magnitude of
augmentation can be clearly represented by the number of modified edges/nodes
(You et al., 2020), we mainly study the augmentation on graphs. But it works
the same in other fields.

In this paper, we provide a new understanding of Graph Contrastive Learning
and use a theoretical approach to analyze the impact of augmentation on model
generalization. We find that with a better augmentation, the model is
performing better mainly because of inter-class separating rather than intra-
class gathering brought by augmentation overlap. So perfect augmentation
overlap and alignment are not the key factor for contrastive learning. To
further analyze the phenomena, we formulate a relationship between downstream
performance, contrastive learning loss, and augmentation, reveal the reason
why stronger augmentation helps class separating, and find stronger
augmentation could benefit the generalization by weaken the positive pair
alignment. Therefore, perfect alignment is not the key to success, and may be
poisonous to contrastive learning.

Then aiming to achieve a better balance between generalization and contrastive
loss, we further analyze the contrastive process through information theory
and graph spectrum theory. From the information theory perspective, we find
augmentation should be stronger while reducing the information loss, which is
actually adopted explicitly or implicitly by designed algorithms (Zhu et al.,
2021; 2020; Suresh et al., 2021). From the graph spectrum theory perspective,
we analyze how the graph spectrum will affect the contrastive loss and
generalization (Liu et al., 2022), finding that non-smooth spectral
distribution will have a negative impact on generalization. Then we propose
two methods based on the theories to verify our findings.

Our main contributions are as follows. (1) We reveal that when stronger
augmentation is applied, contrastive learning benefits from inter-class
separating more than intra-class gathering, and imperfect alignment could be
more beneficial as it enlarges the inter-class distance. (2) We establish the
relationship between downstream performance, contrastive learning loss, and
data augmentation. Further explains why stronger augmentation helps, then we
analyze the result from information theory and graph spectrum theory to guide
algorithm design. (3) Based on the proposed theoretical results, we provide
specific algorithms that verify the correctness of the theory. We also show
that these algorithms can be extended to various contrastive learning methods
to enhance their performance. (4) Extensive experiments are conducted on
different contrastive learning algorithms and datasets using our proposed
methods to demonstrate its effectiveness.

##  2 augmentation and generalization

###  2.1 Preliminaries

A graph can be represented as ${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}})$,
where ${\mathcal{V}}$ is the set of $N$ nodes and
${\mathcal{E}}\subseteq{\mathcal{V}}\times{\mathcal{V}}$ is the edge set. The
feature matrix and the adjacency matrix are denoted as
${\bm{X}}\in\mathbb{R}^{N\times F}$and ${\bm{A}}\in\\{0,1\\}^{N\times N}$,
where $F$ is the dimension of input feature, ${\bm{x}}_{i}\in\mathbb{R}^{F}$
is the feature of node $v_{i}$ and ${\bm{A}}_{i,j}=1$ iff
$(v_{i},v_{j})\in{\mathcal{E}}$. The node degree matrix
${\bm{D}}=\mathrm{diag}(d_{1},d_{2},...,d_{N})$, where $d_{i}$ is the degree
of node $v_{i}$.

In contrastive learning, data augmentation is used to create new graphs
${\mathcal{G}}^{1},{\mathcal{G}}^{2}\in{\mathbb{G}}^{\text{aug}}$, and the
corresponding nodes, edges, and adjacency matrices are denoted as
${\mathcal{V}}^{1},{\mathcal{E}}^{1},{\bm{A}}^{1},{\mathcal{V}}^{2},{\mathcal{E}}^{2},{\bm{A}}^{2}$.
In the following of the paper, $v$ is used to represent all nodes including
the original nodes and the augmented nodes; $v_{i}^{+}$ is used to represent
the augmented nodes including both $v_{i}^{1}$ and $v_{i}^{2}$; $v_{i}^{0}$
represents the original nodes only.

Nodes augmented from the same one, such as $(v_{i}^{1},v_{i}^{2})$, are
considered as positive pairs, while others are considered as negative pairs.
It is worth noting that a negative pair could come from the same graph, for
node $v_{i}^{1}$, its negative pair could be $v_{i}^{-}\in\\{v_{j}^{+}|j\neq
i\\}$. Graph Contrastive Learning (GCL) is a method to learn an encoder that
draws the embeddings of positive pairs similar and makes negative ones
dissimilar (Chen et al., 2020a; Wang & Isola, 2020). The encoder calculates
the embedding of node $v_{i}$ by $f({\bm{X}},{\bm{A}})[i]$, which can be
summarized as $f(v_{i})$ for better comprehension, we assume that
$||f(v_{i})||=1$. The commonly used InfoNCE loss (Zhu et al., 2020) can be
formulated as follows:

${\mathcal{L}}_{\mathrm{NCE}}=\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}\mathbb{E}_{\\{p(v_{i}^{-})\\}}\left[-\log\frac{\exp(f(v_{i}^{1})^{T}f(v_{i}^{2}))}{\sum_{i=1}^{M}\exp(f(v_{i}^{1})^{T}f(v_{i}^{-}))}\right].$
(1)

We use two augmented views to perform GCL (Zhu et al., 2020; Chen et al.,
2020a). However, $v_{i}^{1}$ could be replaced by $v_{i}^{0}$ (Liu et al.,
2022; He et al., 2020a), as $v_{i}^{0}$ is a special case of $v_{i}^{1}$ where
the augmentation happen to change nothing about the original view.

###  2.2 how augmentation infect downstream performance

Previous work (Wang & Isola, 2020) proposes that effective contrastive
learning should satisfy alignment and uniformity, meaning that positive
samples should have similar embeddings, i.e., $f(v_{i}^{1})\approx
f(v_{i}^{2})$, and features should be uniformly distributed in the unit
hypersphere. However, Wang et al. (2022b) pointed out that when
$\\{f(v_{i}^{0})\\}_{i=1}^{N}$ are uniformly distributed and
$f(v_{i}^{0})=f(v_{i}^{+})$, there is a chance that the model may converge to
a trivial solution that only projects very similar features to the same
embedding, and projects other features randomly, then it will perform random
classification in downstream tasks although it achieves perfect alignment and
uniformity.

Wang et al. (2022b) argues that perfect alignment and intra-class augmentation
overlap would be the best solution. If two intra-class samples have
augmentation overlap, then the best solution is projecting the two samples and
their augmentation to the same embedding. For example, if two different nodes
$v_{i}^{0}$, $v_{j}^{0}$ get the same augmentation $v^{+}$, then the best
solution to contrative learning is $f(v_{i}^{0})=f(v^{+})=f(v_{j}^{0})$. So
perfect alignment and augmentation overlap could project all intra-class nodes
to the same embedding, and project inter-class nodes differently because of
limited inter-class overlap.

However, a stronger augmentation would connect more intra-class nodes by
overlap, but will inevitably make achieving perfect alignment more
challenging. Conversely a weaker augmentation would help alignment but
augmentation overlap would be rare. Therefore, it is difficult to achieve both
optimal augmentation and perfect alignment. And Saunshi et al. (2022) proposes
that augmentation overlap is actually rare in practice, even with quite strong
augmentation. So the better performance may not be brought by perfect
alignment and overlap, in order to further study how exactly augmentation
helps contrastive learning, we evaluate how the downstream performance changes
while the augmentation being stronger.

To begin with, we give an assumption on the label consistency between positive
samples, which means the class label does not change after augmentation.

######  Assumption 2.1 (View Invariance).

For node $v_{i}^{0}$, the corresponding augmentation nodes $v_{i}^{+}$ get
consistent labels: $p(y|v_{i}^{0})=p(y|v_{i}^{+})$. Also the encoder should
learn similar embeddings
$\mathbb{E}_{p(v_{i}^{0},v_{i}^{+})}||f(v_{i}^{0})-f(v_{i}^{+})||^{2}\leq\delta_{aug}^{2}$.

This assumption is widely adopted (Arora et al., 2019; Wang et al., 2022b;
Saunshi et al., 2022) and reasonable. If the augmentation still keeps the
basic structure and most of feature information is kept, the class label would
not likely to change. Else if the augmentation destroys basic label
information, the model tends to learn a trivial solution, so it is meaningless
and we do not discuss the situation.

As $\delta_{aug}$ is largely decided by the augmentation when the model and
dataset are given, we need to clarify the relationship between $\delta_{aug}$
and augmentation. First, we use graph edit distance (GED) to denote the
magnitude of augmentation, Trivedi et al. (2022) proposes that all allowable
augmentations can be expressed using GED which is defined as minimum cost of
graph edition (node insertion, node deletion, edge deletion, feature
transformation) transforming graph ${\mathcal{G}}^{0}$ to ${\mathcal{G}}^{+}$.
So a stronger augmentation could be defined as augmentation with a larger GED.

######  Assumption 2.2 (Positive Pair difference and Augmentation).

While Assumption 2.1 holds i.e., $p(y|v_{i}^{0})=p(y|v_{i}^{+})$, as the
augmentation getting stronger, positive pair difference $\delta_{aug}$ will
increase, i.e.,
$\delta_{aug}\propto\mathrm{GED}({\mathcal{G}}^{0},{\mathcal{G}}^{+})$.
$\mathrm{GED}({\mathcal{G}}^{0},{\mathcal{G}}^{+})$ indicates the graph edit
distance between ${\mathcal{G}}^{0}$ and ${\mathcal{G}}^{+}$.

This is a natural assumption that is likely to hold because input with a
bigger difference will lead to a bigger difference in output when the model is
correctly trained, which is guaranteed by $p(y|v_{i}^{0})=p(y|v_{i}^{+})$.
With the assumptions, we can get the theorem below:

######  Theorem 2.3 (Augmentation and Classification).

If Assumption 2.1 holds, we know that:

$\displaystyle\mathbb{E}_{p(v,y)}f(v_{y}^{0})^{T}\mu_{y}$ $\displaystyle\geq
1-\frac{1}{3}\delta_{aug}^{2}-\frac{2}{3}\delta_{aug}\delta_{y^{+}}-\frac{1}{2}\delta_{y^{+}}^{2},$
(2) $\displaystyle\mathbb{E}_{p(v,y,y^{-})}f(v_{y}^{0})^{T}\mu_{y^{-}}$
$\displaystyle\geq
1-\frac{1}{3}\delta_{aug}^{2}-\frac{2}{3}\delta_{aug}\delta_{y^{-}}-\frac{1}{2}\delta_{y^{-}}^{2},$
(3)

where $\mu_{y}=\mathbb{E}_{p(v,y)}\left[f(v)\right]$,
$\delta_{y^{+}}^{2}=\mathbb{E}_{p(y,i,j)}||f(v^{0}_{y,i})-f(v^{0}_{y,j})||^{2}$
and
$\delta_{y^{-}}^{2}=\mathbb{E}_{p(y,y-,i,j)}||f(v^{0}_{y,i})-f(v^{0}_{y^{-},j})||^{2}$,
$y^{-}$ stands for a class different from $y$.

Figure 1: PCS means positive center similarity ($f(v_{y})^{T}\mu_{y}$), NCS
means negative center similarity ($f(v_{y})^{T}\mu_{y^{-}}$) and accuracy is
the downstream performance. X-axis stands for dropout rate of both edge and
feature, and the y-axis stands for the normalized values.

The proof can be found in Appendix A.1. This shows that the similarity between
a node and the center could be roughly represented by the positive pair
difference $\delta_{aug}$ and the inter-class/intra-class divergence
$\delta_{y^{-}}$, $\delta_{y^{+}}$. We then use positive and negative center
similarity to represent $\mathbb{E}_{p(v,y)}f(v_{y}^{0})^{T}\mu_{y}$ and
$\mathbb{E}_{p(v,y,y^{-})}f(v_{y}^{0})^{T}\mu_{y^{-}}$, respectively. Note
that we calculate the class center $\mu_{y}$ by averaging nodes from both
original view and augmented views, as the class label of nodes after
augmentation remains unchanged, our class center should be more precise as
more nodes are included.

As we assumed in Assumption 2.2, when the augmentation becomes stronger,
positive pair difference i.e., $\delta_{aug}$ would increase, and based on
previous researches (Zhu et al., 2020; You et al., 2020; Veličković et al.,
2018), the express power of the model would also be enhanced initially,
causing intra-class divergence $\delta_{y^{+}}$ decreasing and inter-class
divergence $\delta_{y^{-}}$ increasing. Therefore, from Inequality (2) we can
conclude that when we perform a stronger augmentation, initially, the
similarity between node $v_{y}$ and its center $\mu_{y}$ is hard to predict as
$\delta_{aug}$ increases and $\delta_{y^{+}}$ decreases. However, the right
hand side of Inequality (3) should decrease gradually as both $\delta_{aug}$
and $\delta_{y^{-}}$ increase, so the negative center similarity would more
likely to be lower.

The experiment shown in Figure 1 confirms our suspicion. We use dropout on
edges and features to perform augmentation, and the dropout rate naturally
represents the magnitude of augmentation i.e., graph edit distance. Initially,
as the dropout rate increases, positive center similarity may decrease
sometimes, but downstream performance could be enhanced as negative center
similarity decreases much faster. Therefore contrastive learning mainly
contributes to downstream tasks by separating nodes of different classes
rather than gathering nodes of the same class, and perfect alignment may not
help as it hinders class separating.

Also we can observe from Figure 1 that when we drop too much edges/features,
downstream performance decreases sharply, and both positive and negative
center similarity increases as too much information is lost and the basic
assumption $p(y|v_{i}^{0})=p(y|v_{i}^{+})$ does not hold, then a trivial
solution is learned.

###  2.3 augmentation and generalization

Although GCL with a stronger augmentation may help to improve downstream
performance, why it works stays unclear. We need to figure out the
relationship between positive pair difference, contrastive loss and downstream
performance to further guide algorithm design. We first define the mean cross-
entropy (CE) loss below, and use it to represent downstream performance.

######  Definition 2.4 (Mean CE loss).

For an encoder $f$ and downstream labels $y\in\left[1,K\right]$, we use the
mean $\mathrm{CE}$ loss
$\hat{{\mathcal{L}}}_{\mathrm{CE}}=\mathbb{E}_{p(v^{0},y)}\left[-\log\frac{\exp(f(v^{0})^{T}\mu_{y})}{\sum_{j=1}^{K}\exp(f(v^{0})^{T}\mu_{j})}\right]$
to evaluate downstream performance, where
$\mu_{j}=\mathbb{E}_{p(v|y=j)}\left[f(v)\right]$.

It is easy to see that mean CE loss could indicate downstream performance as
it requires nodes similar to their respective class center, and different from
others class centers. Also it is an upper bound of CE loss
${\mathcal{L}}_{\mathrm{CE}}=\mathbb{E}_{(v^{0},y)}\left[-\log\frac{\exp(f(v^{0})^{T}\omega_{y}}{\sum_{i=1}^{K}\exp(f(v^{0})^{T}\omega_{y_{i}})}\right]$,
Arora et al. (2019) showed that the mean classifier could achieve comparable
performance to learned weights, so we analyze the mean CE loss instead of the
CE loss in this paper. Similar to Theorem 2.3, we calculate the class center
using both original and augmented view nodes, instead of using only the
original view nodes (Arora et al., 2019; Wang et al., 2022b).

######  Theorem 2.5 (Generalization and Positive Pair Difference).

If Assumption 2.1 holds, and $\mathrm{ReLU}$ is applied as activation, then
the relationship between downstream performance and $\mathrm{InfoNCE}$ loss
could be represented as:

$\begin{split}\hat{{\mathcal{L}}}_{\mathrm{CE}}&\geq{\mathcal{L}}_{\mathrm{NCE}}-3\delta_{aug}^{2}-2\delta_{aug}-\log\frac{M}{K}-\frac{1}{2}\operatorname*{Var}(f(v^{+})|y)\\\
&\hskip
15.00002pt-\sqrt{\operatorname*{Var}(f(v^{0})|y)}-e\operatorname*{Var}(\mu_{y})-O(M^{-\frac{1}{2}}),\end{split}$

where $M$ is number of negative samples111the generalization are correlated
with $-\log M-O(M^{-\frac{1}{2}})$, which is decreasing when $M$ increases and
$M$ is large, so the theorem encourages large negative samples., $K$ is number
of classes,
$\operatorname*{Var}(f(v^{0})|y)=\mathbb{E}_{p(y)}\mathbb{E}_{p(v^{0}|y)}||f(v^{0})-\mathbb{E}_{p(v|y)}f(v)||^{2}$
and
$\operatorname*{Var}(f(v^{+})|y)=\mathbb{E}_{p(y)}\mathbb{E}_{p(v^{+}|y)}||f(v^{+})-\mathbb{E}_{p(v|y)}f(v)||^{2}$
both mean intra-class variance, and
$\operatorname*{Var}(\mu_{y})=\mathbb{E}_{p(y)}||\mathbb{E}_{p(v|y)}f(v)-\mathbb{E}_{p(v)}f(v)||^{2}$
represents the variance of $K$ class centers.

The proof can be found in Appendix A.2. Theorem 2.5 suggests a gap between
$\hat{{\mathcal{L}}}_{\mathrm{CE}}$ and ${\mathcal{L}}_{\mathrm{NCE}}$,
meaning that the encoders that minimize ${\mathcal{L}}_{\mathrm{NCE}}$ may not
yield optimal performance on downstream tasks. Furthermore, it suggests that a
higher positive pair difference $\delta_{aug}$ and
$\operatorname*{Var}(f(v)|y)$ would enhance generalization and potentially
improve performance on downstream tasks. Also Inequality (2) also demonstrates
that $f(v_{y})^{T}\mu_{y}\propto\left[-\operatorname*{Var}(f(v)|y)\right]$ and
$f(v_{y})^{T}\mu_{y}\propto\left[-\delta_{aug}\right]$. So better
generalization correlates with worse positive center similarity. This aligns
with the findings before that better downstream performance may come with a
lower positive center similarity.

Theorem 2.5 explains why as the augmentation becomes stronger, negative center
similarity decreases, while positive center similarity remains unpredictable.
The InfoNCE loss ${\mathcal{L}}_{\mathrm{NCE}}$ can be written as
${\mathcal{L}}_{\mathrm{NCE}}=\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}\mathbb{E}_{p({v_{i}^{-}})}\left[-\log\frac{\exp(f(v_{i}^{1})^{T}f(v_{i}^{2}))}{\sum_{\\{v^{-}_{i}\\}}\exp(f(v_{i}^{1})^{T}f(v^{-}_{i}))}\right]$,
and the numerator $f(v_{i}^{1})^{T}f(v_{i}^{2})\propto
1-\mathbb{E}_{p(v_{i})}||f(v_{i}^{1})-f(v_{i}^{2})||\propto
1-\mathbb{E}_{p(v_{i})}||f(v_{i}^{0})-f(v_{i}^{+})||\propto 1-\delta_{aug}$.
This implies that a higher $\delta_{aug}$ caused by stronger augmentation
tends to make the numerator harder to maximize. So GCL would pay more
attention to the minimize the denominator just as shown in Figure 5. And
minimizing the denominator is actually separating negative samples which is
mainly performing inter-class separating as most negative samples are from the
different classes. Thus inter-class separating is enhanced. In contrast,
intra-class gathering is weakened due to the existence of same-class samples
in the negative set, while the worse alignment performance and better
augmentation overlap can hardly help (Wang et al., 2022b; Saunshi et al.,
2022). As a result intra-class nodes may not gather closer.

Theorem 2.5 also highlights the significance of augmentation magnitude in
graph contrastive learning algorithms like GRACE (Zhu et al., 2020). A weak
augmentation leads to better alignment but also a weak generalization, InfoNCE
loss might be relatively low but downstream performance could be terrible
(Saunshi et al., 2022). When augmentation gets stronger, although perfect
alignment cannot be achieved, it promotes better generalization and
potentially leads to improved downstream performance. And when the
augmentation is too strong, minimizing the InfoNCE loss becomes challenging
(Li et al., 2022), leading to poorer downstream performance.

Therefore, it is crucial to determine the magnitude of augmentation and how to
perform augmentation as it directly affects contrastive performance and
generalization.

##  3 Finding better augmentation

Previous sections have revealed that perfect alignment, which minimizes the
positive pair difference $\delta_{aug}$ to $0$ may not help downstream
performance. Instead a stronger augmentation that leads to larger
$\delta_{aug}$ will benefit generalization while weakening contrastive
learning process. Therefore, we need to find out how to perform augmentation
to strike a better balance between positive pair difference and contrastive
loss, leading to better downstream performance.

###  3.1 information theory perspective

As shown by Oord et al. (2018), ${\mathcal{L}}_{\mathrm{NCE}}$ is actually a
lower bound of mutual information. Additionally,
$\operatorname*{Var}(f(v^{0})|y)$, $\operatorname*{Var}(f(v^{+}|y))$ and
$\operatorname*{Var}(\mu_{y})$ can be represented by inherent properties of
the graph and the positive pair difference $\delta_{aug}$. Thus, Theorem 2.5
could be reformulated as follows:

######  Corollary 3.1 (CE with Mutual Information).

If Assumption 2.1 holds, the relationship between downstream performance,
mutual information between views and positive pair difference could be
represented as:

$\hat{{\mathcal{L}}}_{\mathrm{CE}}\geq\log(K)-I(f(v^{1}),f(v^{2}))-g(\delta_{aug})-O(M^{-\frac{1}{2}}),$
(4)

where $I(f(v^{1}),f(v^{2}))$ stands for the mutual information between
$f(v^{1})$ and $f(v^{2})$, $g(\delta_{aug})$ is monotonically increasing, and
is defined in Appendix A.3.

The proof can be found in Appendix A.3. Corollary 3.1 suggests that the best
augmentation would be one that maximize the mutual information and positive
pair difference. To verify this, we propose a simple but effective method. We
recognize important nodes, features and edges, then leave them unchanged
during augmentation to increase mutual information. Then for those unimportant
ones, we should perform stronger augmentation to increase the positive pair
difference.

Similar to Wei et al. (2023), we utilize gradients to identify which feature
of node $v$ is relatively important and carries more information. We calculate
the importance of feature by averaging the feature importance across all
nodes, the importance of node $v$ could be calculated by simply averaging the
importance of its features, and then use the average of the two endpoints to
represent the importance of an edge:

$\begin{split}&\alpha_{v,p}=\frac{\partial{\mathcal{L}}_{\mathrm{NCE}}}{\partial
x_{v,p}},\quad\alpha_{p}=\mathrm{ReLU}\left(\frac{1}{|V^{\prime}|}\sum_{v}\alpha_{v,p}\right),\\\
&\alpha_{v}=\mathrm{ReLU}\left(\frac{1}{|P^{\prime}|}\sum_{p}\alpha_{v,p}\right),\quad\alpha_{e_{i,j}}=\left(\alpha_{v_{i}}+\alpha_{v_{j}}\right)/2,\end{split}$

where $\alpha_{v,p}$ means importance of the $p^{th}$ feature of node $v$,
$\alpha_{p}$ means the importance of $p^{th}$ feature, $\alpha_{v}$ means
importance of node $v$, and $\alpha_{e_{i,j}}$ means the importance of edge
$(v_{i},v_{j})$.

For those edges/features with high importance, we should keep them steady and
do no modification during augmentation. For those with relatively low
importance, we can freely mask those edges/features, but we should make sure
that the number of masked edges/features is greater than the number of kept
ones to prevent $\delta_{aug}$ from decreasing. The process can be described
by the following equation:

$\tilde{{\bm{A}}}={\bm{A}}\ast({\bm{M}}_{e}\vee{\bm{S}}_{e}\wedge{\bm{D}}_{e}),\quad\tilde{{\bm{F}}}={\bm{F}}\ast({\bm{M}}_{f}\vee{\bm{S}}_{f}\wedge{\bm{D}}_{f}),$

where $\ast$ is hadamard product, $\vee$ stands for logical OR, $\wedge$
stands for logical AND. ${\bm{M}}_{e}$, ${\bm{M}}_{f}$ represent the random
mask matrix, which could be generated using any mask method, ${\bm{S}}_{e}$,
${\bm{S}}_{f}$ are the importance based retain matrix, it tells which
edge/feature is of high importance and should be retained. For the top $\xi$
important edges/features, we set ${\bm{S}}_{e}$, ${\bm{S}}_{f}$ to $1$ with a
probability of 50% and to $0$ otherwise. ${\bm{D}}_{e}$, ${\bm{D}}_{f}$ show
those edges/features should be deleted to increase $\delta_{aug}$, for the
least 2$\xi$ important edges/features, we also set ${\bm{D}}_{e}$,
${\bm{D}}_{f}$ to $0$ with a probability of 50% and to $1$ otherwise. It is
worth noting that $\delta_{aug}$ is defined as
$\mathbb{E}_{p(v_{i}^{0},v_{i}^{+})}||f(v_{i}^{+})-f(v_{i}^{0})||$ rather than
$\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}||f(v_{i}^{1})-f(v_{i}^{2})||$, therefore,
we applied this deletion on both views.

This is a simple method, and the way to measure importance can be replaced by
any other methods. It can be easily integrated into any other graph
contrastive learning methods that require edge/feature augmentation. There are
many details that could be optimized, such as how to choose which
edges/features to delete and the number of deletions. However, since this
algorithm is primarily intended for theoretical verification, we just randomly
select edges to be deleted and set the number to twice the number of edges
kept.

In fact, most graph contrastive learning methods follow a similar framework to
maximize mutual information and implicitly increase positive pair difference
as discussed in Appendix B.1.

###  3.2 graph spectrum perspective

In this section, we attempt to analyze InfoNCE loss and positive pair
difference from graph spectrum perspective. We start by representing them
using the spectrum of the adjacency matrix ${\bm{A}}$.

######  Theorem 3.2 (Theorem 1 of Liu et al. (2022) Restated).

Given adjacency martix ${\bm{A}}$ and the generated augmentation
${\bm{A}}^{\prime},{\bm{A}}^{\prime\prime}$, the $i^{th}$ eigenvalues of
${\bm{A}}^{\prime}$ and ${\bm{A}}^{\prime\prime}$ are
$\lambda_{i}^{\prime},\lambda_{i}^{\prime\prime}$, respectively. The following
upper bound is established:

$\begin{split}{\mathcal{L}}_{\mathrm{NCE}}&\geq N\log
N-(N+1)\sum_{i}\theta_{i}\lambda_{i}^{\prime}\lambda_{i}^{\prime\prime},\\\
\end{split}$ (5)

where $\theta_{i}$ is the adaptive weight of the $i^{th}$ term, the detail of
$\theta_{i}$ is discussed in $\mathrm{Appendix}$ C.4.

######  Corollary 3.3 (Spectral Representation of $\delta_{aug}$).

If Assumption 2.1 holds, and $\lambda_{i}^{\prime},\lambda_{i}^{\prime\prime}$
are $i^{th}$ eigenvalues of ${\bm{A}}^{\prime}$ and ${\bm{A}}^{\prime\prime}$,
respectively, then:

$2\delta_{aug}\geq\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}||f(v_{i}^{1})-f(v_{i}^{2})||\geq\sqrt{2-\frac{2}{N}\sum_{i}\theta_{i}\lambda_{i}^{\prime}\lambda_{i}^{\prime\prime}}.$
(6)

Theorem 2.5 suggests that we should strive to make
${\mathcal{L}}_{\mathrm{NCE}}$ small while increase $\delta_{aug}$, but they
are kindly mutually exclusive. As shown in Theorem 3.2, and Corallary 3.3
proved in Appendix A.4, when $\theta_{i}$ is positive, a small
${\mathcal{L}}_{\mathrm{NCE}}$ requires for large $|\lambda_{i}|$ while a
large $\delta_{aug}$ requires for small $|\lambda_{i}|$, and it works
exclusively too when $\theta_{i}$ is negative. As contrastive learning is
trained to minimize ${\mathcal{L}}_{\mathrm{NCE}}$, $\theta$s are going to
increase as the training goes, so we can assume that $\theta$s will be
positive, the detailed discussion and exact definition of $\theta$ can be
found in Appendix C.4. Since $\theta$s are trained parameters that we have
limited control over, we turn to adjusting $\lambda$s through data
augmentation. Therefore, to achieve a better trade-off, we should decrease
$|\lambda_{i}|$ while keep InfoNCE loss also decreasing.

In fact, reducing $|\lambda_{i}|$ actually reduces the positive $\lambda_{i}$
and increases the negative $\lambda_{i}$, which is trying to smoothen the
graph spectrum and narrow the gap between the spectrum. As suggested by Yang
et al. (2022), graph convolution operation with an unsmooth spectrum results
in signals correlated to the eigenvectors corresponding to larger magnitude
eigenvalues and orthogonal to the eigenvectors corresponding to smaller
magnitude eigenvalues. So if $|\lambda_{i}|\gg|\lambda_{j}|$, then
$\mathrm{sim}(f(v),e_{i})\gg\mathrm{sim}(f(v),e_{j})$, where $e_{i}$ denotes
the eigenvector corresponding to $\lambda_{i}$, causing all representations
similar to $e_{i}$. Therefore, an unsmooth spectrum may lead to similar
representations. This can also be observed from Inequality (6), where a higher
$|\lambda_{i}|$ will reduce the positive pair difference, making
$f(v_{i}^{1})$ and $f(v_{i}^{2})$ more similar.

We now know that smoothing the graph spectrum can help with graph contrastive
learning. The question is how to appropriately smooth the spectrum. We propose
a simple method. As the training aims to minimize
${\mathcal{L}}_{\mathrm{NCE}}$, the parameter $\theta_{i}$s are supposed to
increase. Therefore, we can use $\theta_{i}$ as a symbol to show whether the
model is correctly trained. When $\theta_{i}$ gradually increases, we can
decrease $\lambda$ as needed. However, when $\theta_{i}$ starts to decrease,
it is likely that the change on the spectrum is too drastic, and we should
take a step back. The process could be described as follows:

$\lambda_{i}=\lambda_{i}+\mathrm{direction}_{i}*\lambda_{i}*\alpha,\quad\mathrm{direction}_{i}=\begin{cases}-1,&\text{$\mathrm{cur}(\theta_{i})-\mathrm{pre}(\theta_{i})\geq\epsilon$}\\\
1,&\text{$\mathrm{cur}(\theta_{i})-\mathrm{pre}(\theta_{i})\leq-\epsilon$},\\\
0,&\text{otherwise}\end{cases}$

where $\alpha$ is a hyperparameter that determines how much we should
decrease/increase $\lambda_{i}$. $\epsilon$ is used to determine whether
$\theta_{i}$ is increasing, decreasing, or just staying steady.
$\mathrm{cur}(\theta_{i})$ and $\mathrm{pre}(\theta_{i})$ represents the
current and previous $\theta_{i}$ respectively.

In this way, the contrastive training will increase $\theta_{i}$ and result in
a lower ${\mathcal{L}}_{\mathrm{NCE}}$, while we justify $\lambda_{i}$ to
achieve a better positive pair difference, which promises a better
generalization ability. However, just like Section 3.1, the method is quite
simple, in fact this method is more a data preprocessing rather than
augmentation, but it is capable of verifying the theory and guide algorithm
design, as we decrease $\lambda^{\prime}$ by directly decreasing $\lambda$,
but it could also be achieved by augmentation methods.

Also some spectral augmentations implicitly decreases $|\lambda|$s as shown in
Appendix B.2.

##  4 experiments

In this section, we mainly evaluate the performance of the methods we proposed
on six datasets: Cora, CiteSeer, PubMed, DBLP, Amazon-Photo and Amazon-
Computer. We select 3 contrastive learning GNN, GRACE (Zhu et al., 2020), GCA
(Zhu et al., 2021), AD-GCL (Suresh et al., 2021), and integrate those models
with our proposed methods to verify its applicability and correctness of the
theory. Details of datasets and baselines are in Appendix C.1. The results are
summarized in Table 1. We further investigate the positive/negative center
similarity in Appendix C.6, the hyperparameter sensitivity is studied in
Appendix C.7, and the change of $\theta$ and the spectrum while training is
shown in Appendix C.5.

Table 1: Quantitative results on node classification, algorithm+I stands for
the algorithm with information augmentation, and algorithm+S stands for the
algirithm with spectrum augmentation

Datasets | Cora | CiteSeer | PubMed | DBLP | Amazon-P | Amazon-C
---|---|---|---|---|---|---
Mi-Fi | Ma-Fi | Mi-Fi | Ma-Fi | Mi-Fi | Ma-Fi | Mi-Fi | Ma-Fi | Mi-Fi | Ma-Fi | Mi-Fi | Ma-Fi
GCN | 83.31 | 81.97 | 69.81 | 66.44 | 85.36 | 84.88 | 81.26 | 75.40 | 93.28 | 91.78 | 88.11 | 81.57
GAT | 83.83 | 82.45 | 70.31 | 66.76 | 84.04 | 83.43 | 81.92 | 75.87 | 93.17 | 91.84 | 86.82 | 78.37
GRACE | 82.52 | 81.23 | 68.44 | 63.73 | 84.97 | 84.51 | 84.01 | 79.63 | 91.17 | 89.09 | 86.36 | 84.15
GRACE+I | 83.33 | 82.23 | 70.47 | 64.83 | 84.99 | 84.57 | 84.39 | 80.24 | 91.13 | 89.11 | 86.61 | 84.77
GRACE+S | 83.25 | 81.85 | 69.87 | 64.92 | 85.03 | 84.62 | 84.47 | 80.33 | 91.91 | 90.09 | 86.61 | 84.66
GCA | 83.74 | 82.28 | 71.09 | 66.43 | 85.38 | 85.07 | 83.99 | 79.82 | 91.67 | 90.21 | 86.77 | 85.18
GCA+I | 84.71 | 83.42 | 71.24 | 67.23 | 85.38 | 84.89 | 84.29 | 79.91 | 91.94 | 90.40 | 86.60 | 84.12
GCA+S | 83.51 | 82.30 | 70.95 | 65.31 | 85.28 | 84.98 | 84.49 | 80.28 | 92.02 | 90.36 | 86.97 | 85.30
AD GCL | 81.68 | 79.83 | 70.01 | 64.17 | 84.77 | 84.29 | 83.14 | 78.86 | 91.34 | 89.28 | 84.80 | 82.04
AD GCL+I | 83.06 | 81.20 | 71.06 | 64.69 | 85.52 | 85.00 | 83.51 | 79.05 | 91.91 | 90.24 | 86.02 | 84.12
AD GCL+S | 82.96 | 81.39 | 71.35 | 63.88 | 85.08 | 84.60 | 83.45 | 79.13 | 91.79 | 89.94 | 85.49 | 82.52

From Table 1, we can observe that GRACE+I (GRACE with information
augmentation) and GRACE+S (GRACE with spectrum augmentation) both improve the
downstream performance. This improvement is significant for GRACE since it
primarily performs random dropout, resulting in the loss of valuable
information. But for GCA, the information augmentation only brings minor
improvements. This is because GCA already drops the unimportant ones with a
higher probability, allowing it to capture sufficient information, especially
on large graphs. AD-GCL aggressively drops as much information as possible to
eliminate irrelevant information while some important ones are also dropped,
so the information augmentation helps greatly. Overall, our methods improve
the performance of original algorithm and helps downstream tasks.

###  4.1 positive pair difference

Figure 2: Positive pair difference and InfoNCE, GRACE+I stands for GRACE with
information augmentation, and GRACE+S stands for GRACE with spectrum
augmentation. GRACE+x$\\_$MI means mutual information between two views after
training, and GRACE+x$\\_\delta_{aug}$ is positive pair difference caused by
the method.

Figure 2 demonstrates that for all three algorithms, our methods maintain
similar mutual information while achieving a larger positive pair difference.
This indicates that we preserve the contrastive loss while enhancing its
generalization, resulting in improved downstream performance. Similar to the
result of Table 1, the improvement of $\delta_{aug}$ on GRACE and AD-GCL are
much sharper because GCA has already tried to increase positive pair
difference and achieve a balance with the InfoNCE loss as discussed in
Appendix B.1.

###  4.2 over-smooth

Figure 3: Accuracy on downstream tasks with different number of layers. GRACE
is the original algorithm (Zhu et al., 2020), and GRACE+S stands for GRACE
with spectrum augmentation.

While reducing $|\lambda_{i}|$, we obtain a graph with smoother spectrum, and
could relieve the over-smooth. This, in turn, enables the application of
relatively more complex models. We can verify this by simply stacking more
layers. As shown in Figure 3, if applied spectrum augmentation, the model
tends to outperform the original algorithm especially with more layer, and the
best performance may come with a larger number of layers, which indicates that
more complicated models could be applied and our method successfully relieve
over-smooth.

##  5 Conclusion

In this paper, we investigate the impact of contrastive learning on downstream
tasks and propose that perfect alignment does not necessarily lead to improved
performance. Instead, we find that a relatively large positive pair difference
is more beneficial for generalization. Building upon this insight, we
introduce two simple yet effective methods to strike a balance between the
contrastive loss and positive pair difference.

Limitations and future work. In our work, we focus on manipulating positive
pair difference through augmentation. However, the model architecture and loss
function can also have a significant impact. And when performing spectrum
augmentation, large matrix multiplications are needed. It would be more
efficient if the augmentation could be represented by simple edge
perturbations.

## References

  * Arora et al. (2019) Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi.  A theoretical analysis of contrastive unsupervised representation learning.  _arXiv preprint arXiv:1902.09229_ , 2019.
  * Ash et al. (2021) Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra.  Investigating the role of negatives in contrastive representation learning.  _arXiv preprint arXiv:2106.09943_ , 2021.
  * Bojchevski & Günnemann (2017) Aleksandar Bojchevski and Stephan Günnemann.  Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking.  _arXiv preprint arXiv:1707.03815_ , 2017.
  * Budimir et al. (2000) Ivan Budimir, Sever S Dragomir, and Josep Pecaric.  Further reverse results for jensen’s discrete inequality and applications in information theory.  _RGMIA research report collection_ , 3(1), 2000.
  * Chen et al. (2020a) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In _International conference on machine learning_ , pp. 1597–1607. PMLR, 2020a.
  * Chen et al. (2020b) Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton.  Big self-supervised models are strong semi-supervised learners.  _Advances in neural information processing systems_ , 33:22243–22255, 2020b.
  * Gilmer et al. (2017) Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl.  Neural message passing for quantum chemistry.  In Doina Precup and Yee Whye Teh (eds.), _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pp. 1263–1272. PMLR, 06–11 Aug 2017.
  * Hassani & Khasahmadi (2020) Kaveh Hassani and Amir Hosein Khasahmadi.  Contrastive multi-view representation learning on graphs.  In _International conference on machine learning_ , pp. 4116–4126. PMLR, 2020.
  * He et al. (2020a) Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 9729–9738, 2020a.
  * He et al. (2020b) Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang.  Lightgcn: Simplifying and powering graph convolution network for recommendation.  In _Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval_ , pp. 639–648, 2020b.
  * Huang et al. (2021) Weiran Huang, Mingyang Yi, and Xuyang Zhao.  Towards the generalization of contrastive self-supervised learning.  _arXiv preprint arXiv:2111.00743_ , 2021.
  * Jiang et al. (2019) Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo.  Semi-supervised learning with graph learning-convolutional networks.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 11313–11320, 2019.
  * Kumar et al. (2023) Teerath Kumar, Muhammad Turab, Kislay Raj, Alessandra Mileo, Rob Brennan, and Malika Bendechache.  Advanced data augmentation approaches: A comprehensive survey and future directions.  _arXiv preprint arXiv:2301.02830_ , 2023.
  * Lee et al. (2021) Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo.  Predicting what you already know helps: Provable self-supervised learning.  _Advances in Neural Information Processing Systems_ , 34:309–323, 2021.
  * Li et al. (2022) Sihang Li, Xiang Wang, An Zhang, Yingxin Wu, Xiangnan He, and Tat-Seng Chua.  Let invariant rationale discovery inspire graph contrastive learning.  In _International conference on machine learning_ , pp. 13052–13065. PMLR, 2022.
  * Lin et al. (2022) Lu Lin, Jinghui Chen, and Hongning Wang.  Spectral augmentation for self-supervised learning on graphs.  _arXiv preprint arXiv:2210.00643_ , 2022.
  * 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.  _Advances in Neural Information Processing Systems_ , 35:2972–2983, 2022.
  * Liu et al. (2018) Qi Liu, Miltiadis Allamanis, Marc Brockschmidt, and Alexander Gaunt.  Constrained graph variational autoencoders for molecule design.  _Advances in neural information processing systems_ , 31, 2018.
  * Oord et al. (2018) Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_ , 2018.
  * Saunshi et al. (2022) Nikunj Saunshi, Jordan Ash, Surbhi Goel, Dipendra Misra, Cyril Zhang, Sanjeev Arora, Sham Kakade, and Akshay Krishnamurthy.  Understanding contrastive learning requires incorporating inductive biases.  In _International Conference on Machine Learning_ , pp. 19250–19286. PMLR, 2022.
  * 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.
  * Shchur et al. (2018) Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann.  Pitfalls of graph neural network evaluation.  _arXiv preprint arXiv:1811.05868_ , 2018.
  * Shi & Rajkumar (2020) Weijing Shi and Raj Rajkumar.  Point-gnn: Graph neural network for 3d object detection in a point cloud.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 1711–1719, 2020.
  * Stewart (1990) Gilbert W Stewart.  Matrix perturbation theory.  1990\.
  * Suresh et al. (2021) Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville.  Adversarial graph augmentation to improve graph contrastive learning.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), _Advances in Neural Information Processing Systems_ , volume 34, pp. 15920–15933. Curran Associates, Inc., 2021.
  * Tian et al. (2020) Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola.  What makes for good views for contrastive learning?  _Advances in neural information processing systems_ , 33:6827–6839, 2020.
  * Trivedi et al. (2022) Puja Trivedi, Ekdeep Singh Lubana, and Danai Koutra.  Understanding self-supervised graph representation learning from a data-centric perspective.  2022\.
  * Veličković et al. (2018) Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm.  Deep graph infomax.  _arXiv preprint arXiv:1809.10341_ , 2018.
  * Wang et al. (2022a) Haoqing Wang, Xun Guo, Zhi-Hong Deng, and Yan Lu.  Rethinking minimal sufficient representation in contrastive learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 16041–16050, 2022a.
  * Wang & Isola (2020) Tongzhou Wang and Phillip Isola.  Understanding contrastive representation learning through alignment and uniformity on the hypersphere.  In _International Conference on Machine Learning_ , pp. 9929–9939. PMLR, 2020.
  * Wang et al. (2022b) Yifei Wang, Qi Zhang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin.  Chaos is a ladder: A new theoretical understanding of contrastive learning via augmentation overlap.  _arXiv preprint arXiv:2203.13457_ , 2022b.
  * Wei et al. (2023) Chunyu Wei, Yu Wang, Bing Bai, Kai Ni, David Brady, and Lu Fang.  Boosting graph contrastive learning via graph contrastive saliency.  In _International Conference on Machine Learning_ , pp. 36839–36855. PMLR, 2023.
  * Wu et al. (2019) Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang.  Graph wavenet for deep spatial-temporal graph modeling.  _arXiv preprint arXiv:1906.00121_ , 2019.
  * Xu et al. (2021) Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang.  Infogcl: Information-aware graph contrastive learning, 2021.
  * Yang et al. (2022) Mingqi Yang, Yanming Shen, Rui Li, Heng Qi, Qiang Zhang, and Baocai Yin.  A new perspective on the effects of spectrum in graph neural networks.  In _International Conference on Machine Learning_ , pp. 25261–25279. PMLR, 2022.
  * Yang et al. (2016) Zhilin Yang, William Cohen, and Ruslan Salakhudinov.  Revisiting semi-supervised learning with graph embeddings.  In _International conference on machine learning_ , pp. 40–48. PMLR, 2016.
  * You et al. (2020) Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen.  Graph contrastive learning with augmentations.  _Advances in neural information processing systems_ , 33:5812–5823, 2020.
  * Yuan et al. (2022) Yige Yuan, Bingbing Xu, Huawei Shen, Qi Cao, Keting Cen, Wen Zheng, and Xueqi Cheng.  Towards generalizable graph contrastive learning: An information theory perspective.  _arXiv preprint arXiv:2211.10929_ , 2022.
  * Zhao et al. (2022a) Tong Zhao, Wei Jin, Yozen Liu, Yingheng Wang, Gang Liu, Stephan Günnemann, Neil Shah, and Meng Jiang.  Graph data augmentation for graph machine learning: A survey.  _arXiv preprint arXiv:2202.08871_ , 2022a.
  * Zhao et al. (2022b) Tong Zhao, Wei Jin, Yozen Liu, Yingheng Wang, Gang Liu, Stephan Günnemann, Neil Shah, and Meng Jiang.  Graph data augmentation for graph machine learning: A survey.  _arXiv preprint arXiv:2202.08871_ , 2022b.
  * Zhu et al. (2020) Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Deep graph contrastive representation learning.  _arXiv preprint arXiv:2006.04131_ , 2020.
  * Zhu et al. (2021) Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Graph contrastive learning with adaptive augmentation.  In _Proceedings of the Web Conference 2021_ , pp. 2069–2080, 2021\.

##  Appendix A theoretical Proof

###  A.1 proof of Lemma 2.3

If we set
$\delta_{y^{+}}^{2}=\mathbb{E}_{p(y,i,j)}||f(v^{0}_{y,i})-f(v^{0}_{y,j})||^{2}$,
and
$\delta_{y^{+}}^{2}=\mathbb{E}_{p(y,y^{\prime},i,j)}||f(v^{0}_{y,i})-f(v^{0}_{y^{\prime},j})||^{2}$.
Then with Assumption 2.1 and jensen inequality, we know that
$\mathbb{E}_{p(v_{i})}||f(v_{i}^{0})-f(v_{i}^{+})||^{2}\leq\delta_{aug}^{2}$,
$\mathbb{E}_{p(v_{i})}||f(v_{i}^{0})-f(v_{i}^{+})||\leq\delta_{aug}$ and
$\mathbb{E}_{p(y,i,j)}||f(v^{0}_{y,i})-f(v^{0}_{y,j})||\leq\delta_{y^{+}}$,
$\mathbb{E}_{p(y,y^{\prime},i,j)}||f(v^{0}_{y,i})-f(v^{0}_{y^{\prime},j})||\leq\delta_{y^{-}}$.
Therefore, we can get the inequality below:

$\displaystyle\mathbb{E}_{p(v_{y,i},v_{y,j}|y)}||f(v^{+}_{y,i})-f(v^{0}_{y,j})||^{2}$
$\displaystyle\leq\mathbb{E}_{p(v_{y,i},v_{y,j}|y)}||f(v^{+}_{y,i})-f(v^{0}_{y,i})||^{2}+\mathbb{E}_{p(v_{y,i},v_{y,j}|y)}||f(v^{0}_{y,i})-f(v^{0}_{y,j})||^{2}$
$\displaystyle\hskip
15.00002pt+2\mathbb{E}_{p(v_{y,i},v_{y,j}|y)}||f(v^{+}_{y,i})-f(v^{0}_{y,j})||\cdot||f(v^{0}_{y,i})-f(v^{0}_{y,j})||$
$\displaystyle\leq\delta_{aug}^{2}+\delta_{y^{+}}^{2}+2\delta_{aug}\delta_{y^{+}}$
$\displaystyle=(\delta_{aug}+\delta_{y^{+}})^{2}.$

As
$\mu_{y}=\mathbb{E}_{p(v_{y}|y)}[f(v_{y})]=\frac{1}{3}\mathbb{E}_{p(v_{y}^{0}|y)}f(v_{y}^{0})+\frac{2}{3}\mathbb{E}_{p(v_{y}^{+}|y)}f(v_{y}^{0})$,
we know that,

$\displaystyle\mathbb{E}_{p(v_{y}^{0^{\prime}}|y)}f(v_{y}^{0^{\prime}})^{T}\mu_{y}$
$\displaystyle=\mathbb{E}_{p(v_{y}^{0^{\prime}}|y)}f(v_{y}^{0^{\prime}})^{T}(\frac{1}{3}\mathbb{E}_{p(v_{y}^{0}|y)}f(v_{y}^{0})+\frac{2}{3}\mathbb{E}_{p(v_{y}^{+}|y)}f(v_{y}^{0}))$
$\displaystyle=\frac{1}{3}\mathbb{E}_{p(v_{y}^{0^{\prime}}|y)}\mathbb{E}_{p(v_{y}^{0}|y)}f(v^{0^{\prime}}_{y})^{T}f(v_{y}^{0})+\frac{2}{3}\mathbb{E}_{p(v_{y}^{0^{\prime}}|y)}\mathbb{E}_{p(v_{y}^{+}|y)}f(v^{0^{\prime}}_{y})^{T}f(v_{y}^{+}).$

assume that $\mathbb{E}_{p(a,b)}||a-b||^{2}\leq c^{2}$, $||a||=||b||=1$, then

$\displaystyle\mathbb{E}_{p(a,b)}(a^{T}-b^{T})(a-b)\leq c^{2}$
$\displaystyle\mathbb{E}_{p(a,b)}[a^{T}a-a^{T}b-b^{T}a+b^{T}b]\leq c^{2}$
$\displaystyle\mathbb{E}_{p(a,b)}[2-2a^{T}b]\leq c^{2}$
$\displaystyle\mathbb{E}_{p(a,b)}a^{T}b\geq\frac{2-c^{2}}{2}=1-\frac{c^{2}}{2}.$

As we already know that
$\mathbb{E}_{p(y,y^{\prime},i,j)}||f(v^{0}_{y,i})-f(v^{0}_{y^{\prime},j})||^{2}\leq\delta_{y^{+}}^{2}$
and
$\mathbb{E}_{p(v_{y,i},v_{y,j}|y)}||f(v^{+}_{y,i})-f(v^{0}_{y,j})||^{2}\leq(\delta_{aug}+\delta_{y^{+}})^{2}$.
So
$\mathbb{E}_{p(v_{y}^{0^{\prime}}|y)}\mathbb{E}_{p(v_{y}^{0}|y)}f(v^{0^{\prime}}_{y})^{T}f(v_{y}^{0})\geq
1-\frac{\delta_{y^{+}}^{2}}{2}$ and
$\mathbb{E}_{p(v_{y}^{0^{\prime}}|y)}\mathbb{E}_{p(v_{y}^{+}|y)}f(v^{0^{\prime}}_{y})^{T}f(v_{y}^{+})\geq
1-\frac{(\delta_{aug}+\delta_{y^{+}})^{2}}{2}$.

Then, we can calculate
$\mathbb{E}_{p(v_{y}^{0^{\prime}}|y)}f(v_{y}^{0^{\prime}})^{T}\mu_{y}$ as
below:

$\begin{split}\mathbb{E}_{p(v_{y}^{0^{\prime}}|y)}f(v_{y}^{0^{\prime}})^{T}\mu_{y}&=\frac{1}{3}\mathbb{E}_{p(v_{y}^{0^{\prime}}|y)}\mathbb{E}_{p(v_{y}^{0}|y)}f(v^{0^{\prime}}_{y})^{T}f(v_{y}^{0})+\frac{2}{3}\mathbb{E}_{p(v_{y}^{0^{\prime}}|y)}\mathbb{E}_{p(v_{y}^{+}|y)}f(v^{0^{\prime}}_{y})^{T}f(v_{y}^{+})\\\
&\geq
1-\frac{\delta_{aug}^{2}}{3}-\frac{2\delta_{aug}\delta_{y^{+}}}{3}-\frac{\delta_{y^{+}}^{2}}{2}.\end{split}$
(7)

Similarly, we know that
$\mathbb{E}_{p(v_{y}^{0},y^{-}|y)}f(v_{y}^{0})^{T}\mu_{y^{-}}\geq
1-\frac{\delta_{aug}^{2}}{3}-\frac{2\delta_{aug}\delta_{y^{-}}}{3}-\frac{\delta_{y^{-}}^{2}}{2}$.

###  A.2 Proof of Theorem 2.5

$\hat{{\mathcal{L}}}_{\mathrm{CE}}=\underbrace{-\mathbb{E}_{p(v_{i}^{0},y)}f(v_{i}^{0})^{T}\mu_{y}}_{\Lambda_{1}}+\underbrace{\mathbb{E}_{p(v_{i}^{0})}\log\sum_{i=j}^{K}\exp(f(v_{i}^{0})^{T}\mu_{j})}_{\Lambda_{2}}.$
$\displaystyle\Lambda_{1}$
$\displaystyle=-\mathbb{E}_{p(v_{i}^{0},y)}f(v_{i}^{0})^{T}\mu_{y}$
$\displaystyle=-\mathbb{E}_{p(v_{i}^{0},y)}\left[f(v_{i}^{0})^{T}f(v_{i}^{+})+f(v_{i}^{0})^{T}(\mu_{y}-f(v_{i}^{+}))\right]$
$\displaystyle\overset{(a)}{\geq}-\mathbb{E}_{p(v_{i}^{0},v_{i}^{+},y)}f(v_{i}^{0})^{T}f(v_{i}^{+})-\mathbb{E}_{p(v_{i}^{+},y)}||f(v_{i}^{+})-\mu_{y}||$
$\displaystyle\geq-\mathbb{E}_{p(v_{i}^{0},v_{i}^{+},y)}f(v_{i}^{0})^{T}f(v_{i}^{+})-\mathbb{E}_{p(v_{i}^{0},v_{i}^{+},y)}||f(v_{y}^{+})-f(v_{y}^{0})||-\mathbb{E}_{p(v_{i}^{0},v_{i}^{+},y)}||f(v^{0}_{y})-\mu_{y}||$
$\displaystyle\overset{(b)}{\geq}-\mathbb{E}_{p(v_{i}^{0},v_{i}^{+},y)}f(v_{i}^{1})^{T}f(v_{i}^{2})-3\delta_{aug}^{2}-\delta_{aug}-\mathbb{E}_{p(v_{i}^{0},v_{i}^{+},y)}||f(v^{0}_{y})-\mu_{y}||.$

(a)
$f(v_{i}^{0})^{T}(\mu_{y}-f(v_{i}^{+}))\leq(\frac{\mu_{y}-f(v_{i}^{+})}{||\mu_{y}-f(v_{i}^{+})||})^{T}(\mu_{y}-f(v_{i}^{+}))=||\mu_{y}-f(v_{i}^{+})||$.

(b)
$\mathbb{E}_{p(v_{i}^{0},v_{i}^{+})}||f(v_{i}^{0})-f(v_{i}^{+})||^{2}\leq\delta_{aug}^{2}$,
then:

$\displaystyle\delta_{aug}^{2}$
$\displaystyle\geq\mathbb{E}_{p(v_{i}^{0},v_{i}^{1})}(f(v_{i}^{0})-f(v_{i}^{1}))^{T}\cdot(f(v_{i}^{0})-f(v_{i}^{1}))$
$\displaystyle=\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}(f(v_{i}^{0})-f(v_{i}^{1}))^{T}\cdot(f(v_{i}^{0})-f(v_{i}^{1})+f(v_{i}^{2})-f(v_{i}^{2}))$
$\displaystyle=\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}f(v_{i}^{0})^{T}f(v_{i}^{0})-f(v_{i}^{0})^{T}f(v_{i}^{1})+f(v_{i}^{0})^{T}f(v_{i}^{2})-f(v_{i}^{0})^{T}f(v_{i}^{2})$
$\displaystyle\hskip
50.00008pt-f(v_{i}^{1})^{T}f(v_{i}^{0})+f(v_{i}^{1})^{T}f(v_{i}^{1})-f(v_{i}^{1})^{T}f(v_{i}^{2})+f(v_{i}^{1})^{T}f(v_{i}^{2})$
$\displaystyle=2+\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}\left[-2f(v_{i}^{0})^{T}f(v_{i}^{1})+f(v_{i}^{0})^{T}f(v_{i}^{2})-f(v_{i}^{0})^{T}f(v_{i}^{2})-f(v_{i}^{1})^{T}f(v_{i}^{2})+f(v_{i}^{1})^{T}f(v_{i}^{2})\right]$
$\displaystyle\overset{(c)}{\geq}2-2+\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}\left[f(v_{i}^{0})^{T}f(v_{i}^{2})-1-f(v_{i}^{1})^{T}f(v_{i}^{2})+1-2\delta_{aug}^{2}\right]$
$\displaystyle=\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}\left[f(v_{i}^{0})^{T}f(v_{i}^{2})-f(v_{i}^{1})^{T}f(v_{i}^{2})\right]-2\delta_{aug}^{2}.$

So, we can get the relationship between
$\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}f(v_{i}^{0})^{T}f(v_{i}^{2})$
and
$\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}f(v_{i}^{1})^{T}f(v_{i}^{2})-2\delta_{aug}^{2}$
as below:

$\displaystyle\delta_{aug}^{2}\geq\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}f(v_{i}^{0})^{T}f(v_{i}^{2})-\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}f(v_{i}^{1})^{T}f(v_{i}^{2})-2\delta_{aug}^{2},$
$\displaystyle\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}f(v_{i}^{0})^{T}f(v_{i}^{2})\leq\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}f(v_{i}^{1})^{T}f(v_{i}^{2})+3\delta_{aug}^{2}.$

As $v_{i}^{2}$ is an augmented node, we can get that,

$\mathbb{E}_{p(v_{i}^{0},v_{i}^{+})}f(v_{i}^{0})^{T}f(v_{i}^{+})\leq\mathbb{E}_{p(v_{i}^{0},v_{i}^{1},v_{i}^{2})}f(v_{i}^{1})^{T}f(v_{i}^{2})+3\delta_{aug}^{2}.$

(c) $f(v_{i}^{0})^{T}f(v_{i}^{1})\leq 1$, $f(v_{i}^{0})^{T}f(v_{i}^{2})\leq
1$, and
$\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}f(v_{i}^{1})^{T}f(v_{i}^{2})\geq\frac{2-\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}||f(v_{i}^{1})-f(v_{i}^{2})||^{2}}{2}\geq
1-\frac{\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}(||f(v_{i}^{1})-f(v_{i}^{0})||+||f(v_{i}^{0})-f(v_{i}^{2})||)^{2}}{2}\geq
1-2\delta_{aug}^{2}$.

######  Lemma A.1 ((Budimir et al., 2000) Corollary 3.5 (restated)).

Let $g:\mathbb{R}^{m}\rightarrow\mathbb{R}$ be a differentiable convex mapping
and $z\in\mathbb{R}^{n}$. Suppose that $g$ is $L$\- smooth with the constant
$L>0$, i.e. $\forall x,y\in\mathcal{R}^{m},\|\nabla g(x)-\nabla g(y)\|\leq
L\|x-y\|$. Then we have

$\displaystyle 0\leq\mathbb{E}_{p(z)}g(z)-g\left(\mathbb{E}_{p(z)}z\right)\leq
L\left[\mathbb{E}_{p(z)}\lVert
z\rVert^{2}-\|\mathbb{E}_{p(z)}z\|^{2}\right]=L\sum_{j=1}^{n}\operatorname*{Var}(z^{(j)}),$

where $z^{(j)}$ denotes the $j$-th dimension of $v$.

######  Lemma A.2 ((Wang et al., 2022b) Lemma A.2. restated).

For ${\rm LSE}:=\log\mathbb{E}_{p(z)}\exp(f(v)^{\top}g(z))$, we denote its
(biased) Monte Carlo estimate with $M$ random samples $z_{i}\sim
p(z),i=1,\dots,M$ as $\widehat{\rm
LSE}_{M}=\log\frac{1}{M}\sum_{i=1}^{M}\exp(f(v)^{\top}g(z_{i}))$. Then the
approvimation error $A(M)$ can be upper bounded in expectation as

$A(M):=\mathbb{E}_{p(v,z_{i})}|\widehat{\rm LSE}(M)-{\rm
LSE}|\leq\mathcal{O}(M^{-1/2}).$

We can see that the approvimation error converges to zero in the order of
$M^{-1/2}$.

$\displaystyle\Lambda_{2}$
$\displaystyle=\mathbb{E}_{p(v_{i}^{0})}\log\sum_{j=1}^{K}\exp(f(v_{i}^{0})^{T}\mu_{y_{j}})$
$\displaystyle=\mathbb{E}_{p(v_{i}^{0})}\log\frac{1}{K}\sum_{i=j}^{K}\exp(f(v_{i}^{0})^{T}\mu_{y_{j}})+\log
K$
$\displaystyle=\mathbb{E}_{p(v_{i}^{0})}\log\mathbb{E}_{p(y_{j})}\exp(f(v_{i}^{0})^{T}\mu_{y_{j}})+\log
K$
$\displaystyle\overset{(d)}{\geq}\mathbb{E}_{p(v_{i}^{1})}\log\mathbb{E}_{p(y_{j})}\exp(f(v_{i}^{1})^{T}\mu_{y_{j}})-\delta_{aug}-e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})+\log
K$
$\displaystyle\overset{(e)}{\geq}\mathbb{E}_{p(v_{i}^{1})}\mathbb{E}_{p(y_{i})}\log\frac{1}{M}\sum_{j=1}^{M}\exp(f(v_{i}^{1})^{T}\mu_{y_{j}})-A(M)+\log
K-\delta_{aug}-e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})$
$\displaystyle=\mathbb{E}_{p(v_{i}^{1})}\mathbb{E}_{p(y_{i})}\log\frac{1}{M}\sum_{j=1}^{M}\exp(\mathbb{E}_{p(v_{i}^{-}|y_{i}^{-})}f(v_{i}^{1})^{T}f(v_{i}^{-}))-A(M)+\log
K-\delta_{aug}-e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})$
$\displaystyle\overset{(f)}{\geq}\mathbb{E}_{p(v_{i}^{1})}\mathbb{E}_{p(y_{i})}\mathbb{E}_{p(v_{i}^{-}|y_{i}^{-})}\log\frac{1}{M}\sum_{i=1}^{M}\exp(f(v_{i}^{1})^{T}f(v_{i}^{-}))$
$\displaystyle\hskip
15.00002pt-\frac{1}{2}\sum_{j=1}^{m}\operatorname*{Var}(f_{j}(v^{-}|y))-A(M)+\log
K-\delta_{aug}-e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})$
$\displaystyle=\mathbb{E}_{p(v_{i}^{1})}\mathbb{E}_{p(y_{i})}\mathbb{E}_{p(v_{i}^{-}|y_{i}^{-})}\log\sum_{i=1}^{M}\exp(f(v_{i}^{1})^{T}f(v_{i}^{-}))$
$\displaystyle\hskip 15.00002pt-\log
M-\frac{1}{2}\sum_{j=1}^{m}\operatorname*{Var}(f_{j}(v^{-}|y))-A(M)+\log
K-\delta_{aug}-e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j}).$

(d) We can show that: $\exp(\left[f(v)^{T}\mu_{y_{j}}\right]$ is convex, and
$u_{y_{j}}$ satisfy e-smooth,

$\displaystyle\hskip 15.00002pt||\frac{\partial\exp(f(v)^{T}a)}{\partial
a}-\frac{\partial\exp(f(v)^{T}b)}{\partial b}||$
$\displaystyle=||\exp(f(v)^{T}a)f(v)-\exp(f(v)^{T}b)f(v))||$
$\displaystyle=|\exp(f(v)^{T}a)-\exp(f(v)^{T}b)|\cdot||f(v)||$
$\displaystyle\leq|\exp(f(v)^{T}a)-\exp(f(v)^{T}b)|$ $\displaystyle\leq
e||(f(v)^{T})(a-b)||\quad(f(v)^{T}a,f(v)^{T}b\leq 1,\text{so the biggest slope
is}\ e)$ $\displaystyle\leq e||a-b||.$

So according to Lemma A.1, we get,

$\begin{split}\mathbb{E}_{p(y_{j})}\exp(\left[f(v_{i}^{1})^{T}\mu_{y_{j}}\right])&\leq\exp(\left[f(v_{i}^{1})^{T}\mathbb{E}_{p(y_{j})}\mu_{y_{j}}\right])+e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})\\\
&=\exp(f(v_{i}^{1})^{T}\mu)+e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j}).\end{split}$

Then, we can calculate the difference between
$\log\mathbb{E}_{p(y_{j})}\exp(\left[f(v_{i}^{0})^{T}\mu_{y_{j}}\right])$ and
$\log\mathbb{E}_{p(y_{j})}\exp(\left[f(v_{i}^{1})^{T}\mu_{y_{j}}\right])$ by
applying reversed Jensen and Jensen inequality, respectively.

$\displaystyle\hskip
15.00002pt\log\mathbb{E}_{p(y_{j})}\exp(\left[f(v_{i}^{1})^{T}\mu_{y_{j}}\right])-\log\mathbb{E}_{p(y_{j})}\exp(\left[f(v_{i}^{0})^{T}\mu_{y_{j}}\right])$
$\displaystyle\leq\log\mathbb{E}_{p(y_{j})}\exp(\left[f(v_{i}^{1})^{T}\mu_{y_{j}}\right])-\left[f(v_{i}^{0})^{T}\mu\right]$
$\displaystyle\leq\log\left[\exp(f(v_{i}^{1})^{T}\mu)+e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})\right]-\left[f(v_{i}^{0})^{T}\mu\right]$
$\displaystyle=\log\left[\exp(f(v_{i}^{1})^{T}\mu)\right]+\log\left[1+\frac{e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})}{\exp(f(v_{i}^{1})^{T}\mu)}\right]-\left[f(v_{i}^{0})^{T}\mu\right]$
$\displaystyle\leq
f(v_{i}^{1})^{T}\mu-f(v_{i}^{0})^{T}\mu+\log\left[1+e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})\right]\quad(e^{2}\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})\text{,
if not ReLU)}$
$\displaystyle\leq(f(v_{i}^{1})^{T}-f(v_{i}^{0})^{T})\mu+e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})$
$\displaystyle\leq(f(v_{i}^{1})-f(v_{i}^{0}))^{T}\frac{||\mu||}{||f(v_{i}^{1})-f(v_{i}^{0})||}(f(v_{i}^{1})-f(v_{i}^{0}))+e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})$
$\displaystyle\leq(f(v_{i}^{1})-f(v_{i}^{0}))^{T}\frac{1}{||f(v_{i}^{1})-f(v_{i}^{0})||}(f(v_{i}^{1})-f(v_{i}^{0}))+e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})$
$\displaystyle\leq\delta_{aug}+e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j}).$

(e) We adopt a Monte Carlo estimation with $M$ samples from $p(y)$ and bound
the approximation error with Lemma A.2.

(f) We also uses Lemma A.1, and as proof by Wang et al. (2022b), logsumexp is
L-smooth for $L=\frac{1}{2}$.

$\displaystyle{\mathcal{L}}_{\mathrm{CE}}$
$\displaystyle=\Lambda_{1}+\Lambda_{2}$
$\displaystyle\geq-\mathbb{E}_{p(v,y)}f(v_{i}^{1})^{T}f(v_{i}^{2})-3\delta_{aug}^{2}-\delta_{aug}-\mathbb{E}_{p(v^{0},y)}||f(v_{y}^{0})-\mu_{y}||$
$\displaystyle\hskip
15.00002pt+\mathbb{E}_{p(v_{i}^{1})}\mathbb{E}_{p(y_{i})}\mathbb{E}_{p(v_{i}^{-}|y_{i})}\log\sum_{i=1}^{M}\exp(f(v_{i}^{1})^{T}f(v_{i}^{-}))$
$\displaystyle\hskip 15.00002pt-\log
M-\frac{1}{2}\sum_{j=1}^{m}\operatorname*{Var}(f_{j}(v^{-}|y))-A(M)+\log
K-\delta_{aug}-e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})$
$\displaystyle=\left[-\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}f(v_{i}^{1})^{T}f(v_{i}^{2})+\mathbb{E}_{p(v_{i}^{-})}\log\sum_{i=1}^{M}\exp(f(v_{i}^{1})f(v_{i}^{-}))\right]-3\delta_{aug}^{2}-\delta_{aug}-\mathbb{E}_{p(v^{0},y)}||f(v_{y}^{0})-\mu_{y}||$
$\displaystyle\hskip 15.00002pt-\log
M-\frac{1}{2}\sum_{j=1}^{m}\operatorname*{Var}(f_{j}(v^{-}|y))-A(M)+\log
K-\delta_{aug}-e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})$
$\displaystyle={\mathcal{L}}_{\mathrm{NCE}}-3\delta_{aug}^{2}-2\delta_{aug}-\log\frac{M}{K}-\frac{1}{2}\sum_{j=1}^{m}\operatorname*{Var}(f_{j}(v^{-}|y))-A(M)-e\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})-\mathbb{E}_{p(v^{0},y)}||f(v_{y}^{0})-\mu_{y}||$
$\displaystyle\overset{(g)}{\geq}{\mathcal{L}}_{\mathrm{NCE}}-3\delta_{aug}^{2}-2\delta_{aug}-\log\frac{M}{K}-\frac{1}{2}\operatorname*{Var}(f(v^{+})|y)-\sqrt{\operatorname*{Var}(f(v^{0})|y)}-O(M^{-\frac{1}{2}})-e\operatorname*{Var}(\mu_{y}).$

(g) This holds because, $v^{-}$ is randomly selected from $v^{+}$ and,

$\displaystyle\hskip
15.00002pt\sum_{j=1}^{m}\operatorname*{Var}(f_{j}(v^{-}|y))$
$\displaystyle=\sum_{j=1}^{m}\mathbb{E}_{p(y)}\mathbb{E}_{p(v|y)}(f_{j}(v^{+})-\mathbb{E}_{p(v^{\prime}|y)}f_{j}(v^{\prime}))^{2}$
$\displaystyle=\mathbb{E}_{p(y)}\mathbb{E}_{p(v|y)}\sum_{j=1}^{m}(f_{j}(v^{+})-\mathbb{E}_{v^{\prime}}f_{j}(v^{\prime}))$
$\displaystyle=\mathbb{E}_{p(y)}\mathbb{E}_{p(v|y)}||f(v)-\mathbb{E}_{v^{\prime}}f(v^{\prime})||^{2}$
$\displaystyle=\operatorname*{Var}(f(v^{+})|y).$

And similarly, we can get
$\sum_{j=1}^{n}\operatorname*{Var}(\mu_{j})=\operatorname*{Var}(\mu_{y})$.

###  A.3 Proof of Corollary 3.1

For $\operatorname*{Var}(f(v_{y}^{0}|y))$, we can use positive pair difference
and the intrinsic property of model and data to express.

$\displaystyle\operatorname*{Var}(f(v_{y}^{0}|y))$
$\displaystyle=\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}^{0}|y)}||f(v_{y}^{0})-\mu_{y}||^{2}$
$\displaystyle=\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}^{0}|y)}\left[(f(v_{y}^{0})-\mu_{y})^{T}(f(v_{y}^{0})-\mu_{y}))\right]$
$\displaystyle=\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}^{0}|y)}\left[f(v_{y}^{0})^{T}f(v_{y}^{0})+\mu_{y}^{T}\mu_{y}-2f(v_{y}^{0})^{T}\mu_{y}\right]$
$\displaystyle\leq\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}^{0}|y)}\left[2-2f(v_{y}^{0})^{T}\mu_{y}\right]$
$\displaystyle\overset{(h)}{\leq}\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}^{0}|y)}\left[2-2(1-\frac{1}{3}\delta_{aug}^{2}-\frac{2}{3}\delta_{aug}\delta_{y^{+}}-\frac{1}{2}\delta_{y^{+}}^{2})\right]$
$\displaystyle=\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}^{0}|y)}\left[\frac{2}{3}\delta_{aug}^{2}+\frac{4}{3}\delta_{aug}\delta_{y^{+}}+\delta_{y^{+}}^{2})\right]$
$\displaystyle\leq\frac{2}{3}\delta_{aug}^{2}+\frac{4}{3}\delta_{aug}L\epsilon_{0}+L^{2}\epsilon_{0}^{2},$

where
$\epsilon_{0}=\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{i}^{0},v_{j}^{0}|y)}||v_{i}^{0}-v_{j}^{0}||$
and $L$ is the Lipschitz constant, so
$\delta_{y^{+}}^{2}=\mathbb{E}_{p(y,i,j)}||f(v^{0}_{y,i})-f(v^{0}_{y,j})||^{2}\leq(L\epsilon_{0})^{2}$.

Then we can easily get that,

$\begin{split}\operatorname*{Var}(f(v_{y}^{+})|y)&=\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}^{-}|y)}||f(v_{y}^{+})-\mu_{y}||^{2}\\\
&\leq\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}^{+}|y)}(||f(v_{y}^{+})-f(v_{y}^{0})||+||f(v_{y}^{0})-\mu_{y}||)^{2}\\\
&=\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}^{+}|y)}||f(v_{y}^{+})-f(v_{y}^{0})||^{2}+\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}^{+}|y)}||f(v_{y}^{0})-\mu_{y}||)^{2}\\\
&\hskip
15.00002pt+2\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}^{+}|y)}||f(v_{y}^{+})-f(v_{y}^{0})||\cdot||f(v_{y}^{0})-\mu_{y}||\\\
&\leq\delta_{aug}^{2}+\operatorname*{Var}(f(v_{y}^{0})|y)+2\delta_{aug}\sqrt{\operatorname*{Var}(f(v_{y}^{0})|y)}\\\
&=(\delta_{aug}+\sqrt{\operatorname*{Var}(f(v_{y}^{0})|y)})^{2}.\end{split}$

(h) We use Theorem 2.3.

And $\operatorname*{Var}(\mu_{y})$ can also be expressed by intrinsic
properties.

$\displaystyle\operatorname*{Var}(\mu_{y})$
$\displaystyle=\mathbb{E}_{p(y)}||\mu_{y}-\mu||^{2}$
$\displaystyle=\mathbb{E}_{p(y)}||\mu_{y}-f(v_{y}^{*})+f(v_{y}^{*})-\mu||^{2}$
$\displaystyle\leq\mathbb{E}_{p(y)}(||\mu_{y}-f(v_{y}^{*})||+||f(v_{y}^{*})-\mu||)^{2}$
$\displaystyle=\mathbb{E}_{p(y)}||\mathbb{E}_{p(v_{y}|y)}f(v_{y})-f(v_{y}^{*})||^{2}+\mathbb{E}_{p(y)}||f(v_{y}^{*})-\mathbb{E}_{p(v)}f(v)||^{2}$
$\displaystyle\hskip
15.00002pt+2\mathbb{E}_{p(y)}(||\mathbb{E}_{p(v_{y}|y)}f(v_{y})-f(v_{y}^{*})||\cdot||f(v_{y}^{*})-\mathbb{E}_{p(v)}f(v)||)$
$\displaystyle=\mathbb{E}_{p(y)}||\mathbb{E}_{p(v_{y}|y)}[f(v_{y})-f(v_{y}^{*})]||^{2}+\mathbb{E}_{p(y)}||\mathbb{E}_{p(v)}[f(v_{y}^{*})-f(v)]||^{2}$
$\displaystyle\hskip
15.00002pt+2\mathbb{E}_{p(y)}(||\mathbb{E}_{p(v_{y}|y)}[f(v_{y})-f(v_{y}^{*})]||\cdot||\mathbb{E}_{p(v)}[f(v_{y}^{*})-f(v)]||)$
$\displaystyle\leq\mathbb{E}_{p(y)}\mathbb{E}_{p(v_{y}|y)}||f(v_{y})-f(v_{y}^{*})||^{2}+\mathbb{E}_{p(y)}\mathbb{E}_{p(v)}||f(v_{y}^{*})-f(v)||^{2}$
$\displaystyle\hskip
15.00002pt+2\mathbb{E}_{p(y)}(\mathbb{E}_{p(v_{y}|y)}||f(v_{y})-f(v_{y}^{*})||\cdot||f(v_{y}^{*})-f(v)||)$
$\displaystyle\leq
L^{2}\epsilon_{1}^{2}+L^{2}\epsilon_{2}^{2}+2L^{2}\epsilon_{1}\epsilon_{2}$
$\displaystyle=L^{2}(\epsilon_{1}+\epsilon_{2})^{2},$

where $v_{y}^{*}$ could be any node of class $y$, and
$\epsilon_{1}=\mathbb{E}_{p(v,y)}||v_{y}-v_{y}^{*}||$,
$\epsilon_{2}=\mathbb{E}_{p(y)}\mathbb{E}_{p(v)}||v-v_{y}^{*}||$.

$\displaystyle\hat{{\mathcal{L}}}_{\mathrm{CE}}$
$\displaystyle\geq{\mathcal{L}}_{\mathrm{NCE}}-3\delta_{aug}^{2}-2\delta_{aug}-\log\frac{M}{K}-\frac{1}{2}\operatorname*{Var}(f(v^{-})|y)-\sqrt{\operatorname*{Var}(f(v^{0})|y)}-O(M^{-\frac{1}{2}})-e\operatorname*{Var}(\mu_{y})$
$\displaystyle\geq{\mathcal{L}}_{\mathrm{NCE}}-3\delta_{aug}^{2}-2\delta_{aug}-\log\frac{M}{K}-\frac{1}{2}(\delta_{aug}+\sqrt{\operatorname*{Var}(f(v_{y}^{0})|y)})^{2}-\sqrt{\operatorname*{Var}(f(v_{y}^{0})|y)}-O(M^{-\frac{1}{2}})-eL^{2}(\epsilon_{1}+\epsilon_{2})^{2}$
$\displaystyle={\mathcal{L}}_{\mathrm{NCE}}-3\delta_{aug}^{2}-2\delta_{aug}-log\frac{M}{K}-\frac{1}{2}\delta_{aug}^{2}-(\delta_{aug}+1)\sqrt{\operatorname*{Var}(f(v_{y}^{0})|y))}$
$\displaystyle\hskip
15.00002pt-\frac{1}{2}\operatorname*{Var}(f(v_{y}^{0})|y))-O(M^{-\frac{1}{2}})-eL^{2}(\epsilon_{1}+\epsilon_{2})^{2}$
$\displaystyle={\mathcal{L}}_{\mathrm{NCE}}-g(\delta_{aug})-\log\frac{M}{K}-O(M^{-\frac{1}{2}}),$

where
$g(\delta_{aug})=\frac{23}{6}\delta_{aug}^{2}+\frac{1}{2}L^{2}\epsilon_{0}^{2}+eL^{2}(\epsilon_{1}+\epsilon_{2})^{2}+2\delta_{aug}+\frac{2}{3}\delta_{aug}L\epsilon_{0}+(\delta_{aug}+1)\sqrt{\frac{2}{3}\delta_{aug}^{2}+\frac{4}{3}\delta_{aug}L\epsilon_{0}+L^{2}\epsilon_{0}^{2}}$.

According to Oord et al. (2018), we get,

$\begin{split}&I(f(v_{i}^{1}),f(v_{i}^{2}))\geq\log(M)-{\mathcal{L}}_{\mathrm{NCE}},\\\
&{\mathcal{L}}_{\mathrm{NCE}}\geq\log(M)-I(f(v_{i}^{1}),f(v_{i}^{2})).\end{split}$

Therefore, we can reformulate Theorem 2.5 as below:

$\begin{split}\hat{{\mathcal{L}}}_{\mathrm{CE}}&\geq\log(M)-I(f(v_{i}^{1}),f(v_{i}^{2}))-g(\delta_{aug})-\log\frac{M}{K}-O(M^{-\frac{1}{2}})\\\
&=\log(K)-I(f(v_{i}^{1}),f(v_{i}^{2}))-g(\delta_{aug})-O(M^{-\frac{1}{2}}).\end{split}$

###  A.4 proof of Corollary 3.3

Corallary 3.3 could be simply proved below:

$\begin{split}\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}||f(v_{i}^{1})-f(v_{i}^{2})||^{2}&=\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}[(f(v_{i}^{1})^{T}-f(v_{i}^{2})^{T})(f(v_{i}^{1})-f(v_{i}^{2}))]\\\
&=\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}[2-2f(v_{i}^{1})^{T}f(v_{i}^{2})]\\\
&=2-\frac{2}{N}tr((H^{1})^{T}H^{2})\\\
&\overset{(1)}{=}2-\frac{2}{N}\sum_{i}\theta_{i}\lambda_{i}^{\prime}\lambda_{i}^{\prime\prime}.\\\
\end{split}$

So
$(\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}||f(v_{i}^{1})-f(v_{i}^{2})||)^{2}\leq\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}||f(v_{i}^{1})-f(v_{i}^{2})||^{2}=2-\frac{2}{N}\sum_{i}\theta_{i}\lambda_{i}^{\prime}\lambda_{i}^{\prime\prime}$,
then
$\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}||f(v_{i}^{1})-f(v_{i}^{2})||\leq\sqrt{2-\frac{2}{N}\sum_{i}\theta_{i}\lambda_{i}^{\prime}\lambda_{i}^{\prime\prime}}$.

(1) is suggested by Liu et al. (2022), $tr((H^{1})^{T}H^{2})$ could be
represented as
$\sum_{i}\theta_{i}\lambda_{i}^{\prime}\lambda_{i}^{\prime\prime}$.

As we know that,

$\begin{split}\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}||f(v_{i}^{1})-f(v_{i}^{2})||\leq\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}(||f(v_{i}^{1})-f(v_{i}^{0})||+||f(v_{i}^{0})-f(v_{i}^{2})||)\leq
2\delta_{aug}.\end{split}$

Then, we can get:

$2\delta_{aug}\geq\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}||f(v_{i}^{1})-f(v_{i}^{2})||\geq\sqrt{2-\frac{2}{N}\sum_{i}\theta_{i}\lambda_{i}^{\prime}\lambda_{i}^{\prime\prime}}.$
(8)

###  A.5 proof of Lemma B.1

From Stewart (1990), we know the following equation:

$\Delta\lambda_{i}=\lambda_{i}^{{}^{\prime}}-\lambda_{i}=u_{i}^{T}\Delta
Au_{i}-\lambda_{i}u_{i}^{T}\Delta Du_{i}+O(||\Delta A||).$

So we can calculate the difference between
$\lambda_{i}^{\prime},\lambda_{i}^{\prime\prime}$ and $\lambda_{i}$,

$\displaystyle\Delta\lambda_{i}$
$\displaystyle=\sum_{m}(\sum_{n}u_{i}\left[n\right]\Delta
A\left[m\right]\left[n\right])u_{i}\left[m\right]-\lambda_{i}\sum_{m}u_{i}\left[m\right]\Delta
D\left[m\right]u_{i}\left[m\right]+O(||\Delta A||)$
$\displaystyle=\sum_{m,n}u_{i}\left[m\right]u_{i}\left[n\right]\Delta
A\left[m\right]\left[n\right]-\lambda_{i}\sum_{m,n}u_{i}\left[m\right]\Delta
A\left[m\right]\left[n\right]u_{i}\left[m\right]+O(||\Delta A||).$

And we can directly calculate
$\lambda_{i}^{\prime}-\lambda_{i}^{\prime\prime}$ as below:

$\displaystyle\lambda_{i}^{\prime}-\lambda_{i}^{\prime\prime}$
$\displaystyle=\Delta\lambda_{i}^{\prime}-\Delta\lambda_{i}^{\prime\prime}$
$\displaystyle=\sum_{m,n}u_{i}\left[m\right]u_{i}\left[n\right]\Delta\widehat{A}\left[m\right]\left[n\right]-\lambda_{i}\sum_{m,n}u_{i}\left[m\right]\Delta\widehat{A}\left[m\right]\left[n\right]u_{i}\left[m\right]$
$\displaystyle=\sum_{m,n}u_{i}\left[m\right]\Delta\widehat{A}\left[m\right]\left[n\right](u_{i}\left[n\right]-\lambda_{i}u_{i}\left[m\right]).$

##  Appendix B GCL methods with spatial and spectral augmentation

###  B.1 spatial augmentation

Most augmentation methods are applied to explicitly or implicitly increase
mutual information while maintain high positive pair difference. GRACE simply
adjusts this by changing the drop rate of features and edges. AD-GCL (Suresh
et al., 2021) directly uses the optimization objective
$min_{\\{aug\\}}max_{\\{f\in F\\}}I(f(v),f(aug(v)))$ to search for a stronger
augmentation.

Figure 4: influence of $p_{\tau}$ on Cora (all the data are normalized for
better visualization)

And GCA (Zhu et al., 2021) could always perform better than random drop. This
is mainly because GCA calculates node importance and masks those unimportant
to increase mutual information. Also they use $p_{\tau}$ as a cut-off
probability, so for those unimportant features/edges, all of them share the
same drop probability $p_{\tau}$. By setting a large $p_{\tau}$, GCA can
reduce the drop probability for the least important features/edges and drop
more relatively important ones to achieve a trade-off between mutual
information and positive pair difference.

From Figure 4, we could clearly see that, as $p_{\tau}$ increases, positive
pair difference and ${\mathcal{L}}_{\mathrm{NCE}}$ are increasing, and leads
to a better downstream performance, than when $p_{\tau}$ becomes too large, we
got a trivial solution. And in the code provided by the author, $p_{\tau}$ is
set to 0.7. So GCA performances well on downstream tasks not only because its
adaptive augmentation, but also its modification on positive pair difference.

###  B.2 spectral augmentation

Furthermore, we can demonstrate that lots of spectral augmentations follow
this schema to improve downstream performance. Liu et al. (2022) proposes that
increasing the number of high-frequency drops leads to better performance.
This is because high-frequency parts are associated with higher coefficients
$\lambda_{i}$, so increasing the number of high-frequency drops can have a
stronger increasement on $\delta_{aug}$, resulting in better performance.

######  Lemma B.1 (Change of Spectrum).

if we assume that $A^{\prime}=A+\Delta A_{1}$, $A^{\prime\prime}=A+\Delta
A_{2}$, $\lambda_{i}^{\prime}$, $\lambda_{i}^{\prime\prime}$ is the $i^{th}$
eigenvalue of $A^{\prime}$ and $A^{\prime\prime}$, respectively.
$\Delta\hat{A}=A^{\prime}-A^{\prime\prime}$, and $u_{i}$ is the corresponding
eigenvector.

$\begin{split}\lambda_{i}^{\prime}-\lambda_{i}^{\prime\prime}=\sum_{m,n}u_{i}\left[m\right]\Delta\widehat{A}\left[m\right]\left[n\right](u_{i}\left[n\right]-\lambda_{i}u_{i}\left[m\right]).\end{split}$

Lemma B.1 is proved in Appendix A.5. Lin et al. (2022) propose to maximize the
spectral difference between two views, but Lemma B.1 shows that difference
between spectrum is highly correlated with the original magnitude, so it is
actually encouraging more difference in large $|\lambda_{i}|$. But rather than
just drop information, they try to improve the spectrum of first view, and
decrease the other view. if we simply assume
$\lambda_{i}^{\prime}=\lambda_{i}+n$,
$\lambda_{i}^{\prime\prime}=\lambda_{i}-n$, then
$\lambda_{i}^{\prime}\lambda_{i}^{\prime\prime}=\lambda_{i}^{2}-n^{2}\leq\lambda_{i}^{2}$,
so this could also be explained by positive pair difference increasement.

##  Appendix C experiments

###  C.1 datasets and baselines

We choose the six commonly used Cora, CiteSeer, PubMed, DBLP, Amazon-Photo and
Amazon-Computer for evaluation. The first four datasets are citation networks
(Sen et al., 2008; Yang et al., 2016; Bojchevski & Günnemann, 2017), where
nodes represent papers, edges are the citation relationship between papers,
node features are comprised of bag-of-words vector of the papers and labels
represent the fields of papers. In Amazon-Photos and Amazon-Computers (Shchur
et al., 2018), nodes represent the products and edges means that the two
products are always bought together, the node features are also comprised of
bag-of words vector of comments, labels represent the category of the product.

After performing contrastive learning, we use logistic regression for
downstream classification, and randomly choose 10% of nodes for training and
the rest for testing.

Table 2: Dataset statistics Dataset | Nodes | Edges | Features | Classes
---|---|---|---|---
Cora | 2,708 | 5,429 | 1,433 | 7
Citeseer | 3,327 | 4,732 | 3,703 | 6
Pubmed | 19,717 | 44,338 | 500 | 3
DBLP | 17,716 | 105,734 | 1,639 | 4
Amazon-Photo | 7,650 | 119,081 | 745 | 8
Amazon-Computers | 13,752 | 245,861 | 767 | 10
Table 3: Dataset download links Dataset | Download Link
---|---
Cora | https://github.com/kimiyoung/planetoid/raw/master/data
Citeseer | https://github.com//kimiyoung/planetoid/raw/master/data
Pubmed | https://github.com/kimiyoung/planetoid/raw/master/data
DBLP | https://github.com/abojchevski/graph2gauss/raw/master/data/dblp.npz
Amazon-Photo | https://github.com/shchur/gnn-benchmark/raw/master/data/npz/amazon_electronics_photo.npz
Amazon-Computers | https://github.com/shchur/gnn-benchmark/raw/master/data/npz/amazon_electronics_computers.npz

And the publicly available implementations of Baselines can be found at the
following URLs:

  * •

GCN: https://github.com/tkipf/gcn

  * •

GAT: https://github.com/PetarV-/GAT

  * •

GRACE: https://github.com/CRIPAC-DIG/GRACE

  * •

GCA: https://github.com/CRIPAC-DIG/GCA

  * •

AD-GCL https://github.com/susheels/adgcl

###  C.2 change on positive/negative pair similarity

The InfoNCE loss ${\mathcal{L}}_{\mathrm{NCE}}$ can be written as
${\mathcal{L}}_{\mathrm{NCE}}=\mathbb{E}_{p(v_{i}^{1},v_{i}^{2})}\mathbb{E}_{p({v_{i}^{-}})}\left[-\log\frac{\exp(f(v_{i}^{1})^{T}f(v_{i}^{2}))}{\sum_{\\{v^{-}_{i}\\}}\exp(f(v_{i}^{1})^{T}f(v^{-}_{i}))}\right]$,
and when we perform stronger augmentation, $f(v_{i}^{1})^{T}f(v_{i}^{2})$
would be hard to maximize, and the model will try to minimize
$f(v_{i}^{1})^{T}f(v^{-}_{i})$ harder. From Figure 5, when the augmentation
gets stronger, negative and positive pair similarity both decreases, so the
class separating performance is enhanced.

Figure 5: $\mathrm{sim+}$ represents the positive pair similarity
$f(v_{i}^{1})^{T}f(v_{i}^{2})$, and $\mathrm{sim-}$ is negative pair
similarity $f(v_{i}^{1})^{T}f(v_{i}^{-})$, the x-axis stands for dropout rate
on edges

###  C.3 hyperparameter setting

Table 4: Hyperparameters settings Dataset | Learning rate | Weight decay | num layers | $\tau$ | Epochs | Hidden dim | Activation
---|---|---|---|---|---|---|---
Cora | $5^{-4}$ | $10^{-6}$ | 2 | 0.4 | 200 | 128 | ReLU
Citeseer | $10^{-4}$ | $10^{-6}$ | 2 | 0.9 | 200 | 256 | PReLU
Pubmed | $10^{-4}$ | $10^{-6}$ | 2 | 0.7 | 200 | 256 | ReLU
DBLP | $10^{-4}$ | $10^{-6}$ | 2 | 0.7 | 200 | 256 | ReLU
Amazon-Photo | $10^{-4}$ | $10^{-6}$ | 2 | 0.3 | 200 | 256 | ReLU
Amazon-Computers | $10^{-4}$ | $10^{-6}$ | 2 | 0.2 | 200 | 128 | RReLU

The hyperparameter settings is shown in Table 4, other hyperparameter
correlated to only one algorithm are set the same as the original author. The
hyperparameter in our methods retain rate $\xi$ and spectrum change amplitude
$\alpha$, we select them from 0.05 to 0.45 and from -0.1 to 0.01,
respectively.

###  C.4 value of $\theta$s

As defined by Liu et al. (2022), $\theta$s are actually linear combination of
the eigenvalues of adjacency matrix ${\bm{A}}$. To demonstrate what $\theta$s
actually are, we first focus on the assumption below.

######  Assumption C.1 (High-order Proximity).

$\bm{M}=w_{0}+w_{1}\bm{A}+w_{2}\bm{A^{2}}+\dots+w_{q}\bm{A^{q}}$, where
$\bm{M}=X^{1}W\cdot W^{T}(X^{2})^{T}$, $\bm{A^{i}}$ means matrix
multiplications between $i$ $\bm{A}$s, and $w_{i}$ is the weight of that term.

Where $X^{1},X^{2}$ indicates the feature matrix of graph
${\mathcal{G}}^{1},{\mathcal{G}}^{2}$, $W$ stands for the parameter of the
model, so $\bm{M}=X^{1}W\cdot W^{T}(X^{2})^{T}$ means embedding similarity
between two views, and could be roughly represented by the weighted sum of
different orders of $\bm{A}$. Furthermore, we have that:

$\left\\{\begin{aligned}
w_{0}+w_{1}\lambda_{1}+&\dots+w_{q}\lambda_{1}^{q}=\theta_{1}\\\
w_{0}+w_{1}\lambda_{2}+&\dots+w_{q}\lambda_{2}^{q}=\theta_{2}\\\ &\dots\\\
w_{0}+w_{1}\lambda_{N}+&\dots+w_{q}\lambda_{N}^{q}=\theta_{N},\\\
\end{aligned}\right.\\\ $

where $\lambda_{1},...,\lambda_{N}$ is N eigenvalues of the adjacency matrix
${\bm{A}}$.

Figure 6: Percentage of positive $\theta$

So we know that $\theta$s are actually linear combination of $\lambda$s. As
the model is trained to minimize ${\mathcal{L}}_{\mathrm{NCE}}$, $\theta$s are
expected to increase, and we can simply set $w_{0},w_{2},...,w_{2(q/2)}$ to be
positive and other $w_{i}$ to $0$, then we can get $\theta$s that are all
positive, and the model would easily find better $w$s.

Therefore, we can say that in the training process, $\theta$s are mostly
positive, and the experiments shown in Figure 7 indicate it to be true.

###  C.5 changes on the spectrum

Figure 7: As we perform spectrum augmentation each 10 epochs, the x-axis is
epoch/10, the y-axis of the left figure is number of decreasing $\lambda$s
minus number of increasing $\lambda$s; for the middle one, y-axis stands for
how much $\lambda$s averagely decreases; and the right one is the average
value of $\lambda$.

From Figure 7(a), we can see that, when the algorithm is training, $\theta$s
are mostly increasing gradually, and when we perform spectrum augmentation,
$\theta$s will not increase as before, increasing number of $\theta$ is close
even smaller to decreasing ones. Then we take a step back on those decreasing
ones, result in increasing $\theta$s again in the next epoch. Therefore, what
we do is actually perform augmentation to maximize positive pair difference
first, then maximize the mutual information after spectrum augmentation. The
idea is actually similar AD-GCL, but we use $\theta$s to indicate whether the
augmentation is too much, so we get a more reasonable result. Figure 7(b) and
(c) shows that as the training goes, the change on larger magnitude
eigenvalues are also more significant, causing the spectrum to be smoother.

Also there is one thing to notice that when we perform spectrum smoothen
method, we are indirectly changing the edge weights, causing the augmentation
being weaker or stronger as drop an edge with weight of 1 is different than
drop an edge with weight $1+noise$. To reduce its influence, we conduct extra
augmentation or recovery based on the average weight change.

###  C.6 center similarity

As we mentioned earlier, GCL mainly contributes to downstream tasks by
decreasing the negative center similarity while maintaining a relatively high
similarity to the positive center. We propose two methods: one that increases
mutual information between two views while keeping a high positive pair
difference by masking more unimportant edges or features. This allows the
model to learn more useful information, which forces nodes close to its
positive center. The other method tries to increase positive pair difference
while maintaining a relatively high mutual information, so it may not learn as
much useful information. However, by increasing the positive pair difference,
it forces the model to separate nodes from different classes further apart. In
summary, the first method brings nodes of the same class closer together,
while the second method separates nodes from different classes further apart
just as shown in Figure 8.

Figure 8: similarity of nodes between its positive center and negative center,
GRACE stands for the pure GRACE, GRACEI stands for GRACE with information
augmentation, and GRACES stands for GRACE with spectrum augmentation

###  C.7 hyperparameter sensitivity

Analysis of retain rate. Retain rate controls how many important
features/edges we kept, and how many unimportant ones dropped. We can see from
Figure 9 that AD-GCL benefits from a larger retain rate as it is designed to
minimize the mutual information, and lots of vital structures are dropped. And
large datasets like PubMed, DBLP benefits less, it is mainly because a graph
with more edges are more likely to maintain enough information than graph with
little edges. For example, after a 30% dropout on edges, a graph with 1000
edges would still kept enough information for downstream tasks, but a graph
with 10 edges would probably lose some vital information.

Figure 9: accuracy on downstream tasks with different $\alpha$

Analysis of $\alpha$. $\alpha$ controls how much $|\lambda|$ will decrease, as
we take a step back when the $|\lambda|$ decreases too much, the
hyperparameter $\alpha$ does not matter so much. But as shown in Figure 10, it
still performs more steady on large graphs as a wrong modification on a single
$\lambda$ matters less than on small graphs.

Figure 10: accuracy on downstream tasks with different retain rate

##  Appendix D related work

Graph Contrastive Learning. Graph Contrastive Learning has shown its
superiority and lots of researcher are working on it. DGI (Veličković et al.,
2018) contrasts between local node embeddnig and the global summary vector;
GRACE (Zhu et al., 2020), GCA (Zhu et al., 2021) and GraphCL (You et al.,
2020) randomly drop edges and features; AD-GCL (Suresh et al., 2021) and
InfoGCL Xu et al. (2021) learn an adaptive augmentation with the help of
different principles. In theoretical perspective, Liu et al. (2022) correlates
the InfoNCE loss with graph spectrum, and propose that augmentation should be
more focused on high frequency parts. Lin et al. (2022) thinks that
augmentation maximize the spectrum difference would help, and Yuan et al.
(2022) analyse GCL with information theory.

Contrastive Learning Theory. By linking downstream classification and
contrastive learning objectives, Arora et al. (2019) propose a theoretical
generalization guarantee. Ash et al. (2021) further explore how does the
number of negative samples influence the generalization. Then Wang & Isola
(2020) propose that perfect alignment and uniformity is the key to success
while Wang et al. (2022b) argues augmentation overlap with alignment helps
gathering intra-class nodes by stronger augmentation. And Tian et al. (2020);
Wang et al. (2022a) further discuss what kind of augmentation is better for
downstream performance.