Large-Scale Representation Learning on Graphs via Bootstrapping
Authors: Shantanu Thakoor
Corentin Tallec
Mohammad Gheshlaghi Azar
Mehdi Azabou
Eva L Dyer
Remi Munos
Petar Veličković
Michal Valko
Venue: ICLR 2022 Poster (2022)

Abstract: Self-supervised learning provides a promising path towards eliminating the need for costly label information in representation learning on graphs.  However, to achieve state-of-the-art performance, methods often need large numbers of negative examples and rely on complex augmentations.  This can be prohibitively expensive, especially for large graphs. To address these challenges, we introduce Bootstrapped Graph Latents (BGRL) - a graph representation learning method that learns by predicting alternative augmentations of the input. BGRL uses only simple augmentations and alleviates the need for contrasting with negative examples, and thus is scalable by design. BGRL outperforms or matches prior methods on several established benchmarks, while achieving a 2-10x reduction in memory costs. Furthermore, we show that BGRL can be scaled up to extremely large graphs with hundreds of millions of nodes in the semi-supervised regime, achieving state-of-the-art performance and improving over supervised baselines where representations are shaped only through label information.  In particular, our solution centered on BGRL constituted one of the winning entries to the Open Graph Benchmark -Large Scale Challenge at KDD Cup 2021, on a graph orders of magnitudes larger than all previously available benchmarks, thus demonstrating the scalability and effectiveness of our approach.

Published as a conference paper at ICLR 2022
LARGE-SCALE REPRESENTATION LEARNING ON
GRAPHS VIA BOOTSTRAPPING
Shantanu Thakoor"
Corentin Tallec DeepMind
Mohammad Gheshlaghi Azar DeepMind
DeepMind
Mehdi Azabou Georgia Institute of Technology
Eva Dyer
Rémi Munos DeepMind
Georgia Institute of Technology
Petar Veličković DeepMind
Michal Valko
DeepMind
ABSTRACT
supervupe learning provides promising path towards eliminating the need for costly label information in representation learning on graphs. However, to achieve ttateoofthh-ane performance, methods often need large numbers of neg- ative examples and rely on complex augmentations. This can be prohibitively expensive, especially for large graphs. To address these challenges, we introduce Bootstrapped Graph Latents (BCRL) graph representation learnnng method that learns by predicting alternative augmentations of the input. BGRL uses only simple augmentations and alleviates the need for contrasting with negative examples, and is thus scalable by design. BGRL outperforms eral established benchmarks. while achieving a 2-10x reduction in memory costs. Furthermore, we show that BGRL can be scaled up extremely large graphs with hundreds of millions of nodes in the semi sumi-supeviseed regime- achieving otate-of- the-art performance and improving over supervised baselines where representations are shaped only through label information. In particular, our solution centered on BGRL constituted one of the winning entries to the Open Graph Benchmark Large Scale Challenge at KDD Cup 2021, graph orders of magnitudes larger than all previously available benchmarks, thus demonstrating the scalability and effectiveness of our approach.
matches prior methods sev-
INTRODUCTION
Graphs provide powerful abstraction for complex datasets that arise a variety applications such social networks, transportation networks, and biological sciences (Hamilton al., 2017; Derrow- Pinion et al., 2021: Zitnik Leskovee, 2017; Chanussot et al., 2021). Despite recent advances in graph neural networks (GNNs), when trained with supervised data alone, these networks can easily overfit and may fail to generalize (Rong et al., 2019). Thus, finding ways to form simplified representations of graph-structured data without labels is an important yet unsolved challenge.
Current state-of -fe methods for unsupervised representation learning on graphs (Veličković et al., 2019; Peng al., 2020; Hassani & Khasahmadi, 2020; Zhu et al., 2020b;a; You al., 2020) contrastive. These methods work by pulling together representations of related objects and pushing apart representations of unrelated ones. For example, current best methods Zhu al. (2020b) and Zhu et al. (2020a) learn node representations by creating two augmented versions of a graph, pulling together the representation the same node in the two graphs, while pushing apart every other node pair. As such, they inherently rely on the ability to compare each object to large number of negatives. In the absence of principled way of choosing these negatives, this can require computation and memory quadratic in the number of nodes. In many cases, the generation of large number of negatives poses a prohibitive cost, especially for large graphs.
"Correspondence Shantanu Thakoor <thakoor google.com>.

---

Published as a conference paper at ICLR 2022
(8, Az)
(Hs.A1) A1)
(2,
[X.A]
RMA
Zu Pin Magl
(2)
(1l, As)
Figure Overview our proposed BGRL method. The original graph first used to derive two different semantically similar views using augmentations Tı,2- From these, we use encoders Ev,o to form online and target node embeddings. The predictor pe uses the online embedding H₃ to form prediction Z, the target embedding H2. The final objective then computed as the cosine similarity between Z. and H2. flowing gradients only through Z, The target parameters & updated exponentially moving average of O.
In this paper, we introduce a scalable approach for self-supervised representation learning on graphs called Bootstrapped Graph Latents (BGRL). Inspired by recent advances in self-supervised learning in vision (Grill et al., 2020). BGRL learns node representations by encoding two augmented versions of a graph using two distinct graph encoders: an online encoder, and target encoder. The online encoder is trained through predicting the representation of the target encoder, while the target encoder updated an exponential moving average of the online network. Critically, BGRL does not require contrasting negative examples, and thus can scale easily to very large graphs.
Our main contributions are:
We introduce Bootstrapped Graph Latents (BGRL), a graph self-supervised learning method that effectively scales to extremely large graphs and outperforms existing methods, while using only simple graph augmentations and not requiring negative examples (Section 2).
We show that contrastive methods face trade-off between peak performance and memory constraints, due to their reliance on negative examples (Section 4.2). Due to having time and space complexity scaling only linearly in the size of the input, BGRL avoids the performance- memory trade-off inherent to contrastive methods altogether. BGRL provides performance competitive with the best contrastive methods, while using 2- 10x less memory on standard benchmarks (Section 3).
We show that leveraging the scalability of BGRL allows making full use of the vast amounts of unlabeled data present in large graphs via semi- cuni--upervieed learning. In particular, find that efficient use of unlabeled data for representation learning prevents representations from overfitting the classification task, and achieves significantly higher, state-of-ue state-of-the-ant the-art performance. This was critical to the success of our solution at KDD Cup 202/ in which our BGRL-based solution was awarded one of the winners, on the largest publicly available graph dataset, of size 360GB consisting of 240 million nodes and 1.7 billion edges (Section 4.3).
BOOTSTRAPPED GRAPH LATENTS
2. BGRL COMPONENTS
BGRL builds representations through the of two graph encoders, an online encoder Eg and target encoder Es, where and & denote two distinct sets of parameters. We consider a graph G = (X, A), with node features X E X and adjacency matrix A E RNN BGRL first produces two alternate views of G: G = X A1) and G2 = (X2, A2), by applying stochastic graph augmentation functions and Tz respectively. The online encoder produces an online representation from the first augmented graph, H, := Es (X, A1); similarly the target encoder produces a target representation of the second augmented graph, H. = Es (X2, Az). The online representation is fed into node-level predictor pa that outputs prediction of the target representation, Z Pa H
BGRL differs from prior bootstrapping approaches such as BYOL (Grill et al., 2020) that does not projector network. Unlike vision tasks, in which projection step is used by BYOL for
2

---

Published as a conference paper at ICLR 2022
dimensionality reduction, common embedding sizes quite small for graph tasks and this is not a concern in our case. In fact, we observe that this step can be eliminated altogether without loss in performance (Appendix B).
The augmentation functions Ti and Tz used are simple, standard graph perturbations previously explored (You et al., 2020; Zhu al., 2020b). We combination of random node feature masking and edge masking with fixed masking probabilities P, and Pe respectively. More details and background graph augmentations is provided in Appendix D.
2.2 BGRL UPDATE STEP
Updating the online encoder Eg: The online parameters 0 (and not Φ), are updated to make the predicted target representations Z, closer the true target representations H2 for each node, by following the gradient of the cosine similarity w.r.t. 0, i.c.,
((0,0) = 2
Z 1.0 (2
2 (1.))
H (2nll
< optimize(0,, f) 0gl(0,0))
where y) is the learning rate and the final updates are computed from the gradients of the objective with respect to only, using an optimization method such as SGD or Adam (Kingma & Ba, 2015). In practice, we symmetrize this loss, by also predicting the target representation of the first view using the online representation of the second.
Updating the target encoder Egi The target parameters ø are updated as an exponential moving average the online parameters 0, using a decay rate T, i.c.,
Φ (1 r)0,
Figure visually summarizes BGRL's 's architecture.
Note that although the objective E(0, o) has undesirable or trivial solutions, BGRL does not actually optimize this loss. Only the online parameters 0 are updated to reduce this loss, while the target parameters ø follow a different objective. This non-collapsing behavior even without relying on negatives has been studied further (Tian al., 2021). We provide an empirical analysis of this behavior in Appendix A, showing that in practice BGRL does not collapse to trivial solutions and E(0, () does not converge O.
Scalable non-contrastive objective: Here we note that a contrastive approach would instead encourage (1.s) and ((2))) to be far apart for node pairs (i.j) that are dissimilar. In the absence of a principled way of choosing such dissimilar pairs, the na've approach of simply contrasting all pairs {(i, i * j}. scales quadratically in the size of the input. As BGRL does rely on this contrastive step, BGRL scales linearly in the size of the graph, and thus is scalable by design.
3 COMPUTATIONAL COMPLEXITY ANALYSIS
We provide brief description of the time and space complexities of the BGRL update step, and illustrate its advantages compared to previous strong contrastive methods such as GRACE (Zhu et al., 2020b), which perform a quadratic all-pairs contrastive computation at each update step. The same analysis applies to variations of the GRACE method such as GCA (Zhu al., 2020a).
Consider a graph with N nodes and M edges, and simple encoders E that compute embeddings time and space O(N + M). This property is satisfied by most popular GNN architectures such as convolutional (Kipf & Welling, 2017), attentional (Veličković et al., 2018), or message-passing (Gilmer et al., 2017) networks. BGRL performs four encoder computations per update step (twice for the target and online encoders, and twice for each augmentation) plus node-level prediction step; GRACE performs two encoder computations (once for each augmentation). plus a node-level projection step. Both methods backpropagate the learning signal twice (once for each augmentation),
3

---

Published as a conference paper at ICLR 2022
and we assume the backward pass to be approximately as costly a forward pass. We ignore the cost for computation of the augmentations in this analysis. Thus the total time and space complexity per update step for BGRL is enender (M .N + PCrediiction . + CBCRL compared to enoooee (M + .) Prrojeccioo N + CGRACE for GRACE, where C. are constants depending on architecture of the different components, Table shows an empirical comparison of BGRL and GRACE's computational requirements on a set of benchmark tasks, with further details in Appendix I.
Dataset
Amazon Photos
WikiCS
Amazon Computers
Coauthor CS
Coauthor Phy
#Nodes
7.650
11,701
13.752
18,333
34,493
#Edges
119,081
216,123
245,861
81,894
247,962
BGRL Memory
0.47 GB
0.63 GB
0.58 GB
2.86 GB
5.50 GB
GRACE Memory
1.81 GB
3.82 GB
5.14 GB
11.78 GB
OOM
Table I:
Comparison of computational requirements on set of standard benchmark graphs. 0OM indicates ruuning out of memory 16GB V100 GPU.
4 EXPERIMENTAL ANALYSIS
We present extensive empirical study of performance and scalability, showing that BGRL is effective across a wide range of settings from frozen linear evaluation to semi-supervised learning, and both when performing full-graph training and training on subsampled node neighborhoods. We give results across a range of dataset scales and encoder architectures including convolutional, attentional, and message-passing neural networks.
We analyze the performance of BGRL on set of 7 standard transductive and inductive benchmark tasks, as well in the very high-data regime by evaluating on the MAG240M dataset (Hu al., 2021). We present results on medium-sized datasets where contrastive objectives can be computed on the entire graph (Section 4.1), on larger datasets where this objective must be approximated (Section 4.2), and finally on the much larger MAG240M dataset designed to test scalability limits (Section 4.3), showing that BGRL improves performance across all scales of datasets. show that BGRL achieves state-of-the- the-aatt performance even in the low-data regime on set of 4 small-scalc datasets. Dataset sizes are summarized in Table and described further Appendix
Appendix C,
Evaluation protocol: In most tasks, follow the standard linear-evaluation protocol on graphs (Veličković et al., 2019). This involves first training each graph encoder in a fully un- supervised manner and computing embeddings for each node; a simple linear model is then trained on top of these frozen embeddings through a logistic regression loss with lg regularization, without flowing any gradients back to the graph encoder network. In the more challenging MAG240M task, we extend BGRL to the semi-supervised setting by combining our self-supervised representation learning loss together with supervised loss. We show that BGRL's 's bootstrapping objective obtains state-of-the-art performance in this hybrid setting, and even improves further with the added use of unlabeled data for representation learning- properties which have not been previously demonstrated by prior works on self- supervised representation learning graphs.
Implementation details including model architectures and hyperparameters are provided in Ap- pendix F. Algorithm implementation and experiment code for most tasks can be found at https://ithub.com/ee www./neddaaabbbbgdd while code for our solution on MAG240M has been open-sourced as part of the KDD Cup 202/ (Addanki al., 2021) at https//gihhbb.com//eepmnn///eee beseercctttee/nsstrgggg........ lsc/mag.
4.1 PERFORMANCE AND EFFICIENCY GAINS WHEN SCALABILITY IS NOT A BOTTLENECK
We first evaluate our method on a set of 5 recent real-world datasets - WikiCS, Computn-Cmmputes, Amazon-Photos, Coauthor-CS, Coauthor-Physics challenging medium-seee sicllui--caleeeeee datasets specifically proposed for rigorous evaluation semi- semi-supervised node classification methods (Meryyei & Cangea, 2020; Shchur et al., 2018), but are almost all small enough that constrastive approaches such as GRACE (Zhu et al., 2020b) can compute their quadratic objective exactly. Thus, these experiments present a comparison of BGRL with prior methods in the
in the transductive setting. Note that these are
4

---

Published as a conference paper at ICLR 2022
Task
Nodes
Edges
Features
Classes
WikiCS
Transductive
11,701
216,123
300
10
Amazon Computers
Transductive
13,752
245,861
767
10
Amazon Photos
Transductive
7,650
119,081
745
Coauthor CS
Transductive
18,333
81,894
6,805
15
Coauthor Physies
Transductive
34,493
247,962
8,415
ogbn-arxiv
Transductive
169,343
1,166,243
128
40
PPI (24 graphs)
Inductive
56,944
818,716
50
121 (multilabel)
MAG240M
Transductive
244,160,499
1,728,364.232
768
153
Table 2: Statistics of datasets used our experiments.
idealized case where scalability is not a bottleneck. We show that even in this steelmanned setting, our method outperforms or matches prior methods while requiring fraction of the memory costs.
We primarily compare BGRL against GRACE, a recent strong contrastive representation learning method on graphs. We also report performances for other commonly used self seff-supe graph methods from previously published results (Perozzi et al., 2014; Veličković et al., 2019; Peng et al., 2020; Hassani Khasahmadi, 2020; Zhu al., 2020a), as well as handom-Init (Veličković et al., 2019), baseline using embeddings from a randomly initialized encoder, thus measuring the quality of the inductive biases present in the encoder model. We use a 2-layer GCN model (Kipf Welling, 2017) our graph encoder E, and closely follow models, architectures, and muph-augmentation settings used in prior works (Zhu et al., 2020a; Veličković et al., 2019; Zhu et al., 2020b).
WikiCS
Am. Comp.
Am. Photos
Co.CS
Co.Phy
Raw features
71.98 + 0.00
73.81 0.00
78.53 + 0.00
90.37 0.00
93.58 0.00
DeepWalk
74.35 + 0.06
85.68 + 0.06
89.44 + 0.11
84.61
0.22
91.77 0.15
DeepWalk feat.
77.21 + 0.03
86.28 = 0.07
90.05 0.08
87.70 + 0.04
94.90 + 0.09
DGI
75.35 0.14
83.95 0.47
91.61
92.15 0.63
94.51 0.52
74.85 + 0.08
82.21 = 0.31
90.68 0.17
0OM
0OM
MVGRL
77.52 + 0.08
87.52 = 0.11
9.074
9.11
95.33 0.03
Bandom-Init'
78.95 + 0.58
86.46 0.38
92.08 1.44
9.264
93.71 +: 0.29
GRACE
80.14 1 0.48
89.53 0.35
92.78
0.45
91.12 0.20
0OM 95.73 0.05
BGRL
79.98 + 0.10
90.34 0.19
93.17 0.30
93.31 + 0.13
GCA Supervised GCN
78.35 1 0.05
94 0.15
92.53 1 0.16
93.10 1 0.01
95.73 1 0.03
77.19 1 0.12
86.51 1 0.54
92.42 1 0.22
93.03 1 0.31
95.65 1 0.16
Table 3: Performance measured in terms of classification accuracy along with standard deviations. Our experiments, marked as *, are over 20 random dataset splits and model initializations. The other results are taken from previously published reports. OOM indicates running out of memory a 16GB V100 GPU. We report the best result for GCA out of the proposed GCA-DE, GCA-PR, and GCA-EV models.
In Table 3, we report results of experiments on these standard benchmark tasks. We see that even when scalability does not prevent the use of contrastive objectives, BGRL performs competitively both with our unsupervised and fully supervised baselines, achieving state-of-the-art performance of the 5 datasets. Further, as noted in Table 1, BGRL achieves this despite using 2-10x less memory. BGRL provides this improvement in memory-effciiency at no cost in performance, demonstrating useful practical advantage over prior methods such as GRACE.
Effect of more complex augmentations: In addition to the original GRACE method, we also highlight GCA, a variant of it that has the same learning objective but trades off more expressive but expensive graph augmentations for better performance. However, these augmentations often take time cubie in the size of the graph, are otherwise cumbersome to implement on large graphs. As we focus on scalability to the high-data regime, we primarily restrict our comparisons to the base method GRACE, which uses the same simple, easily scalable augmentations sake of completeness, in Table we investigate the effect of these complex augmentations with BGRL. We see that BGRL obtains equivalent performance with both simple and complex augmentations, while GCA requires more expensive augmentations for peak performance. This indicates that BGRL can safely rely simple augmentations when scaling to larger graphs without sacrificing performance.
BGRL. Nevertheless, for the
5

---

Published as a conference paper at ICLR 2022
Method
Augmentation
Co.CS
Co.Phy
Am. Comp.
Am. Photos
BGRL
Standard
93.31
95.73 + 0.05
90.34
93.17 0.30
Degree centrality
93.34 = 0.13
95.62 0.09
90.39 0.22
93.15 + 0.37
Pagerank centrality
93.34 = 0.11
95.59 1.09
90.45
93.13 + 0.34
Figenvector centrality
93.32 0.15
95.62 0.06
90.20
93.03 0.39
GCA
Standard
92.93 = 0.01
95.26
0.02
+ 0.02
86.25 0.25
92.15 + 0.24
Degree centrality
93,10 = 0.01
95.68 - 0.05
87.85 0.31
92.49 + 0.09
Pagerank centrality
93.06 = 0.03
95.72 0.03
87.80
+ 0.23
92.53 + 0.16
Eigenvector centrality
92.95 0.13
95.73 + 0.03
87.54 + 0.49
92.24 0.21
Table 4: Comparison of BGRL and GCA for simple versus complex augmentation heuristics on four benchmark graphs. For GCA, report the numbers provided in their original paper.
Validation
Test
MLP
57.65 0.12
55.50 0,23
node2vec
71.29 + 0.13
70.07 0.13
Random Random-Init'
69.90 = 0.11
68,94 + 0.15
DGI"
71.26 + 0.11
7.16
GRACE full full-graph"
0OM
OOM
PRACE-SUBSAMPL.ENE (h: 2)
60.49 3.72
4.02
GRACE- SAACE-SUBSAMPLING (A: 8)*
71.30 0.17
70.33
(k- =32)"
72.18 0.16
71.18
MAACEE-SBBAMPLING (k- 20048*
72.61 1 0.15
71.51 1 0.11
BGRL*
72.53
71.64 0.12
Supervised GCN
73.00 0.17
71.74 + 0.29
Table 5: Performance the ogbn-arXiv task measured terms of classification accuracy along with standard deviations. Our experiments, marked as *, are averaged over 20 random model initializations. Other results are taken from previously published reports. OOM indicates running out of memory on 16GB V100 GPU.
4.2 SCALABILITY-PEFFORMAAN TRADE-OFFS FOR LARGE GRAPHS
When scaling up to large graphs, it may not be possible to compare each node's representation to all others. this case, a natural way to reduce memory is to compare each node with only a subset of nodes in the rest of the graph. To study how the number of negatives impacts performance in this case, we propose an approximation of GRACE's objective called SAACE-SUBSAMPLIIH of contrasting every pair of nodes in the graph, we subsample l nodes randomly across the graph to use as negative examples for each node at every gradient step. Note that & = 2 the asymptotic equivalent of BGRL in terms of memory costs, BGRL always only compares each node with itself across both views, i.e., BGRL faces no such computational difficulty or design choice in scaling up.
where instead
EVALUATING ON ORBI- DATASET
To study the tradcoff between performance and complexity we consider a node classification task on much larger dataset, from the OGB benchmark (Hu al., 2020a), ogbn-arXiv. In this case, GRACE cannot run without subsampling (on GPU with 16GB of memory). Considering the increased difficulty of this task, we slightly expand our model use 3 GCN layers, following the baseline model provided by Hu et al. (2020a). As there has not been prior work on applying GNN-based unsupervised approaches the ogbn-arXiv task, we implement and compare against two representative contrastive- learning approaches, DGI and GRACE. In addition, we report results from Hu et al. (2020a) for node2vec (Grover & Leskovec, 2016) and a supervised-leaninng baseline. We report results on both validation and test sets, as is convention for this task since the dataset is split based on chronological ordering.
Our results, summarized in Table 5, show that BGRL is competitive with the supervised learning PRACE-SUBSAMPLLET
baseline. Further, we note that the performance parameter A k-requiring a large number of negatives to match the performance of BGRL. Note that BGRL far exceeds the performance in terms of memory; and that larger values of k lead to out-of- memory errors These results suggest that the performance contrastive methods such as GRACE may suffer due to approximations their objectives that must be made when scaling up.
very sensitive to the
GRACE- SUBSAMPLING with k = 2, its asymptotic equivalent 16GB GPU.

---

Published as a conference paper at ICLR 2022
PPT
Raw features
42.20
DGI
63,80 + 0.20
GMI
65.00 0.02
Random-Init
62.60 0.20
GRACE McanPooling encoder'
69.66 + 0.15
BGRL McanPooling encoder'
69.41 + 0.15
GRACE GAT encoder"
69.71 0.17
BGRL GAT encoder*
70.49 + 0.05
Supervised MeanPooling
96.90 + 0.20
Supervised GAT
97.30 + 0.20
Table 6: Performance on the PPI task measured in terms of Micro-F, across the 121 labels along with standard deviations. Our experiments. marked as are averaged over 20 random model initializations. Other results are taken from previously published reports.
EVALUATING ON PROTEIN-PROTERE INTERACTION DATASET
Next, we consider the Protein-Proteii Interaction (PPI) task-a more challenging inductive task on multiple graphs where the gap between the best self-supervised methods and fully supervised methods is (still) significantly large, due to 40% of the nodes missing feature information. In addition to simple mean-pooliing propagation rules from GraphSage-GGa GCN (Hamilton et al., 2017), we also consider Graph Attention Networks (GAT, Veličković al., 201 8) where each node aggregates features from its neighbors non-uniformly using a learned attention weight. It has been shown (Veličković et al., 2018) that GAT' improves over non-attentional models this dataset when trained in supervised settings, but these models have thus far not been able to be trained to a higher performance than non-attentional models through contrastive techniques.
We report our results in Table 6, showing that BGRL is competitive with GRACE when using the simpler MeanPooling networks. Applying BGRL to GAT model, results in a new state-of-the performance, improving over the MeanPooling network. On the other hand, the GRACE contrastive loss is unable to improve performance a GAT model over the non-attentional MeanPooling encoder. We observe that the approximation of the contrastive objective results not only in lower accuracies
Grace sampling
Gracs sampligg
Grace sampling C4
0.75
Grace sampligg 128
Goae samplin 256
Goaee samplins
1000
0.55
Gracs camplng
sampling
500
campling 8G4L.
2500
5000
7500
10036
12500
35:00
17500
Figure 2: PPT task performance, averaged over 20 seeds.
Figure 3: Histogram of GAT attention entropies.
(Figure 2), but also qualitatively different behaviors in the GAT models being trained. In Figure we examine the internals of GAT models trained through both BGRL and GRACE by analyzing the entropy of the attention weights learned. For each training node, we compute the average entropy of its attention weights across all GAT layers and attention heads, minus the entropy of uniform attention distribution as a baseline. We see that GAT models learned using GRACE, particularly when subsampling few negative examples, tend to have very low attention entropies and perform poorly. On the other hand, BGRL is able to train the model to have meaningful attention weights, striking balance between the low-entropy models learned through GRACE and the maximum-entropy
7

---

Published as a conference paper at ICLR 2022
uniform-attention distribution. This aligns with recent observations (Kim & Oh, 2021; Wang et al., 2019) that auxiliary losses must be chosen carefully for the stability of GAT attention weights.
4.3 SCALING TO EXTREMELY LARGE GRAPIIS
To further test the scalability and evaluate the performance of BGRL in the very high-data regime, we consider the MAG240M node classification task (Hu et al., 2021). As a single connected graph of 360GB with over 240 million nodes (of which 1.4 million are labeled) and 1.7 billion edges, this dataset is orders of magnitude larger than previously available public datasets, and poses a significant scaling challenge. Since the test labels for this dataset are (still) hidden, we report performance based on validation accuracies in our experiments. Implementation and experiment details are in Appendix G.
To account for the increased scale and difficulty of the classification task on this dataset, make number of changes to our learning setup. First, since we can no longer perform full-graph training due the sheer size of the graph, we thus adopt the Neighborhood Sampling strategy proposed by Hamilton et al. (2017) to sample a small number of central nodes at which our loss is to be applied, and sampling fixed size neighborhood around them. Second, we use more expressive Message Passing Neural Networks (Gilmer et al., 2017) as our graph encoders. Finally, as we are interested in pushing performance on this competition dataset, we make use of the available labels for representation learning and shift from evaluating on top of a frozen representation, to eemi-supervised training by combining both supervised and self-supervised signals at each update step. We emphasize that these are significant changes from the standard small-scale evaluation setup for graph representation learning methods studied previously, and more closely resemble real-world conditions in which these algorithms would be employed.
MAG240M Dataset
Mixing varying fraction unlabeled data
0.7400
0.734
0.7375
0.732
0.7350
0.7.0
Accursiy
0.7325
0.728
0.7 0.7300
0.726
0.7275
0.724
BGRL superised semi suporvised
0.7250
Dx uniaieled unlabeled
0.722
0.7225
unlobeled
Fully supervised
10x urlabeled
0.720
8.7200
10000
20600
30c0n
40000
50900
100000
200000
200000
400000
506800
Training Stop
Training Step
Figure 4: Performance on MAG240M using BGRL or GRACE-SUBSAMLLNN as an auxiliary signal, av- eraged over 5 seeds and run for 50k steps.
Figure 5: Mixing varying amounts of unlabeled data for representation learning with BGRL, averaged over 5 seeds and run for 500k steps.
In Figure 4, we see that BGRL used as an auxiliary signal is able to learn faster and significantly improve final performance over fully supervised learning on this challenging task. Considering the difficulty of this task and the small gap in final performance between winning entries in the KDDI Cup 2021 contest, this is a significant improvement. On the other hand, MAACESSBBAMMPLING provides much lower benefits over fully supervised learning, possibly due to no longer being able to sample sufficiently many negatives over the whole graph. Here we used k 256 negatives, the largest value we were able to run without running out of memory.
We further show that we can leverage the high scalability of BGRL to make use of the vast amounts of unlabeled data present in the dataset. Since labeled nodes form only 0.5% of the graph, unlabeled data offers rich self-supervised signal for learning better representations and ultimately improving performance on the supervised task. In Figure 5, we consider adding some number of unlabeled nodes to each minibatch of data, and examine the effect on performance as this ratio of unlabeled to labeled data in each batch increases. Thus at each step, we apply the supervised loss on only the labeled nodes in the batch, and BGRL on all nodes. Note that a ratio of 0 corresponds to the case where we apply BGRL as auxiliary loss only the training nodes, already examined in Figure 4. We observe a dramatic increase in both stability and peak performance as we increase this ratio, showing that BGRL can utilize the unlabeled nodes effectively to shape higher quality representations and prevent
8

---

Published as a conference paper at ICLR 2022
early overfitting to the supervised signal. This effect shows steady improvement we increase this ratio from Ix to 10x unlabeled data, where we stop due to resource constraints on running ablations on this large-scale graph however, this trend may continue to even higher ratios, the true ratio of unlabeled to laheled nodes present in the graph is 99x.
This result of 73.89% is state-of-the-art for this dataset for the highest single-mode performance (i.e., without ensembling) - the OGB baselines report a score of 70.02% (Hu et al., 2021) while the KDD Cup 2021 contest first place solution reported a score of 73.71% % before ensembling.
KDD Cup 2021:" Our solution using BGRL to shape representations, utilizing unlabeled data in conjunction with a supervised signal for semi-supervised learning, was awarded as one of the winners of the MAG240M track at DGB-LSC(Addank) et al., 2021). It achieved final position of second overall, achieving 75. 75.19% accuracy on the test set. The first and third place solutions achieved 75.49% and 74.60% respectively. Although differences in many other factors such model architectures, feature engineering, ensembling strategies, etc. prevent a direct comparison' between these solutions, these results serve strong empirical evidence for the effectiveness of BGRL for learning representations on extremely large scale datasets.
RELATED WORK
Early methods in the area relied on random-walk objectives such as DeepWalk (Perozzi al., 2014) and node2vec (Grover & Leskovec, 2016). Even though the graph neural networks (GNNs) inductive bias aligns with these objectives (Wu et al., 2019; Veličković et al., 2019; Kipf & Welling, 2017), com- posing GNNs and random-wale walks does not work very well and can even degrade performance (Hamil- ton et al., 2017). Earlier combinations of GNNs and self-supervised learning involve Embedding Propagation (Garefa-Durán & Niepert, 2017), Variational Graph Autoencoders (Kipf & Welling, 2016) and Graph2Gauss (Bojchevski & Günnemann, 2018). Hu et al. (2020b) leverages BERT (Devlin et al., 2019) for representation learning in graph-structured inputs. Hu al. (2020b) assumes specific graph structures and uses feature masking objectives to shape representations.
Recently, contrastive methods effective images have also been adapted to graphs using GNNs. This includes DGI (Veličković et al., 2019), inspired by Deep InfoMax Hjelm et al. (2019), which contrasts node-local patches against global graph representations, Next, Inf onrahh (Sun et al., 2020) modified DGI's pipeline for graph classification tasks. GMI Peng et al. (2020) maximizes notion of graphical mutual information inspired by MINE (Belghazi et al., 2018). allowing for a more fine- grained contrastive loss than DGI's. s.. The SimCLR method of Chen et al. (2020a;b) has been specialized for graphs by GRACE and variants such as GCA (Zhu et al., 2020b;a) that rely on more complex data- adaptive augmentations. GraphCL (You et al., 2020) adapts SimCLR to learn graph-level embeddings using a contrastive objective. MVGRL (Hassani & Khasahmadi, 2020) generalizes CMC (Tian et al., 2020) to graphs. Graph Barlow Twins (Bielak al., 2021) presents method to learn representations by minimizing correlation between different representation dimensions. Concurrent works DGB (Che al., 2020) and SelfGNN (Kefato & Girdzijauskas, 2021), like BGRL, adapt BYOL (Grill al., 2020) for graph representation learning. However, BGRL differs from these works in the following ways:
We show that BGRL scales to and attains state-of-the-art results on the very high-data regime on the MAG240M dataset. These results are unprecedented in the graph self-supervised learning literature and demonstrate high degree of scalability.
We show that BGRL is effective even when trained on sampled subgraphs and not full graph.
We provide an extensive analysis of the perfornance-copptatioo trade-off of BGRL versus contrastive methods, showing that BGRL can be more efficient in terms of computation and memory usage as it requires no negative examples.
We show that BGRL is effective when performing semi-supervised training, providing further gains when leveraging both labeled data and unlabeled data. This is significant result that has not been demonstrated in graph representation learning methods using neural networks prior
work.
I cadeebooar at https://ogh.staatet/e stanford. stanforddedu/kddddeeee edu/kddcup2222 1rteuupp222//r/r//////eaaae /results/Hawarrdess hatp:///aaaardeessmaa000..... For example, the first place solution used much larger set of 30 ensembled models compared to our 10, and exclusively relied architectural improvements improve performance without using self- self-super learning.

---

Published as a conference paper at ICLR 2022
ICLR ETHICS STATEMENT
Our contributions are in developing and evaluating a general method for self-supervised representation learning graphs. As such, they may be helpful in applications where obtaining labels can be challenging or expensive, thus enabling newer applications potentially in the direction of positíve social good.
On the other hand, an unsupervised pretraining method, there is a risk of practitioners using it for downstream tasks without carefully considering how these embeddings were originally trained, potentially leading to stereotyping or unfair biases. Further, since the bootstrapping dynamics of BGRL are not yet fully understood, there is a higher chance of it being used as a blackbox machine learning method and harmful downstream effects being difficult diagnose and resolve.
ICLR REPRODUCIBILITY STATEMENT
We believe that the results we report in this paper are reproducible and strengthen our empirical contributions.
We have submitted our algorithm implementation and experimental setup, config, and code for almost all of our experiments supplementary material. Most experiments finish within 30 minutes a single V100 GPU, and thus are easy to verify with few resources. addition, we are providing trained model weights/checkpoints for directly loading and verifying performance without train- ing. Experiments for which code has not been provided are described in detail in the appendices (Appendix E and Appendix F) and should allow for reproduction.
Besides this, code for our large-scale MAG240M solution has been open-sourced as part of the KDD) Cup 2021 and has been verified independently by the OGB-LSC contest organizers.
REFERENCES
Ravichandra Addanki, Peter W. Battaglia, David Budden, Andreea Deac, Jonathan Godwin, Thomas Keck, Wai Lok Sibon Li, Alvaro Velickovic. scale graph representation learning with very deep gnns and self-supervision. CoRR, abs/2107.0940 092.09927 2021. URL https: //axxivv org/ wwwaaaas/001 09422.
Jacklynn Stott, Shantanu Thakoor, and Petar
Jimmy Ba, J. Kiros, and Geoffrey E. Hinton. Layer normalization. ArXiv, 0bss/1677.0444 2016.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International Conference on Machine Learning, 2018. URL http:hht/ppcceeediineeen/////
mlr. www..prees//eee hatps//v0/bbelgaaaeeee 11a.. html.
Piotr Bielak, Tomasz Kajdanowicz, and Nitesh V. Chawla. Graph barlow twins: self-supervised representation learning framework for graphs. CoRR, abs/2106.02466, 2021. URL https:
//arxiv. llaaaaii..rgaaas////a/aaaaaaaaaa wtgg/bss///0/.oo/ 02466.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. arXiv preprint 1rXiv:1707.03813 2017.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. In International Conference on Learning Representations, 2018. 8.
URL https::/ nett/forumiidrr12k..1111
Lowik Chanussot, Abhishek Das, Siddharth Goyal, Thibaut Lavril, Muhammed Shuaibi, Morgane Riviere, Kevin Tran, Javier Heras- Dorra-DDmmnno, Caleb Ho, Weihua Hu, and al. Open catalyst 2020 (oc20) dataset and community challenges. ACS Catalysis, ((10):6059-6072 May 2021. ISSN 2155-5435. doi: 10. httl://cccaal..00445555 URL http::/dxx.ee doi http::///....oooo///...ooo. http:///.....//aaaaaaaaaaa 0c04525.
Feihu Che, Guohua Yang. Dawei Zhang, Jianhua Tao, Pengpeng Shao, and Tong Liu. Self-supervised graph representation learning via bootstrapping. arXiv preprint arXiv:201 1.05/26, 2020.
10

---

Published as a conference paper at ICLR 2022
Ting Chen, Simon Komblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning, 2020a. URL http::h/ppooceednnggeee mlr.
wttp:gg..w.....eei/esseeeee wttppp//11///cee200000000 .tmll.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E. Hinton. Big self-supervised models are strong semi-supervised Iearners. In Neural Information Pro- cessing Systems, 2020b. URL attpes:/prroeeedingg neurips...... cttplps..cccpeeeec ct/cc////a////.e hppppp///2///////pa/pp/ Eooo5ccddd51dd11120000000 Abstract. hhttrallct.tll......
Djork-Aréé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learn- ing by exponential linear units (elus). In International Conference on Learning Representations, 2016. URL http: /tttp://arxiv.ortt abs 1511. 07289.
Deng, Dong, R. Socher, L.-J. Li, Li, and Fei-Fei. ImageNet: Large-Scale Hierarchical Image Database. In CVPR09, 2009.
Austin Derrow-Pinion, Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Marc Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, Peter W. Battaglia, Vishal Gupta, Ang Li, Zhongwen Xu, Alvaro Sanchez-Gonzalez. Yujia Li, and Petar Velickovie. ETA prediction with graph neural networks google maps. CoRR, abs/2108. 1482, 2021. org/abs/2108 11482.
URL attps://arxxe
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. Conference of the North American Chapter of the Association for Computational Linguistics, 2019. doi: 10.18653/v1/N199 1423.
URL https: //ww. aclweb. org/ aat/aholooo//1111222222
Alberto Garefa-Durán and Mathias Niepert. Learning graph representations with embedding propaga- tion. In Neural Information Processing Systems, 2017. ISBN 9781510860964,
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, 2017.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Conference on Artificial Intelligence and Statisties, 2010.
Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko. Bootstrap your own latent: A new approach to self-supervised learning. In Neural Information Processing Systems, 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In ACM SIGKDD International Conference on Knowledge discovery and Data Mining, 2016.
Sylvain Gugger and Jeremy Howard. Adamw and super-convergence is now the fastest way train neural nets. https: / /tww///www../ fast. ai/2018/01 wwwp////wwwwwwwaaaaaaaeeeeeee
2018.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Neural Information Processing Systems, 2017. URL https://///// http:///aaaaaaaaaaaaaataaaaaaaaa Abstrrat. html.
neuripa ips.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-viww representation lcarning on graphs. In International Conference Machine Learning, 2020. URL http://prooceeddngg mlr. www.prresvvvve hwwe111//hhhaaanee 20a. html.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In International Conference on Computer Vision, USA, 2015. ISBN 9781467383912 doi: 10.1109//CC.22015..222 URL https://doi. org/10. 1109 1109/ICCVV ICCV. 2015. 123.
11

---

Published as a conference paper at ICLR 2022
R. Devon Hjelm, Alex Fedorov, Samuel Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference Learning Representations, 2019. URL https: //openreviev wtwpaarviwiw..etefrrreeeeee
Karan Grewal, Philip Bachman, Adam
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. In Neural Information Processing Systems, 2020a. URL http:: httttps://proceednngg. neur.ss.. meurips.cc/paper.
2020 22000h/ese/.0001111cc0000777/720 Abstract. .tml.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference Learning Representations, 2020b. URL https: http:::///pppeevieeee net/ forum/1d-HUJWWWSFD
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Isc: A large-scale challenge for machine learning on graphs, 2021.
Sergey loffe and Christian Szegedy. Batch normalization:
Accelerating deep network training by reducing internal covariate shift. In International Conference Machine Learning, 2015. URL wttp:/ing.......ese///////////// hwtp///fffe....//// .ttml.
http:// proceedings..... weweeeeeinnn.m.....ee.eeeeeeee.e pwwps////eiiiieeee
Zekarias T. Kefato and Sarunas Girdzijauskas. Self-supervised graph neural networks without explicit negative sampling. CoRR, abs/2103.14999 14958, 2021. URL httpt: org/abs/ /203., 14958.
Dongkwan Kim and Alice Oh. How to find your friendly neighborhood: Graph attention design with self-supervision. In International Conference on Learning Representations, 2021. URL
/tttps://opereeviii net/ wwweet/forumm// 1o
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. URL http: wttps//org/ababb//////// 19800
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv: 1en:::111.0000000 1.07308, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https://openrrviier net//forum?dd-SJU4ay22
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image-based recom- mendations styles and substitutes. In ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 11, 2015. ISBN 978 1450336215. doi: 10.114522766462227677555 URL https://doi. org/10. / 2767755.
Péter Mernyei and Cătälina Cangea. Wiki-es: wikipedia-based benchmark for graph neural networks, 2020.
Tomás Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. In International Conference on Learning Representations, 2013. URL http://arxis: wrweeorg/gaaaaae htrg//bs//00 /tt///111.388.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830. 2011.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Jun- zhou Huang. Graph Representation Learning via Graphical Mutual Information Maximiza- tion, pp. 259-270. Association for Computing Machinery. New York. NY, USA, 2020. ISBN 9781450370233. https:/:: org/ 1145/3366423 3380112.
Jeffrey Pennington, Richard Socher. and Christopher Manning. GloVe: Global vectors for word representation. In Conference on Empirical Methods Natural Language Processing, 2014. doi: 10.3115/v 1162. htt.httss: h/t::://wwwweet awwweb. org/ http///hoooog//141112222
12

---

Published as a conference paper at ICLR 2022
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk. ACM SICKDD International Con- ference on Knowledge discovery and Data Mining, 2014. doi: 10.114552623330.22223222 URL
http://dx.0 http:/xx.dooi..ooo org. 1111114//232222.2 2623733
Siyuan Qiao, Huiyu Wang. Chenxi Liu, Wei Shen, and Alan L. Yuille. Weight standardization, CoRR,
abs/1903. 10520, 2019. URL http: //axivv.////.vee//eeee/ee www./ogg//////aooooo..oeoee http//aa//11....5555
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification. In International Conference on Learning Representations, 2019.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS 2018, 2018.
Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June (Paul) Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In International Conference on World Wide Web, 2015. ISBN 9781450334730. doi: 10. A..11///749900824228833 URL https://doi...... org/10. / 2742839.
Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. In Interna- tional Conference on Learning Representations, 2020. URL htttps://openrevviee..ettt
id-r11fF2NYvH.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In 2020, doi: 11t.:///.0000977-------300- 10.1007/978-3-0300 3-030-58622 18661-887 _58 URL ott
Yuandong Tian, Xinlei Chen, and Surya Ganguli. Understanding self-supervised learnng dynamics without contrastive pairs. CoRR, abs/2102.066) 2021. URL htkL.ttts///rrxx..orr////ae o010 06810.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL https:// htt.rrr.......ttttorooaaaaaaaaaa
Petar Veličković, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019.
http:///pppareeeeeeeaaoaraaaaaaa wwtp://orrrmmiidr11........ URL https: htttt:::///peerevieeee
Guangtao Wang, Rex Ying, Jing Huang, and J. Leskovec. Improving graph attention networks with large margin-based constraints. ArXiv, abs/1910. 1994, 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In International Conference on Machine Learning, 2019.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Neural Information Pro- cessing Systems, 2020. URL https: sttps://proceedingg wetpeeeddinnn.uurrpps..... www..neuuuccppppeeeeee wwwpp//pp///////////ecp Abstract html.
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propaga- tion. 2002.
Yanqiao Zhu, Yichen Xu, Feng Yu. Qiang Liu, S. Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. ArXiv, abs/2010. 14945, 2020a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. ArXiv, abs/2006.04131, 2020b.
13

---

Published as a conference paper at ICLR 2022
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue net- works. Bioinformatics, 33(14)1190-i1198 Jul 2017. ISSN 1460-2059. doi: 00.10%//ioimformatic//// btx252. URL http: doii http:////..00/.ooooooooo/oo/////
14

---

Published as a conference paper at ICLR 2022
A BGRL DOES NOT CONVERGE TO TRIVIAL SOLUTIONS
In Figure 6 we show the BGRL loss curve throughout training for all the datasets considered. As we see, the loss does not converge zero, indicating that the training does result in trivial solution.
In Figure 7 we plot the spread of the node embeddings, i.e., the standard deviation of the represen- tations learned across all nodes, divided by the average norm. As see, the embeddings learned across all datasets have a standard deviation that a similar order of magnitude as the norms of the embeddings themselves, further indicating that the training dynamics do not converge a constant solution.
Further, Figure 8 shows that the embeddings do not collapse zero or blow up as training progresses.
1.40
Priting
Figure 6: BORL Loss
Figure Embedding spread
Figure 8: Average embodding norm
B ABLATIONS ON PROJECTOR NETWORK
As noted in Section BGRL does not use a projector network, unlike both BYOL and GRACE, Prior works such as CRACE use a projector network to prevent the embeddings from becoming completely invariant to the augmentations used however purpose. On the other hand, BYOL relies on this for dimensionality reduction, to simplify the task of the predictor pa, as challenging to directly predict very high-dimensional embeddings. required for large-scale vision tasks like ImageNet (Deng al., 2009). Here empirically verify that even in our most challenging, large-scale task of MAG240M, the projector network is not needed and only slows down learning. In Figure we can that adding the projector network leads to both slower learning and a lower final performance.
BGRL, the predictor network can serve the same
MAG240M Dataset
0.734
0.732
0.730
Accuracy
0.728
0.726
0.724
0.722
BGRL with projector
BGRL without projector
0.720
10000
20000
30000
40000
50000
Training Step
Figure 9: Performance on OGB-LSC MAG240M task, averaged over seeds, testing effect of using projector network.
15

---

Published as a conference paper at ICLR 2022
C COMPARISON ON SMALL DATASETS
We perform additional experiments on 4 commonly used small datasets, (Cora, CiteSeer, PubMed, and DBLP) (Sen et al., 2008; Bojchevski & Günnemann, 2017) and show that BGRL's bootstrapping mechanism still performs well in the low-data regime, even attaining new state of the art performance on two the datasets.
Note that Table reports results averaged over 20 random dataset splits, as has been followed in Zhu al. (2020b), instead of using the standard fixed splits for these datasets which are known to easy to unreliable for evaluating GNN methods (Shchur et al., 2018).
Cora
CiteSeer
PubMed
DBLP
GRACE
83.02 + 0.89
71.63 E 0.64
86.06 + 0.26
84.08 0.29
BGRL
83.83 + 1.61
72.32 + 0.89
86.03 + 0.33
84.07 + 0.23
Supervised
82.8
72.0
84.9
82.7
Table 7: Evaluation on small datasets. Results averaged over 20 dataset splits and model initializations.
D GRAPH AUGMENTATION FUNCTIONS
Generating meaningful augmentations is much less explored problem in graphs than in other domains such as vision. Further, since we work over entire graphs, complex augmentations can be very expensive to compute and will impact all nodes once. Our contributions are orthogonal to this problem, and we primarily consider only the standard graph augmentation pipeline that has been used in previous works representation learning (You et al., 2020; Zhu et al., 2020b).
In particular, we consider two simple graph augmentation functions - node feature masking and edge masking. These augmentations are graph-wise: they do not operate each node indepen- dently, and instead leverage graph topology information through edge masking. This contrasts with transformations used in BYOL, which operate each image independently. First, we generate single random binary mask of size F, each element of which follows a Bernoulli distribution (5(1 py), and use it to mask features of all nodes in the graph (i.e., all nodes have the same features masked). Empirically, we found that performance is similar for using different random masks per node or sharing them, and so we use a single mask for simplicity. In addition to this node-level attribute transformation, we also compute a binary mask of size E (where E' is the number of edges in the original graph), each element of which follows a Bernoulli distribution B(1 Pe). and use it to mask edges in the augmented graph. To compute our final augmented graphs, we make use of both augmentation functions with different hyperparameters for each graph, i.e. pf, and pe, for the first view, and Pfa and Pca for the second view.
Section 4.1 we also consider more complex adaptive augmentations proposed by prior works (Zhu et al., 2020a) which use various heuristics to mask different features or edges with different probabilities.
Beyond these standard augmentations,
E DATASET DETAILS
WikiCS This graph is constructed from Wikipedia references, with nodes representing articles about Computer Science and edges representing links between them. Articles are classified into 10 classes based on their subfield, and node features are the average of GloVE (Pennington et al., 2014) embeddings all words in the article. This dataset comes with 20 canonical train/valid/test splits, which we use directly.
Amazon Computers, Amazon Photos" These graphs are from the Amazon co-purchase graph (McAuley et al., 2015) with nodes representing products and edges being between pairs of goods frequently purchased together. Products are classified into 10 (for Computers) and 8 (for Photos)
16

---

Published as a conference paper at ICLR 2022
classes based product category, and node features bag-of-words representation of a product's reviews. We use a random split of the nodes into (10/10/80%) train/validationntes nodes respectively as these datasets do not come with standard dataset split.
Coauthor CS, Coauthor Physics" These graphs are from the Microsoft Academic Graph (Sinha et al., 2015), with nodes representing authors and edges between authors who have co-authored a paper. Authors are classified into 15 (for CS) and (for Physics) classes based on the author's research field, and node features are a bag-of-words representation of the keywords of an author's s papers. We again use a random (10/10/80%) split for these datasets.
ogbn-arXiv: This is another citation network, where nodes represent CS papers on ar indexed by the Microsoft Academic Graph (Sinha al., 2015). In our experiments, we symmetrize this graph and thus there is an edge between any pair of nodes if one paper has cited the other. Papers are classified into 40 classes based on arXiv subject area. The node features are computed as the average word-embedding of all words in the paper, where the embeddings are computed using skip-gram gram model (Mikolov et al., 2013) over the entire corpus.
PPI 6 is a protein-protein interaction network (Zitnik & Leskovee, 2017; Hamilton et al., 2017). comprised of multiple (24) graphs each corresponding different human tissues. We the standard dataset split as 20 graphs for training, 2 for validation, and 2 for testing. Each node has 50 features computed from various biological properties. This is multilabel classification task, where each node can possess up to 121 labels.
F IMPLEMENTATION DETAILS
In all our experiments, we use the Adam V optimizer (Kingma & Ba, 2015; Gugger & Howard, 2018) with weight decay set 10-5, and all models initialized using Glorot initialization (Glorot & Bengio, 2010). The BGRL predictor used to predict the embedding of nodes across views is fixed to be Multilayer Perceptron (MLP) with a single hidden layer. The decay rate т controlling the rate of updates of the BGRL target parameters é is initialized to 0.99 and gradually increased to 1.0 over the course of training following a cosine schedule. Other model architecture and training details vary per dataset and are described further below. The augmentation hyperparameters Pf1,2 and per,a reported below.
Graph Convolutional Networks Formally, the GCN propagation rule (Kipf & Welling, 2017) for single layer as follows,
(X, = - AD AD- AxD,)..)).
(4)
where À = A is the adjacency matrix with self-loops, D is the degree matrix, is non-linearity such as ReLU, and W, is a learned weight matrix for the i'th layer.
Mean Pooling Rule Formally, the Mean Pooling (Hamilton et al., 2017) rule for a single layer is given by:
MP.(X,A) (D
(5)
As proposed by Veličković et al. (2019), our exact encoder in inductive experiments E is a 3-layer mmean-pooligg network with skip connections. We use layer size of 512 and PReLU (He et al., 2015) activation. Thus, we compute:
H. a (MP) A)) H2 = a (MP (H, + XW skip A))
(6)
(7)
8(X, A) (MP; (H2 H XW skip', A))
(8)
"httpa://a3 ws-east-2222 www.amaas..coommmmmmmmmm aww.anaaes.com/gglaaa///// httpc/////gg..aaaaaaat/ppppppppp
17

---

Published as a conference paper at ICLR 2022
Graph Attention Networks The GAT layer (Veličković et al., 2018) consists of a learned matrix W that transforms each node features. We then use self-attention to compute attention coeffi- cient for pair of nodes and as Giy a ( h,). The attention function a is computed as LeakyRel.Ug [Wh:]Whj)) where a is a learned matrix transforming a pair of concatenated at- tention queries into single scalar attention logit. The weight of the edge between nodes i and is computed as O'j = softmax, (Etz). We follow the architecture proposed by Veličković et al. (2018) including a 3-layer GAT model (with the first 2 layers consisting of 4 heads of size 256 each and the final layer size 512 with 6 output heads), ELU activation (Clevert et al., 2016), and skip-connections in intermediate layers.
Model architectures As described Section 4, we use GCN (Kipf & Welling, 2017) encoders in our experiments on the smaller transductive tasks, while on the inductive task of PPI we use MeanPooling encoders with residual connections. The BGRL predictor pa implemented as mutilayer perceptron (MLP). We also used stabilization techniques like batch normalization (loffe & Szegedy, 2015), layer normalization (Ba et al., 2016), and weight standardization (Qiao et al., 2019). The decay rate use for statistics in the batch normalization is fixed to 0.99. We PReLU activation (He et al., 2015) in all experiments except those using GAT encoder, where we use the ELU activation (Clevert et al., 2016). In all our models, each layer including the final layer, apply first the batch/layer normalization as applicable, and then the activation function. Table describes hyperparameter and architectural details for most of our experimental setups with BGRL. In addition to these standard settings, we perform additional experiments on the PPI dataset using GAT (Veličković al., 2018) model the encoder. When using the GAT encoder on PPI, we use attention layers the first two with 4 attention heads of size 256 each, and the final with attention heads of size 512, following a very similar model proposed by Veličković et (2018). We concatenate the attention head outputs for the first 2 layers, and use the mean for the final output. We also use the ELU activation (Clevert et al., 2016), and skip connections the intermediate attention layers, as suggested by Veličković et al. (2018).
Dataset
WikiCS
Am. Computers
Am. Photos
Physics
ogbn-arXiv
PPI
0.2
0.2
0.1
0.3
0.1
0.0
0.25
P5.2
0.1
0.1
0.2
0.4
0.4
0.0
0.00
Pe,1
0.2
0.5
0.4
0.3
0.4
0.6
0.30
Pe,2
0.3
0.4
0.1
0.1
0.25
Thuse
5 10
5 10-4
10-4
10
10
10
5 10
embedding size
256
128
256
256
128
256
512
hidden sizes
512
256
512
256
256, 256
512, 512
Pe hidden sizes
512
512
512
512
512
256
512
batch norm
Y
Y
Y
Y
Y
N
N
layer
N
N
N
N
Y
weight standard.
N
N
Table 8: Hyperparameter settings for unsupervised BGRL learning.
Augmentation parameters The hyperparameter settings for graph augmentations, as well as the sizes of the embeddings and hidden layers, very closely follow previous work (Zhu et al., 2020b;a) on all datasets with the exception of ogbn-arXiv. On this dataset, since there has not been prior work on applying self-supervised graph learning methods, we provide the hyperparameters found through small grid search.
Optimization settings We perform full-graph training at each gradient step all small-scale experiments, with the exception of experiments using GAT encoders on the PPI dataset. Here, due to memory constraints, we perform training with batch size of I graph. Since the PPI dataset consists of multiple smaller, disjoint subgraphs, we not have to perform any node subsampling at training time.
We use Glorot initialization (Glorot & Bengio, 2010) the Adam optimizer (Kingma & Ba, 2015; Gugger & Howard, 2018) with base learning rate Tuse and weight decay set to 10-5 The learning rate is annealed using cosine schedule over the course of learning of nootl total steps with an initial warmup period of Warmmup steps. Hence, the learning rate step i is computed as
18

