\section{Introduction}
Self-supervised learning has achieved remarkable success in learning informative representations without using costly handcrafted labels~\citep{cpc, bert, uncovering, moco, simclr, byol, cca-ssg, gao2021simcse}. Among current self-supervised learning paradigms, InfoNCE loss~\citep{cpc} based multi-view contrastive methods~\citep{moco, simclr, gao2021simcse} 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~\citep{poole2019variational}. Inheriting the spirits of contrastive learning on vision tasks, similar methods have been developed to deal with graphs and bring up promising results on common node-level classification benchmarks~\citep{dgi, mvgrl, grace, grace-ad}.

The challenge, however, is that prevailing contrastive learning methods rely on predefined augmentation techniques for generating positive pairs as informative training supervision. Unlike grid-structured data (e.g., images or sequences), it is non-trivial to define well-posed augmentation approaches for graph-structured data~\cite{grace-ad, cca-ssg}. The common practice adopted by current methods resorts to random perturbation on input node features and graph structures~\citep{graphcl}, which might unexpectedly violate the underlying data generation and change the semantic information~\citep{afgrl}. Such an issue plays as a 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~\citep{grace, grace-ad}, 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.e., batch size = graph size) since the graph structure information might be partially lost through mini-batch partition, such a nature heavily constrains contrastive methods for scaling to large graphs.

Some recent works seek negative-sample-free methods to resolve the scalability issue by harnessing asymmetric structures~\citep{bgrl} or feature-level decorrelation objectives~\citep{cca-ssg}. However, these methods either lack enough theoretical justification~\citep{bgrl} or necessitate strong assumptions on the data distributions~\citep{cca-ssg}. Moreover, they still require data augmentations to generate two views of the input graph, albeit non-contrastive and free from negative sampling. Some other works construct positive examples using the target's $k$-nearest-neighbors (kNN) in the latent space~\citep{nnclr, msf, afgrl}. Nonetheless, the computation of nearest neighbors could be cumbersome, time-consuming, and, therefore hard to scale.

\textbf{Presented Work.} To cope with the dilemmas above, in this paper we introduce \textbf{\underline{Local}}ized \textbf{\underline{G}}raph \textbf{\underline{C}}ontrastive \textbf{\underline{L}}earning ({\sc{Local-GCL}}\xspace in abbreviation), a light and \textbf{augmentation-free} contrastive model for self-supervised node-level representation learning on graphs. {\sc{Local-GCL}}\xspace benefits from two key designs. \textbf{First}, it does not rely on data augmentation to construct positive pairs. Instead, inspired by the graph homophiliy theory~\citep{homo}, 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. \textbf{Second}, to deal with the quadratic complexity curse of contrastive loss (i.e., InfoNCE loss~\citep{cpc}), we propose a 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~\citep{rff, rff-survey, orf}. Such a design greatly improves the efficiency of our model.

We evaluate the proposed methods on seven public node classification benchmarks with various scales. The empirical results demonstrate that though not using any graph augmentations, our method achieves state-of-the-art performance on six of seven datasets. On the challenging \texttt{Ogbn-Arxiv}\xspace 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, {\sc{Local-GCL}}\xspace can also perform well on graphs with low homophily ratios.

\noindent\textbf{We summarize the highlights of this paper as follows:}
\begin{itemize}[topsep=0in,leftmargin=0em,wide=0em]
\item[\textbf{1)}]  We introduce {\sc{Local-GCL}}\xspace, 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.

\item[\textbf{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.

\item[\textbf{3)}] Experimental results show that without data augmentation and other cumbersome designs {\sc{Local-GCL}}\xspace achieves quite competitive results on a variety of graphs of different scales and properties. Furthermore, {\sc{Local-GCL}}\xspace demonstrates a better balance of model performance and efficiency than other self-supervised methods.
\end{itemize}

\section{Background and Related Works}
\subsection{Contrastive Representation Learning}
Inspired by the great success of contrastive methods in learning image representations~\citep{cpc, dim, cmc, moco, simclr}, recent endeavors develop similar strategies for node-level tasks in graph domain~\citep{dgi, mvgrl, grace, grace-ad}. Among graph contrastive learning methods, the most popular methods should be those based on the InfoNCE loss~\citep{cpc} due to their simple concepts and better empirical performance. InfoNCE-based graph contrastive learning methods, including GRACE~\citep{grace} and GCA~\citep{grace-ad} 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~\citep{mini-1}. The quadratic complexity also limits their applications to larger batch sizes/datasets.

\subsection{Augmentation-Free Self-supervised Learning on Graphs}
Besides graph contrastive learning~\citep{grace, grace-ad} and the similar two-branched models~\citep{bgrl, cca-ssg} 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~\citep{gae}, for example, learn node embeddings unsupervisedly through reconstructing the adjacency matrix, while GMI~\citep{gmi} maximizes 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~\citep{sugrl} employs two encoder models: one is a GCN, and the another is an MLP, 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~\citep{afgrl} and AF-GCL~\citep{afgcl-guarantee} treat nodes in the target node's multi-hop neighborhood as candidate positive examples and use well-designed similarity measures to select the most similar nodes as positive examples. {\sc{Local-GCL}}\xspace, by contrast, treats all neighbors equally without discrimination. This not only simplifies the model design but also offers a theoretical guarantee for the effectiveness of the proposed model. Empirical results also demonstrate that our method can achieve better performance than theirs. 
\subsection{Random Fourier Features}\label{sec-intro-rff}
Though InfoNCE-loss-based based methods are successful in self-supervised 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)~\citep{rff, rff-survey}. RFF is an effective technique for enhancing the scalability of kernel methods such as SVM, ridge regression~\citep{ridge_regression} and independence test~\citep{kernel_dependence, SSL-HSIC}. Also, recently, RFF has been adopted to develop linear Transformers by approximating the softmax attention~\citep{performer, rfa}. Given $d$-dimensional vectors $\bm{x}$ and $\bm{y}$ and a shift-invariant kernel $\kappa(\cdot)$, RFF constructs an explicit mapping $\psi$: $ \mathbb{R}^{d} \rightarrow \mathbb{R}^D$, such that $\kappa(\bm{x},\bm{y}) \approx \psi(\bm{x})^{\top}\psi(\bm{y})$, 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 $\kappa(\bm{x}, \bm{y}) = f(\bm{x} - \bm{y}) $, the Fourier transform $p$ of kernel $\kappa$ is $p(\bm{\omega}) = \frac{1}{2\pi} \int e^{-j\bm{\omega}'\Delta}k(\Delta)\mathrm{d}\Delta$, where $\Delta = \bm{x} - \bm{y}$. Then we could draw $D$ i.i.d. samples $\bm{\omega}_1, \cdots, \bm{\omega}_D \in \mathbb R^{d}$ from $p$, and $\psi(\bm{x})$ is given by:
\begin{equation}\label{eqn-rff1}
\begin{aligned}
    \psi(\bm{x}) = \frac{\left[\cos(\bm{\omega}_1^{\top}\bm{x}), \cdots, \cos(\bm{\omega}_D^{\top}\bm{x}), \sin(\bm{\omega}_1^{\top}\bm{x}), \cdots, \sin(\bm{\omega}_D^{\top}\bm{x})\right]^{\top}}{\sqrt{D}}.
\end{aligned}
\end{equation}
Let $\bm{W} = [\bm{\omega}_1, \cdots, \bm{\omega}_D] \in \mathbb{R}^{d\times D}$ be a linear transformation matrix, one may realize that the computation of Eq.~\ref{eqn-rff1} entails computing $\bm{W}^{\top}\bm{x}$. Specifically, when $\kappa(\cdot)$ is a standard Gaussian kernel (a.k.a., RBF kernel), each entry of $\bm{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 $\bm{W}$, so as to further reduce the computational cost~\citep{fastfood} or lower the approximation variance~\citep{orf}.

\section{Contrastive Learning on Graphs with InfoNCE Loss}\label{sec:background}
The InfoNCE~\citep{cpc} 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 a target data point $\bm{z}_{i}$, together with one positive embedding $\bm{z}_{i}^{+}$ and a set of negative embeddings $\{\bm{z}_{j}^{-}\}_{j=1}^{M-1}$, the InfoNCE loss aims at discriminating the positive pair $(\bm{z}_i, \bm{z}_i^{+})$ from the negative pairs $\{(\bm{z}_i, \bm{z}_j^{-}) \}_{j=1}^{M-1} $ via the following contrastive objective function:
\begin{equation}\label{eqn-infonce}
    \mathcal{L}_{\rm{InfoNCE}}(i) = -\log \frac{\exp({f(\bm{z}_i, \bm{z}_i^{+}) / \tau})}{\exp({f(\bm{z}_i, \bm{z}_i^{+}) / \tau})+\sum\limits_{j=1}^{M-1} \exp({f(\bm{z}_i^+, \bm{z}_j^{-})}/\tau)},
\end{equation}
where $f(\cdot, \cdot)$ is a similarity measure, usually implemented as the simple dot product $f(\bm{x}, \bm{y}) = \bm{x}^{\top}\bm{y}$~\citep{moco, simclr}, and $\tau$ is the temperature hyperparameter. Note that $\bm{z}_i, \bm{z}_i^{+}$ and $\bm{z}_i^{-}$ are all $\bm{\ell}_2$ normalized to have a \textbf{unit norm}, i.e., $\Vert \bm{z}_i \Vert_2^2 = 1$. In the context of node-level contrastive learning, each $\bm{z}_i$ denotes the embedding of node $i$, which is the output of an encoder model which takes the node feature $\bm{x}_i$ and the graph structure as input. As demonstrated in Eq.~\ref{eqn-infonce}, 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 on $M-1$  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 \textbf{positive examples} on graphs is through data augmentation. For example, MVGRL~\citep{mvgrl} uses graph diffusion to generate a fixed, augmented view of the studied graph. GCC~\citep{gcc} resorts to random walk to sample subgraphs of the anchored node as positive examples. GRACE~\citep{grace} and GCA~\citep{grace-ad} employ random graph augmentation--\textit{feature masking} and \textit{edge removing} to generate two views of the input graph before every training step. However, recent studies have shown that existing graph augmentations might unexpectedly change or lose the semantic information~\citep{afgrl, afgcl-guarantee} 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.

Compared with the construction of positive examples, \textbf{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~\citep{grace, grace-ad, cca-ssg}. However, the computation of the negative term of InfoNCE has $\mathcal{O}(|\mathcal{V}|^2d)$ time complexity and $\mathcal{O}(|\mathcal{V}|^2)$ memory complexity, where $|\mathcal{V}|$ is the number of nodes and $d$ is the embedding dimension. Note that the real-world graphs are usually very large, Eq.~\ref{eqn-infonce} can hardly be used in a full-graph training manner. One plausible remedy is to use down-sampling to zoom in on a fraction of negative samples for once feedforward computation. However, theoretical analysis demonstrates InfoNCE loss benefits from a large number of negative examples~\citep{poole2019variational}, and empirical observations show that reducing the number of negative examples leads to worse performance on downstream tasks~\citep{bgrl} (also see our experiments in Sec.~\ref{sec:exp-scale}). As a result, it would be promising to devise an 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 ({\sc{Local-GCL}}\xspace in short) to mitigate the above issues. {\sc{Local-GCL}}\xspace 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 as its positive examples; 2) we introduce a 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.

\section{Methodology}\label{sec:method}
\subsection{Anchoring Node Contrastive Learning on Topology}\label{sec-positive}
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 to 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~\citep{dansar, homo} and citation networks~\citep{homo-citation}) conform with the homophily phenomenon that similar nodes may be more likely to attach than dissimilar ones~\citep{lp, homo}.
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~\citep{beyond-homo}. This motivates us to directly treats all the first-order neighboring nodes of the target node as positive examples. Formally, the loss for the positive pairs of node $i$ can be written as  
\begin{equation}\label{eqn:pos}
    \mathcal{L}_{\rm pos}(i) = -\log \sum\limits_{j \in \mathcal{N}(i)} \exp (\bm{z}_i^{\top}\bm{z}_j / \tau) / |\mathcal{N}(i)|.
\end{equation}
For the negative term, we can directly use all nodes in the graph as negative examples. Then the loss for the negative pairs of node $i$ can be formulated as:
\begin{equation}\label{eqn:neg}
  \mathcal{L}_{\rm neg}(i) = \log \sum\limits_{k \in \mathcal{V}} \exp (\bm{z}_i^{\top}\bm{z}_k / \tau).  
\end{equation}
The overall loss function is simply the sum of $\mathcal{L}_{\rm pos} $ and $\mathcal{L}_{\rm neg}$, then averaged over all nodes:
\begin{equation}\label{eqn:loss-model}
    \mathcal{L}_{\rm {\sc{Local-GCL}}\xspace} = -\frac{1}{|\mathcal{V}|} \sum\limits_{i=1}^N  \log \frac{\sum\limits_{j \in \mathcal{N}(i)}  \exp (\bm{z}_i^{\top}\bm{z}_j/\tau) / |\mathcal{N}(i)|}{\sum\limits_{k \in \mathcal{V}} \exp (\bm{z}_i^{\top}\bm{z}_k /\tau)} .
\end{equation}
Then we'd like to provide a theoretical analysis of the effectiveness of 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 a graph by $\mathcal{G} = (\mathcal{V}, \mathcal{E})$, where $\mathcal{V}$ is the node st and $\mathcal{E}$ is the edge set. The adjacency matrix and degree matrix are denoted by $\bm{A}$ and $\bm{D}$, respectively. Let $\tilde{\bm{A}} = \bm{D}^{-1/2}\bm{A}\bm{D}^{-1/2}$ be the symmetric normalized adjacency matrix, and $\bm{L} = \bm{I} - \tilde{\bm{A}}$ be the symmetric normalized graph Laplacian matrix. Denote the eigenvalues of $\bm{L}$ in Zn ascending order by $\{\lambda_i\}_{i=1}^{|\mathcal{V}|}$. Finally we denote the node embedding matrix $\bm{Z} = \{ \bm{z}_i \}_{i=1}^{|\mathcal{V}|} \in \mathbb{R}^{|\mathcal{V}|\times d} $ and the one-hot label matrix by $\bm{Y} = \{ \bm{y}_i \}_{i=1}^{|\mathcal{V}|} \in \mathbb{R}^{|\mathcal{V}|\times c}$. Without loss of generality we assume $d \le |\mathcal{V}|$.

We then give a formal definition of graph homophily ratio $\phi$:
\begin{definition}\label{def:homo_ratio}
(Graph Homophily Ratio)
For a graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ with adjacency matrix $\bm{A}$,  its  homophily ratio $\phi$ is defined as the probability that two connected nodes share the same label:
\begin{equation}\label{eqn:homo-ratio}
    \phi = \frac{\sum_{i,j \in \mathcal{V}} A_{ij} \cdot \mathbbm{1}[{\bm{y}_i = \bm{y}_{j}}]}{\sum_{i,j \in \mathcal{V}} A_{ij}} = \frac{\sum_{i,j \in \mathcal{V}} A_{ij} \cdot \mathbbm{1}[{\bm{y}_i = \bm{y}_{j}}]}{|\mathcal{E}|}
\end{equation}
\end{definition}

 With the conclusions in \citet{contrastive-spectral} and \citet{contrastive-guarantee}, which build connections between contrastive loss and spectral method, the following theorem guarantees the linear classification error of the embeddings learned from {\sc{Local-GCL}}\xspace:
\begin{theorem}\label{theorem:error}
Let $\bm{Z}^*$ be the global minimizer of  Eq.~\ref{eqn:loss-model}, then for any labeling function $\hat{y}: \mathbb{V} \rightarrow \mathbb{R}^{c}$ with graph homophily $\phi$, there exists a linear classifier $\bm{B}^* \in \mathbb{R}^{d \times c}$ with norm $\Vert \bm{B}^* \Vert_F \le 1/(1-\lambda_d) $ such that
\begin{equation}\label{eqn:error}
    \mathbb{E}_{i \in \mathcal{V}} \left[\Vert \hat{\mathop{y}}(i)  - {\bm{B}^*}^{\top}\bm{z}_i^{*} \Vert_2^2 \right] \le \frac{1-\phi}{\lambda_{d+1}}
\end{equation}
\end{theorem}
See proof in Appendix~\ref{appendix-proof-error}. Theorem~\ref{theorem:error} demonstrates that the linear classification accuracy of the learned embeddings through {\sc{Local-GCL}}\xspace is bounded by the homophily ratio $\phi$ and the $d+1$ smallest eigenvalue $\lambda_{d+1}$. Specifically, the larger the homophily ratio, the smaller the prediction error. Besides, Eq.~\ref{eqn:error} indicates that a larger embedding dimension can lead to better classification accuracy, which is also validated empirically in Sec.~\ref{sec-experiments}.

\subsection{Fast and Efficient Approximation for the Negative Loss}\label{sec-negative}
We next probe into how to reduce the computation complexity of the negative loss term $\mathcal{L}_{\rm neg} = \sum\limits_{i \in \mathcal{V}} \mathcal{L}_{\rm neg} (i) $, for which the $|\mathcal{V}|^2$ pair-wise similarities can be efficiently and precisely approximated with efficient computation methods for kernel functions~\citep{rff, rff-survey}.

We notice that the pair-wise similarity (in dot-product format) in Eq.~\ref{eqn:neg} is essentially a Gaussian kernel function, i.e.,
\begin{equation}
\exp(\bm{z}_i^{\top}\bm{z}_j/\tau)  = \exp(\frac{2-\Vert \bm{z}_i - \bm{z}_j\Vert_2^2}{2\tau}) = e* \exp(\frac{-\Vert \bm{z}_i - \bm{z}_j \Vert}{2\tau}) = e\cdot\kappa^{G}(\bm{z}_i, \bm{z}_k ; \sqrt{\tau)},
\end{equation}
where $\kappa^{G}(\bm{z}_i, \bm{z}_k ; \sqrt{\tau)}$ is the Gaussian kernel function with bandwidth $\sqrt{\tau}$. This motivates us to seek for a projection function ${\psi}(\bm{x}) (\mathbb{R}^{d} \rightarrow \mathbb{R}^{2D})$ such that $\kappa^{G}(\bm{x}, \bm{y};\sqrt{\tau}) \approx {\psi}(\bm{x})^{\top}{\psi}(\bm{y})$. Then we are able to use a surrogate negative loss function as a remedy of the previous one:
\begin{equation}\label{eqn-decompose}
    \mathcal{L}_{{neg}} \triangleq \frac{1}{|\mathcal{V}|} \sum_{i \in \mathcal{V}} \left(\log {\sum_{j\in\mathcal{V} } {\psi}(\bm{h}_i)^{\top} {\psi}(\bm{h}_j)}\right) =  \frac{1}{|\mathcal{V}|} \sum_{i\in \mathcal{V}} \left( \log \left({ {\psi}(\bm{h}_i)^{\top} \sum_{j\in \mathcal{V} } {\psi}(\bm{h}_j)}\right) \right).
\end{equation}
Once we obtain all the projected vectors $\{\bm{\psi}(\bm{h}_{i})\}_{i=1}^{|\mathcal{V}|}$, the summation term $\sum_{j \in \mathcal{V}} {\psi}(\bm{h}_j)$ in Eq.~\ref{eqn-decompose} could be calculated within $\mathcal{O}(|\mathcal{V}|D)$ in advance (where $D$ is the dimension of projected vectors). In addition to the $\mathcal{O}(|\mathcal{V}|D)$ cost for computing the loss, the overall computational cost will be $\mathcal{O}(|\mathcal{V}|D + |\mathcal{V}|D) = \mathcal{O}(VD)$, which is linear to the number of nodes. Then we discuss how to formulate the projection function ${\psi}(\cdot)$ below.

\paragraph{Linear-Order Projection}\label{sec-rff}
The theory of Random Fourier Features~\citep{rff} introduced in Sec.~\ref{sec-intro-rff} demonstrates that a Gaussian kernel function $\kappa^{G}(\bm{x},\bm{y} ; \sqrt{\tau})$ could be unbiasedly estimated with $\psi(\bm{x})^{\top}{\psi}(\bm{y})$, and the projection function $\psi(\bm{x})$ is defined as follows:
\begin{equation}\label{eqn-rff2}
    \psi(\bm{x}) = \frac{[\cos(\bm{W}^{\top}\bm{x}), \sin(\bm{W}^{\top}\bm{x})]}{\sqrt{D}} = \frac{\left[\cos(\bm{\omega}_1^{\top}\bm{x}), \cdots, \cos(\bm{\omega}_D^{\top}\bm{x}), \sin(\bm{\omega}_1^{\top}\bm{x}), \cdots, \sin(\bm{\omega}_D^{\top}\bm{x})\right]^{\top}}{\sqrt{D}}.
\end{equation}
where $\bm{W} = [\bm{\omega}_1^{\top}, \cdots, \bm{\omega}_D^{\top}]$, and each $\bm{\omega}_i$ is sampled from the Gaussian distribution $p(\bm{\omega}) = \mathcal{N} (\bm{0}, \tau\bm{I})$. $D$ is the number of total samples. Usually, the larger the sampling number $D$ is, the more accurate the approximation will be:
\begin{theorem}\label{theorem-rff}
Let $\{\bm{\omega}_i\}_{i=1}^{D}$ be i.i.d samples from Gaussian distribution $\mathcal{N}(\bm{0}, \tau\bm{I})$, and $ \psi(\bm{x}) $ is given by Eq.~\ref{eqn-rff2}, then with probability at least $1-\varepsilon$, the approximation error $\Delta = |{\psi}(\bm{h}_i)^{\top} {\psi}(\bm{h}_j) - \kappa^{G} (\bm{h}_i, \bm{h}_j) | $ will be bounded by $\mathcal{O}\left({\frac{1-\exp(-4/\tau)}{\sqrt{2D\varepsilon}}}\right)$.
\end{theorem}
Theorem~\ref{theorem-rff} suggests that the Gaussian kernel function could be accurately approximated with Random Fourier Features as long as we sample enough number of linear transformation vectors $\bm{\omega}$ 
(i.e., $D$ should be large enough). Note that the computation of linear projection $ \bm{W}\bm{h}_i$ ($i = 1 \in \mathcal{V}$) requires additional $\mathcal{O}(|\mathcal{V}|dD)$ time. A large number of the projection dimension $D$ makes the computation of Eq.~\ref{eqn-decompose} still expensive for high-dimensional data.

\paragraph{Log-Order Projection}\label{sec-sorf}
To handle the above issues, we resort to Structured Orthogonal Random Features (SORF)~\citep{orf}, another Random Feature technique that imposes structural and orthogonality on the linear transformation matrix $\bm{W}$. Different from the vanilla RFF which directly samples linear transformation vectors $\bm{\omega}$ form normal distribution to construct the transformation matrix $\bm{W}_{\rm rff} = [\bm{\omega}_1^{\top}, \cdots,  \bm{\omega}_D^{\top}] \in \mathbb{R}^{d\times D}$, SORF assumes $D = d$ and constructs a structured orthogonal transformation matrix through the continued product of a series of structured matrixes $
     \bm{W}_{\rm{sorf}} = \frac{\sqrt{d}}{\sigma} \bm{HD}_1\bm{HD}_{2}\bm{HD}_{3}$,
where $\bm{D}_i \in \mathbb{R}^{d\times d}, i = 1, 2, 3 $, are diagonal ``sign-ﬂipping” matrices, with each diagonal entry sampled from the Rademacher distribution, and $\bm{H} \in \mathbb{R}^{d \times d}$ is the normalized Walsh-Hadamard matrix. By this definition, the projected dimension is restricted to $d$, 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 $\mathcal{O}(|\mathcal{V}|D\log d)$ time using fast Hadamard transformation~\citep{hadamard}, and hardly requires extra memory cost using in-place operations~\citep{orf}. 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 {\sc{Local-GCL}}\xspace denotes our method equipped with SORF to approximate the negative loss.
\section{Experiments}\label{sec-experiments}
We conduct experiments to evaluate the proposed method by answering the following questions:
\begin{itemize}
    \item \textbf{RQ1}: How does {\sc{Local-GCL}}\xspace perform compared with other self-supervised learning methods on graphs with different properties?
    \item \textbf{RQ2}: How do the specific designs of {\sc{Local-GCL}}\xspace, such as the embedding dimension and projection dimension, affect its performance?
    \item \textbf{RQ3}: What's the empirical memory and time consumption of {\sc{Local-GCL}}\xspace compared with prior works? Is {\sc{Local-GCL}}\xspace able to scale to real-world large-scale graphs with satisfying performance?
\end{itemize}

\subsection{Experimental Setups}
\paragraph{Datasets.}
We evaluate {\sc{Local-GCL}}\xspace on various datasets with different scales and properties. Following prior works~\citep{grace, cca-ssg} on self-supervised node representation learning, we adopt the $7$ common small-scale benchmarking graphs: \texttt{Cora}\xspace, \texttt{Citeseer}\xspace, \texttt{Pubmed}\xspace, \texttt{Amazon-Computer}\xspace, \texttt{Amazon-Photo}\xspace, \texttt{Coauthor-CS}\xspace, and \texttt{Coauthor-Physics}\xspace. To evaluate the performance and scalability of {\sc{Local-GCL}}\xspace on larger graphs, we also adopt \texttt{Ogbn-Arxiv}\xspace with about 170k nodes, on which a lot of methods fail to scale due to memory issues. Furthermore, we adopt three widely used heterophily graphs, \texttt{Chameleon}\xspace, 
\texttt{Squirrel}\xspace, and \texttt{Actor}\xspace to evaluate the generalization ability of {\sc{Local-GCL}}\xspace on graphs where the graph homophily assumption does not hold. The detailed introduction and statistics of these datasets are presented in Appendix~\ref{appendix-dataset}
\paragraph{Baselines.}
We consider representative prior self-supervised models for comparison. We classify previous methods into two types: 1) \textbf{Augmentation-based}, which uses data augmentations to generate positive or negative pairs. 2) \textbf{Augmentation-free}, which uses other information rather than any form of data augmentation to create self-supervised signals. For augmentation-based baselines, we consider DGI~\citep{dgi}, MVGRL~\citep{mvgrl}, GRACE~\citep{grace}, GCA~\cite{grace-ad}, BGRL~\citep{bgrl} and CCA-SSG~\citep{cca-ssg}. For augmentation-free baselines, we consider GMI~\citep{gmi}, SUGRL~\citep{sugrl}, AFGRL~\citep{afgrl}, AF-GCL~\citep{afgcl-guarantee}.
\paragraph{Evaluation Protocols.}
 We follow the linear evaluation scheme in previous works~\citep{dgi, mvgrl, grace-ad, cca-ssg}: For each dataset, i) we first train the model on all the nodes in a graph without supervision by optimizing the objective in Eq.~\ref{eqn:loss-model}; 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., a 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. 
