S3GC: Scalable Self-Supervised Graph Clustering
Authors: Fnu Devvrit
Aditya Sinha
Inderjit S Dhillon
Prateek Jain
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Clustering
GNN
Contrastive Learning

Abstract: We study the problem of clustering graphs with  additional side-information of node features. The problem is extensively studied, and several existing methods exploit Graph Neural Networks to learn node representations. However, most of the existing methods focus on generic representations instead of their cluster-ability or do not scale to large scale graph datasets. In this work, we propose S3GC which uses contrastive learning along with Graph Neural Networks and node features to learn clusterable features. We empirically demonstrate that S3GC is able to learn the correct cluster structure even when graph information or node features are individually not informative enough to learn correct clusters. Finally, using extensive evaluation on a variety of benchmarks, 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 -- while being scalable to graphs of size 100M. 


GC: Scalable Self-Supervised Graph Clustering
Fnu Devvrit"
Aditya Sinha Google Research Bengaluru, India, 560016
Department of Computer Science
University of Texas at Austin devvrit.
03@gmail.coo dewvrit.03@gmail..
synhood
Inderjit Dhillon
Prateck Jain Google Research Bengaluru, India, 560016 prajain@google. com
Google & Department of Computer Science University of Texas at Austin isd@google com
Abstract
We study the problem clustering graphs with additional side-information of node features. The problem is extensively studied, and several existing methods exploit Graph Neural Networks to learn node representations [2]. However, most of the existing methods focus generic representations instead of their cluster-ability do not scale to large scale graph datasets. In this work, we propose SCGC which contrastive learning along with Graph Neural Networks and node features to learn clusterable features. We empirically demonstrate that S able to learn the correct cluster structure are individually not informative enough to learn correct clusters. Finally, using extensive evaluation on a variety of benchmarks, we demonstrate that S* is able to significantly outperform state-of-the-ar methods in terms of clustering accuracy with as much as 5% gain in NMI while being scalable to graphs of size 100M.
when graph information node features
Introduction
Graphs commonplace data structures store information about entities/users, and have been S4!
57 In modern ML systems, the entities/nodes are often equipped with vector embeddings from different sources. For example, authors are nodes in citation graph and can be equipped with embeddings of the title/content of the authored papers [16 41 as relevant side information. Owing the utlility of graphs in large-scale systems, tremendous progress has been made in the domain of supervised learning from graphs and node features, with Graph Neural Networks (GNNs) headlining the state-of th-the-rrtt methods [2X 19 (52). However, typical real- world ML workflows start with unsupervised data analysis to better understand the data and design supervised methods accordingly. In fact, many times clustering is key tool ensure scalability to web-scale data 22). Furthermore, even independent of supervised learning, clustering the graph data with node features is critical for variety of real-world applications like recommendation, routing, triaging
investigated for decades [5 15.
31
32 etc.
Effective graph clustering methods should be scalable, especially with respect the number of nodes, which can be millions even for a moderate-scale system [57]. Furthermore, in the presence of side-information, the system should be able use both the views node features and graph information of the data "effectively". For example, the method should be more accurate than single-view methods that either consider only the graph information 27] or only the node feature
"work done while the author intern Google Research Now at University of Illinois, Urbana-Clin Chaama-h
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

-30
-00
x
-00
(a) Node2vec
(b) DGI
(c) GC (Ours)
Figure 1: tSNE visualization of embeddings when applied to the data model given in Section 3.5 SBM parameters p.q such p = +18, while o,
ie.. both graph information and feature information are separately insufficient for clustering (see Table D SCGC is able to well-separate all the clusters while Node2vec [1]] and DGI [53] have significant amount of cluster overlap.
information
This problem of graph clustering with side information has been extensively for a review of the existing and recent methods. Most methods map the problem to that of learning vector embeddings and then apply standard k-means 33 style clustering techniques. However, such methods like Node2vec [ don't explicitly optimize for clusterability, therefore the resulting embeddings might not be suitable for effective clustering. Furthermore, several existing methods tend to be highly reliant on the graph information and thus tend to perform poorly when graph information is noisy/incomplete. Finally, several existing methods such as GraphCL [8 propose expensive augmentation and training modules, and thus do scale to realistic web-scale datasets.
3
studied in the literature [61; see Section 2
We propose SCGC which uses a one-layer GNN encoder to combine both the graph and node-feature information, along with graph only and node feature only encodings. GC applies contrastive learning to ensure that the embedding of a node is close to "near-by" nodes obtained by random walk while being far away from all other nodes. That is, GC explicitly addresses the above three mentioned challenges: a) SC is based on contrastive learning which is known to promote linear separability and hence clustering 20 b) SCGC carefully combines information from both the graph view and the feature view, thus performs well when one of the views is highly noisy/incomplete c) SC use light-weight encoder and simple random walk based sampler/augmentation, and can be scaled to hundreds of millions of nodes on single virtual machine (VM).
For example, consider a dataset where the adjacency matrix of the graph is sampled from stochastic block model with 10 clusters; let probability of an edge between nodes from same cluster is p and from different clusters is q. Furthermore, features of each node also sampled from mixture of 10 Gaussians where oe is the distance between any two cluster centers while o the standard deviation of each Gaussian. Now, consider setting where > q but p, are close, hence information from the graph structure is weak. Similarly, a. < a but they are close. Figure plots two-dimensional tSNE projection [5T] of embeddings learned by the state-of-the-ai Node
and DGI methods, along with SOGC. Note that while Node2vec's s objective function is optimized well, the embeddings do not appear to be separable. DGI's embeddings are better separated, still there is a significant overlap. In contrast, SCGC is able to produce well-separated embeddings due to the contrastive learning objective along with explicit utilization of both data views.
We conduct extensive empirical evaluation of SaGC and compare it to a variety of baselines and standard sfte-of-the-as the-art benchmarks, particularly: Spectral Clustering 43), k-means [33 METIS 277 Node2vec 18). DGI(5:), GRACE 62), MVGRL 21 and BGRI [48). Overall, we observe that our method consistently outperforms Node2vec, DGI SOTA scalable methods achieving as much as 5% higher NMI than both the methods. For two small scale datasets, our method is competitive with MVGRL method, but MVGRL does not scale
all seven datasets,
moderate sized datasets with about 2.5M nodes and 61M edges, while our method scales to datasets with 11 nodes and 1.6B edges.
Related Work
Below, we discuss works related to various aspects of graph clustering and self-supervised learning, and place contribution in the context of these related works.