---

Published as a conference paper at ICLR 2022
Viune
if Rwwarmup
A
Decnmy
Tji
(á- (d-Aoormpp): X
basc X
COS
x 0.5 if Awarmup S S Rooall
Phass Phaamop
We Rhotal to be 10,000 total steps and Twarmup to 1,000 warmup steps, with the exception of experiments on the GAT encoder that requires using batch size of graph the PPI dataset. In this case, we increase number of total steps to 20,000 and warmup to 2,000 steps.
The target network parameters & are initialized randomly from the same distribution of the online parameters / but with a different random seed. The decay parameter T is also updated using a cosine schedule starting from initial value of Thase 0.99 and is computed as
Thuse)
(coss
π
x
+
Thotal
These annealing schedules for both and follow the procedure used by Grill et al. (2020).
Frozen linear evaluation of embeddings In the linear evaluation protocol, the final evaluation done by fitting linear classifier on top of the frozen learned embeddings without flowing any gradients back to the encoder. For the smaller datasets of WikiCS, Amazon Computers/Photos, and Coauthor CS/Physics, we use an fz-regularized LogisticRegression classifier from Scikit-Learn (Pedregosa et al., 2011) using the 'liblinear' solver. We do a hyperparameter search over the regularization strength be between (2- 2-9 2-.....2% 29, 211).
For larger PPI and ogbn-arXiv datasets, where the liblinear solver takes too long to converge, we instead perform 100 steps of gradient descent using Adam with learning rate 0.01, with smaller hyperparameter search on the weight decay between {2-10, 2 2- ..... 26, 2 2
2
In cases, we normaiale the frozen learned embeddings over the entire graph before fitting the classifier on top.
G MAG240M EXPERIMENT DETAILS
Full implementation and experiment code has been open- sourced as part of the KDD Cup 2021. Key implementation details and hyperparameter descriptions are reproduced below.
OGB-LSC MAG240M Dataset: This is heterogeneous graph introduced for the KDD Cup 2021 (Hu et al., 2021), comprised of 121 million academic papers, 122 million authors, and 26 thousand institutions. Papers represented by 768- -f8-dimensional BERT embeddings (Devlin et al., 2019), and the task is to classify arXiv papers into one 153 categories, where I 1 the paper nodes are from arXiv.
Message Passing Neural Networks encoders: We use a bi-directional version of the standard MPNN (Gilmer al., 2017) architectures with message passing steps, hidden size of 256 each layer, with node and edge update functions represented by Multilayer Perceptrons (MLPs) with 2 hidden layers of size 512 each.
Node Neighborhood Sampling: Since we can no longer perform full-graph training, sample batch size of 1024 central nodes split across devices, and subsample fixed-size neighborhood for each. Specifically, we sample depth-2 neighborhood with different numbers of neighbors sampled per layer depending on the type (paper, author, institution) of each neighbor. We sample up to 80 papers and 20 authors for each paper; and 40 papers and 10 institutions per author.
Other hyperparamters: We use edge masking probability P. of 0.2 and feature masking probabil- ity py of 0.4 for each augmentation. We use a higher decay rate т, starting at 0.999 and decayed to 1.0 with cosine schedule. We use AdamW optimizer with weight decay of 10 and learning rate starting at 0.01 and annealed to over the course of learning with a warmup step equal to 10% the period of learning.
19

---

Published as a conference paper at ICLR 2022
H MODEL ABLATIONS ON MAG240M EXPERIMENTS
In our main experiments on the OGB-LSC MAG240M dataset, we focus on MPNN encoders to (i) achieve high accuracy this challenging dataset, and (ii) evaluate the stability of training these more complex models with the BGRL approach. In this section, we further experiment with simpler GCN encoders and evaluate the benefits of applying BGRL even on top of these weaker encoders.
We use 2-layer GCN encoder, with an embedding size of 128. All other settings such as learning rate schedules, augmentation parameters, etc. are unchanged.
In Figure 10, we see that both BGRL and GRACE improve over the performance of a fully supervised approach, with BGRL learning faster and more stably. Thus the effectiveness of BGRL even with weaker encoder architectures makes it more applicable in practice.
GCN Encoders MAG Dataset
0.730
0.725
0.720
Accuracy
0.715
0.710
BGRL semi-supervised
0.705
GRACE sepi-supe
Fully supervised
0.700
0
10000
20000
30000
40000
50000
Training Step
Figure 10: Performance on OGB-LSC MAG240M task, averaged over 3 seeds, using GCN encoders.
I VISUALIZATION OF SCALING BEHAVIOR
BGRL
10
Memory in GiB
0
10000
15000
20000
25000
30000
35000
Number nodes
Figure 11: Memory usage of BGRL and GRACE across 5 standard datasets.
In this section, we provide the information contained in Table as a scatterplot, to more easily visualize the different scaling properties of BGRL and GRACE. We see in Figure ll that the empirical scaling behavior matches the theoretical predictions in Section 3. Note that we do not show the memory usage of GRACE for the largest dataset, as it runs out of memory here, and we only visualize as function of the number nodes in the graph and ignore the number edges for the purposes of this visualization.
20

---

Published as a conference paper at ICLR 2022
J FROZEN LINEAR EVALUATION ON MAG240M
We briefly run experiments evaluating BGRL and GRACE under the frozen evaluation protocol using an MLP classification layer the MAG240M dataset. We see that although GRACE outperforms BGRL in this setting, both methods perform poorly. In particular, they underperform LabelProp (Zhu & Ghahramani, 2002; Hu al., 2021) a simple parameterless, graph-agnostic baseline. This, combined with our goal of pushing performance on the competition dataset, motivates our consideration of the remi-supervised learning setting.
Self-supervised learning on MAG
0.7
0.6
Accuracy
0.5
0.4
0.3
BGRL
0.2
GRACE
LabelProp
0.1
10000
20000
30000
40000
50000
Training Step
Figure 12: Performance on OGB-LSC MAG240M task, averaged over seeds, under frozen evalua-
tion protocol.
21


Reviews:
[{"review_id": "y6x8fWQ_CWQ", "reviewer": "Reviewer_CbdK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Strengths:\n\nThe developed method is technically sound. The paper is well-organized and easy to follow. The motivation of employing BYOL in tackling the scalability challenge is clearly stated and the empirical studies are sufficient to show the efficacy of BGRL in both producing high quality node representations and scaling to extremely large graphs. I appreciate the empirical results provided by the paper, which is useful to the graph representation learning community. The implementation specifications are recorded in detail. Other contributions are summarized as above.\n\nWeaknesses:\n\n(1) My major concern is the novelty of the paper. Although dropping projection network makes differences in the model architecture between BGRL and the original BYOL, its technical contribution is incremental. Besides, such technique is already discussed in SelfGNN [1].  \n\n(2)  In experiments on large graphs, it would increase the significance if \n\n* an ablation study on the model choice of encoder is provided,\n* more recent base model(s) with O(n) complexity in computing objective functions (e.g., MVGRL [2]) are compared against.\n\n\n\nReferences\n\n[1] Zekarias T. Kefato and Sarunas Girdzijauskas. Self-supervised graph neural networks without explicit\nnegative sampling. CoRR, abs/2103.14958, 2021\n\n[2] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on\ngraphs. In International Conference on Machine Learning, 2020.", "summary_of_the_paper": "The paper proposes a self-supervised graph representation learning algorithm named BGRL. BGRL employs similar architecture & training mechanism with BYOL and necessary adjustments (e.g., the augmentation methods, dropping the prejector module) to adapt to the characteristics of graph datasets. Given the nature of BYOL-based methods that negative samples are not used during training, BGRL scales only to O(n) when computing the objective function, which essentially breaks the computation limit incurred by the quadratically complex objective function adopted by SimCLR-based models (e.g., GRACE), hence makes the proposed model applicable to large graphs.\n\nThe major contributions of the paper are summarized as follows:\n\n(1) The paper highlights and empirically verifies BYOL's advantages in not only boosting task performance but also enhancing model scalability, the second aspect is important but ignored by previous / concurrent BYOL-based methods.\n\n(2) The paper tests the effect of introducing label supervision to the BYOL-based scheme on learning node representations for large graphs, which is not studied in previous / concurrent BYOL-based methods.\n\n(3) The paper evaluated BGRL against other base models on various benchmarks, which not only provides multiple aspects of BGRL's advantages, but also enriches the baselines of unsupervised graph representation learning, especially on large graphs.", "summary_of_the_review": "In summary, although there are empirical contributions in the proposed method, the paper appears only to apply the well-developed BYOL scheme to graph representation learning tasks. The technical contribution is sort of incremental.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ul-TEI5sw5", "reviewer": "Reviewer_GsyJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "# Strengths\n+ The proposed method is easy to follow and the paper is well-organized.\n+ The BGRL model is simple and effective.\n+ Extensive experiments demonstrate the effectiveness and efficiency.\n\n# Weaknesses\n- The novelty of this work is a bit limited as this is a simple adaptation of BYOL on graph-structured data.\n", "summary_of_the_paper": "This paper presents a novel graph contrastive learning model with bootstrapping latent objectives. Extensive experiments demonstrate the effectiveness of the proposed BGRL method.", "summary_of_the_review": "It feels to me that no obvious weaknesses can be spotted. The BGRL method is easy to follow, is simple and also powerful, and the authors did an extensive set of experiments to verify the effectiveness and also efficiency of BGRL.\n\n# Suggestions\n* In Table 5, the memory consumption for both GRACE and BGRL should be given so that readers could understand how much memory is needed for sufficient number of negative samples to achieve similar performance as with BGRL.\n* I believe some graph-level evaluations may further expand the applicability of BGRL. In this case, how to choose appropriate representations (e.g., graph- or node-level embeddings or some sort of context representations) for both branches is important.\n* As the authors point out, theoretical analysis on the learning dynamics of the online and the offline branch [1] may be helpful for understanding the superior performance of BGRL.\n\n[1] Y. Tian, X. Chen, and S. Ganguli, Understanding Self-Supervised Learning Dynamics without Contrastive Pairs, in ICML, 2021.\n", "strength_and_weaknesses": "", "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": "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": "XBjTCPkN4yW", "reviewer": "Reviewer_8P5B", "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": "# Strengths\n\n* Different from contrastive methods, the cost of computing the loss for BRGL exactly scales only linearly with graph size. \n* An extensive suite of experiments shows BRGL achieves SOTA while avoiding the performance-memory tradeoff of contrastive methods.\n* BRGL was validated in practice at the KDD cup 2021.\n\n# Weaknesses\n* BRGL is a direct analogue of BYOL for graphs (but without a projector network). Therefore, the novelty here is relatively limited.\n* The authors provide no intuition on why their method works.\n\n# Observations\n*  It might help to show Table 1 as scatter plots nodes/edges versus memory. This way, we could ‘visualize’ the asymptotic difference between GRACE and BRGL.\n* From the description in Section 4.2, GRACE-SUBSAMPLING scales linearly on $k$. If this is the case, $k=2$ asymptotically implies the same complexity as $k=2048$.  ", "summary_of_the_paper": "This paper proposes BRGL, a method for graph representation learning based on ‘bootstrapping’ (in the same sense BYOL is). Different from the prior art, which mainly relies on contrastive learning, BRGL naturally scales linearly with graph size.  An extensive suite of experiments shows that BRGL scales better than previous works while yielding state-of-the-art (SOTA) performance in node classification. ", "summary_of_the_review": "The paper shows good results, but i) the novelty is relatively limited; and ii) there is no intuition on why the method works. Therefore, I believe the paper is just below borderline.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "CrPFve9h9V7", "reviewer": "Reviewer_8wKC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "The paper can be evaluated mainly from two perspectives:\n\n1. The novelty of the method and the conceptual contribution is extremely limited since the proposed model is a pretty straightforward application of the BYOL [1] model on graph data.  The difference of not having a projection head cannot be deemed as a contribution or novelty, since the reason is the low dimension of the node features in the graph datasets, as mentioned by the authors.\n\n2. The experimental contribution is very solid. The model is evaluated on multiple large datasets and is also tested via the KDD CUP competition and promising results are obtained. This would be a significant contribution to the community and would facilitate future researches in this direction.\n\nBesides the two main points raised above, the method section could be further improved by including explanations on the motivation of the designs, which is especially important for readers who are not familiar with BYOL. Currently, the paper just described the operations of the model without explanation on the operations are designed in this way. Explanations from the following points may be considered: 1. What is the difference between the online and the target branch. 2. What makes the target branch become a target for the online branch? 3. Why is the target branch updated through EMA? 4. What objective does the target branch (\\phi) follows, as mentioned in the paragraph under Eq(3), in page 3. \n\n[1] Grill, Jean-Bastien, et al. \"Bootstrap your own latent: A new approach to self-supervised learning.\" arXiv preprint arXiv:2006.07733 (2020).", "summary_of_the_paper": "This paper introduces Bootstrapped Graph Latents (BGRL) to learn graph representation by predicting alternative augmentations of the input.  The experiment results on a wide range of datasets exhibit appealing performance.", "summary_of_the_review": "Considering the empirical contribution of the paper, I am inclined to accept this paper.\n", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: To perform self-supervised graph representation learning that is scalable to large graphs, the authors propose Bootstrapped Graph Latents (BGRL) that learns its graph representation by predicting alternative augmentations of the input, avoiding the need to construct negative examples. The weakness of the paper lies in its novelty, as it can be considered as a direct adaptation of the BYOL method, whose success has been demonstrated on self-supervised visual representation learning, to learn graph node representations. While the novelty is limited, the paper has shown how to appropriately apply BYOL to graph representation learning, achieving state-of-the-art results on graph node representation learning on large-scale graphs. The overall assessment of the reviewers is that the empirical significance of the paper outweighs its shortcoming in novelty. The AC agrees with this assessment and hence recommends acceptance.
Decision: Accept (Poster)