Efficient block contrastive learning via parameter-free meta-node approximation
Authors: Gayan K Kulatilleke
Marius Portmann
Shekhar S. Chandra
Venue: Submitted to ICLR 2023 (2023)
Keywords: Contrastive
approximation
efficient
parameter-free
block
theory

Abstract: Contrastive learning has recently achieved remarkable success in many domains including graphs. However contrastive loss, especially for graphs, requires a large number of negative samples which is unscalable and computationally prohibitive with a quadratic time complexity. Sub-sampling is not optimal and incorrect negative sampling leads to sampling bias. In this work, we propose a meta-node based approximation technique that can (a) proxy all negative combinations (b) in quadratic cluster size time complexity, (c) at graph level, not node level, and (d) exploit graph sparsity. By replacing node-pairs with additive cluster-pairs, we compute the negatives in cluster-time at graph level. The resulting Proxy approximated meta-node Contrastive (PamC) loss, based on simple optimized GPU operations, captures the full set of negatives, yet is efficient with a linear time complexity. By avoiding sampling, we effectively eliminate sample bias. We meet the criterion for larger number of samples, thus achieving block-contrastiveness, which is proven to outperform pair-wise losses. We use learnt soft cluster assignments for the meta-node constriction, and avoid possible heterophily and noise added during edge creation. Theoretically, we show that real world graphs easily satisfy conditions necessary for our approximation. Empirically, we show promising accuracy gains over state-of-the-art graph clustering on 6 benchmarks. Importantly, we gain substantially in efficiency; up to 3x in training time, 1.8x in inference time and over 5x in GPU memory reduction.