\paragraph{Implementation Details.}
The model is implemented with PyTorch and DGL~\citep{dgl}. All experiments are conducted on an NVIDIA V100 GPU with 16 GB memory unless specified. We adopt \texttt{structure-net}\footnote{\url{https://github.com/HazyResearch/structured-nets}} to do fast Walsh-Hadamard transformation, which enables much faster forward and backward computation with CUDA accelerations.
We use the Adam optimizer~\citep{adam} for both self-supervised pretraining training and linear evaluation using logistic regression. Following previous works~\citep{grace-ad, cca-ssg, bgrl, afgcl-guarantee}, we the random 1:1:8 split for \texttt{Amazon-Computer}\xspace, \texttt{Amazon-Photo}\xspace, \texttt{Coauthor-CS}\xspace and \texttt{Amazon-Computer}\xspace, and use the public recommended split for the remaining datasets. For each experiment, we report the average test accuracy with the standard deviation over 20 random initialization. If not specified, we use a two-layer GCN model as the encoder to generate node embeddings. More detailed hyperparameter settings for each dataset can be found in Appendix~\ref{appendix:hyper}
\subsection{Numerical Results}\label{exp-major}

\paragraph{Results on common graphs.}
We first report the results of node classification tasks on small-scale citation networks and social networks in Table~\ref{tbl-exp-main}. We see that although not relying on data augmentations or other complicated operations to create self-supervised signal, {\sc{Local-GCL}}\xspace performs competitively with our self-supervised baselines, achieving state-of-the-art performance in 6 out of 7 datasets. It is worth noting that the competitive InfoNCE-loss based contrastive methods GRACE and GCA suffer from OOM on \texttt{Coauthor-Physics}\xspace datasets due to the $\mathcal{O}(|\mathcal{V}|^2d)$ space complexity, while {\sc{Local-GCL}}\xspace can avoid such an issue thanks to the linear approximation of the negative loss.


\begin{table*}[tb!]
	\centering
	\caption{Comparison of self-supervised methods on benchmarking graphs. We group each method according to whether it relies on graph augmentation.}
	\label{tbl-exp-main}
	\small
	\begin{threeparttable}
       
        \scalebox{0.87}
        {
		\begin{tabular}{l|lccccccc}
			\toprule[1.0pt]
		       & Methods & \texttt{Cora}\xspace & \texttt{Citeseer}\xspace & \texttt{Pubmed}\xspace & \texttt{Computer}\xspace & \texttt{Photo}\xspace & \texttt{CS}\xspace & \texttt{Physics}\xspace  \\
			\midrule
              \multirow{6}{*}{\rotatebox{90}{Aug-based}} & DGI & 82.3$\pm$0.6  & 71.8$\pm$0.7 & 76.8$\pm$0.6 & 83.95$\pm$0.47  & 91.61$\pm$0.22 & 92.15$\pm$0.63 & 94.51$\pm$0.52\\
                & MVGRL & 83.5$\pm$0.4  & 73.3$\pm$0.5 & 80.1$\pm$0.7 & 87.52$\pm$0.11  & 91.74$\pm$0.07 & 92.11$\pm$0.12 & 95.33$\pm$0.03  \\
                & GRACE & 81.9$\pm$0.4 & 71.2$\pm$0.5 & 80.6$\pm$0.4 & 86.25$\pm$0.25  & 92.15$\pm$0.24 & 92.93$\pm$0.01 & OOM$^*$ \\
                & GCA & 82.3$\pm$0.4 &  72.1$\pm$0.4 &  80.7$\pm$0.5 & 87.85$\pm$0.31  & 92.49$\pm$0.09 & 93.10$\pm$0.01 & OOM   \\
                & BGRL & 82.7$\pm$0.6 & 71.1$\pm$0.8  & 79.6$\pm$0.5 & 89.69$\pm$0.37 & 93.07$\pm$0.28 & 92.59$\pm$0.17 & 95.48$\pm$0.08 \\
                & CCA-SSG & 84.2$\pm$0.4 & 73.1$\pm$0.3 & {81.6}$\pm${0.4}   & {88.74}$\pm${0.28} & {93.14}$\pm${0.14} & {93.31}$\pm${0.22} & 95.38$\pm$0.06\\
                \midrule
                \multirow{5}{*}{\rotatebox{90}{Aug-free}}  & GMI & 82.4$\pm$0.6  & 71.7$\pm$0.2 & 79.3$\pm$1.0 & 84.22$\pm$0.52 & 90.73$\pm$0.24 & OOM & OOM \\
                & SUGRL & 83.4$\pm$0.5 & 73.0$\pm$0.4 & 81.9$\pm$0.3 & 
                {88.93}$\pm${0.21} & 93.07$\pm$0.15 & 92.83$\pm$0.23 & 95.38$\pm$0.11 \\
                 & AFGRL & 81.3$\pm$0.2 & 68.7$\pm$0.3 & 80.6$\pm$0.4 & 
                \textbf{89.88}$\pm$\textbf{0.33} & \textbf{93.22}$\pm$\textbf{0.28} & 93.27$\pm$0.17 & OOM   \\
                & AF-GCL & 83.2$\pm$0.2  & 72.0$\pm$0.4 & 79.1$\pm$0.8 & 
                {89.68}$\pm${0.19} & 92.49$\pm$0.31 & 91.92$\pm$0.10 & 95.12$\pm$0.15   \\
                & {\sc{Local-GCL}}\xspace & \textbf{84.5}$\pm$\textbf{0.4} & \textbf{73.6}$\pm$\textbf{0.4} & \textbf{82.1}$\pm$\textbf{0.5}  & 88.81$\pm$0.37 & 
                \textbf{93.25}$\pm$\textbf{0.40} & \textbf{94.90}$\pm$\textbf{0.19}  & \textbf{96.33}$\pm$\textbf{0.13} \\
		\bottomrule[1.0pt]
		\end{tabular}
        }
		\begin{tablenotes}
        \item[$*$] OOM indicates out-of-memory on an NVIDIA-V100 GPU of 16G memory.
        \end{tablenotes}
	\end{threeparttable}
\end{table*}

\begin{figure}[t]
    \begin{minipage}[h]{0.45\linewidth}
    \vspace{0pt}
    \centering
    \captionof{table}{Performance on \texttt{Ogbn-Arxiv}\xspace dataset. As recommended, we report both the validation accuracy and test accuracy.}
    \label{tbl-exp-arxiv}
    \small
   
    {   
	\begin{threeparttable}
       
        \scalebox{1.0}
        {
	\begin{tabular}{lcc}
		\toprule[1.0pt]
             Methods & Validation & Test \\
            \midrule
            DGI  & 71.21$\pm$0.23  & 70.32$\pm$0.25    \\
            GMI & OOM & OOM \\
            MVGRL  & OOM   & OOM \\
            GRACE  & OOM   & OOM \\
            GCA & OOM   & OOM \\
            BGRL & \textbf{72.71}$\pm$\textbf{0.22} & \textbf{71.54}$\pm$\textbf{0.17}  \\
            CCA-SSG & 72.31$\pm$0.18 & 71.21$\pm$0.20 \\
            AFGRL & OOM & OOM \\
            \midrule 
            {\sc{Local-GCL}}\xspace & 72.29$\pm$0.25 & 71.34$\pm$0.25 \\
            \bottomrule[1.0pt]
	\end{tabular}
		}

	\end{threeparttable}
	}
    \end{minipage}
        \begin{minipage}[h]{0.5\linewidth}
        \vspace{0pt}
        \centering
        \includegraphics[width=1.0\textwidth,angle=0]{Fig/scale.pdf}
        \vspace{-15pt}
        \caption{Test accuracy and training time comparison of {\sc{Local-GCL}}\xspace, BGRL, CCA-SSG and GRACE with subsampling.}
        \label{fig:scale}
    \end{minipage}
\end{figure}
\paragraph{Results on Ogbn-Arxiv.} Then, we evaluate the effectiveness and scalability of {\sc{Local-GCL}}\xspace on large-scale graphs taking \texttt{Ogbn-Arxiv}\xspace as an example. Following the practice in~\citet{bgrl}, we expand the encoder to a 3-layer GCN model. We report the validation and test accuracy of baseline models and ours in Table~\ref{tbl-exp-arxiv}. As demonstrated, many baseline methods cannot run in a full graph manner (on a GPU with 16GB memory). Compared with other scalable methods, 
{\sc{Local-GCL}}\xspace can give a competitive performance on \texttt{Ogbn-Arxiv}\xspace.

\paragraph{More empirical results and ablation studies.} We conduct further experiments and present the results in Appendix~\ref{appendix:exp} due to the space limit: 1) the performance on heterophilic graphs (Appendix~\ref{appendix:hetero}); 2) the effect of reweighting the importance of positive examples (Appendix~\ref{appendix:pos}); 3) applying the positive example construction strategy to non-contrastive methods (Appendix~\ref{appendix:free}); 4) combining with hard-negative sampling methods (Appendix~\ref{appendix:hard}).

