Year: 2021

Abstract:
Self-supervised learning (SSL) of graph neural networks is emerging as a promising way of leveraging unlabeled data. Currently, most methods are based on contrastive learning adapted from the image domain, which requires view generation and a sufficient number of negative samples. In contrast, existing predictive models do not require negative sampling, but lack theoretical guidance on the design of pretext training tasks. In this work, we propose the LaGraph, a theoretically grounded predictive SSL framework based on latent graph prediction. Learning objectives of LaGraph are derived as self-supervised upper bounds to objectives for predicting unobserved latent graphs. In addition to its improved performance, LaGraph provides explanations for recent successes of predictive models that include invariance-based objectives. We provide theoretical analysis comparing LaGraph to related methods in different domains. Our experimental results demonstrate the superiority of LaGraph in performance and the robustness to decreasing of training sample size on both graph-level and node-level tasks.

heading: 1 INTRODUCTION
text: Self-supervised learning (SSL) methods seek to use supervisions provided by data itself and design effective pretext learning tasks. These methods allow deep models to learn from a massive amount of unlabeled data and have achieved promising successes in natural language processing (Devlin et al., 2019; Wu et al., 2019; Wang et al., 2019) and image tasks (Batson and Royer, 2019; Xie et al., 2020; He et al., 2020; Chen et al., 2020). To use unlabeled graph data, earlier studies (Perozzi et al., 2014a; Grover and Leskovec, 2016) adapt sequence-based SSL methods (Mikolov et al., 2013b;a) to learn node representations. Inspired by the recent success of SSL in the image domain, a variety of SSL methods based on graph neural networks (GNNs) have been proposed in different learning paradigms. In particular, (Veličković et al., 2019; Zhu et al., 2020; Thakoor et al., 2021; Hassani and Khasahmadi, 2020; You et al., 2020) construct SSL tasks as unsupervised approaches to learn representations from graph data at either node-level or graph-level; (Hu et al., 2020) proposes SSL strategies to pre-train GNNs for downstream tasks; and (Jin et al., 2020; Kim and Oh, 2021) employ SSL as auxiliary tasks to boost the performance of main learning tasks.
Common taxonomies in recent survey works (Xie et al., 2021; Liu et al., 2020) consider two categories of SSL methods to train GNNs; namely, contrastive methods and predictive methods. Contrastive methods employ pair-wise discrimination as their pretext learning tasks. It performs transformations or augmentations to obtain multiple views from a graph and trains GNNs to discriminate between jointly sampled view pairs and independently sampled view pairs. In contrast, predictive methods (Hamilton et al., 2017; Hwang et al., 2020; Rong et al., 2020) train GNNs to predict certain labels obtained from the input graph, such as node reconstruction, connectivity reconstruction, graph statistical properties, and domain knowledge-based targets.
Adapted from the image domain, current state-of-the-art SSL methods for graphs are mostly contrastive. As a drawback, they usually depend on large training sample size to include a sufficient number of negative samples. With limited computing resources, contrastive methods may not be applicable to large-scale graphs without suffering from performance loss. To address the drawback, BGRL (Thakoor et al., 2021) adapts BYOL (Grill et al., 2020) to the graph domain. BGRL still obtains different views from each given graph, but it eliminates the requirement of negative samples by replacing contrastive objectives with the prediction of offline embedding. BGRL has achieved
competitive performance to the contrastive methods. However, unlike contrastive methods grounded by mutual information estimation and maximization, BYOL and BGRL lack theoretical guidance and require implementation measures to prevent collapsing to trivial representations, such as stop gradient, EMA, and normalization layers.
In this work, we propose LaGraph, a predictive SSL framework for representation learning of graph data, based on self-supervised latent graph prediction. In particular, we describe the notion of the latent graph and introduce the latent graph prediction as a pretext learning task. We adapt the supervised objective of latent graph prediction into a self-supervised setting by deriving its self-supervised upper bounds, according to which we present the learning framework of LaGraph. We provide further justifications of LaGraph by comparing it with theoretically sound methods in different domains. Our experimental results demonstrate the effectiveness of LaGraph on both graph-level and node-level representation learning, where a remarkable performance boost is achieved on a majority of datasets with higher stability to smaller batch size or training on subsets of nodes.
Relations with Prior Work: Both LaGraph and some existing contrastive methods (You et al., 2020; Zhu et al., 2020; Hu et al., 2020) apply node masking. A major difference is that LaGraph is a predictive method instead of contrastive. While those contrastive methods use node masking as an augmentation to obtain different views for contrast, LaGraph employ it for the computation of the invariance regularization. In addition, the objective of BGRL can be considered similar to the invariance regularization term in our objective. While the objective of BGRL is designed without theoretical guidance, our derived theorems associated with LaGraph objectives can explain the success of BGRL to some extent and provide guidance on how to better adopt objectives related to the invariance regularization on graphs.

heading: 2 METHODS

heading: 2.1 NOTATIONS AND PROBLEM FORMULATION
text: We consider an undirected graph G = (V,E) with a set of attributed nodes V and a set of edges E. We formulate the graph data as a tuple of matrices (A,X), where A ∈ R|V |×|V | denotes the adjacency matrix and X ∈ R|V |×d denotes the node features of dimension d. We employ a graph encoder E based on graph neural networks (GNNs) to encode each node or graph into a corresponding representation. Namely, we compute the node-level representations or node embedding by H = E(A,X) ∈ R|V |×q and the graph-level representation or graph embedding by z = R(H) ∈ R1×q , where q denotes the embedding dimension andR : R|V |×q → R1×q is a readout function. Self-supervised representation learning is employed to train the graph encoder E on a set of K graphs {Gi}Ki=1 without labels from downstream tasks. In particular, we seek to design effective pre-text learning tasks, whose labels are obtained by task designation or from given data, to train the graph encoder E and produces informative representations for downstream tasks. Depending on the pre-text learning tasks, the encoder E is usually trained together with some prediction head D for predictive SSL or a discriminator for contrastive SSL.

heading: 2.2 LATENT GRAPH PREDICTION
text: Our method considers latent graph prediction as a pretext task to train graph neural networks. In this subsection, we introduce the general notion of latent data, followed by its specific definition for graph data, and the construction of the learning task. For any observed data instance x, we assume that there exists a corresponding latent data xI , determining the semantic of x, such that the latent data xI is generated from a prior p(xI) and the observed data instance is further generated from a certain distribution conditioned on the latent data, i.e., p(x|xI). The most common case for the pair of observed data and latent data is the noisy data and its clean version.
When it comes to graph data, we consider the case that an observed graph data G = (A,X) is (noisily) generated from its latent graph G` = (A,F ) with the same node set and edge set, where node feature matrices X and F for the two graphs have the same dimensionality. We make two assumptions to the graphs without loss of generality. First, we assume that the observed feature vector xv of each node v in an observed graph is independently generated from a certain distribution
conditioned on the corresponding latent graph. In other words, how xv is generated from the latent feature fv is not affected by the generation of other observed feature vectors. Second, we assume that the conditional distribution of the observed graph is centered at the latent graph, i.e., E[X|G`] = F . The above assumptions are natural when we have little knowledge about the generation process and are commonly used in other types of data such as the non-structural and zero-mean noise in images. In cases that the generation processes of different nodes are related or the distribution is not centered at F , we can still consider the related or biased components into the latent feature and therefore have the assumptions satisfied.
As the latent data usually determine the semantic meaning of observed data, we believe the prediction of latent graph can provide informative supervision for the learning of both graph-level and nodelevel representations. We are hence interested in constructing the learning task of latent graph prediction. To perform latent graph prediction, it is straightforward to employ a graph neural network f : {0, 1}|V |×|V | × R|V |×d → R|V |×d that takes an observed graph G = (A,X) as inputs and predicts the feature matrix of its latent graph GI = (A,F ). When the ground truth of the latent feature matrix F is known, the learning objective can be designed as
f∗ = argmin f E ‖f(A,X)− F ‖2 . (1)
Intuitively, the latent graph prediction can be considered as a generalized task from noisy data reconstruction that predicts the signal from the noisy data with the objective argminf E ‖f(x)− s‖2, where the mapping from the signal to the noisy data p(x|s) can usually be explicitly modeled and samples of signal (ground truth) can usually be captured. In the data reconstruction case, pairs of (x, s) can be therefore directly captured or synthetically generated given a certain noise model p(x|s). However, when the task is generalized to latent graph prediction, there is a key challenge preventing us from directly applying the prediction task. That is, whereas there are natural supervisions for noisy data reconstruction, the latent graph is not observed and we are unable to explicitly model the mapping from latent graphs to observed graphs, i.e., the conditional distribution p(G|GI).

