Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination
Authors: YIZHEN ZHENG
Shirui Pan
Vincent Lee
Yu Zheng
Philip S. Yu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Contrastive Learning
Self-supervised Graph Representation Learning
Unsupervised Graph Representation Learning
Graph Representation Learning

Abstract: Graph contrastive learning (GCL) alleviates the heavy reliance on label information for graph representation learning (GRL) via self-supervised learning schemes. The core idea is to learn by maximising mutual information for similar instances, which requires similarity computation between two node instances. However, GCL is inefficient in both time and memory consumption. In addition, GCL normally requires a large number of training epochs to be well-trained on large-scale datasets. Inspired by an observation of a technical defect (i.e., inappropriate usage of Sigmoid function) commonly used in two representative GCL works, DGI and MVGRL, we revisit GCL and introduce a new learning paradigm for self-supervised graph representation learning, namely, Group Discrimination (GD), and propose a novel GD-based method called Graph Group Discrimination (GGD). Instead of similarity computation, GGD  directly discriminates two groups of node samples with a very simple binary cross-entropy loss. In addition, GGD requires much fewer training epochs to obtain competitive performance compared with GCL methods on large-scale datasets. These two advantages endow GGD with very efficient property. Extensive experiments show that GGD  outperforms state-of-the-art self-supervised methods on eight datasets. In particular, GGD can be trained in 0.18 seconds (6.44 seconds including data preprocessing) on ogbn-arxiv, which is orders of magnitude (10,000+) faster than GCL baselines while consuming much less memory. Trained with 9 hours on ogbn-papers100M with billion edges, GGD outperforms its GCL counterparts in both accuracy and efficiency. 

Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Diserimination
Yizhen Zheng', Shirui Pan"; Vincent CS Lee', Yu Zheng', Phillip S. Yu², Monash University, "Griffith University, *La Trobe University, University of Illimons at Chicago yizhen. zheng1 @oogashmonash..mmmmm edu, s. pan@griffth edu. au, vincent. cs. lee@monash. edu yu. ww..he@@latrrbee www.roobeedu.arr.. ad, psyuβuic.
Abstract
Graph contrastive learning (GCL) alleviates the heavy reliance on label information for graph representation learning (GRL) via self-supervised learning schemes. The core idea learn by maximising mutual information for similar instances, which requires similarity computation between two node instances. However, GCL is inefficient in both time and memory consumption. In addition, GCL normally requires a large number of training epochs to be well-trained on large- scale datasets. Inspired by an observation
technical defect (i.e., inappropriate usage of Sigmoid function) commonly used in two representative GCL works, DGI and MVGRL,, we revisit GCL and introduce a new learning paradigm for self-supervised graph representation learning, namely, Group Discrimination (GD), and propose a novel GD-based method called Graph Group Discrimination (GGD). Instead of similarity computation, GGD directly discriminates two groups of node samples with a very simple binary cross-entropy loss. addition, GGD requires much fewer training epochs obtain competitive performance compared with GCL methods on large-scale datasets. These two advantages endow GGD with very efficient property. Extensive experiments show that GGD outperforms state-of-the- art self-supervised methods on eight datasets. In particular, GCD can be trained in 0.18 seconds (6.44 seconds including data preprocessing) is orders of magnitude (10,000+) faster than GCL baselines while consuming much less memory. Trained with hours on ogbn-papers papers100M 100M with billion edges, GGD outperforms its GCL counterparts in both accuracy and efficiency.
ogbn-arxiv, which
Introduction
Graph Neural Networks (GNNs) have been widely-adopted in learning representations for graph- structured data, By utilising message-passing over the topology of a graph, GNNs can learn effective low-dimensional node embeddings, which can be used for a variety of downstream tasks such as node classification ①. GNNs have been further applied in diverse domains, e.g., federated learning 2 3)
trustworthy systems [] dynamic graphs 6 7 and anomaly detection [ [.
However, many GNNs adopt supervised learning manner train models with label information, which is expensive and Labour-intensive to collect in real-world. To address this issue, a few studies (e.g., DGI [10], MVGRL [I]] GMI [12], and GRACE [33] borrow the idea of contrastive learning from computer vision (CV), and introduce graph contrastive learning (GCL.) methods for self- supervised GRL. The core idea of these methods maximise the mutual information (MI) between an anchor node and its positive counterparts, sharing similar semantic information while doing the
*Corresponding Author,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

opposite for negative counterparts shown in Figure Ia). Nonetheless, such a scheme relies on similarity calculation in contrastive loss computation. Additionally, GCL normally requires large number of training epochs to be well-trained on large-scale datasets. Thus, when the size of the dataset is large, these methods require a significant amount of time and resources to be well-trained.
Though few GCL works attempt to improve graph contrastive learning with specially designed schemes, e.g., BGRL [1]] and GBT [14], they are still inefficient and require high time con- sumption for model training, Inspired by BYOL. [6], BGRL [I5] adopts a bootstrapping scheme and remove neg- ative node pairs. It only contrasts a node from the online network (i.e., up- dated with gradient) to its correspond- ing embedding from the target network (i.e.. updated momentumly with stop gradient). Based on Barlow-Twins [17], GBT [4] borrows the idea of -redudcttyrrdtttion principle and utilises a cross-correlation-bae loss to build contrastiveness between embedding dimensions.
Maximise
Positive
Posilive
Group
Nogative Group
Anchor
Discriminate
Negativo
Re
Miniimise
(a)Graph Contrastive Learning
(b) Group Discrimination
The left subfigure shows the GCL learning scheme. Red line indicates MI maximisation between two nodes, each of which E RIIDD while blue line indicates the opposite operation. The right subfigure presents Group Discrimination. It discriminates positive and negative node samples, each of which E RR 1x11
Figure 1:
To boost training efficiency of self-supervised GRL, inspired by an observation of a technical defect (i.e., inappropriate application of Sigmoid function) in two representative GCL studies, we introduce a novel learning paradigm, namely, Group Discrimination (GD). Instead of similar- ity computation, GD directly discriminates a group of positive nodes from group of neg- ative nodes, as shown in Figure [bb.. Specifi- cally, GD defines node samples generated with original graph as the positive group, while node samples obtained with corrupted topology are regarded as the negative group. Then, GD trains the model by classifying these node samples into the correct group with a very simple bi- nary cross-entropy loss. By doing so, the model can extract valuable self-supervised signals from learning the edge distribution of graph. Com-
Table I: Training time in seconds comparison be- tween CGD and GBT [14] (i.e.. the most efficient GCL baseline as shown in section [5.1] ogbn- arxiv. Number in brackets means the hidden size. 'Pre', "Tr' and 'Epo' indicate preprocessing time, training time per epoch, and the number of epochs for training GNNs. "Total(E)' and "Total(T)' total end-to-end training time (i.e., including pre- processing), which equals to (Pre Epo x Tr) and total training time, which is (Epo x Tr). 'Imp(E)' and 'Imp(T)' indicate how many times GGD im- prove on 'TotalEE) and (Total(T).. 'Acc' is aver- aged accuracy result on test set over five runs.
Method
Tr
Epo
Totak()) EmpcF)
Total(T) Imp(T)
Ace
GRT(256)
5.52 6.47
300
1.946.52
1,94.000
70.1
200(256)
6.26
0.18
1
6.44
302.25 x
0.18
70.3
(GD()_500)
6.26 0.95
1
7.11
269.96
0.95
2,043.16x
71.6
pared with GCL, GD enjoys numerous merits including extremely fast training, fast convergence (e.g., epoch to be well-trained on large-scale datasets), and high scalability while achieving SOTA performance with existing GCL. approaches.
Using GD as backbone, we design a new self-supervised GRL model with the Siamese structure called Graph Group Discrimination (GGD). Firstly, we can optionally augment a given graph with augmentation techniques, e.g., feature and edge dropout. Then, the augmented graph is fed into GNN encoder and a projector to obtain embeddings for the positive group. After that, the augmented feature corrupted with node shuffling (i.c., disarranging the order of nodes in the feature matrix) to disrupt the topology of graph and input to the same network for obtaining embeddings of the opposing group. Finally, the model is trained by discriminating these two groups of node samples. The contributions of this paper are three-fold: 1) We re- re-examine existing GCL approaches (e.g., DGI [10 and MVGRL M.), and we introduce novel and efficient self-supe GRL paradigm, namely, Group Discrimination (GD). 2) Based on GD, we propose a new self superviie GRL model, GGD, which is fast training and convergence, and possess high scalability. 3) We conduct extensive experiments on eight datasets, including an extremely large dataset, ogbn-papers 1a0persppp00MM 100M with billion edges. The experiment results show that our proposed method reaches state-of-the-ar performance while consuming much less time and memory than baselines, e.g., 10783 x faster than the most efficient GCL baseline with its best selected epochs number [14], as shown in Table T
2

