Revisiting Graph Contrastive Learning from the Perspective of Graph Spectrum
Authors: Nian Liu
Xiao Wang
Deyu Bo
Chuan Shi
Jian Pei
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph neural network
graph contrastive learning
graph spectral theory
graph self-supervised learning

Abstract: Graph Contrastive Learning (GCL), learning the node representations by augmenting graphs, has attracted considerable attentions. Despite the proliferation of various graph augmentation strategies, there are still some fundamental questions unclear: what information is essentially learned by GCL? Are there some general augmentation rules behind different augmentations? If so, what are they and what insights can they bring? In this paper, we answer these questions by establishing the connection between GCL and graph spectrum. By an experimental investigation in spectral domain, we firstly find the General grAph augMEntation (GAME) rule for GCL, i.e., the difference of the high-frequency parts between two augmented graphs should be larger than that of low-frequency parts. This rule reveals the fundamental principle to revisit the current graph augmentations and design new effective graph augmentations. Then we theoretically prove that GCL is able to learn the invariance information by contrastive invariance theorem, together with our GAME rule, for the first time, we uncover that the learned representations by GCL essentially encode the low-frequency information, which explains why GCL works. Guided by this rule, we propose a spectral graph contrastive learning module (SpCo), which is a general and GCL-friendly plug-in. We combine it with different existing GCL models, and extensive experiments well demonstrate that it can further improve the performances of a wide variety of different GCL methods.