heading: 2.3 SELF-SUPERVISED UPPER BOUNDS FOR LATENT GRAPH PREDICTION
text: As discussed in the previous subsection, unlike typical noisy data reconstruction tasks, the latent graph is not observed and p(G|GI) cannot be modeled explicitly. This makes it difficult to construct a direct learning task for latent graph prediction using the objective in Equation (1). We therefore seek to optimize an alternative objective that approximately optimizes the objective in Equation (1) without requiring the distribution p(G|GI), nor features F of the latent graph. We now introduce the proposed self-supervised objective for latent graph prediction.
We derive our self-supervised objective without involving F by constructing an upper bound of the objective in Equation (1). Specifically, we let J ⊂ {0, · · · , |V | − 1} be an arbitrary subset of node indices, Jc denote the complement of set J , and XJc := 1Jc X + 1J M be the feature matrix with features of nodes in VJ masked, where denotes element-wise multiplication, M ∈ R|V |×d denotes a matrix consisting of independent random noise or zeros as masking values, and 1J ∈ R|V |×d denotes an indicator matrix such that 1J [i, :] = 1,∀i ∈ J and 1J [i, :] = 0,∀i /∈ J . We describe the self-supervised upper bound in Theorem 1, whose proof is provided in Appendix A. Theorem 1. Consider a graph G = (A,X) and its latent graph GI = (A,F ). We let the variance of any elements in X be bounded by σ2 and J be a subset of nodes V in the graph G. For any graph neural network f : {0, 1}|V |×|V | ×R|V |×d → R|V |×d, we have the following inequality
EA,X,F
[ ‖f(A,X)− F ‖2 + ‖X − F ‖2 ] ≤ EA,X ‖f(A,X)−X‖2 +
2σ|V |EJ [ EA,X ‖fJ(A,X)− fJ(A,XJc)‖2
|J |
]1/2 . (2)
Intuitively, the first component in the upper bound derived in Theorem 1 measures the reconstruction error on the feature matrix X of the given observed graph G, enforcing the intermediate representations to be informative. The second component controls how much information is accessible from the input feature of a node vi when reconstructing the feature of vi, by encouraging the output of a
node to be invariant to the missing of its features in the input graph. We then call the first component as a reconstruction term and the second component as an invariance regularization term. Note that the invariance regularization is only computed on masked nodes in contrast to the BGRL objective, based on different theoretical grounding and leading to a different effect (see Appendix D).
In tasks of self-supervised representation learning, we are more interested in graph-level or node-level representations than predicted latent graphs. In these cases, we expect the representations also holds the invariance property held by the final outputs. We therefore seek to apply the invariance regularization to the representations, since a regularization applied to the output does not necessarily control the information accessibility of representations produced intermediately in the graph neural network. To do so, we separately consider the encoder E and decoder D in the graph neural network f . We introduce certain assumptions to the decoder networkD and the readout functionR, and derive two additional upper bounds for node-level and graph-level representation learning, respectively in following corollaries. Proofs of the corollaries are provided in Appendix B. Corollary 1. Let G = (A,X) be a given graph, GI = (A,F ) be its latent graph, E and D be a graph encoder and a prediction head (decoder) consisting of fully-connected layers. If the prediction head D is `-Lipschitz continuous with respect to l2-norm, we further have the following inequality,
E [ ‖D(H)− F ‖2 + ‖X − F ‖2 ] ≤ E ‖D(H)−X‖2 + 2σ|V |`EJ [ E ‖HJ −H ′J‖ 2
|J |
]1/2 ,
(3)
where H = E(A,X) and H ′ = E(A,XJc) denote the node embedding of the given graph and the masked graph, respectively, and HJ := H[J, :] selects rows with indices in J . Corollary 2. Let G = (A,X) be a given graph, GI = (A,F ) be its hidden latent graph, E be a graph encoder,R be a readout function satisfying k-Bilipschitz continuity with respect to l2-norm, and D be a prediction head (decoder). If the prediction head D is `-Lipschitz continuous with respect to l2-norm, we have the following inequality,
E [ ‖D(H)− F ‖2 + ‖X − F ‖2 ] ≤ E ‖D(H)−X‖2 + 2σ|V |k`EJ [ E ‖z − z′‖2 |J | ]1/2 , (4)
where z = R(H) and z′ = R(H ′) denote the graph-level representations of the given graph and the masked graph, respectively.
We note that the assumptions and restrictions are natural or practically satisfiable. The assumption that variance of each element in X is bounded by σ holds when node features are from {0, 1}d or when feature normalization is applied. The `-Lipschitz continuous property is common for neural networks. And the k-Bilipschitz continuity can be satisfied by applying an injective readout function such as global sum pooling, which is commonly used in graph-level tasks.
2.4 THE LaGraph FRAMEWORK
We design our self-supervised learning framework according to upper bounds derived in Corollary 1 and Corollary 2. To train encoder E together with decoder D under self-supervision, we input to the encoder both the given graph (A,X) and its variation (A,XJc) with a random subset J of node indices for nodes to be masked and obtain node-level representations H = E(A,X) and H ′ = E(A,XJc) for the two graphs respectively. The self-supervised losses are computed on input node features, reconstructed node features, and representations, as demonstrated in Figure 1.
In particular, we consider a mini-batch of N graphs {(Ai,Xi)}Ni=1 and their corresponding masked variation {(Ai,X(i,Jic))}Ni=1 where Ji denotes the node indices subset for the i-th graph. The self-supervised loss for node-level representation learning follows Corollary 1 and is computed as
Lnode(E ,D) = 1
N N∑ i=1
‖D(Ai,Hi)−Xi‖2 /|Vi|+ α [∑ i ‖1Ji Hi − 1Ji H ′i‖ 2∑
i |Ji|
]1/2 , (5)
where α is a hyper-parameter corresponding to the multiplier 2σ` in Corollary 1. To fulfill the conditions in Corollary 1, we employ fully-connected layers instead of graph convolutional layers in the decoder D. The pseudo-code are provided in Appendix C.
Similarly, using the same notations above, the self-supervised loss for graph-level representation learning follows Corollary 2 and is computed as
Lgraph(E ,D) = 1
N N∑ i=1
‖D(Ai,Hi)−Xi‖2 /|Vi|+ α′ [∑
i ‖zi − z′i‖ 2 / ∑ i
|Ji| ]1/2 , (6)
where zi = R(Hi) and z′i = R(H ′i) denote the graph-level representations obtained by applying readout function R to the node-level representations, respectively, and α′ is a hyper-parameter corresponding to the multiplier 2σk` in Corollary 2. To fulfill the conditions in Corollary 2, we employ global sum pooling as the readout function R, where as the decoder D here can consists of either fully-connected layers or graph convolutional layers. The pseudo-code are provided in Appendix C.

heading: 3 THEORETICAL ANALYSIS AND RELATIONS WITH PRIOR WORK
text: In this section, we further theoretically justify and motivate LaGraph by providing comparisons and connections between our method and existing related methods, including denoising autoencoders (Vincent et al., 2010; Wang et al., 2017), information bottleneck principle (Tishby et al., 1999), and contrastive methods based on local-global mutual information maximization (Veličković et al., 2019; Sun et al., 2019; Hassani and Khasahmadi, 2020).

heading: 3.1 DENOISING AUTOENCODERS
text: Denoising autoencoders employ an encoder-decoder network architecture and perform self-supervised training by masking or corrupting a portion of dimensions of the given data, and reconstruct the masked or corrupted value given their context. Such an approach have been also applied for selfsupervised image denoising (Batson and Royer, 2019), known as the blind-spot denoising. Similarly to our method, the denoising autoencoder can be also viewed as an approximation of the latent graph prediction. Using the same notation in Section 2, we formulate the connection between latent graph prediction and the graph denoising autoencoder in the following theorem. Theorem 2. Let J be a uniformly sampled subset of node indices of the given graph (A,X), F be the class of all graph neural networks, and F∗ be the class of graph neural networks such that f∗J (A,X) does not depend on XJ , for any J and f
∗ ∈ F∗. Given any graph neural network f ∈ F , there exist f∗ ∈ F∗ and f ′ ∈ F such that EA,X,F [ ‖f(A,X)− F ‖2 + ‖X − F ‖2 ] =EA,X ‖f(A,X)−X‖2 +
EA,X,F [2〈f(A,X)− F ,X − F 〉] (7) ≈EA,X ‖f∗(A,X)−X‖2 (8) =|V |EJEA,X ‖f ′J(A,XJc)−XJ‖ 2 /|J |. (9)
Equation (7) is proved in the proof of Theorem 1. It can be verified that the second term, i.e., the expectation of the inner product, in Equation (7) reduces to zero when the neural network f satisfies that fJ(A,X) does not depend on XJ , for any J , according to Batson and Royer (2019). The objective can be therefore approximated by Equation (8) with the neural network f∗ satisfying such a property. To let any graph neural network f satisfy the property, one can apply masks to a portion of nodes indexed by J so that their original value is inaccessible by f when predicting fJ(A,X). Therefore, the latent graph prediction objective under supervision can be further approximated by Equation (9), who describes the objective of a graph denoising autoencoder.
A substantial difference between our method and the denoising autoencoder lies in how to handle the inner product term in Equation (7). In particular, the denoising autoencoder forces the term to be zero by assuming certain property of the graph neural network, whereas our method derives an upper bound, i.e., the invariance term, for the inner product. Theoretically, the graph denoising autoencoder is equivalent to our framework with infinite weight scalar for the invariance term. As a drawback, when fJ(A,X) does not depend on XJ , the learned representations can be less informative as representations of nodes in VJ do not include the information of XJ , for any J , leading to performance loss. Our proposed upper bounds allow an encoder to access a certain level of information of the masked nodes, whose representations can be as good as ones from supervised learning. In fact, our method can be viewed as an autoencoder with an invariance regularization.

heading: 3.2 THE INFORMATION BOTTLENECK PRINCIPLE
text: The information bottleneck principle (Tishby et al., 1999) is a technique for data compression and signal processing in the field of information theory, and has been widely applied in deep learning problems (Tishby and Zaslavsky, 2015; Saxe et al., 2018). Let X be a random variable to be compressed, X̃ be an observed relevant variable, and Z denote the compressed representation of X . The information bottleneck principle seeks to optimize the following problem
Z∗ = argmin Z I(Z; X̃)− βI(Z;X), (10)
where I(·; ·) denotes the mutual information and β > 1 is a Lagrange multiplier. The work Barlow Twin (Zbontar et al., 2021) has discussed a connection between the information bottleneck principle and self-supervised learning. In particular, to apply information bottleneck to SSL, one usually obtain X̃ by performing augmentations or distortions on the given data X . And Equation (10) can be rewritten into
Z∗ = argmin Z
[ H(Z)−H(Z|X̃) ] − β [H(Z)−H(Z|X)] (11)
= argmin Z
H(Z|X)− λH(Z), (12)
where λ = β−1β > 0 is a weight scalar. Intuitively, the conditional entropy H(Z|X) is to be minimized, indicating that the distortion should add no additional information to the representation Z. In other words, the representation Z should be as invariant as possible to distortions applied to X . In addition, the entropy H(Z) is to be maximized, indicating that the representation Z itself should be as informative as possible.
The two terms in objectives of LaGraph correspond to the terms in Equation (12). In particular, the invariance term corresponding to H(Z|X) and the reconstruction term aims to ensure informative representations, i.e., to maximize H(Z). Objectives in existing SSL methods such as BYOL (Grill et al., 2020), its variation BGRL (Thakoor et al., 2021) in graph domain, and Barlow Twin (Zbontar et al., 2021) also include invariance terms corresponding to H(Z|X). To encourage informative representations, Barlow Twin further include a redundancy reduction term to minimize the crosscorrelation between different dimensions of the representation, as a proxy of the maximization of H(Z). In spite of the similarity, there are still substantial differences as discussed in Appendix D. In addition, the InfoNCE (NT-XENT) loss employed in some contrastive learning methods (You et al., 2020; Zhu et al., 2020) induces a similar effect, according to Zbontar et al. (2021). Both Equation (12) and the derivation of LaGraph objectives indicate the importance of the invariance term in SSL objectives. In addition, compared to the redundancy reduction term in Barlow Twin and the noise contrast in InfoNCE, LaGraph objectives can directly guarantee the learning of informative representations measured by the reconstruction capability.

heading: 3.3 CONTRASTIVE LEARNING BY MAXIMIZING LOCAL-GLOBAL MUTUAL INFORMATION
text: Motivated by Deep InfoMax (Hjelm et al., 2019), recent graph self-supervised learning methods (Veličković et al., 2019; Sun et al., 2019; Hassani and Khasahmadi, 2020) constructs their learning tasks by maximizing the mutual information between local (node-level) representations and a global (graph-level) summary of the graph. Practically, as a k-layer encoder E has the receptive field of at most k-hop neighborhood, the goal becomes the maximization of the mutual information between local representations and their k-hop neighborhood, formulated as
E∗ = argmax E |V |∑ i=1 I(X (k) i ; Ei(A,X)), (13)
where I denotes the mutual information, X(k)i is the k-hop neighborhood of node i, E is a graph encoder with k GNN layers, and Ei(A,X) denotes the local representation of node i. The learning objective is motivated by the goal that the local representations should contain as much the global information of the entire graph (or the k-hop neighborhood) as possible.
As for LaGraph, the reconstruction term encourages representations to contain sufficient information to reconstruct the input features while the invariance term limits the information accessibility from a local node when reconstructing its features. The two terms in the objective jointly promote node representations to learn limited local information and as much contextual information from the neighborhood as possible for reconstruction. It hence has a similar effect to the local-global mutual information maximization.

heading: 4 EXPERIMENTS
text: We conduct experiments on both node-level and graph-level self-supervised representation learning tasks with datasets used in two most recent state-of-the-art methods for SSL (You et al., 2020; Thakoor et al., 2021). For graph-level tasks, we follow GraphCL (You et al., 2020) to perform evaluations on eight graph classification datasets (Wale and Karypis, 2006; Borgwardt et al., 2005; Dobson and Doig, 2003; Debnath et al., 1991; Yanardag and Vishwanathan, 2015) from TUDataset (Morris et al., 2020). For node-level tasks, as the citation network datasets (McCallum et al., 2000; Giles et al., 1998; Sen et al., 2008) are recognized to be saturated and unreliable for GNN evaluation (Shchur et al., 2018; Thakoor et al., 2021), we follow Thakoor et al. (2021) to include four transductive node classification datasets from (Shchur et al., 2018), including Amazon Computers, Amazon Photos from the Amazon Co-purchase Graph (McAuley et al., 2015), Coauthor CS, and Coauthor Physics from the Microsoft Academic Graph (Sinha et al., 2015). We further include three larger scale inductive datasets, PPI, Reddit, and Flickr, for node-level classification used in SUBG-CON (Jiao et al., 2020).
We follow You et al. (2020) and Zhu et al. (2020) for the standard linear evaluation protocols at graph-level and node-level, respectively. In particular, for both levels, we first train the graph encoder on unlabeled graph datasets with the corresponding self-supervised objective. We then compute and freeze the corresponding representations and train a linear classification model on top of the fixed representations with their corresponding labels. Linear SVM and the regularized logistic regression are employed as linear classifiers for graph-level datasets and node-level datasets, according to You et al. (2020) and Zhu et al. (2020), respectively. For inductive node-level datasets, the self-supervised training is only performed on graphs in the training datasets whereas the test graphs are unavailable during the self-supervised training.

heading: 4.1 COMPARISONS WITH BASELINES
text: We perform experiments on both graph-level and node-level datasets to demonstrate the effectiveness of LaGraph. We construct our model and losses according to Section 2.4. Detailed model configurations, training settings, and dataset statistics are provided in Appendix G.
Graph-level Datasets. We evaluate the performance of LaGraph in terms of the linear classification accuracy and compare it with three kernel-based methods including graphlet kernel (GL) (Shervashidze et al., 2009), Weisfeiler-Lehman kernel (WL) (Shervashidze et al., 2011), and deep graph
kernel (DGK) (Yanardag and Vishwanathan, 2015), together with five unsupervised methods including Node2Vec (Grover and Leskovec, 2016), Sub2Vec (Adhikari et al., 2018), Graph2Vec (Narayanan et al., 2017), GAE and VGAE (Kipf and Welling, 2016). We further compare the results with recent SOTA SSL methods based on contrastive learning, including InfoGraph (Sun et al., 2019) , MVGRL (Hassani and Khasahmadi, 2020), and GraphCL (You et al., 2020). Results in Table 1 show that LaGraph outperforms the current SOTA methods on a majority of datasets and is on par with the best performance on the rest of datasets. Additional results adopting LaGraph as a pre-training strategy under the semi-supervised learning setting are provided in Appendix F.
Node-level Datasets. We perform node-level experiments on both transductive and inductive learning tasks. For the evaluation of transductive learning, we compare the performance of LaGraph in terms of linear classification accuracy with DeepWalk (Perozzi et al., 2014b), GAE, VGAE, and six contrastive learning methods including Deep Graph InfoMax (DGI) (Veličković et al., 2019), GMI (Peng et al., 2020), MVGRL (Hassani and Khasahmadi, 2020), GRACE (Zhu et al., 2020), GCA (Zhu et al., 2021), and BGRL (Thakoor et al., 2021), where BGRL is the current state-of-theart SSL method for node-level representation learning. We further include the results of directly performing linear classification on raw node feature (raw features) and by supervised training for references. To be consistent to Thakoor et al. (2021), we have ensured that the GPU memory consumption of LaGraph are under 16GB for the four transductive datasets. We then perform additional experiments on the larger-scale inductive datasets (Zitnik and Leskovec, 2017; Zeng et al., 2019; Hamilton et al., 2017) and compare our results in terms of micro-averaged F1-score with DeepWalk, unsupervised GraphSAGE (Hamilton et al., 2017), DGI, GMI, SUBG-CON (Jiao et al., 2020) and BGRL. Results for both transductive datasets and inductive datasets shown in Table 2 suggest competitive performance of LaGraph compared to the existing SOTA methods.

heading: 4.2 ABLATION STUDY
text: We further conduct three ablation studies to explore model robustness to smaller batch sizes on graph-level data and to training with sub-graphs on large-scale node-level datasets. An additional ablation study on the effect of optimizing different objectives is provided in Appendix G.
Robustness to Batch Sizes. Different from contrastive learning methods, LaGraph does not requires negative samples to perform noise contrast or pair-wise discrimination. Therefore, an advantage of LaGraph is that the performance is robust to the batch size as it does not depend on large batch sizes with sufficient negative samples. To verify the statement, we perform ablation study on how model performance changes when decreasing the batch size from 128 to 8 for graph-level datasets. We include corresponding results of GraphCL who uses InfoNCE for references and show the comparisons in Figure 2. The results indicate while contrastive methods based on InfoNCE suffer from significant performance loss with a small batch size, LaGraph are more robust to the batch size.
COLLAB
RDT-B
Training on Sub-Graphs for Large-Scale Datasets. Training graph encoders on all nodes for some large-scale graphs can be heavily expensive in computation. We hence conduct ablation study on how training graph encoders on a portion of sampled nodes instead of entire graph affect the effectiveness of training. Results in Table 3 suggest that the model perfor-
mance remains stable when decreasing the number of nodes until the number becomes extremely small. The collapse is due to the very sparse connectivity and LaGraph fails to reconstruct a node from its neighbor nodes as there is no neighbors at all. In contrast, though GraphCL does not collapse at extremely small subsets, it suffer more from performance loss above 1,000 nodes and consumes significantly more GPU memory.

heading: 5 CONCLUSIONS AND FUTURE DIRECTIONS
text: We introduced LaGraph, a state-of-the-art predictive SSL framework whose objectives are based on the self-supervised latent graph prediction. We provided theoretical analysis and discussed the relationship between LaGraph and theories in different related domains. Experimental results demonstrate the strong effectiveness of the proposed framework and the stability to the training scale for both graph-level and node-level tasks. Currently, our framework mainly considers the latent graph regarding its node features. Only limited topology information can be included by augmenting node features, e.g., with node degrees. Further investigation into a latent graph prediction framework that includes richer information such as edge features and latent connectivity into self-supervision can potentially bring additional improvement on the performance. See more discussions in Appendix G.
REPRODUCIBILITY STATEMENT
The experiment setting and evaluation protocol are described in Section 4. To ensure reproducibility, we provide implementation details, model configurations, and the selection of hyper-parameters in Appendix G. In addition, we provide the proof to all theorems and corollaries in Appendix A and Appendix B. The code to fully reproduce the results will be released upon acceptance of the paper.

heading: A PROOF OF THEOREM 1
text: Proof. We first derive the relationship between the supervised objective of latent graph prediction E ‖f(A,X)− F ‖2 and the self-supervised reconstruction lossE ‖f(A,X)−X‖2 in the following equations,
E ‖f(A,X)−X‖2 = E ‖(f(A,X)− F )− (X − F )‖2 (14) = E [ ‖f(A,X)− F ‖2 + ‖X − F ‖2 − 2〈f(A,X)− F ,X − F 〉 ] , (15)
where 〈·, ·〉 denotes the inner product along all dimensions {0, · · · , d|V | − 1}. The expectation E‖f(A,X)‖ in the above equation is not relevant to the neural network f . It hence can be considered as a constant during the optimization of f . To derive an upper bound to E ‖f(A,X)− F ‖2, we only need to derive an upper bound of its equivalentE ‖f(A,X)−X‖2+2E〈f(A,X)−F ,X−F 〉. As F is unobserved, our goal is to derive an upper bound to eliminate the need of F for the inner product term 〈f(A,X)− F ,X − F 〉. To do so, we apply the definition of latent graph E[X|A,F ] = F and rewrite the inner product into the following form.
E〈f(A,X)− F ,X − F 〉 = EA,FEX [∑
i
(fi(A,X)− Fi)(Xi − Fi)|A,F ]
(16)
= ∑ i EA,F [ E [ (fi(A,X)− Fi)(Xi − Fi)|A,F ] −
E [ fi(A,X)− Fi|F ] E [ Xi − Fi|A,F ]] (17)
= ∑ i EA,F [Cov(fi(A,X)− Fi,Xi − Fi|A,F )] (18)
= ∑ i EA,F [Cov(fi(A,X),Xi|A,F )] , (19)
where i sums over all dimensions {0, · · · , d|V | − 1}, fi and Xi denotes the i-th element of the flattened matrices. Note that we employ E[X − F |A,F ] = 0 to let Equation (17) hold, according to the definition of latent graphs. Letting J be a uniformly sampled subset of all node indices {0, · · · , |V | − 1}, the right hand side of the above equation satisfies
RHS = EJ |V | |J | ∑ j∈J d−1∑ k=0 EA,F [Cov(fjd+k(A,X),Xjd+k|A,F )] , (20)
where fjd+k ∈ R and Xjd+k ∈ R denote the (jd + k)-th element of corresponding matrices, i.e., the k-th element of the node vj , whereas XJ ∈ R|J|×d denotes the feature matrix of nodes in VJ . Given the bounded variance Var(Xi) ≤ σ2,∀i, we bound the above term as
RHS = EJ |V | |J | ∑ j∈J,k EA,F [ Cov(fjd+k(A,X)− fjd+k(A,XJc),Xjd+k|A,F ) ] (21)
≤ EJ |V | |J | ∑ j∈J,k EA,F [ Var(fjd+k(A,X)− fjd+k(A,XJc)|A,F ) ·Var(Xjd+k) ]1/2 (22)
≤ |V |EJ ( 1
|J | ∑ j∈J,k EA,F [ Var(fjd+k(A,X)− fjd+k(A,XJc)|A,F ) · σ2 ])1/2 (23)
≤ σ|V |EJ ( 1
|J | ∑ j∈J,k EA,F
[ E [[ fjd+k(A,X)− fjd+k(A,XJc) ]2|A,F ]])1/2 (24) = σ|V |EJ ( 1
|J | ∑ j∈J,k E [ fjd+k(A,X)− fjd+k(A,XJc) ]2)1/2 (25)
= σ|V |EJ ( 1
|J |E ‖fJ(A,X)− fJ(A,XJc)‖ 2
)1/2 . (26)
Above inequalities and equations are derived based on the fact that fJ(A,XJc) does not correlate to Xjd+k as j /∈ Jc for Equation (21), the Cauchy-Schwarz inequality for Inequality (22), and (EX)2 ≤ EX2 for Inequality (23). We complete the proof of Theorem 1 by combining Equation (15) and Inequality (26),
E [ ‖f(A,X)− F ‖2 + ‖X − F ‖2 ] = E ‖f(A,X)−X‖2 + 2〈f(A,X)− F ,X − F 〉 (27)
≤ E ‖f(A,X)−X‖2 +2σ|V |EJ ( 1
|J |E ‖fJ(A,X)− fJ(A,XJc)‖ 2
)1/2 . (28)

heading: B PROOF OF COROLLARY 1 AND 2
text: Proof. We first prove Corollary 1. Consider an `-Lipschitz continuous prediction head with respect to l2-norm consists of fully connected layers. We have
‖fJ(A,X)− fJ(A,XJc)‖2 = ‖D(HJ)−D(H ′J)‖2 ≤ ` ‖HJ −H ′J‖2 . (29) We therefore have the following inequality
E ‖fJ(A,X)− fJ(A,XJc)‖22 ≤ E [ `2 ‖HJ −H ′J‖ 2 2 ] . (30)
We apply the above inequality to Theorem 1 and obtain the following inequality E [ ‖f(A,X)− F ‖2 + ‖X − F ‖2 ] ≤ E ‖f(A,X)−X‖2 +2σ|V |EJ ( 1
|J |E ‖fJ(A,X)− fJ(A,XJc)‖ 2
)1/2 (31)
≤ E ‖f(A,X)−X‖2 +2σ|V |EJ ( 1 |J |E [ `2 ‖HJ −H ′J‖ 2 2 ])1/2 (32)
= E ‖f(A,X)−X‖2 +2σ|V |`EJ ( E ‖HJ −H ′J‖ 2 2 /|J | )1/2 , (33)
which completes the proof of Corollay 1.
Similarly, for Corollay 2, we have
‖fJ(A,X)− fJ(A,XJc)‖2 = ‖D(HJ)−D(H ′J)‖2 ≤ ` ‖HJ −H ′J‖2 . (34) Given an `r-Bilipschitz continuous readout functionR, the following inequalities hold,
1 `r ‖HJ −H ′J‖2 ≤ ‖R(HJ)−R(H ′J)‖2 ≤ `r ‖HJ −H ′J‖2 . (35)
We therefore have E [ ‖f(A,X)− F ‖2 + ‖X − F ‖2 ] ≤ E ‖f(A,X)−X‖2 +2σ|V |`EJ ( E ‖HJ −H ′J‖ 2 2 /|J | )1/2 (36)
≤ E ‖f(A,X)−X‖2 +2σ|V |``rEJ ( E ‖R(HJ)−R(H ′J)‖ 2 2 /|J | )1/2 (37)
= E ‖f(A,X)−X‖2 +2σ|V |k`EJ ( E ‖z − z′‖22 /|J | )1/2 , (38)
which completes the proof of Corollay 2.

heading: C PSEUDO-CODE FOR COMPUTING LAGRAPH OBJECTIVES
text: The pseudo-code for computing LaGraph objectives for node-level representations and graph-level representations are shown in Algorithms 1 and 2.
Algorithm 1 LaGraph objective: node-level Inputs: A mini-batch of graphs {G1, · · · , GN}, the encoder E , the prediction head D, and the hyper-parameter α. . Gi = (Ai,Xi)
for i in 1, · · · , N do Generate random Ji ∈ {0, 1}|Vi|×1, M ∈ R|Vi|×d Xi,Jci ← 1Jci X + 1Ji M . Randomly mask nodes Hi ← E(Ai,Xi) . Compute node representations H ′i ← E(Ai,Xi,Jci ) Xrec ← D(Ai,Hi) . Reconstructed node attributes `rec,i ← ‖Xrec,i −Xi‖2 /|Vi| `inv,i ← ‖1Ji Hi − 1Ji H ′i‖2 end for L(E ,D; {G1, · · · , GN}) = 1N ∑ i `rec,i + α( ∑ i `inv,i/ ∑ i |Ji|)1/2
Algorithm 2 LaGraph objective: graph-level Inputs: A mini-batch of graphs {G1, · · · , GN}, the encoder E , the prediction head D, the readout functionR, and the hyper-parameter α. . Gi = (Ai,Xi)
for i in 1, · · · , N do Generate random Ji ∈ {0, 1}|Vi|×1, M ∈ R|Vi|×d Xi,Jci ← 1Jci X + 1Ji M . Randomly mask nodes Hi ← E(Ai,Xi) . Compute node embeddings H ′i ← E(Ai,Xi,Jci ) zi ← R(Hi) . Readout graph representations z′i ← R(H ′i) Xrec ← D(Ai,Hi) . Reconstructed node attributes `rec,i ← ‖Xrec,i −Xi‖2 /|Vi| `inv,i ← ‖zi − z′i‖2 end for L(E ,D; {G1, · · · , GN}) = 1N ∑ i `rec,i + α( ∑ i `inv,i/ ∑ i |Ji|)1/2

