Localized Graph Contrastive Learning
Authors: Hengrui Zhang
Qitian Wu
Yu Wang
Shaofeng Zhang
Junchi Yan
Philip S. Yu
Venue: Submitted to ICLR 2023 (2023)

Abstract: Contrastive learning methods based on InfoNCE loss are popular in node representation learning tasks on graph-structured data. However, its reliance on data augmentation and its quadratic computational complexity might lead to inconsistency and inefficiency problems. To mitigate these limitations, in this paper, we introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL in short). Local-GCL consists of two key designs: 1) We fabricate the positive examples for each node directly using its first-order neighbors, which frees our method from the reliance on carefully-designed graph augmentations; 2) To improve the efficiency of contrastive learning on graphs, we devise a kernelized contrastive loss, which could be approximately computed in linear time and space complexity with respect to the graph size. We provide theoretical analysis to justify the effectiveness and rationality of the proposed methods. Experiments on various datasets with different scales and properties demonstrate that in spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.

Under review as a conference paper at ICLR 2023
LOCALIZED GRAPH CONTRASTIVE LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Contrastive learning methods based InfoNCE loss are popular in node repre- sentation learning tasks on graph-structured data. However, its reliance on data augmentation and its quadratic computational complexity might lead incon- sistency and inefficiency problems. To mitigate these limitations, in this paper, we introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (LOCAL--GC) in short). LOCAL-
consists of two key designs: 1) We fabricate the positive examples for each node directly using its first- order neighbors, which frees our method from the reliance on carefully-desinned graph augmentations; 2) To improve the efficiency of contrastive learning on graphs, we devise kernlizedd contrastive loss, which could be approximately computed in linear time and space complexity with respect to the graph size. We provide theoretical analysis to justify the effectiveness and rationality of the proposed methods. Experiments on various datasets with different scales and properties demonstrate that in spite of its simplicity, LOCAL-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
INTRODUCTION
Self-supervised learning has achieved remarkable success in learning informative representations without using costly handcrafted labels (van den Oord et al., 2018; Devlin et al., 2019; Banville et al., 2021; He et al., 2020; Chen et al., 2020; Grill et al., 2020; Zhang et al., 2021; Gao et al., 2021). Among current supf-supe learning paradigms, InfoNCE loss (van den Oord et al., 2018) based multi-view contrastive methods (He et al., 2020; Chen et al., 2020; Gao et al., 2021) are recognized as the most widely adopted ones, due to their solid theoretical foundations and strong empirical results. Generally, contrastive learning aims at maximizing the agreement between the latent representations of two views (e.g. through data augmentation) from the same input, which essentially maximizes the mutual information between the two representations (Poole et al., 2019). Inheriting the spirits of contrastive learning on vision tasks, similar methods have been developed to deal with graphs and bring up promising results common node-level classification benchmarks (Velickovic et al., 2019; Hassani & Ahmadi, 2020; Zhu et al., 2020b; 2021).
The challenge, however, is that prevailing contrastive learning methods rely predefined aug- mentation techniques for generating positive pairs as informative training supervision. Unlike grid-structured data (e.g., images sequences), is non-trivial to define well-posed augmentation approaches for graph-structured data Zhu et al. (2021); Zhang et al. (2021). The common practice adopted by current methods resorts random perturbation tures (You et al.. 2020), which might unexpectedly violate the underlying data generation and change the semantic information (Lee et al., 2021). Such an issue plays bottleneck limiting the practical efficacy of contrastive methods on graphs. Apart from this, the InfoNCE loss function computes all-pair distance for in-batch nodes as negative pairs for contrasting signals (Zhu al., 2020b; 2021) 1), which induces quadratic memory and time complexity with respect to the batch size. Given that the model is preferred to be trained in a full-graph manner (i.c., batch size = graph size) since the graph structure information might be partially lost through mini-bater partition, such nature heavily constrains contrastive methods for scaling to large graphs.
input node features and graph struc-
Some recent works seek regative-sample-ffe asymmetric structures (Thakoor et al., 2021) or feature-level decorrelation objectives (Zhang et al., 2021). However, these methods either lack enough theoretical justification (Thakoor et al., 2021) or
methods to resolve the scalability issue by harnessing

---

Under review as a conference paper at ICLR 2023
necessitate strong assumptions the data distributions (Zhang et al., 2021). Moreover, they still require data augmentations to generate two views of the imput graph, albeit non con-contrastive and free from negative sampling. Some other works construct positive examples using the target's k-nearest- neighbors (kNN) in the latent space (Dwibedi et al., 2021; Koohpayegani et al., 2021; ; Lee et al., 2021). Nonetheless, the computation of nearest neighbors could be cumbersome, time-consuming, and, therefore hard to scale.
To cope with the dilemmas above, in this paper we introduce Localized Graph Contrastive Learning (LOCAL-GCL in abbreviation), a light and augmentation-free contrastive model for self-supervised node-level representation learning on graphs. LOCAL-GCI benefits from two key designs. First, it does not rely on data augmentation to construct positive pairs. Instead, inspired by the graph homophiliy theory (McPherson et al., 2001), ), it directly treats the first-order neighboring nodes as the positive examples of the target node. This not only increases the number of positive examples for each node but also helps our model get rid of complicated data augmentations. Besides, the computation of positive pairs can be performed in linear time and space complexity w.r.t the graph size, bringing no additional cost for the model. Second, to deal with the quadratic complexity curse of contrastive loss (i.e., InfoNCE loss (van den Oord et al., 2018)) 8)), we propose surrogate loss function in place of the negative loss term in the vanilla InfoNCE loss, which could be efficiently and accurately approximated within linear time and space complexity (Rahimi et al., 2007; Liu et al., 2020; Yu et al., 2). Such a design greatly improves the efficiency of our model.
Presented Work.
We evaluate the proposed methods seven public node classification benchmarks with various scales. The empirical results demonstrate that though not using any graph augmentations, our method achieves staeeoffttheaa performance on six of seven datasets. On the challenging Ogbn Arxiv dataset, our method can also give a competitive performance with a much training speed compared with other scalable models. Experiments on three heterophily graphs demonstrate that besides homophily graphs, LOCAL-GCL can also perform well on graphs with low homophily ratios.
We summarize the highlights of this paper as follows:
1) We introduce LOCAL-GCL, a simple model for contrastive learning on graphs, where the positive example is fabricated using the first-order neighborhood of each node. This successfully frees node-level contrastive learning methods from unjustified graph augmentations.
2) To overcome the quadratic complexity curse of contrastive learning, we propose a kernelized contrastive loss computation that can precisely approximate the original loss function within linear complexity w.r.t. graph size. This significantly reduces the training time and memory cost of contrastive learning on large graphs.
3) Experimental results show that without data augmentation and other cumbersome designs LOCAL- GCL achieves quite competitive results on variety of graphs of different scales and properties. Furthermore, LOCAL- demonstrates a better balance of model performance and efficiency than other self- supervied methods.
BACKGROUND AND RELATED WORKS
2.1 CONTRASTIVE REPRESENTATION LEARNING
Inspired by the great success of contrastive methods in learning image representations (van den Oord al., 2018; Hjelm et al.. 2019: Tian et al., 2020; He al., 2020; Chen et al., 2020), recent endeavors develop similar strategies for node-level tasks in graph domain (Velickovic et al., 2019; Hassani & Ahmadi, 2020; Zhu et al., 2020b; 2021). Among graph contrastive learning methods, the most popular methods should be those based on the InfoNCE loss (van den Oord et al., 2018 8) due to their simple concepts and better empirical performance. InfoNCE-based graph contrastive learning methods, including GRACE (Zhu et al., 2020b) and GCA (Zhu et al., 2021) aim to maximize the similarity of positive node-node (or graph-graph pairs (e.g., two views generated via data augmentation) and minimize the similarity of negative ones (e.g., other nodes/graphs within the current batch). However, they require well-designated data augmentations that could positively inform downstream tasks (Tsai et al., 2021). The quadratic complexity also limits their applications to larger batch sizes/datasets.
2

---

Under review as a conference paper at ICLR 2023
2.2 AUGMENTATION EEEEETIIOO--REEEEEEEE SELF-SUPERVISED LEARNING ON GRAPHS
Besides graph contrastive learning (Zhu et al., 2020b; 2021) and the similar two-branched mod- els (Thakoor et al., 2021; Zhang al., 2021) that use graph augmentations to create positive pairs, there is another line of work exploring the rich structure information in the graph to create self- supervised signals. Graph AutoEncoders (Kipf & Welling, 2016), for example, learn node embeddings unsupervisedly through reconstructing the adjacency matrix, while GMI (Peng et al., 2020) maxi- mizes the mutual information of both features and edges between inputs and outputs. Inspired by the success of contrastive learning, some recent work explores constructing positive pairs using reliable graph information instead of data augmentations. For example, SUGRL (Mo et al., 2022) employs two encoder models: one is GCN, and the another is an MIP, to generate two sets of node embedding from different sources. Then for each node, the positive pair can be constructed using its GCN output and MLP output. AFGRL (Lee et al., 2021) and AF-GCL (Wang et al., 2022) treat nodes in the target node's multi-hop neighborhood as candidate positive examples and use well-designed similarity measures select the most similar nodes as positive examples. LOCAI-GCI. by contrast, treats all neighbors equally without discrimination. This not only simplifies the model design but also offers theoretical guarantce for the effectiveness of the proposed model. Empirical results also demonstrate that our method can achieve better performance than them.
2.3 RANDOM FOURIER FEATURES
Though InfoNCE-loss-basee based methods are successful in self-suuervised node representation learning, their quadratic time and memory complexity with respect to the graph size prevent them from being applied to graphs with tens of thousands of nodes. This paper seeks to address this issue by optimizing a surrogate loss function with Random Fourier Features (RFF or Random Features in short) (Rahimi al., 2007; Liu et al., 2020). RFF an effective technique for enhancing the scalability of kernel methods such as SVM, ridge regression (Avron et al., 2017) and independence test (Zhang et al., 2018; Li et al., 2021). Also, recently, RFF has been adopted to develop linear Transformers by approximating the softmax attention (Choromanski et al., 2020; Peng et al., 2021). Given d- dimensional vectors x and y and a shift-invarian kernel nc(-), RFF constructs an explicit mapping th: Rd + RR,, such that k(x:, y) (x)) (yy), which reduces the quadratic computation cost of the kernel matrix to a linear one w.r.t data size. Generally, given a positive definite shift-invariant kernel <(æ; y) = f(x y), the Fourier transform p of kernel is p(w) 2 ʃ e jw A ((A)dA, where
A = x Then we could draw D i..dd samples W1, .DD E Rdd from and vx(x)) is given by:
(x)) [cos(w]] x), ... cos(w sin(w] w),... sin sin(w
(I)
VD
Let W == [w].... wp) d be linear transformation matrix, one may realize that the computation Eq. entails computing W x. Specifically, when x(-) a standard Gaussian kernel (a.k.a., RBF kernel), each entry of W can be directly sampled from a standard Gaussian distribution. The improved variants of RFF mainly concentrate on different ways to build the transformation matrix W, as to further reduce the computational cost (Le et al., 2013) lower the approximation variance (Yu et al., 2016).
CONTRASTIVE LEARNING ON GRAPHS WITH INFONCE Loss
The InfoNCE (van den Oord et al., 2018) loss has been employed in various areas and has shown great power in learning informative representations in a self-supervised manner. Given the embedding of target data point z;, together with one positive embedding 2," and set of negative embeddings {2, 1-1 the InfoNCE loss aims at discriminating the positive pair (zi, x,t) from the negative pairs {(z,, 2, M via the following contrastive objective function:
exp(f(z,, 2/1/T)
(In =-log log
(2)
M-1
exp(f x x /)77) + Σ xxp(f(xt22))
where . is similarity measure, usually implemented as the simple dot product f(x y) x y (He al., 2020; Chen et al., 2020), and 7 is the temperature hyperparameter. Note that 2;, 2,-
3

---

Under review as a conference paper at ICLR 2023
and a; are all 22 normalized to have unit norm, i.e., ||2.1|2 1. In the context of node-level contrastive learning, each &, denotes the embedding of node i, which is the output of an encoder model which takes the node feature e; and the graph structure imput. As demonstrated in Eq. 2, the InfoNCE loss is composed of two terms: 1) the numerator term on the positive pair that maximizes the similarity between positive pairs (positive term); 2) the denominator term M - negative pairs and one positive pair (for simplicity, we call all the M terms in the denominator "negative terms") that encourages the embeddings of negative pairs to be distinguished (negative term). Like the study of contrastive learning on vision and language, recent node-level contrastive learning research mainly focuses on how to construct/select more informative positive and negative examples.
The most popular method for constructing positive examples on graphs is through data augmentation. For example, MVGRL. (Hassani & Ahmadi, 2020) uses graph diffusion to generate fixed, augmented view of the studied graph. GCC (Qiu et al., 2020) resorts to random walk to sample subgraphs of the anchored node as positive examples. GRACE (Zhu et al., 2020b) and GCA (Zhu et al., 2021) employ random graph augmentation-featte the input graph before every training step. However, recent studies have shown that existing graph augmentations might unexpectedly change lose the semantic information (Lee et al., 2021; Wang et al., 2022) of the target node, hurting the learned representation. This motivates us to investigate the possibility of constructing positive examples without using random, ambiguous graph augmentations.
masking and edge removing to generate two views of
Compared with the construction of positive examples, negative examples are much easier to select. A common adopted and effective practice is to use all other nodes in the graph as negative examples (Zhu et al., 2020b; 2021; Zhang et al., 2021). ). However, the computation of the negative term of InfoNCE has ((V/dd) time complexity and ((V))) memory complexity, where [V] is the number of nodes and d is the embedding dimension. Note that the real-world graphs are usually very large, Eq. 2 can hardly be used in a full-graph training manner. One plausible remedy is to use down-sampling to zoom in on fraction of negative samples for once feedforward computation. However, theoretical analysis demonstrates InfoNCE loss benefits from a large number of negative examples (Poole et al., 2019), and empirical observations show that reducing the number of negative examples leads to worse performance on downstream tasks (Thakoor et al., 2021) (also see our experiments in Sec. 5,4). As result, it would be promising to devise efficient and scalable computation method for the contrastive loss above, without reducing the number of negative examples.
In the next section, we propose Localized Graph Contrastive Learning with Kernel Approximation (LoCAL-GCL in short) to mitigate the above issues. LOCAL- distinguishes itself from previous contrastive methods in the following two aspects: 1) instead of constructing positive examples for target nodes using data augmentations or other techniques, we directly treat all the first-order neighbors of each target node its positive examples; 2) we introduce Gaussian kernelized surrogate loss function, which could be accurately and efficiently approximated with linear time and memory complexity in place of the vanilla InfoNCE loss.
4 METHODOLOGY
4.1 ANCHORING NODE CONTRASTIVE LEARNING ON TOPOLOGY
Contrastive learning is firstly investigated in unsupervised visual representation learning where the data points are i.i.d. sampled from the data distribution, and the ground-truth labels are unknown during training. As a result, we have to employ well-defined augmentations create two views of the same image that are likely to share the same ground-truth label. Different from images or texts where each input data is often assumed i.i.d. generated from a certain distribution and there is no explicit prior knowledge about the relationship among different instances, in the graph domain, nodes within the same graph are highly inter-dependent given the input graph structure. That is, the graph structure could provide additional information that reflects the affinity of node pairs. Furthermore, in network (graph) science, it is widely acknowledged that many real-world graphs (such as social networks (Wu et al., 2019; McPherson et al., 2001) and citation networks (Ciotti et al., 2016)) conform with the homophily phenomenon that similar nodes may be more likely to attach than dissimilar ones (Zhu al., 2003; McPherson et al., 2001). Such a phenomenon also inspires the core principle followed by the designs of modern graph neural networks, i.e., connected nodes should have similar embeddings in the latent space (Zhu et al., 2020a). This motivates us directly treats all the first-order neighboring
4

---