Revisiting Graph Contrastive Learning from the Perspective of Graph Spectrum
Nian Liu', Xiao Wangl.2, Deyu Bo', Chuan Shill2, Jian Pei
Beijing University of Posts and Telecommunications
Peng Cheng Laboratory
Simon Fraser University
(nianliu, xiaowang, bodeyu, shichuan| @bupt.edu.cn, jpei jpei@es.sfu.ca
Abstract
Graph Contrastive Learning (GCL), learning the node representations by aug- menting graphs, has attracted considerable attentions. Despite the proliferation of various graph augmentation strategies, some fundamental questions still remain unclear: what information is essentially encoded into the learned representations by GCL? Are there some general graph augmentation rules behind different aug- mentations? If so, what are they and what insights can they bring? In this paper, we answer these questions by establishing the connection between GCL and graph spectrum. By an experimental investigation in spectral domain, we firstly find the General grAph augMEntation (GAME) rule for GCL, i.c., the difference of the high-frequenee parts between two augmented graphs should be larger than that of wwwffreuunncy parts. This rule reveals the fundamental principle to revisit the current graph augmentations and design new effective graph augmentations. Then we theoretically prove that GCL is able to learn the invariance information by contrastive invariance theorem, together with our GAME rule, for the first time, we uncover that the learned representations by GCL essentially encode the low-frequency information, which explains why GCL works. Guided by this rule, we propose spectral graph contrastive learning module (SpCe"), which is a general and GCL-friendly plug-in. We combine it with different existing GCL models, and extensive experiments well demonstrate that can further improve the performances of wide variety of different GCL methods.
Introduction
Graph Neural Networks (GNNs) learn the node representations in a graph mainly by message passing. GNNs have attracted significant interest and found many applications [1]] 23 14]
Training
the high quality GNNs heavily relies on task-specific labels, while is well known that manually
annotating nodes in graphs is costly and time- mone-conuuming [10). Therefore, Graph Contrastive Learning (GCL) is developed as a typical technique for self-supervised learning without the explicit usage of
labels [28 36
The traditional GCL framework (Fig. (a)) mainly includes three components: graph augmentation, graph representation learning by an encoder, and contrastive loss. In essence, GCL aims to maximize agreement between augmentations to learn invariant representations (36). Typical GCL methods have
'Corresponding authors.
'Code available http://gittab.ccmm/uuuucntttccce
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(a)
A
Encoder
(b)
Embeiidin Hig
v;
Amplitutie s
High Low
Original Graph A
Contrastive Loss
Optimal Contrastive Pair
Augmentation
Enceder
Frequency
V2
Embadding Ha
V2
Figure 1: (a) The general framework of GCL. (b) The illustration of our findings in the empirical study (Section 3) If two contrasted graphs have a larger margin between nigh-frequency part than low-frequency part, they will boost the GCL. We call such two graphs optimal contrastive pair.
sought to elaborately design different graph augmentation strategies. For example, the heuristic based methods including node or edge dropping [32 feature masking [33], and diffusion [2] and the learn-
ing based methods including InfoMín [26 30 disentanglement [13], and adversarial training [31. Although various graph augmentation strategies are proposed, the fundamental augmentation mech- anism is not well understood. What information should we preserve discard in augmented graph? Are there some general rules across different graph augmentation strategies? How to use those general rules to validate and improve the current GCL methods? This paper explores those questions.
Essentially, an augmented graph is obtained by changing some components in the original graph and thus strength of frequencies (20) in graph spectrum. This natural and intuitive connection between graph augmentation and graph spectrum inspires us explore the effectiveness of augmentations from the spectral domain. We start with an empirical study (Section 3 to understand the importance of low-frequency and high-frequency information in GCL. Our findings indicate that both the lowest- frequency information and the gighffrequency information is particularly helpful to improve the performance of GCL. However, as shown in Fig. (b), the way of handling gegh-freuuncy information in two contrasted graphs V1 and V/2 should be different, which be finally summarized general graph augmentation (GAME) rule: the difference of amplitudes of high frequencies in two contrasted graphs should be larger than that of low frequencies.
information are important in GCL. Retaining more
To explain the GAME rule, we need to understand what information encoded into the learned representations by GCL. We propose the contrastive invariance (Theorem [. which, for the first time, theoretically proves that GCL can learn the invariance information from two contrasted graphs. Mcanwhile, can be seen in Fig. (b), because the difference of amplitudes of lowest-frequue wwweet-freuueccyy in- formation is much smaller than that of figguffry information, the lowest-frequency information will be the approximately invariant pattern between the graphs V1 and V/2 Therefore, with such two augmentations V/2 and V.2 we can conclude that the information learned by GCL is mainly the low-freed wwwfrreuencyy information, whose usefulness has been well demonstrated (6). This not only explains why GCL works, but also provides a clear and concise demonstration of which augmentation strategy better, verified by the experiments in Section 4
Based on our findings and theoretical analysis, we define two augmentations satisfying the GAME rule are called an optimal contrastive pair. Then, we propose novel spectral graph contrastive learning (SpCo), a general GCL framework, which can boost existing GCL methods with optimal contrastive pairs. Specifically, to ensure that the learned augmented graph is optimal contrastive pair with the original adjacency matrix, we need to make the amplitude of its high frequency ascend while keeping the low frequency the same the original structure. We model this process as an optimization objective based on matrix perturbation theory, which can be solved by Sinkhorn's 's Iteration 24 and finally obtain the augmented structure used for the following target GCL model.
Our contributions are summarized as follows. Firstly, we answer the question "what information learned by GCL and whether there exists general augmentation rule". To the best of our knowledge, this is the first attempt to fundamentally explore the augmentation strategies for GCL. from spectral domain. We not only reveal the general graph augmentation rule behind different augmentation

---

strategies, but also explain why GCL works by proposing the contrastive invariance theorem. Our work provides deeper understanding on the nature of GCL. Secondly, we answer the question "how to utilize the augmentation rule for GCI." We show that the augmentation rule provides novel insight to estimate the current augmentation strategies. We propose a novel concept optimal contrastive pair and theoretically derive a general framework SpCo, which is able to improve the performance of existing GCL methods. Last, we choose three typical GCL methods as target methods, and plug SpCo into them. We validate the effectiveness of SpCo on five datasets. We consistently gain improvements compared with those target methods.
2 Preliminaries
Let G = (V,E) represent an undirected attributed graph, where V the set of nodes and 5 C V V the set of edges. All edges formulate an adjacency matrix A {0, 1JNXN, where Aij {0, 13 denotes the relation between nodes and j in V. The node degree matrix D = diag(d)..... .dn). where d, Ejev Ai is the degree of node i V. Graph & is often associated with a node feature matrix X = [x], .2,...,,IN' E Rg where is a dimensional feature vector of node i E V. Let C= D be the unnormalized graph Laplacian of G. If we set symmetrie normalized adjacency
matrix as Á D à AD 2, then L In A D à (D A)D à is the symmetric normalized graph Laplacian.
Since é is symmetric normalized, its cigen-decomposition is UAUT, where A = diag(\ (A Ax) and U = [u] ,..., " E N are the eigenvalues and eigenvectors of L. respectively. Without loss of generality, assume S A S ... I AN < (where we approximate AN RS [I].. Denote by Fc (A1,-.. ( } the amplitudes of low-frequency components and by FH [ALN/2]+1,..... An the amplitudes of figu--reeueecc components. The graph spectrum is defined as these amplitudes of different frequency components, denoted as ((A), indicating which parts of frequency are enhanced or weakened [20]. Additionally, we rewrite L = Y1 "1 + +... AN uNuN. N. where we define term u.u, E IR Nx as the eigenspace related to A; denoted as S,
9 33 aims to learn discriminative embeddings without supervision, whose pipeline is shown in Fig. I(a). We summarize the representative GCL in Ap- pendix E Specifically, two augmentations are randomly extracted from A in predefined way and are encoded by GCN [ to obtain the node embeddings under these two augmentations. Then, for one target node, its embedding in one augmentation is learned to be close to the embeddings of its positive samples in the other augmentation and be far away from those its negative samples. Models built in this way are capable of discriminating similar nodes from dissimilar ones. For example, some use classical InfoNCE loss [19 as the optimization objective:
Graph Contrastive Learning (GCL) 28
graph contrastive methods [36] 32 35)
exp(O(h V4 h V22 )/T))
C(h
V2 log V1 h
(1)
exp(O(h)) h. //T) Σ exp(O(h)) h (/T)/))
where h.2 and h 22 are the embeddings of node under augmentations V1 and V2, respectively, is the similarity metric, such as cosine similarity, and 7 is temperature parameter. The total loss is
LInfoNCE = Σ 1/ (Ch V. n/2) c(h V2 nYt)).
3 Impact of Graph Augmentation: An Experimental Investigation
In this section, we aim to explore what information should be considered in two contrasted augmentations from the perspective of graph spectrum. Specifically, we design simple GCL framework shown in Fig. 2 Two input augmentations are adjacency matrix and generated V. Then, we utilize shared GCN with one layer as the coder to encode A and V and get their nodes embeddings as H A and Hv.We train the GCN by utilizing InfoNCE loss as in Eq. (T) More experimental settings can be found in appendix B.1
Adjacency
H
Shared
InfoNCE
Generated V
GCN
Hv
Figure 2: The case study model.
3

---

Generating augmentation V We construct the aug- mented graph by extracting information with different frequencies from the original graph, so that we can ana- lyze the effect of different information. This process is shown in Fig. [ Specifically, we divide the eigenvalues of into Fc and FH parts, and conduct augmentations in these two parts, respectively. Taking the augmentation
Augmentation
Augmentation in
in Fc for example, we keep the high-frequency part as uNuN- Then, gradually add the eigenspaces FC back with rates [20%, 40%, 60%, 80%), starting from the lowest frequency. There- fore, augmenting 20% in Fc is u1 Ui + N 0.2=N/2 UN/2 N/2 +....ttttt0 UNUN Similarly, V augmenting 20% in Fu is ii ... + "N/2" N/2 + (2
Figure 3: The generation of V.
No.7N Please note that we set graph spectrum of V, (v = 1, VA [0.2] above, in that we just want to test the effect of different u.u, and avoid the influence from eigenvalues À [8]
0.60
0.40
0.39
0.62
00.2
X 0.40
0.50
0.51
0.30
0.33
0.50
0.59
U
0.33
0.35
025
0.30
0.25
0.56
0.20
20
0.45
0.30
0.30
0.53
02:
Adction Ratell61
Addtion Rater 96)
Adotion Rate!16)
Addtio Rater
(a) Cora
(b) Citescer
(c) BlogCatalog
(d) Flickr
Figure 4: The results of case study four datasets. The x-axis means different addition rate of different frequency interval, and y-axis means the performance on ACC. The performance of augmentations in Fc plotted the left y-axis, and in Fx plotted the right y-axis.
Results and analyses We conduct the node classification on four datasets: Cora, Citeseer [Л. BlogCatalog, and Flickr [6]. The accuracy (ACC)
shown in Fig. 4 In appendix B.2 we also report the results when both high and low frequency components are added back in the high-to-low
Amplitude
frequency order. Results. For each dataset, in generated V. (1) when the lowest part of frequencies are kept, the best performance is achieved; (2) when more frequencies in F& are involved, the performance generally rises. Analyses. From the graph spectra of A and V shown in Fig. 5 we can see that in generated V. (1) when the lowest part of frequencies kept, the difference of amplitude, i.e., the graph spectrum, between A and V becomes smaller; (2) when more frequencies in FH involved, the margin of graph spectrum in Fx between A and becomes larger. Combining results and observations, we propose the following general Graph AugMEnnation rule, called GAME rule
Frequency
Fc
Figure 5: The spectrum of A and V.
The General Graph Augmentation Rule
Given two random augmentations V1 and V2, their graph spectra are Φv; (X) and Φv, (A). Then, V Am E [1,2] and X, [0, V1 and V2 are effective pair of graph augmentations if the following condition is satisfied:
f (Am.) - Φv, (Am)) l > |&v; (An) - Φv, (2n)).
We define such pair of augmentations optimal contrastive pair.
Althooghh this rule is derived from contrasting A and V. the selection of certain views does not curb the generality of GAME rule. Considering that most of augmentations are obtained from the raw adjacency matrix A. it is natural setting that one view is fixed A and the other is augmented one.

---

4 Analysis of The General Graph Augmentation Rule
In this section, we aim to verify the correctness of GAME rule that whether two contrasted aug- mentations satisfying GAME rule can perform better in downstream tasks from experimental and theoretical analysis.
Experimental analysis We substitute existing augmentations proposed by MVGRL [ GCA 36 and GraphCL 32 for augmentation V in the case. Specifically, MVGRL. proposes PPR matrix, heat diffusion matrix and pair- distance matrix. GCA mainly randomly drops edges based on Degree, Eigenvector and PageRank. GraphCL adopts random node dropping, edge perturbation and subgraph sampling. The nine augmentations almost cover the mainstream augmentations in GCL. To accurately depict the change of the amplitude after these augmentations for some A; we turn to matrix perturbation theory
25
AA: - X - u; AAu; X.u; ADu; + I[))A|]))
(2)
where X is the eigenvalue after change, AA A' A represent the modification of edges after augmentation, and AD the respective change in degree matrix. With Eq. ( we calculate the eigenvalues on Cora after each augmentation, and plot their graph spectra in Fig. 6 Simultaneously, we use the GCL framework in Section 3 to separately contrast adjacency matrix A and these augmentations, and results are shown in Table T As shown in Fig. 6 PPR matrix, Heat diffusion matrix and Distance matrix better accord with GAME rule, where they have small difference with A in Fc, and have large difference in Fr. Therefore, they outperform other augmentations in Table
Amplltde
Ampfituee
Laplocin Matrix
Ampittud
Frequency(A)
Frequenzy(k)
Frequincy)))
Ingelann
Egewacarr
Dapne
Aurehtuda
Frequency(A)
Anjacency
Ampitude
Frequency(A)
Frequenzy(h)
Frecuency(A)
Mode Jeopping
Suterphh
Eage Parubetion
Aireflude
Frequency(A)
Frequency(A)
Frequinzy(A)
Frecuency(A)
Figure 6: The graph spectra of laplacian, adjacency matrix and nine existing augmentations.
Table 1: Performance of different existing augmentations verify the GAME rule.
Methods
GraphCL
GCA
MVGRL
Type
Subgraph
Node dropping
Edge perturbation
Degree
PageRank
Eigenvector
PPR
Heat
Distance
29.12.33
37.71444
40.2..1
5.0
42.1149
3800
49.9
17.5
We also test the GAME rule in another circumstance, where contrast among three cases: A and A (two-hop A), and A, and A² and A?, The results are given in Appendix C
Theoretical analysis We have the following theorem to depict the learning process of the GCL.
Theorem 1. (Contrastive Invariance) Given adjacency matrix A and the generated augmentation V. the amplitudes of i-th frequency of A and V are X; and %, respectively. With the optimization of InfoNCE loss LinfoNCE, the following upper bound is established:
LInfoNCE I 1+N Σ 0g 2 - (2: - 7
where 0, an adaptive weight of the ith term.
Here, we do not use eigenvalue decomposition to obtain X' of A', because the obtained X' are unordered compared with previous À of A. That is to say. for certain X of A, we cannot figure out which eigenvalue of cannot calculate the change Aλ; for As in this case.
A' matches to it after decomposition,
5

---

The proof is given in the Appendix A. where we simplify GCN without the activation function. Theorem (indicattssss an upper bound of GCL loss, implying that maximizing the contrastive loss equals to maximize the upper bound. So, larger 0, will be assigned to the smaller (A, - 7:) or X RS "/- Meanwhile, if X; R "i. these two contrasted augmentations are regarded to share the invariance at ith frequency. Therefore, with contrastive learning, the encoder will emphasize the invariance between two contrasted augmentations from spectrum domain. To our best knowledge, theorem I for the first time, theoretically proves that GCL can capture the invariance between two augmentations. Please recall that GAME rule suggests that the difference between two augmentations in F& is smaller. Thus, under the guidance of GAME rule, GCL attempts to capture the common low-freee wwwfrequency information of two augmentations. Thus, GAME rule points out general augmentation strategy to manipulate encoder to capture low-frequency information, which achieves a better performance.
5 Spectral Graph Contrastive Learning
Based on the GAME Rule, we mainly aim to learn a general and GCI-friendly transformation A from adjacency matrix A to a new augmen- tation A_ (or A = A_ A), where A and A_ are required to be an optimal contrastive pair. Then, they are fed into existing GCL method 4 ie. augmenting with the same strategies of & to generate V1 and V/2 and training with the corre- sponding contrastive loss, shown in Fig. 7 The whole pipeline is our proposed spectral graph contrastive learning (SpCo), which can boost existing GCL methods.
Original Graph
AugmentictionV:
Aepinate
Target Model
Freguenc
Frejuenc
A
Groph A...
Augmentction V.
Aepinale
Frequenoy
Frequcnoy
Figure 7: Combine SpCo with existing GCL.
Firstly, we separate AA = - - where AAt and A indicate which edge added and deleted, respectively. Next, we indicate how to learn A AAt. while the calculation of A Based on our theoretical derivation in Appendix. A.2, the following optimization objective of AA+ should be maximized:
A- is similar.
= ==<C, AA+ > cH(AA+) + Sr<s..A - -
(3)
Matching Term
Entropy Reg.
Lagrange Constraint Conditions
This objective consists of three components: (1) Matching Term. V P.Q E NNNN < P.Q Eij PijQuj. To maximize < C, AAt >2, AAA should learn to "match" or be similar to C. In A.2 we define C- = Ug(A)UTT, where U and g(A) are eigenvector matrix and some function about eigenvalues of A. According to GAME rule, we set (A) ( A (A)), and we need ds (Am) da (Xn), v Am E [1,2] and An E [0.1]. Therefore, we stipulate that di d should be monotone increasing function. Since C will guide AA+ to capture the change of difference between graph spectra (Ø) (A)), we naturally set g()) of C also monotone increasing function. Furthermore, we notice that the graph spectrum of Laplacian C does meet our need about g()) (shown in Fig. 66) so simply set C OL, where θ is a parameter updating in training. (2) Entropy Regularization. Here, (P) = = Pr, (log( Pt,)) 1) 21], and is the weight of this term. This term aims to increase the uncertainty of the learnt AA+. which encourages more edges (entries in A A+) to join in optimization. (3) Lagrange Constraint Conditions. f E Nx1 and g E N x1 are Lagrange multipliers, and a E IR X1 and b E Nx1 are distributions II This term restrains the row and column sums of A A within some limitation.
Next, we expound how to solve eq.
(3). The partial of J with respect to A is as following:
aJ / ((AA+)is = < C, AAt > Cis - log( A A+ )is + f. + gj
(4a)
m.y + 2c,, AA++)s e clog( A )sp + f. + g5.
(4b)
where we separate 2C²; (A from 2 < C, A > Cij. and set the rest part as my- The next theorem points out when J can get the maximal value in the domain of definition (AA+)is E (0, 1):
We define a and b are both node degree distribution in this paper.

---

Theorem 2. Given (Aat)is (0, J exists the maximal value, iff
CI)
ti and f: + + maj or
2
(2) < C. exp( fitt; +. ) and f: 9, maj + < O.
We provide the proof in the Appendix A.3 Normally, we should let eq. (4b) equal to zero and get the analytical solution of (AA+)ú, However, eq. (4b) is a transcendental equation because of the coexistence of linear term and logarithm. Thus, we require eq. (4a) to equal to 0. As the training goes
on, A A+ does not change sharply. So, we firstly rewrite eq. (4a) as follows:
DJ 0( 2 D'A+ > Cij - e
+ + 9j.
(5)
Compared with eq. 4aa eq. 5 only replaces AA+ with D'A+ in the first term, where D'+ is obtained from the last training epoch, and frozen at the current epoch. In this case, the matrix form of solution of current epoch is:
AAt = diag(u) exp (2 < <C > C
))) = UUKKU
(6)
where U+ diag(u;)
diag( exp ( and V+ diag(v;) diag( ( exp [ calculate U+ and V+, we restrain the row and column sums of Aa+ according to Lagrange Constraint Conditions: u * (K+v) = a and v (KIu) b. We solve this matrix scaling problem [17 by Sinkhorn's 's Iteration [24]. which is shown in Algorithm | 4 There exists upper bound of the difference between A and D'At:
To further
Theorem 3. After Sinkhorn's 's Iteration, the bound between A and D' is:
[a(Aa+)i (Aa+)yl -ा- (d(r(0) aa) + d(c!o), b)} + axl + [mas]
where a = "0Tj V(x,x') E (RT)), x') is the Hilbert's projective metric (3] on R. q is
K( ( +), and is contraction ratio 77. (0)) and c are the row and column sum vectors of K K+-
The proof is given in Appendix A.4 The calculation of A is similar as D shown as follows:
A diag(u' exp (-2 < C, >c
C/ c diag(v') = U K V-,
where diag(u'). diag(v') and A'A- have the similar meanings as in eq. 66
Finally, we get the solution A = Á - A- utilizing eq. (6) and eq. mation A we can obtain the new augmentation A_ as:
With learnt transfor-
A = 1 S AA.
(8)
where *#* means element-wise product, and v is the combination coefficient. make A sparse, we use scope matrix S to limit our focus, e.g. one-hop neighbors for each node. The whole algorithm is given Algorithm
Algorithm 1: Sinkhorn's 's Iteration
Algorithm 2: The proposed SpCo
Input : Matrix K. distribution
Input : augmentation Augo. A, L. X Params: Total epochs T, update epochs 22, S, 7). θ, a and b
a E IR Nx and b E Nx1
Params: : Iteration number Iter Output : (or AA-)
for i = 1 to T do
Initialize
2
C OC:
u 1//, ..... 1/NJIxN; K = chags((1/o)) K:; K;
3
Calculate K K_ in eq. (6)
4
Get A A / A A- through Algorithm
for
Iter do 1./K (b/K u):
5
A_ = A + m A Is with eq.
6
Update O;
for j 1 to l do
end
b/ KT u;
8
V1, 1/2 Augo (A), AAg)
7 A / A = diag(u u) K diag(u));
9
Train (VV, X);
end
8 return AA+/DA-:
11 end
7

---

Experiments
In this section, we mainly evaluate the performance of proposed SpCo on five datasets: Cora,
Citeseer, Pubmed [i]]. BlogCatalog and Flickr [6]. Details of datasets are in Appendix D.2
We
select two categories of baselines: supervissd GNN models (GCN M GAT [27 and
representative graph contrastive learning methods (DGI (28), MVGRL 19. GRACE [5], GCA [3).
GraphCL [32], CCA-SSG [3]] These GCL methods can divided into three categories based on
their contrastive losses: BCE loss (DGI, MVGRL), InfoNCE loss (GRACE, GCA, GraphCL. and CCA loss (CCA-SSG).
verify the applicability our SpCo, we select one baseline from each
category (DGI, GRACE and CCA-SSG) to integrate with SpCo. The detailed descriptions of DGI, GRACE and CCA-SSG are given in Appendix D.6 Experimental implementation details are given in Appendix D.1
Table 2: Quantitative results (% node classification.
Datasets
Metrics
GCN
GAT
DGI
DGI+SpCo MVGRL
GRACE
GRACE+SPCo
GCA
GrupbCL
CCA-SSG
CCA+SpCo
Mr-F1
79.6+0.7 81.3+0.
80.40077
81.1+0.5
81.500.5
79.2+1.0
80.3+0.8
79.9=1.1
80.7-0.9
82,9+0.8
83.620.4
Coma
Mi-FI
80.710.6
62.3u0.2
82.020.5
82.810.7
82.810.1
$0.011.0
81.210.9
62.3.0.9
83.620.9
Ma-FI
68.120.5
67.520.2
67,720.9
68.340.5
66 66.820.7
65.121.2
65.110.8
62.821.3
67.821.0
67.921.0
68.5:1.0
70.9.0.5
72.0e0.9
71.7=0.8
72.4+0.5
72.5+0.5
68.7+1.1
71.9=0.9
73.1+0.7
Ma-FI
71.261.2
67 622.2222
68.2=1.3
71,5+008
80.363.6
67.7a1.2
68.2+0.4
71.7:0.4
63.9c2.1
72.0k0.5
72.8stk.
BlogCotalog
Mi-FI
72.1a1.3
68.3+2.2
68.8=1.4
72.3+0.9
80.9
68.5
69.4+1.3
72.720.5
64.622.1
73.020.5
73.720.3
Ma-F1
48.961.6
35.0H0.8
31,2=1.6
33.749.7
31.2+2.9
35.7+1.3
36.3+1.4
41,260.5
32.1=1.1
37.0+1.1
38.750.6
Hllkkr
Mi-FI
50.261.2
37.1
33.0=1.6
35.2+0.7
33.4+3.0
$7.3+1.0
38.1+1.3
42/2+0.6
34.5=0.9
39.3+0.9
40.4
78.540.3
76.820.9
77.620.6
79.810.4
$0.010.7
80.340.3
80.710.6
PubMed
Mi-FI
78.9e0.3 77. 17.8.01.2 76.7=0.9
77.4+0.5
79.7=0.3
79.940.7
80.7+0.2
81.4m0.6
76.8e00.5
81.0+0.6
81.5+00.4
6.1
Node classification
To more comprehensively evaluate our model, we use two common evaluation metrics, including Macro-F1 and Micro-F1. The results are reported in Table 2 where the training set contains 20 nodes per class. As can be seen, the proposed SpCo can generally improve the performances of the corresponding original models on all datasets, which verifies that SpCo is widely applicable and effective. We also choose 5 and 10 labeled nodes per class as training set respectively. which are reported in Appendix(... D.4.1
A A
Specttal Coefficient
V
Spectral Coefficient i- a
1/
Spectral Coefficient 1.
0
Eigenvalue (N)
Eigenvalue (M
Eigenvalue lue
(a) DGI: Citeseer
(b) GRACE: Citescer
(c) CCA-SSG: Citescer
Figure 8: The visualisation of graph spectrum on Citeseer.
6.2 Visualisation of graph spectrum
In this section, we test the learnt view A_ and A meet the GAME rule. We plot the graph spectrum of A_ A, V1 and V2 in one figure for each method on Citeseer, which are shown in Fig. g Here. we discard the impact of self-loop operation. For DGI, does not use topological augmentation. Therefore, only plot A_ and A for it. For GRACE, the augmentation strength of V1 is set O. Thus, the plot of V1 is same with A. From the figures, we can see that the difference between A_
Although in DGL, the authors summary vector to depict the global view. this summary vector does not reflect any graph structure, thus think DGI does not have special augmentation strategies topology.

---

and A is smaller in Fc than in Fr, which proves that they are optimal contrastive pair. Meanwhile, they can drive 11 and V22 also to obey the GAME rule, and thus boost the final results. More results on Cora are given in Appendix D.4.2
6.3 Hyper-parameter sensitivity
In this subsection, we systematically investigate the sensitivity of two parameters: matrix C and e. We conduct node classification on Cora and BlogCatalog datasets and report the Micro-F] values. More experiments of paramerrssssssss are given in Appendix D.4.3
Analysis of C. The matrix di- rectly affects the final structures of the AA+ and A- Therefore, we give three kinds of C: I + C, L and
ltL
0.84
0.74
Evaluation
0.83
Evsluation
0.72
0.82
I + L + L² and corresponding re-
0.81
0.70
sults are shown in Fig. 99] From the
figures, we can see that L is the best choice compared with two candidates. So, use OL C. Other well- designed C can also replace L here.
0.80
DGI
GRACE CCA-55G
0.68
DGI
GRACE CCA-SSG
(a) Cora
(b) BlogCatalog
Figure 9: The comparison between three candidates for C.
Analysis of c. The in eq. (3 controls the strength of entropy regularization, and in eq. ( also controls the smoothness of exponential. We vary the value of it and plot the results on BlogCatalog in Fig. 10 From the results, know that is sensitive parameter for SpCo. If is too small, the effect of entropy term will diminish. And if e too large, the entropy term will interfere the molding of new structure. More results on Cora are given in Appendix D.4.3
0.725
Test F1-micro
0.720
ho1e
0.594
Test F1 1--mcrro
0.736
0.757
0.715
4714
0.25
0.691
5,533
0.733
F1
800
axpr
0.685
6,729
0,000
0.727
5e.2 16.2 5e:3 1c.3 5e
16:4
5e 1c:1 5e.2
1e Se 10:3
Se 16:2 58 1o 5e Ic44
The value of
The value of
The value of
(a) DGI: BlogCatalog
(b) GRACE: BlogCatalog
(c) CCA-SSG: BlogCatalog
Figure 10: Analysis of the hyper-parameter c on BlogCatalog.
Conclusion
In this paper, we fundamentally explore the topological augmentation of GCL from spectral domain. We propose contrastive invariance theorem, and discover general augmentation (GAME) rule, which deepen our understanding of the essence of GCL. Then, we propose a general augmentation plug-in based on GAME rule, SpCo, to boost existing GCL methods. Extensive experiments verify the effectiveness of SpCo.
Limitations and broader impact. On potential limitation is that this work mainly focuses on the homophily graph, rather than the heterophily graphs [1] where high-frequency information is more useful. Despite the great development of GCL, some theoretical foundations are still lacking. Our work points out the great potential of graph spectrum in GCL, and may open new path to understand and design GCL. Other than that, we do not foresee any direct negative impacts on the society.
Acknowledgments and Disclosure of Funding
This work is supported in part by the National Natural Science Foundation of China (No. U20B2045. 62192784, 62172052, 62002029, U1936014).

---

References
[1] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequent frequency information in graph convolutional networks. arXiv preprint arXiv:2101.00797, 2021.
[2] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In 2nd International Conference on Learning Representations, 2014.
[3] Peter Bushell. Hilbert's 's metric and positive contraction mappings in a banach space. Archive for Rational Mechanics and Analysis, 52((): 1973.
[4] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
[5] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in Neural Information Processing Systems 29: Annual Conference Neural Information Processing Systems 2016, pages 3837- 3845, 2016.
[6] Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks graphs. In Proceedings of the 1 13th International Conference on Web Search and Data Mining, pages 169-177, 2020.
[7] Joel Franklin and Jens Lorenz On the scaling of multidimenssonal matrices. Linear Algebra and its applications, 14:7177733, 1989.
[8] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1025-1035, 2017.
[9] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In ICML, pages 4116-4126, 2020.
[10] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint arXiv: 1905. /2265, 2019.
[11] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICIRR 2017.
[12] Namkyeong Lee, Junseok Lee, and Chanyoung Park. Augmentation-fiee self-supervised learning graphs arXiv preprint arXiv:2112.02472 2021.
[13] Haoyang Li, Xin Wang. Ziwei Zhang, Zehuan Yuan, Hang Li, and Wenwu Zhu. Disentangled contrastive learning on graphs. Advances in Neural Information Processing Systems, 34, 2021.
[14] Hu Linmei, Tianchi Yang, Chuan Shi, Houye Ji, and Xiaoli Li. Heterogeneous graph attention networks for semi-supervised short text classification. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLE) pages 4821-4830, 2019.
[15] Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1): 444, 2001.
[16] Zaiqiao Meng, Shangsong Liang, Hongyan Bao, and Xiangliang Zhang. Co-embedding attributed networks. In Proceedings of the twelfth ACM international conference web search and data mining, pages 393-401, 2019.
[17] Arkadi Nemirovski and Uriel Rothblum. On complexity of matrix scaling. Linear Algebra and its Applications, 302:435-460, 1999.
[18] Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: 2019.
10

---

[19] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint 1XX::1807.03748, 2018.
[20] Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808 828, 2018.
[21] Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport. Center for Research in Economics and Statistics Working Papers, (2017-86). 2017.
[22] Gabriel Peyré. Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends Machine Learning, 11(5-6):355-66 2019.
[23] Weijing Shi and Raj Rajkumar. Point-gnn: Graph neural network for 3d object detection in a point cloud. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 1711-1719, 2020.
[24] Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. The annals of mathematical statistics, 35(2):876-879 1964.
[25] Gilbert W Stewart. Matrix perturbation theory. 1990.
[26] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning, Advances in Neural Information Processing Systems, 34, 2021.
[27] Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
[28] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. arXiv preprint arXiv:1809. 2018.
[29] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip Yu. comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn. Syst., pages 4-24, 2021.
[30] Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information-aware graph contrastive learning. Advances in Neural Information Processing Systems, 34, 2021.
[31] Longqi Yang, Liangliang Zhang, and Wenjing Yang. Graph adversarial self-supervised learning. Advances in Neural Information Processing Systems, 34, 2021.
[32] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances Neural Information Processing Systems, 33:5812-5823, 2020.
[33] Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu. From canonical correlation analysis to self-supervised graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
[34] Ziwei Zhang, Peng Cui, Xiao Wang, Jian Pei, Xuanrong Yao, and Wenwu Zhu. Arbitrary- order proximity preserved network embedding. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pages 2776, 2018.
[35] Yanqiao Zhu, Yichen Xu, Feng Yu. Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning, arXiv preprint arXiv:2006. 04131, 2020.
[36] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW, pages 2069-2080, 2021.
11

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 7
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] We include the code, data, and instructions the supplemental material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section @ and Appendix
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] See Section 6.1 and Appendix D.4.1
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix D.5
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [No] We were unable find the license for the assets we used.
URL? [Yes] (d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A] The datasets are public benchmarks.
(c) Did you include any assets either in the supplemental material
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] The datasets are public benchmarks.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "kTXy6OstLRj", "reviewer": "Reviewer_3xAc", "summary": "The paper notes prior work on Graph Contrastive Learning (GCL), then proposes a new concept based on which to produce the contrasting graph: by focusing on changing the spectrum of the graph. In particular, the authors assert the \"GAME rule,\" which roughly states that a good contrastive pair of graphs differs more in high-frequency components than in low-frequency ones. They then run an experiment on real-world graphs to support this assertion, followed by proof of a theorem upper bounding the GCL loss, which also suggests application of the GAME rule. The authors then theoretically derive their SpCo algorithm, which allows for producing contrasting graphs in a manner that obeys GAME, and perform experiments to show that it (1) can improve prior methods' performance and (2) indeed produces graphs which tend to obey GAME. ", "questions": "Based on the Figure 1(b) and Figure 6, the modified $\\mathbf{A_-}$ looks somewhat like a low-pass filtered version of $\\mathbf{A}$. Have the authors confirmed that setting $\\mathbf{A_-}$ to just be a low-pass filtered version of $\\mathbf{A}$ will not work as well?\n\nI found the description of the experiment in Section 3 difficult to understand. Is there perhaps a mistake in Lines 125-126 or Figure 3? I don't see how the addition rate can go up to 80%; based on the description, it seems like it should only go up to 50% at most. Also, why are the eigenvalues ignored and set to 1? Finally, it seems a bit strange that both high and low frequency components are added incrementally in the low-to-high frequency order.\nIt also seems like this section in general should go after the experimental setup, e.g., hyperparameters and how link prediction is done, has been fully described.\n\nI have similar issues with the other experimental sections. It would be helpful to clearly describe the motivation, the full setup, and how the results support the conclusion.\n\nThe statement of Theorem 1 could be more rigorous: For what network model is the loss minimized? (This is stated, with fairly strong assumptions, but only in the appendix.) And what is meant by 'limited value'?\n\nThe theory work in Section 5.1 is quite dense, and could use more discussion of the intuition behind the steps. I recommend moving most of it to the appendix, just keeping a sketch in the main work, and moving Algorithm 2 into the main work, making the algorithm description more self-contained (i.e., naming all parameters, including $\\Theta$ and $\\epsilon$, and describing how Eq. 8 and 10 are implemented), and providing more discussion of the intuition of the algorithm.\n\nMinor comments:\n+ Line 85: Typo on equation for unnormalized Laplacian (should be degree, not identity matrix)\n+ Line 94: Typo \"weaken\" -> \"weakened\"\n+ Line 131: \"the performance achieves the best\" -> \"the best performance is achieved\"\n+ Line 136: \"specturm\" typo\n+ Line 142: \"with both of\" typo\n+ Line 176: \"tempt\" -> \"attempt\" typo?\n+ It wasn't clear to me what is meant by \"samples\" (Line 102) in the explanation of GCL, especially since the example loss in Equation 1 does not seem stochastic.", "limitations": "The authors note the limitation that the work is only applicable to homophilous graphs, not heterophilous ones, which is a useful remark. They could additionally note the assumptions required for the main theory result.\nThere is not much discussion of potential negative societal impacts beyond that the statement this work could improve GCL methods in the future; there is some possibility, if desired, to discuss potential negative societal impacts of improved GCL methods.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ The paper attempts to advance understanding and application of a recently-popular type of method, GCL.\n+ The core idea, at least as described, of using contrastive pairs which mostly preserve low-frequency information while allowing high-frequency information to change seems reasonable and interesting.\n+ The paper seems to ground its ideas in theory.\n\nWeaknesses\n+ Descriptions of some ideas, procedures, and experimental setups are unclear.\n+ Descriptions are also rather dense at times, leaving me with a limited idea of the motivation and intuition.\n\nNotes\n+ It is difficult for me to evaluate the soundness of the paper given the presentation issues discussed below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "f864OgaOwvH", "reviewer": "Reviewer_Zdi6", "summary": "In this work, the high-frequency and low-frequency information are explored in the graph contrastive learning framework. The graph augmentation strategies are investigated from the spectral domain. A new spectral graph contrastive learning method is proposed based on the matrix perturbation theory. Experiments on five datasets show the model effectiveness.", "questions": "What are the specific parameter settings of compared baselines in the performance comparison section?\n\nHow is the model scalability of the new proposed SpCo component when integrating with the existing graph contrastive learning methods?\n", "limitations": "The detailed setting descriptions of compared baselines are missing in the evaluation section. For example, for the baseline DGI and GRACE, how the model depth is configured for performing the message passing. What is the graph scale in DGI to generate the graph-level representation for self-supervised learning task.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.The studied problem is very interesting and important for research works on graph contrastive learning.\n2.The conducted experiments are comprehensive by demonstrating the effectiveness of the new proposed SpCo method in improving the graph representation performance.\n3. Hyperparameter studies are provided to show the sensitivity of parameters.\n\nWeaknesses:\n1. The detailed parameter settings of compared baselines can be described to better understand the performance superiority of the new proposed SpCo method.\n\n2. It would be better to perform analysis on the computational cost of the new proposed SpCo component in graph contrastive learning paradigm.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Qv_GU92z8uB", "reviewer": "Reviewer_gfze", "summary": "This paper discusses the reason that some contrastive learning methods work well in the view of graph spectrum. Based on their survey, the authors proposed the general graph augmentation rule (GAME rule) which defines what kind of pair of augmentations is optimal contrastive pair. Finally, they proposed a plug-in method for graph augmentation based on this rule. The experiments and theoretical analysis show the effectiveness of the proposed approach.", "questions": "1. In Table 2, why not report the experiments of MVGRL/GCA/GaphCL + SpCo?\n2. In line 151, “With Eq. (2), we calculate the eigenvalues on Cora after each augmentation”, where the eigenvalues on Cora could be directly obtained, how Eq. (2) is used here?\n3. In line 167, it was mentioned that “In other words, the invariance of two augmentations is enhanced from the point of view of graph spectrum.” The details were limited, and more explanations should be provided.\n4. It seems that the proposed SpCo focuses on the high-frequency information, but actually, GNNs often face over smoothing because of the low-frequency information. So, can this method eliminate the over smoothing problem?\n\nSome typos:\n- In line 178, \"we use ‘*’ to\" -> \"we use `*’ to\".\n-  In lines 179, 194, \"eq.\" -> \"Eq.\".\n- Some notations are not consistent, for example $\\bf{u}$_i in Eq. (3a).", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths：\n- This paper is well structured. The authors first propose problems, then analyze them with extensive experiments, and finally resolve these issues through the proposed method and theorem, which makes this paper can be well understood. \n- The analysis of graph contrastive learning with a graph spectrum view is interesting, which provides a new aspect for GCL.\n- The experiments and theories are sufficient to demonstrate the effectiveness.\n\nWeaknesses：\n- Although the paper is well structured, it is difficult to understand some theorems and formulas. The notations used in the paper is too complex, more explanations and working principles of the proposed method should be given.\n- From Table 2, the performance improvement of SpCo is very limited comparing to the other methods by taking into account the corresponding standard deviation values.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ID7AumMbzn", "reviewer": "Reviewer_ndDo", "summary": "In this paper, the authors explore the topological augmentation of GCL from the spectral domain. Based on a series of theoretical analysis, they propose a contrastive invariance theorem and discover a general augmentation (GAME) rule. Then, they propose a general augmentation plug-in based on the GAME rule, i.e., SpCo, to boost existing GCL methods. Extensive experiments verify the effectiveness of SpCo.", "questions": "For the questions and suggestions, please refer to W1—W5.\n", "limitations": "Yes.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\nS1: The problem of graph contrastive learning is important and interesting.\n\nS2: The proposed method has a theoretical basis.\n\nCons:\n\nW1: The notations in this paper is confusing. For example, in Line 80 and Line 81, $\\xi$ -> $\\mathcal{E}$, N -> $\\textit{N}$, $\\textbf{A}$ -> $\\textbf{\\textit{A}}$.\n\nW2: The proposed method has a serious limitation. In the paper, the authors fix one of the two views as the raw adjacency matrix, but do not discuss the two augmented views; in addition, some other augmentation operations (such as feature masking) are not discussed.\n\nW3: Incomplete experiments. Apart from node classification, graph classification is one of the important tasks in graph contrastive learning. However, in this paper, the authors only show the results on node classification and ignore graph classification. In addition, in Table 2, why do not use MVGRL+SpCo (considering that MVGRL seems to be the best baseline used in this paper)?\n\nW4: No proof of 'optimal contrastive pair'. In Figure 1 and other parts, the authors say that 'optimal contrastive pair'. How to prove its optimality? If not, please replace 'optimal' with other words.\n\nW5: Unclear experimental description. For example, In Table 1, the authors do not state what dataset is used in the experiment; in Figure 3, what is the meaning of 'ACC'?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G5cuQV4SIzL", "reviewer": "Reviewer_g6CU", "summary": "This paper mainly focuses on a fundamental problem in graph contrastive learning (GCL) domain, which is dedicated to design a general augmentation rule to uplift the performance of current GCL frameworks. The authors first commence from a complete case study to figure out a general augmentation rule, GAME rule, with a contrastive invariance theorem. Then, to practice this rule, the authors design the SpCo architecture, a general plug-in by plentiful and rigorous derivation. They also conduct adequate experiments to demonstrate the effectiveness of SpCo and analyze some relative characters.", "questions": "1. As mentioned above, the authors should give more descriptions about theorem 3. \n\n2. The figure 1(a) draws a skeleton about general framework of GCL, but I notice some components are neglected, like projection head and feature mask. \n\n3. This paper mainly starts from InfoNCE loss, while BCE loss used by DGI is another main branch in GCL. So, what will the result should be for BCE loss? \n\n4. This paper argues that the difference between low-frequency parts between two views should be smaller than that of high-frequency parts to reduce the negative impact of high-frequency parts. If so, can we directly filter out the high-frequency parts and only keep the low-frequency parts to achieve the same goal?\n\n 5. I notice that the authors utilize Sinhorn’s Iteration, which involves some matrix multiplication operations. I worry about the computational complexity.", "limitations": "Yes, the authors have addressed the limitations and potential negative societal impact of their work.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Motivation: As claimed in the paper, there lacks a deeper insight concerning about a general rule behind various augmentations. This is a core and valuable problem for GCL, and this paper has made a beneficial step towards this target.\n\n2. Methodology: This paper proposes the GAME rule and follows it to devise SpCo framework. Each part is supported by adequate theorems and derivations, which contributes to this technically solid paper.\n\n3. Experiments: The authors employ extensive experiments, where the base models see various degrees of improvement.\n\n4. Contexture: This paper is well-organized, and the literature is coherent and readable. Meanwhile, the illustrations are esthetic and concise enough.\n\nWeakness:\n1. As pointed out in conclusion, this paper seems only effective to homophily graphs, but failed to heterophily graphs. Anyway, this flaw is not so severe, since homophily is a basic assumption in unsupervised settings. I suggest the authors to further promote this paper to adapt to each case flexibility.\n\n2. The proposed contrastive invariance theorem seems a little limited. For example, the authors restrain two augmentations as A and V, rather than two random augmentations. It may be a higher requirement.\n\n3. Some details are not explained so clearly. For instance, followed by theorem3, there are some descriptions about its function, which is a little unclear.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept