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: The paper proposes a Scalable Self-Supervised method that uses graph neural networks (hence called S3GC) and node features to learn clusterable representations using contrastive learning. 

S3GC uses a 1 layered graph convolutional network to encode feature and structural information. To encode the structure, the authors propose to use normalized adjacency and a k-hop diffusion matrix. To use the contrastive loss for generating clusterable representations, positive and negative samples are needed. S3GC uses a biased random walk sampler to get similar nodes. Negative nodes are generated randomly from the remaining nodes. 

Authors have shown that it can scale well to graphs with 100M nodes which are challenging for current graph neural network-based approaches. S3GC is shown to gain as much as 5% in NMI.
strengths_and_weaknesses: **Strengths**

The proposed approach is simple and intuitive.

The paper is well written and easy to understand.

The proposed approach combines information from both the graph and the node features and hence is applicable in settings where one vs the other is noisy. Extensive experiments are conducted to validate this using a synthetic dataset.

This method only uses a single GCN layer with normalized adjacency and diffusion matrix and thus it can take into account higher order neighborhood information and still scale to very large-scale graphs which allows for its application in real-world settings.

Extensive experimentation is done to show the effectiveness of the approach on small-scale as well as large-scale datasets.
Space and time complexity provided add to the clarity of the central idea of the paper about scalability.

**Weaknesses**

IMO this is more of applied work and I think perhaps an applied conference is a better place for this work for a larger impact. All the insights for instance for linear separability and clusterable contrastive representations are known ([1]). The part about scaling that uses a diffusion matrix has also been used as a scalable way of getting higher-order information ([2]). I think perhaps (to the best of my knowledge) the idea of enforcing closeness of neighbors is new but it doesn’t contribute to the main idea of the paper which is scalability.

It will be interesting to see a baseline that compares the baseline contrastive learning approaches (DGI, MVGRL, etc.) with just one gcn layer with 1 hop neighborhood perturbations. I think MVGRL will become pretty scalable in that setting as well and because it also uses a diffusion matrix my hunch is that it will be pretty competitive on larger datasets. From table 3 it seems like MVGRL is better than the proposed approach on average (on NMI at least which is considered to be the metric for clustering) whenever it didn’t have OOM error.

Another potential weakness is that all of the datasets are homophilous. I am not sure how will this perform on heterophilous graphs.

Another weakness is that it is not clear how this approach is directly applicable to heterogeneous graphs (which authors mention as well). 

As authors point out, there is no theoretical justification for the proposed method. Perhaps one can borrow ideas from [1]

[1] Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss

[2] SIGN: Scalable Inception Graph Neural Networks
questions: Is there an ablation that uses only the normalized adjacency/diffusion matrix in the GCN.  I didn’t find these in the paper (or in the appendix).

This paper refers to DGI as SOTA (page 6 lines 233-235, 273-274). Is that true? Perhaps the authors meant to say DGI style methods? MVGRL has been shown to work better and that is validated in the experiments as well (Table 3). Thus, I think Table 1 should have results with MVGRL. I understand authors have concerns that the reported values are higher in MVGRL (line 317-318) but I think it is good to add for completeness.
limitations: See Weaknesses +  questions.
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 studies the problem of graph clustering using additional information such as node features. Previous works focus on learning graph embeddings and don’t explicitly optimize for clustering, are highly reliant on graph information which fall short when noisy or involve expensive modules which do not scale well. This method utilizes both node attribute information and the graph structure information to generate embeddings that are more linearly separable into k clusters. The experiments and results show that the proposed S3GC method outperforms several clustering baselines and produces better quality embedding clusters. 
strengths_and_weaknesses: Strengths:
1. Related works are well covered.
2. Proposed method is simple and neat. It scales well to large graphs of the order of 100 million nodes.
3. The standard experiment setup has been followed. Synthetic data generation uses the well-studied SBM algorithm.
4. Experiments on large scale datasets show the superior performance of the proposed method in comparison with the baselines.
5. The paper is written in a simple and easy-to-follow manner. 

Weaknesses:
1. The novelty in the proposed method is weak. It is rather similar to Node2Vec but with the SimCLR loss function which improves linear separability in the node representations. 
2. Considering that there are several hyperparameters involved in the proposed algorithm, the paper does not include a systematic study of different ranges for the parameter values.

questions: 1. In equation 5, both $\alpha$ and $alpha$ are used to indicate the same variable. It is important to be consistent with the notations.

2. In Table 1, the name S3GC-I is a little confusing because it usually implies S3GC method without (minus) I while it actually means using only I. So it would be good to consider changing the name to something more intuitive (eg. S3GC_I or Only I, etc)

3. The second observation under section “Setup and observations”, line 247, talks about DGI not performing well when attributes are noisy but does not reference any result table or figure. If the authors were referring to table 2, it is not clear how they have arrived at that conclusion. Which parameter controls the quality of the node attributes?

4. Similar comment for observation 3 (line 249), 

5. Can the choice of parameter values (eg in table 1) be justified? The $p$, $q$ & $\sigma$ values chosen for the experiments are arbitrary and it is good to experiment with a bigger range of values. For eg, similar to Fig. 5a in [1]. 