Under review as a conference paper at ICLR 2023
nodes of the target node positive examples. Formally, the loss for the positive pairs of node can be written as
pos (1)
log Σ exp(2[2z/+1//WW)))
JEA(()
For the negative term, we can directly all nodes in the graph as negative examples. Then the loss for the negative pairs of node can formulated as:
Lneg (i)
log Σ
exp(2z #x/T).
KEV
The overall loss function is simply the sum of poss and Lrnge then averaged over all nodes:
Σ exp(z, 2//T)//((i)
1
JEN(
Li.ocal-Gee GCT,
log
(5)
V
exp(z; 2x/T)
Then we'd like to provide a theoretical analysis of the effectiveness constructing positive examples directly with the first-order neighbors. First, let's introduce some notations that will be used in the following analysis. We denote graph by G = (V, where V is the node st and & is the edge set. The adjacency matrix and degree matrix denoted by A and D, respectively. Let Á = D-11/2 AP-AD111 1/2 be the symmetric normalized adjacency matrix, and L I Á be the symmetric normalized graph Laplacian matrix. Denote the eigenvalues of L in Zn ascending order by { Finally we denote the node embedding matrix Z { IR Vixd and the one-hot label matrix by Y = (yrb E M Without loss of generality we assume d < [V].
We then give formal definition of graph homophily ratio d;
Definition 1. (Graph Homophily Ratio) For graph G E) with adjacency matrix A, its homophily ratio & is defined as the probability that two connected nodes share the same label:
Σijev Aig 1 yjl
Eisev Agj [ =ys
(6)
Eis
1l
With the conclusions in Balestriero & LeCun (2022) and HaoChen al. (2021), which build connections between contrastive loss and spectral method, the following theorem guarantees the linear classification error of the embeddings learned from LOCAL-GCL:
Theorem 1. Let Z" be the global minimizer of Eq. 5, then for any labeling function V - R with graph homophily dh there exists a linear classifier B E Rdxxe with norm | S 1/(1 Aa) such that
Eiev [10(0) B
2111
1- Φ
Ad+1
See proof in Appendix A.1. Theorem demonstrates that the linear classification accuracy of the learned embeddings through LOCAL-GCL is bounded by the homophily ratio & and the d+ smallest eigenvalue A4+1. Specifically, the larger the homophily ratio, the smaller the prediction error. Besides, Eq. indicates that a larger embedding dimension can lead to better classification accuracy, which is also validated empirically in Sec.
4.2 FAST AND EFFICIENT APPROXIMATION FOR THE NEGATIVE Loss
We next probe into how to reduce the computation complexity of the negative loss term Lneg Σ (i), for which the |v|2 pair-wise similarities can be efficiently and precisely approximated KEV
with efficient computation methods for kernel functions (Rahimi et al., 2007; Liu et al., 2020).
pisr-wise We notice that the pair- wise similarity (in dot drodput format) in Eq. 4 is essentially Gaussian kemel function, i.e.,
|| 1 = e * exp( ||,, 2,|1 c. x " 2ki VT), (8)
exp(2] 23/T) = expl
2r
2r
5

---

Under review as a conference paper at ICLR 2023
where xO (z,, zx3 VT) is the Gaussian kernel function with bandwidth VF. This motivates to seek for projection function ( - IRP) such that x0 y: vF) se +xxx) (z)) Then are able to use a surrogate negative loss function as a remedy of the previous one:
Lney
1 V
log
(h,) (())))) (T.s)T((h))))
log
T (h.))
Σ (b(h))
(9)
V
jEV
EVV
jEV
Once we obtain all the projected vectors (vb( the summation term Σj (h2, in Eq. could be calculated within D)) in advance (where D is the dimension of projected vectors). In addition the O(VID) cost for computing the loss, the overall computational cost will be ((V) + D) = O(V)), which is linear to the number of nodes. Then we discuss how to formulate the projection function (b)) below.
Linear-Order Projection The theory of Random Fourier Features (Rahimi et al., 2007) introduced in See. 2.3 demonstrates that a Gaussian kernel function xe y: vT) could be unbiasedly estimated with (a)) (by), and the projection function (x(x) is defined as follows:
(xx) [cos( W TyTa ()) sin W T x)]
[wo (o)u[T))...)>>). cos ax),
sin (x))
w),... si)s:...,,ss((() T
VD
VD
(10)
where W = [ .... WbI, and each w, is sampled from the Gaussian distribution p(w) = NO r.). D the number of total samples. Usually, the larger the sampling number D is, the more accurate the approximation will be:
Theorem 2. Let [ be i.i.d samples from Gaussian distribution N(0, rI), and (xx) is given by Eq. 10, then with probability at least 1 E, the approximation error A = (b,)))) (b,)) (h h2)
will be bounded by O 1-exp(-4/77
v2DE
Theorem 2 suggests that the Gaussian kernel function could he accurately approximated with Random Fourier Features as long as we sample enough number of linear transformation vectors w (i.e., D should be large enough). Note that the computation of linear projection W h, (i = 1 E V) requires additional ((V)D time, A large number of the projection dimension makes the computation of Eq. 9 still expensive for high- sigh--imensional data.
Log-Order Projection To handle the above issues, we resort to Structured Orthogonal Random Features (SORF) (Yu al., 2016), another Random Feature technique that imposes structural and orthogonality on the linear transformation matrix W. Different from the vanilla RFF which directly samples linear transformation vectors w form normal distribution to construct the transformation matrix W. [w]... wh] E Idd SORF assumes D d and constructs a structured or- thogonal transformation matrix through the continued product of a series of structured matrixes Wsorf de H HD, D3, where D; E Rdxd, i = 1, 2, 3, are diagonal "sign-flipping" matri- ces, with each diagonal entry sampled from the Rademacher distribution, and H E Rddd is the matrix. By this definition, the projected dimension is restricted to d,
normalized Walsh-Hadaman but could be extended to any dimension by concatenating multiple independently generated features or simply using a proportion of them. The stand-out merit of SORF is that it can be computed in ((V) D log d) time using fast Hadamard transformation (Fino & Algazi, 1976), and hardly requires extra memory cost using in-place operations (Yu et al., 2016). This further reduces its complexity and endows our method with desirable scalability to not only larger dataset sizes but also larger embedding dimensions. If not specified, in the following section, the term LOCAL-GCL denotes our method equipped with SORF to approximate the negative loss.
EXPERIMENTS
We conduct experiments to evaluate the proposed method by answering the following questions:
RQI:
How does LOCAL-GCL perform compared with other self-supervised learning methods on graphs with different properties?

---

Under review as a conference paper at ICLR 2023
How do the specific designs of LOCAL-GCL, such as the embedding dimension and projection dimension, affect its performance?
RQ2:
What's the empirical memory and time consumption of LOCAL-GCL compared with prior works? Is LOCAL- able to scale to real- large-scale scale graphs with satisfying performance?
RQ3:
5.1 EXPERIMENTAL SETUPS
Datasets. We evaluate LOCAL-GCL on various datasets with different scales and properties. Fol- lowing prior works (Zhu et al., 2020b; Zhang et al., 2021) self-supervised node representation learning, we adopt the 7 common small-scale benchmarking graphs: Cora, Citeseer, r, Pubmed, Amazon-Computer Amazon-Photo, Coauthor-CS, and Coauthor-Physi ate the performance and scalability of LOCAL-GCL on larger graphs, we also adopt Ogbn-Arxiv with about 170k nodes, on which a lot of methods fail scale due memory issues. Furthermore, we adopt three widely used heterophily graphs, Chame leon, Squirre gquirrel, and Actor to evaluate the generalization ability of LOCAL- ACLL on graphs where the graph homophily assumption does not hold. The detailed introduction and statistics of these datasets are presented in Appendix C.I
To evalu-
Baselines. We consider representative prior self-supervised models for comparison. We classify previous methods into two types: 1) Augmeentation-basse, which uses data augmentations to generate positive or negative pairs. 2) Augmentation-free form of data augmentation to create self-supervised signals. For augmentation-
which uses other information rather than any baselines, consider DGI (Velickovic et al., 2019), MVGRL (Hassani & Ahmadi, 2020), GRACE (Zhu et al., 2020b), GCA Zhu al. (2021), BGRL (Thakoor al., 2021) and CCA-SSG (Zhang al., 2021). For augmentation-fiee free baselines, we consider GMI (Peng et al., 2020), SUGRL (Mo et al., 2022), AFGRL (Lee al., 2021), AF-GCL (Wang et al., 2022).
Evaluation Protocols. We follow the linear evaluation scheme in previous works (Velickovic et al., 2019; Hassani & Ahmadi, 2020; Zhu et al., 2021; Zhang et al., 2021): For each dataset, i) we first train the model on all the nodes in graph without supervision by optimizing the objective in Eq. 5; ii) after the training ends, we freeze the parameters of the encoder and obtain all the nodes' embeddings, which are subsequently fed into a linear classifier (i.e., logistic regression model) to generate a predicted label for each node. In the second stage, only nodes in the training set are used for training the classifier, and we report the classification accuracy on testing nodes.
Implementation Details. The model is implemented with PyTorch and DGL (Wang et al., 2019). All experiments are conducted on an NVIDIA V100 GPU with 16 GB memory unless specified. We adopt st ructure-net! to do fast Hadamadd transformation, which enables much faster forward and backward computation with CUDA accelerations. We use the Adam optimizer (Kingma & Ba, 2015) for both self-supervised pretraining training and linear evaluation using logistic regression. Following previous works (Zhu et al., 2021; Zhang et al., 2021; Thakoor et al., 2021; Wang et al., zmazzoCCmpptee Computer, Amazon-Photts and use the public recommended split for the remaining datasets. For
2022), we the random 1:1:8 split for Ama zon
Coauthor-CS
and Mraazon-Compute each experiment, we report the average test accuracy with the standard deviation over 20 random initialization. If not specified, we use two-layer GCN model as the encoder generate node embeddings. More detailed hyperparameter settings for each dataset can be found in Appendix C.2
5.2 NUMERICAL RESULTS
Results on common graphs. We first report the results of node classification tasks on small-scale citation networks and social networks in Table 1. We see that although not relying on data aug- mentations or other complicated operations to create self-superrised signal, LOCAL-GCL performs competitively with our self-supervised baselines, achieving state-of-the-arr performance in 6 out of datasets. It is worth noting that the competitive InfoNCE-loss based contrastive methods GRACE and GCA suffer from OOM on Coauthor Sacoorr-Physss Physice cs datasets due the ((V(22) space complexity. while LOCAL-GCL can avoid such an issue thanks to the linear approximation of the negative loss.
phttps:/Al / thub. com wwt.c//////aaae www.m//aaaeeeeereeeo..o.o st wuctured-neeeee
7

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison of self-supervised methods on benchmarking graphs. We group each method according to whether it relies on graph augmentation.
Methods
Cora
Citeseer
Fubmed
Computer
Photo
Physics
DGI
82.3+0066
71.8=0.7
76.8+:0.6
83.95+00.47
91.61+0.22
92.15+00.3
94.51=0.52
Aug bas-basdd
MVGRL.
83.5++0.4
73.3=0.5
80.1++0.7
87.52++0.11
91.74-t0.07
92.11+0.112
95.33=0.03
GRACE
81.9:0.4
71.2=0.5
80.6::0.
86.25::0.55
92.15+0.24
92.93=0001
OOM"
GCA
82.3+0.4
72.1=0.4
80.7+00.5
87.85+00.1
92.49+00.09
93.10=00.01
OOM
BGRL
82.7++0.6
71.1=0.8
79.6+-0.5
89.69++0.37
93.07++0.28
92.59++.117
95.48=00.8
CCA-SSG
84.2:10.4
73.1
81.6110.4
88.74:10.28
93.14:10.14
93.31-10,22
05.0
GMI
82.4+0.6
71.7=0.2
79.3+1100
84.22+0.52
90.73+0.24
OOM
OOM
sig-froc
SUGRL
83.410.5
73.0=0.4
819900.3
88.9320.21
93.07:10.15
92.83-10,23
95.38=0.11
AFGRL
81.3+0.2
68.7=0.3
80.6+00.
89.88+0.33
93.22++0.28
93.27=0.17
OOM
AF-GCL
83.2+0.22
72.0=0.4
79.1+-0.8
89.68+0.19 88.81-+0.37
92.49+0.31
91.92:+0.10 94.90
95.1220.155
LOCAL-GCII 84.5+00.4
7.46:0.4
82.1+-0.5
93.25++0.40
96.33-0.13
OOM indicates out-of- on an NVIDIA-V100 GPU of 16G memory.
Table 2:
Performance Ogbn-Arxiv
dataset. As recommended, we report both Table 3: Performance on Heterophily graphs. Re-
the validation accuracy and test accuracy.
sults of baseline methods are taken from Wang et al. (2022)
Methods
Validation
Test
Methods
Chame leon
Squi rrel
Actor
DGI
71.21+0.23
70.32++0.25
GMI
OOM
OOM
60.27+0.70
42.22400.3
28.30::0.76
MVGRL
OOM
OOM
GMI
52.81110.3
35.25:11.21
27.28:10.87
GRACE
OOM
OOM
MVGRL.
53.81+
38.75+
32.09+ 1.07
GRACE
61.24
41.09:00.5
28.27=0.43
GCA
0OM
0OM
GCA
60.9410.81
41.53.11.09
28.8910.50
BGRL
72.71=0.22
71.54=00.17
BGRL
64.86+00.3
46.24++0.70
28. 28-50-0
CCA-SSG
72.31+0.18
7..21+:0220
AF-GCL
65.28+00.33
52.10:+0.67
28.94
APGRL
OOM
OOM
LOCAL-GCL
68.74:00.99
52.94+0.88
33.91=00557
LOCAL-GCL
72.29 71.3410.25
Results on Ogbn-Arxiv. Then, we evaluate the effectiveness and scalability of LOCAL-GCL on large-scale graphs taking Ogbn-Arxiv
an example. Following the practice in Thakoor al. (2021), we expand the encoder to a 3-layer GCN model. We report the validation and test accuracy of baseline models and ours in Table 2. As demonstrated, many baseline methods cannot in full graph manner (on a GPU with 16GB memory). Compared with other scalable methods, LOCAL-GCL. can give competitive performance on Ogbn Arxiv.
Results on Heterophily graphs. Finally, we investigate the performance on non-homophily graphs, much more challenging task as directly using first-order neighbors as positive examples without diseriminating might be harmful to non-homophily graphs. The results on the three heterophily graphs are presented in Table 3. Counterintuitively, LOCAL-GCL, achieves amazing performance, outperforming all the baseline methods. This probably due to following reasons: 1) Even though connected nodes may not share the same label, as long the neighborhood distributions for different classes are different, LOCALL-GLL able to recognize the neighborhood patterns of different classes and make the node embeddings for different classes distinguishable. This is also justified in one recent work showing that a GCN model can still perform well on heterophily graphs (Ma et al., 2022). 2) Data sugmentation-baser methods tend keep the low-frequency information while discarding the high-frequeed one (Wang et al., 2022; Liu et al., 2022), while high-frequency information is much more important for classification on heterophilic graphs (Bo al., 2021). By contrast, edge-wise positive pairs enable LOCAL-GCL to learn the differences between connected nodes better, thus benefiting heterophilic graphs. We provide more explanations for this point in Appendix C.4.
5.3 ABLATIONS
As demonstrated in Theorem and Sec. 4.2, the embedding dimension d and projection dimension D should be two critical hyperparameters affecting the model's performance. In this section, test.
8

---

Under review as a conference paper at ICLR 2023
of embedding dimension
85.0
62.5
GCL
72
CCA-SSG
BGRL
77.5
PGRACE(K=B192)
75.0
GRACE(K-2049)
72.5
Test Accuracy
70.0
Can
GRACE(k-16)
67.5
Fubmed
66
2048
GRACE(k=4 4)
(b) Effect projection dimension
84
82
62
Accure
GRACE|K=21
78
20
40
60
80
100
76
Training time (min)
74
2048
4096
8192
16384
Figure 2: Test accuracy and training time com- parison of LOCAL-GCL, BGRL, CCA-SSG and GRACE with subsampling.
Figure I: Sensitivity analysis of embedding dimension and projection dimension
LOCAL-GCL' sensitivities with respect them in Fig. 1. The observations are two-fold: 1) Similar to other self-supervised learning models (Hassani & Ahmadi, 2020; Zhu et al., 2021: Zhang et al., 2021; Lee et al., 2021), LOCAL-GCL that benefit from a large embedding dimension (e.g.. 512), LOCAL-GCL's performance perforrmnn also grows we increase the embedding dimension d. However, the optimal embedding dimension for LOCAL- GCL is even larger, e.g., 2048 on Cora and Citeseer (note that other methods do not benefit from such large embedding dimension). This could be justified by our analysis in Theorem 1, which demonstrates that with a larger embedding dimension, the bound of the prediction error will become lower (because the target eigenvalue dd+1 becomes larger). 2) Increasing the projection dimension can lead to better but minimal improvement. This indicates that practice, LOCAL-GCL can perform quite well without using huge projection D.
5.4 SCALABILITY COMPARISON
To evaluate the scalability of LOCAL-GCL real-world datasets, compare the total training time and accuracy with state-of-the-art scalable methods BGRL (Thakoor et al., 2021) and CCA- SSG (Zhang et al., 2021) on Arxiv dataset. To further justify the necessity of adopting large number of negative examples, we additionally adopt GRACE (Zhu et al., 2020b), powerful non-scalable contrastive model. We use sub-sane samplinglig strategy randomly sample a fixed number of negative examples every epoch so that the GRACE model could be fit into GPU with 16G memory. In Fig, we plot the model's 's performance and the corresponding training time of different methods. We can see that compared with scalable methods CCA-SSG and BGRL, LOCAI-GCII achieves comparable performance but with the least training time. We can also observe that although reducing the number of negative examples (k in Fig. 2) can enable the model to be trained much faster, the performance drop is significant, which cannot make up for the efficiency benefit. Furthermore, we continue to larger number of negative examples, GRACE will soon out of memory. This result demonstrates that LOCAL-GCL can better balance the training efficiency and model performance.
6 CONCLUSIONS
In this paper, we have presented LOCAL-GCL, a simple, liggt-weighted yet effective contrastive model for self-supervised node representation learning. LOCAI.-GCI. incorporates two orthogonal techniques to address two key issues in contrastive learning graph data: reliance on data augmenta- tion and scalability, respectively. The former involves a new definition positive examples such that the model is free from data augmentation whose design could be more difficult than its counterparts in vision and text, and calls for careful customization for different graph data and tasks. The latter devises approximated contrastive loss, which reduces the quadratic complexity of traditional contrastive learning to linearity in terms of the graph size. Extensive experimental results on seven public graph benchmarks show its efficiency and efficacy.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh. Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees. In ICML, pp. 253-262, 2017.
Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-supervised learning recover global and local spectral embedding methods. arXiv preprint orXiv:2205.15508 2022.
Hubert Banville, Omar Chehab, Aapo Hyvärinen, Denis-Alexander Engemann, and Alexandre Gramfort. Uncovering the structure of clinical eeg signals with self-supervised learning. Journal of Neural Engineering, 18(4)004602,, 2021.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 3950-3957, 2021.
Ting Chen, Simon Komblith ands Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In ICML, pp. 1597-1607, 2020.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. ICLR, 2020.
Valerio Ciotti, Moreno Bonaventura, Vincenzo Nicosia, Pietro Panzarasa, and Vito Latora. Homophily and missing links in citation networks. EPJ Data Sci., 2016.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In NAACL, pp. 4171-4186 2019.
Debidatta Dwibedi, Yusuf Aytar, Jonathan Tompson, Pierre Sermanet, and Andrew Zisserman. With little help from my friends: Nearest contrastive learning of visual representations. arXiv preprint arXiv:2 104. 14548, 2021.
Bernard J. Fino and V. Ralph Algazi. Unified matrix treatment of the fast walsh-hadamard transform. IEEE Transactions on Computers, 25(11):1142-1145 1976.
Tianyu Gao, Xingcheng Yao, and Danqi Chen. Simese: Simple contrastive learning of sentence embeddings. arXiv preprint arXiv:2 00004.88111... 2021.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Ávila Pires, Zhaohan 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 NeurIPS, 2020.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. NeurlPS, 34:5000-5011 2021.
Kaveh Hassani and Amir Hosein Khas Ahmadi. Contrastive multi-view representation learning on graphs. In /CML, 2020.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, pp. 9726 9735, 2020.
R. Devon Hjelm, Alex Fedorov, Samuel Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In ICLR, 2019.
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 NewrIPS. 2020.
Yannis Kalantidis, Mert Bülent Sariyildiz, Noé Pion, Philippe Weinzaepfel, and Diane Larlus. Hard negative mixing for contrastive learning. In NewrlPS, 2020.
10

---