---

Graph OR features-only clustering: Graph clustering is a well-studied problem, and several techniques address the problem including Spectral Clustering (SC)
43 Graclus [2.. METIS (77. Node2vec [88. and DeepWalk [40]. In particular, 2ece2 [8] is a probabilistic framework that is an extension to Deep
and maps nodes to low-dimensional feature spaces such that the likelihood of preserving the local and global neighhorhood of the nodes is maximized. In the setting of node-features only data, k-means clustering is one of the classical methods, in addition to several others like agglomerative clustering [4 density based clustering [59], and deep clustering 77].
As demonstrated in Figure and Table S*GC attempts to exploit both the views, and if both views are meaningful then it can be significantly more accurate than single-view methods.
Self Supervised Learning: Self-supervised learning methods have demonstrated that they can learn linearly separable features/represennttions in the absence of any labeled information. Typical approach is define instance-wis "augmentations" and then pose the problem that of learning contrastive representations that map instance augmentations close to the instance embedding, while pushing it far apart from all other instance embeddings. Popular examples include MoCo [2]. MoCo v2 [Л) SimCLR [2], and B BYLL 177. Such methods require augmentations, and as such do not clustering problem. SCGC uses simple random walk based
apply directly to the graph+node-featue augmentations to enable contrastive learning based techniques.
Graph Clustering with Node Features: To exploit both the graph and feature information, several existing works use the approach of autoencoder. That is, they encode nodes using Graph Neural Networks (GNN) 28 with the goal that inner-product of encodings can reconstruct the graph structure; GAF and VGAF 29 use this technique. GALA 38, ARGA and ARVGA 37 extend the idea by using Laplacian Sharpening and generative adversarial learning. Structural Deep Clustering Network (SDCN) [4] jointly learns an Auto-Encoder (AE) along with a Graph Auto-Encoder (GAE) for better node representations, while Deep Fusion Clustering Network (DFCN) (50 merges the representations learned by AE and GAE for consensus representation learning. Since AE type approaches attempt to solve a much harder problem, their accuracy in practice lags significantly to the state-of-the-arr for example, see Table 3 in [21 which shows that such techniques can be 5-8% less accurate. MinCutPool
22 and DMoN 10 extend spectral clustering with graph encoders, but the resulting problem is somewhat unstable and leads to relatively poor partitions; see Table B
Graph Contrastive Learning: Recently several papers have explored contrastive Graph Representa- tion Learning based approaches and have demonstrated state-of-the -frte-rrr-- performance. Deep Graph Infomax (DGI) [33) is based on MINE A4 method, and is one of the most scalable method with nearly SOTA performance. It uses edge permutations to learn augmentations and embeddings. Info- graph extends the DGI idea to learn unsupervised representations for graphs as well. GraphCL design framework with four types of graph augmentations for learning unsupervised represen- tations of graph data using a contrastive objective. MVGRL [ extends these ideas by performing node diffusion and contrasting node representations with augmented graph representations while GRACE 62 maximizes agreement of node embeddings across two corrupted views of the graph.
Bootstrapped Graph Latents (BGRL) [4X] adapts the BYOL [17] methodology to the graph domain, and eliminates the need for negative sampling by minimizing an invariance based loss for augmented graphs within batch. While these methods are able to obtain more powerful embeddings. the augmentations and objective function setup become expensive, and hence they are hard scale to large datasets beyond ~ 1M nodes. In contrast, SC is able to provide competitive or better clustering accuracy, while still being scalable to graphs of size 100M nodes.
3 GC: Scalable Self-Supervised Graph Contrastive Clustering
In this section, we first formally introduce the problem of graph clustering and notations. Then we discuss challenges faced by the current methods and outline the framework of our method SC Finally, we detail each component of our method and highlight the overall training methodology.
3.1 Problem Statement and Notations
Consider a graph G (V, E) with the vertex set V = (u1,... " and the edge set E VVVVV. where E = m. Let A E Raxn be the adjacency matrix of G, where Ad = 1 if (v,, 02)) E E, else AG = Let E R be the node attributes or feature matrix, where the i-th row X, denotes the d-dimensional feature vector of node i. Given the graph G and attributes X, the aim is to partition the graph G into partitions [G1, G2, G3, G& } such that nodes in the same cluster are similar/close to each other in terms of the graph structure as well as in terms of attributes.
3

---

Now, in general, one can define several loss functions to evaluate quality of clustering but that might not reflect the underlying ground truth. So, to evaluate the quality of clustering, we use standard benchmarks which have ground truth labels apriori. Furthermore, Normalized Mutual Information (NMI) between the ground truth labels and the estimated cluster labels is used as the key metric. NMI between two labellings Y1 and Y2 is defined as:
2. 2-1(Y,,
NY Y2) H(Y) + (Y2)
(I)
where 7(Y,, Y2) is the Mutual Information between labellings Y1 and Y2, and H(-) is the entropy. Normalized Adjacency Matrix denoted by Á = 1D-2A AD-À E mgax where diag (AIx) is the degree matrix. We also compute a hop Diffusion Matrix, denoted by Sk = Ei= a, E RTxx" where a E [o, 1] Vi E [k]. and Σ, a; & 1. Intuitively, k-hop diffusion matrix captures weighted average of k-hop neighbourhood around every node. For specific a; and for h oc, diffusion matrix can be computed in closed form 30 36 However, in this work we focus on finite k.
3.2 Challenges in Graph Clustering
Clustering in general is challenging problem as the underlying function to evaluate quality of the clustering solution is unknown apriori. However, graph partitioning/lluserinng with attributes poses several more challenges. In particular, scaling the methods is challenging as graphs are sparse data structures, while neural network based approaches produce dense artifacts. Furthermore, is challenging to effectively combine information from the two data views: graph and the feature attributes. Node2vec 18 uses only graph structure information, DGI 531 and related methods are highly dependent upon attribute quality, Motivated by the above mentioned challenges, we propose SCGC which uses a self-supervised variant of GNNs.
21 [39
3.3
S GC: Scalable Self Supervised Graph Clustering - Methodology
At high level, SC uses Graph Convolution Network (GCN) based encoder and optimizes it using a contrastive loss where the nodes are sampled via a random walk. Below we describe the three components of SC and then provide the resulting training algorithm.
Graph Convolutional Encoder: We use I-layer Graph Convolutional Network graph and feature information for each node:
28 to encode the
X (PReLU + PRELU()))))) +I))
where X E Raxd stores the learned d-dimensional representation of each node. Recall that Á is the normalized adjacency matrix and Sx is the k-hop diffusion matrix. I E R=dd is learnable matrix. (e, O'} are the weights of the GCN layer, and P PReLU is the parameteric ReLU activation function 23
f(z) 2; if 2, 0, f(z;)
2; otherwise,
where a a learnable parameter. Our choice of encoder makes the method scalable as 1-layer GCN requires storing only the learnable parameters in the GPU/memory, which is small ( (Od)), where d the dimensionality of the node attributes). The parameter I scales only linearly with the number of nodes n. More importantly, we use mini-batchtr that reduce the memory requirement of forward and backward pass to order O(rsd + d²) where r is the batch size consideration and s is the average degree of nodes, therefore making our method scalable graphs of very large sizes as well. We provide further discussion on memory requirement of our method in Section 3.4
we utilise biased second order Random Walks with restarts to generate points similar to given node and thus capture the local neighborhood of each node. Formally following [18), we start with a source node u, and simulate random walk of length We use & to denote the i-th node the random walk starting from en = u. Every other node in walk e is generated from the distribution:
Random Walk Sampler:
Next, inspired by 40 18
P P c--
Fiz if (2, E, P(G G-1 = = otherwise
(4)
where Tor is the unnormalized transition probability between nodes v and x and Z the normalization constant. To bias the random walks and compute the next edge we follow a methodology similar

---

to | and from node v after traveling (t, v), the transition probability Tew is set to (t,(t,z) ) Wiv where Waar is the weight on the edge between and x, and the bias parameter a defined by:
1 P
1
Opg (l, 2)
if des = O, Opg (1, - 1 iff des = 1, alphapa (1, (1,2)) .if dea 2, (5)
where p the return parameter, controlling the likelihood of immediately revisiting node, q the in-oul parameter [8]. allowing the search to differentiate between "inward" and "outward" nodes, and dez denotes the shortest path distance between nodes / and æ. We note that dzs from node / can only take values E {0, 1, 2}. Setting to a high value (> maz(g, 1)) ensures a lesser likelihood of revisiting a node and setting
low value (< min(g. g. 1)) would make the walk more "local". Similarly, setting > 1 would bias the random walk to nodes near and obtain a local view of the graph encouraging BFS-like behaviour, whereas a q would bias the walk towards nodes further away from and encourage DFS-like behaviour.
Contrastive Loss Formulation: Now to learn the encoder parameters, we use SimCLR style loss function where nodes generated from the random walk are considered be positives while rest of the samples are considered to be negative. That is, we use graph neighborhood information to produce augmentations of node. Formally, let C(u)+ {co, cI....,ct) c.. be the nodes generated by random walk starting at Co = u. Then, C(u) is the set of positive samples ptt while the set of negatives pa is generated by sampling nodes from the remaining set of nodes [n] pp Given p and Pu we can now define the loss for each u as:
Event cippssi((X, X,))
LsimCt..(u) Evert (xppssim(X........ X,)) Every exp(sinn X,,, X.,))
(6)
where sim is some similarity function, for example inner product: sim(u, o)
"
Note that SimCLR style loss functions have been shown to lead to "linearly separable" representations (0 and hence aligns well with the clustering objective [55 ICC. In contrast, loss functions like those used in Node2vec [18] might not necessarily lead to "clusterable" representations which is also indicated by their performance synthetic well real-world datasets.
3.4 Algorithm
Now that have discussed the individual components of our method, describe the overall training methodology in Algorithm [ We begin with the initialization of the learnable parameters in line 1. In line 4,5 generate the positive and negative samples for each node in the current batch. Since we operate with embeddings of only the nodes in batch and their positive/negative samples, we take union of these create "node set" in line 6. This helps in reducing the memory requirements of our algorithm, since we do not do forward/backward pass on the entire AX, but only on the nodes needed for the current batch. Once we have the node set, compute representations for the nodes in the current batch using forward pass in line 8, compute the loss for nodes in this set in line 9, and perform pack-propagate
to generate the gradient updates for the learnable parameters in line 10. Finally, we update the learnable parameters in line 11 and repeat the process for the next batch.
The space complexity for the forward and backward pass of our algorithm is Orrsd + d)), where r is the batch size, s is the average degree of nodes, and d the attribute dimension. The process of random walk generation is fast and can be done in memory, which is abundantly available and highly parallelizable. Therefore, storing the graph structure in memory for sampling of positives doesn't it create memory bottleneck and takes ((m) space. For all the datasets other than ogbn-papers 100M, we store the AX, SX, and in the GPU memory as well, requiring additional ((d) space. However, for very large-scale datasets, one can conveniently store these in the memory itself and interface with the GPU when required, thereby restricting the GPU memory requirement to (rsdd d²).
Space Complexity:
Time Complexity: The forward and backward computation for a given batch takes O(rsd?) time. Hence, for nodes, batch size of r, and K epochs, time complexity is O(Knsd?).
Detecting communities ideally requires nodes to be clustered based on their position, rather than structural similarities. We show in Appendix C that SCGC produces positional embeddings [46)
Embedding property:
Code: Implementation code of &CGC is available at: http::/gittubcco//vvrriSSSCC
5

---

Algorithm GC: Training and Backpropagation
Input: Graph G. Matrices AX E IRaxd and S Raxd number of epochs K, Batched inputs of
nodes B, Self-supervised Loss formulation LSmCLL. Encoder definition ENC, Learning Rate
1: Initialize model parameters: O O
2: for epoch = 2,,,,
........ K do
3: for each batch: b B do
4: Generate Positive Samples p using biased random walks Section 3.3 2 U Yubb
5:
Generate Negative Samples p. using random sampling V u
6:
Compute the node set N₂ UNION(P: -Po) A
7:
Select subset rows (AX)N, and (S,X) corresponding to the node set N₁
8:
Forward Pass compute the representations: X < ENC( ( ( N. (SkX) O II)
9:
Compute loss using the self-supervised formulation: L(X)
10:
Compute Gradients for learnable parameters at time t: ut O e' t Ve.er,z((X)
11:
Refresh the parameters: (O, ()+41 < (0, O' I)+ [6 14 (9,0',Z)
Output: X: X
Table 1: Results on experiments using dataset generated from Stochastic Block Models. SC represents Spectral Clustering [33 the graph, k-means utilises only the attributes, Node2vec uses the graph structure and DGI 533 utilizes both. We experiment with two variants of our method GCC- using only I as the learnable embeddings without using the attributes and &CGC using both graph and attributes, and evaluate the quality of clustering using mean NMI, reported over 3 runs.
SBM Parameters
Baselines: NMI
Our Method: NMI
P
de
SC
k-means
Nece2
DGI
S I
SCG
0.65
0.40
0.5
1.5
0.96
0.25
0.96
0.85
0.99
1.00
0.63
0.45
0.5
1.5
0.45
0.25
0.47
0.55
0.64
0.71
0.63
0.45
1.0
1.5
0.45
0.90
0.47
0.86
0.64
0.91
3.5
Synthetic Dataset Stochastic Blockmodel with Gaussian Features
To better understand the working of our method in scenarios with varied quality of the graph structure and node attributes, propose study on synthetic dataset using Stochastic Block Models (SBM) with Gaussian features. For a given parameter k, the SBM 45 constructs graph G = (V, with k partitions of nodes V. The probability of intra-cluster edge is p and an inter-cluster edge is where p > q Similar studies have been proposed for benchmarking of D and Graph clustering methods [4 40 using SBM. In this work. we create an attributed SBM model, where each node has an s-dimensional attribute associated with it. Following the for clusters (partitions) we generate cluster centers using s-multivariate normal distributions A (0.,, o² Ta), where of is hyperparameter we define. Then attributes of nodes of given cluster are sampled from an s-multivariate gaussian distribution with the corresponding cluster center and o² variance. The ratio o²/o" controls the expected value of the classical between vs within sum-of-squares of the clusters.
GNNs
setup
We compare our method with: k-means on the attributes, Spectral Clustering Node2vec [8]. This choice of baseline methods focuses on different facets of graph data and clustering across which we want to assess the performance of our method. k-means on attributes utilizes only the nodes attribute information. Spectral Clustering is a non-trainne trainaainabee classical algorithm commonly used for solving SBMs, but uses only the graph-structure information. Similarly, Node2vec a common graph-embedding trainable algorithm that utilizes only the structural information. DGI is a scalable SOTA self self-supervised graph representation learning algorithm that uses both structure as well as node attributes.
4 DGI [3 and
To demonstrate the effectiveness of our choice of loss formulation, we also run our method without using any attribute information and using only the learnable embedding I E Rand i.e. II
NNoe that these are parameters for the SBM dataset generation. unrelated to the random walk sampling parameters in the S GC model.

---

Table 2: Datasets and Setup.
Scale
Dataset
# nodes
# edges
feat dim
# classes
Cora
2.708
5,278
1,433
7
Small Scale
Citeseer
3,327
4,614
3,703
6
Pubmed
19,717
44,325
500
3
ogbn-arxiv
169,343
1,166,243
128
40
Moderate/Large Scale
Reddit
232,965
23,213,838
602
41
sebn-products 2.449.029
61,859,140
100
Extra-Large Scale
Ogbn-papers100M
111,059,956
1,615,685,872
128
172
Setup and Observations: We set the number of nodes n 1000 and number of clusters At 10, where each cluster contains n/k 100 nodes, and vary p and q to generate graphs of different structural qualities. Varying 0²/0² controls the quality of the attributes. The first row in table | represents graph with high structural as well as attribute quality. The second row represents low structural as well as low attribute quality. While the last row represents low structural but high attribute quality. We make several observations: 1) Even without using any attribute information, our method performs significantly better as compared to other structure-only based methods like Spectral Clustering and Node2 which demonstrates the effectiveness of our loss formulation and training methodology that promotes clusterability, which is also in line with recent observations IC [55] 2) We observe that DGI depends highly on the quality of the attributes and not able to utilize the high-quality graph structure well, when the attributes are noisy. In contrast, our method uses both sources of information effectively and performs reasonably well even when even only one of the structure or attribute quality is high (first and the last row in the table).
Visualization of the Embeddings: We further observe the quality of the generated embeddings using [-SNE[5]] projected in 2-dimensions. Figure I corresponds to the second setting with weak graph and weak attributes, where we observe that S& generates representations which are more cluster-like as compared to the other methods. Additionally, we note that SC shows similar behaviour in the other two settings as well, the plots for which are provided in the Appendix.
4 Empirical Evaluation
We conduct extensive experiments on several node classification benchmark datasets to evaluate the performance of SC as compared key state-of-the-en (SOTA) baselines across multiple facets associated with Graph Clustering.
4.1 Datasets and Setup
Datasets: We use small scale, 3 moderate/large scale, and extra large scale dataset from GCN (28) GraphSAGE [19 and the OGB-suite 255 to demonstrate the efficacy of our method. The details of the datasets are given Table and additional details of the sources are mentioned in Appendix.
Baselines: We compare our method with k-means on features and 8 recent state-of-the-ard baseline algorithmss including MinCutPool [3) METIS (27] Node2vec [8]] DGI [53], DMoN 59] GRACE [62.. BGRL 48 and MVGRL 21 We choose baseline methods from a broad spectrum of method- ologies, namely methods that utilize only the graph structure, methods that utilize only the features and specific methods that utilize combination of the graph structure and attribute information to provide an exhaustive comparison across important facets of graph learning and clustering. METIS 27 is well-known and scalable classical method for graph partitioning using only the structural information. Similarly, Node2vec [18) is another scalable graph embedding technique that utilizes random walks the graph structure. MinCutPool K and DMoN 49 are graph clustering techniques motivated by the normalized MinCut objective 42
and Modularity 335 respectively. DGI is a SOTA self-supervised method utilizing both graph structure and features, that motivated line of work based on entropy maximization between local and global views of a graph. GRACE [22] in contrast to DGI's methdology, contrasts embeddings at the node level itself, by forming two views of the graph and maximizing the embedding of the same nodes in the two views. BGRL 48) and MVGRL 21 recent SOTA methods for performing self-supervised graph representation learning.
21 39
We measure metrics which are relevant for evaluating the quality of the cluster asssign- ments following the evaluation setup of [56] 21: Accuracy, Normalized Mutual Information (NMI), Completeness Score (CS), Macro-F1 Score (F1), and Adjusted Rand Index (ART). For all these aforementioned metrics, higher value indicates better clustering performance. We generate the
Metrics:
7

---

representations using each representation-leane -earming method and then perform k-means clustering on the embeddings to generate the cluster assignments used for evalution of these metries.
Detailed Setup. We consider the unsupervised learning setting for all the seven datasets where the graph and features corresponding to all the datasets are available. We the labels only for evaluating the quality of the cluster assignments generated by each method. For the baselines, we use the official implementations provided by the authors without any modifications. All experiments are repeated times and the mean values are reported in the Table E We highlight the highest value as well as any other values within 1 standard deviation of the mean of the best performing method, and report the results with standard deviations in the Appendix, due to space constraints. We utilize a single Nvidia A100 GPU with 40GB memory for training each method for a maximum duration of 1 hour for each experiment in Table B For ogbn-papers papers 100M we allow upto ~ 24 hours of training and upto 300GB main memory in addition. We provide a mini-batches and highly scalable implementation of our method S&GC in PyTorch such that experiments on all datasets other than ogbn- -aaeerspp 100M easily fit in the aforementioned GPU. For the ogbn-papers 100M dataset, the forward and backward pass in GC are performed in the GPU, with an interfacing with the CPU memory to store the graph, AX, and SX, and to maintain and update I, with minimal overheads. We also provide a comparison of the time and space complexity for each method in the Appendix.
Hyperparameter Tuning: SC requires selection of minimal hyperparameters: we use k 2 for the k-hop Diffusion Matrix S₂ which offers the following advantages: 1) S = ag_ + a1 A. A² X is a finite computation which can be pre-computed and only requires sparse-dense matrix multiplications. 2) We chose Ou > > 022 giving a higher weight to 0-hop neighbourhood attributes X which allows SCGC to exploit the rich information from good quality attributes even when the structural information is not very informative. 3) Two-hop neighbourhood intuitively captures all the features of nodes with similar attributes while maintaining scalability. This is motivated by the 2-hop and 3-hop choice of neighborhoods in [19 and 25 for these datasets. We additionally tune the learning rate, batch size and random walk parameters, namely the walk length I while using the default values of p 1 and q 1 for the bias parameters in the walk. We perform model selection based on the NMI on the validation set and evaluate all the metrics for this model. Additional details regarding the hyperparameters are mentioned in the Appendix due to space restrictions.
4.2 Results
Table 3 compares clustering performance of SCG to number of baseline methods on datasets of three different scales. For the small scale datasets, namely Cora, Citeseer and Pubmed, we observe that MVGRL outperforms all methods. We also note that MVGRL's performance in our experiments, using the author's official implementation with extensive hyperparameter tuning is slightly lower than the reported values, as has been reported by other works as well 60). Nonetheless, we use these values for comparison and observe that $$GC also performs either competitively or is slightly inferior to MV- GRL's accuracy. For example, the Cora dataset, GC is within 2% of MVGRL's performance and outperforms all the other baseline methods, while on the Pubmed dataset, SC is within ~ 1.5% of MVGRL's performance. Next, we observe the performance note that SCGC significantly outperforms baselines such as k-means, MinCutPool, METIS, Node2vec, DGI and DMoN. Notably, SC is ~ 5% better on ogbn-arxiv, ~ 1.5% better Reddit and ~ 4% better on eebnn-product in terms of clustering NMI as compared to the next best method. The official implementations of GRACE, BGRL, and MVGRL do not scale to datasets with >200k nodes, running into Out of Memory (OOM) errors due to the non-scalable implementations, sub-optimal memory utilization, or the non-scalable methodology. For example, MVGRL proposes diffusion matrix as the alternate view of graph structure, which is a dense n X n matrix hence, not scalable.
moderate/large scale datasets and
We also note that SCGC performs reasonably well in settings where the node attributes are not very informative while the graph structure is useful, as evident from the performance on the Reddit dataset. k-means on the node attributes gives an NMI of only 10% while methods like METIS and Node2vec perform well using the graph structure. Methods like DGI which depend heavily on the quality of the attributes, thus suffer a degradation in performance having a clustering NMI of only ~ 30%, while S3GC which uses both the attributes and graph information effectively outperforms all the other methods and generates clustering with an NMI of 80%.
ogbn-papers, 10bb:: 00M: Finally, we compare the performance of S&GC on the extra- scale dataset with I1 nodes and 1.6B edges in Table g and note that only k-means, Node2vec and DGI scale
8

---

Table 3: Comparison of clustering obtained by our method GC to several state-of-the-art methods.. Metries for evaluation across different datasets and experiments are Accuracy, NMI, CS, Fl and ARI as described in Section We use the official implementations provided by the authors for all the methods and provide additional details in the Appendix. denotes that the method ran Out of Memory (OOM) while trying to run the experiments on the hardware as specified in Section indicates that the method did not converge.
Baseline
Ours
Datasct
Metric
k-means
MinCutPool
METIS
Node2vee
DGI
DMoN
GRACE
BGRL
MVGRL
SC
Accuracy
0.350
0.490
0.540
0.612
0.726
0.517
0.739
0.742
0.763
0.742
NMI
0.173
0.396
0.571
0.584
Cora
CS
0.171
0.407
0.384
0.449
0.568
0.406
0.562
0.595
0.617
0.586
0.360
0.471
0.518
0.692
0.574
0.691
0.721
ARI
0.127
0.317
0.308
0,329
0.511
0.301
0.527
0.534
0,566
0,544
Accuracy
0.421
0.537
0.413
0.686
0.385
0.631
0.675
0.688
NMI
0.199
0.295
0.17
0.240
0.435
0.303
0.399
0.422
0.459
0.441
Citeseer
0.167
0.441
F1
0.394
0,516
0,400
0.401
0.643
0.437
0.603
0.631
0.654
0.643
0.142
0.262
0.150
0.116
0.445
0.200
0.428
0,471
0.448
Accuracy
0.601
0,521
0.693
0.641
0.657
0.351
0.637
0.654
0.675
0.713
NMT
0.314
0.297
0.322
0.257
0.308
0.315
0.333
Puhmed
CS
D.344
0.247
0.291
0.288
0.332
0.179
0.321
0.325
0.355
0.137
0.682
0.649
0.672
0.703
ARI
0.281
0.175
0,323
0,258
0.292
0.108
0.276
0.285
0.310
0.345
Accuracy
D.176
0.242
0,209
0,290
0.314
0,250
0.227
0.350
NMI
0.216
0,380
0.345
0.406
0.412
0.356
0.321
0.463
oghn-
0.198
0.312
0.379
0.326
0.293
0.420
F1
0.121
0,198
0.167
0.220
0.230
0.190
0.166
0.230
0.074
0.139
0.126
0.190
0.223
0.127
0.130
0.270
Accuracy
0.089
0.524
0,709
0.224
0,529
0.736
NMI
0.727
0.306
Reddit
CS
0.112
0.697
0.795
0,300
0.678
0.821
0.068
0.495
0.183
0.260
0.560
ARI
0.029
0.470
0.640
0.170
0.502
0.745
Accuracy
0.200
0,257
0.294
0.357
0.320
0,304
0,402
NMI
0.273
0.430
0.468
0.489
0.467
0.428
0.536
ugbn products
0.360
0.401
0.463
F1 0.124
0,180
0,220
0.247
0.192
0.210
0.250
0.082
0.130
0.145
0.170
0.174
0.139
0.230
Table 4: Results of comparison of the embeddings generated by our method GC as compared
to different scalable methods on ogbn-papers100e 100M with 111M nodes and 1.6B edges.
oghn-papers 100M
Method
Accuracy
NMI
CS
F1
ARI
k-means
0.144
0.368
0.342
0.101
0.074
Node2vec
0.175
0,380
0.352
0.099
0.112
DGI
0.151
0.416
0.386
0.111
0.096
GC (Ours)
0.173
0.453
0.430
0.118
0.110
to this dataset size and run in reasonable time of ~ 24 hours. We observe that SCGC seamlessly scales to this dataset and significantly outperforms methods utilizing only the features (k-means) by ~ 8.5%, only graph structure (Node2vec) by 7% and both (DGI) by ~ 4% in terms of clustering NMI on the gebn-papers 100M dataset.
Ablation Study on Hyperparameters: We perform detailed ablation studies to investigate the stability of GC'ss clustering and provide the same, in the Appendix. We find that S*GC is robust its few hyprraarameters such as walk-length and batch size, enabling near-optimal choice. We note that smaller walk lengths ~ 5 are an optimal choice across datasets, since they are able to include the "right" positive examples in the batch, while using larger walk lengths may degrade the performance due to the inclusion of nodes belonging to other classes in the positive samples. This helps in scalability as well, as we need to sample only a few positives per node. While small batches take more time per-epoch but converge faster, larger batch sizes are better in per-epoch training time, but require more epochs to converge. Both, however, enjoy similar performance in terms of the quality of the clustering.
4.3 Novelty of GCCss Design Choices
Our design choices have unique roles to play which make SCGC both scalable and accurate, by effectively utilizing structure as well as node attribute information for learning clusterable representa-

---

Table 5: Comparison between encoder choices. SCGC GCN refers to SCGC where we use encoder X = (AX)) + (re
While SC refers to encoder X Z. We compare
with structure-only method Nede2Vec and an attribute-dependent method DGL.
Dataset
Node2Vec
DGI
SCG cCN
SC z S'GC
ogbn-arxiv 0,406
0.412
0.460
0,444
0,463
reddit
0.792
0.306
0.777
0.808
0.807
ogbn-products 0.489
0.467
0.528
0.535
0.536
tions. We describe their importance and contrast with other possible design choices in this section, highlighting how these choices put together work the most effectively empirically, contributing to SCG''s novelty.
Encoder: Using a multilayered GCN 128 to capture local graph structure along with attribute information increases the space required to (A))) making any method non-scalable for very large graphs. This issue is also faced by existing methods like MVGRL (21) which compute the entire diffusion matrix, and hence run into OOM errors on larger datasets as discussed earlier. Hence, we use I-layered GCN and precompute AX, requiring only ((d) space. Intuitively, we see that is important to utilize both the attribute information as well as structural information in the encoder. With this motivation, we design S to capture attribute information using 1-layer GCN and capture structural information using learnable parameter I (eq. 2 We empirically verify this intuition with experiments using either just the attribute information (for example on the Reddit dataset) or only the structural information (on the ogbn-arxiv dataset) and summarize our findings in Table 5 We find that the design choice of S GC'ss Encoder is optimal for effectively capturing both sources of information and removing any one source, leads to considerably suboptimal performance.
Positive and Negative nodes sampler: Using random walk sampler offers several advantages it can be computed in a scalable fashion and it samples nodes from a k-hop neighbourhood. We consider several intuitive sampling approaches and discuss the most intuitive and simple sampling approach here: for a given node, we consider all its h-hop neighbourhood nodes as positives, and r randomly sampled nodes as negative. This becomes non-scalable, since calculating a k-hop neighbourhood for all the nodes in the graph has significant computation cost (it is equivalent to computing non-zero elements in A²). Hence, for simplicity, we experiment with & = 1 and note that on the ogbn-arxiv dataset, using this sampling scheme and a learnable embedding as the encoder X = I gives only 0.252 NMI. This is significantly lesser than using a random walk generator for sampling and the same encoding scheme X = I, which gives an NMI of 0.444.
Loss function As we already observe in Section 3.5 using the same encoder X I but a different loss function gives rise to more clusterable embeddings when using the SimCLR loss as compared to using the Node2Vec Vec loss. The experiments on real-world datasets also reinforce these observations, as we see in Table 5 that S&GC z performs better than Node2 Vec on ogbn-arxiv and ogbn-productt datasets where both of the methods use the same encoder and random sampler but different loss functions.
5 Discussion and Future Work
We introduced S*GC, new method for scalable graph elustering with node feature side-information. S*GC is a simple method based on contrastive learning along with a careful encoding of graph and node features, but it is an effective approach across all scales of data. In particular, we showed that S*GC is able to scale to graphs with 100M nodes while still ensuring SOTA clustering performance.
Limitations and Future Work: SC demonstrates empirically that Stochastic Block Models along with Soatuurr-o-GGuusiin features, it is able to identify the clusters accurately. Further theoretical investigation into this standard setting and establishing error bounds for S$GC is of interest. S&GC can be applied to graphs with heterogeneous nodes, but cannot explicitly exploit the information. Extension of SCGC to cluster graphs while directly exploiting heterogeneity of nodes is another open problem. Finally, SCGC like all deep learning methods is susceptible to being unfairly biased by few "important" nodes. Ensuring stable clustering techniques with minimal bias for small number of nodes is another interesting direction.
10

---

References
[1] Carolyn J Anderson, Stanley Wasserman, and Katherine Faust. Building stochastic blockmodels. Social networks, 14(1-2):137-161, 1992.
[2] Muhammed Ali Aydin, Baybars Karabekir, and Abdüi Halim Zaim. Energy efficient clustering- based mobile routing algorithm on wsns. EEEE Access, 9:89593-89001, 2021.
[3] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling, 2019.
[4] Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. In Proceedings of The Web Conference 2020, pages 1400-1410, 2020.
[5] Béla Bollobás, TI Fenner, and AM Frieze. Long cycles in sparse random graphs. Graph theory and combinatorics (Cambridge, 1983), Academic Press, London, pages 59-64, 1984.
[6] Amar Budhiraja, Gaurush Hiranandani, Darshak Chhatbar, Aditya Sinha, Navya Yarrabelly, Ayush Choure, Oluwasanmi Koyejo, and Prateek Jain. Rich-Item Recommendations for Rich- Users: Exploiting Dynamic and Static Side Information, 2020.
[7] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features. In Proceedings of the European conference computer vision (ECCV), pages 132-149, 2018.
[8] Deepayan Chakrabarti and Christos Faloutsos. Graph mining: Laws, generators, and algorithms. ACM computing surveys (CSUR), 38(1):2-es 2006.
[9] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1659--6077 PMLR, 2020.
[10] Ting Chen, Calvin Luo, and Lala Li. Intriguing properties of contrastive losses. Advances in Neural Information Processing Systems, 34, 2021.
[11] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning, arXiv preprint wxXiv:2003.04299 2020.
[12] Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors a multilevel approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(11):1944-1957, 2007.
[13] Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks, 2020.
[14] Santo Fortunato and Darko Hric. Community detection in networks: A user guide. Physics Reports, 659: 2016. Community detection in networks: A user guide.
[15] Alan Frieze and Colin McDiarmid, Algorithmic theory of random graphs. Random Structures & Algorithms, 10(1-2):5 1997.
[16] C Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pages 89-98, 1998.
[17] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to self-supervised learning. Advances in Neural Information Processing Systems, 33:21271 2020.
[18] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864 2016.
[19] Will Hamilton, Zhitao Ying, and Jure Leskovec, Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.

---

[20] Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34, 2021.
[21] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pages 41 16164126. PMLR, 2020.
[22] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 9729-9738, 2020.
[23] Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification, 2015.
[24] R Devon Hjelm, Alex Fedorov, Samuel Sewoiie-arcchldoon Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv: /000iv:/80..00 06670, 2018.
[25] Weihua Hu, Matthias Fey, Marinka Zitikk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 12-22133-2 2020.
[26] Jyun-Yu Jiang, Patrick H Chen, Cho-Jui Hsich, and Wei Wang. Clustering and constructing user coresets to accelerate large-scale top-k recommender systems. In Proceedings of The Web Conference 2020, pages 2177 2020.
[27] George Karypis and Vipin Kumar. Metis: A software package for partitioning unstructured graphs partitioning meshes, and computing fill-reducing orderings of sparse matrices. 1997.
[28] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1609.02900 2016.
[29] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07380 2016.
[30] Risi Imre Kondor and John Lafferty. Diffusion kernels on graphs and other discrete structures. In In Proceedings of the ICML, pages 315-322, 2002.
[31] Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 631-636, 2006.
[32] Weibo Liu, Zidong Wang, Xiaohui Liu, Wenbin Yue, and David Bell. A clustering approach to triage categorization in a&e departments. In 2017 23rd International Conference Automation and Computing (ICAC), pages 1-6. IEEE, 2017.
[33] Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2):129-137, 1982.
[34] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.378.
[35] M. E. J. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577-8582, 2006.
[36] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. In Proceedings the 7th International World Wide Web Conference, pages 161-172, Brisbane, Australia, 1998.
[37] Shirui Pan, Ruiqi Hu, Sai-fu Fung, Guodong Long, Jing Jiang, and Chenggi Zhang. Learn- ing graph embedding with adversarial training methods. IEEE transactions on cybernetics, 50(6):2475-2433 2019.
12

---

[38] Jiwoong Park, Minsik Lee. Hyung Jin Chang, Kyuewang Lee, and Jin Young Choi. Symmetric graph convolutional autoencoder for unsupervised graph representation learning. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pages 6519-6528, 2019.
[39] Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong. Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization, 2020.
[40] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pages 701-710, 2014.
[41] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-95 93,,9993322390 2008.
[42] Jianbo Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888-900 -95, 2000.
[43] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-900 905, 2000.
[44] Peter Henry Andrews Sneath and Robert R. Sokal. Numerical Taxonomy: The Principles and Practice of Numerical Classification. W. H. Freeman and Co., 1973.
[45] Tom A. B. Snijders and Krzysztof Nowicki. Estimation and prediction for stochastic blockmod- els for graphs with latent block structure. Journal of Classification, 14:75-100, 1997.
[46] Balasubramariam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. 2019.
[47] Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. arXiv preprint arXiv: 0000, 2019.
[48] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In International Conference on Learning Representationss 2021.
[49] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. arXiv preprint arXiv:2006. 16904, 2020.
[50] Wenxuan Tu, Sihang Zhou, Xinwang Liu, Xifeng Guo, Zhiping Cai, Jieren Cheng, et al. Deep fusion clustering network. arXiv preprint arXiv:2012.09600, 2020.
[51] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008
[52] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 1rXiv:1710.10003, 2017.
[53] Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
[54] Yang Wang, Deepayan Chakrabarti, Chenxi Wang, and Christos Faloutsos. Epidemic spreading in real networks: An eigenvalue viewpoint. In 22nd International Symposium on Reliable Distributed Systems, 2003. Proceedings., pages 25-34. IEEE, 2003.
[55] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data, 2020.
[56] Rongkai Xia, Yan Pan, Lei Du, and Jian Yin. Robust multi-view spectral clustering via low-rank and sparse decomposition. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1), Jun. 2014.
13

---

[57] Rex Ying, Ruining He. Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983, 2018.
[58] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen. Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812-5823, 2020.
[59] Tian Zhang and Usama Fayyad. Birch: a new data clustering algorithm and its applications. Data Min. Knowl. Disc, pages 141-182, 1997.
[60] Han Zhao, Xu Yang, Zhenru Wang, Erkun Yang, and Cheng Deng. Graph debiased contrastive learning with joint representation clustering, In Proc. I/CAI, pages 3434 3440, 2021.
[61] Yuchen Zhao and Philip S Yu. On graph stream clustering with side information. In Proceedings of the 2013 SIAM International Conference on Data Mining, pages 139-150. SIAM, 2013.
[62] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006. 04131, 2020.
14


Reviews:
[{"review_id": "nPUCcVZ5Oo", "reviewer": "Reviewer_8qP4", "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. \n\nS3GC 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.", "questions": "Q1. Please check Line 214 and see whether \"r\" is missed.\n\nQ2. Please report the details of running times for each method. As this paper studies scalability, these efficiency results are important.\n\nQ3. 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.\n\nQ4. 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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nS1.\tThe paper is in general easy to follow. \n\nS2.\tScalable clustering is important in practice.\n\nS3.  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. \n\nS4.\tThe proposed model can be applied to billion-edge graphs for clustering.\n\nS5.\tThe 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.\n\nW1. 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.\n\nW2. Seems there is a minor error in line 214. The author states that the time complexity is O(Knsd2), seemingly forgetting “r”.\n\nW3. I did not find the results on detailed running times of different methods (though roughly mentioned).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "f7Oe9xPMSVV", "reviewer": "Reviewer_2dNT", "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. \n\nS3GC 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. \n\nAuthors 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.", "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).\n\nThis 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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe proposed approach is simple and intuitive.\n\nThe paper is well written and easy to understand.\n\nThe 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.\n\nThis 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.\n\nExtensive experimentation is done to show the effectiveness of the approach on small-scale as well as large-scale datasets.\nSpace and time complexity provided add to the clarity of the central idea of the paper about scalability.\n\n**Weaknesses**\n\nIMO 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.\n\nIt 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.\n\nAnother potential weakness is that all of the datasets are homophilous. I am not sure how will this perform on heterophilous graphs.\n\nAnother weakness is that it is not clear how this approach is directly applicable to heterogeneous graphs (which authors mention as well). \n\nAs authors point out, there is no theoretical justification for the proposed method. Perhaps one can borrow ideas from [1]\n\n[1] Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss\n\n[2] SIGN: Scalable Inception Graph Neural Networks", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5RGX04GsoC", "reviewer": "Reviewer_4aEs", "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. ", "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.\n\n2. 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)\n\n3. 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?\n\n4. Similar comment for observation 3 (line 249), \n\n5. 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]. \n\n6. 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.\n\n7. 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. \n\n[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.\n\n[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.\n", "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. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Related works are well covered.\n2. Proposed method is simple and neat. It scales well to large graphs of the order of 100 million nodes.\n3. The standard experiment setup has been followed. Synthetic data generation uses the well-studied SBM algorithm.\n4. Experiments on large scale datasets show the superior performance of the proposed method in comparison with the baselines.\n5. The paper is written in a simple and easy-to-follow manner. \n\nWeaknesses:\n1. 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. \n2. 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept