Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper investigates how can graph SSL methods work well. Specifically, they first perform a generalization analysis for generic graph data augmentations based on dataset recoverability and separability constraints. Also, they observe that generic graph augmentations adopted in GraphCL do not introduce meaningful invariance. And then, they introduce a designed data generation process to control the amount of content vs. style in samples, which enables to empirically evaluate oracle augmentations. 
strengths_and_weaknesses: **Strengths**

[+] The paper is well-organized and easy to follow.

[+] The empirical and analytical framework is reasonable.

[+] The codes for reproducing the reported results are provided.

[+] This work shows some insightful opinions on data augmentations in graph contrastive learning. Also, they provide a useful benchmark to better evaluate oracle augmentations.

**Weakness**

[-] Previous works on content-aware augmentations [1] or implicit augmentations [2] in graph contrastive learning should be discussed.

[-] The technical contributions are limited. The content-aware augmentations in this paper only work well in the generated toy dataset.  How can the empirical and analytical framework help us develop more effective graph data augmentations or more powerful graph URL algorithms for practical graph data? 

[-] Studying data augmentations in self-supervised learning from a 'content vs. style' perspective has been performed in previous works [3].

[-] I notice that the codes (Readme file) uploaded by the authors include some personal information. If the authors use the open-sourced pyGCL framework, they should cite the paper [4] to violate the anonymity rules. 

[1] MoCL: Contrastive Learning on Molecular Graphs with Multi-level Domain Knowledge, KDD 2021.

[2] SimGRACE: A Simple Framework for Graph Contrastive Learning without Data Augmentation, WWW 2022.

[3] Self-Supervised Learning with Data Augmentations Provably Isolates Content from Style, NeurIPS 2021.

[4] An Empirical Study of Graph Contrastive Learning, NeurIPS 2021 (Datasets and Benchmarks track)


questions: See the weakness above.
limitations: The authors has adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper performs systematic and quantitative analyses on the relationship between properties of generic graph augmentations and model performance by deriving the generalization error bound. Analyses and empirical results show that commonly used GGAs do not necessarily lead to task-relevant invariance. Further experimental studies with proposed synthetic data generation indicate benefits from recoverable augmentations.
strengths_and_weaknesses: \+ To my knowledge, while adopting existing concepts such as recoverability and separability as a tool, the paper performs the first study to quantitatively study the relationship between measured augmentation properties and the performance (error bound) of SSL methods.

\+ The proposed theory and its derivation is quite solid. And the empirical results are insightful.

\- The authors claim that the analysis motivate the necessity of ask-aware augmentations one of their contributions. In fact, the conclusion has been derived from existing studies such as Tian et al. [16] from the mutual information prospect of view, i.e., the worst performance is achieved when there is no task-relevant mutual information overlapping MI of two views. A discussion on the differences and connection of the two groundings could strengthen this as a contribution.

\- The study mainly focus on the theoretical analysis specifically regarding the GGA in contrastive learning (SpecLoss). The title can be made more specific accordingly to avoid potential over-claim or misleading. Moreover, while strict derivation is not necessary, it'd be better to include discussions regarding how/whether the recoverability and separability can be adopted in predictive methods (or objectives other than SpecLoss) with augmentations (e.g., Section 4.2 of [1*]).

[1*] Xie, Yaochen, et al. "Self-supervised learning of graph neural networks: A unified review." IEEE Transactions on Pattern Analysis and Machine Intelligence (2022).
questions: The analysis specifically focuses on the SpecLoss. How would specifically implemented labeling functions and learning objectives (quantitatively) affect the error bound (or can their error bound be derived specifically)? For example, BYOL is different to typical contrastive methods as it does not require negative pairs but experimental studies still include BYOL.
limitations: n/a
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 theorectically demonstrates why task-relevant graph augmentation is required, using the concept of Graph Edit Distance (GED). In experiments, they showed that existing generic graph augmentation induce limited task-relevent invariance, revealing the error of common graph augmentation practice. To prove their theoretical analysis, they generate synthetic data and show content aware augmentation (task relevant augmentation) improves model performance.
strengths_and_weaknesses: Strengths
- This paper has strong theoretical background.
- Also, to my best knowledge, this work is the first attempt to analyze graph augmentation in terms of Graph Edit Distance (GED).
- Authors demonstrate their theoretical analysis through experiments on synthetic datasets.

Weakness 
- Paper is hard to read. Specifically, concept of invariance, recoverability and separability should be more clearly defined. Moreover, definition of task relevant augmentation / augmentation that induces invariance to task-irrelevant attributes is not clear.
- Practicality is limited. Different from image data, it is hard to dichotomously divide style and content in graph domain. I think this is the reason why authors couldn't show the correlation between invariance and accuracy in real-world dataset.
 
questions: - In Assumption 3.3, can the similarity of representation be guaranteed simply with correct classification?
- Is this theoretical analysis only applicable for SpecLoss?
limitations: This work provides theoretical analysis in common practice of graph augmentation. However, it would be better if the authors could validate the practicality of the proposed method, i.e., to real-world graphs.
review_title: null

Meta-review: metareview: Overall the reviews are positive, appreciating the proposed theory, derivation, and presentation. Also some concerns raised are properly addressed during the discussion period. Hence, I recommend the accetance of this paper. 
confidence: Certain
Decision: Accept