Under review as a conference paper at ICLR 2023
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders, arXiv preprint /rXiv:/611.000 2016.
Soroush Abbasi Koohpayegani, Ajinkya Tejankar, and Hamed Pirsiavash. Mean shift for self- supervised learning. In ICCV, pp. 10326-10335, 2021.
Quoc Le. Tamás Sarlós, Alex Smola, al. Fastfood aapprooiatpppoiiitingg kernel expansions in loglinear time. In ICML, pp. 244-252, 2013.
Namkyeong Lee, Junseok Lee, and Chanyoung Park. Augmentation-free self-supervised learning on graphs. arXiv preprint arXiv:21 12.0212..2242. 2021.
Yazhe Li, Roman Pogodin, Danica Sutherland, and Arthur Gretton. Self-supervieed learning with kernel dependence maximization. arXiv preprint arXiv:2106.08:22 2021.
Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens. Random features for kernel approximation: A survey on algorithms, theory, and beyond. arXiv preprint arXiv:2004. / 154, 2020.
Nian Liu, Xiao Wang, Deyu Bo, Chuan Shi, and Jian Pei. Revisiting graph contrastive learning from the perspective of graph spectrum. arXiv preprint arXiv:2210.02330, 2022.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? ICLR, 2022.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image-based recommendations on styles and substitutes. In SIGIR, pp. 43-52, 2015.
Miller McPherson, Lynn Smith-Lovin and James M Cook. Birds of feather: Homophily in social networks. Annual review of sociology, 27((1):155444)) 2001.
Yujie Mo, Liang Peng, Jie Xu, Xiaoshuang Shi, and Xiaofeng Zhu. Simple unsupervised graph representation learning. In AAAI, pp. 7797-7805, 2022.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, 2012.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A Smith, and Lingpeng Kong. Random feature attention. In ICLR, 2021.
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, pp. 259-270, 2020.
Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. In ICMI. pp. 5171-5180, 2019.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. GCC: graph contrastive coding for graph neural network pre-training. In KDD, pp. 1150-1160. 1160, 2020.
Ali Rahimi, Benjamin Recht, al. Random features for large-scale kernel machines. In NIPS, pp- 1177-1884, 2007.
Joshua David Robinson, Ching- Yao Chuang, Suvrit Sra, and Stefanic Jegelka. Contrastive learning with hard negative samples. In ICLR, 2021.
Benedck Rozemberezki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
11

---

Under review as a conference paper at ICLR 2023
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rate Rad. Collective classification in network data. Al magazine, 29(3):93 93,9999-33220 2008.
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 WWW, pp. 243-246, 2015.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Velickovic, and
Michal Valko. Bootstrapped representation learning on graphs. arXiv preprint arXiv:2102.0657/ 2021.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In ECCV, pp. 776-794, 2020.
Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. Self-supervised learning from multi-view perspective. In ICLR, 2021.
Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint 1007.v38 2018.
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and Devon Hjelm. Deep graph infomax. In ICLR, 2019.
Haonan Wang, Jieyu Zhang, Qi Zhu, and Wei Huang. Augmentation-free graph contrastive learning with performance guarantee. arXiv Preprint arXiv:2204.04874 abs/2204.04874, 2022.
Minjie Wang. Lnn Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma. Ziyue Huang, Qipeng Guo, Hao Zhang, Haibin Lin, Junbo Zhao, Jinyang Li, Alexander J. Smola, and Zheng Zhang. Deep graph library: Towards efficient and scalable deep learning graphs. arXiv, 1909.01315, 2019.
Qitian Wu, Hengrui Zhang, Xiaofeng Gao, Peng He, Paul Weng, Han Gao, and Guihai Chen. Dual graph attention networks for deep latent representation of multifaceted social effects in recommender systems. WWW. pp. 2091-2102. ACM, 2019.
Jun Xia, Lirong Wu, Ge Wang, Jintao Chen, and Stan Z. Li. Progel: Rethinking hard negative mining in graph contrastive learning. In /CML, volume 162 of Proceedings of Machine Learning Research, pp. 24332 24346. PMLR, 2022.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NeurIPS, 2020.
Felix Xinnan X Yu, Ananda Theertha Suresh, Krzysztof M Choromanski, Daniel N Holtmann- Rice, and Sanjiv Kumar. Orthogonal random features. In NIPS, pp. 1975-1983, 2016.
Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu. From canonical correlation analysis to self-supervised graph neural networks. In NeurIPS, 2021.
Qinyi Zhang, Sarah Filippi, Arthur Gretton, and Dino Sejdinovic. Large-scale kernel methods for independence testing, Statistics and Computing, 28( 28(1):113-130 2018.
Shaofeng Zhang, Meng Liu, Junchi Yan, Hengrui Zhang, Lingxiao Huang, Xiaokang Yang, and Pinyan Lu. M-mix: Generating hard negatives via multi-sample mixing for contrastive learning. In KDD, pp. 2461-2470. ACM, 2022.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In NearlPS, 2020a.
Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, pp. 912-919, 2003.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv: 04131, 2020b.
Yanqiao Zhu, Yichen Xu, Feng Yu. Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW. 2021.
12

---

Under review as a conference paper at ICLR 2023
A PROOFS
A.1 PROOF FOR THEOREM
Proof. To prove Theorem I, we first introduce a lemma that shows the optimal representations learned from InfoNCE-like loss function (e.g.. Eq. 5) derived from Balestriero & LeCun (2022):
Lemma 1. Denote the eigendecomposition of the normalized graph adjacency matrix by À UAU", where U and A are the eigenvectors and eigenvalues of respectively. Assume node embeddings are free vectors, then a global minimizer of the loss function in Eq. 5 is given by:
Z (U (/A11/)),.a
(11)
up to permutations of the eigenvector associated with the same eigenvalue. 1: d in Eq. 11 indicates the largest d eigenvalues and the associated eigenvectors.
Besides, HaoChen et al. (2021) has presented the following theoretical guarantee for the model learned with the matrix factorization loss:
Lemma For graph with symmetric normalized graph udjacency matrix and Laplacian matrix A and L, let Jmf arg min fm.:V-RR be a minimizer of the matrix factorization loss:
)1?) where F is the embedding matrix. Then, for any labeling function 9 V jr). there exists linear classifier B" E Raxx with norm [| p S 1/(1 dd+1) such that:
fmr F) =I[[I- - L [[[--L-
Evey [| B' S
(12)
Aep1
where o is the graph homophily ratio defined in Eq. 6.
Then we just need to connect r in Eq. 11 with the optimal solution the rthe matrix factorization
loss Cmr (F) I L FF | Á FF ||. According Eckart Eckart-Young- Goung-Mirske theorem,
the optimal FF is FFT U U.I.A,,, .idd As a result, F Z (UA ia is exactly the
global minimizer of Lm (F). Then the proof is complete.
A.2 PROOF FOR THEOREM 2
Proof. prove Theorem we first introduce the following lemma given by Lemma in (Yu et al., 2016).
Lemma The Random Fourier Estimation KRFF (x, y) an unbiased estimator of the Gaus- sian kernel, i.e. Ew (wb(w)) (by)) = -111=111 Let z || -yllz/ vF, then the variance of Knrr(æ, y) is V (v(()) (1))) = 10000(1--65 (1/6-3)9/22.
The lemma shows that the Random Fourier Features can achieve an unbiased approximation for Gaussian kernel with quantified variance.
Back to our main theorem, we can derive the following probability using the Chebyshev's 's inequality:
P(A 1 exp( (/p(-4/T) 2 V. (v) (h:) (v 2Ds
(13)
V2D
(1 exp( -4/T))²
where A (h:) oh (h₂) x (h; h denotes the deviation of the kernel approximation. Using the result in Lemma 3, we can further obtain that the RHS of Eq. 13 is
c #
1 - e1-expl 4/T))2
(14)
As both h; and hy are ez-normalized, we have 2² = hh: h 11// S 4/T, so we can conclude the stated result:
P(A < 1 exp( (4//)
(1 -1- e #
2 1
2
(15)
V2D=
exp( (4/-))
n
13

---

Under review as a conference paper at ICLR 2023
B ADVANTAGES OF LOCAL-GCL OVER PRIOR METHODS
We provide a systematic comparison for the proposed LOCAL-GCL with previous typical methods self-supervised node representation learning, including DGI (Velickovic et al., 2019), MVGRL (Has- sani & Ahmadi, 2020), GRACE (Zhu et al., 2020b), GCA (Zhu et al., 2021), BGRL (Thakoor et al., 2021), CCA-SSG (Zhang et al., 2021) and AFGRL (Lee et al., 2021).
B. TOTALLY FUGRENTATION-FREE WITH SINGLE BRANCII
Most of previous seff-supe learning models (Velickovic et al., 2019; Hassani & Ahmadi, 2020; Zhu et al., 2020b; 2021; Thakoor et al., 2021; Zhang et al., 2021) require carefully-defined graph augmentations to obtain positive pairs. However, noted above, it is hard and costly design task and dataset-specific graph augmentations. Our method LOCAL-GCL naturally avoids data augmentation by using the first-order neighborhood information of each node. Moreover, different from all previous methods that have two branches of models (double amounts of inputs, hidden variables, outputs, etc.), our approach only requires a single branch, which makes our method light-weighted.
B.2 RROJECTOOPPEEDICCOODDSSCCMMMMMMD
Most the previous methods require additional components besides the hasic encoder for decent empirical results (Zhu et al., 2020b; 2021), to break symmetries avoid trivial solutions (Thakoor et al., 2021; 1; Lee et al., 2021) or to estimate some score functions in their final objectives (Velickovic al., 2019; Hassani & Ahmadi, 2020). Compared with them, LOCAL-GCL. is much simpler, in both conceptual and practical senses, without using any parameterized model but the basic encoder.
B.3 THEORETICALLY GROUNDED WITH LINEAR COMPLEXITY
Empirically, InfoNCE- contrastive methods (Zhu et al., 2020b; 2021) often show better perfor- mance than DIM-based methods (Velickovic al., 2019; Hassani & Ahmadi, 2020) yet suffers from the scalability issue. Recent non-contrastive methods (Thakoor et al., 2021; Lee et al., 2021) could maintain decent performance with linear model complexity through asymmetric structures, while the rationale behind their success still remains unclear (Zhang et al.. 2021). As contrastive model, LOCAI.-GCL, is theoretically grounded (through maximizing the mutual information between target node's s embedding and its neighbor's embeddings), and its kernelized approximation of negative loss enables it to scale to large graphs with linear time and memory complexity with respect to the graph size.
C EXPERIMENT DETAILS AND ADDITIONAL. EMPIRICAL RESULTS
C.I DATASETS
The statistics the used datasets are presented in Table 4, and brief introduction and settings are as follows:
Cora, Citeseer, Pubmed are three widely used node classification benchmarks (Sen et al., 2008; Namata et al., 2012). Each dataset consists one citation network, where nodes represent papers and edges represent a citation relationship from one node to another. use the public split, where each class has fixed 20 nodes for training, another fixed 500 nodes and 1000 nodes for validation/test, respectively for evaluation.
Coauthor-Ca Coauthor-Physe Graph from the KDD Cup 2016 challenge (Sinha et al., 2015). Nodes are authors that are connected by an edge if they co-authored paper; node features represent paper keywords for each author's papers, and class labels indicate the most active fields of study for each author. As there is no public split for these datasets, randomly split the nodes into train/validation/tsst (10%/10%/80) sets.
co-authorship graphs based on the Microsoft Academic
Amazon Ciaazon-Computer Amazon-Phot are segments of the Amazon co- co-purchase graph (McAuley al., 2015), where nodes represent goods, edges indicate that goods are frequently bought
14

---

Under review as a conference paper at ICLR 2023
Table 4: Statistics of benchmark datasets.
Dataset
#Nodes
#Edges
#Classes
#Features
Cora
2,708
10.556
7
1,433
0.810
Citesser
3,327
9,228
6
3,703
0.736
Pubmed
19,717
88,651
3
500
0.802
Coauthor-CS
18,333
327,576
15
6,805
0.808
Coauthor-Physics
34,493
991,848
5
8,451
0.931
Amazon-Computer
13,752
574,418
10
767
0.777
Amazon-Photo
7,650
287.326
745
0,827
Ogbn-Arxiv
169,343
2,332,386
40
128
0.655
Chameleon
2,277
36,101
5
2,325
0.235
Squirrel
5,201
217,073
5
2,089
0.224
Actor
7,600
33,544
5
931
0.219
Table 5: Details of hyper-parameett of the experimental results in Table
Local-GCI.
Dataset
Encoder
Steps
# layers
Ir
wd
Cora
GCN
50
5c-4
lc-6
2048
8192
0.5
Citeseer
GCN
20
lc-3
lc-4
2048
4096
0.5
Pubmed
GCN
50
2
5c-4
0
1024
8192
0.5
Amazon-Computer
GCN
50
5e-4
1024
8192
0.8
Amazon-Photo
GCN
50
Se-4
le-6
2048
8192
Coauthor-CS
MLP
50
2
Se-4
le-4
1024
4096
0.5
Coauthor-Physics
MLP
50
2
5e-4
0
1024
4096
0.7
together; node features are bag-of-words encoded product reviews, and class labels are given by the product category. We also use 10%//0%%/0%% split for these two datasets.
For simplicity, use the processed version of these datasets provided by Deep Graph Library (Wang et al., 2019)". One can easily acquire these datasets using the api provided by DGL.
Ogbn-Arx: is directed graph, representing the citation network between all Computer Science (CS) arXiv papers (Hu et al., 2020). Each node is an arXiv paper and each directed edge indicates that paper cites another one. Each paper comes with 128 22-dimmnnioonal feature vector obtained by averaging the embeddings of words in its title and abstract. The embeddings of individual words computed by running the skip-gram over the MAG corpus. All papers are also associated with the year that the corresponding paper was published. We use the official split in our experiments.
Chame leon and Squirrel (Rozemberczki et al., 2021) Wikipedia networks introduced. Nodes represent web pages, and edges represent hyperlinks between them. Node features represent several informative nouns in the Wikipedia pages. The task is predict the average daily traffic of the web page.
Actor is the actor-only induced subgraph of the film-director-actee writer network used in Pei et al. (2020). Each node corresponds to an actor, and the edge between two nodes denotes co-occurrence on the same Wikipedia page. Node features correspond to some keywords in the Wikipedia pages. The task is to classify the nodes into five categories in term of words of actor's Wikipedia.
For Chameleon, Squirrel and Actor, we use the raw data provided by the Geom-Gee GCN (Pei et al., 2020) paper", and we use the 10-fold split provided.
C.2 HYPER-PARAMETERS
We provide detailed syper-parametent on the seven benchmarks Table All hyper-parameten are selected through small grid search, and the search space provided as follows:
htttps::/ddoc..d1..a.... 'https://gi http///ttttttttttt www.hhhw....c.cccoooooooeeeeeeee wttptthb.m.maaammmm... http//aappppmmmamm..m -uii jacliiuoolllluuueeeee 1la-jjon-gggnnn
15

---

Under review as a conference paper at ICLR 2023
Training steps: 50)
Number of layers: [1,2)
Embedding dimension d: (512, 1024, 2048)
Projection dimension D: (2048, 4096, 8192)
Temperature т: [0.5, 0.6, 0.7, 0.8, 0.9, 1.0]
Learning rate: (5e-4, le-3, 5e-3]
Weight decay: (0, le-6, le-4)
C.3 EXTENSIVE ABLATION STUDIES
We further extend LOCAL-GCL with other designs of positive example construction, negative example selection, and self-supervised objective functions to evaluate the effectiveness of each single component of the proposed method.
C.3.1 DIFFERENT STRATEGIES FOR CONSTRUCTING POSITIVE EXAMPLES USING NEIGHBORHOODS
In addition to treats each neighboring node equally positive examples, further explore two other positive sampling strategies: 1) computing the similarities between neighboring nodes, and the most similar as the positive example (we term it LOCAL-GCL the importance of different neighboring nodes according to their similarities, where more similar neighboring node should be assigned larger weight (we
reweighting
GCL-w--C)
For LOCAL-GCL-max, we first its the nearest neighbor:
= arg min
(16)
JEN(()
z
and the objective function is
V
exp(2, /T
CLocatGCL-mar
Σ
log
(17)
M
Σ
exp(2, 2x/T)
kEV
For LocalGCL-weeiht, we first compute the pair-wise similarities of neighboring nodes:
sim
A.j
(18)
Then, for target node i, it softmax the scores of its neighboring nodes as the weights:
w. wi(j)
softmax[sim,))
(19)
The objective function of LocalGCL-weight is consequently defined
Σ JEN(O)
wi(i) exp/2222////WW00
M
LLocllCCL-weigh
log
(20)
Σ KEV
exp(2 2t/T)
The results LOCAL-GCL-mas and is presented in Table 6: From this table, we can observe that using the nearest neighboring node as the only one positive example is likely harmful (except on Citeseer) to the performance, this should be because this operation can discard lot of useful information in the local neighborhood. Besides, LoCAL-GCL-weight improves the performance on Cora significantly but makes little difference on Citeseer and Pubmed. This might be because, without supervision, higher similarity in the latent space does not necessarily indicate a higher probability of sharing the same label. Considering that BOCAL--CL--wdd performance the original LOCAL-GCL, is already quite good, we just treat every neighboring node equally in this work.
together with the original LOCAL-GCL
requires additional computational cost for computing the weights, and the
16

---

Under review as a conference paper at ICLR 2023
Table 6: Performance variation when using different strategies constructing positive examples from neighboring nodes.
Cora
Citeseer
Pubmed
LOCAL-GGCI (origin)
84.5 + 0.4
73.6 0.4
82.1 0.5
LoCAI-GCI--max
83.6 + 0.5
73.7 0.5
81.7 0.5
LoCAI-GGLI-weight
84.9 +
73.7 0.4
82.2 + 0.5
Table 7: Test accuracy, training time cost and memory cost when using the positive pair constructing method in this paper compared with using data augmentation for BGRL and CCA-SSG.
Coauthor-CS
Coauthor- Physiic
Acc
Time
Memory
Acc
Time
Memory
BGRL
92.59 + 0.17
30.4 min
2.9G
94.48 0.08
57.7 min
5.6G
BGRL-Local
92.98 0.23
18.2 min
188G
95.82 0.11
32.3 min
3.7G
CCA-SSG
93.31 + 0.22
1.1 min
3.5G
95.38 0.06
5,9 min
7.1G
CCA-SSG-Local
94.08 + 0.19
0.7 min
2.2G
95.69 + 0.09
4.3 min
4.4G
C.3.2 COMBINING WITH NEGATIVE-SAMPLE-
SELF-SUPERVISED LEARNING METHODS
using the target node's first-order neighbors as positive examples) could also benefit non-contrastive methods, like BGRL and CCA-SSG. Note that both BGRL and CCA-SSC use the exact same data augmentations methods proposed in GRACE (a contrastive method). As result, we can simply replace the positive examples in BGRL, and on-diagonal terms in CCA-SSG with the ones used in this paper, thus making them free from data augmentations. In such as case, the models do not require two-vite viewee data as inputs, so the size of inputs, intermediate variables, and outputs can be reduced by half. To better demonstrate this point, we further extend our method with BGRL and CCA-SSG.
For BGRL,, denote the target embedding of node by h; and the corresponding prediction by our BGRL-Local optimizes the following loss function:
2
h
LBGRL-Loce Local
(21)
N
JEN(())
For CCA-SSG, denote the embedding of node by his we first compute the local summary of node i by 2,
[OT Σ hy. Then we compute two standardized embedding matrix by: jEN(()
H H - (H) 2 o(H) V o(Z) V
Z (-
(22)
Finally, CCA-SSG-Local opimiizs the following loss function:
LoCA-sSG-Loch f 2 + (H
|
1 11
(23)
We report the performance of BGRL-Local and CCA-SSG-Local compared with the original BGRL and CCA-SSG on CS and Physics, together with their training time/memory cost in Table 7 (We didn't choose the three citation networks as BGRL performs really bad on them).
(BGRL takes much longer time for training, because it does require a lot of training epochs to converge.) As demonstrated in the table. The performance of BGRL and CCA-SSG both get improved after adopting neighboring nodes as positive examples, which highlights the value of graph structure information as self-supervised learning signals. Besides, it also reduces the training time and memory cost because it gets rid of the two-branch architecture caused by data augmentations.
C.3.3 COMBINING WITH HARD NEGATIVE SAMPLING METHODS
Furthermore, one important advantage of contrastive learning is that it can be incorporated with hard negative sampling techniques (Robinson et al., 2021; Kalantidis et al., 2020; Zhang al.,
17

---

Under review as a conference paper at ICLR 2023
Table Effect of combining LOCAL-GCL with hard-negative sampling methods.
Cora
Citeseer
Pubmed
LOCAI.-GCL (origin)
84.5 + 0.4
73.6 + 0.4
82.1 = 0.5
LOCAL-GCL +ProGCL-mix
84.9 + 0.5
74.2 + 0.4
82.3 = 0.5
Table 9: Bootstrapped confidence interval (with 95% confidence).
Cora
Citeseer
Pubmed
Computer
Photo
CS 193.25, 93.41] 194.89, 94.988
Physics
CSG
[8406, 84,30]
[73.05, 73.21]
[81.5], 81.72]
[88.57, 88.86 86]
[93.10, 93.22] 193.20, 93.48)
195.37, 95.41]
LOCAL-GCL
184.43, 84.75]
[73.45, 73.83]
[81.22 82.291
188.66, 89,06]
196.26. 96.35]
2022: Xia et al., 2022). These works either assign weights different negative samples so that true negative examples are more important than false negative examples, or use mix-up methods to generate even harder negative examples. With these techniques, the performance of contrastive learning can be greatly boosted. To demonstrate this point, we further combine our method with the hard negative mining strategy ProGCL-mix proposed Xia al. (2022), and we report the perfor- mance comparison on Cora, Citeseer and P Pubmed in Table 8: The improvement is prominent (especially on Cit Citeseer) thanks to the hard-negative sampling strategy(however, ProGCL-mix is not our contribution so cannot include it in our method in this paper). Besides, we notice that the improvement on Pubmed is smaller than that on the other two datasets, we guess this is because there are only classes of nodes Pubmed, so it is less effective to mine hard negatives than 7 classes on Cora and on Ci Ciseeer.. By contrast, negative-sample-fre method like BGRL and CCA-SSG cannot get benefits from it.
C.4 ANALYSIS OF THE RESULTS ON HETEROPHILIC GRAPHS
Although a little bit counter-intuitive the better performance of our method on heterophilic graphs does exist, and can be justified through the differences between the two distinguished methods of generating positive pairs: 1) data augmentations
graph data; 2) two connected nodes being a positive pair. Two recent studies Wang et al. (2022) and Liu et al. (2022) both demonstrate that existing data augmentations on graphs, such as graph diffusion used in MVGRL (Hassani & Ahmadi, 2020), edge dropping and feature masking used in GRACE (Zhu et al., 2020b), GCA (Zhu al., 2021), BGRL (Thakoor et al., 2021) and CCA-SSG (Zhang et al., 2021) have larger impacts on the high-frequency information of the graph than the low-frequency information. As a result, the differences between two graph views are about low-frequency components. Considering that contrastive learning aims at maximizing the mutual information shared between the two views, only the invariant information (low- (ow-frequency) is encouraged be learned by the embeddings, while the middle and high-frequency information is discarded.
On the other hand, studies on GNNs for heterophilic graphs (Bo et al., 2021) demonstrate that for heterophilic graphs, the high-frequency information in the graph is more effective for down- stream classification performance. Considering that data-auggmenttiinn-oee
methods focus on one, it is not strange that they cannot
www-freuency information while neglecting give satisfactory performance. By contrast, as high-frreuency knowledge in the graph represents the differences between the node feature with its neighborhood features, the edge-wise contrastive loss used in our work can better capture the differences in the information between two connected nodes, thus performing better heterophilic graphs.
C.5 STATISTICAL SIGNIFICANCE TEST
We further conduct statistical significance tests to show that LOCAL-GCL does perform better than the previous SOTA method CCA-SSG (Zhang et al., 2021).
In Table 9 we present the bootstrapped confidence interval (with 95% confidence). We also conduct Wilcoxon signed-ran test on the proposed LOCAL-GCO GCL and the second best model CCA-SSG, using the averaged test accuracy the datasets in Table 1. The p-value of CCA-SSG and LOCAL-GCL'S performance on the 7 datasets is 0.0325 < 0.05. As a result, we can conclude that there is a genuine performance difference between the performance of LOCAI.GGLL and that of CCA-SSG.
18

---

Under review as a conference paper at ICLR 2023
D REPRODUCIBILITY
We provide detailed codes and running instructions in the supplementary material.
19


Reviews:
[{"review_id": "wQdKPC-6Zt", "reviewer": "Reviewer_BqrR", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper proposes an augmentation-free graph contrastive learning framework based on the assumption of the graph homophily assumption. Meanwhile, the authors use the Random Fourier Features to approximate the negative loss in contrastive learning and thereby reduce the computation cost to linear complexity. ", "summary_of_the_review": "Overall, the idea is interesting and efficient, but the contribution of the idea over the prior negative -sample-free graph SSL method is limited. More importantly, the proposed claim is not well-supported, and the authors do not provide a very detailed analysis of the theorem in the paper.  Except for the performance comparison, the paper does not demonstrate enough experiments to support the claim and show the superiority of the proposed method over the baselines.  Additional theoretical analysis and experiments mentioned above are necessary to strengthen this work.  ", "strength_and_weaknesses": "The following are the pros of the paper: \n1. The paper proposes a new graph contrastive learning without relying on any hand-crafted graph augmentation techniques. According to the reported results, the proposed method achieves SOTA performances on many datasets. \n\n2. The paper design a surrogate loss to approximate the negative loss in contrastive learning and thus reduce the quadratic computation cost in linear complexity. Experiments are conducted to demonstrate the obvious complexity advantages of the proposed method over prior graph CL models with extensive negative sampling (GRACE etc.)\n\n3. Overall, the paper is well-organized and easy to read. \n\nThe following are some concerns and questions about the paper:\n1. Although the proposed model can achieve better computation efficiency compared with those GCL methods with extensive negative sampling, this advantage does not exist for those negative-sample-free methods, e.g., BGRL and CCA-SSG. Besides, the performance gain over the two baselines seems to be incremental, the authors are encouraged to clarify the contribution of the proposed methods over the prior negative-sample-free graph CL methods. \n\n2. The proposed augmentation-free mechanism is designed based on the graph homophily theory. According to the assumption and theoretical justification of the paper, the performance of the proposed method should be heavily dependent on the homophily ratio. However, the performance gain of the method seems to be even more significant on the heterophily graphs, which conflicts with the paper’s assumption. It is very important to conduct more discussions and experiments to study this phenomenon because this is the most important claim of this paper. The authors are encouraged to provide more explanation on the phenomenon and testify to the correlation between its work mechanism and graph homophily. \n\n3. It is good to see the authors try to theoretically justify their claims in the paper, but the proof of theorem 1 is still confusing. For example, how do you derive Equation (14) from Equation 12 and how do you derive the relation between the homophily ratio and the node embeddings that minimize matrix factorization loss? The authors are encouraged to provide more detailed proof of their proposed theorem.\n \n4. The ablation study in the paper can be only considered as the parameter sensitivity analysis. A more comprehensive ablation study is necessary to evaluate the design of the paper, for example, what the performance and scalability of the proposed method will be with different positive and negative sampling strategies. Besides, the paper only compares the training time of the proposed methods and selected baselines, it would be better if the experiment about training space comparison is included.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "hU7N0nGgYv", "reviewer": "Reviewer_Nj2N", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper \"Localized Graph Contrastive Learning\" suggests a contrastive learning method (Local-GCL) for graph data, based on the InfoNCE loss. In this setting, each graph node is associated with a feature vector, and the goal is to learn a meaningful representation of the graph nodes (representation quality can be measured using a linear classifier for known node labels). Local-GCL is based on two ideas: (1) use graph edges instead of data augmentations for positive pairs; (2) use random Fourier features to quickly compute negative part of the loss. The authors show that Local-GCL achieves SOTA performance on several benchmark datasets.", "summary_of_the_review": "The paper suggests several novel ideas to graph contrastive learning and achieves SOTA results. Strong accept. However, disclaimer: I am unfamiliar with the literature on graph contrastive learning.", "strength_and_weaknesses": "Disclaimer: I am familiar with contrastive learning but am unfamiliar with the literature on graph representation learning / graph contrastive learning. So I cannot judge on the novelty compared to the existing literature. That said, the literature overview and the benchmarks shown in this paper look legit convincing, and the method does appear SOTA. Both novel ideas (for positive and negative pairs) are interesting. Therefore I believe this is a strong paper and a strong accept. \n\nI do not have any major issues. A number of things were not entirely clear to me, but it should be easy to edit them for clarity. \n\n* Section 2.3: it is not immediately clear how this section refers to the rest. I only understood it several pages later. Perhaps one introductory sentence could be added to explain the purpose of this section.\n\n* Equation 2 -- the InfoNCE loss usually has positive pair in the denominator as well, not only in the numerator (see e.g. SimCLR paper). Here you don't include the positive pair in the denominator. Why is that? Please comment.\n\n* Section 3: it was not entirely clear to me here what is the input to the network, and what are the i's in z_i. Later I understood that every node in the graph has an associated feature vector, and these features constitute the input neurons of the network. This is what you mean by \"node-level\", but I think it may be helpful to spell it out more clearly.\n\n* page 5: \"st\" -> \"set\"\n\n* Theorem 1 sounds like a really strong and important result, but inspection of Appendix A.1 suggests that it is a rather straightforward consequence of the results from two other papers. I think it would be prudent to cite both of them in the main text and to write something like \"The proof is a direct consequence of the results of \\citet{} and \\citet{}\".\n\n* Section 5.1: It would be great to have Table 4 in the main text but I understand that the space constraint may not allow it. But I would suggest to give some summary stats in the text of this section, perhaps mention that the number of nodes varied from 2k to 170k, etc. Maybe also give the range of the feature dimensionalities, etc.\n\n* Section 5.1: \"Implemention details\" paragraph could mention the network architecture. Was it a fully-connected network (MLP)? Something else?\n\n* Figure 2: I would suggest to connect all GRACE points with a solid green line.\n\n* Section 5.4: In SimCLR, the number of negative examples is determined by the mini-batch size. Is the same true in GRACE? \n\n* Related: I am actually not sure what if you used mini-batches for Local-GCL. What was the mini-batch size? Or did you use full-batch training instead of stochastic gradient descent? Your description on page 5 sounds as if you use *all* graph nodes as negative pairs, meaning that your M in Equation 2 is equal to the number of nodes. Is my understanding correct? If so, then does this mean that you did full-batch training? Otherwise how did you implement mini-batches?\n\n* Equation 8 holds for a non-graph contrastive learning models such as SimCLR. Does it mean that one could you user random Fourier features approach in SimCLR and related non-graph methods?\n\n* Section B.1 and also the main text: As I said, I am unfamiliar with the graph contrastive learning literature, but I am surprised to read that most existing methods usg some elaborate data augmentation schemes. Your approach (take graph edges as positive pairs) seems much simpler. Why has it not been adopted before?", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5_lMBH0-OL", "reviewer": "Reviewer_4oqi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes a contrastive learning method for self-supervised node-level tasks in graph domain. It involves (1) sampling positive samples from the first order neighbourhoods and (2) kernelizing negative loss to reduce the training time and memory overheads.\nThe main contribution of this paper is presenting a simple yet efficient and intuitively reasonable idea regarding the use of first level neighbourhoods for selecting positive samples and achieving competitive performance with state-of-the-art methods. Some theoretical results are presented to support the adopted approach.\n", "summary_of_the_review": "The paper proposes a simple technique for self-supervised learning for node classification. Theoretical results are provided to motivate the approach. The paper introduces a kernelization strategy to significantly reduce the computational burden. Although simple, the experiments demonstrate that the method can achieve SOTA performance. The main misgiving concerning the paper is the novelty and the impact, considering that a similar approach has already been proposed in other work. \n\n", "strength_and_weaknesses": "Strengths:\nS1. The use of first order neighbourhoods for positive sampling is theoretically justified under the homophily assumption.\nS2. The proposed method is computationally efficient and experiments show that the approach can scale to larger graphs.\nS3. The paper is well organized and explains the approach very clearly.\n\nWeaknesses:\n\n1. The idea relies on homophily, however the performance improvement for heterophilic graphs (table 4) is more pronounced. It is not clear how this is possible and the paper provides no explanation apart from unsupported conjectures. The result tends to undermine the other experimental results for the homophilic, drawing into question whether the observed good performance is genuine and whether it arises for the reasons posed in the paper.\n\n2. Although the proposed approach is effective, the idea of using neighbours as positive samples in graph contrastive learning has been proposed before, albeit recently. The use of kernel approximations random Fourier features has been proposed in other (non-graph) self-supervised learning work. This diminishes the novelty and impact of the paper. \n\n\nQuestions and Comments\n\n1.\tNovelty: The idea of using the neighbour as a positive sample in contrastive learning has been proposed before (for example, in [R1, R2]). [R2] was only published in July, so may be consider concurrent work, but [R1] appeared in February. Although the definition of a “neighbour” in [R1] is more complicated (making it much less computationally efficient than the proposed technique), this does diminish the novelty of the proposed approach. \n\nIf it is accepted that graph contrastive learning using neighbours as positive samples is a known idea, then it’s not clear to me that the paper makes a sufficient theoretical or experimental contribution. Each theorem, while interesting, is derived fairly straightforwardly from existing results. The experiments are conducted over multiple datasets and compare against numerous baselines, but the results for the graphs displaying heterophily are unexplained and a concern. The kernel approximations to make the computation efficient are a valuable contribution, although in the context of non-graph learning, the use of random Fourier features has been proposed in [R3]. The proposal to use structured orthogonal random features in this context is novel, to the best of my knowledge, and does result in a significant computational saving. \n\nCan the authors discuss the related work that I have identified, stressing the differences, and reinforcing the novelty of the contribution?\n\n2. Can the authors provide a better explanation for the performance in the heterophilic graph case?\n\n3. The paper does not report the results of any statistical significance tests. I would encourage the reporting of (bootstrapped) confidence intervals rather than 1 standard deviation. Single split results also give a false impression of the variability of the performance. Wilcoxon pair tests between the best and second-best techniques would provide more compelling evidence that there is a genuine performance difference.\n\n[R1] Zihan Lin, Changxin Tian, Yupeng Hou, Wayne Xin Zhao, “Improving Graph Collaborative Filtering with Neighborhood-enriched Contrastive Learning,” in Proceedings of the ACM Web Conference (WWW), 2022.\n\n[R2] Sun, Z., Harit, A., Cristea, A. I., Yu, J., Shi, L., & Al Moubayed, N. “Contrastive Learning with Heterogeneous Graph Attention Networks on Short Text Classification,” In Proc. International Joint Conference on Neural Networks (IJCNN), 2022.\n\n[R3] Li, Y., Pogodin, R., Sutherland, D. J., & Gretton, A. (2021). Self-supervised learning with kernel dependence maximization. Advances in Neural Information Processing Systems, 34, 15543-15556.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2iA6xWkSjm", "reviewer": "Reviewer_q5an", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces Local-GCL, a graph contrastive learning approach that tackles two of the most common issues of GCL models: the need for augmentation to generate positive pairs (which is non-trivial in the graph-learning setting) and the need for a high amount of negative pairs comparisons (whose quadratic complexity makes the problem intractable for large graphs). It does so by, respectively, creating positive pairs from first-order neighbors, and introducing an approximated contrastive loss computation that approximates the original loss with a much lower complexity (linear instead of quadratic). The authors provide theoretical justifications for their model and show empirically that it performs competitively to the state of the art while having a much smaller computational footprint.", "summary_of_the_review": "The paper aims at improving CGL by providing a model which is, at the same time, independent of graph augmentations and more scalable. Motivations are clear and relevant and the presentation of the related work is in my opinion sufficient to place this work in the proper context.\n\nWhile empirical results are in my opinion quite positive, the paper still leaves some open questions about the contributions brought individually by the two components implemented in the model. I also think some claims should be better supported, so that the theoretical contribution becomes more rigorous and less incremental.", "strength_and_weaknesses": "Strengths:\n- the method proposes a method to significantly reduce the computational complexity of the calculation of negative loss in GCL models\n- the experiments show results which are promising, especially when compared to other models' running times\n\nWeaknesses:\n- the paper is not always clear due to mistakes or ambiguous definitions\n- I have some doubts about the contribution and the soundness of the theoretical part of the paper (see below)\n- the experimental section still leaves some open questions (related to the contribution brought by the two different components and the performances on heterophilic graphs)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject