Venue: NeurIPS 2022 Conference

Reviews:

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 proposes a discrepancy-based framework to learn graph representations. The framework leverages the discrepancy between 1) the original graph and the perturbed graphs and 2) the original graph with other negative graphs. The discrepancy amount for perturbed graph is defined via graph edit distance, which is easy to obtain by perturbed graph generating process. The discrepancy amount for other negative graphs are defined above a margin. Under such discrepancy hierarchy, the learned graph representations could preserve dissimilarity among graphs accurately. The learned representations could be used for downstream tasks such as graph classification and link predictions in chemical and biological domains or social networks.
strengths_and_weaknesses: Originality
This paper proposes a new discrepancy preserved framework for learning graph representations, addressing limitations in existing literatures that would learn similar representations of two perturbed graphs with different properties. However, I would like to understand the novelty of the framework as how the discrepancy framework is different from redefining the similarity functions, e.g., sim(two perturbed graphs) = graph edit distance, and sim(graph, negative graph) = $\alpha$ + additional terms, and then use existing methods. Would appreciate if the authors could further clarify it.

Quality:
The paper is well written. The experiments are overall comprehensive, and additional analysis support the main points well.

Clarity:
The methodologies and implementation details are clearly explained in the main article and supplementary material.

Significance
As mentioned in the originality section, this paper uses discrepancy preserved framework to learn graph representations. However, my understanding is that authors define a new similarity function, which leverages the discrepancy among graphs. The significance is not quite obvious, and would appreciate authors' further clarifications.

questions: 1. This method has data augmented by generating perturbed graph via eq(5). I wonder is this a common approach for obtaining perturbed graph, or a novel part of this paper? For those contrastive learning method papers which also consider original graph and perturbed graphs, are the perturbed graphs being generated, or being found by calculating graph edit distance? 

2. This approach first generates perturbed graphs and defines discrepancy as graph edit distance. Then all the other samples are viewed as negative samples, and eq(7) assumes distance between original graph and negative graph is greater than a margin. This assumes that all the other graphs are very different from the original graph, at least not as some perturbation of original graph. I wonder could it be the case that in real data the graph samples already contains graphs similar to the original graph. For example, in Figure 1, (d) and (e) are two similar graphs in the samples, and the edit distance between (d) and (e) appear to be 1. Based on the proposed method, it will first generates some perturbed graph of (d), and then define distance of (d) and (e) greater than $\alpha$. In this example, distance(d,e)  > distance(d, perturbed graph of d), is this still a reasonable assumption? How the graph sample (e) different from those generated perturbation of (d)?

In summary, my question is: how the method differentiate the generated perturbed graphs, and the graphs that are similar to the original graphs in the sample? Will the assumption that all the other graphs are negative samples and have distance at least $\alpha$ actually disturb learning and makes the learning results worse, when they are actually similar to the original graph? Consider the extreme cases that the graph samples are all perturbations of one graph, what graph representations the proposed method would give?

3. How to choose the number of perturbed graphs n, and if the perturbed graphs samples are large, would the imbalance of two classes (1 vs n) affect the performance of classifier/discriminator?

limitations: The authors have discussed limitations thoroughly in the supplementary materials. I do not have other to add except the ones listed in Questions and Strengths And Weaknesses sections.
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 presents a novel self-supervised learning approach on graphs to boost up the performance on downstream graph classification tasks. In many scenarios, two graphs with highly similar structure have remarkably different properties ((i.e. belong to different classes). By design, the classical contrastive learning-based approaches fail to separate out the representations of such similar graphs because they aim to maximize similarity between graphs and their perturbations. To address these limitations, the authors propose a novel approach referred to as Discrepancy-Based Self-Supervised Learning(D-SLA) that comprises of multiple pretext tasks including: i) training a discriminator to distinguish between a real graph and a perturbed variant; ii) learning the exact discrepancy between the original and the perturbed graphs, where the discrepancy is measured as the graph-edit distance. Additionally, increase the discrepancy measure between any two real graphs by introducing a margin factor, thereby enforcing that the original graph is embedded closer to its perturbed variants than any other  similar-looking real graph. The proposed approach outperforms the SOTA approaches from contrastive learning and 
predictive learning literature on on several graph-related downstream tasks, including molecular property prediction, protein function prediction, and link prediction. 
strengths_and_weaknesses: Strengths: 
1. The proposed approach is quite plausible and likely to be relevant to biological networks and molecular graphs where two similar graphs could have distinct properties.
2. The approach outperforms or matches the performance of several baselines from the fields of predictive and contrastive learning approaches on both graph classification and link prediction downstream tasks.
3. The paper is overall well-written and augmented with informative figures.


Weaknesses: 
1. The approach involves a bunch of hyperparameters (e.g. the margin parameter \alpha, parameters \lambda_1 and \lambda_2 to determine the weight of each pretext task in the final objective function, max graph-edit distance considered to generate perturbed graphs). The paper does not include any guidelines on tuning these hyperparameters and how the choice of hyperparameters affect the results.

