Self-Supervised Representation Learning via Latent Graph Prediction
Authors: Yaochen Xie
Zhao Xu
Shuiwang Ji
Venue: ICLR 2022 Submitted (2022)
Keywords: Self-supervised learning
representation learning
graph neural networks

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.

Under review as a conference paper at ICLR 2022
SELF-SUPERVISED REPRESENTATION LEARNING VIA LATENT GRAPH PREDICTION
Anonymous authors Paper under double-blind review
ABSTRACT
Self-supervised learning (SSL) of graph neural networks is emerging as 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 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, La- Graph 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 decreasing of training sample size on both graph-level and node-level tasks.
INTRODUCTION
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 al. 2019 Wu et al. |019 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- basedd 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, (Veličković 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. (2220) 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 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 graph and trains GNNs discriminate between jointly sampled view pairs and independently sampled view pairs. In contrast, predictive methods (Hamilton al., 2017 Hwang et al., 2020 Rong al. 2020) train GNNs 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 con- trastive. 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 al.) (221) adapts BYOL Grril et al. 2020) to the graph domain. BGRL still obtains different views from each given graph, but eliminates the requirement negative samples by replacing contrastive objectives with the prediction of offline embedding. BGRL has achieved

---

Under review as a conference paper at ICLR 2022
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, 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 LaGruph and some existing contrastive methods (You 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.
2 METHODS
2.1 NOTATIONS AND PROBLEM FORMULATION
We consider an undirected graph G 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 R/V| denotes the adjacency matrix and X R V denotes the node features of dimension d. We employ graph encoder & 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) | and the graph-level representation or graph embedding by z = R(H) E R1xg, where q denotes the embedding dimension and R: RIVixg R1x9 is readout function.
Self-supervised representation learning is employed to train the graph encoder & on a set of K graphs [G without labels from downstream tasks. In particular, we seek 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 È is usually trained together with some prediction head D for predictive SSL or a discriminator for contrastive SSL.
2.2 LATENT GRAPH PREDICTION
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 æ, we assume that there exists corresponding latent data 27, determining the semantic of ær, such that the latent data æ generated from a prior p(æT) and the observed data instance is further generated from a certain distribution conditioned on the latent data, i.e., p(æ æz). 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 G2 = (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 F, of each node in observed graph is independently generated from certain distribution
2

---

Under review as a conference paper at ICLR 2022
conditioned on the corresponding latent graph. In other words, how æ, is generated from the latent feature fo is not affected by the generation 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 Gy] F. The above assumptions are natural when we have little knowledge about the generation process and commonly used in other types of data such 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 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 node- level 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|x[V| x R I + R xd that takes an observed graph G = (A, X) as inputs and
predicts the feature matrix of its latent graph Gz (A, F). When the ground truth of the latent feature matrix F is known, the learning objective can be designed as
f arg min E (I FI1
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 arg miny E [z) a|l where the mapping from the signal to the noisy data p(æ(s) can usually be explicitly modeled and samples of signal (ground truth) can usually be captured. In the data reconstruction case, pairs of (ax s) can be therefore directly captured or synthetically generated given a certain noise model p(æ: 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 Gz).
2.3 SELF-SUPERVISED UPPER BOUNDS FOR LATENT GRAPH PREDICTION
As discussed in the previous subsection, unlike typical noisy data reconstruction tasks, the latent graph not observed and p(G cannot be modeled explicitly. This makes it difficult to construct direct learning task for latent graph prediction using the objective in Equation (T). We therefore seek to optimize an alternative objective that approximately optimizes the objective in Equation (T) without requiring the distribution Gz), nor features F of the latent graph. We now introduce the proposed self- supervisdd objective for latent graph prediction.
We derive our self-supervised objective without involving F by constructing an upper bound of the objective in Equation (I). Specifically, we let J C {o...., IVI 1} be an arbitrary subset of node indices, J denote the complement of set J, and X,- == 1, & X + I, @ M be the feature matrix with features of nodes in Vy masked, where @ denotes element-wise multiplication, M R R x denotes matrix consisting of independent random noise or zeros as masking values, and y E IR denotes an indicator matrix such that I [ 1, Vi E J and Il / :] = O, Vi & J. We describe the self-supervised upper bound in Theorem [ whose proof is provided Appendix
Theorem 1. Consider graph G (A, X) and its latent graph Gz (A, We let the variance of any elements in X be bounded by o² and J be a subset of nodes V in the graph G. For any graph neural network f (0, 111Vix VI IR! Vixd RIV|xd, we have the following inequality
EAX [If(A.
F + X F1?
S EAX II(A,X) -X12+
1/2 (2)
EAX ff X) fo
20 V E,
[J]
Intuitively, the first component in the upper bound derived in Theorem measures the reconstruction on the feature matrix X of the given observed graph G, enforcing the intermediate representa- tions to be informative. The second component controls how much information is accessible from the input feature of node in when reconstructing the feature of u; by encouraging the output of
3

---

Under review as a conference paper at ICLR 2022
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- representation learning, are more interested in graph-level 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 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 & and decoder D in the graph neural network f. We introduce certain assumptions to the decoder network DD and the readout function R. 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 [
Corollary 1. Let G (A, X) be given graph, Gr (A. F) be its latent graph, & and 'D be graph encoder and a prediction head (decoder) consisting of fully fully-connected layers. If the prediction head D is 8- E-Lipschitz continuous with respect to 12-norm, we further have the following inequality,
1/2
E [D(H) - F1I + ||X
F(1] < D(H) - X1I 2
E H. J
H
(3)
where H = E), and H' = E xa) denote the node embedding of the given graph and the masked graph, respectively, and H. := HJ.. selects rows with indices J.
Corollary 2. Let G (A, X) be given graph, G₁ = (A. be its hidden latent graph, & be graph encoder. R be a readout function satisfying k-Bilipschitz continuity with respect to lo-norm, and D be a prediction head (decoder). If the prediction head D is E-Lipschitz continuous with respect to 12-norm, we have the following inequality,
E E
z²113
1/2
[I(HH) - F F + X
F(2]
S E D(H) - X1I + Vo E,
(4)
|
where: z = R(H and x' = 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 a holds when node features are from {0, 1)dd or when feature normalization is applied. The f-Lipschitz continuous property is common for neural networks. And the k- Billipsshitz 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 [ and Corollary [ To train encoder E together with decoder D under self-supervision, input to the encoder both the given graph (A, X) and its variation (A, X.-) with a random subset of node indices for nodes to be masked and obtain node-level representations H E(A, X) and H' = (()) ) for the two graphs respectively. The self-supervised losses are computed on input node features, reconstructed node features, and representations, as demonstrated in Figure []
In particular, we consider a mini-batch of N graphs ((A,, X,) and their corresponding masked variation {(A,, ((i.).e))) ))),,, where J; denotes the node indices subset for the i-th graph. The self-supervised loss for node-level representation learning follows Corollary and is computed as
1/2
1 N
Σ I.IA.. / ELL, H. 1, O H; J.
Tnode (node(E, (E,D)
(5)
1=1
where is hyper-paramedt conditions in Corollary we employ fully colle-coneected layers instead of graph convolutional layers in the decoder D. The pseudo-code provided in Appendix C
corresponding to the multiplier 2 in Corollary I To fulfill the
[
4

---

Under review as a conference paper at ICLR 2022
(A.X)
XI
Node-teval
B(AXX)
Graph-level
Dacoder D(-)
H
Dacader
D(H)
Mask V.
Draph Encoder
R(H)
S(-)
H
MSE(D (I).
NIS(D)
MSE 1
[MSE
(A.Xx
E y
Hi
Loss
H EXA,X, x
R(H))
Loss
Input graphs
Ropresentations
Representations
Figure 1: Overview of the LaGraph framework. Given training graph, we randomly mask small portion VG E V of its nodes and input both original graph and masked graph to the encoder &. Crossed nodes in the figure have all their attributes masked but topology preserved. The final loss consists of a reconstruction loss on node features and an invariance loss between representations of the original graph and the masked graph. We omit the encoding part of the graph-level framework as frameworks for the two levels mainly differ in whether the invariance term is computed on representations of masked nodes or graph-level representations obtained by R.
Similarly, using the same notations above, the self-superviser loss for graph-level representation learning follows Corollary 2 and is computed as
1/2
grraph (E, D)
1 N
DDA,, XiIl / a
Σ 2 x1ll" 1
|4,1
(6)
where 2; R(H,) and z R(H)) denote the graph-level representations obtained by applying readout function R. to the node-level representations, respectively, and a' is a hyper-parameter corresponding the multiplier 20ké in Corollary 2 To fulfill the conditions in Corollary - 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
3 THEORETICAL ANALYSIS AND RELATIONS WITH PRIOR WORK
In this section, we further theoretically justify and motivate LaGraph by providing comparisons and connections between our method and existing related methods, including denoising autoen- coders (Vincent et al., (0100 Wang et al. 2017). information bottleneck principle (Tishby et al. [999), and contrastive methods based local-global mutual information maximization (Veličković et al.) 2019 Sun et al.
2019 Hassani and Khasahmadi 2020).
3.1 DENOISING AUTOENCODERS
Denoising autoencoders employ encoder-decoder network architecture and perform self sule-super training by masking or corrupting a portion of dimensions of the given data, and reconstruct the masked corrupted value given their context. Such approach have been also applied for self- supervised image denoising (Batson and Royer| (2019), known as the blind-spot denoising. Similarly 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 the following theorem.
Theorem 2. Let J be a uniformly sampled subset of node indices of the given graph X), F be the class of all graph neural networks, and F be the class of graph neural networks such that (A, X) does not depend on X,, for any J and f E Ft. Given any graph neural network f F. there exist f F and f' E such that
E EAX.F
[f(,
F1
X
XFF
F11]]
-EAX x) 2
EAXXF [2 X) F. X
F?]
(7)
EAX (I - xx
(8)
=IV|E,EA, (I X,,) -x,1 /1//
(9)
5

---

Under review as a conference paper at ICLR 2022
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 fA, X) does not depend X,, for any J, according to Batson and Royer (019). 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 portion of nodes indexed by J so that their original value is inaccessible by f when predicting fs 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.
substantial difference between our method and the denoising autoencoder lies in how 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 drawback, when fo X) does not depend on X,, the learned representations can be less informative as representations of nodes in V, do not include the information of X,, for any J, leading to performance loss. Our proposed upper bounds allow encoder to access certain level of information of the masked nodes, whose representations can be as good as ones from supervised learning. In fact, our method be viewed autoencoder with invariance regularization.
3.2 THE INFORMATION BOTTLENECK PRINCIPLE
The information bottleneck principle Tishby et al., 1999) is technique for data compression and signal processing in the field of information theory, and has been widely applied 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 = arg min 1(2 X) - 3I(Z;
(10)
2
where ((:-) denotes the mutual information and B > is 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 distortions the given data X. And Equation rewritten into
(10)
can be
z" = arg min (((2)-((Z1))) z arg min H( (Z(
3 (H)) - H(]
(11)
(12)
where À = 2-1 0 is a weight scalar. Intuitively, the conditional entropy H (Z 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 is be maximized, indicating that the representation Z itself should be as informative as possible.
The two terms in objectives of LaGraph correspond the terms in Equation 12).. In particular, the invariance term corresponding to H X) and the reconstruction term aims to ensure informative representations, i.e., maximize HiZ). .. Objectives in existing SSL methods such BYOL Grill et al. 2020), its variation BGRL (Thakoor et al. 202T) in graph domain, and Barlow Twin (bbontar al. 2021) also include invariance terms corresponding to H ( X). To encourage informative representations, Barlow Twin further include a redundancy reduction term to minimize the cross- correlation between different dimensions of the representation, as a proxy of the maximization of H()). 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.

---

Under review as a conference paper at ICLR 2022
3.3 CONTRASTIVE LEARNING BY MAXIMIZING LOCAL-GLOBAN MUTUAL INFORMATION
Motivated by Deep InfoMax (Heelm et al. 2019). recent graph self supervised learning meth- ods (Velčković al., 2019 Sun et al., 2019 Hassami 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 k-layer encoder 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
IVI T(X (K), (A,
m arg max
(13)
where I denotes the mutual information, X is the k-hopp neighborhood of node i, E is graph encoder with & GNN layers, and (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 possible for reconstruction. It hence has similar effect to the local-global mutual information maximization.
4
EXPERIMENTS
We conduct experiments both node-level and graph-level self-supervised representation learning tasks with datasets used in two most recent state-of-the-an methods for SSL ( (You et al.) 2020 Thakoor
repprreritcdrrprreeentttttio
ett al. 202T). For graph-level tasks, we follow GraphCL. You et al. (0200) perform evaluations
eight graph classification datasets (Wale and Karypis 2006 Borgwardt et al. 2005 Dobson and Doig
2003 Debnath et al. [991 Yanardag and Vishwanathan (013) from TUDataset (Morris al.) 2020).
For leve- tasks, as the citation network datasets (McCallum et al. 2000; Giles et ] 1998; Sen
al.]|l1.00 (2008) are recognized to be saturated and unreliable for GNN evaluation (Shchur al. 2018 Thakoor et al. 2021), we follow Thakoor et al. (202T) to include four transductive node classificatinn
datasets from (Shchur et al. 2018)) including Amazon Computers, Amazon Photos from the Amazon Co-purchase Craph (McAuley et al. 2015), Coauthor CS, and Coauthor Physics from the Microsoft Academic Graph (Sinha et al. 2015). 5). We further include three larger scale inductive datasets, PPI, Reddit, and Flickr, for node-level classification used in SUBG-CON (Tiao 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- respectively. In particular, for both levels, we first train the graph encoder on unlabeled graph datasets with the corresponding celf-supervieed objective. We then compute and freeze the corresponding representations and train 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 it al. (2020) and Zhu et al. (2020), respectively. For inductive node-level datasets, the self-supervised training only performed on graphs the training datasets whereas the test graphs are unavailable during the self-supervised training.
4.1 COMPARISONS WITH BASELINES
We perform experiments on both graph-level and node-level datasets to demonstrate the effective- ness 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
Graph-level Datasets. We evaluate the performance of LaGraph in terms of the linear classifica- tion accuracy and compare with three kernel based methods including graphlet kernel (GL) (Sher) vashidze et al. 2009), Weisfeiler-LLehman kemel (WI.) (Shervashidze al. 201 T). and deep graph
7

---

Under review as a conference paper at ICLR 2022
Table 1: Performance on graph-level classification tasks, scores are averaged over runs. Bold and underlined numbers highlight the top-2 performance. OOM indicates running out-of-memory 56GB Nvidia A6000 GPU.
NCTI
PROTHINS
DD
MUTAG
COLLAB
RDT-B
RDT-M5K
IMDB-B
GL
81.7+2.1
77.340.2
41.00.2
65.9=1.0
WI.
80.0+0.5
72.9+0.6
80.7+3.0
68.8+0.4
46. 46.120.2
72,3=3.4
DGK
80.3+0.5
73.3+0.8
87,4+2.7
78.0+0.4
41,3+0.2
67.0=0.6
Node2 Vec
54.941.6
57.543.6
72.6+10.2
Sub2Vec
52.8+1.5
53.045.6
61.1
71.5+0.4
36.740.4
5..3+1.5
Gre
73.2+118
73,3+2.1
83.2+9.3
75.8+1.0
47.9+0.3
01.1=0.5
GAE
73.3+t0.6
74.1
77.9+0.5
84.0=0.6
56.3+0.1
74.8+0.2
37.6+1.6
52.1=0.2
VGAE
73.7+0.3
74.0#0.5
77.6+0.4
84,420.6
56.3+0.0
74.8+0.2
39.1#1.6
52.1=0.2
InfoGraph
76.2#1.1
74.4+0.3
72.9E18
89.0#1.1
70.721.1
82.5+1.4
53,5+1.0
73.0=0,9
GraphCL 77.9+0.4
74.4+0.5
78.6+0.4
8.,
71,4+1.2
89,5+0.8
56.0#0.3
71.1=0.4
MVGRL
75.1
71.5+0.3
OOM
89.7+1.1
OOM
84.5+0.6
OOM
74.2+0.7
LaGraph 79.920.5
75.2+0.4
78.1
90.2+1.1
77.620.2
90.4#0.8
56.4+0.4
73.7=0.9
Table 2: Performance on node-level datasets, 20 runs averaged. Results of SSL methods with the best performance are highlighted in bold numbers. Left: Mean classification accuracy on transductive datasets. Right: Micro-averaged FI scores on larger-scale inductive datasets.
Transductive Am.Comp.
Am.Pht.
Co.CS
Co.Phy
Inductive
PPI
Flickr
Reddit
Raw features
73,8=0.0
78.5=0.0
90.420.0
93.640.0
Raw feat.
42.5+0.3
20.340.2
58.540.1
DeepWalk
85.7+0.1
89.4=0.1
84.6#0.2
91.8+0.2
GAE
75.7=0.0
50.7+0.2
0OM
GAE
87.7+0.3
92.7=0.3
92.4=0.2
95.3+0.1
VGAE
75.8+0.0
50.4+0.2
0OM
VGAE
88.1+0.3
92.8=0.3
92.5=0.2
95.3+0.1
Super-GCN
51.5+0.6
48.7+0.3
93.3+0.1
Supervised
86.5+0.5
92.4=0.2
93.0=0.3
95.7+0.2
Super-GAT
97.3+0.2
00M
OOM
DGI
84,0=0.5
91.6#0.2
92.2=0.6
94.5#0.5
GraphSAGE
46.5+0.7
36.5+1.0
10.8=1.1
GMI
82.2+0.3
90.7=0.2
0OM
OOM
DGI
63.8+0.2
42.9+0.1
94.0#0.1
MVGRL
87.5+0.1
91.7=#.1
92.1
95.3+0.0
GMI
65.0=0.0
44.5+0.2
95.0+0.0
GRACE
87.5+0.2
92.2+0.2
92.9=0.0
95.3+0.0
SUBG-CON 66.9+0.2
48.8+0.1
95.240.0
GCA
88.940.2
92.5+0.2
93.1=0.0
95.7+0.0
BGRL-GCN 69.620.2
BGRL 89.7+0.3
92.920.3
93.2=0.2
95.620.1
BGRL-GAT 70.5+0.1
LaGraph
88.0+0.3
93.5+0.4
93.3+0.2
95.8+0.1
LaGraph 74.6+0.0 51.340.1 95.240.0
kernel (DGK)
Yanardag and Vishwanathan 2015). together with five unsupervised methods includ-
ing Node2 Vee (rrover and Leskovee (2016), Sub2Vec (Adhikari al.] 2018). Graph2 (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 al., 2019) MVGRL (Hassani and Khasahmadi 2020), and GraphCL Youu al. 2020). Results in Table show that LaGraph outperforms the current SOTA methods on majority of datasets and on par with the best performance on the rest of datasets. Additional results adopting LaGraph pre-training strategy under the semi-supervised learning setting are provided in Appendix
Node-level Datasets. We perform node-level experiments on both transductive and inductive learning tasks. For the evaluation of transductive learning, 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) (Veličković al. 2019)
GMI (Peng et al., 2020), MVGRL (Hassani and Khasahmadi 2020), GRACE (Zhu et al. 2020). GCA (Zhu al. (202)) and BGRL (Thkkoor al.) 2021), where BGRL the current state-of of the- art 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. (202T), 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-averagge
Fi-score with
Deep DeepWalk Walk, unsupervised GraphSAGE (Hamilton et al. 2017), DGI, GMI, SUBG-COS CBGG (Jiao et al. 2020)) and BGRL. Results for both transductive datasets and inductive datasets shown in Table 2
suggest competitive performance of LaGraph compared the existing SOTA methods.
8

---

Under review as a conference paper at ICLR 2022
Table Model performance when trained on subset of nodes.
# nodes sampled
100
1.000
2,500
5,000
10,000
all
% nodes sampled
0.22%
2.24%
5.60%
11.20%
22.41%
100.00%%
Fl-score LaGraph
6.07
51.12
51.12
51.27
51.29
51.26
Flickr
Memory LaGraph
1389MB
1465MB
1553MB
1725MB
2065MB
421
Fl-score GraphCL
45.27
45.27
45.27
45.38
45.45
45,48
Memory GraphCL
1647MB
2599MB
4137MB
6741MB
11905MB
47939MBB
nodes sampled
0.07%
0.65%
1.63%
3.25%
6.50%
100.00%
Fl-score- LaGraph
5.76
95.05
95.06
95.08
95.09
95.22
Reddit
Memory LaGraph
1403MB
1475MB
1585MB
1783MB
2161MB
16933MB
Fl-score GraphCL
93.24
93.24
93.25
93.31
93.32
OOM
Memory GraphCL
4199MB
6117MB
6687MB
9297MB
14495MB
OOM
4.2
ABLATION STUDY
We further conduct three ablation studies to explore model robustness to smaller batch sizes 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
Robustness to Batch Sizes. Different from contrastive learning methods. LaGraph does not re- quires negative samples to perform noise contrast or pair-wise discrimination. Therefore, an advantage of LaGruph 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 GraphCL who uses InfoNCE for references and show the com- parisons in Figure 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.
Training on Sub-Graphs for Large-Scale Datasets. Training graph encoders on all nodes for some large-scale
COLLAB
RDT-B
Top-1 Accuracy Dit.
Top-3 Accuracy Dff.
1. 1
-1
graphs can be heavily expen- sive in computation. We hence conduct ablation study on how training graph coders on a portion of sam- pled 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 node from its neighbor nodes there 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.
-2
1
LaGraph
GraphCL
GraphCL
36
32 Batch size
128
216
15
32
61
120
256
B Batch size
Figure 2: Model robustness to small batch sizes. Shown are changes accuracy compared the batch size of 256.
CONCLUSIONS AND FUTURE DIRECTIONS
We introduced LaGraph, a thee-arr- predictive SSL framework whose objectives are based on the self-supervins 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 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.
be included by augmenting node

---

Under review as a conference paper at ICLR 2022
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 thper-paaamente in Appendix G In addition, we provide the proof to all theorems and corollaries in Appendix and Appendix
The code fully reproduce the results will released upon acceptance of the paper.
REFERENCES
Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and B Aditya Prakash. Sub2vec: Feature learning for subgraphs. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 170-182. Springer, 2018.
Joshua Batson and Loic Royer. Noise2Self: Blind denoising by self-supervision. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 924-533, 2019.
Karsten M. Borgwardt, Cheng Soon Ong. Stefan Schönauer, S. V. N. Vishwanathan, Alex J. Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21:i47-i56, 06 2005. ISSN 1367-4803.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Proceedings of the International Conference on Machine Learning, 2020.
Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan Shusterman, and Corwin Hansch. Structure-actie relationship of mutagenic aromatic and heteroaromatic nitro compounds correlation with molecular orbital energies and bydrophobicity. Journal of Medicinal Chemistry, 34(2):786-797, 02 1991.
Jacob Devlin, Ming-Weiieeee Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pages
2019.
Paul D. Dobson and Andrew J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of Molecular Biology, 330(4):771-783, 2003. ISSN 0022-2836.
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the Third ACM Conference on Digital Libraries, page 89 10-99.8. Association for Computing Machinery, 1998. ISBN 0897919653.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9, pages 249-256 2010.
Sean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, koray kavukcuoglu, Remi Munos, and Michal Valko. Bootstrap your own latent new approach to self-supervised learning. In Advances Neural Information Processing Systems, volume 33, pages 21271-21284, 2020.
Aditya Grover and Jure Leskovec. Node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1024-1034, 2017.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi view representation learning on graphs. In Proceedings of the 37th International Conference on Machine Learning, 2020.
10

---

Under review as a conference paper at ICLR 2022
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2020.
Devon Hjelm, Alex Fedorov, Samuel Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations, 2019.
Karan Grewal, Phil Bachman, Adam
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitiik, Percy Liang, Vijay Pande, and Jure Leskovec.
Strategies for pre-training graph neural networks. In International Conference on Learning Representations, 2020.
Dasol Hwang, Jinyoung Park, Sunyoung Kwon, Kyung-Min Kim, Jung- Ha, and Hyunwoo Kim. Self-supervised auxiliary learning with meta-paths for heterogeneous graphs. arXiv preprint arXiv:2007.08294, 2020.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448-456. PMLR, 2015.
Yizhu Jiao, Yun Xiong, Jiawei Zhang. Yao Zhang, Tianqi Zhang, and Yangyong Zhu. Sub-graph con- trast for scalable self-supervised graph representation learning. arXiv preprint UrXiv:2009.1022 2020.
Wei Jin, Tyler Derr, Haochen Liu, Yiqi Wang, Suhang Wang, Zitao Liu, and Jiliang Tang. Self- supervised learning on graphs: Deep insights and new direction. arXiv preprint arXiv:2006.1011 2020.
Dongkwan Kim and Alice Oh. How find your friendly neighborhood: Graph attention design with self-supervision. In International Conference on Learning Representations, 2021.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint 1oxiv:/611.0770 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks In International Conference on Learning Representations, 2017.
Samuli Laine, Tero Karras, Jaakko Lehtinen, and Timo Aila. High-quality sclf-supervised deep image denoising. Advances in Neural Information Processing Systems, (16970-6980, 2019.
Xiao Liu, Fanjin Zhang, Zhenyu Hou, Zhaoyu Wang, Li Mian, Jing Zhang, and Jie Tang. Self- supervised learning: Generative or contrastive. arXiv preprint arXiv:2006.088: 08218, 1(2), 2020.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 43-52, 2015.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Tomas Mikolov, Kai Chen, G. Corrado, and J. Dean. Efficient estimation of word representations in vector space. In International Conference on Learning Representations, 2013a.
Tomas Mikolov, Ilya Sutskever, Kai Chen, G. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, 2013b.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. ICML 2020 Workshop Graph Representation Learning and Beyond (GRL+ 2020), 2020.
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. arXiv preprint arXiv: 1007.000000000 2017.
11

---

Under review as a conference paper at ICLR 2022
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong. Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Proceed- ings of The Web Conference 2020, pages 259-270, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 701-710, 2014a.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 701-710, 2014b.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Supf-super graph transformer on large-scale molecular data. In Advances in Neural Informa- tion Processing Systems, 2020.
Andrew Michael Saxe, Yamini Bansal, Joel Dapello, Madhu Advani, Artemy Kolchinsky, Bren- dan Daniel Tracey, and David Daniel Cox. On the information bottleneck theory of deep learning. In International Conference on Learning Representations, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-92 93, 2008
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurlPS 2018, 2018.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kerells for large graph comparison. In Artificial intelligence and statistics, pages 488-495. PMLR, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th International Conference on World Wide Web, pages 243-246, 2015.
Fan-Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. In Interna- tional Conference on Learning Representations, 2019.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Veličković, and Michal Valko. Bootstrapped representation learning on graphs. arXiv preprint arXiv:2102.0651/ 2021.
Naftali Tishby and Noga 7aslavsky. Deep learning and the information bottleneck principle. In 2015 IEEE Information Theory Workshop (ITW), pages 1-5. IEEE, 2015.
Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. The 37th annual Allerton Conference Communication. Control, and Computing, pages 368-377, 1999.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Deep image prior. pages 9446-9454, 2018.
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and Devon Hjelm. Deep graph infomax. International Conference on Learning Representations, 2019.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, Pierre-Antoine Manzagol, and
Léon Bottou. Stacked denoising autoencoders: Learning useful representations in deep network with a local denoising criterion. Journal of Machine Learning Research, 11(12), 2010.
N. Wale and G. Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. In Sixth International Conference on Data Mining, pages 678-689, 2006.
12

---

Under review as a conference paper at ICLR 2022
Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. Mgae: Marginalized graph autoencoder for graph clustering. Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pages 889-898 2017.
Hong Wang, Xin Wang, Wenhan Xiong, Mo Yu, Xiaoxiao Guo, Shiyu Chang, and William Yang
Wang. Self-supervised learning for contextualized extractive summarization. In Proceedings of the 57th Anmual Meeting of the Association for Computational Linguistics, pages 2221-2227, 2019.
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self self-training with deep networks on unlabeled data. arXiv preprint arXiv:2010.03622 2020.
Jiawei Wu, Xin Wang, and William Yang Wang. Self-supervised dialogue learning. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3857-3867, 2019.
Jierui Xie, Stephen Kelley, and Boleslaw K Szymanski. Overlapping community detection in networks: The state-of-the-an and comparative study. Acm computing surveys (csur), 45(4):133 2013.
Yaochen Xie, Zhengyang Wang. and Shuiwang Ji. Noise2Same: Optimizing self-supervised bound for image denoising. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems, pages 10320-203300 2020.
Yaochen Xie, Zhao Xu, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural networks: unified review. arXiv preprint arXiv:2 2021.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1365-1374, 2015.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Advances in Neural Information Processing Systems, volume 33, pages 5812-5823, 2020.
Jure Zbontar, Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. arXiv preprint arXiv:2103.0322 2021.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint wrXiv:1977.04999 2019.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. In ICML Workshop Graph Representation Learning and Beyond, 2020.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of The Web Conference 2021, WWW '21, 2021.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):i10--1198, 2017.
13

---

Under review as a conference paper at ICLR 2022
A PROOF OF THEOREM
Proof. We first derive the relationship between the supervised objective of latent graph prediction
E [A X) - FIl and the self seff-superviee reconstruction loss E IIfA, X l in the following
equations,
E (I X 2 = E (I(( X) - F) - (X F)1
(14)
-)( FII |X FI 2 X) X -
(15)
where (:.-) denotes the inner product along all dimensions f0. d 1}. The expectation
E X] || in the above equation is not relevant to the neural network f. It hence can be considered
constant during the optimization of f. To derive upper bound to E f X F only need derive an upper bound of its equivalent E [I X) -|| 2E (A, x F 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, F.X X F). To do so, we apply the definition of latent graph ||X|A, F F and rewrite the inner product into the following form.
E(f(A,X) - F, - F) = EAFEX
Σ E(((A.)) F) F
(16)
EA. B[(G(A, BX(X; -.),F,)AA...
E(f((A,)) - F| F.A.FF)
(17)
EA. (Cov(/(AA - X, - F)A
(18)
Σ EAF (C X,A,F)))
(19)
where i sums over all dimensions {0, ... dvl - 11] f. and X, denotes the i-th element of the flattened matrices. Note that we employ E|X F|A, 0 let Equation (17) hold, according
to the definition of latent graphs. Letting be a uniformly sampled subset of all node indices {O..... [V] 1}, the right hand side of the above equation satisfies
V JJ
RHS = ES
EAAF (Cov(Ja+*((A X {,
(20)
K=
where fja+* E R and Xjd+& E R denote the (jd + k))thh element of corresponding matrices, i.e.. the ke-th element of the node Vy, whereas X, IR J|xd denotes the feature matrix of nodes in Vy. Given the bounded variance Var(X)) I 0², Vi, we bound the above term as
V
RHS E,
Σ
EAF Cor(FsaHa(A,x)) fjat X X (.
(21)
JEJ,K
V
1/2
E
Σ
EA.
( - (x) Var Var(XJutt)
(22)
JEJ.
1/2
SIVIES
Σ
WAF Var(faa -AstA(A,Axx)),)... o2]
(23)
[J]
jEJ.k
1)
1/2
So|ViE>
Σ EA,F
E [[UAAA(A,,) (A, [A
(24)
[J]
JEJ.K
1/2
Σ
E. [E (A,)(A,
(25)
[J]]
jEJ.K

---

Under review as a conference paper at ICLR 2022
1/2
= [
(26)
Above inequalities and equations are derived based on the fact that f)(A, x=) does not correlate to X jd+tk as j & Je for Equation (21), the Cauchy-Schwarz inequality for Inequality (22), and (EE))² < EX for Inequality (23). We complete the proof of Theorem by combining Equation (15)
and Inequality (26),
E [II
- F|| + IX - F = EI - x + +( - F F) (27)
E (A, =,(A1x,)11+) 1/2
S -
(28)
B PROOF OF COROLLARY AND
Proof. We first prove Corollary Consider an &-Lipschitz continuous prediction head with respect to 12-ormm consists of fully connected layers. We have
(A, - = - 2H - H, H
(29)
We therefore have the following inequality
(llff(A.)) f) E
e HH, H3l
(30)
We apply the above incquality to Theorem and obtain the following inequality
X(I F + ||x
]]]]] ]
1/2
s Ef(A, XII 12
(
E (f((A
xxx)1
(31)
1
ea [|H H111 1)
1/2
SE]S(A)) XII VE0
(32)
1/2
=E [((A X VIE
E H -H31
(33)
which completes the proof of Corollay 1. Similarly, for Corollay 2, we have
[| X) (A x = | >
(34)
Given an f,-Biilpsshhizz continuous readout function R, the following inequalities hold,
H. - H'لl2 < (R(H)) R(H)) S4 [ H'll2
(35)
ef
We therefore have
E [[ - 2 + | - =
$ {E]f(A, X)= - x +2 V EEE E | H111/1111 1/2
(36)
1/2
{EI X) X11 VIEE,E
E ()(((H, -R(EE)))//111
(37)
[|| - z'112 (1//111)) 1/2
E EJ X)-
x +20 V
(38)
which completes the proof of Corollay 2.
2

---

Under review as a conference paper at ICLR 2022
C PSEUDO-CODE FOR COMPUTING LAGRAPH OBJECTIVES
The pseudo-code for computing LaGraph objectives for node-level representations and graph-level representations are shown in Algorithms and
Algorithm LaGraph objective: node-level
Inputs: A mini-batch of graphs {GI,-.. Gr.. the encoder E, the prediction head D, and the hyper-parameter a. for i in 1,.... .N do Generate random Jj E {0, I]IIIx1 M E R Vilxa
G2 (A,, X;)
X1 - 1. O X +1, OM
Randomly mask nodes Compute node representations
H. E(A; X,)
H: + A,, Xi.::)
Xrec + D H.)
Reconstructed node attributes
(ree, f Xreai -xill=/10
Lin + |1, H: 11, @ H'l?
end for
,GN]) E, Creei + ao EiEi lineas/ E, (J/)
Algorithm 2 LaGraph objective: graph-level
Inputs: mini-batch of graphs (G),... ,Gn), the encoder the prediction head D, the readout function R, and the hyper-parameter a. for i in 1,...,... N do
G. (A,, X,,
Generate random J. E f0, 1IllXx1 M E IR Vixd
Xt,: & 1,y @ X 11, @ M H. E(A,, X,)
Randomly mask nodes Compute node embeddings
H + E(A,, Xi.;;)
2; + R(H:)
Readout graph representations
2 + R(H))
Xree + D(A;, H,)
Reconstructed node attributes
Crec, f- Xreci xil1 /IVI
Lin t 2 2/1
end for
LE,, D; (Gi.... ,Gn]) = 3/2 E, bree,t + al Ei lines// 12)///2
D DISCUSSION ON THE DIFFERENCES TO BGRL AND BARLOW-TWIN OBJECTIVES
In spite of the similarity in the objective of BGRL, Barlow-Twin the consistency regularization (Weil ct 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 Theorem and objective for node-level representations, in contrast the BGRL and Barlow-Twe Twins objectives where all nodes are computed. It is worth noting that the objective is an upper bound to the latent graph prediction only the invariance is computed on the masked nodes, according 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 contradicted effect, i.c., enforcing encoders to capture less information from contextual nodes, as lets the representation remain consistent when its neighbor nodes (who are masked) are changed. We believe the derivation and the intuition the proposed objective can provide guidance on how to adopt the consistent regularization into SSL studies.
3

---

Under review as a conference paper at ICLR 2022
E EXPERIMENT SETTINGS AND MODEL CONFIGURATIONS
Dataset Statistics. Statistics including number of graphs, averaged number of nodes, averaged number edges, and node attribute dimensions are summarized Table
Table 4: Summary and statistics of common graph datasets for self supervveee learning.
Datasets
Evaluation task
# graphs
Avg. nodes
Avg. edges
features
NCII
4110
29.87
32.30
37
PROTEINS
1178
39.06
72.82
3
DD
188
284.32
715.66
89
MUTAG
Graph-level
1113
17.93
19.79
7
COLLAB
classification
5000
74.49
2457.78
1
RDT-B
2000
429.63
497.75
1
RDT-M5K
4999
508.52
594.87
1
IMDB-B
1000
19.77
96.53
Amazon Computer
13,752
245,861
767
Transductive Node-level
Amazon Photos
7,650
119,081
745
Coauthor CS
81,894
81,894
6,806
classification
Coauthor Physies
1
247,962
247,962
8,415
PPI
Inductive
24
2,373
34,133
50
Flickr
Node-level classification
1
89,250
899,756
500
Reddit
232,965
11,606,919
602
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 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 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 evaluated on testing graphs. Second, Flickr graph, the training and testing nodes from the
and Reddit each consist of only During self-supervised training, all test nodes are masked-out. During evaluation, all training nodes masked-out, i.e., test nodes 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.
graph.
Experimental Details. We train graph-level datasets on single 11GB GeForce RTX 2080 Ti GPU, and train node-level datasets on single 56GB Nvidia RTX A6000 GPU. Our experiments are implemented with PyTorch 1.7.0 7.. and PyTorch Geometric 1.7.0. All neural networks employ batch normalization (loffe 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 3-layer GIN Xu et al. 2019) as the graph encoder E, and 2-layer MLP as the decoder D. Following GraphCL You et al. 2020), we use 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, 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
4

---

Under review as a conference paper at ICLR 2022
vector of the degree for each node as the node attributes that the node degrees 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 a' and threshold for max degrees are shown in 5 Note that we do not include carefully designed implementation mechanisms by BGRL, such as stop gradients, EMA, and batch normalization the last layer.
Models for Node-I Datasets. For node-level datasets, we employ 2-layer GCN (Kipf and Welling 2017) as the graph encoder &, and a linear layer or an MI.P as the decoder D. We use 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 a' of 2 as we observed that the model performance is not sensitive the selection of a' 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 (lyanov et al. 2018) of data distribution whereas the given graph data serves as the observed samples. And the posteriorí should be based combination of the priori (encoder output) and the observed data itself (Laine et al. 2019). Node representation is then taken by 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 (Shchur et al. 2018) for Coauthor and Amazon, (Zitnik and Leskovec 22077: Hamilton 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.
Table 5: Model configurations for graph-level datasets.
NCII
PROTEINS
DD
MUTAG
COLLAB
RDT-B
RDT-MSK
IMDB-B
Mask ratio
0.05
0.3
0.1
0.05
0.05
0.05
0.05
0.05
Noise SD
0.5
2
0.5
0.5
0.5
0.5
0.5
0.5
Weight scalar o'
10
1
10
10
10
10
10
10
Degree threshold
128
64
Learning rate
10-5
10-5
10-5
10
10-4
10
10
10-4
Table 6: Model configurartions for node-level datasets.
Compurrss
Am. Ahotos
CoautherCS
CoauthorPhy
PPI
Flickr
Reddit
Mask ratio
0.05
0.05
0.05
0.05
0.05
0.01
Noise SD)
0.5
0.5
0.005
0.5
0,5
0.5
0.5
Decoder layers
1
1
2
2
2
2
Learning rate
10-4
10-5
10-3
10
10-3
10-4
10
Weight decay
0
10-4
0
0
10-5
0
0
LogReg epochs
400
400
400
300
200
200
500
LogReg WD
10-3
10-3
10-3
10-3
10-3
10-3
F EXPERIMENTAL RESULTS UNDER SEMI-SUPERVISED SETTING
For graph-level datasets, we perform emii-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
5

---

Under review as a conference paper at ICLR 2022
from {5, 10, 15, 20). The results shown in Table 7 and Table indicate that our proposed LaGraph
framework is also effective for semi- -umi-iuieee learning with different GNN backbones.
Table 7: GIN results for Semi-supervised learning.
NCTI PROTEINS
DD
MUTAG
COLLAB
RDT-B
RDT-MSK
IMDB-B
Rand. Init. + 10% supervised 76.67
75.29
76.66
86.67
77.54
85.45
56.03
72.70
LaGraph + 10% supervised
80.19
76.10
77.93
91.40
78.04
89.65
56.43
74.30
Table 8: GCN results for Semi-supervised learning.
NCTI PROTEINS
DD
MUTAG
COLLAB RDT-B RDT-M5K
IMDB-B
Rand. Init. + 10% supervised 75.47
74.48
77.33
84.59
79.02
85.30
53.67
72.90
LaGraph 10% supervised 78.18
76.28
78.86
85.12
80.12
90.35
55.33
75.10
G ADDITIONAL ABLATION STUDIES.
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 Theorem I, who applies invariance regularization on the reconstructed node features. In addition, node attributes in many graph-level datasets 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 fA, X) and (A, X Note that the multinomial versions longer strictly upper bounds of supervised latent graph prediction. In Table TO we show the results obtained under four objectives above, namely, compute invariance on on-embedding (MSE-Embed), on-output (MSE-Outpute and their corresponding multinomial versions (CE- Embed and CE-Output), respectively. Results indicate that there no sigmificant 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.
Table 9: Effect of training with different objectives on graph-level datasets.
NCI1
PROTEINS
DD
MUTAG
COLLAB
RDT-B
RDT-M5K
IMDB-B
MSE-Embed 79.9+0.5
75.2+0.3
78.120.3
90.2+1.3
77.6+0.1
90.4#0.9
56.420.2
73.720.7
MSE-Output 79.9+0.7
75.0#0.4
78.1
89.2+2.1
77.7+0.1
89.8=0.9
56.0:0.4
73.4+0.6
CE-Embed 79.920.5
75.240.3
78.1+0.4
90.1+1.0
77.6+0.2
90.5+1.3
56.310.4
73.720.7
CE-Output 79.920.7
75.2+0.4
78.120.4
89,322.7
77.6+0.1
89.4+1.8
55.720.2
73.540.5
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 TO 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 gap between SSL and supervised performance. Meanwhile, the performance of LaGraph is on par with the performance supervised learning and the SOTA method BGRL on datasets that are less challenging.

---

Under review as a conference paper at ICLR 2022
Table 10: Effect of performing concatenation with node features.
Dataset
Am. Comp.
Am. Pht.
Co. CS
Co. Phy
PPI
Flickr
Reddit
With concat
08.02..3
93.520.4
93.340.2
95,820.1
74.620.0
51.340.1
95.240.0 94.840.0
Wo concat
88.8
92.7+0.4
92.640.2
95.320.1
75.2+0.0
51.620.1
H ADDITIONAL DISCUSSION ON POTENTIAL LIMITATIONS AND FUTURE DIRECTIONS
In this section, discuss several limitations of the proposed method and their solutions related future directions.
Non-significant improvement compared to BGRL on transductive tasks. From the experimen- tal 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 comes to inductive tasks, where there is still 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 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 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 the node degrees, i.e., the degree of a node is considered as & if it exceeds k. The current solution can capture topological information of graph at some degree. However, there can be better solutions capturing full topological information 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 derive similar objectives (e.g.. upper bound link prediction objective) following a similar idea.
Scaling-up up issue. The scaling-up of graph neural networks becomes an emerging topic. Many existing sulf--sue 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 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 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 fully demonstrate the effectiveness of self-supe learning methods.
7


Reviews:
[{"review_id": "UPr8L25LIP0", "reviewer": "Reviewer_Fi7g", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "+Strengths\n  1. Good overall presentation of the technical content\n  2. New contributions of tackling the challenges of conditional distribution $p(G|{G_I})$ instead of simply applying the noisy data reconstruction\n  3. Sound theoretical analysis\n  4. Comprehensive comparison with related work based on various techniques, e.g., denoising autoencoders, information bottleneck principle, and local-global mutual information maximization for contrastive learning\n  \n+Weaknesses\n  1. Some problem definitions, preliminaries, and details regarding the proposed method are not very clear (see Detailed Comments 1)\n  2. Some details regarding the experiments are not given (see Detailed Comments 2)\n  3. No discussion about the inherent limitations of the proposed method and possible solutions (see Detailed Comments 3)\n\n+Details Comments\n1. Some problem definitions and technical details regarding the proposed method are unclear and need to be further clarified.\n\n  For the problem definitions in Section 2.1, the authors claim that they 'consider an undirected graph'. It seems the proposed method can only derive the representations of one single graph. However, in Section 2.4, the authors claim that they consider a mini-bath of $N$ graphs, which is inconsistent with that in Section 2.1. In the experiments, the author applied the proposed method to multiple graphs for graph classification, which is also inconsistent with that in Section 2.1 (i.e., learning representation of one single graph). It is better to formulate the graph representation learning based on a set of graphs (but not a single graph) in Section 2.1.\n\n  It is also recommended to give formal definitions regarding transductive and inductive graph representation learning. Especially for the inductive graph embedding, it is unclear that the authors consider inductive node-level task for new unseen nodes of a graph or across multiple graphs (w.r.t. what they conduced in the experiments). The authors should also  verify some constraints of inductive graph embedding, e.g., different graphs can have different node sets, all the graphs must have the same feature dimensionality, etc.\n\n  In the first paragraph of Section 2.2, the authors claim that the latent data ${\\bf{x}}_{I}$ determines the semantic of the observed data ${\\bf{x}}$. What does the 'semantic' of observed data (e.g., in terms of graphs) mean? It is better to give some simple examples to explain the 'semantic' of an observed graph.\n\n  In the 2nd paragraph in Section 2.2, the authors claim that 'the pair of graphs have matched structure and feature dimensions'. What does 'matched structure' mean? From my perspective, one may have ambiguous understandings. It may indicate that the two graphs (i.e., an observed graph and its latent graph) have the same node set (but with different topology described by different edge sets). It can also indicate that the two graphs have the same node set and edge set. Until I read Theorem 1 with the notations $G=({\\bf{A}}, {\\bf{X}})$ and $G_I=({\\bf{A}}, {\\bf{F}})$, I know that it indicate the latter case. It is better to give the formal definitions of the observed graph and its latent graph at the beginning of Section 2.2.\n\n  In Corollary 1 and Corollary 2, ${\\bf{H}}'$ denotes the embedding of 'masked graph', but what is a 'masked graph'? Is it with the same definition as 'latent graph'? It seems there is no definition of 'masked graph' before Corollary 1 and Corollary 2.\n\n  In Section 2.4, what is the definition of ${\\bf{X}}_{(i,J_i^c)}$? Is it a single masked variant of an observed graph? If so, the proposed method only generated one masked variant for each graph. It is not clear how many mask variants are generated for each single observed graph $G_i$. In fact, some details of the proposed method can be clearly presented using the pseudo-code (even in the appendix) but there is no pseudo-code to describe the overall training and inference procedures of the proposed method.\n\n  From my perspective, Fig. 1 does not accurately present the basic ideas of the proposed method. In this paper, the authors consider the representation learning of attributed graph, where each node is associated with a feature vector. However, node feature vectors are not presented in Fig. 1. For the masked graph in the 'Input graphs' subfigure, some of the nodes are crossed. What are the crossed nodes? Are they the nodes selected to be masked? The masking operation is conducted on node features but not both on topology and attributes. The current presentation of the masked graph implies that one needs to first remove the crossed nodes from the original graph (i.e., the masked graph is then with the node set $J^c$), which is inconsistent with the proposed method. Moreover, in the 'Representation' subfigures of Fig. 1, there is the topology of two graphs, which are not the derived representations. In fact, the representations are low-dimensional vectors but not graph topology as presented in the 'Representation' subfigures. Why the graph-level representations of the observed graph and latent graph are denoted as ${\\bf{Z}}$ and ${\\bf{Z}}'$ in bold capital letters in Fig. 1? Usually, bold capital letters are used to describe matrices. From my perspective, they should be presented in bold lowercase letters, i.e., ${\\bf{z}}$ and ${\\bf{z}}'$ as in Eq. (6), which indicate that they are vectors (but not matrices).\n\n  In Section 3.1, the author claim that the 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'. I am curious about how the information of the masked nodes is captured by the proposed method and why the derived representations can be as good as ones from supervised learning? It is better to give some simple examples to help the readers better understand this point.\n\n2. Some details regarding the experiments are missing. Some experiment settings also need further clarification.\n\n  There are no statistic details regarding the datasets used in the experiments, e.g., number of graphs, number of nodes, number of edges, dimensionality of node attributes, etc. Details regarding the evaluation protocols for different tasks are also not given. Although the authors claim that they follow the experiment settings of prior work, some important content (e.g., experiment settings) of a paper should be self-contained and do not rely on other papers. Hence, it is recommended to briefly introduce the statistic details and evaluation protocols even in the appendix.\n\n  As I mentioned in the Detailed Comments 1, what does the inductive node-level classification indicate? Does it refer to the (i) classification for new unseen nodes in a graph, (ii) classification across multiple graphs, or (iii) both of them? It is better to give a clear definition of this task.\n  \n  In the graph classification task, how node2vec and sub2vec are used to derive the graph embedding? As I know node2vec and sub2vec can only derive the vector representations for each node and subgraph, respectively. How did the authors convert the node and subgraph embeddings to the graph embedding? How did the subgraphs sampled for sub2evc? The settings of other baselines should also be briefly introduced.\n  \n  Why did the authors use node2vec in graph classification but use DeepWalk in transductive node classification? As I know, node2vec and DeepWalk are two node embedding baselines with similar motivations. Why not use both of them in graph classification and transductive node classification?\n  \n  In Table 2, why did the authors use different evaluation metrics for transductive and inductive node classification (i.e., accuracy and Micro-average F1 score)? \n\n  In Table 1 and Table 2, why some of the results of GL (e.g., on NCI1, PROTEINS, and DD), WL (e.g., on DD and COLLAB), DGK, Node2Vec, Sub2Vec, Graph2Vec, BGRL-GCN, and BGRL-GAT are not given?\n  \n  For the empirical analysis regarding the batch size and number of sampled nodes in Fig. 2 and Table 3, besides the memory usage, what is the corresponding training time w.r.t. each setting? \n\n3. The limitations of the proposed method and possible solutions are not fully discussed in Section 5. A good paper should also comprehensively discuss its limitations in addition to its contributions.\n\n  From my perspective, the proposed method is designed for attributed graphs and relies heavily on the reconstruction of node features. How can the proposed method deal with the representation learning on graphs without any available node attributes? By reading the appendix, I know that the authors tried to apply the one-hot vector of degree for each node as the node attributes. It is not an elegant way for the inductive representation learning across multiple graphs, where the model can only be trained on some of the graphs (i.e., the training set) and be generalized to the other unseen graphs (i.e., the test set). During the training, only the information of training set is given, which indicates that the node degree of the test set is unknown. When the node degrees in the test set have a wide value range but those in the training set only have a small value range, it is possible that most of the node attributes in a test graph are zero vectors. Moreover, what about the graph embedding on a set of regularized graphs without node attributes, where all the nodes have the same degree value? In this case, all the node feature vectors are the same.\n  \n  In addition to reconstructing the node attributes, why not consider another direction of reconstructing the topology? Namely, we can derive an observed graph and its latent graph with different set of edges (but with the same node attributes). The authors can give some discussions regarding this direction.\n  \n  To scale a GNN to large graphs (in terms of the number of nodes) is a hot topic in recent research. The authors also mention that the proposed method can be applied to large graphs. However, as I can check from the descriptions of experiments, the largest graph (i.e., Reddit) used in the experiments only has 232,965 nodes, which cannot be considered as a very large graph. For the reported evaluation results in Table 2, it seems that the authors did not apply any mini-batch subgraph sampling strategies. For large graphs (e.g., with more than one million nodes), most of the GNN structures need certain mini-batch subgraph sampling strategies. How the sampling strategies can be applied to the proposed method considering both the effects of topology and attributes? The authors can give some further discussions regarding this point.\n  \n  Most of the SSL-based graph embedding methods are based on unsupervised training loss and evaluated via supervised downstream tasks (e.g., node and graph classification). I am curious about their ability to deal with some unsupervised downstream tasks (e.g., disjoint and overlapping community detection).", "summary_of_the_paper": "  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.", "summary_of_the_review": "This paper has good overall presentation of the technical content and sound theoretical analysis regarding the proposed method as well as related work. From my perspective, the proposed method is novel. However, there are some details regarding the problem definitions and experiment settings that need to be further verified.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KLFEa6vdFHz", "reviewer": "Reviewer_t1HQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n* Simple architecture, with good results (Table 1)\n* Theory is provided to justify their method and approach.\n* The authors do a good job at explaining the conceptual differences between LaGraph and prior work.\n* Comparisons with other SOTA methods on a number of graph-level and node-level benchmarks.\n\nWeaknesses:\n* It appears that the BGRL accuracies shown in Table 2 were reported in the original work and were not reproduced by the authors. The evaluation protocol used for LaGraph is different from the one used in BGRL: in BGRL, logistic regression is performed over the last layer of the encoder whereas in LaGraph (Appendix C), it is performed over the concatenation of the original features and the embeddings of the last layer. This is especially relevant for the transductive tasks, where the differences in accuracy are within 0.1% (which lies within the confidence interval). The authors should compare their methods using the same evaluation protocol.\n* In table 2, LaGraph is only better than BGRL on one dataset (PPI). It would be interesting to see how this method provides additional benefits beyond performance since the methods give similar performance.\n* The ablation studies are lacking as well. Given the similarity between LaGraph and BGRL, the ablations and other comparisons should include BGRL to show the performance gains. \n* The assumption that each node embedding is sampled independently from the rest is not fully justified. The theory lacks any discussion of properties of the graph or its connectivity and thus is limited in its impact.\n* While the authors describe the method as a new approach for latent graph prediction, the method is very similar to other predictive methods, especially BGRL and Graph BarlowTwins: the node representations of two views (view 1 = original graph, view 2 = graph with node dropout) are compared. The only difference is in the way the collapse is avoided is through the reconstruction term. Thus the novelty of the approach is limited in this respect. \n", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper introduces a new reconstruction-based loss for avoiding representation collapse and theory to justify their choice. In experiments on both graph- and node-level tasks, they show competitive performance with other SOTA methods. While the goal of providing some insights into SSL-based approaches is laudable, their theory is limited in that it doesn't provide any unique information that is graph specific and thus fails to provide insights into graph representation learning. When compared with similar SOTA methods, there is limited gain in performance; thus, it would be useful to evaluate other aspects of the algorithm and make stronger connections to the theory.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Fts9VfABN0D", "reviewer": "Reviewer_X3u8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "However, the model assumption, that the conditional distribution of the observed graph is centered at the latent graph, is too strong, which is not natural at all. Meanwhile, it seems the introduced objective is just an upper bound, whose tightness should be further discussed. \n\nMeanwhile, as claimed in Section 3, the introduced objective is highly correlated with the existing method, which is good for us the understand the method. However, the difference or superiority of the objective over the existing InforMax should also be highlighted to analyze the method deeper. \n\nAlthough the motivation of eliminating the latent feature matrix F is impressive, the method adopted in this paper highly depends on the approximation of the upper bound, i.e., the number of subgraph N and hyperparameter alpha. This should be declared in the paper and the scenario that the proposed method is not suitable can also be discussed. \n\nThe notation in this paper is not professional, especially the use of subscript. $1_J, X_J, f_J, E_J, H_J; l_n, l_g, l_r$ It hinders me from fully understanding the meaning of some terms. \n\nsome minor concerns:\n\nHow is Eq.12 derived? \n\nwhat does \"Supervised\" mean in Table 2?", "summary_of_the_paper": "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. ", "summary_of_the_review": "The idea of the proposed method is novel and interesting to me, but the assumption of latent graph about the generation process of graph is a bit strong. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "78lf5wePyJ", "reviewer": "Reviewer_e11u", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n--\n\n* The paper studied self-supervised learning for GNNs that is less explored than other domains.\n* The authors provide theoretical analyses of the proposed method. The relation between the proposed method and previous work is discussed with theoretical analysis.\n* The memory consumption is much less than a strong baseline GraphCL and works well (e.g., relatively small degradation) with a relatively small mini-batch size.\n \nWeaknesses\n--\n* The proposed method and losses are a simple variation of existing methods. Although the authors present their works as latent graph prediction, it is indeed a simple consistency regularization with noise on randomly sampled nodes. Since the method is proposed as an unsupervised method, the authors impose the consistency regularization on hidden representations, which are the output of encoder (GNNs) rather than predictions/softmax values. \n* Although the relation between latent graph prediction and consistency regularization is interesting, the relation and analyses barely provide intuitions to improve the consistency loss.\n* It is not clear whether the performance gain is statistically significant. \n\nQuestions\n--\n* Do you use stop gradient along the branch for original graphs?\n* Is the proposed method applicable to link prediction?\n* Why do you focus on only masked nodes for the consistency of hidden representations in (5) and (6)?\n* Is the substitution of node features with random noise for randomly sampled nodes more effective than dropNode, which are used in previous work such as GRAND [1]?\n\n[1] Feng, Wenzheng, et al. \"Graph Random Neural Network for Semi-Supervised Learning on Graphs.\" NeurIPS, 2020.", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper studies a self-supervised learning framework to perform representation learning for graph neural networks. The authors provide theoretical discussion about latent graph prediction and related domains. Even though many theoretical analyses and derivations are provided, the resulting algorithm is too close to existing methods, and the latent graph prediction perspective makes it more difficult to understand the proposed method. It has strengths with interesting theoretical analyses, but the impact and the novelty of the resulting algorithms are limited.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies self-supervised learning for graph neural networks by proposing a framework called LaGraph. Both theoretical analysis and experimental evaluation are provided in the paper.

We acknowledge the merits of this paper, which include studying a relatively less explored topic, providing theoretical analysis and comparison with other methods, and requiring less memory than a strong baseline.

On the other hand, there are also outstanding concerns (even after the discussions) regarding the novelty and significance of the proposed method (despite the claims of the authors during the discussions), whether the performance improvement over strong baselines is significant across different datasets, and missing a more comprehensive ablation study (beyond the preliminary results provided during the discussion period), among others.

In its current form, this is certainly a borderline paper for a top conference such as ICLR. It would be a better paper if the outstanding concerns could also be addressed before publication.
Decision: Reject