heading: D DISCUSSION ON THE DIFFERENCES TO BGRL AND BARLOW-TWIN OBJECTIVES
text: In spite of the similarity in the objective of BGRL, Barlow-Twin, the consistency regularization (Wei et al., 2020), and the invariance term of the LaGraph objective, we argue that there are substantial differences between the invariance term in our objective and the BGRL and Barlow-Twins objectives. Regarding how the objective is computed, the invariance term is only computed for the masked nodes in Theorem 1 and objective for node-level representations, in contrast to the BGRL and Barlow-Twins objectives where all nodes are computed. It is worth noting that the objective is an upper bound to the latent graph prediction only if the invariance is computed on the masked nodes, according to the derivation during Proof of Theorem 1. Intuitively, during the computation of a node representation, the invariance term enforces the encode to capture less information from the node itself and more contextual information. If we also include unmasked nodes like BGRL, the invariance will lead to a contradicted effect, i.e., enforcing encoders to capture less information from contextual nodes, as it lets the representation remain consistent when its neighbor nodes (who are masked) are changed. We believe the derivation and the intuition of the proposed objective can provide guidance on how to adopt the consistent regularization into SSL studies.

heading: E EXPERIMENT SETTINGS AND MODEL CONFIGURATIONS
text: Dataset Statistics. Statistics including number of graphs, averaged number of nodes, averaged number of edges, and node attribute dimensions are summarized in Table 4.
Transductive and Inductive Settings. For node-level tasks, data typically consists of one or more large graphs with nodes and edges. The goal of self-supervised learning on such node-level datasets is to learn high-quality node representation that facilitates downstream node classification tasks. Our node-level experiments are divided into two categories, namely, transductive and inductive tasks. Transductive self-supervised learning of node representation allows utilization of all data at hand to pre-train GNNs for downstream tasks. Although labels of nodes are not visible during pre-training, patterns and information present in all nodes are observed. In contrast to transductive learning, inductive self-supervised learning only allows using a portion of data to pre-train GNNs, while holding out a certain amount of data for downstream tasks. Our inductive tasks include two cases. First, the PPI dataset consists of 24 graphs, and the training and testing nodes are split by graphs. In this case, the inductive task is considered across multiple graphs. In other words, node representations are learned from training graphs, and the encoder is evaluated on testing graphs. Second, Flickr and Reddit each consist of only one graph, the training and testing nodes are from the same graph. During self-supervised training, all test nodes are masked-out. During evaluation, all training nodes are masked-out, i.e., test nodes are unseen nodes of the graph. For both cases of inductive learning, data used during the self-supervised training stage and data used during evaluation stage are distinct, but the feature dimensionality should be the same for data used in both stages.
Experimental Details. We train graph-level datasets on a single 11GB GeForce RTX 2080 Ti GPU, and train node-level datasets on a single 56GB Nvidia RTX A6000 GPU. Our experiments are implemented with PyTorch 1.7.0 and PyTorch Geometric 1.7.0. All neural networks employ batch normalization (Ioffe and Szegedy, 2015), and are optimized with Adam optimizer. We initialize GNNs with Xavier initialization (Glorot and Bengio, 2010).
Models for Graph-Level Datasets. We employ a 3-layer GIN (Xu et al., 2019) as the graph encoder E , and a 2-layer MLP as the decoder D. Following GraphCL (You et al., 2020), we use a hidden dimension of size 32 and concatenate the embedding at each encoding layer to obtain the final representation. To fulfill the conditions in Corollary 2, we apply global sum pooling as the readout function R. The obtained graph representation is then taken by a SVM classifier with a 10-fold evaluation. For graph datasets that do not come with node attributes, we apply the one-hot
vector of the degree for each node as the node attributes so that the node degrees are reconstructed. Certain thresholds for max degrees are applied to reduce computational cost and avoid over sparse node features. The neural network is trained using the loss described in Equation (6). We mask all attributes of the sampled nodes with Gaussian noise. Detailed training configurations including mask ratio, standard deviation of noise, weight scalar α′ and threshold for max degrees are shown in Table 5. Note that we do not include carefully designed implementation mechanisms by BGRL, such as stop gradients, EMA, and batch normalization at the last layer.
Models for Node-Level Datasets. For node-level datasets, we employ a 2-layer GCN (Kipf and Welling, 2017) as the graph encoder E , and a linear layer or an MLP as the decoder D. We use a hidden dimension of size 512 at each encoding layer. The neural network is trained using the loss described in Equation (3). We uniformly employ the weight scalar α′ of 2 as we observed that the model performance is not sensitive to the selection of α′ within the range [1, 100]. We obtain the final node representation by concatenating the original feature with the embedding from the last layer of encoder. The intuition of this is based on the Bayesian rule where the learned encoder provides the prior knowledge (Ulyanov et al., 2018) of data distribution whereas the given graph data serves as the observed samples. And the posteriori should be based on a combination of the priori (encoder output) and the observed data itself (Laine et al., 2019). Node representation is then taken by a logistic regression classifier that is trained using the cross entropy (CE) loss with a learning rate of 0.01. Detailed training configurations including mask ratio, standard deviation of noise, number of encoder and decoder layers, learning rate and weight decay of the graph neural network, training epochs and weight decay of the logistic regression classifier are shown in Table 6. To split train, valid and test sets, we use the public split used in (Shchur et al., 2018) for Coauthor and Amazon, (Zitnik and Leskovec, 2017; Hamilton et al., 2017; Zeng et al., 2019) for PPI, Reddit and Flickr provided by PyTorch Geometric. Note that we do not include implementation mechanisms by BGRL, such as stop gradients, EMA, and batch normalization at the last layer.

heading: F EXPERIMENTAL RESULTS UNDER SEMI-SUPERVISED SETTING
text: For graph-level datasets, we perform semi-supervised experiments with 10% label rate using both GIN and GCN. All experiments are conducted with the same random seed to avoid randomness in data split and initialization. Under the setting of random initialization followed by supervised learning, the GNN is random initialized without pre-training. Under the setting of LaGraph followed by supervised learning, the GNN is pre-trained with the proposed LaGraph framework. Weights of GNNs are fine-tuned during the supervised learning with 10% labels. For each dataset, learning rate and epoch number for pre-training are the same as what we use under unsupervised setting. For fine-tuning, learning rate is selected from {10−3, 10−4, 10−5}, and epoch number is selected
from {5, 10, 15, 20}. The results shown in Table 7 and Table 8 indicate that our proposed LaGraph framework is also effective for semi-supervised learning with different GNN backbones.

heading: G ADDITIONAL ABLATION STUDIES.
text: Ablation on Optimizing Different Objectives. We empirically compare the effect of different upper bounds on graph-level datasets. In addition to objectives described in Corollary 2, we further train the graph encoder with the upper bound described in Theorem 1, who applies invariance regularization on the reconstructed node features. In addition, as node attributes in many graph-level datasets are formed as one-hot vectors of node type, we also provide the results of using two corresponding multinomial versions of the objective. In particular, we replace the reconstruction term by the cross-entropy between f(A,X) and X and, if computed on the outputs, the invariance term by the KL-divergence between fJ(A,X) and fJ(A,XJc). Note that the multinomial versions are no longer strictly upper bounds of supervised latent graph prediction. In Table 10, we show the results obtained under four objectives above, namely, to compute invariance on on-embedding (MSE-Embed), on-output (MSE-Output), and their corresponding multinomial versions (CE-Embed and CE-Output), respectively. Results indicate that there is no significant difference among the four versions on most datasets, while MSE-Embed and CE-Embed generally tend to be more stable and achieve higher performance on MUTAG, RDT-B, and RDT-M5K.
Ablation on Concatenated Representations for Node-Level Datasets. For the node-level datasets, We obtain the final node representation by concatenating the original feature with the embedding from the last layer of encoder, due to the intuition discussed in Appendix . Results in Table 10 compare the performance of representations with or without concatenations. The removal of the concatenation leads to reduced performance on four of the seven datasets, and performance gain on the rest datasets including the most challenging PPI. The results indicates that the concatenation generally positively contributes to the final performance. However, the conclusion still holds that, on node-level datasets, LaGraph can provide significant performance gain on challenging datasets where there is a gap between SSL and supervised performance. Meanwhile, the performance of LaGraph is on par with the performance of supervised learning and the SOTA method BGRL on datasets that are less challenging.