2. I  am not quite convinced if graph-discriminator pretext task is needed over L_{edit} and L_{margin}. (See my questions on table 5 below). It would be helpful if authors could throw insights on why all the three pretext tasks might be needed.


questions: 1. For ablation study in Table 5, there needs to be another variant where graph-discriminator is turned off, but the discrepancy modeling is on. This will justify the additional utility of graph discriminator over the discrepancy-modeling pretext tasks.
limitations: I will encourage authors to discuss more on the possible intuition behind the efficacy of the proposed approach. To my understanding, discrepancy modeling with margin factor for real graphs is indirectly helping the model to identify key features (edges or nodes) that if perturbed, could lead to a valid graph with distinctive properties. Identification of such distinctive nodes/edges could largely aid to the downstream task of graph classification. Is that correct? If so, perhaps authors should clearly articulate this clearly in the paper as it might not be obvious to readers.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper argues that existing graph self-supervised learning methods have some drawbacks. Specifically, predictive learning methods may not capture the global properties of graphs, and contrastive learning methods may not discriminate two similar graphs with different properties. To this end, a framework D-SLA is proposed to learn the exact discrepancy between the original and the perturbed graphs.
strengths_and_weaknesses: - Strengths
>    1. The drawbacks of existing graph self-supervised methods are well analyzed and demonstrated.
>    2. The visualization experiment shows that the proposed method is quite effective.
>    3. The provided source codes facilitate the good reproducibility of this work.

- Weaknesses
>    1. There are also some existing works that do not rely on contrasting perturbed graphs, e.g., [1,2,3]. In this case, the argued drawbacks of existing methods claimed by the authors do not seem to hold.
>    2. Why use Equation (4) to discriminate original graphs from perturbed graphs? This could be explained more intuitively.
>    3. The proposed method D-SLA consists of many components and many hyperparameters. The sensitivity of the three key hyperparameters $\alpha$, $\lambda_1$, and $\lambda_2$ should be studied in the main text.
>    4. Most existing works report AUC and AP scores for the link prediction experiment. This work only reports accuracy.


*References*

[1] [arXiv 2022] Augmentation-Free Graph Contrastive Learning

[2] [SIGIR 2022] Are Graph Augmentations Necessary Simple Graph Contrastive Learning for Recommendation

[3] [WWW 2022] A Simple Framework for Graph Contrastive Learning without Data Augmentation


questions: Please respond to the weaknesses listed above.
limitations: Yes. the authors have detailedly discussed the limitations and potential societal impacts in the appendix.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies the problem of self-supervised learning of graph neural networks. The goal is to learn representations for nodes and graphs in an unsupervised manner. The paper studies the limitations of the predictive and contrastive learning methods and proposes a new framework (D-SLA) to incorporate the discrepancy between the original and perturbed graphs in the self-supervised loss. D-SLA is tested for various tasks.
strengths_and_weaknesses: Strengths: 

1. Self-supervised learning is an important problem that has recently gained a lot of attention. 

2. The proposed method is tested on various tasks on several graph benchmarks.


Weaknesses: 


1. The proposed self-supervised loss in Equation 8 mainly focuses on the global information in a graph as Equations 4, 6, and 7 are all defined on the graph embedding level. This might cause the model not to pay attention to local information in the graph.

2. The motivation of the work is based on a pitfall of contrastive learning methods, which assumes two similar graphs (one original and one perturbed version of the original) are the same. The paper proposed using distance-based self-supervised learning which incorporates the distance of two graphs when pushing their embeddings closer or pulling their embeddings apart in the latent space. However, the notion of distance here is a weighted version of the original contrastive learning version:  two similar graphs will still have small distances and be close in the latent space even if some properties of the perturbed graph drastically change from the original graph. Also, it is not clear why a perturbed graph with a distance of two to the original graph should be further apart compared to a graph with a distance of one to the original graph. How can we make sure that graph edit distance is a good proxy for measuring if two graphs should be close or far in the latent space?

questions: 1. Tables 2 and 4: how many times did the authors run the model to get the results in these two tables? which results are statistically significant compared to the best baseline?

2. How does the value of $\lambda_1$ and $\lambda_2$ in Equation 8 affect the performance of the model? some charts that show the performance of the model for different values of $\lambda_1$ and $\lambda_2$ will be helpful.

3. The paper tested the proposed model for link prediction on social networks. However, I find the motivation of the paper to be weak in social networks (and stronger for small graphs like molecules). Why some perturbations in a large social network might drastically change some of its properties?
limitations: See weaknesses 1 and 2.
review_title: null

Meta-review: metareview: This paper proposes a novel self-supervised learning strategy by considering the quantitative discrepancy of two perturbed graphs, which is measured by graph edit distance. The major concerns come from the motivation of the proposed approach. This has been well addressed in authors’ rebuttal, with additional new experiments. The authors have done a great job in addressing this main concern and other questions raised by reviewers, such as ablation studies on major hyperparameters. The contribution of incorporating graph-level quantitative metric as additional self-supervision signal is clear. Although there are divided ratings in the end, I still recommend acceptance of this paper.
confidence: Less certain
Decision: Accept