Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
1.The studied problem is very interesting and important for research works on graph contrastive learning.
2.The conducted experiments are comprehensive by demonstrating the effectiveness of the new proposed SpCo method in improving the graph representation performance.
3. Hyperparameter studies are provided to show the sensitivity of parameters.

Weaknesses:
1. The detailed parameter settings of compared baselines can be described to better understand the performance superiority of the new proposed SpCo method.

2. It would be better to perform analysis on the computational cost of the new proposed SpCo component in graph contrastive learning paradigm.

questions: What are the specific parameter settings of compared baselines in the performance comparison section?

How is the model scalability of the new proposed SpCo component when integrating with the existing graph contrastive learning methods?

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.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Pros:

S1: The problem of graph contrastive learning is important and interesting.

S2: The proposed method has a theoretical basis.

Cons:

W1: 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}}$.

W2: 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.

W3: 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)?

W4: 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.

W5: 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'?
questions: For the questions and suggestions, please refer to W1—W5.

limitations: Yes.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: Strengths
+ The paper attempts to advance understanding and application of a recently-popular type of method, GCL.
+ 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.
+ The paper seems to ground its ideas in theory.

Weaknesses
+ Descriptions of some ideas, procedures, and experimental setups are unclear.
+ Descriptions are also rather dense at times, leaving me with a limited idea of the motivation and intuition.

Notes
+ It is difficult for me to evaluate the soundness of the paper given the presentation issues discussed below.
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?

I 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.
It 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.

I 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.

The 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'?

The 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.

Minor comments:
+ Line 85: Typo on equation for unnormalized Laplacian (should be degree, not identity matrix)
+ Line 94: Typo "weaken" -> "weakened"
+ Line 131: "the performance achieves the best" -> "the best performance is achieved"
+ Line 136: "specturm" typo
+ Line 142: "with both of" typo
+ Line 176: "tempt" -> "attempt" typo?
+ 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.
There 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths：
- 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. 
- The analysis of graph contrastive learning with a graph spectrum view is interesting, which provides a new aspect for GCL.
- The experiments and theories are sufficient to demonstrate the effectiveness.

Weaknesses：
- 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.
- 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.
questions: 1. In Table 2, why not report the experiments of MVGRL/GCA/GaphCL + SpCo?
2. 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?
3. 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.
4. 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?

Some typos:
- In line 178, "we use ‘*’ to" -> "we use `*’ to".
-  In lines 179, 194, "eq." -> "Eq.".
- Some notations are not consistent, for example $\bf{u}$_i in Eq. (3a).
limitations: Yes
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
1. 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.

2. 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.

3. Experiments: The authors employ extensive experiments, where the base models see various degrees of improvement.

4. Contexture: This paper is well-organized, and the literature is coherent and readable. Meanwhile, the illustrations are esthetic and concise enough.

Weakness:
1. 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.

2. 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.

3. Some details are not explained so clearly. For instance, followed by theorem3, there are some descriptions about its function, which is a little unclear.
questions: 1. As mentioned above, the authors should give more descriptions about theorem 3. 

2. 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. 

3. 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? 

4. 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?

 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.
review_title: null

Meta-review: metareview: This paper had borderline reviews. The reviewers felt that the contributions were significant and that the connection between graph contrastive learning and spectral properties of the graph were valuable. Weaknesses included a focus on just node classification and some significant issues with presentation. The authors addressed many concerns presented and agreed to address the presentation issues. We hope that they will indeed do so in the final version of the paper, as the presentation issues would significantly limit the impact of the paper.

In our discussion one reviewer strongly advocated rejection, while three pushed for acceptance, putting the paper above bar.
confidence: Less certain
Decision: Accept