Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes Proxy approximated meta-node Contrastive (PamC) for contrastive representation learning on graphs. PamC is motivated by the computational burden of vanilla contrastive loss (i.e., InfoNCE), and to deal with this problem, it proposes a meta-node based approximation technique which proxies all negative combinations in quadratic cluster size time complexity. Empirical reuslts sho that the proposed method demonstrates promising accuracy gains over sota graph clustering methods on 6 benchmarks with better efficiency.

strength_and_weaknesses: Strenghts:
1. The motivation of this paper is good and solid. The computation complexity of InfoNCE loss is quadratic with respect to the number of nodes, which severly prevent full-graph training.
2. The proposed method does show better efficacy than traditional contrastive methods.

Weaknesses:
  1. The authors claim that contrastive learning on graphs require a large number fo negative samples while subsampling is suboptimal. Is there any empirical support for this claim as according to my experience, subsampling will not severly degrade the model’s performance.
 
2. Compared with data augmentation based contrastive learning  (InfoNCE loss) methods which ony requires two shared GNN encoder to generate node embeddings, the proposed method looks much more complicated (e.g., pretraining to get soft clusters). Although the overall complexity is linear, I doubt whether it can lead to efficacy when really applied to these datasets (especially when the graph is not that large, e.g., the datasets used in experiments)
3. The paper focus on contrastive learning on graphs, however, a lot of important related works are missing in both related works and experiments. For example, [1] and [2] are two data augmentation-based contrastive methods using InfoNCE loss. [3] avoids negative samples using asymmetric structures. [4] avoids negative samples through feature-level decorrelation. The complexity of [3] and [4] are both linear to the graph size and thus they are scalable. However, this paper never consider these important baselines.
4.  I am also confused about the tasks and datasets used in experiments. According to my knowledge, most self-supervised learning methods (including contrastive ones) foucs on node classifcation tasks (e.g., [1-4]). Why you consider graph clustering tasks instead of more commonly used node classication tasks.
5. Although the most imporant claimed advantage is scalability, the datasets used for evaluation are really small. The authors should consider use larger graphs.

References:
[1] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006.04131, 2020b.
[2] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW, 2021.
[3] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Velickovic, and Michal Valko. Bootstrapped representation learning on graphs. arXiv preprint arXiv:2102.06514, 2021.
[4] Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu. From canonical correlation analysis to self-supervised graph neural networks. In NeurIPS, 2021.


clarity,_quality,_novelty_and_reproducibility: Overall, the propsoed method is novel and is clearly presented. 
summary_of_the_review: Generally, I think the motivation of this paper is good. However, I think the propsoed method is over-complicted while does not show prominently better performance than simple methods. Besides, I believe the proposed method is not properly evaluated, in terms of tasks, datasets and baselines. I am leaning on rejection.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the task of representation learning for graph data. The proposed objective is a contrastive learning objective that is based on using clusters in negative sampling. Empirical analysis compares the proposed approach to a wide variety of representation learning and clustering approaches for graphs. 
strength_and_weaknesses: **Strengths** 
* The proposed approach seems to be widely empirically effective and is accurate. The approach is very computationally efficient compared to baseline approaches. 
* The proposed approach uses an interesting clustering-based objective that seems well motivated. 

**Weaknesses**
* Clustering objectives have been studied in other contrastive learning approaches e.g. [1, 2, 3] among a wide array of other approaches in deep clustering. It would greatly improve the paper to consider how these approaches relate to the proposed approach. 
* Could the authors clarify the statement
>We provide theoretical proof and show that real world graphs always satisfies the necessary
conditions, and that PamCGC is block-contrastive, known to outperform pair-wise losses
* While the proposed approach offers empirical advantages and is an interesting idea, I am wondering if the methodological depth is sufficient for the ICLR "bar". It would seem that the novelty is the combination of clustering ideas in graph representation learning. I think this is nice, but I feel the authors could clarify how their contribution investigates deeper questions in this area than past work. For instance, efficiency is a major advantage of the proposed approach. Understanding tradeoffs here is in Figure 2. It seems like more emphasis could be placed in this understanding.

[1] Caron, Mathilde, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. "Unsupervised learning of visual features by contrasting cluster assignments." Advances in Neural Information Processing Systems 33 (2020): 9912-9924.

[2] Zhang, Chunyang, Hongyu Yao, C. L. Chen, and Yuena Lin. "Graph Representation Learning via Contrasting Cluster Assignments." arXiv preprint arXiv:2112.07934 (2021).

[3] Li, Junnan, Pan Zhou, Caiming Xiong, and Steven CH Hoi. "Prototypical contrastive learning of unsupervised representations." arXiv preprint arXiv:2005.04966 (2020).
clarity,_quality,_novelty_and_reproducibility: Please see weaknesses for additional clarifications. 
summary_of_the_review: This paper presents an empirically effective approach for graph representation learning and clustering. The approach, which uses clustering  is more efficient than previous work. The paper could be improved with more complete description of the landscape of related work on representation learning and clustering. The paper could be further improved with more clarity on the technical depth and revealed performance tradeoffs.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper extends the contrastive learning on graph by replacing the contrastive between negative samples with that between class clusters with theoretical analysis. It possesses the attractive characteristic of reducing complexity. Experimental evaluations demonstrate its effectiveness and efficiency.
strength_and_weaknesses: Strength
- It makes sense to replacing the contrastive between negative samples with that between class clusters to reduce the complexity.
- The experimental evaluations are sufficient.
- The writing and organization are good.

Weakness
- My main concern is the novelty may not be significant. Although authors call the cluster center as meta-nodes, they are actually the prototype of the cluster. There are many efforts have be paid on prototypical contrastive learning, such as [1] and its variants, which also takes cluster centers into considerations and reduce the complexity.

[1] Junnan Li, Pan Zhou, Caiming Xiong, Steven C. H. Hoi: Prototypical Contrastive Learning of Unsupervised Representations. ICLR 2021
2020

clarity,_quality,_novelty_and_reproducibility: - The clarity and reproducibility are good.
- The novelty and originality may be not significant.
summary_of_the_review: This paper possesses clear motivation, good writing and organization, and sufficient evaluations. My main concern is the novelty, since existing prototypical contrastive learning also reduce complexity by considering cluster centers.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to utilize the meta-node (average of node embeddings within a cluster) for constructing negative samples in contrastive learning. It claims that this approach is more efficient than previous sampling based methods and it leads naturally to block contrastive learning which could be beneficial. Experiments on various datasets demonstrate the performance of the proposed method on different modalities including image, text and graph.
strength_and_weaknesses: ## Strength
1. The direction of more efficient negative sample mining is important for contrastive learning.
2. The idea of utilizing the clustering centers as negative samples saves the sampling cost.
3. Extensive experiments demonstrate comparable performance with baseline methods while achieving good speedup ratio for training time.

## Weaknesses
1. Discussion on related works is not enough, which makes the novelty a little unclear. Is this work the first to utilize averaged embeddings as negative samples for contrastive learning? What are the closest related works? 
2. It is not clear how the proposed method can save inference time
3. How long does it take to evaluate the soft label? Is it included in the training time?
clarity,_quality,_novelty_and_reproducibility: Clarity: fair, see questions above
Quality: reasonable
Novelty: needs clarification

summary_of_the_review: Overall the proposed method is well motivated and achieves reasonable speedup for training. I have some questions about the novelty and experiments. I may consider adjusting my rating after discussing with the authors.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper provides a method to speed up contrastive learning, by using clusters to construct negative samples. Contrastive learning is a strong method yet is known to be a computational challenge, hence the goal of reducing its computational complexity is well motivated. The approach taken in the paper is agreed by the reviewers to be sensible, 
and the experiments convincingly show the method reduces runtime without hurting performance when compared to baseline approaches for contrastive learning. The main problem with the paper, raised in some way in all of the reviews, is its comparison to existing works. The reviews raise several papers that this approach should be better positioned against. 
There were some concerns about the techniques having limited novelty when compared against these previous works, but this could be an issue that can be resolved with a clearer comparison. The authors gave some explanations in the rebuttal phase, but the reviewers and I feel that the issue is too major to be fixed in a rebuttal phase. 
The paper has potential, but requires a revision and another round of reviews before it can be accepted to a venue such as ICLR.
justification_for_why_not_higher_score: Unanimous agreement that the comparison with existing art should be substantially improved. 
justification_for_why_not_lower_score: n/a
Decision: Reject