---

2 Rethinking Representative GCL Methods
In this section, we analyse a technical defect observed in two representative GCL methods, DGI [T] and MVGRL [T Based on the tech- nical defect, we show that mutual information maximisation behind these two approaches is not the contributed factor to contrastive learn- ing, but a new paradigm, group discrimination. Finally, from the analysis, provide the defi- nition of this new concept.
maximise
Cooruee
Pooling
minimmis
Figure 2: The architecture of DGI. Cubes indicate node embeddings. Red and blue lines represent MI maximisation and minimisation, respectively. and 9 denote the original graph and the corrupted graph. s is the summary vector.
2.1 Rethinking GCL Methods
DGI 10 is the first work introducing con- trastive learning into GRL. However, due to technical defect observed in their official open- source code, we found it is essentially not work- ing as the authors thought (i.e., learning via MI interaction).
Constant Summary Vector. As shown in Figure 2 the original idea of DGI is to maximise the MI (i.e.. the red line) between node and the summary vector which is obtained by averaging all node embeddings a graph 9. Also, to regularise the model training, DGI corrupts 9 by shuffling the node order of the input feature matrix to get $. Then, generated embeddings of 9 serve as negative samples, which are pulled apart from the summary vector s via MI minimisation.
Nonetheless, the implementation of DGI, a Sigmoid function is inappropri- ately applied on the summary vector generated from GNN whose weight is initialised with Xavier initialisation. As result, elements in the summary vector are very close to the same value. We have validated this finding on three datasets, Cora, CiteSeer and PubMed. The experiment result is shown in Ta- ble which shows that summary vec-
Table 2: Summary vector statistics on three datasets with different activation functions including ReLU, LeakyReLU (i.e., LReLU shown below), PReLU, and Sigmoid.
Activation
Statistics
Cora
CiteSeer
PuhMed
0.50
ReL.VLR-UUPRALUU
1.3e-03
1.0e044
Range
1.46-03
8.0e-04
Mean
0.62
0.62
0.62
Sigmoid
Std
5.4e-05
3.9e-05
6,6e 08
Range
3.60-03
3.0e-03
3.22-03
tors all datasets are approximately constant vector el, where is scalar and is all-ones vector (i.c., ==0.50 with ReLU/LReLU/PReLU and ==0.62 with Sigmoid as non-linear activation in these datasets).
To theoretically explain this phenomenon, we present the proposition below:
Table 3:
The experiment result on three datasets with changing value from 0 to 1.0 for the summary vector.
Proposition 1 Given - (X A E RRNNN J. and GCN encoder g(-) initialised with Xavier ini- tialisation, we can obtain its embedding H agg())) where a--) a non-linear activation function. By ap- plying the sigmoid function (.) to the summary vector (i.e., the average row vector of H), values digg(s approximately become 0.5 with ReI.UR/.R or 0.62 with Sigmoid as non-linear activation of g(-) at the initialisation stage.
Dataset
Cora
70.3
82,4+0.2
87.5
3+0.3 2.55:0.1
CineSeer
618400.8
71.7+06 71 710-007 716++0 71.7+10 7166008
Pubbded
68. 77.8.0.5 77..0.88 17.7.00.8 77ALL 77.20.9
Based on this proposition, we can see these summary vectors can lose variance and become constant vector the initialisation stage. Based on Table 2 we can see the constant in the summary vector remain unchanged, and the information loss still occurs even the GNN encoder trained. Thus, we conjecture the training process won't ' affect the constant value much in the summary vector of DGL. The proof for the proposition is presented in Appendix A.
To evaluate the effect of to constant summary vector, we vary the scalar (from 0 to increment by 0.2) to change the constant summary vector and report the model performance (i.e., averaged accuracy on five runs) in Table
3

---

From this table, we can see, except for O, the model performance is trivially affected by e for constant summary vector. When the summary vector is set O, the model performance plummets because node embeddings become all O when multiplying with such vector and the model converges to the trivial solution. As the summary vector only has a trivial effect on model training, the hypothesis of DGI [T0] on learning via contrastiveness between anchor nodes and the summary instance does not hold, which raises a question to be investigated: What truly leads to the success of DGI?
Simplifying DGI. To answer the question, we predigest the objective function proposed in DGI (i.e., maximising the MI between h, and the summary vector s) by using an all-ones vector as the summary vector (i.e., setting d = D) and simplifying the discriminator D(-) (i.e., removing the learnable weight matrix). Then, we rewrite the objective function to the following form:
1
DGI
log ((h,, s) + log(1 - D(h,, s))),
2N
1
log(h; s) log(1 hn s))),
(I)
2N
log(sum(ba)) + log(1 sum(h,)))
2N
where is the vector multiplication operation, N the number of nodes in a graph, h, E RIxD and h2 E Lx1x are the original and corrupted embedding for node i, sum(-) ) the summation function, and (-)) is discriminator for bilinear transformation, which can be formulated as follows:
Db,,, asig (h:
W s),
where W is a learnable weight matrix and sig (-) is the sigmoid function. Specifically, as shown in
Table 4: Comparison of the original DGI and DGI in terms of accuracy (averaged on five runs), memory efficiency (in MB) and training time (in seconds). Number after I shows how many times have DGIBCE im- proved on top of DGI.
Equation[2] _ by removing the weight matrix W, h, is directly multiplied with s. As s is vector containing only one, the multiplication of h, and s is equivalent to summing h, itself directly. From this form, we can see that the multiplication of h, and the summary vector only serves as an aggregation function (i.e., summation aggregation) to aggregate h; To explore the effect of other aggregation functions, we replace the summation function in Equation | with other aggregation methods such as mean-, minimum- and maximum- pooling, and present the experiment result in Appendix A.3.
Experiment
Method
Cora
Citbberr
PubMed
Accuracy
DGI
81.7::0.6
71.5:0.7
27.3:006
DGlece
62.5:00.5
71.7=0.6
77.7=0.5
Memory
DGI
4189MB
8199MB
11471MB
DGllee
14
1587MR8866
1639M9855.8
DGI
0.8K3
0.134s
0.15%s
0.021114x
0015/10.5
Based on Equation [ we can rewrite to a very simple binary cross entropy loss we also include corrupted nodes data samples and setting ÿ, (h:), where agg(-) stands for aggregation:
2N
LBC
ys log d: + (1 - yi) log(1 - (s)))
2N
where yi E RIx1 means the indicator for node i (i.e., if node is corrupted, yi is O, otherwise is 1), and ii RRxx1 represents the prediction for node sample i. As we include corrupted nodes as data samples, the size of nodes to be processed is doubled to 2N (i.e., the number of corrupted nodes is equal to the number of original nodes). From the equation above, we can casily observe that what DGI truly does is discriminate between group of nodes generated with correct topology and nodes generated with corrupted topology, shown in Figure [ We name this self-supervised learning paradigm "Group Discrimination" To validate the effectiveness of this paradigm, we replace the original DGI loss with Equation namely, DGIBCE and compare it with DGI on three datasets in terms of training time, memory efficiency and model performance as shown in Table [ Here, DGI adopts the same parameter setting as DGI. From this table, we can observe DGI BCE dramatically improves DGI in both memory and time efficiency while it slightly enhances the model performance of DGI. This may be contributed to the removal of multiplication operations between node pairs, which eases the burden of computation and memory consumption.

---

Similar to DGI, the same technical defect is observed in MVGRL [ which makes it become GD-based method. Extended on DGI, MVGRL [T] incorporates diffusion augmentation to inject additional global information into model training, which enhances the model performance. The detailed analysis for MVGRL presented in Appendix A.4.
Definition Group Discrimination
As mentioned above, Group Discrimination is self-supervised GRL paradigm, which learns by dis- criminating different groups of node samples. Specifically, the paradigm assigns different indicators to different groups of node samples. For example, for binary group discrimination, one group is considered as the positive group with class its indicator, whereas the other group is the negative group, having its indicator assigned O. Given graph 9, the positive group usually includes node samples generated with the original graph 9 or its augmented views (i.c., similar graph instances of created by augmentation). In contrast, the opposing group contains negative samples obtained by corrupting 9, e.g., changing its topology structure.
Based on our theoretical analysis, group discrimination is learning to avoid making 'mistakes' (i.e., bias the encoder towards avoiding mistaken samples), thus improving the quality of generated embeddings. The analysis and an intuitive explanation are presented in Section 6.1.1 and A.2.1.
3 Methodology
We first define unsupervised node representation learning and then present the architecture of GGD, which extends DGI BCE with additional augmentation, the projector and embedding reinforcement reach better model performance. Given graph 9 with attributes E N where N the numher of nodes in G, and D is the number of dimensions of X, aim is train GNN encoder without the reliance on labelling information. With the trained encoder, taking 9 and X as input, it can output learned representations H E R D where D' is the predefined hidden dimension. H can then be used in many downstream tasks such as node classification.
Positive
Angmentation
Encoder
Projecter
Aggregation
Edge/Feat Dropout (Optional)
Corrapt
Shared Weight
Shared Weight
Shared Aggregation
Discriminate
x
Rucodei
Projector
Aggregation
Negative
Figure 3: The architecture of GGD. Given a graph with feature matrix X, we can optionally apply augmentation on them to generate 9 and X. Then, we corrupt and 9 to obtain X and G. Taking X and 9 as input to the encoder and the projector, i.e., a multilayer perceptron, positive node samples can be obtained. Similarly, X and & are fed to the same encoder and projector to generate negative samples. The generated embeddings are aggregated get predictions for the group discrimination task. This process will be iteratively conducted until reaching the predefined training epochs.
3.1 Graph Group Discrimination
Based on the proposed self-supervised GRL paradigm, group discrimination, have designed novel method, namely GGD, to learn node representations using a siamese network structure and a BCE loss. The architecture of GGD is presented in Figure 3 The framework mainly consists of four components: augmentation, corruption, a siamese GNN network, and group discrimination.
Augmentation. With a given graph & and feature matrix X, optionally, we can augment it with augmentation techniques such as edge and feature dropout to create 9 and X. In practice, we follow the
5

---

augmentation proposed in GraphCL [1]. Specifically, edge dropout removes predefined fraction of edges, while we use node dropout mask predefined proportion of feature dimension, i.e. assigning O to replace values in randomly selected dimensions. This step is optional in implementation.
Notably, the motivation of using augmentation in our framework is distinct from contrastive learning methods. In our study, augmentation is used to increase the difficulty of the self-supervised training tasks. With augmentation, 9 and X change in every training iteration, which forces the model to lessen the dependence on the fixed pattern (i.e., unchanged edge and feature distribution) in a monotonous graph. However, in contrastive learning, augmentation creates augmented views sharing similar semantic information for building contrastiveness.
Corruption. and X are then corrupted to build 9 and X for the generation of node embeddings in the negative group. We adopt the same corruption technique used in DGI [10] and MVGRL [I]] (as shown in Figure 5. The corruption technique devastates the topology structure of S by randomly changing the order of nodes in X. The corrupted X and 9 can be used for producing node representations with incorrect network connections.
The Siamese GNN. We have designed a siamese GNN network to output node representations given a graph and its attribute. The siamese GNN network is made up of two components, which are a GNN encoder and projector. The backbone GNN encoder is replaceable with a variety of choices of GNNs, e.g., GCN [9] and GAT [2]- In our work, we adopt GCN as the backbone. The projector is a multi-layer perceptron network, whose number of layers can be adjusted. When generating node embeddings of the positive group, the Siamese network takes 9 and X input. Using the same encoder and projector, the Siamese network output the negative group with 9 and X. These two groups of node embeddings are considered as a collection of data samples with a size of 2NV for discrimination. Before conducting group discrimination, in the "aggregation" phase, all data samples are aggregated with the same aggregation technique, e.g., sum-, mean-, and linear aggregation.
Group Discrimination. In the group discrimination process, we adopt a very simple binary cross entropy (BCE) loss to discriminate two groups of node samples as shown in Equation 3 In our implementation, y/4 is 0 and 1 for node embeddings in negative and positive groups. During model training, the model is optimised by categorising node embeddings in the collection of data samples into their corresponding class correctly. The loss is computed by comparing the prediction of node i, i.e., scalar, with its indicator y;- With the ease of BCE loss computation, the training process of GGD is very fast and memory efficient.
3.2 Model Inference
During training, the model is optimised via loss minimisation with Equation 3 The time complexity analysis of GGD is provided in Appendix A.5. In the inference phase, we freeze the trained GNN encoder Go and obtain node embeddings H, with the input G.
Inspired by MVGRL 11, which strengthens the output embeddings by including additional global information, we adopt conceptually similar embedding reinforcement approach. Specifically, they obtain the final embeddings by summing up embeddings from two views: the original view comprising local information and the diffused view with global information. This operation reinforces the final embeddings and leads to model performance improvement. Nonetheless, graph diffusion impairs the scalability of a model 21 and hence cannot be directly applied in our embedding generation process. To avoid the diffusion computation, we have come up with workaround in the virtue of the power of graph to extract global information. The power of graph can extend the message passing scope of Ho to n-hop neighbourhood, which encodes global information from distant neighbours. It can be formulated as follows:
Halobal A A
0
where Hgiobal is the global embedding, and A is the adjacency matrix of the graph G. is notable that this operation can be casily decomposed with the associative property of matrix multiplication and is easy to compute. To show the easiness of such computation, we conduct an experiment showing its time consumption on various datasets in Appendix A.6. Finally, the final embedding can be achieved by H = Hgiabal + Ho, which can be used for downstream tasks. In our experiment, we conduct node classification tasks. Following the common practice of GCL methods [10 13
15
12 17, these tasks
performed by using the final embeddings H to train and test simple logistic regression classifier.

---

4
Related Work
Graph Neural Networks (GNNss. are generalised deep neural networks for graph-structured data. GNNs mainly have two categories, spectral-based GNNs and spatial-based GNNs. Spectral GNNs attempt to use eigen-decomposition
obtain the spectral-based representation of graphs, whereas spatial GNNs focus on using spatial neighbours of nodes for message passing. Extending spectral-based methods to the spatial domain, GCN [19] utilises first-order Chebyshev polynomial filters to approximate spectral-based graph convolution. Taking the weight of spatial neighbours in consideration, GAT (0], improves GCN by introducing attention module in message passing. To decouple message passing from neural networks, SGC [22] simplifies GCN by removing non-linearity and weight matrices in graph convolution layers. However, these studies cannot handle datasets with limited or no labels. Graph contrastive learning has been recently exploited to address this issue.
Graph Contrastive Learning (GCL), aims to alleviate the reliance on labelling information in model training based on the concept of mutual information (MI). Specifically, GCL approaches maximise MI between instances with similar semantic information, and minimise MI between dissimilar instances. For example, DGI [10] builds contrastiveness between node embeddings and a summary vector (i.e.. a graph level embedding obtained by averaging all node embeddings) with a JSD estimator. To improve DGI, MVGRL. [11] and GMI [12 extends the idea of DGI by introducing multi-view contrastiveness with diffusion augmentation, and focusing on a local scope with the first-order neighbourhood, respectively. Adopting InfoNCE loss, GRACE 133 applies augmentation techniques to create two augmented views and inject contrastiveness between them. Though these GCL methods have successfully outperformed some supervised basclines in benchmark datasets, these methods suffer from significant limitations, including cons-coonuming training, memory inefficiency, and poor scalability. In contrast, GGD requires much less time in training and posses high scalability.
Scalable GNNs. Efficiency is a bottleneck for most existing GNNs handle large graphs. To address this challenge, there are mainly three categories of approaches: layer-wise sampling (e.g.. GraphSage (23), graph sampling methods such as Cluster-GCN 24 and GraphSAINT (5), and
linear models, e.g., SGC [22] and PPRGo (26. GraphSage 23 introduces neighbour-sampling
approach, which creates fixed-size subgraphs for each node. Underpinned by graph sampling, Muster-GGN [24] decomposes a large-scale graph into multiple subgraphs based on clustering, while
GraphSAINT [25] utilises light- graph samplers along with a normalisation technique for biases elimination in mini-batches. Linear models, SGC [22] and PPRGo (26). decouple graph convolution from embedding transformation (i.e., matrix multiplication with weight matrices), and leverage Personalised PageRank to encode multi-hop neighbourhood, respectively. However, all these methods only focus on supervised learning on graphs. For ssupperriisssssee----rrriieddddd supervised learning settings where labelled supervision signal is available, these frameworks are not applicable. The closest works to ours to handle large scale graph datasets under self-supervised settings are BGRL (15) and GBT [1]. They try improve the contrastive losses by removing negative samples. However, BGRL
15 and GBT [4] still require much more time in training compared with GCD.
Table 5: Model performance of node classifica- tion on 5 datasets. X, A and Y represent feature, adjacency matrix, and labels. Best performance for each dataset is in bold. Comp and Photo refer to Amazon Computers and Amazon Photos.
5 Experiments
We evaluate the effectiveness of model us- ing eight benchmark datasets of different sizes. These datasets include five small- and medium- scale datasets: Cora, CiteSeer, PubMed (27). Amazon Computers, and Amazon Photos as well as large-scale datasets ogbn-arxiv, ogbn-
Data
Method
Corn
CiteSeer
PuhMed Comp
Photo
X,
GCN
81.5
70.3
79.0
76.3-:055
1.0
28
A,
GAT
830=00.7 72.5+0.7
79.8+003
79.3=1.1
261.5
X, Y,
SGC
81.0==000
71.9+0.11
78.9+00.
74.4-0.1
86.4+000
A,
CG3
834420.7
73.620.8
80.2508
79.9:0.6
89.410.5
products and ogbn-papers 100M. Notably, ogbn-
X,A
DGI
81.720.6 71.5 77,3600
759
13.05
papers 100M is the largest dataset provided by Open Graph Benchmark 29] for node property prediction tasks. It has over 110 million nodes and billion edges. The statistics of these datasets are summarised in Appendix A.7. To
X, A
GMI
227-0027500+0.
80. 90.1440.2
768--0.1
85.1+0.11
X.A
MYGRL
829:20.7 72.610.7 79.42:0.3
79.0::0.6 $7.310.3
GRACE
800:00.4
7
79.52:1.1
71.8:044
81.8t1.0
X.A
GraphCL
82.5.102 72.810.3 77.5100.2
00M
79.510.1
X,A
BGRL
s0.5= 71.0::1.2 79.5=:0.6
89.2=00.9 91 21.240.8
X.A
CBT
$1.0.0.55 70.810.2 79.010.1
8.0 91.110.7
X.A
GGD
83.9 73.010.6 81.310.5 90.1 92.510.6
ensure reproducibility, the detailed experiment settings and computing infrastructure are sum- marised in Appendix A.8. The source code is already open sourced] 2
http::/ghhhhloooooorsssssooouuur cisou--Disrininnationn
7

---

5.1 Evaluating on Small- and Medium-scale Datasets
We compare GGD with ten baselines includ-
Table 6: Comparison of training time per epoch in seconds between six GCL-based methods and GGD on five datasets. Improve means how many times are GGD faster than baselines. ' means the improvement range.
ing four supervised GNNs (i.e., GCN
[19].
GAT (20), SGC [22), and CG3
(30]) and
six GCL methods (i.e., DGI [0], GMI
[12].
MVGRI. [TI, GRACE [T3], BGRI. [15] and
GBT (44 on five small- and medium scale benchmark datasets. In the experiment, we fol- low the same data splits BI for Cora, Cite- Seer and PubMed. For Amazon Computers and Photos, use random split setting, which randomly allocates 10/10/80% of data to train- ing/validation/test set, respectively. The model performance is measured using the averaged classification accuracy with five results along with standard deviations and reported in Table 5
Method
Cora
CiteSoer
PubMerl
Comp
Photo
DGI
0:085
0,059
GMI
0.394
1.297
0.637
0:323
0.171
0.663
0.468
GRACE
0.066
0.092
0.893
0.546
0.200
GraphCLL
0,073
0.085
0.123
00M
0.188
BGRL
0.085
0.081
0.147
0.337
0,273
GAT
0.073
0.072
0.103
0,492
0,173
OID
0.010
0,021
0,015
0,016
0.009
Improve
7.3-30.4x
3.4-3.7X
6,9-1523x
10.7-15.xx
19.2-708x
Accuracy. From Ta we can observe that GGD generally outperforms all baselines in all datasets. The only exception is on Cite- Seer dataset, where the sepi-supe method, CG3 slightly outperforms GGD, which still provides the 2nd best performance. In this ex- periment, we use the officially released code of GraphCL. [8], BGRL [15] and GBT [14) to re- produce the result, while the other results are sourced from previous studies [3
Table 7: Comparison of memory consumption in MBs of six GCL baselines and GCD on five datasets.
Method
Cora
CHecSeer
PubMed
Comp
Photo
8,199
GMI
4,527
5,467
5,219
5,361
3,429
GRACE
1,913
2,443
12.507
4.881
GrapCL
4,163
8,249
11,555
RARI.
1,627
1.349
2,209
5,69
3,303
GBT
1.651
1,799
2,461
50077
2.641
OZD
1.475
1,587
1,629
1,787
1,637
Improve
10.7-72.6
11.8-80.6%
27.3.85.88 86
64 5-83.55
58.0-7544
Efficiency and Memory Consumption. GGD is substantially more efficient than other self-supervised baselines in time and memory consumption as shown in Table 6 and Table 7 Remarkably, GGD is 19.2 times faster in Amazon Photos for training time per epoch, and consumes 64.5% less memory in Amazon Computers for memory consumption than the most efficient baseline (i.e., GBT [14). The dramatic boost of time and memory efficiency of GGD is contributed to the exclusion of similarity computation, which enables model training without multiplication of node embeddings.
5.2 Evaluating on Large-scale datasets
To evaluate the scalability of GGD, we choose three large-scale datasets from Open Graph Bench- mark [29), which are ogbn-arxiv, ogbn-products, and ogbn-papers 100M. ogbn-papers 100M is the most challenging large-scale graph available in Open Graph Benchmark for node property prediction with over billion edges and 110 million nodes. Extending to extremely large graphs (i.c., ogbn- products and ogbn-papers 100M), we adopt a Neighbourhood Sampling strategy, which is described in Appendix A.8.
Table 8: Node classification result and efficiency comparison on ogbn-arxiv. 'epo' means epoch. "Time' means training time per epoch (in seconds). "Total' is total training time (Number of epochs x "Time"). OOM indicates out-of-memory on Nvidia A40 (48GB). Number after means the hidden size
ogbn-arxiv & ogbn-products. ogbn-arxiv, we compare GGD against four self-supervised baselines (i.e., DGI
For
[10].
GRACE 13,, BGRL [n] GBT (4).
whereas BGRL [15] and GBT [14] are
selected to be compared for ogbn-products. In
of GGD.
addition, we include the performance of MLP.
Methed
Valid
Menory
Time Total
Node2vec (32), and supervised GCN [19
Supervisal GCN
73,0:0.2
71.7+0.3
sourced from 29 in Table and Table 9 For
53.75044 55 55.+0--
memory and training time comparison, we
Neae2vce
71.3:0.1 70.1+0.1
DXI
71.3e0.1 70.++0-2
only compare GGD with the two most efficient baselines (i.e., BGRL and GBT according to
CRACEJIR qpea)
72.6-0.2 71.5+0.1
RGRL/1OK qued CBB Ti epen)
72.5=0.11
71.640.11
OOM (Full-gmph)
710000.1
70.14002
14,999MB
6.47 1.94
Tables 6 and 7). In ogbn-arxiv, we reproduce BGRL 15 and found it fails to process
open 1500)
72.7a0055 71.660.5
14,666MB
0,05 0.912,043
qpei 256)
710060.2 70.340.3
4,515MB 69.8%
0.1000733x
ogbn-arxiv in full batch. Thus, we only compare GGD and GBT in this dataset, which can successfully train in full-graph processing mode.
8

---

Table 9: Node classification result and efficiency
From Table 8 and Table 9 we can see GGD re- markably achieves the oftte-of-the-art perfor- mance using only one epoch to train. As result, GGD is 10,783 times faster than the most efficient baseline, i.e., GBT [14) on total training time to reach the desirable performance in ogbn-arxiv. Please note that the number of epoches in our experiment is consistent with the optimal choice
comparison on beonn-prouuct...
Method
Valid
Test
Memory
Time
Total
Supervised GCN
92.80.0
75.6m002
Nodeóvee
70010.0
68.8:000
BERL (p00))po))
78.1+2.1
64.0=1.6
29,33MM
53ml6s
5.326msls
OBT (100 epons
85010.1
70.5-04
20.41988
48m18. 4,863mm20s
ac01 epo)
90.950.5
75.7=0.4|
4.99MBBN
12
of this hyperparameter specified in GBT [14). For rebn-productte we are 381 x faster than GBT [14
on total training time. Notably, our performance is significantly higher than GCL baselines using 100 epochs (i.e., 6% and 5.2% improvement
GBT [14 in validation and test set, respectively)
with only one epoch training in this dataset. In addition, we compare the convergence speed among GGD, BGRL [15] and GBT [4] on ogbn-arxiv and ogbn-products, which are shown in Figure [4] For ogbn-arxiv, BGRL [15 is running using batched processing with neighbour sampling. This figure shows the preeminence of our GGD in convergence speed GGD can be well-trained with only one epoch (i.e., reaching the peak model performance in the first epoch and staying stable with increased epochs). In contrast, the other two baselines require comparatively much more epochs to gradually improve their performance. Compared with GCL baselines, GGD achieves much faster convergence via Group Discrimination. We conjecture this is because GD-based method focuses on the general edge distribution of graphs instead of node-specific information. Inversely, GCL methods can suffer from convergence inefficiency as they may be easily distracted from too-detailed node-specific information during training.
ogbn-papers100M, We further com-
pare GCD with BGRL (15] and GBT [14] on ogbn-papers 100M, the largest OGB dataset with billion scale edges. Other self-supervised learn-
71.5
76.0
Accuracy
Aceuracy
68.5
66.0
GB7
ing algorithms such as DGI [10] and GMI [12) fail to scale to such large graph with a reasonable batch size (i.c.. 256). We only report the per- formance of each algorithm after a single epoch of training in Table TT) due to the extreme scale of the dataset and the limitation of our available re- sources. From the table, we can observe that GCD outperforms the two GCL counterparts, BGRL [5] and GBT 14] in both accuracy and efficiency. Specifically, GGD achieves 60.2 in accuracy while BGRL and GBT reach 59.3 and 58.9 in test set, respectively. With only one epoch, these two algorithms may not be well trained. However, training each epoch of these two requires over I day and if we would like to train them for 100 epochs, then we will need 100+ GPU days, which is prohibitively impractical for general practitioners. In contrast, GGD can be trained in about hours to achieve good result for this dataset, which is more appealing in practice.
DGILL
65.5
55.5
20
40
80
100
10
15
20
Epoches
Epoches
(a) oghn-arxiv
(b) oghn pproducts
Convergence speed comparison among GGD, BGRL(15) and GBT [14]. X-axis means number of epochs, while Y-axis represents the accuracy on test set.
Figure 4:
Explore Group Discrimination
In this section, explore the corruption technique in GCD and provide the theoretical analysis of group discrimination.
6.1 Exploring Corruption
Firstly, we explore the corruption technique used in DGI [10) and MVGRL [II, which is shown
Table 10: Node classification result and efficiency comparison on lognn-paers I 100M.
in Figure 5 These two studies corrupt the topol- ogy of given graph 9 by shuffling the feature matrix X. This is because by changing the node order of X, the neighbouring structure of S is completely changed, e.g., neighbours of node a become node b neighbours.
Method
Validation
Test
Memory
Time
Supervised SGC
63.3:2022
66.520.2
MLP
47.2:0.3
49.610.3
Node2vee
55.6+60.0
58.1+0.0
BGRLa epach)
59:34-0.5
62.1+0.3
14,057MB
26h28m
GBT (1 spoch)
58.9:0.4
61.5+0.5
13,18MB
24h38m
auxc epoch)
6022:0.3
63.500.]
4.105MBK8..9 9% 9h15ml2.7x

---

With the corruption technique, negative samples in the negative group are generated with incorrect edges. Thus, by discriminating the positive group (i.e., nodes generated with ground truth edges) and the negative group, we conjecture the model can distil valuable signals by learning how to identify nodes generated with correct topology and output effective node embeddings. To provide explanation to this, we present the theoretical analysis of group discrimination in the following section.
6.1.1 Theoretical Analysis of Group Discrimination
Group discrinination learning to avoid making 'mistakes' (i.e., bias the encoder to- wards avoiding mistaken samples). To ex- plain this point, we first present Theorem and then provide an intuitive explanation for group discrimination.
X
Comrup
X
Figure 5: Corruption technique in DGI and MVGRL.
Theorem Given graph 9. corrupted
graph G, and a encoding network g(-), we consider the distribution of positive embeddings g(9) as P pos and negative embeddings g(S) as Paeg- Optimising the group discrimination loss is equivalent to maximising the -aasen-hannon divergence between Pyos and Pneg
The proof for Theorem is presented in Appendix A.2. From the theorem above, maximising the group JS represents the discrimination loss is the same as maximising JS pos Pneg), where divergence. Thus, by optimising the loss L, Ppos and Pneg tend to be separated. As a result, group discrimination is intuitively learning to avoid making "mistakes' (i.e., bias the encoder towards avoiding mistaken samples) because by separating Poos and Pueg. Ppos can gradually become similar to Poptimal, the optimal distribution for node embeddings. As P Poptimal, is disjoint with P Pneg- if the generated embeddings can avoid being similar to -fi----distiittiinn samples, i.e., negative samples, it can be ideally closer P Pootimaat- Therefore, the trained model can improve the quality of generated node embeddings for node samples.
shown in Figure This is
7 Future Work
In this paper, we have intro- duced new self-supervised GRL paradigm: Group Discrim- ination, which achieves the same level of performance as GCL methods with much less resource consumption (i.e., training time and memory). Some limitations of this work are we still have not explored some questions for GD. For example, can we ex- tend the current binary Group Discrimination scheme (i.c., clas- sifying nodes generated with dif- ferent topology) to discrimina- tion among multiple groups? Are there any other corruption tech- nique to create more difficult negative group discrimination? More importantly, with extremely efficient property, GD has the potential to be deployed to various real-world applications, e.g., recommendation systems, which have limited labelling information and desire fast computation with limited resources.
Pazs
Pors
Pora
P
P
P
pas
Become
Payeeu
P
Pytiiss
PAzz
Figure 6: Poptimal is the optimal distribution for node embed- dings, Ppos the distribution of positive samples, Poeg is the distribution of negative samples, blue nodes represent negative samples, and red nodes are samples in the optimal distribution. At the beginning, Ppos is overlapped with Pneg- Then, Ppos is gradu- ally separated from Pneg and ideally become closer to P Poptimal-
10

---

Acknowledgments and Disclosure of Funding
This research was partially supported by an Australian Research Council (ARC) Future Fellowship (FT210100097).
This work is supported in part by NSF under grants III-1763325, III-1909323, III-2106758, and SaTCC-930941.
References
[1] Ming Jin, Yizhen Zheng. Yuan-Fang Li, Chen Gong, Chuan Zhou, and Shirui Pan. Multi-scale contrastive siamese networks for self-supervised graph representation learning. IJCAI, 2021.
[2] Yue Tan, Guodong Long, Jie Ma, Lu Liu, Tianyi Zhou, and Jing Jiang. Federated learning from pre-trained models: A contrastive learning approach. First Workshop on Pre-training: Perspectives, Pitfalls, and Paths Forward at ICML 2022.
[3] Yue Tan, Guodong Long, Lu Liu, Tianyi Zhou, Qinghua Lu, Jing Jiang, and Chengqi Zhang. Fedproto: Federated prototype lcarning across heterogeneous clients. In AAAI Conference on Artificial Intelligence, volume 1, page 3, 2022.
[4] He Zhang, Bang Wu, Xingliang Yuan, Shirui Pan, Hanghang Tong, and Jian Pei. Trustworthy graph neural networks: Aspects, methods and trends. arXiv preprint arXiv:2205.07422 2022.
[5] He Zhang, Bang Wu, Xiangwen Yang. Chuan Zhou, Shuo Wang. Xingliang Yuan, and Shirui Pan. Projective ranking: transferable evasion attack method on graph neural networks. CIKM, 2021.
[6] Ming Jin, Tuan-Fang Li, and Shirui Pan. Neural temporal walks: Motif aware representation learning on continuous-time dynamic graphs. In Advances in Neural Information Processing Systems, 2022.
[7] Ming Jin, Yu Zheng, Yuan-Fang Li, Siheng Chen, Bin Yang, and Shirui Pan. Multivariate time series forecasting with dynamic graph neural odes. arXiv preprint arXiv:2202.08440 2022.
[8] Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. Anomaly detection on attributed networks via contrastive ceffssupervised learning. TNNLS, 2021.
[9] Yizhen Zheng, Vincent Lee, Zonghan Wu, and Shirui Pan. Heterogencous graph attention network for small and medium-sized enterprises bankruptey prediction. In PAKDD, pages 140-151. Springer, 2021.
[10] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR, 2019.
[11] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In ICML, pages 41 16-4126. PMLR, 2020.
[12] Zhen Peng. Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong. Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In WWW, pages 259-270, 2020.
[13] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. ICML Workshop Graph Representation Learning and Beyond, 2020.
[14] Piotr Bielak, Tomasz Kajdanowiez, and Nitesh V Chawla. Graph barlow twins: A self-supervised representation learning framework for graphs arXiv preprint arXiv:2106.0244 2021.
[15] Shantanu Thakoor, Corentin Tallee, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Veličković, and Michal Valko. Bootstrapped representation learning on graphs. ICLR2021, 2021.
[16] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent: A new approach to self-supervised learning. NIPS, 2020.
[17] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. In /CML, pages 12310-12320 2021.
[18] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. NIPS, 33:5812 5823, 2020.

---

[19] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks ICLR, 2017.
[20] Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018.
[21] Yizhen Zheng, Ming Jin, Shirui Pan, Yuan-Fang Li, Hao Peng, Ming Li, and Zhao Li. Towards graph self-supervised learning with contrastive adjusted zooming. arXiv preprint arXiv:2111. 2021.
[22] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger. Simplifying graph convolutional networks. In ICML, pages 6861-6871. PMLR, 2019.
[23] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pages 1025-1035, 2017.
[24] Wei-Lin Chiang, Xuanqing Liu, Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In KDD, pages 257-266, 2019.
[25] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. ICI.R, 2019.
[26] Alcksandar Bojehevski. Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózem- berezki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. KDD, pages 2464-2473, 2020.
[27] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Radd Collective classification network data. Al magazine, 29(3):93-93, 2008.
[28] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 18/ 1.08868, 2018
[29] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. NIPS, 2020.
[30] Sheng Wan, Shirui Pan, Jian Yang, and Chen Gong. Contrastive and generative graph convolutional networks for graph-based semi-supervised learning. AAAI, 2020.
[31] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi- supersuper learning with graph embeddings. In ICML, pages 40-48, PMLR, 2016.
[32] Aditya Grover and Jure Leskovee. node2vec: Scalable feature learning for networks. In KDD, pages 855-864, 2016.
[33] Behzad Kamgar-Patt Parsi. Behrooz Kamgar-Parsi, Menashe Brosh. Distribution moments of the weighted sum uniforms random variables, with applications in reducing monte carlo simulations. Journal of Statistical Computation and Simulation, 52(4):399 1995.
[34] Jean Daunizcau. Semi-analytical approximations to statistical moments of sigmoid and softmax mappings of normal variables. arXiv preprint (003:0/770000090 2017.
[35] Ian Goodfellow, Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
12


Reviews:
[{"review_id": "ucz6YtIcps", "reviewer": "Reviewer_5yox", "summary": "This paper focuses on a way of scaling up GSL via the proposed group discrimination. The authors first analyze the actual reason that makes DGL work and then naturally use one scalar to summarize each node for discrimination in the MI max/min process compared to the usage of a d-dimensional vector in DGI. In summary, the proposed method is somewhat interesting and makes sense even though it is straightforward. However, the quality of this paper is still below the acceptance bar for NeurIPS due to its unclear contribution to the graph domain experts and the lack of theoretical analysis of the proposed method. ", "questions": "How is Theorem 1 related to the GCL specifically? It seems that it is just an oversmoothing issue in GNN, not caused by GCL. \n\nWhy does the accuracy not drop when using group discrimination? How can we ensure this from a theoretical perspective? Since we only use one scalar now compared to the DGI, there should be some information loss.\n\nHow is the proposed method specific to the graph domain? It seems that the idea of group discrimination can be easily adapted to the image domain. If so, what is the performance in terms of efficiency and accuracy? ", "limitations": "The authors are suggested to elaborate more on the motivation part and the relationship with the oversmoothing issue in GNN.\n\nThe authors are suggested to provide a theoretical guarantee of the accuracy of the proposed method. ", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n\nThe research question is significant. GSL is a hot term nowadays in the GNN domain. The demand for an efficient GSL method is increasing. This work fills this gap.\n\nThe logic of this work is quite clear. The authors first analyze why DGI works and how we can simplify it accordingly for efficiency. Then the term \"group discrimination\" is naturally introduced, and how it can be plugged into the paradigm of GSL is clearly elaborated.\n\nThe experiments are extensive and include several well-known large-scale ogbn datasets. The improvement in terms of efficiency is quite tremendous.\n\n\n\nWeaknesses\n\nThe most critical issue of this work is that the proposed method is not specific to the graph domain. In other words, the proposed method seems to work perfectly even if the input is not the graph, say images. We can also apply the same idea of group discrimination for self-supervised learning on the image classification task. If the proposed method is motivated by the image domain or the general large-scale self-supervised learning, the authors should conduct experiments on the image data as well, as the proposed method is not domain-specific to graph data.\n\nThe motivation is unclear. The analysis of the DGI method is seemingly sound, but the mentioned phenomenon has nothing to do with graph contrastive learning. In fact, it is the over-smoothing issue involving GNN itself. Theorem 1 is also well-known[1]. The authors at least add some discussion on the relationship between oversmoothing issue in GNN and the graph contrastive learning. Otherwise, the motivation does not hold. It is not a rethinking of a GCL method but rather a reiteration of the well-known fact in GNN. If the motivation originates from the issue of DGI only, how can we ensure that the proposed method also works for other GCL methods except for DGI?\n\nThe proposed method is not quite exciting, and the group discrimination cannot be overexaggerated as a new GCL paradigm but more like a trick or technique. In fact, using one scalar to summarize the whole embedding vector is not quite new. For instance, in binarized GNN[2], we also aim to learn a binarized vector to quantize the embedding for scaling up GNN, which shares a similar idea.\n\nAnother critical issue is the lack of direct theoretical analysis. Since only one scalar is used for each node in GCL, how to make sure there is no information loss? Why does it perform even better than classic GCL methods? Are there any theoretical guarantees?\n\n\n[1] Cai, Chen, and Yusu Wang. \"A note on over-smoothing for graph neural networks.\" arXiv preprint arXiv:2006.13318 (2020).\n\n[2] Wang, Hanchen, et al. \"Binarized graph neural network.\" World Wide Web 24.3 (2021): 825-848.", "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": "rwXVtyJ_xuM", "reviewer": "Reviewer_92EW", "summary": "I enjoyed reading this unusual paper. This paper proposes a new graph pretraining pre-text task -- group discrimination -- with low computational cost and fast convergence speed. The idea is simple -- pre-train a GNN to discriminate the node embeddings of original graphs and the nodes from corrupted graphs with randomly shuffled nodes. Besides group discrimination, the method also uses a diffusion operator to enhance the node embeddings. This method achieves state-of-the-art or comparable performances on node classification benchmarks. \n\nThe method is inspired by an interesting observation in the previous DGI and MVGRL works. By analysis, the authors show that the supposedly contrastive objective in previous works is actually doing group discrimination. The authors then simplify the existing methods into this group discrimination pre-text task. The new pre-text task shows lower complexity and faster convergence speed.\n", "questions": "Q1: graph diffusion models like SGC have shown promising feature extraction capability without any pre-training. GGD shares the similar spirit of using the power of adjacency matrix to obtain global embedding. How does GGD perform without the diffusion operator? How does the baseline perform if the diffusion operator is included?\n\nQ2: how does GraphCL perform in the given benchmarks?\n", "limitations": "none", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The method is surprisingly simple but effective. It is also new and original in self-supervised learning for graphs. In experiments, the method shows significant improvement than baselines in terms of complexity and performance.\n\nHowever, I find some incorrect claims of complexity and missing ablation study while reading. These weaknesses can hurt the credibility of the proposed method.\n\n\n\nWeaknesses:\n\n- The ablation study for the graph diffusion module is missing. Doe the group discrimination perform as good when the graph diffusion model is removed?\n- Missing baseline: GraphCL. In Line218, the model uses the augmentation from GraphCL. How does GraphCL perform in the presented benchmarks?\n- Some claims about the complexity are incorrect. I didn't verify all the complexity claims, but here are examples:\n  - The complexity of the loss function for one node is actually O(d) because of the sum operator for node embeddings in Line173. The authors claim the complexity if O(1) throughout the paper. Despite the O(1) complexity, the theoretical improvement is weak. The time complexity of training GNNs is dominated by the GNN forward of at least O(EDL) (E is the edge number). Compared to GNN forward, the improvement on the time complexity of loss function is negligible.\n  - The complexity of BarlowTwins loss is actually O(ND^2) for a batch of N nodes. This complexity is due to calculating the cross-correlation matrix using two matrices of shapes (D, N) and (N, D). However, the authors claim the complexity for one node is O(D) in Line50-51.\n  - The complexity of GCN is actually O(LMD + LND^2) rather than the claimed value in Line648-649. See Cluster-GCN for the analysis of GCN's complexity.\n\n- Some important experimental details are missing. \n  - It is unclear if the authors freeze the encoder while linear evaluation or do they fine-tune the entire model?\n  - Is the learning rate in Table15 used for pre-training or fine-tuning?\n\n\n\nTypos:\n\n- Line123: are served --> serve\n- Line142: Theorem and detailed --> Theorem\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": "m1gxEUoWKA6", "reviewer": "Reviewer_2iwV", "summary": "The paper presents a novel approach to graph representation learning that learns informative node embeddings by projecting the embeddings obtained from the original graph using a GCN into scalars, and the embeddings obtained from a corrupted version of the graph using the same GCN into scalars, and optimizing the parameters of the model so that the embeddings of the original graph are all distinguishable from the embeddings of the corrupted version of the graph using a logistic classifier. The proposed method, Graph Group Discrimination, is shown to use much less memory, converge much faster, be more scalable, and to usually be more accurate than prior models when applied to node classification tasks.", "questions": "- Explain how the graph representations learned by GGD and competing methods are actually used to compute the reported node classifications. E.g. are the same architectures used?\n\n- State that the Figure 5 mentioned in Section 3 is in the appendix.\n\n- The current description in Section 3 is not sufficient. Give an unambiguous loss function, and algorithm listing for minimizing this loss. Explain what the projector and aggregation steps are, and what architectures are used to parameterize/accomplish them, in the same way that it is explained a GCN is used for the encoder.\n\n- It is mentioned that global information can be included in the GGD method in Section 3.2, but it is not clear whether this is used in any of the experiments from the main body of the paper. This should be clarified (i.e. no, none used global infromation), and the reader pointed to the Appendix for experiments using global information.\n\n- I had questions about the data sets and specific architectures and hyperparameters used in the experiments. The former (data sets) were addressed in the Appendix; this should be pointed out in the paper. However, the experiments are not well specified because I do not see what the architectures or hyperparameters were used; please give this information in the Appendix as well. Also, what code did the authors use for the two baselines BGRL and GBT: did they reimplement them, or use existing code? This should be mentioned in section 5.1.\n\nOverall, I thought the paper's contribution is significant, but the presentation needs work to address the above issues before I can give it a solid accept.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- The approach is novel, fast, and more scalable than previous graph contrastive learning methods.\n- The method leads to embeddings that are accurate for node classification.\n- The overview of GCL methods is informative and positions the contribution clearly.\n\nWeaknesses:\n- It is not stated how the learned graph representations are used to compute the node classifications show in the results.\n- No explicit algorithm is stated, so some steps are ambiguous (e.g., it's never made clear how a \"projection\" and \"aggregation\" are in Figure 3; it's also not clear from that figure that the augmentation and corruption change between training iterations)\n- I don't see why the claim in Theorem 1 about the GCN encoder leading to constant summaries is relevant: this result assumes that the encoder is not being trained, but it is, so the result does not accurately reflect what is going on in DGI. The empirical results of the author in \nTable 2 aren't explained by Theorem 1.\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": "D06dJMnT7aB", "reviewer": "Reviewer_o3aj", "summary": "DGI has shown successful performance as the graph contrastive learning method.\nThis paper points out the technical defect of DGI, that is, the sigmoid function in the loss makes the embedding uniform.\nFrom that observation, the authors suggest to modify the original loss to much more simplified version (i.e., graph discrimination).\nThey propose GGD based on the graph discrimination loss, and show the experimental results to prove its efficiency.", "questions": "- What is the rationale for saying that \"GD-based method focuses on the general edge distribution of graphs instead of node-specific information\"?\n- How are the training time and memory consumption of the supervised GNN models in the small- and medium-scale datasets?\n- Please clarify which results are reproduced and which are sourced from other papers in other sections as in Section 5.1, and indicate how many epochs the models are trained in every case.\n- I was curious about the behavior in convergence of the models until 300 and 100 epochs in Figure 4.", "limitations": "- As the authors mentioned, the group discrimination can depend on augmentation or corruption methods.\n- It would be more persuasive if the experiments are conducted on the datasets from more various domains.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- They improve both the performance and the resource efficiency.\n- It is a well-organized paper: easy to catch the idea, and contains detailed but concise explanation.\n\n**Weaknesses**\n- It would be better if there are more empirical explanations how GGD achieves the higher performance than DGI, for example, by the ablation study.\n- There are minor mistakes: overlapping letters in Table 9, unit error in line 387 (% $\\rightarrow$ %p).", "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