heading: H ADDITIONAL DISCUSSION ON POTENTIAL LIMITATIONS AND FUTURE DIRECTIONS
text: In this section, we discuss several limitations of the proposed method and their solutions or related future directions.
Non-significant improvement compared to BGRL on transductive tasks. From the experimental perspective, we admit that BGRL is a quite strong baseline method for transductive tasks. As the results are already on the same level as the performance of supervised training, it is very difficult to further obtain significant improvements. However, when it comes to inductive tasks, where there is still a significant gap between the performance of BGRL and supervised learning, our method is able to bring significant improvements in performance. Therefore, we argue that the non-significant performance boost on some transductive datasets does not degrade our main conclusion about the effectiveness of our method.
Unattributed graphs. Although, in this work, we mainly focus graphs with attributed nodes, there exists cases where the nodes are unattributed and its all information are contained in the graph topology, especially for some graph-level datasets. In such cases, we follow a common solution to consider the one-hot vectors of node degrees as the node attributes and our objective performs reconstruction on the node degree. To avoid inconsistency between training and testing graphs in their range of degrees, we introduce thresholds to the node degrees, i.e., the degree of a node is considered as k if it exceeds k. The current solution can capture topological information of a graph at some degree. However, there can be better solutions capturing full topological information of graphs. A potential direction is to perform connectivity reconstruction with invariance of representations to changing in the input edge set. Although the described approach does not currently fit into our theoretical framework, it is possible to derive similar objectives (e.g., upper bound to link prediction objective) following a similar idea.
Scaling-up issue. The scaling-up of graph neural networks becomes an emerging topic. Many existing self-supervised methods may suffer from the scaling-up issue, when the graph scales up to billions of nodes and edges. Although we do not perform experimental study on extremely large graphs, we perform ablation studies to demonstrate the robustness of our method to the training schemes of sampling subgraphs (mini-batches of nodes) for each training iterations.
Performance of SSL methods on unsupervised downstream tasks. Performing linear evaluation with supervised downstream tasks on learned representations is the most common way to evaluate the performance of SSL methods. However, evaluation performance on graph-specific unsupervised tasks such as overlapping community detection (Xie et al., 2013) are seldom studied. Further investigations in unsupervised downstream task are required to fully demonstrate the effectiveness of self-supervised learning methods.

Review summaries:
  In this paper, the authors propose a novel SSL method (i.e., LaGraph) for graph representation learning based on latent graph prediction. The overall presentation is good with sound theoretical analysis. There is also a theoretical comparison between LaGraph and various related work with different categories. Extensive experiments were conducted on various datasets for both node-level and graphs-level tasks, where the proposed method has competitive performance to a set of baselines. However, there are some details regarding the problem definitions, technical content, and experiment settings that need further clarification.

The paper proposes a new self-supervised learning framework for learning latent representations of graphs. Like recent SSL methods (BGRL,  Barlow twins), LaGraph does not rely on negative samples but only compares the embeddings of the graph to the embeddings of an augmented version of the graph. To avoid representational collapse, a reconstruction term (similar to denoising autoencoders) is used. They provide a theoretical analysis of the method which provides some connections to other approaches.

A method called LaGraph is proposed for semi-supervised graph representation learning. In particular, a new task named latent graph prediction is introduced, and the corresponding objective requiring no negativing samples is also derived. It is impressive that the proposed method requires no negative samples and works with a small batch size. 

The authors propose a self-supervised learning (SSL) framework for graph neural networks by predicting an unobserved latent graph. The proposed self-supervised learning loss is derived from upper bounds to the original objective functions for predicting latent graphs. The proposed method is robust to small sample size and small batch size.