6. Why does MVGRL perform better than S3GC in the small scale datasets? Is this just an artifact of the citation networks or is a similar behavior observed in other small scale datasets? It would be interesting to look at which components of MCGRL are contributing to its performance, especially on these datasets.

7. Gemsec [2] is another related work that has not been included in this paper but might be worth including in the baselines. It is similar in terms of learning clusterable graph embeddings. The embeddings are learned while considering the cluster information. 

[1] - Grover, Aditya, and Jure Leskovec. "node2vec: Scalable feature learning for networks." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016.

[2] - Rozemberczki, Benedek, et al. "Gemsec: Graph embedding with self clustering." Proceedings of the 2019 IEEE/ACM international conference on advances in social networks analysis and mining. 2019.

limitations: The authors have mentioned some limitations of their work. It does not particularly consider different types of nodes in the learning of embeddings. It does not discount several “important” nodes that may cause the model to be unfairly biased.  However, there are several things that need to be improved in this paper (mentioned above) to make it a strong and novel contribution to the graph clustering literature.
review_title: null

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: The paper presents a new method, S3GC, for scalable graph clustering. S3GC takes both the graph structure information and node-feature information into consideration by using a one-layer GNN encoder and performs self-supervised contrastive learning. There are several contributions. First, S3GC implements self-supervised learning on the graph clustering problem. Second, S3GC combines graph structure information and node feature information. Third, systematic experiments have been conducted. 

S3GC has three key components, namely graph convolutional encoder, random walk sampler, and contrastive loss formulation. The graph convolutional encoder is a 1-layer Graph Convolutional Network, which is used to combine both graph structures and node features. One important design in the encoder is that the author uses mini-batches to reduce the memory requirement, which makes S3GC scalable to the large graph. Random walk sampler uses biased second order Random Walks with restarts to generate points similar, and thus capture the local neighborhood of each node. Contrastive loss formulation is a SimCLR style loss function, which is used for learning the encoder parameters. With this formulation, the authors use graph neighborhood information to produce augmentations of a node.
strengths_and_weaknesses: 
S1.	The paper is in general easy to follow. 

S2.	Scalable clustering is important in practice.

S3.  The authors apply self-supervised learning to graph clustering, and present an effective and scalable model. The result shows that the model can address some existing limitations. 

S4.	The proposed model can be applied to billion-edge graphs for clustering.

S5.	The author conducts extensive experiments and gives correlated analysis. The experimental result proves that S3GC can solve graph clustering problems with better performance in different aspects.

W1. The three components of S3GC all use the existing designs partly. The first part, the graph convolutional encoder, uses a 1-layer Graph Convolutional Network, and the novelty here seems to be the way of combining both graph information and node features. The second part, the random walk sampler, is inspired by previous work and formally follows previous work. The third part, contrastive loss formulation, uses a SimCLR style loss function.

W2. Seems there is a minor error in line 214. The author states that the time complexity is O(Knsd2), seemingly forgetting “r”.

W3. I did not find the results on detailed running times of different methods (though roughly mentioned).

questions: Q1. Please check Line 214 and see whether "r" is missed.

Q2. Please report the details of running times for each method. As this paper studies scalability, these efficiency results are important.

Q3. In abstract, the authors state that "we demonstrate that S3GC is able to significantly outperform state-of-the-art methods in terms of clustering accuracy with as much as 5% gain in NMI". However, from Table 3 this seems not always true (e.g., compared with MVGRL). Please explain the reason.

Q4. The three components of S3GC use the existing designs partly. Please explain more exactly where the novelty lies.
limitations: This paper is in general elegant in terms of method design. However, the novelty is a bit unclear. All the three modules are inspired directly from the existing work. To make their combination a novelty, I believe a deeper discussion is needed, i.e., why such combinations can maintain the effectiveness. For example, 1-layer GCN seems to be simple, and why its combination with random walks and contrastive loss are effective?  Which part has the dominating factor? The related ablation study that checks the effectiveness of each component should be included in the main paper. The ablation study in the Appendix only includes some parameter testings.
review_title: null

Meta-review: metareview: TL;DR: Accept is there is room.

The paper proposes a Scalable Self-Supervised method that uses graph neural networks (1 layered graph convolutional network to encode feature and structural information), diffusion augmentations, and contrastive learning for graph clustering.  The work is more applied, the baselines are somewhat weak (but these are the ones that scale), and overall there is nothing ground-breaking about this work. Generally NeurIPS does not accept this type of work but it could be interesting to part of the community focused on scalability.

During rebuttal almost all reviewer concerns were addressed. The authors did a good job showing with their experiments.

It worries me that the authors answered the questions but did not make significant changes to their draft (despite saying they would do that). I was inclined to reject the paper because of the absence of updates but I will trust the authors' word this time. But if the discussed changes are not implemented there should be consequences.

"Our method is also doing positional encoding similar to node2vec, as we are forming positives/negatives in our contrastive learning formulation based on some kind of random walk." => I read it again and I highly doubt this statement. Contrastive learning does not necessarily create positional representations. Please clearly state the type of embedding and add a proof to your paper (it can be added in the appendix).
confidence: Less certain
Decision: Accept