\subsection{Scalability Comparison}\label{sec:exp-scale}
To evaluate the scalability of {\sc{Local-GCL}}\xspace on real-world datasets, we compare the total training time and accuracy with state-of-the-art scalable methods BGRL~\citep{bgrl} and CCA-SSG~\citep{cca-ssg} on Arxiv dataset. To further justify the necessity of adopting a large number of negative examples, we additionally adopt GRACE~\citep{grace}, a powerful non-scalable contrastive model. We use sub-sampling strategy to randomly sample a fixed number of negative examples every epoch so that the GRACE model could be fit into a GPU with 16G memory. In Fig.~\ref{fig:scale} we plot the model's performance and the corresponding training time of different methods. We can see that compared with scalable methods CCA-SSG and BGRL, {\sc{Local-GCL}}\xspace achieves comparable performance but with the least training time. We can also observe that although reducing the number of negative examples ($k$ in Fig.~\ref{fig:scale}) can enable the model to be trained much faster, the performance drop is significant, which cannot make up for the efficiency benefit. Furthermore, if we continue to use an even larger number of negative examples, GRACE will soon run out of memory. This result demonstrates that {\sc{Local-GCL}}\xspace can better balance the training efficiency and model performance.

\subsection{Sensitivity to embedding/projection dimensions}

\begin{wrapfigure}[22]{l}{0.5\textwidth}
\begin{center}
    \includegraphics[width=0.5\textwidth,angle=0]{Fig/dim.pdf}
    \caption{Sensitivity analysis of embedding dimension $d$ and projection dimension $D$.}
    \label{fig:sensitivity}
\end{center}
\end{wrapfigure}

As demonstrated in Theorem~\ref{theorem:error} and Sec.~\ref{sec-negative}, the embedding dimension $d$ and projection dimension $D$ should be two critical hyperparameters affecting the model's performance. In this section, we test {\sc{Local-GCL}}\xspace' sensitivities with respect to them in Fig.~\ref{fig:sensitivity}. The observations are two-fold: 1) Similar to other self-supervised learning models~\citep{mvgrl, grace-ad, cca-ssg, afgrl}, {\sc{Local-GCL}}\xspace that benefit from a large embedding dimension (e.g., $512$), {\sc{Local-GCL}}\xspace's performance also grows as we increase the embedding dimension $d$. However, the optimal embedding dimension for {\sc{Local-GCL}}\xspace is even larger, e.g., $2048$ on \texttt{Cora}\xspace and \texttt{Citeseer}\xspace (note that other methods do not benefit from such a large embedding dimension). This could be justified by our analysis in Theorem~\ref{theorem:error}, which demonstrates that with a larger embedding dimension, the bound of the prediction error will become lower (because the target eigenvalue $\lambda_{d+1}$ becomes larger). 2) Increasing the projection dimension can lead to better but minimal improvement. This indicates that in practice, {\sc{Local-GCL}}\xspace can perform quite well without using a huge projection $D$.


\section{Conclusions} 
In this paper, we have presented {\sc{Local-GCL}}\xspace, a simple, light-weighted yet effective contrastive model for self-supervised node representation learning. {\sc{Local-GCL}}\xspace incorporates two orthogonal techniques to address two key issues in contrastive learning on graph data: reliance on data augmentation and scalability, respectively. The former involves a new definition of 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 an 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.

{
\bibliographystyle{iclr}

\section{General response to all reviewers}
We thank all the reviewers for their thorough comments and valuable opinions/suggestions. We've uploaded the revised version, which has addressed most of the concerns. Here we'd like to summarize the major changes in the revised version:

1) We emphasize the preconditions/assumptions of Lemma 1. Our Lemma 1 focuses on the Laplacian regularization loss, neglecting the impact of supervised loss. Besides, we assume a linear model to simplify the proof.

2) We replot Fig.2, focusing on the top-$8$ eigenvalues instead of all the $512$ eigenvalues, to better demonstrate the differences in different subfigures. Besides, we add another three subfigures in Fig.2, showing that at the same epoch, the drop rate of eigenvalues will increase as the trade-off hyperparameter $\lambda$ increases.

3) We add more content in Appendix: 1) In Appendix C.5, we conduct a sensitivity analysis of the trade-off hyperparameters $\alpha$ and $\beta$ in Eq.7. 2) in Appendix E, we provide more analysis of why dimensional collapse is not beneficial for linear classification.

4) We fix some typos and misleading symbols that might affect the reading.

Besides, we have provided individual responses for each reviewer, which answer each question detailedly. We hope our responses can address your concerns. 

\section{Responses to Reviewer q5an}
We thank the reviewer for the thorough comments and constructive suggestions, which will be a great help for us to improve our work. We are glad to address your concerns here:

\textbf{Clarity}

Q1: Typos that affect reading.

A1: We've fixed these typos and unclear equations/definitions in the revised version. 

\textbf{Soundness of the theoretical presentation}

Q2: Whether to cover positive terms in the denominator of the objective function.

A2: This is an interesting and important question which does worth discussing. First, let's review the InfoNCE loss [1], and the NT-Xent loss used in SimCLR [2]. Given embeddings of two views: $\{(\mathbf{z}^A_i, \mathbf{z}^B_i)\}_{i=1}^N$, and consider the loss for view A (for view B is just symmetric):

InfoNCE:
$$
\mathcal{L}_{InfoNCE} = -\sum\limits_{i=1}^N \log \frac{\exp(\mathbf{z}_i^A\cdot \mathbf{z}_i^B / \tau)}{\sum\limits_{j=1}^N \exp(\mathbf{z}_i^A\cdot \mathbf{z}_j^B / \tau)}
$$

NT-Xent in SimCLR:
$$
\mathcal{L}_{SimCLR} = -\sum\limits_{i=1}^N \log \frac{\exp(\mathbf{z}_i^A\cdot \mathbf{z}_i^B / \tau)}{\sum\limits_{j = 1}^N \exp(\mathbf{z}_i^A\cdot \mathbf{z}_j^B / \tau) + \sum\limits_{j \neq i} \exp(\mathbf{z}_i^A\cdot \mathbf{z}_j^A / \tau)}.
$$




In both the original InfoNCE loss and NT-Xent loss in SimCLR, the positive loss is covered in the denominator together with the negative ones. This is not a casual operation but is due to its theoretical connection to the Mutual Information maximization principle. In the CPC paper[1], the authors show that the InfoNCE loss is a lower bound of mutual information. Concretely, denote the random variables of two views' embeddings by $Z^A$ and $Z^B$ respectively, the InfoNCE tries to maximize the Mutual Information between $Z^A$ and $Z^B$, i.e., $I(Z^A, Z^B)$, or the KL-Divergence between two distributions $p(Z^A, Z^B)$, $p(Z^A)p(Z^B)$. From this perspective, the numerator term in InfoNCE does represent a positive example, while the denominator term means two embeddings randomly and uniformly sampled from two marginal distributions, so it is necessary to cover a positive term together with true negative ones in the denominator, and this is the reason that the negative loss is calculated on all nodes in Eq.9, although we believe removing the positive loss from the denominator will not make significant differences to the model performance.

Besides, it is easy to implement if we would like to cover only nodes that do not belong to a given node's neighborhood. As noted in the paper, for a target node $i$, we compute its positive loss by:
$$
    \mathcal{L}_{\rm pos}(i) = -\log \sum\limits_{j \in \mathcal{N}(i)} \exp (\mathbf{z}_i^{\top}\mathbf{z}_j / \tau) / |\mathcal{N}(i)|,
$$
and original the negative loss is:
$$
     \mathcal{L}_{\rm neg}(i) = \log \sum\limits_{k \in \mathcal{V}} \exp (\mathbf{z}_i^{\top}\mathbf{z}_k / \tau). 
$$
If we only consider nodes do not belong to the given node's neighborhood:
$$
     \mathcal{L}'_{\rm neg}(i) = \log \sum\limits_{k \notin \mathcal{N}(i)} \exp (\mathbf{z}_i^{\top}\mathbf{z}_k / \tau). 
$$

As the $\log$ operation is applied at the last step, we neglect it, and we can find that:
$$
     \sum\limits_{k \notin \mathcal{N}(i)} \exp (\mathbf{z}_i^{\top}\mathbf{z}_k / \tau) =  \underbrace{\sum\limits_{k \in \mathcal{V}} \exp (\mathbf{z}_i^{\top}\mathbf{z}_k / \tau)}_{\exp(\mathcal{L}_{neg}(i))} -\underbrace {\frac{\sum\limits_{j \in \mathcal{N}(i)} \exp (\mathbf{z}_i^{\top}\mathbf{z}_j / \tau)}{  |\mathcal{N}(i)|}}_{\exp(-\mathcal{L}_{pos}(i))} \cdot {|\mathcal{N}(i)|} . 
$$

As a result, the new negative term can be directly derived from the original negative term and positive term without additional computational cost. Based on this, we further conduct experiments using the new negative loss that excludes neighboring nodes. We compare the results in the table below (we use exactly the same set of hyperparameters and results are averaged over 20 random trials):

|  Cora   | Citeseer  | Pubmed |

|  ----   | ----  | | ----  |

| LocalGCL(origin)  | 84.5$\pm$0.4 | 73.6$\pm$0.4 |82.1$\pm$0.5|

| LocalGCL(new)  |  84.6$\pm$0.4 | 73.5$\pm$0.5 |81.9$\pm$0.5|

The results are within our expectations: excluding the positive terms from the denominator  makes little difference to the model performance. Though on some datasets, it can lead to marginal improvement, it might hurt the performance a little for others. Besides, this result might also indicate that forcing the embeddings to distribute uniformly in the latent space may be more beneficial than simply separating negative pairs [3].

The reviewer also mentions that it would be better to discuss the error changes of two implementations w.r.t. the average degree v.s. graph size. We agree with the reviewer that this will be an interesting topic. However, considering that in the studied datasets, the average (even the largest) node degree is much smaller than the total number of nodes, it is likely that we cannot get a meaningful result. A more appropriate study case should be on synthetic datasets where we can control the graph size and avg. node degrees, but it is out of the range of this paper.


Q3: Unclear assumptions or boundary conditions in the proof of Theorem 1:

A3: For the compatibility of approximated Local-GCL's loss and the original InfoNCE loss, we didn't cover this discussion in the paper because RFF is just making numerical approximations to reduce the computational complexity without affecting the optimal solution of the loss. The proof is trivial: according to Lemma 3 in Appendix A.2, the Gaussian kernel function $e^{-\Vert \mathbf{x} - \mathbf{y} \Vert_2^2 / 2\tau}$ can be unbiasedly approximated with RFF. As a result, Eq. (9) is also an unbiased approximation of the denominator of Eq. (5). As we didn't approximate the positive terms of Eq. (5), the approximated Local-GCL loss should be an unbiased estimation of Eq.(5). As a result, when the surrogate loss function reaches its global minimum, Eq. (5) also reaches its global minimum.


For Lemma 2 (eigenvalues), we are sorry for the typo that incorrectly describes the order of eigenvalues. Actually, it should be an **ascending order** so that $\lambda_1$ is the smallest one, and $\lambda_{|\mathcal{V}|}$ is the largest one. This is consistent with the analysis below Eq.(7), that the larger the embedding dimension $d$ is (the larger $\lambda_d$ is), the smaller the linear classification error bound can be. We've fixed this typo in the revised version.


For the boundary conditions, we do assume that the maximum dimension $d$ should be no larger than the number of nodes in the graph $|\mathcal{V}|$ (see the last paragraph before the definition of graph homophily ratio). Considering that most studied graphs have at least tens of thousands of nodes, which is much larger than the embedding dimension actually used, this assumption is reasonable.  For the number of connected components $k$, you might want to mean $d < k$ because in Theorem 1 $\lambda_d$ is d-th smallest eigenvalue, and in this case, $\lambda_{d+1}$ = 0. However, even in this extreme case, Theorem 1 is still correct as the error will be bounded by infinity when $\lambda_{d+1} = 0$. 

\textbf{Concerns about experimental results}

Q4: Which of the two model improvements contributes to the performance?

A4: We would like to emphasize that the utilization approximation of the negative loss is just to reduce the computational complexity, and it will not bring performance improvement. All the performance improvements are actually brought by the positive example of construction using neighbors. To better demonstrate this, we further provide the results of directly using Eq.(5) as the objective function in the following table (we add this table in the revised version):


|  Cora   | Citeseer  | Pubmed |

|  ----   | ----  | | ----  |

| w/o approx.  | 84.5$\pm$0.4 | 73.6$\pm$0.4 |82.2$\pm$0.5|

| Local-GCL(RFF)  |  84.3$\pm$0.5| 73.6$\pm$0.7 |81.9$\pm$0.7|

| Local-GCL(SORF)  |  84.5$\pm$0.4 | 73.6$\pm$0.5 |82.1$\pm$0.5|

In this table, w/o approx denotes the performance when directly using Eq.(5) as the loss function. The results above demonstrate that using approximated loss not only brings no improvements but may also cause a slight performance drop. This is because there is randomness in the approximation, which can only be reduced instead of eliminated. Besides, SORF shows better performance than RFF, which is because SORF has a much smaller approximation variance than RFF, when using the same projection dimension.

Q5: Highlight the strongest baseline in Photo dataset.

A5: We thank the reviewer for this suggestion. AFGRL's mean performance on Photo is close to ours but has a smaller deviation. We have highlighted their results as well in the revised version as suggested.


Q6: Results on heterophilic graphs.

\section{Responses to Reviewer 4oqi}

\textbf{Empirical results}

Q1: More explanations for the results on heterophilic graphs.


\textbf{Novelty}

Q2: Differences to existing neighborhood-based contrastive learning methods.

A2: We thank the reviewer for pointing out two recent works which share a similar idea of using neighboring nodes to construct positive examples. We didn't notice [R1] because it is designed for recommender systems, and we didn't notice the second one because 1) it is a very recent paper, and 2) it does not imply that it uses neighbors in its title. Though the basic idea of these two works and ours is similar: neighboring nodes can serve as positive examples for contrastive learning, there are significant differences in the implementations.

In [R1], Eq.(6), the positive pairs is constructed between user $u$'s embedding at layer $0$, and layer $k$. The motivation for such a design is that graph convolution (e.g, user $u$'s embedding at layer $k$) is a summary of the information of the neighboring nodes, so it contrasts a user's embeddings from different layers. The issue with such a design, however, is that embeddings from different layers lie in different spaces and thus cannot be theoretically justified using mutual information maximization theory. Besides, Eq.(6) in [R1] is a node-centric contrastive objective, while LocalGCL is an edge-centric one. As a result, [R1] is not guaranteed to recover the graph structure, while our LocalGCL can (see Proof of Theorem 1 in Appendix A.1, where the LocalGCL loss can recover the graph adjacency matrix $\tilde{A}$).

[R2] is more close to our work because it also performs edge-centric contrastive learning. The major difference between Eq.(5) in [R2] and ours is that [R2] considers all nodes within the $k$-hop neighborhoods as positive examples. Though $k$ should be a very important hyperparameter that can significantly affect the model's performance, [R2] fails to give any analysis or empirical results (e.g., ablation studies on $k$ ) on how to decide it. Besides, as shown in III.D in [R2], the authors seem to choose a large $k$, which can be computationally inefficient. We agree that utilizing the graph structure information for unsupervised node representation learning itself is not a novel idea. For example, the classic network embedding method, LINE[R4], just treats first-order neighbors as positive examples and uses randomly sampled nodes as negative examples. However, no previous work has successfully applied such a simple idea to node-level contrastive representation learning. The major contribution of this work is that, we demonstrate that contrastive learning with purely first-order neighbors, without high-order connectivity and without data augmentation, can achieve competitive or even better performance than those with high-order connectivity or data augmentations. 

References:

[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.

[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.

[R4] Tang, Jian, et al. "Line: Large-scale information network embedding." Proceedings of the 24th international conference on world wide web. 2015.

Q3: Differences to another method using kernel approximation.

A3: Though [R3] also adopts kernel approximation for self-supervised learning, the motivation and implementation in [R3] and our work is totally different. In [R3], the authors propose to maximize the HSIC between two transformed views instead of mutual information (which is usually realized using InfoNCE loss). As the computation of HSIC directly requires a gram matrix of the kernel function, it naturally employs RFF to reduce the complexity of the computation of HSIC. From this perspective, SSL-HSIC is a replacement of the InfoNCE-loss-based contrastive learning methods. Although performing similarly, they are two distinct methods with different motivations. By contrast, there isn't an explicit formulation of the kernel function in InfoNCE loss. In this paper, we show that the InfoNCE loss could be transformed into a kernelized version and thus can be accelerated using kernel approximation. 

References:

[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.


Q4: Results of statistical significance tests.

A4: We agree with the reviewer that simply reporting the standard deviation might not be strong enough. However, to my knowledge, in the context of self-supervised learning on graphs, it is a common practice to report the averaged score with a standard deviation [A,B,C,D]. In order for consistency with these baselines, we simply report the performance in terms of mean accuracy with the standard deviation of 20 random trials. For Cora, Citeseer and PubMed, we have to use the fixed public split as nearly all the important baseline models are based on this split. This is the same for ogbn-arxiv dataset, where the public split is recommended by the dataset contributor. Note that for Computer, Photo, CS, and Physics, we use random split so there should not be concerns about the model's robustness against dataset split.

\section{Responses to Reviewer Nj2N}
We thank the reviewer for the thorough review. We notice that your questions are mainly about some unclear expressions. We are glad to your questions one by one.

Q1: Add an introductory sentence to explain Section 2.3.

A1: We thank the reviewer for noticing that it requires aN introductory sentence at the beginning of Sec. 2.3. In the revised version, we have highlighted the scalability issue of InfoNCE loss when applied to large graphs, which motivates the utilization of Random Features.

Q2: Equation 2: why the positive pair is not included in the denominator?

A2: This should be a typo. The positive pair should be covered in the denominator together with negative ones so that the pairs in the denominator are randomly sampled from the product of two marginal distributions (then it can be related to mutual information). Note that in Local-GCL's loss (Eq. 5), the positive term is also included in the denominator. We thank the reviewer for noticing this mistake and we've revised it in the latest version.

Q3: Sec3. Not clear what is the input to the network, and what is $i$ in $z_i$.

A3: We are sorry for assuming that the readers are very familiar with the context of self-supervised learning on graphs. Just as you comprehend, the input is node features (together with the graph structure), and the output is each node's embedding $z_i$. The encoder could be either an MLP or a GNN. We've added a short description in the first paragraph of Sec.3 so that readers that are not familiar with this area can quickly understand the framework of node-level contrastive learning.

Q4: Theorem 1.

A4: As suggested, we've added the citations, which clearly suggest that our theorem can be easily derived from the conclusions of these two works. 

Q5: Add descriptional sentences about datasets in the main text.

A5: Due to space limitations, we cannot add more descriptions about the dataset statistics in Sec 5.1, but we stated that ogbn-arxiv has about 17k nodes, and on it a lot of previous methods can not scale.

Q6: Implementation details about the encoder architecture.

A6: In implementation details, we have already mentioned that the encoder is a two-layer GCN by default.

Q7: Questions about mini-batch training and GRACE.

A7: In SimCLR for image representation learning, the number of negative examples is (about double) of the batch size. However, in GRACE (you can view it as a graph version of SimCLR), the number of negative examples is $2|\mathcal{V} -1|$, where $\mathcal{V}$ is the number of nodes in the graph. So GRACE does not use mini-batch training, and this is exactly the reason that it cannot scale to large graphs. (We've revised Fig. 2 as suggested.)

We didn't use mini-batch training for Local-GCL. Instead, at each training epoch, we forward the model to get all node embeddings within the graph and optimize the model using our Local-GCL loss (your understanding is correct, and we use all graph nodes as negative pairs). 

Q8: Can Random Fourier Features be applied to non-graph contrastive learning scenarios?

A8: It is correct that RFF can be applied to non-graph contrastive learning tasks such as SimCLR in CV. However, there is an essential difference between graph (node) and images, which makes it unnecessary to approximate the computation of SimCLR loss in CV: the main bottleneck in image contrastive learning is the backbone model, e.g., ResNet-18 or ResNet-50. This prevents a large batch size from being used. For example, in SimCLR, the largest batch size can only be 8192, and this is based on the fact that they use over 32 TPUs. For such a baseline, the number of negative examples is small, and the computation cost for the contrastive loss function is almost negligible compared with the backbone encoder. As a result, it is unnecessary to use RFF to accelerate in CV. By contrast, for node representation learning, it is not hard to train the model in a full-graph manner. In this case, the number of negative examples could be huge. As a result, RFF can benefit a lot in both time and memory complexity.

Q9: Why wasn't the idea studied in previous works?

A9: This is an interesting question. Actually, utilizing the graph structure information  for unsupervised node representation learning itself is not a novel idea. For example, the classical network embedding method, LINE[1], just treats first-order neighbors as positive examples and uses randomly sampled nodes as negative examples. The difference, to be rough, is just the loss function, where that of LINE is a cross-entropy one, while ours is based on InfoNCE. In our opinion, the concept of contrastive learning for unsupervised representation learning was first proposed in late 2018 (CPC[2]), and became popular until the beginning of 2020 (SimCLR[5]), in computer vision for learning image representations. As in images, there isn't structure information available for constructing positive pairs, data augmentations are indispensable. Then, motivated by the success of contrastive (and some non-contrastive) methods in CV, some researchers tried to transfer them to the graph domain (e.g., DIM[2] and DGI[4], SimCLR[5] and GRACE[6], BYOL[7] and BGRL[8], BarlowTwins[9] and Graph BarlowTwins[10]). As they are direct applications of these methods from CV to graph, they simply design (or borrow existing) graph data augmentation strategies without considering the unique property of the graph (e.g., connections between nodes). In this paper, we rethink the necessity of data augmentations in graph contrastive learning, and we demonstrate that with simple connecting nodes as positive examples, we can achieve competitive or even better performance than the augmentation-based methods.


References:

[1] Tang, Jian, et al. "Line: Large-scale information network embedding." Proceedings of the 24th international conference on world wide web. 2015.

[2] Oord, Aaron van den, Yazhe Li, and Oriol Vinyals. "Representation learning with contrastive predictive coding." arXiv preprint arXiv:1807.03748 (2018).

[3] Hjelm, R. Devon, et al. "Learning deep representations by mutual information estimation and maximization." arXiv preprint arXiv:1808.06670 (2018).

[4] Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In ICLR, 2019.

[5] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In ICML, Proceedings of Machine Learning Research, pages 1597–1607, 2020.

[6] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006.04131, 2020.

[7] Grill, Jean-Bastien, et al. "Bootstrap your own latent-a new approach to self-supervised learning." Advances in neural information processing systems 33 (2020): 21271-21284.

[8] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Velickovic, and Michal Valko. Bootstrapped representation learning on graphs. arXiv preprint arXiv:2102.06514, 2021.

[9] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self=supervised learning via redundancy reduction. In ICML, 2021.

[10] Bielak, Piotr, Tomasz Kajdanowicz, and Nitesh V. Chawla. "Graph Barlow Twins: A self-supervised representation learning framework for graphs." Knowledge-Based Systems 256 (2022): 109631.

\section{Responses to Reviewer BqrR}

Q1: Contributions of our work to negative-free methods.

A1: First, we'd like to clarify the concept of **contrastive learning**. When we talk about contrastive learning, there should always be a positive pair and negative pair, as 'contrast' just means we would like to discriminate between positive pairs and negative pairs. Methods like BGRL and CCA-SSG are actually non-contrastive instead of CL methods (although the two concepts were confused in some works). As stated in the title and abstract, one purpose of of our work is to mitigate the inefficiency problem of contrastive learning (i.e., InfoNCE loss) on graphs, so we didn't pay much attention to non-contrastive methods in our submission.

Second, besides the approximation of the negative loss, our first contribution (i.e., 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-SSG uses the exactly same data augmentations methods proposed in GRACE (a contrastive method). As a 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 getting them free from data augmentations. In such as a case, the models does not require two-viewed data as inputs, so the size of inputs, intermediate variables and outputs can be reduced by half. To better demonstrate this point, we further extends our method with BGRL and CCA-SSG.

For BGRL, denote the target embedding of node $i$ by $\mathbf{h}_i$ and the corresponding prediction by $\mathbf{z}_i$, our BGRL-Local optimizes the following loss function:

$$
   \mathcal{L}_{BGRL-Local} = -\frac{2}{N} \sum\limits_{i \in \mathcal{V}} \sum\limits_{j \in \mathcal{N}(i)} \frac{\mathbf{z}_j \cdot \mathbf{h}_i}{\Vert \mathbf{z}_j \Vert_2^2  \Vert \mathbf{h}_i \Vert_2^2}
$$

For CCA-SSG, denote the embedding of node $i$ by $\mathbf{h}_i$,
 we first compute the local summary of node $i$ by $\mathbf{z}_i = \frac{1}{|\mathcal{N}(i)|} \sum\limits_{j\in\mathcal{N}(i)}
 \mathbf{h}_j$. Then we compute two standardized embedding matrix by:
 
 $$
    \tilde{\mathbf{H}} = \frac{\mathbf{H} -\mu(\mathbf{H})}{\sigma(\mathbf{H})*\sqrt{|\mathcal{V}|}},     \tilde{\mathbf{Z}} = \frac{\mathbf{Z} -\mu(\mathbf{Z})}{\sigma(\mathbf{Z})*\sqrt{|\mathcal{V}|}}.
 $$

Finally, CCA-SSG-Local optimizes the following loss function:

$$
  \mathcal{L}_{CCA-SSG-Local} = \left\| \tilde{\mathbf{H}} - \tilde{\mathbf{Z}} \right\|_F^2 + \lambda \left( \left\|  \tilde{\mathbf{H}}^{\top}\tilde{\mathbf{H}} - \mathbf{I} \right\|_F^2 + \left\|  \tilde{\mathbf{Z}}^{\top}\tilde{\mathbf{Z}} - \mathbf{I} \right\|_F^2 \right).
$$

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 the following table (We didn't choose the three citation networks as BGRL performs really bad on them):

| CS | CS | CS  | Physics  | Physics | Physics  |

| Acc | Time  | Memory  |  Acc | Time  | Memory |

|  ----   | ----  |  ----   | ----  |  ----   | ----  |

| BGRL  | 92.59$\pm$0.17 | 30.4 min  |  5.7G  | 95.48$\pm$0.08 | 57.7 min  | 14.4G |

| BGRL-Local  | 92.98$\pm$0.23 | 18.2 min  | 4.1G | 95.82$\pm$0.11| 32.3 min  | 9.4G |

| CCA-SSG  | 83.31$\pm$0.22 |  1.1 min  | 6.4G | 95.38$\pm$0.06 |  5.9 min  | 15.1G |

| CCA-SSG-Local  | 94.08 $\pm$0.19 | 0.7 min  | 4.5G | 95.69$\pm$0.09 |  4.3 min  | 10.5G |

(BGRL takes much longer time for training, because it does requires 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. 



Third, even though negative-free methods like BGRL and CCA-SSG are much more efficient than the vanilla contrastive methods with negative samples, and can demonstrate competitive performance, contrastive methods are still important and have incomparable advantages than non-contrastive ones. Besides, the theoretical guarantees (e.g., lower bound of mutual information [R1], and the performance guarantee (Theorem 1)) another, typical example is hard negative sampling techniques [R2, R3, R4, R5]. These works either assign weights to different negative samples so that true negative examples are more important than false negative examples, or using 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 in [R5], and we report the performance comparison on Cora, Citeseer and Pubmed in the following table:

|  Cora   | Citeseer  | Pubmed |

|  ----   | ----  | | ----  |

| Local-GCL(origin)  | 84.5$\pm$0.4 | 73.6$\pm$0.4 |82.1$\pm$0.5|

| Local-GCL + ProGCL-mix  | 84.9$\pm$0.5 | 74.2$\pm$0.4 |82.3$\pm$0.5|

The improvement is prominent (especially on Citeseer) thanks to the hard-negative sampling strategy is prominent. 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 3 classes of nodes on Pubmed, so it is less effective to mine hard negatives than 7 classes on Cora and 6 on Citeseer. By contrast, negative-sample-free method like BGRL and CCA-SSG cannot get benefits from it.

Last but not least, we want to emphasize that the improvement is not is not marginal, considering that as an **unsupervised** method, our model's performance is already very close to SOTA **(semi)supervised** GNN methods with complicated architectures and regularizations. For example, one of the SOTAs on Cora and Pubmed is GRAND [R6], which employs a high-order convolution model, combined with consistency regularization between embeddings of different views generated from random data augmentations. GRADN achieves 85.4\% on Cora and 82.7\% on Pubmed, which are less than $1\%$ percent improvement than our results. Considering the existence of such a upper bound, our model's improvement is not marginal.

References 

[R1] Poole, Ben, et al. "On variational bounds of mutual information." International Conference on Machine Learning. PMLR, 2019.

[R2] Robinson, Joshua, Ching-Yao Chuang, Suvrit Sra, and Stefanie Jegelka. "Contrastive learning with hard negative samples." arXiv preprint arXiv:2010.04592 (2020).

[R3] Kalantidis, Yannis, Mert Bulent Sariyildiz, Noe Pion, Philippe Weinzaepfel, and Diane Larlus. "Hard negative mixing for contrastive learning." Advances in Neural Information Processing Systems 33 (2020): 21798-21809.

[R4] Zhang, Shaofeng, 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 Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2461-2470. 2022.

[R5] Xia, Jun, Lirong Wu, Ge Wang, Jintao Chen, and Stan Z. Li. "Progcl: Rethinking hard negative mining in graph contrastive learning." In International Conference on Machine Learning, pp. 24332-24346. PMLR, 2022.

[R6] Feng, Wenzheng, et al. "Graph random neural networks for semi-supervised learning on graphs." Advances in neural information processing systems 33 (2020): 22092-22103.

Q2: More explanations about the results on heterophily graphs.

A2: 

Q3: Proof for Theorem 1 is not clear.

A3: 
The relation between homophily ratio $\phi$ and node embeddings learned from matrix factorization loss is a direct conclusion of Lemma 2, which is initially presented by Theorem B.3 of [R7]. The whole proof of Theorem B.3 of [R7] is complicated, which consists of a series of Lemmas, as a result it is inappropriate to present the its proof in our paper. Since the reviewer would like us to present more details about the proof of it, here we present the major steps that build a connection between graph homophily ratio $\phi$, the eigenvalues/eigenvectors of the normalized graph Laplacian matrix, and a specific labeling function that induces the homophily ratio.

First, we have to introduce some notations. For a graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ with $|\mathcal{V}|$ nodes, the normalized Laplacian matrix is $\mathcal{L}$. $v_i$ is the i-th smallest unit-norm eigenvector of $\mathcal{L}$ with eigenvalue $\lambda_i$.  

Step 1 is to show that for any vector $u \in \mathbb{R}^{|\mathcal{V}|}$,
there exits a linear combination the smallest $d$ eigenvectors such that the error of the estimation of $u$ is bounded by the $d+1$ smallest eigenvalue. Formally,

$$
  \left\| u - \sum\limits_{i=1}^d b_iv_i  \right\|_2^2 \le \frac{R(u)}{\lambda_{d+1}} \Vert u \Vert_2^2,
$$
where each $b_i$ is a scalar, $R(u) = \frac{u^{\top}\mathcal{L}u}{u^{\top}u}$ is the Rayleigh quotient of the vector $u$. 

The proof is trivial: the vector $u$ can always be decomposed into the summation of the eigenvector basis:

$$
    u = \sum\limits_{i=1}^{\mathcal{V}} \zeta_i v_i.
$$
Besides, we have:
$$
    R(u) = \frac{\sum_{i=1}^{\mathcal{V}} \lambda_i \zeta_i^2}{\Vert u \Vert_2^2}. 
$$

As a result, we can simply let $b_i = \zeta_i$. Also, as $\Vert b \Vert_2^2 \le \Vert u \Vert_2^2$, we can conclude that:

$$
  \left\| u - \sum\limits_{i=1}^d b_iv_i  \right\|_2^2 = \sum\limits_{i=k+1}^{|\mathcal{V}|} \zeta_i^2 \le \frac{R(u)}{\lambda_{d+1}} \Vert u \Vert_2^2
$$

The second step is to show that when the $u$ is defined by an extended labeling function $\hat{y}$, i.e., $u^{\hat{y}}_i(v) = \mathbbm{1}[\hat{y}(v) = i] $ ($i$ denotes the i-th class) which gives a class-level graph homophily ratio $\phi^{\hat{y}}_i$, the Rayleigh quotient of the vector $u_i^{\hat{y}}$ is directly related to the graph homophily ratio $\phi^{\hat{y}}_i$:
$$
   R(u^{\hat{y}}_i) = \frac{1}{2} (1-\phi^{\hat{y}}_i).
$$

To prove this, note that $u_i^{\hat{y}}$ projects a node in the graph to an scalar (either 0 or 1), then:

$$
    u^{\top}\mathcal{L}u =  \Vert u \Vert_2^2 - u^{\top}D^{-1/2}AD^{-1/2}u  \\
    = \sum\limits_{v \in \mathcal{V}} u(v)^2 - \sum\limits_{(v, v') \in \mathcal{E}} (u(v) - u(v'))^2 \\  = \frac{1}{2} \sum\limits_{(v, v') \in \mathcal{E}} (u(v) - u(v'))^2.
$$

As a result, we have 

$$
    R(u_i^{\hat{y}}) = \frac{{u_i^{\hat{y}}}^{\top}\mathcal{L}u_i^{\hat{y}}}{{u_i^{\hat{y}}}^{\top} u_i^{\hat{y}}} \\ = \frac{1}{2} \frac{\sum\limits_{(v,v')\in \mathcal{E}} (u_i^{\hat{y}}(v)-u_i^{\hat{y}}(v'))^2}{\sum\limits_{v\in\mathcal{V}} u_i^{\hat{y}}(v)^2}.
$$
Setting $u_i^{\hat{y}}(v) = 1$ when $v$ is labeled as $i$, and $0$ otherwise, then we can find that the last term is exactly the probability that when one node is labeled as $i$, while its neighbors is not, i.e. $1-\phi^{\hat{y}}_i$. As a result, we complete the proof. 

Combining Step 1, and Step 2, we are able to build a connection between a labeling function, the induced graph homophily ratio and the eigenvalues/eigenvectors of the normalized graph Laplacian matrix. For more detailed proof, we recommend the reviewer to directly read [R7] if you are interested. 
 
References:

[R7] Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised
deep learning with spectral contrastive loss. NeurIPS, 34:5000–5011, 2021.

Q4: More comprehensive ablation studies.

A4: In the response of Q1, we have included two more ablation studies: 1) extending the positive sampling strategies to negative-sample-free methods like BGRL and CCA-SSG; 2) adopt a advanced negative sampling strategy ProGCL-mix. Both experimental results demonstrate the proposed positive sampling method and approximated loss can be successfully combined with other techniques.

In addition to treats each neighboring node equally as positive examples, we further explore two other positive sampling strategies: 1) compute the similarities between neighboring nodes, and use the most similar one as the positive example (we term it LocalGCL-max); 2) reweight the importance of different neighboring nodes according to their similarities, where more similar neighboring node should be assigned a larger weight (we term it LocalGCL-weight).

For LocalGCL-max, we first its the nearest neighbor:
$$
    \mathbf{s}_i = \mathop{\arg\min}_{\mathbf{z}_j, j \in \mathcal{N}(i)} \left\| \frac{\mathbf{z}_j}{\Vert \mathbf{z}_j \Vert_2^2} - \frac{\mathbf{z}_i}{\Vert \mathbf{z}_i \Vert_2^2} \right\|^2,
$$
and the objective function is
$$
    \mathcal{L}_{LocalGCL-max} = -\frac{1}{|\mathcal{V}|} \sum\limits_{i=1}^N  \log \frac{  \exp (\mathbf{z}_i^{\top}\mathbf{s}_i/\tau)}{\sum\limits_{k \in \mathcal{V}} \exp (\mathbf{z}_i^{\top}\mathbf{z}_k /\tau)} .
$$

For LocalGCL-weight, we first computes the pair-wise similarities of neighboring nodes:

$$
    \text{sim}_{ij} =  \mathbf{A}_{i,j} \cdot  \frac{\mathbf{z}_i^{\top}\mathbf{z}_{j}}{\Vert \mathbf{z}_i \Vert_2^2 \Vert \mathbf{z}_j \Vert_2^2}.
$$

Then, for a target node $i$, it softmax the scores of its neighboring nodes as the weights:

$$
    w_{i}(j) = \text{softmax} [\text{sim}_{ij}]_{j \in \mathcal{N}(i)}.
$$

The objective function of LocalGCL-weight is consequently defined as

$$
    \mathcal{L}_{LocalGCL-weight} = -\frac{1}{|\mathcal{V}|} \sum\limits_{i=1}^N  \log \frac{\sum\limits_{j \in \mathcal{N}(i)}  w_i(j)\exp (\bm{z}_i^{\top}\bm{z}_j/\tau) / |\mathcal{N}(i)|}{\sum\limits_{k \in \mathcal{V}} \exp (\bm{z}_i^{\top}\bm{z}_k /\tau)}.
$$

The results of LocalGCL-max and LocalGCL-weight, together with the original LocalGCL is presented in the following table:

|  Cora   | Citeseer  | Pubmed |

|  ----   | ----  | | ----  |

| LocalGCL(origin)  | 84.5$\pm$0.4 | 73.6$\pm$0.4 |82.1$\pm$0.5|

| LocalGCL-max  | 83.6$\pm$0.5 | 73.7$\pm$0.5 |81.7$\pm$0.5|

| LocalGCL-weight  | 84.9$\pm$0.4 | 73.7$\pm$0.4 |82.2$\pm$0.5|

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 a lot of useful information in the local neighborhood. Besides, LocalGCL-weight improves the performance on Cora significantly, but makes little differences on Citeseer and Pubmed. This might be because without supervision, a higher similarity in the latent space does not necessarily indicates a higher probability of sharing the same label. Considering that LocalGCL-weight requires additional computational cost for computing the weights, and the performance of the original LocalGCL is already quite good, we just treats every neighboring node equally in this work.

All the three ablation studies have been added in the revised version in Appendix. 
\end{document}