Under review as a conference paper at ICLR 2023
EFFICIENT BLOCK CONTRASTIVE LEARNING VIA PARAMETER-FREI META-NODE APPROXIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
Contrastive learning has recently achieved remarkable success in many domains including graphs. However contrastive loss, especially for graphs, requires a large number of negative samples which is unscalable and computationally prohibitive with quadratic time complexity. Sub-sampling is not optimal. Incorrect neg- ative sampling leads to sampling bias. In this work, we propose a meta-node based approximation technique that can (a) proxy all negative combinations (b) in quadratic cluster size time complexity, (c) at graph level, not node level, and (d) exploit graph sparsity. By replacing node-pairs with additive cluster-pairs, we compute the negatives in cluster-time at graph level. The resulting Proxy ap- proximated meta-node Contrastive (PamC) loss, based on simple optimized GPU operations, captures the full set of negatives, yet is efficient with linear time complexity. By avoiding sampling, we effectively eliminate sample bias. We meet the criterion for larger number of samples, thus achieving cook-coontastiiveness,, which is proven to outperform pair-wise losses. We use learnt soft cluster assign- ments for the meta-node construction, and avoid possible heterophily and noise added during edge creation. Theoretically, we show that real world graphs easily satisfy conditions necessary for our approximation. Empirically, we show promis- ing accuracy gains over state-of of-the-art graph clustering on 6 benchmarks. Impor- tantly, we gain substantially in efficiency; up to 2x in training time and over 5x GPU memory reduction. The code is publicly available.
INTRODUCTION
Discriminative approaches based on contrastive learning has been outstandingly successful in prac- tice (Guo et al., 2017; Wang & Isola 2020), achieving statc-of-the-ard results (Chen et al. 2020a)
or at times outperforming even supervised learning (Logeswaran & Lee| [2018] Chen et al. 2020b).
Specifically in graph clustering, contrastive learning outperform traditional convolution and
bated Graph Neural Networks (GNN) on speed and accuracy (Kulatilleke et al. 2022).
While traditional objective functions encourage similar nodes be closer in embedding space, their penalties do not guarantee separation of unrelated graph nodes (Zhu et al. 20211)) Differently, many modern graph embedding models (Hamilton et al. [017]] Kulatilleke al.] 2022). use contrastive objectives. These encourage representation of positive pairs to be similar, while making features of the negatives apart in embedding space (Wang & Isola 2020). A typical deep model consists of a trainable encoder that generates positive and negative node embedding for the contrastive loss (Zhu al., 2021a). It has been shown that convolution is computationally expensive and may not be necessary for representation learning (Chen et al., 2020a). As the requirement for contrastive loss simply an encoder, recently researchers have been able to produce state-of of-te-------rr art results using simpler and more efficient MLP based contrastive loss implementations (Hu et al. 2021 Kulatilleke jet al. 2022). Thus, there is a rapidly expanding interest and scope for contrastive loss based models.
We consider the following specific but popular (Hu et al. 2021: Kulatilleke et al. 2022) form of contrastive loss where 7 is the temperature parameter, KKu is the relationship between nodes i and the loss for the 1th node is:
Σ/=1 1 7 exp (sim (2,, 2z) 7)
B
4, = -lo
(1)
Σk=1 1 [( exp (sim (z) T)

---

Under review as a conference paper at ICLR 2023
When no labels are present, sampling of positive and negative nodes plays crucial role (Kipf & Welling 2016) and is a key implementation detail in contrastive methods (Velickovic et al. 2019).
Positive samples in graphs are typically connected by edges (Kulatilleke et al. (021). similar to words in a sentence in language modelling (Logeswaran & Lee] Often data augmentation is used generate positive samples; [Chen al. (2020b) used crop, coloring. blurring. However, it is harder to obtain negative samples. With no access to labels, negative counterparts are typically ob- tained via uniform sampling (Park al. 2022), via wynthesiing/anggeentt adding noise. Also, in graphs. adjacency information can be exploited to derive negatives (Hu et al., 2021 Kulatilleke et al., 2022) for feature contrastion. However, while graphs particularly suited for contrastive learning, to be effective, a large number of negative samples must be used (Wang & Isola 2020 (e.g., 65536 in He et (2020). D. along with larger batch sizes and longer training compared to its supervised counterparts (Chen et al., (022b). Prior work has used data augmentation-ban based con- trastive methods Zhu et al. (2020) 2021b), negative samples using asymmetric structures Thakoor ct al. (22TT or avoided negative samples altogether via feature-level decorrelation [hhang et al. WhileTThakoor
(Chen et al., 2020b) or
(2021b) While Thakoor et al. (2021); y: Zhang et al.] (2021b) address complexity and scalability, as seen in Appendix TaaendiixTable44 their performance can be further improved.
Unlike other domains, such as vision, negative sample generation brings only limited benefits to graphs (Chuang al., 22200] /Zhu et al.) 2021a). To understand this phenomenon, observe the raw embedding of USPS image dataset, in the top row of F which looks already clustered. A direct consequence of this is that graphs are more susceptible to sampling bias (Chuang et al.) 2020 Zhu iet al. 20) Thus, graph contrastive learning approaches suffer from insufficient negatives and the complex task of sample generation in addition to O(N2) time complexity required contrast every negative node.
However, what contrastive loss exactly does remain largely a mystery (Wang & Isola 2020). For example, AArora et al.) (2019)'s 's analysis based on the assumption of latent classes provides good theoretical insights, yet their explanation on representation quality dropping with large number of negatives is inconsistent with experimental findings (Chen et al.] 2020b). Contrastive loss is seen as maximizing mutual information (MI) between two views. Yet, contradictorily, tighter bound on MI can lead to poor representations (Wang& & Isola 2020).
Motivation: Prior work has approximated the task in order to approximate the loss. SWAV (Caron et al., 2020 learns to predict a node prototype code of an augmented view from the other view. GRCCA (Zhang et al. 2021a) maps augmented graphs to prototypes using k-means for alignment. PCL. (Li al. 2020) assigns several prototypes of different granularity
image enforcing its representation to be more similar to its corresponding prototype. However, all these works use some form of data augmentation which assumes that the task-relevant information is not significantly altered and require computationally expensive operations.
Wang & Isola (2020) identifies alignment and uniformity as key properties of contrastive loss: align- ment encourages encoders to assign similar features to similar samples; uniformity encourages a feature distribution that preserves maximal information. dissimilar. Even with the rare possibility of two identical cluster centers initially, one will usually change or drift apart. space, similar to nodes, in order to preserve much information of the data as possible. Uniformly distributing points on a hyperspace is defined as minimizing the total pairwise potential w.r.t. a certain kernel function and is well-studied (Wang& & Isola 2020
fair to assume that latent clusters are
intuitive that cluster centers should uniformly distributed in the hyper-
Thus, we are naturally motivated to use the cluster centers as meta-nodes for negative contrastion. By aggregation, all its constituent nodes cab be affected. Thus, we avoid sampling, effectively climinate sample bias, and also meet the criterion of larger number of samples. Learned soft cluster assignments can avoid possible heterophily and add robustness to noise in edge construction.
In this work, we propose a novel contrastive loss, PamC. which uses paramaterless proxy meta- nods approximate negative samples. Our approach indirectly uses the full set of negative samples and yet is efficient with a time complexity of O(N). Not only does PamCGGC based on PaaCC] outperform or match previous work, but it is also simpler than any prior negative sample generation approach, faster and uses relatively less GPU memory. It can be incorporated to any contrastive learning-base based clustering model with minimal modifications, and works with diverse data, as we demonstrate using benchmark datasets from image, text and graph modalities.
2

---

Under review as a conference paper at ICLR 2023
training (xE(x,x)
ACC, AM,,FI,
feeo
feo
Gan
fcz
fco
cCo
czo
ploot
mod features
Chustering
Self supervision
Inter-cluster cluster centers regulsive
Cluster Centers
repulse attract
KL (1
Distribution (0*)
Real cluster centers NNggatiess
Hog(exp(sim((G...))
Cluster
Centres
Graphadges - Positioes
log(exp(sim(<x.2) (x))))
cltster cluster attracts
Figure 1: PamCGC jointly learns structure and clustering via probabilistic soft assignment which used to derive the real cluster centers A. used as proxy for negative samples. Grey dotted sec- tion outlines the training components. Cluster centroids μ obtained by pre-training reconstruction. Red dotted section our core contribution: we use ja as an efficient approximation, computing centroid-pairs instead of node-pairs, achieve block-contrastivness and do so graph level, not instance level.
AE for
To summarize, main contributions are:
We introduce efficient novel parameter-free free proxy. PamC for negative sample approxi- mation that is scalable, computationally efficient and able to include all samples. It works with diverse data, including graphs. We claim PamC is the first implicitly use the whole graph with O(N) time complexity, in addition to further 3-fold gains.
We provide theoretical proof and show that real world graphs always satisfies the necessary conditions, and that PamCGG is block-contrastive, known to outperform pair-wise losses.
Extensive experiments on 6 benchmark datasets show PamCGC using proposed PamC is par with better than state-of-the-ar graph clustering methods in accuracy while achieving 2x training time and 5x GPU memory efficiency.
2
IMPLEMENTATION
First describe PamC which is parameter-free proxy efficiently approximate the negative samples, as shown in Figure [
Next, we introduce PanCGC a self-supervised model based on PamC to simultancously learn discriminative embeddings and clusters.
2.1 NEGATIVE SAMPLE APPROXIMATION BY META-NODE PROXIES
Contrastive loss makes positive or connected nodes closer and negative or unconnected nodes further away in the feature space (Kulatilleke et al., 2022). However, in order to be effective, all negative nodes need to contrasted with 2; which is computationally expensive. A cluster center is formed aggregated representation,
by combining all member nodes, and can be seen its compositional elements. Motivated by this, we use the cluster centers to enforce negative con- trastion. Specifically, contrast every cluster center (i with every cluster center úi where + j.
proxy, of
3

---

Under review as a conference paper at ICLR 2023
Following Arora et al. 2 Chuang al. (2020). assume underlying set of discrete latent classes which represents semantic content, le., similar nodes Fy. 2, are the same latent class j.. Thus, derive our proxy for negative samples as:
C
c
Eprozy = log E
[azib] exp (sim (Pas (ub) T),
(2)
Note that, Eproay contains no i or terms! resulting in three fold gains. Firstly, we replace E with a more efficient > where N C. typically many magnitudes, in almost all datasets, as evident from Table | Secondly, the Eprozy is at graph level with time complexity of O(N) rather than an instance level O Finally, given real world graphs (especially larger graphs.) are sparse, sparse implantation for the positives, using edge-lists, will result in third efficiency gain, which is only possible by not having to operate on the negatives explicitly.
Note that prerequisite of the proxy approximation is the availability of labels to construct the learned cluster centers D. which we explain in the next section. Thus, the complete graph level contrastive loss can be expressed as:
N
N
8 Peontrast
Σ 1=1
log
Σ ==1
Pa exp (sim (z,, 2,). .)) + l provys
(3)
N
Theoretical explanation. The standard contrastive loss uses Jensen-Shannon divergence, which yields log 2 constant and vanishing gradients for disjoint distributions of positive and negative sam- pled pairs (Zhu et al., (021a). However, in the proposed method, positive pairs are necessarily edge-linked (either explicitly or via influence (Kulatilleke et al. (2022)). and unlikely to be disjoint. Using meta-nodes for negatives, which are compositions of multiple nodes, lowers the possibility of disjointness. An algorithm using the average of the positive and negative samples in blocks proxy instead of just one point has a strictly better bound due to Jensen's inequality getting tighter and is superior compared to their equivalent of element-wiss contrastive counterparts (Arora al. 2019). The computational and time cost is a direct consequence of node level contrastion. Given, N T clusters, circumvent the problem of large N by proposing proxy-ed negative contrastive objective that operates directly at the cluster level.
Establishing mathematical guarantee: Assume node embeddings Z {21, 22, 23 ... 2N), }, clusters Σ 2im
{1r M2... ... .C): label assignment operator label(z;) such that μıa a temperature hyperparameter 7 and,
[[etabbl((s)==a] Zi.
0.
j i +
similarity (1,j,, 25) = sim 2z)
(4)
|=
Using sim((z; 2z) as the shorthand notation for similarity (i. mz), the classic contrastive loss is:
lOSSNN
log
Σ (x 2))))
(5)
Similarly, we can express the cluster based contrastive loss as:
C
M
losscc
Σ
log
Σ
exp(sim (a, b, Hay (T)
(6)
C
a=1
As 0 sim < 1.0, establish the condition for our inequality as;
lOSSNN
log(N)
lossee
log [1 (C
1)e
We provide the full derivation in Appendix A.1
4

---

Under review as a conference paper at ICLR 2023
0.1
=1.0
- 5.0
ratio
=10
Figure 2: Nodes N vs Clusters C' with different temperature values. Grey surface shows the ralio 1.0 inequality boundary. Generally, real world graphs satisfy the condition ratio 1.0 easily. Best viewed in color.
As C > (minimum 2 needed for cluster), and log(2:) >> 0 is strictly increasing, N > 1+ (C 1)e" is the necessary condition, which is easily satisfied for nearly all real world datasets and as seen in Figure 2 for multiple temperatures.
Thus, as lossNN > losscc. loSsN upper bounds lossoc, the more efficient variant. Additionally lossce benefits from block-contrastivveness (Arora al. 2019), achieves a lower minima and uses the fullest possible negative information. We also show, experimentally, that minimizing lossce results in effective, and sometimes better, representations for downstream tasks.
2.2 CONSTRUCTING THE META-NODE CLUSTER CENTERS (i)
In order to derive the real cluster centers P., which is distinct from the learnt cluster centers 14, simply aggregate all the node embedding & of a cluster using its label. Even with unlabeled data, label() can be accomplished using predicted soft labels. The intuition here is that, during back- propagation, the optimization process will update the constituent node embeddings, z, to incorporate negative distancing. Thus,
1 N Σ [clabelle))
Pc
where label(c) is either the ground- or learnt soft labels. Accordingly, our proxy can equally be used in supervised and unsupervised scenarios and has wider general applicability as an im- provement of the contrastive loss large. Finlay, Equation can be realized with so soft fomara)) and mean() operations, which are well optimized GPU primitives in any machine learning framework. We provide a reference pytorch implementation.
2.3 OBTAINING THE SOFT LABELS
Graph clustering is essentially unsupervised. To this end, following Xie al. (2066) Guo et al. (2017); Wang et al. (2019; Kulatilleke et al.) (2022), we use probability distribution derived soft- labels and self-supervision mechanism for cluster enhancement. Specifically, we obtain soft cluster assignments probabilities giu. for embedding and cluster center pa. In order to handle differ- ently scaled clusters and be computationally convenient (Wang et al., (2019), we use the student's 's !-distribution (Maaten & Hinton, 2008) kernel for the similarity measurement between the em-
bedding and centroid:
(1 + 1| (1, 1| Mu /n)
Mml 112 /1) TH
4ia
where, 17 is the Student's t-distribution' 's degree of freedom. Cluster centers j are initialized by K K-means embeddings from the pre-trained AE. We use [quu] as the distribution of the cluster assignments of all samples, and y=1 for all experiments following Bo et al. (2020); Peng et al. (202T) Kulatilleke et al. (2022)
5

---

Under review as a conference paper at ICLR 2023
Table 1: Statistics of the datasets (left) and PamCGC CerGGCyypeene hyperparameters (right).
Dataset
Type
Nodes
Classes
dimension
K
LR
USPS
Image
9298
10
256
2
4
0.5
10
HHAR
Record
10299
561
0.5
12.5
2
1.5
10 10-3
REUT
Text
10000
4
2000
0.2
0.25
10
ACM
Graph
3025
1870
0.5
0.5
0.5
10
CITE
Graph
3327
3703
2
10 10-3
DBLP
Graph 4057
334
2
2.5
3
0.5
10 10-3
Nodes closer in embedding space a cluster center has higher soft assignment probabilities in Q. A target distribution P that emphasizes the confident assignments is obtained by squaring and normalizing Q, given by:
Piuul Ex qiu
Piu Σx (Riee Ei qa:)
(10)
where E: Yiu is the soft cluster frequency of centroid u.
Following Kulatilleke et al. (2022), we minimize the KI. divergence between Q and P distributions, which forces the current distribution to approach the more confident target distribution P. KI.
divergence updates models more gently and lessens severe disturbances the embeddings (Bo
cct al. 2020). Further, it can accommodate both the structural and feature optimization targets of
PamCGC We self-supervise cluster assignments by using distribution to target distribution P,
which then supervises the distribution Q in turn by minimizing the KL. divergence as:
losScluster (L(PII))
ΣΣ
Piulog Pin
(11)
Gia
The final proposed model, after incorporating PamC
contrastive objective with self-supervised clustering, where 0 controls structure incorporation and B > controls cluster optimization is:
Pam CGC
Linal = alpenntrast (K, r) + Bloss
(12)
2.4 COMPLEXITY ANALYSIS
Given input data dimension d and AE layer dimensions of d1, d.......dd... following Kulatilleke et al. (2022), OAE O(N df...d f,/22 for PamCGC Assuming K clusters, from Equation
the time complexity is Odiustr O K
N log.NN N) following Xie al. (2016).
For PamC we only compute ||=|| and zj for the actual positive edges E using sparse matrix resulting time complexity O+ O Edz), linear with the number of edges E. with d, embedding dimension. For the negatives, we use the moda-node based negatives O_ O(CC) where C' is the meta-node. Note that, for real graphs, N C in many magnitudes. Thus. the overall time complexity is linearly related to the number of samples and edges.
EXPERIMENTS
We evaluate PamCGC transductive node clustering comparing to state-of- the-art self self-supervised, contrastive and (semi- jsupervised methods.
Datasets. Following Bo et al. 2020); Peng et al. 2222 Kulatilleke al. (2022). experiments conducted on six common clustering benchmarks, which incl Include one image dataset (USPS (Le Cun
al. 1990)), one sensor data dataset (HHAR (Stisen et al. 2015)), text dataset (REUT (Lewis et al. 2004 and three citation graphs (ACM², CITE and DBLP'). For the non-graph data, we use
We follow Bo al. (020) of the term 'self-supervised" consistent with the GCN training method.

---

Under review as a conference paper at ICLR 2023
undirected k-nearest neighbour (KNN (Altman 1992)) Bo et al. (2020); Peng et al. (2021). Table summarizes the datasets.
generate adjacency matrix A following
Baseline Methods. We compare with multiple models. K-means (Hartigan & Wong 1979 is classical clustering method using raw data. AE (Hinton & Salakhutdinov 2006) applies K K-means to deep representations learned by auto-encoder. DEC (Xie al. (016)) clusters data in jointly optimized feature space. IDEC (Guo et al.) (017) enhances DEC by adding KL divergence- baased
reconstruction loss. Following models exploit graph structures during clustering: SVD (Golub & Reinsch, 197I) applies singular value decomposition to the adjacency matrix. DGI (Velickovic
al. 2019) learns embeddings by maximizing node MI with the graph. GAE (Kipf & Welling
2016 combines convolution with the AE. ARGA (Pan et al. (0188) uses an adversarial regularizer to guide the embeddings learning. Following deep graph clustering jointly optimize embeddings and graph clustering: DAEGC (Wang et al., 2019), uses an attentional neighbor-wise strategy and
clustering loss. SDCN (Bo et al. | 2000), couples DEC and GCN via fixed delivery operator and uses feature reconstruction. AGCN (Peng et al. 2021), extends SDCN by adding attention-based
delivery operator and uses multi scale information for cluster prediction. CGC (Park et al. 2022) uses multi-level, hierarchy based contrastive loss. SCGC and SCGC* (Kulatilleke et al. 2022
uses block contrastive loss with an AE and MLP respectively. The only difference between SCGC
and PamCGG is the PareC Also SCGC* is the current state-of-the-art. Thus, it is used as the benchmark.
Evaluation Metrics. Following Bo et al. 2020 Peng al. (2021), we use Accuracy (ACC), Normalized Mutual Information (NMI), Average Rand Index (ARI), and macro Fl-score (FI) for evaluation. For each, larger values imply better clustering.
3.1 IMPLEMENTATION
The positive component of our loss only requires the actual connections and can be efficiently rep- resented by sparse matrices. Further, the negative component of the loss is graph-based, and not instance based, thus needs be computed only once per epoch. Thus, by decoupling the negatives, our loss is inherently capable of batching and is trivially parallelizuble. Computation of the negative proxy, which is only C' C does not even require a GPU!
For fair comparison, we use the same 500 - 500 2000 - 10 AE dimensions as in Guo et al. (2017):
Bo et al. [2000;] Peng et al. (202T): Kulatilleke et al. (202)) and the same pre-training procedure, i.e.
30 epochs; learning rate of 10 for USPS, HHAR, ACM, DBLP and 10 for REUT and CITE; batch size of 256. We made use of the publicly available pre-trained AE from Bo al. (2020). We
use once computed edge-list for training. which is not needed during inference. For training, for each dataset, we initialize the cluster centers from K-means and repeat the experiments 10 times with 200 epochs prevent extreme cases. We cite published accuracy results from Bo et al. 2020); Peng of al. (202T); Kulatilleke et al. (2022) for other models.
For all timing and memory experiments, replicate the exact same training loops, including in- ternal evaluation metric calls, when measuring performance for fair comparison. Our code will be made publicly available.
3.2 RESULTS
Comparison of results with state-of-the-art graph and non-graph datasets are in Table 2 and Table 3 respectively. For the graph data, PamCGC is state- of-the-art for DBLP. A paired-t test shows ACM and CITE results to be best for both SCGC* and PamCGCC In non-graph results, PPaMCGCcomms second hest in USPS image data. While results for HHAR somewhat lagging, [PamCGCTis is the best for REUT. Generally achieve better results on the natural graph datasets; ACM, DBLP and CITE, while being competitive on other modalities. We present the qualitative results in Appendix A.4
We show our hyperparameters in Table 1
hhtp:///dl.am.orgg
bhtpps//dblp.umm-trree..dd "htp://citeseerx.sst.p ist, wwt.rrr.ws.s..sseee/ieeee..r
7

---

Under review as a conference paper at ICLR 2023
Table Clustering performance the three graph datasets (meanistd)). Best results are bold. Results
reproduced from Bo et al. (2020); Peng et al. (2021); Kulatilleke et al. (2022): Park et al. (2022).
SCGC (Kllatilleke et al.| 2022) uses neighbor based contrastive loss with AE while SCGC* variant
uses hop cumulative Influence contrastive loss with MLP, same our PamCGC
DBLP
ACM
CITE
Method
ACC
NMI
ARI
ACC
NMI
ARI
ACC
NMI
ARI
K-means
38.7:10077
11.5::04
7.0004 319
67.3++0.7
32.4+0.5
30.6
67.6
39.343322
16.943.2
13.4330 36.1
AE
51.4:10.4
25.4:00.
12.210.4
52,5
818810.1
49.31.02
$4.6.02
82.010.1
57.110.1
27.6.00.1
29.3.0.1
53810.11
DRC
58.2.10.6
29.5.:0.3
21.9104
59.4...5
84.3.1.8
54.541.5
60.6
84.5
55.9:0.2
28.340.3
28.14:4
28.
52.6102
IDEC
60.3++0.6
31.2+00.5
25.4+06
61.3#06
85.1
16.6+1
62.2+115
85.1
6..54144
27.2+244
25.7+2.7
61.6+11
SVD
29.3:1:044
0.1::0.0
0.0:0.11
13.3#22
39.945.8
3.84433
3.1+-4.2
30.1
24.1
1.7
0.1::0.3
11.4
DGI
12.5:12.4
3.711.88
1.710.9
29.3133
88.01111
67.74:2.55
88.0110
38.81122
38.1119
60.41099
GAF
61.2.11.2
M0.8.1099
22.0
61.4222
84.5.144
55.4119
59.5.13.1
84.7
61.
14.6.10.7
33.6.112
57.40.88
VGAE
58.62:0.1
26.9::0.1
1799+0.1
58.7+0.1
84.1
53.24005
57.7+0.7
84.240.2
61,0=044
32.740.3
33.1
57.7
ARGA
61.6.110 26.8.1.0 22.710.3
61880.9
86.111.2
55.7.114
62911.11
86.111.2
56,91077
34.5.00.8
33.4.155
548.088
DARGC
62.1
32.5
21
0:05
0.7
869928
56.2442
59
4999
87.1
87.
6..5
36.4
37
12.
CGC
17.6+0.5 46.1=066
19.7+1.1
77.2=0.
92.3+03
72.9=077
78
92.3+03
69.6=0.6
44.6=0.6
46.0=
55.77
SDCN
68.11118 19.5
39.242..
6.57
90.5
68.3
7399104
90
66.0
18.740.3
40.2:0.4
63.4.022
AGCN
73.3-204
39.7+00
42.5+00.3
728+006
90.6+022
68.440.5
74.2404
90
68840.2
41.5+033
438+03
02.4+02
SCOC
77.7+0.1 47.1+0.2
5122002
77.30011
92.6000
73,3+0000
79,2
92,50000
03.2=0.1
46,8+011
50.0
63.3+000
SOGC
77.7+0.11
47.1=0.11
50.2+0.11
775
92.620.0
73.7
79.4
926200
03.3000
46.9+0.0
50.2:0.00 63.4+00.0
PamOGC
79.6.10.0
49.2.10.1
54.110.11
79.0.0.11
92.5100
73.7.0.1
79.210.11
92500.0
0.
47.3.0.3
50.1104
63.4.0.2
Table 3: Clustering performance the three non-graph datasets std). Best results are bold; second best is underlined. Results reproduced from Bo et al. (2020); |eng et al. (202I): Kulatilleke
et al. 2022). SCGC (Kulatilleke et al., 2022) uses neighbour based contrastive loss with AE while
SCGC variant uses r-hop cumulative Influence contrastive loss with MLP, same as our PamCGC
Dataset
Metric
means
DAEGC
AGCN
SCGC
SCGC
PamCGC
ACC
66.82.10.04
63.1020.31
16:19.0.722
73.55:10.00
78.08:10.19
80.98.1.288
82.90-10.08
84.91-1-0.06
USPS
NMI
62.63=0.055
60.6920.58
51.08:0.37
71.12::0:24
79.51+0.27
79.6420.32
82.51
84.16:20.10
80.32-:0.38
ART
54.58.10.06
50.30-10.55
40.9610.59
63.33.1034
71.8410.24
10.4
76.48.10.11
79.50-10.06
70.55.10.56
F1
64.78=0.03
61.8420.43
53.63-+1.05
72.45:00.99
76.984-0.18
77.61
80.06-20.05
81.54:10.06
78.82-+0..1 17
ACC
39.9800.02
02.3311001
71 1133000.36
76.31=2.19
84.26:0017
88. 88.11=0.33
09.49-0.22
89.36:20.16
84.94::1.00
58.8610.01
55.06:1..39
62.95:10.36
69.10:::2.88
79.90:10.09
8..44:062
84.24:00229
84.50-10.41
79.54-100.65
HHAR
ARI
46.0910..2
1..6311.63
51.47:0.73
60.38.12.15
12.04
77.0710..6
79.28 0.228
79.11
72.57.1..20
FI
58.33+0.03
62.64=0.97
71.55:0.29
76.89:22.18
82.58
88.00=0.53
09.59-10.23
89.48-10.17
1.
ACC
54.4100011
54.4010.27
60.55:0:23
65.50110.13
79.3010.11
79.3011.07
80.32:10.04
00.35:10:00
81.78:10001
NMI
41.5410.51 25.92.10.41
25.51
30.55.10.29
56.89110.27
57.831 1.01
55.633110005
55.16:10.00
59.13
REUT
ARI
27.95 19.61
26.18:10.36
31.1240.118
39.58:0.32
60.55
59.67:10.111
57.80-10.01
63.51-100.0
FL
41.2812.43
43.5311042
57.14.1..17
61.82,10.13
66.1510.15
66.1610.64
63.66.10.33
66.54.10.01
69.48
3.3 PERFORMANCE
In Figure 3 we compare the GPU based training time and GPU memory. Our model times also include the time taken for the cumulative influence computation. For all the datasets, PamCGG is superior by 2.2x training time and 5.3x GPU memory savings. Especially, for larger datasets USPS, HHAR and REUT. PamCGC uses 5.2,7.7,8.7x less GPU memory.
Additionally, we used CITE dataset (3327 nodes) to create synthetics nodes. For scale factor as contact nodes n times, along with edge-lists. Figure Bright) shows the scaled edges and nodes for scale factors 5, 10. 15... 45 and the GPU memory and training time for 1 epoch T4 GPU with 16GB memory. Without [Pam[] scales over is not possible due to running out of memory. With [amC] over x45 (150,000 nodes) is possible. GPU and memory increase is liner confirming the theoretical time complexity. We used CITE as it is very common dataset. We used synthetic node creation to capture variation over node size.
Google colab
A. GPU time breakup. Appendix A.6 shows the CITE dataset results with PamC when scaled from 1.. 20 in steps of 1.
3.4
ABLATION STUDY
To investigate PamC ability to generalize to other models, we incorporate it to SDCN and AGCN models, modifid for contrastive loss. Figure g shows the GPU training time and accuracy. As PamC is a loss function, there is difference in the inference times. As expected, training times
8

---

Under review as a conference paper at ICLR 2023
Training time (s)
GPU memory usage (Gb/epach)
16
max 1608 CPU memory (T4)
2.5
GPU memeory VS number of nodes (CITE)
00
#SCGCY
#SDCM
#NODEL
#SCGC
#AGCN
12
vato PANC time
PAMC memory
nlo PANC memory
PAMC time
Strking ooach
1.0
0.5
0.0
12
244
944
2056
3706
5773
8299
11209
14699
16585
usps
hhar reut
ecm
dblp
cite Lops
Nhat
reul
8tm
dblp
cile
150
Number of edges (top) and nodes (below) x1000
Figure 3: GPU performance from the pytorch profiler on Google Colab with T4 16Gb GPU. tefinig time for 200 epochs. center:memory utilization per epoch. right:graph size vs time and memory on synthetic CITE data per epoch; W/o model runs out of memory after 17,000 nodes. With PamC 150,000 nodes and over 18 million edges can be handled on the T4's 16GB. Note that SCGC* only differs from PamCGC by its use of the novel proxy-ed PamC to which we solely attribute the time and memory savings.
GPU training times
Accuracy
AGCN contrastive
AGCX contrustive (ours)
0.
SDCN contrastive
SDCN contrastive lours)
0.6
D8LF
USPS
DBLP
CITE
HBAR
Figure 4: Left:GUU training times with PamCGC on SDCN and AGCN is consistently lower, and significant in large datasets jusps,hhar,,euus Right:Accuracy loss of the approximation very low. For dblp, usps, reut accuracy is actually better.
are significantly shorter, with (often better) training accuracy due to block contrastiveness. Note that PamC only improves loss computation efficiency. Majority of the SDCN and AGCN computation time is spent in their GNNs convolution operations.
We also carry out extensive experimentation to assess the behavior of hyperparameters. Pam is
robust to changes in hyperparameter values and performs best with a learning rate of 0.001, as shown in Appendix A..2] Further, [PamC] accuracy against all hyperparameter combinations is generally equal or better than the less efficient non proxy-ed contrastive loss variant, as seen in Appendix A.3
3.5 FUTURE WORK
Our parameter-free proxy-ed contrastive loss uses the full positive edge information which, as some of our experiments has shown, is redundant. For example. USPS gives similar results with 40% positive edges removed. An algorithm to drop un-informative edges may result in further efficiency improvements, which we leave for future work. While theoretically possible, it would be interesting to see how our proxy-ed contrastive loss works with semi or fully supervised data. Further study is needed to explore how hard cluster centers effect the optimization process.
CONCLUSION
In this work, present efficient warameter-frre proxy approximation incorporate negative samples in contrastive loss for joint clustering and representation learning. We eliminate sample bias, achieve block contrastiveness and O(N). Our work is supported by theoretical proof and em- pirical results. We improve considerably over previous methods accuracy, speed and memory usage. Our approach differs from prior self-supervised clustering by the proxy mechanism we use incor- porate all negative samples efficiently. The strength of this simple approach indicates that, despite the increased interest in graphs, effective contrastive learning remains relatively unexplored.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Naomi S Altman. An introduction to kernel and nearest-neighbor nonparametrie regression. The American Statistician, 46(3):175-115, 1992.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A thcoretical analysis of contrastive unsupervised representation learning. In 36th International Conference on Machine Learning, ICML 2019, pp. 9904-9923, International Machine Learning Society (IMLS), 2019.
Deyu Bo. Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. In Proceedings of The Web Conference 2020, pp. 1400-1410, 2020.
Mathilde Caron, 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:9912-9924 2020.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020a.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference machine learning. pp. 1597-1607. PMLR, 2020b.
Ching-Yas Yao Chuang, Joshua Robinson, Yen-Chen Lin, Antonio Torralba, and Stefanie Jegelka. De- biased contrastive learning. Advances in neural information processing systems, 33:8765-8775. 2020.
Gene H Golub and Christian Reinsch. Singular value decomposition and least squares solutions. In Linear algebra, pp. 134-151, Springer, 1971.
Xifeng Guo, Long Gao, Xinwang Liu, and Jianping Yin. Improved deep embedded clustering with local structure preservation. In IJCAI, pp. 1753-1759, 2017.
William I. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
John A Hartigan and Manchek A Wong. Algorithm as 136: k-means clustering algorithm. Journal of the Royal Statistical Society. Series C (Applied Statistics), 2801):100-108, 1979.
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 on computer vision and pattern recognition, pp. 9729-9738. 2020.
Geoffrey E Hinton and Ruslan Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313(5786):504 507, 2006.
Yang Hu, Haoxuan You, Zhecan Wang, Zhicheng Wang, Erjin Zhou, and Yue Gao. Graph-mlp: node classification without message passing in graph. arXiv preprint arXiv:2106.0405) 1eee220060000000 04051, 2021.
Thomas N Kipf and Max Welling.
Variational
graph auto-encoders.
arXiv preprint
arXiv:1611.07300 2016.
Gayan K Kulatilleke, Marius Portmann, Ryan Ko, and Shekhar S Chandra. Edgatii: Fast dynamic graph attention with initial residual and identity mapping. arXiv preprint arXiv:2110.11664 2021.
Gayan K Kulatilleke, Marius Portmann, and Shekhar Chandra. Sege: Self-supervised contrastive
graph clustering. arXiv preprint arXiv:2204. /2656, 2022.
Yann Le Cun, Ofer Matan, Bernhard Boser. John S Denker, Don Henderson, Richard E Howard, Wayne Hubbard, LD Jacket, and Henry S Baird. Handwritten zip code recognition with multilayer networks. In ICPR, volume 2, pp. 35-40. IEEE, 1990.
10

---

Under review as a conference paper at ICLR 2023
David D Lewis, Yiming Yang. Tony G Rose, and Fan Li. Rev1: A new benchmark collection for text categorization research. Journal of machine learning research, 5(Apr):361-39) 2004.
Junnan Li, Pan Zhou, Caiming Xiong, and Steven Hoi. Prototypical contrastive learning of unsuper-
vised representations. In International Conference on Learning Representations, 2020.
Lajanugen Logeswaran and Honglak Lee. An efficient framework for learning sentence representa- tions. In International Conference on Learning Representations, 2018.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9Novv: 2008.
Leland McInnes, John Healy, and James Melville. Umap:
Uniform manifold approximation and projection for dimension reduction. arXiv preprini arXiv: /802.0330, 2018.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. arXiv preprint arXiv:1802.04407, 2018.
Namyong Park, Ryan Rossi, Eunyee Koh, Iftikhar Ahamath Burhanuddin, Sungchul Kim, Fan Du,
Nesreen Ahmed, and Christos Faloutsos. Cge: Contrastive graph clustering forcommunity detec- tion and tracking. In Proceedings of the ACM Web Conference 2022, pp. 1115-1126, 2022.
Zhihao Peng, Hui Liu, Yuheng Jia, and Junhui Hou. Attention-driven graph clustering network. In Proceedings of the 29th ACM International Conference on Multimedia, pp. 935-943, 2021.
Allan Stisen, Henrik Blunck, Sourav Bhattacharya, Thor Süger Prentow, Mikkel Baun Kjærgaard, Anind Dey, Tobias Sonne, and Mads Møller Jensen. Smart devices are different: Assessing and mitigatingmobile sensing heterogeneities for activity recognition. In SenSys, pp. 127-140, 2015.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Veličković, and Michal Valko. Bootstrapped representation learning on graphs. In ICLR 2021 Workshop on Geometrical and Topological Representation Learning, 2021.
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang. Attributed graph clustering: deep attentional embedding approach. arXiv preprint arXiv: (et.i.90030.55 06532, 2019.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In International Conference Machine Learning, pp-
PMLR, 2020.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In ICML, pp. 478-487, 2016.
Chunyang Zhang, Hongyu Yao, CL. Chen, and Yuena Lin. Graph representation learning via con- trasting cluster assignments. arXiv preprint arXiv:21 2021a.
Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu. From canonical correlation analysis to self-supervised graph neural networks. Advances in Neural Information Processing Systems, 34:76-89, 2021b.
Yizhen Zheng, Yu Zheng, Xiaofei Zhou, Chen Gong, Vincent Lee, and Shirui Pan. Unifying graph contrastive learning with flexible contextual scopes. arXiv preprint arXiv:2210.08792, 2022.
Hao Zhu, Ke Sun, and Peter Koniusz. Contrastive laplacian eigenmaps. Advances in Neural Infor-
mation Processing Systems, 34, 2021a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006.041 2020.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, pp. 2069-2080 2021b.
11

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1 PROOFS OF THEERRTTIAAL RESULTS DERIVATION OF EQUATION
7
Assume node embeddings Z = f21, 22, 23 ... 2N clusters μr {11, M/1, -c). a label assignment operator l2,)l(;;) such that Haa Σi [(ettabl(==) Zzs hyperparameter related to the temperature in contrastive loss and
0,
i=
similarity(4.,,22.. 23) = sim(zi, 25)
(13)
+
||
We use sim( 2j) as the shorthand notation for similarity (4. 21, 23) interchangeably for brevity.
We begin with Equation[] which is the popular form of contrastive loss (Hu al. 2021; Kulatilleke et al. 2022). With r as the temperature parameter, Yi the relationship between nodes 2.J, the loss for the 7 can be expanded as:
B
f log
Σ 1 Line exp (sim (zi, z)) log Σ ==1
1 Mi My exp (sim (z,, 2z) r) (14)
where, the first part on the right corresponds to the negative node contrasting portion and the second portion contrasts the positives for node i. From Equation [4, for all nodes N, we take negative node contrasting portion, by averaging over N nodes to obtain:
N
N Σ
1 N
lOSSNN
=
Σ
log
(15)
Note our use of the more concise sim() and the compact notation over exp() interchangeably for compactness reasons.
We expand Equation
15 together with e = cases where == j. as:
1 l0S8NN
log
+ ee sim((z + sim(21,25)= + aim(s1 cim(s).2N)T +
N
log
sim(22)21)
+ e sim(222,2)) + sim((z)22)
+
log
sim(23:21) + sim( + 1
+ sim( sim(zz.2x)
log (imlex)e))) + cim( + eimlexiess cimllxxess
11)
(16)
Similarly, we can express the cluster based contrastive loss as:
M
losscc = C
Σ log
Σ
sim Ha
(17)
a=1
12

---

Under review as a conference paper at ICLR 2023
with the following expansion:
1
lossce
c log
+ esimlursa)) + us)) + eimm(rs)))) + (xim((rs))))
+
log
(imml +
+ eim((aa simlpaadu) sim (mi((a)))))) +
log (eimllaaan + simppssna) +
simlusssaa (aim(HB.He)))) +
+ ciimlucspe) + 1)
log @immlucaan + pll) + eeimlpesus)
(18)
If, No los, have ing this inequality.
LOSSNN tasscC
1. Next we show the conditions necessary for establish-
As < sim I 1.0, we obtain the min using simmin =
loss
log (1 + + + .... + E0) + ..... + log (1 + e + e + +... + eo)
= log [1 + (N- 1)E logg(N)
-
(19)
Similarly, obtain the max, using simmaz 1.0:
1 loss C log (1 + cti7 + tet + ediT) ... log (1 +
clit t
+ t + .... .... etir)
= log [1 + (C - 1)c"
(20)
Combining Equation 19 and Equation 20 we establish the necessary condition for our incquality, Equation as;
losSNN
log(N) log [1 (C 1)e²
losscc
This derivation is used in Section where we show how the condition almost always satisfied in real graphs. As result, losSNN upper bounds losscc. Note that lower loss is better.
13

---

Under review as a conference paper at ICLR 2023
A.2 HYPERPARAMETERS VS ACCURACY
6.N
20
20
250 230 23.5
03 24
Figure 5: Ablation study on the hyperparameters. TAU=7, ALPHA=a, ORDER= and LR denotes learning rate. A hyperparameter with higher and more condensed distribution represents its superi- ority over its counterpart, PamCGC robust т, a, and best with learning rate Of 0.001. Best viewed in color.
A.3 HYPERPARAMETER BEHAVIOUR WITH AND WITHOUT PAMC
Figure 6: Comparison of hyperparameters with and Aathout|PamC TAU=T, ALPHA=a, ORDER=R and LR denotes learning rate. A hyperparameter with higher and more condensed distribution rep- resents its superiority over its counterpart. PamC is generally better in accuracy for majority of the hyperparameter combinations. Best viewed in color.
14

---

Under review as a conference paper at ICLR 2023
A.4 QUALITATIVE RESULTS
8cm
Figure 7: Visual comparison of embeddings; top: raw data, second row: after AE pre-training, third-row: from SCGC* and last-row: from PamCGC Colors represent ground truth groups. Black squares, jr, are the approximated meta-nodes. Red dots, are the cluster centroids.
2018). in Figure 7 get visual understanding of the and learnt embedding spaces. Except for USPS, which is distinct set of 0 0...9 handwritten digits (raw 1), we see that all other datasets produce quite indistinguishable clusters. Clustering is nearly non-existent in the (last 3) graph datasets. This clearly shows a characteristic difference in graph data, which can lead to high samplings bias. Note that j + l for any meta-node.
We UMAP Mclnnes
A.5 DATASET SIZE VS GPU MEMORY AND TIME, WITH AND WITHOUT PAMC
traing time
GPU memory
70
2,500
PAMC
2.000
* PAMC
(9)
40
GPU memory
1.500
1.000
20
0.500
0
0.000
8000
10000
6000
10000
12000
Number nodes items)
Number nodes (or items)
Figure 8: Graph size vs GPU memory and training time with and without PamC generally better and is more effective with larger graph sizes. Best viewed in color.
Using PamC is
15

---

Under review as a conference paper at ICLR 2023
A.6 IMPROVED GPU MEMORY AND TRAINING TIME SYNTHETIC CITE DATASET
GPU memeory number of nodes (CITE)
max 16GB GPU memory (Google Colab T4;
PAMC Memory
P PAMC -memrr
memory per epcoh
PAMC
0.7
per Sunnn epoch
10
PAMC time
0.6
0.5
0.4
0.3
0.2
0.1
43
159
244
348
469
609
767
944
1138
1351
1582
1831
2098
2384
2688
3010
3350
3708
7
10
13
17
20
23
27
30
33
37
40
43
47
50
53
57
60
63
67
Number of edges (top) and nodes (below) x1000
Figure 9: Graph size GPU memory and training time with and w/o PamC for synthetic CITE dataset scaled from 1 to 20. Scaled edge and node sizes are indicated in the x-axis. [PamC] achieves linear time and memory and is more effective with larger graph sizes. W/o/PamC model runs out of memory on Google Colab T4 (16GB GPU memory). Best viewed in color.
A.7 RESULTS FROM SELECTED WORKS ON THE CITE DATASET
Table 4: Results for CITE dataset shows PamC| is competitiveness in terms of accuracy. #Results reproduced from Zheng et al. (2022)
Model
Accuracy CITE dataset
GRACE Zhu al. 2020)
71.7 0.6 t
GCA Zhu et al. 2021b)
71.2 + 0.2
BGRL Thakoor ct al. (2021
71.6 0.4
CCA-SSG Zhang al. (b021b)
73.1 + 0.3
PamC (urr)
73.3 + 0.2
A.8 GPU WORKLOAD BREAKDOWN WITH AND WITHOUT PAMC
Table 5: The GPU time breakdown for USPS dataset for 200 epochs on Colab T4 (16GB). The model forward figures (1.272 and 2.257) are different because the GPU caching the results the case of no PamC During inference, these figures are identical.
Description of task
w/o PamC
With PamC
Forward pass
24.378s
6.670s
Model forward (computation of z)
1.272s
2.257s
KL superviup loss)
7.200ms
13.448ms
Pseudo label and negative computation
18,947s
28.970ms 0.02897s
Contrastive loss (once the pairs computed)
2.548s
1.914s
16


