Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a reformulation of Laplacian Eigenmaps in a log-linear contrastive setting. Inspired by GAN architecture, the authors show that the their contrastive laplacian eigenmaps (COLES) minimises a surrogate of Wasserstein distance as opposed to JS distance in traditional contrastive methods. Further, COLES in shown to enjoy block contrastive loss, which is upper bounded by pair-wise loss. 

The authors show that the log-linear contrastive loss can be reformulated as a generalised eigenvalue (GEV) problem of a contrastive degree normalised adjacency matrix. They apply this formulation to line graph networks such as SGC and $S^{2}$GC and obtain a closed form solution to the matrix of node embeddings, which depends on a spectral filter and the solution to the GEV problem. 

By casting the positive and negative samples as the real and generated data from a GAN, the authors show that traditional contrastive losses can be reformulated into JS divergence, while COLES can be cast into a surrogate of 1-Wasserstein  metric. They claim that the latter is preferable since, under poor overlap of the the two distributions JS divergence vanishes, leading to vanishing gradients, while 1-Wasserstein distance does not. 

The authors also show that COLES is Lipschitz continuous and enjoys block contrastive loss, wherein one can leverage blocks of similar data as opposed individual pairs. Since from [Saunshi et al] block contrastive loss is smaller than pair-wise loss, the authors claim that COLES is expected to achieve a lower minimum. 

The authors perform empirical evaluation on a host of open source datasets and multiple baseline backbones. In most tasks, COLES objective seems to outperform the methods included in the comparison.  
main_review: Originality: 
The approach seems simple, straightforward but original. They use the log-linear contrast function, instead of the sigmoid, which allows reformulation as a generalised eigenvalue problem. If the contrastive learning problem is interpreted as a GAN, then convergence is in the Wasserstein topology which does not suffering from the vanishing gradient problem when the two measures do not have overlapping support. 

Quality: The submission is technically sound, with extensive empirical evaluation and sufficient theoretical justification.  However, the authors do not sufficiently discuss the weakness of their approach. For example, the reason for the choice of log linear loss, or its interpretation. Is then Laplacian eigen map just one example of contrastive learning or are there some optimality results in this direction?

Clarity: The paper starts off clearly written but in some sections, feels disjointed. For example section 4.1 lines 128-152 could have been summarised succinctly as most of the derivation there is well known. The empirical evaluation is described adequately. 

Significance: 
The paper presents a thoughtful approach to contrastive graph embedding as generalised eigen value problem. If explored further, the results may provide better understanding of contrastive graph embedding  approach. 

limitations_and_societal_impact:  Not applicable.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this article, the authors extended the classic Laplacian eigenmaps to the form of contrastive learning and proposed a new graph contrastive representation learning model. The authors also gave some theoretical analysis about their proposed contrastive learning loss.
main_review: The authors extended the classic Laplacian eigenmaps to the form of contrastive learning, it seems that the experimental results are good. However, the problem studied in this paper is not new. I think the novelty is incremental. In the current version, I have the following suggestions:
1.	Eq. (6) should be explained in more detail about F.
2.	Missing some important related works about graph contrastive representation learning, e.g., Graph contrastive learning with augmentations (You et al., NeurIPS 2020).
3.	What are the advantages of the proposed method compared to You et al., NeurIPS 2020.
4.	The experimental results in Table 1 and 7 are not solid enough to verify the effectiveness of the proposed method, since there lack some state-of-the-art methods for comparison. 

limitations_and_societal_impact: Not sufficient
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides a reformulation of the traditional Laplacian Eigenmaps in a contrastive setting, for graph nodes embedding. Theoretical results for its connection to Wasserstein distance and block-contrastive loss are presented. Overall, I think this is a good paper with substantial contributions in connecting manifold learning and constructive learning. 
main_review: Pros: 
      1) This paper is organised well and clearly written.
      2) The idea to connect the Laplacian Eigenmaps and contrastive learning is novel.
      3) There are both theoretical analysis and empirical results supporting the proposed method.
 

Cons: 
      1) It would be better if the authors can give more details on how the adjacency $\textbf{ W}$ is generated.
If the $\textbf{ W}$ is generated through k-nearest neighbours how can the computational complexity be handled reasonably with large datasets?
      2) The examples on when the methods using JS divergence may underperform have been given, but I think the paper would also benefit from providing more insights on when the proposed method would outperform the traditional Laplacian Eignemaps.
limitations_and_societal_impact: I understand this paper focuses more on methodology part, but I suggest the authors should discuss the potential negative societal impact of their work,  probably in terms of applications. It is currentluy missing from the manuscript.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this work, the authors improved contrastive learning of graph node embedding from the viewpoint of Laplacian eigenmap. Removing nonlinear activation used in traditional NCE, the authors reformulate NCE as a randomized Laplacian eigenmap problem, which can be used to learn the GNNs with linear architectures. The authors claimed that the proposed method is equivalent to minimize the expectation of the Wasserstein distance between the positive and the negative distributions conditioned on the target node. 

-- after rebuttal ---
Most of my concerns are solved, so I change my score from 5 to 6.
main_review: Pros:
1. The paper is written clearly.

2. The experimental results of different tasks demonstrate the usefulness of the proposed method. The implementation details are provided. 

3. Connecting NCE with Laplacian eigenmap provides an interesting paradigm of node embedding, which is promising.

Cons:
1. The introduction of GAN between Line 121 and Line 137 is redundant in my opinion — the conclusion has been given in the paper of WGAN. Compressing this part will give more space and the authors can move more derivations from the supplementary file to the main paper.

2. The Lipschitz continuity of g(u) (and COLES) becomes obvious because the authors have claimed the linearity of the target model. Additionally, it seems unnecessary to derive “||u-u’||_2” in Line 155 and the following inequality. 

3. I am not sure about the superiority of “block-contrastive loss”. As the authors claimed in 163, the block-contrastive loss is a lower bound of pairwise-contrastive loss. However, if my understanding is correct, the objective function is minimizing the loss. I don’t think minimizing a lower bound of an objective function. (For example, EM is reasonable because it minimized an upper bound of MLE; a main drawback of WGAN is that it can just minimize a lower bound of Wasserstein distance.)

4. Additionally, different from classic WGAN, the authors consider the Wasserstein distance between conditional generation and the condition corresponds to the model parameters (i.e. v). In other words, learning the embedding u’s conditioned on v will influence the learning of other nodes’ embeddings that conditioned on the u’s. Such a non-i.i.d. situation makes the feasible domain of g_v(u) in Eq. (11) changes during training. Maybe the authors should emphasize and analyze this difference.

5. The parameters of COLES are constrained (as shown in Eq. (6)). How to achieve the constraints in the framework of SGD is not explained clearly. 

limitations_and_societal_impact: I did not find any obvious or potential negative societal impact of this work.
review_title: null

Meta-review: This paper had very split reviews and required some thought when coming to a recommendation. The authors provided very thorough responses to each reviewer's critiques. While the two positive reviews responded saying they were satisfied with the author responses, neither of the negative reviewers responded to the author feedback. One negative reviewer's only objection was a lack of comparison against You et al. 2020. The author's provided such a comparison in the response, showing good results for their method relative to the baseline. The other reviewer had more detailed critiques, but from my estimation of the author's response, those critiques were well rebutted. Unfortunately I do not know if the reviewer themself thought the critiques were answered well. I am inclined to recommend acceptance for this paper, on the basis of the very thorough responses which I believe answered most of the reviewer critiques, and the failure of the reviewers themselves to answer the authors.
Decision: Accept (Poster)