Reviews:
[{"review_id": "q6US_t72iMC", "reviewer": "Reviewer_X8V7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. ", "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.", "strength_and_weaknesses": "**Strengths** \n* The proposed approach seems to be widely empirically effective and is accurate. The approach is very computationally efficient compared to baseline approaches. \n* The proposed approach uses an interesting clustering-based objective that seems well motivated. \n\n**Weaknesses**\n* 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. \n* Could the authors clarify the statement\n>We provide theoretical proof and show that real world graphs always satisfies the necessary\nconditions, and that PamCGC is block-contrastive, known to outperform pair-wise losses\n* 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.\n\n[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.\n\n[2] Zhang, Chunyang, Hongyu Yao, C. L. Chen, and Yuena Lin. \"Graph Representation Learning via Contrasting Cluster Assignments.\" arXiv preprint arXiv:2112.07934 (2021).\n\n[3] Li, Junnan, Pan Zhou, Caiming Xiong, and Steven CH Hoi. \"Prototypical contrastive learning of unsupervised representations.\" arXiv preprint arXiv:2005.04966 (2020).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jSMkjl53YD", "reviewer": "Reviewer_cHFr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.", "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.\n", "strength_and_weaknesses": "Strength\n- It makes sense to replacing the contrastive between negative samples with that between class clusters to reduce the complexity.\n- The experimental evaluations are sufficient.\n- The writing and organization are good.\n\nWeakness\n- 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.\n\n[1] Junnan Li, Pan Zhou, Caiming Xiong, Steven C. H. Hoi: Prototypical Contrastive Learning of Unsupervised Representations. ICLR 2021\n2020\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "QkU74_S-i-w", "reviewer": "Reviewer_6uyq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.", "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.", "strength_and_weaknesses": "## Strength\n1. The direction of more efficient negative sample mining is important for contrastive learning.\n2. The idea of utilizing the clustering centers as negative samples saves the sampling cost.\n3. Extensive experiments demonstrate comparable performance with baseline methods while achieving good speedup ratio for training time.\n\n## Weaknesses\n1. 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? \n2. It is not clear how the proposed method can save inference time\n3. How long does it take to evaluate the soft label? Is it included in the training time?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8VksCy66JZ", "reviewer": "Reviewer_GN9c", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n", "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.\n", "strength_and_weaknesses": "Strenghts:\n1. 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.\n2. The proposed method does show better efficacy than traditional contrastive methods.\n\nWeaknesses:\n  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.\n \n2. 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)\n3. 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.\n4.  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.\n5. Although the most imporant claimed advantage is scalability, the datasets used for evaluation are really small. The authors should consider use larger graphs.\n\nReferences:\n[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.\n[2] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW, 2021.\n[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.\n[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.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject