Year: 2020

Abstract:
This paper focuses on unsupervised/self-supervised whole-graph representation learning, which is critical in many tasks including drug and material discovery. Current methods can effectively model the local structure between different graph instances, but they fail to discover the global semantic structure of the entire dataset. In this work, we propose a unified framework called Local-instance and Global-semantic Learning (GraphLoG) for self-supervised whole-graph representation learning. Specifically, besides preserving the local instance-level structure, GraphLoG leverages a nonparametric strategy to learn hierarchical prototypes of the data. These prototypes capture the semantic clusters in the latent space, and the number of prototypes can automatically adapt to different feature distributions. We evaluate GraphLoG by pre-training it on massive unlabeled graphs followed by fine-tuning on downstream tasks. Extensive experiments on both chemical and biological benchmark datasets demonstrate the effectiveness of our approach.

heading: 1 INTRODUCTION
text: Learning informative representations of whole graphs is a fundamental problem in a variety of domains and tasks, such as molecule properties prediction in drug and material discovery (Gilmer et al., 2017; Wu et al., 2018), protein function forecast in biological networks (Alvarez & Yan, 2012; Jiang et al., 2017), and predicting the properties of circuits in circuit design (Zhang et al., 2019). Recently, Graph Neural Networks (GNNs) have attracted a surge of interest and showed the effectiveness in learning graph representations. These methods are usually trained in a supervised fashion, which requires a large number of labeled data. Nevertheless, in many scientific domains, labeled data are very limited and expensive to obtain. Therefore, it is becoming increasingly important to learn the representations of graphs in an unsupervised or self-supervised fashion.
Self-supervised learning has recently achieved profound success for both natural language processing, e.g. GPT (Radford et al., 2018) and BERT (Devlin et al., 2019), and image understanding, e.g. MoCo (He et al., 2019) and SimCLR (Chen et al., 2020). However, how to effectively learn the representations of graphs in a self-supervised way is still an open problem. Intuitively, a desirable graph representation should be able to preserve the local-instance structure, so that similar graphs are embedded close to each other and dissimilar ones stay far apart. In addition, the representations of a set of graphs should also reflect the global-semantic structure of the data, so that the graphs with similar semantic properties are compactly embedded, which benefits various downstream tasks, e.g. graph classification or regression. Such structure can be sufficiently captured by semantic clusters (Caron et al., 2018; Ji et al., 2019), especially in a hierarchical fashion (Li et al., 2020).
There are some recent works that learn graph representation in a self-supervised manner, such as local-global mutual information maximization (Velickovic et al., 2019; Sun et al., 2019), structuralsimilarity/context prediction (Navarin et al., 2018; Hu et al., 2019; You et al., 2020) and contrastive multi-view learning (Hassani & Ahmadi, 2020). However, all these methods are capable of modeling only the local structure between different graph instances but fail to discover the global-semantic structure. To address this shortcoming, we are seeking for an approach that is sufficient to model both the local and global structure of a given set of graphs.
To attain this goal, we propose a Local-instance and Global-semantic Learning (GraphLoG) framework for self-supervised graph representation learning. In specific, for preserving the local similarity
between various graph instances, we first align the embeddings of correlated graphs/subgraphs1 by maximizing their mutual information. In this locally smooth embedding space, we further represent the distribution of different graph embeddings with hierarchical prototypes2 whose number is adaptively determined by the data in a nonparametric fashion. During training, these prototypes guide each graph to map to the semantically-similar feature cluster, and, simultaneously, the prototypes are maintained by online-updated graph embeddings. In this process, the global-semantic structure of the data is gradually discovered and refined. The whole model is pre-trained with a large number of unlabeled graphs, and then fine-tuned and evaluated on some downstream tasks.
We summarize our contributions as follows:
• We contribute a unified framework called Local-instance and Global-semantic Learning (GraphLoG) for self-supervised graph representation learning, which is able to model the structure of a set of graphs both locally and globally.
• We novelly propose to infer the global-semantic structure underlying the unlabeled graphs by learning hierarchical prototypes via a nonparametric strategy.
• We empirically verify our framework’s superior performance on different GNN architectures through pre-training on a large-scale unlabeled dataset and fine-tuning on benchmark tasks in both the chemistry and biology domains.

heading: 2 PROBLEM DEFINITION AND PRELIMINARIES

heading: 2.1 PROBLEM DEFINITION
text: An ideal representation should preserve the local structure among the data instances. More specifically, we define it as follows:
Definition 1 (Local-instance Structure). The local-instance structure refers to the local pairwise similarity between different instances (Roweis & Saul, 2000; Belkin & Niyogi, 2002). To preserve the local-instance structure of graph-structured data, a pair of similar graphs/subgraphs, G and G′, are expected to be mapped to the nearby positions of embedding space, as illustrated in Fig. 1(a), while the dissimilar pairs should be mapped to far apart.
The pursuit of local-instance structure is usually insufficient to capture the semantics underlying the entire dataset. It is therefore important to discover the global-semantic structure of the data, which is concretely defined as follows:
Definition 2 (Global-semantic Structure). A real-world dataset is usually distributed as different semantic clusters (Furnas et al., 2017; Ji et al., 2019). Therefore, we define the global-semantic structure of a dataset as the distribution of its semantic clusters, and each cluster is represented by a prototype (i.e. a representative cluster embedding). Since the semantics of a set of graphs can be structured in a hierarchical way (Ashburner et al., 2000; Chen et al., 2012), we represent the whole dataset with hierarchical prototypes. A detailed example can be seen in Fig. 1(b).
1In our method, we obtain correlated graphs/subgraphs via minor modification on node/edge attributes. 2Hierarchical prototypes are representative cluster embeddings organized in a hierarchical way.
Problem Definition. For self-supervised graph representation learning, a set of unlabeled graphs G = {G1,G2, · · · ,GM} are given, and we aim to learn a low-dimensional vector hGi ∈ Rδ for each graph Gi ∈ G under the guidance of the data itself. In specific, we expect the derived graph embeddings H ∈ RM×δ follow both the local-instance and global-semantic structure.

heading: 2.2 PRELIMINARIES
text: Graph Neural Networks (GNNs). Given a graph G = (V, E) with node attributes XV = {Xv|v ∈ V} and edge attributes XE = {Xuv|(u, v) ∈ E}, a GNN aims to learn an embedding vector hv for each node v ∈ V and also a vector hG for the entire graph G. For an L-layer GNN, a neighborhood aggregation scheme is performed to capture the L-hop information surrounding each node. The l-th layer of a GNN can be formalized as follows:
h(l)v = COMBINE (l) ( h(l−1)v ,AGGREGATE (l) ({( h(l−1)v , h (l−1) u , Xuv ) : u ∈ N (v) })) , (1)
where N (v) is the neighborhood set of v, h(l)v denotes the representation of node v at the l-th layer, and h(0)v is initialized as the node attribute Xv . Since hv summarizes the information of a patch centered around node v, we will refer to hv as patch embedding to underscore this point. The entire graph’s embedding can be derived by a permutation-invariant readout function:
hG = READOUT ({ hv|v ∈ V }) . (2)
Mutual Information Estimation. Mutual information (MI) can measure both the linear and nonlinear dependency between two random variables. Some recent works (Belghazi et al., 2018; Hjelm et al., 2019) employed neural networks to estimate the lower bound of MI. Among which, InfoNCE loss (van den Oord et al., 2018) has been introduced to maximize a lower bound of MI by minimizing itself, and we also adopt it in this work for its simplicity and effectiveness. In practice, given a query q, InfoNCE loss is optimized to score the positive sample z+ higher than a set of distractors {zi}Ki=1:
LNCE ( q, z+, {zi}Ki=1 ) = − log
exp ( T (q, z+) ) exp ( T (q, z+) ) + ∑K i=1 exp ( T (q, zi)
) , (3) where T (·, ·) is a parameterized discriminator function which maps two representation vectors to a scalar value, whose architecture is detailed in Sec. 6.1.
Rival Penalized Competitive Learning (RPCL). The RPCL method (Xu et al., 1993) is a variant of classical competitive learning approaches, e.g. K-means clustering. Concretely, given a sample for update, RPCL-based clustering not only pulls the winning cluster center (i.e. the closest one) towards the sample, but also pushes the rival cluster center (i.e. the second closest one) away from the sample. We adopt this clustering algorithm for its strong capability of discovering feature clusters without specifying the number of clusters beforehand (i.e. in a nonparametric fashion), which is critical in the self-supervised learning scenarios where the number of semantic categories is not given.

heading: 3 LOCAL-INSTANCE AND GLOBAL-SEMANTIC LEARNING

heading: 3.1 LEARNING LOCAL-INSTANCE STRUCTURE OF GRAPH REPRESENTATIONS
text: We first define the correlated graphs that are expected to be embedded close to each other in the embedding space. Since the graphs from a dataset lie in a highly discrete space, it is hard to seek out the correlated counterpart of each graph from the dataset. To tackle this limitation, we propose to construct pairs of correlated graphs via the attribute masking strategy (Hu et al., 2019) which randomly masks a part of node/edge attributes in a graph (theoretical analysis is stated in Sec. A).
Through applying this technique to a randomly sampled mini-batch BG = {Gj = (Vj , Ej)}Nj=1 with N graphs, the correlated counterpart of each graph can be obtained, which forms another minibatch B′G = {G′j = (V ′j , E ′j)}Nj=1 (Gj and G′j are deemed as a pair of correlated graphs). Taking both mini-batches as input, the corresponding patch and graph embeddings are derived as follows:
hVj = {hv|v ∈ Vj} = GNN(XVj , XEj ), hV′j = {hv|v ∈ V ′ j} = GNN(XV′j , XE′j ), (4)
hGj = READOUT(hVj ), hG′j = READOUT(hV′j ), (5)
where hVj (hV′j ) is the set of patch embeddings for graph Gj (G ′ j), and hGj (hG′j ) denotes the embedding of entire graph. With these ingredients, we design the learning objective for local-instance structure based on two desiderata: (1) similar subgraphs (i.e. patches) have similar feature representations; (2) graphs with a set of similar patches are embedded close to each other. To attain these goals, we propose to maximize the mutual information (i.e. minimize the InfoNCE loss) between correlated patches/graphs, which derives two constraints for the local-instance structure:
Lpatch = 1∑N
j=1 |V ′j | N∑ j=1 ∑ v′∈V′j ∑ v∈Vj 1v↔v′ · LNCE ( hv′ , hv, {hṽ|ṽ ∈ Vj , ṽ 6= v} ) , (6)
Lgraph = 1
N N∑ j=1 LNCE ( hG′j , hGj , {hGk |1 6 k 6 N, k 6= j} ) , (7)
Llocal = Lpatch + Lgraph, (8) where LNCE(·, ·, ·) is the InfoNCE loss function defined in Eq. 3, and 1v↔v′ denotes the indicator function judging whether v and v′ are the corresponding nodes in a pair of correlated graphs. Note that, masking node/edge attributes doesn’t change the topology of a graph, which makes it easy to determine these corresponding nodes in our method.

heading: 3.2 LEARNING GLOBAL-SEMANTIC STRUCTURE OF GRAPH REPRESENTATIONS
text: It is worth noticing that the graphs in a dataset may possess hierarchical semantic information. For example, drugs (i.e. molecular graphs) are represented by a five-level hierarchy in the Anatomical Therapeutic Chemical (ATC) classification system (Chen et al., 2012). Moreover, the biological functions of proteins (i.e. graphs of amino acid residues) can be organized in a hierarchical structure (e.g. Gene Ontology (Ashburner et al., 2000) and FunCat (Ruepp et al., 2004) protein functionaldefinition schemes).
Motivated by this fact, we propose the notion of hierarchical prototypes to describe the distributions of graph embeddings. These prototypes are structured as a set of trees (Fig. 1(b)), in which each node denotes a prototype (i.e. a representative embedding of feature cluster) and corresponds to an unique parent node unless it is at the top layer. Formally, the hierarchical prototypes can be represented as {cli} Ml i=1 (l = 1, 2, · · · , Lp), where Lp denotes the depth of hierarchical prototypes, and Ml is the number of prototypes at the l-th layer. Except for the leaf nodes, each prototype possesses a set of child nodes, denoted as C(cli) (1 6 i 6 Ml, l = 1, 2, · · · , Lp − 1). During training, the derivation of these variables can be divided into two stages, i.e. initialization and maintenance.
Initialization of hierarchical prototypes. In order to establish appropriate priors of graph embeddings, we first pre-train the GNN by minimizing Llocal for one epoch and utilize it to extract the embeddings of all graphs in the training set, denoted as {hGi} ND i=1 (ND is the size of training set). These embeddings are used to initialize the bottom layer prototypes (i.e. {cLpi } MLp i=1 ) via the RPCL-based clustering algorithm (Sec. 2.2):
{cLpi } MLp i=1 = RPCL ( {hGi} ND i=1 ) , (9)
where RPCL(·) outputs the cluster centers that are assigned with at least one sample. After that, the prototypes of upper layers are initialized by iteratively applying RPCL-based clustering to the prototypes of the layer below:
{cli} Ml i=1 = RPCL ( {cl+1i } Ml+1 i=1 ) , l = 1, 2, · · · , Lp − 1. (10)
It is noteworthy that, in the initialization scheme, the number of prototypes is automatically adapted to the distribution of graph embeddings. As a result, this scheme is nonparametric and can adapt to different datasets without the prior knowledges about them.
Maintenance of hierarchical prototypes. In the training process, since the embedding of each graph is dynamically changing, we propose a strategy to maintain hierarchical prototypes with online updated graph embeddings. Concretely, under the guidance of a similarity measurement (e.g. cosine similarity in our implementation), the graph embeddings extracted from mini-batch BG are
Algorithm 1 Training procedure of Local-instance and Global-semantic Learning (GraphLoG).
Input: Training set D = {Gj}NDj=1, the number of training iterations NT , hierarchical prototypes’ depth Lp and exponential decay rate β. Output: The pre-trained GNN. Initialize hierarchical prototypes {cli} Ml i=1 (l = 1, 2, · · · , Lp) for t = 1 to NT do BG ← RandomSample(D) # Get a mini-batch of graphs B′G ← AttrMasking(BG) # Get the correlated graphs hVj , hV′j , hGj , hG′j ← Eqs. (4, 5) (j = 1, 2, · · · , N ) # Extract patch and graph embeddings Llocal,Lglobal ← Eqs. (8, 13) # Compute losses θGNN
+← −∇θGNN(Llocal + Lglobal) # Update GNN’s parameters θT
+← −∇θT (Llocal + Lglobal) # Update discriminator’s parameters {cli} Ml i=1 ← Eqs. (11, 12) (l = 1, 2, · · · , Lp) # Maintain hierarchical prototypes
end for
divided intoMLp groups according to their most similar bottom layer prototype, and the mean graph embeddings are computed within each group, denoted as {ĉLpi } MLp i=1 . These mean embeddings are employed to update bottom layer prototypes via an exponential moving average scheme:
c Lp i ← βc Lp i + (1− β)ĉ Lp i , 1 6 i 6MLp , (11)
where β is the exponential decay rate. For the prototypes of upper layers, they are updated with the mean of their child prototypes in the corresponding tree:
cli ← 1∣∣C(cli)∣∣ ∑ cl+1k ∈ C(cli) cl+1k , 1 6 i 6Ml, l = 1, 2, · · · , Lp − 1. (12)
Constraint for global-semantic structure. Now that the latent semantic structure of the data has been represented by hierarchical prototypes, we seek to constrain the distributions of graph embeddings with these prototypes. The major goal here is to map correlated graphs to the same set of feature clusters. In practice, according to cosine similarity, we first search for the prototypes most similar to the embedding of graph Gj in each layer, denoted as s(Gj) = {s1(Gj), s2(Gj), · · · , sLp(Gj)}. Note that, this search process follows the topology of hierarchical prototypes, which means that: sl+1(Gj) ∈ C(sl(Gj)) (l = 1, 2, · · · , Lp − 1). Correspondingly, when using the embedding of the correlated graph G′j for search, we expect an identical searching path, and such objective is pursued by maximizing the mutual information (i.e. minimizing the InfoNCE loss) between graph embedding hG′j and the prototypes in s(Gj):
Lglobal = 1
N · Lp N∑ j=1 Lp∑ l=1 LNCE ( hG′j , sl(Gj), {c l i|1 6 i 6Ml, cli 6= sl(Gj)} ) . (13)
Discussion. A recent work (Li et al., 2020) employed hierarchical prototypes for visual representation learning. The semantic hierarchy established in that work is derived from multiple times of clustering with different numbers of clusters, which relies on heuristically selected cluster numbers and fails to model the relations between the prototypes from different hierarchies. In contrast, our method is free from pre-defined cluster numbers, and a set of relational trees are constructed to embody the hierarchical relations between different prototypes.

heading: 3.3 MODEL OPTIMIZATION
text: The training procedure of Local-instance and Global-semantic Learning (GraphLoG) is summarized in Algorithm 1. Along training, using the online-updated graph embeddings, the constraints for local-instance and global-semantic structure are derived, and the hierarchical prototypes are maintained. In each iteration, the parameters of GNN and discriminator are optimized with gradient descent using the following objective:
min GNN,T
Llocal + Lglobal. (14)

heading: 4 SUP-GRAPHLOG: A SUPERVISED BASELINE FOR LOCAL-INSTANCE AND GLOBAL-SEMANTIC LEARNING
text: In order to verify the effectiveness of local-instance and global-semantic learning when it is directly applied to supervised downstream tasks, we propose a baseline model, named as sup-GraphLoG, which combines a plain GNN and the proposed hierarchical prototypes.
In the training phase, in order to establish appropriate local-instance structure of graph embeddings, the GNN is first pre-trained along with a linear classifier to perform graph classification on the training set. For the initialization of hierarchical prototypes, the number of bottom layer prototypes is set as the class number of the supervised task (e.g. 2KT bottom layer prototypes for a task with KT binary classification problems), and each bottom layer prototype is the mean embedding of all the training graphs belonging to the corresponding class. The upper layer prototypes are initialized as in Eq. 10. For maintenance, given a mini-batch of labeled graphs, each bottom layer prototype is updated by the mean embedding of all the graphs belonging to the corresponding class using an exponential moving average scheme as in Eq. 11, and the prototypes of upper layers are maintained following Eq. 12.
For constraining the global-semantic structure, compared with the top-down search in the selfsupervised model (Sec. 3.2), in this supervised setting, we first use the label of graph Gj to randomly select a matched bottom layer prototype sLp(Gj) and then obtain the whole searching path s(Gj) = {s1(Gj), s2(Gj), · · · , sLp(Gj)} from bottom to up. Based on this positive searching path, we randomly sample a negative path sn(Gj) = {sn1 (Gj), sn2 (Gj), · · · , snLp(Gj)} satisfying that graph Gj does not belong to the corresponding class of snLp(Gj), and s n l (Gj) 6= sl(Gj), snl+1(Gj) ∈ C(s n l (Gj)) (l = 1, 2, · · · , Lp − 1). It is expected that the embedding of graph Gj is more similar with the prototypes on path s(Gj) than the ones on path sn(Gj), which defines the loss constraint on a mini-batch as follows:
Lsupglobal = 1
N · Lp N∑ j=1 Lp∑ l=1 LNCE ( hGj , sl(Gj), snl (Gj) ) . (15)
We further optimize the GNN by minimizing this loss, which refines the global-semantic structure in the embedding space.
In the inference phase, given an unlabeled graph, we first compute the similarity between its embedding and all the bottom layer prototypes via the cosine similarity function. After that, the taskspecific prediction is derived by comparing the similarity scores of the classes corresponding to these prototypes, in which the classes with larger scores serve as the prediction result.

heading: 5 RELATED WORK
text: Graph Neural Networks (GNNs). Recently, following the efforts of learning graph representations via optimizing random walk (Perozzi et al., 2014; Tang et al., 2015; Grover & Leskovec, 2016; Narayanan et al., 2017) or matrix factorization (Cao et al., 2015; Wang et al., 2016) objectives, GNNs are proposed to explicitly derive proximity-preserved feature vectors in a neighborhood aggregation manner. As suggested in Gilmer et al. (2017), the forward pass of most GNNs can be depicted in two phases, Message Passing and Readout phase, and various works (Kipf & Welling, 2017; Hamilton et al., 2017; Velickovic et al., 2018; Ying et al., 2018; Zhang et al., 2018; Xu et al., 2019) sought to improve the effectiveness of these two phases. Unlike these methods which are mainly trained in a supervised fashion, our approach aims for unsupervised/self-supervised learning for GNNs.
Self-supervised Learning for GNNs. There are some recent works that explored self-supervised graph representation learning with GNNs. Garcı́a-Durán & Niepert (2017) learned graph representations by embedding propagation, and Velickovic et al. (2019), Sun et al. (2019) and Hassani & Ahmadi (2020) achieved this goal through mutual information maximization. Also, some selfsupervised tasks, e.g. edge prediction (Kipf & Welling, 2016), context prediction (Hu et al., 2019; Rong et al., 2020a), graph partitioning (You et al., 2020) and edge/attribute generation (Hu et al., 2020), have been designed to acquire knowledges from unlabeled graphs. Nevertheless, all these methods are only able to model the local relations between different graph instances. The proposed framework seeks to discover both the local-instance and global-semantic structure of a set of graphs.
Self-supervised Semantic Learning. Clustering-based methods (Xie et al., 2016; Yang et al., 2016; 2017; Caron et al., 2018; Ji et al., 2019; Li et al., 2020) are commonly used to learn the semantic information of the data in a self-supervised fashion. Among which, DeepCluster (Caron et al., 2018) proved the strong transferability of the visual representations learnt by clustering prediction to various downstream visual tasks. Prototypical Contrastive Learning (Li et al., 2020) set a new stateof-the-art for unsupervised visual representation learning. These methods are mainly developed for images but not for graph-structured data. Furthermore, the hierarchical semantic structure of the data has been less explored in previous works.

heading: 6 EXPERIMENTS

heading: 6.1 EXPERIMENTAL SETUP
text: Pre-training details. Following Hu et al. (2019), we adopt a five-layer Graph Isomorphism Network (GIN) (Xu et al., 2019) with 300-dimensional hidden units and a mean pooling readout function for performance comparisons (Secs. 6.2 and 6.3). The discriminator for mutual information estimation is formalized as: T (x1, x2) = g(f(x1), f(x2)), where f(·) is a projection function fitted by two linear layers and a ReLU nonlinearity between them, and g(·, ·) is a similarity function (e.g. cosine similarity in our method). In all experiments, we use an Adam optimizer (Kingma & Ba, 2015) (learning rate: 1 × 10−3, batch size: 512) to train the model for 20 epochs. Unless otherwise specified, the hierarchical prototypes’ depth Lp is set as 3, and the exponential decay rate β is set as 0.95. For attribute masking, 30% node attributes in molecular graphs are masked, and 30% edge attributes in Protein-Protein Interaction (PPI) networks are masked. These hyperparameters are selected by the grid search on the validation sets of four downstream molecule datasets (i.e. BBBP, SIDER, ClinTox and BACE), and their sensitivity is analyzed in Secs. 6.4 and F.
Fine-tuning details. For fine-tuning on a downstream task, a linear classifier is appended on the top of pre-trained GNN, and an Adam optimizer (classifier’s learning rate: 1 × 10−3, GNN’s learning rate: 1×10−4, batch size: 32) is employed to train the model for 100 epochs. For sup-GraphLoG, the GNN is first trained along with a linear classifier for 50 epochs using an Adam optimizer (learning rate: 1×10−3, batch size: 32), and it is then fine-tuned under the guidance of hierarchical prototypes by an Adam optimizer (learning rate: 1×10−4, batch size: 32). All reported results are averaged over five independent runs under the same configuration. Our approach is implemented with PyTorch (Paszke et al., 2017), and the source code will be released for reproducibility.
Performance comparison. We compare the proposed method with existing self-supervised graph representation learning algorithms (i.e. EdgePred (Kipf & Welling, 2016), InfoGraph (Sun et al., 2019), AttrMasking (Hu et al., 2019), ContextPred (Hu et al., 2019) and GraphPartition (You et al., 2020)) to verify its effectiveness. Following the setting in Hu et al. (2019), after pre-training GNN models with self-supervised methods, a graph-level multi-task supervised pre-training is conducted to achieve more transferable graph representations, and the performance on downstream tasks is respectively evaluated before and after this graph-level supervised pre-training.

heading: 6.2 EXPERIMENTS ON CHEMISTRY DOMAIN
text: Datasets. For fair comparison, we use the same datasets as in Hu et al. (2019). In specific, a subset of ZINC15 database (Sterling & Irwin, 2015) with 2 million unlabeled molecules is employed for self-supervised pre-training, and a preprocessed ChEMBL dataset (Mayr et al., 2018) with 456K labeled molecules is used for graph-level supervised pre-training. Eight binary classification datasets contained in MoleculeNet (Wu et al., 2018) serve as downstream tasks.
Results. Tab. 1 reports the performance of proposed GraphLoG method compared with other works. Among all self-supervised learning strategies, our approach achieves the best performance on seven of eight tasks, and a 3% performance gain is obtained in terms of average ROC-AUC. After applying a subsequent graph-level supervised pre-training, our models’ performance is further promoted. In particular, a 2.9% increase is observed on the SIDER dataset. Also, the comparison between two supervised methods without self-supervised pre-training is presented in the table, the proposed supGraphLoG outperforms the vanilla GIN model with random initialization, which demonstrates the benefit of learning global-semantic structure. The training curves of eight downstream tasks are provided in Sec. G.

heading: 6.3 EXPERIMENTS ON BIOLOGY DOMAIN
text: Datasets. For biology domain, following the settings in Hu et al. (2019), 395K unlabeled protein ego-networks are utilized for self-supervised pre-training, and the prediction of 5000 coarsegrained biological functions on 88K labeled protein ego-networks serves as graph-level supervised pre-training. The downstream task is to predict 40 fine-grained biological functions of 8 species.
Results. In Tab. 2a, we report the test ROC-AUC of various self-supervised learning techniques, and more results on biology domain can be found in Sec. C. It can be observed that the proposed GraphLoG method outperforms existing approaches with a clear margin, i.e. a 1.8% performance gain. This result illustrates that the proposed scheme is beneficial to fine-grained downstream tasks. In addition, sup-GraphLoG is able to promote the performance of a plain GIN model by 2.8% on this biological downstream task.

heading: 6.4 ANALYSIS
text: Effect of different loss terms. In Tab. 2b, we analyze the effect of three loss terms on biological function prediction, and we continue using the GIN depicted in Sec. 6.1 in this experiment. When each loss is independently applied (1st, 2nd and 3rd row), the loss for global-semantic structure performs best, which probably benefits from its exploration of data’s semantic information. Through combining these losses, the full model (last row) achieves the best performance, which illustrates that the learning of local-instance and global-semantic structure are complementary to each other. We provide more ablation studies on different model components in Sec. E.
Results on different GNNs. Fig. 2(a) presents the effect of self-supervised pre-training on four kinds of GNNs, GCN (Kipf & Welling, 2017), GraphSAGE (Hamilton et al., 2017), GAT (Velickovic et al., 2018) and GIN (Xu et al., 2019). We can observe that the proposed GraphLoG scheme outperforms two existing methods, AttrMasking and ContextPred, on all configurations, and it avoids the performance decrease relative to random initialization baseline on GAT.
Sensitivity of hierarchical prototypes’ depthLp. In this part, we discuss the selection of parameter Lp which controls the number of discovered semantic hierarchies. In Fig. 2(b), we plot model’s performance under different Lp values. It can be observed that deeper hierarchical prototypes (i.e. Lp > 3) achieve stable performance gain compared to the shallow ones (i.e. Lp 6 2).
Sensitivity of exponential decay rate β. In this experiment, we evaluate our approach’s sensitivity to the parameter β. Fig. 2(c) shows the test ROC-AUC on downstream task using different β values. From the line chart, we can observe that the proposed model’s performance is not sensitive to β, which makes the maintenance scheme of hierarchical prototypes easy to tune.
Visualization. In Fig. 3, we utilize t-SNE (Maaten & Hinton, 2008) to visualize the distributions of graph embeddings and hierarchical prototypes on ZINC15 dataset. Compared to the model with only Lpatch constraint, some feature clusters are formed after constraining the relations between correlated graphs’ embeddings by Lgraph. More obvious feature separation is achieved after applying Lglobal, which illustrates its effectiveness on discovering the global-semantic structure of the data.

heading: 7 CONCLUSIONS AND FUTURE WORK
text: We devise a unified framework called Local-instance and Global-semantic Learning (GraphLoG) for self-supervised graph representation learning, which models the structure of a set of unlabeled graphs both locally and globally. In this framework, we novelly propose to learn hierarchical prototypes upon graph embeddings to infer the global-semantic structure in graphs. Using the benchmark datasets from both chemistry and biology domains, we empirically verify our method’s superior performance over state-of-the-art approaches on different GNN architectures.
Our future works will include exploring novel ways to construct correlated graphs, improving selfsupervised learning manners, unifying pre-training and fine-tuning, and extending our framework to other domains such as sociology, physics and material science.

heading: A THEORETICAL ANALYSIS OF CORRELATED GRAPH CONSTRUCTION
text: In our method, we choose the attribute masking (Hu et al., 2019) strategy to generate correlated graph pairs, which is widely used in recent self-supervised graph representation learning algorithms (Hu et al., 2019; 2020; Qiu et al., 2020). Since the graph structure has not been changed by the masking operation, the masked node attribute information can be partially recovered by its surrounding neighbors after being fed into a GNN. Therefore, the embeddings of correlated graph pairs can maintain a high degree of consistency in the feature space, which is desirable for the proposed GraphLoG model. We formally elucidate this point as follows.
Given an attributed graph G = (V, E , XV , XE) (XV : node attributes, XE : edge attributes), we assume that its correlated graph G′ = (V, E , X ′V , XE) is obtained by masking the attribute of a node v, i.e. X ′V ← XV−{v} ∪ {Xmv }. Proposition 1. The L-layer GNN can repair the lost information induced by attribute masking operation by Irepair > I ( Xv, {Xṽ|ṽ ∈ NLv } ) , where I(·, ·) denotes the mutual information, and NLv is the L-hop neighborhood set of v.
Proof. Before information propagation by GNN, we define the lost information Ilost induced by attribute masking as the conditional entropy of graph G conditioned on its correlated graph G′:
Ilost = H(G|G′) = H(Xv). (16) After the information propagation by GNN, we have:
Ĩlost = H(hG |hG′) = H(hG)− I(hG , hG′), (17) where Ĩlost is the information lost in the embedding of correlated graph G′ compared with the embedding of origin graph G. According to the neighborhood aggregation scheme in GNN, we can derive:
I(hG , hG′) = H(hG)−H(hv) + I ( Xv, {Xṽ|ṽ ∈ NLv } ) , (18)
where I ( Xv, {Xṽ|ṽ ∈ NLv } ) denotes the recovered information for the masked node v from its L-hop neighbors. Combining Eqs. 17 and 18 leads to:
Ĩlost = H(hv)− I ( Xv, {Xṽ|ṽ ∈ NLv } ) . (19)
We can derive the information repaired by GNN, Irepair, as: Irepair = Ilost − Ĩlost = I ( Xv, {Xṽ|ṽ ∈ NLv } ) + ( H(Xv)−H(hv) ) . (20)
Since hv is the low-dimensional embedding of node attribute Xv , we can deduce that: H(Xv) > H(hv). (21)
Therefore, combining Eqs. 20 and 21, we can conclude: Irepair > I ( Xv, {Xṽ|ṽ ∈ NLv } ) . (22)
We also evaluate the GraphLoG model with different correlated graph construction strategies, and the experimental results can be found in Sec. E.1. It empirically shows that attribute masking is more reliable to our method.

heading: B MORE IMPLEMENTATION DETAILS
text: Attribute masking strategy. We add an extra dimension in the vector of node/edge attribute and set only that dimension as 1 when the corresponding node/edge is masked. Given a mini-batch of graphs, we mask the same proportion of node/edge attributes in each graph, and, for undirected graphs, the attributes on the both directions of an edge are masked/unmasked.
GNN architecture. All the GNNs in our experiments (i.e. GCN (Kipf & Welling, 2017), GraphSAGE (Hamilton et al., 2017), GAT (Velickovic et al., 2018) and GIN (Xu et al., 2019)) are with 5 layers, 300-dimensional hidden units and a mean pooling readout function. In addition, two attention heads are employed in each layer of the GAT model.

heading: C MORE RESULTS ON BIOLOGY DOMAIN
text: In Tab. 3, we report the performance of different approaches on the downstream task of biology domain, and the results before and after applying a subsequent graph-level supervised pre-training are respectively reported. It can be observed that the proposed GraphLoG method outperforms existing approaches with a clear margin under both settings, which illustrates the effectiveness of proposed learning scheme with and without the guidance of graph-level supervisory signal.

heading: D MORE RESULTS ON GRAPH CLASSIFICATION BENCHMARKS
text: Setups. In this experiment, we compare GraphLoG with six self-supervised graph representation learning methods, i.e. random walk (Gärtner et al., 2003), node2vec (Grover & Leskovec, 2016), graph2vec (Narayanan et al., 2017), sub2vec (Adhikari et al., 2018), InfoGraph (Sun et al., 2019) and Contrastive (Hassani & Ahmadi, 2020). We strictly follow the linear evaluation protocol in Sun et al. (2019) and report the mean accuracy of 10-fold cross validation. Five conventional graph classification benchmark datasets, i.e. MUTAG (Kriege et al., 2016), PTC (Kriege et al., 2016), IMDB-Binary (Yanardag & Vishwanathan, 2015), IMDB-Multi (Yanardag & Vishwanathan, 2015) and Reddit-Binary (Yanardag & Vishwanathan, 2015), are used for evaluation. The settings of network architecture, optimizer and training parameters follow those in Sec. 6.1.
Results. Tab. 4 presents the comparisons of self-supervised approaches on five graph classification benchmark datasets. The proposed GraphLoG model ranks the first place in every task, and, especially, it outperforms a recent contrastive-learning-based method (Hassani & Ahmadi, 2020), which demonstrates the effectiveness of learning local-instance and global-semantic structure.

heading: E MORE ABLATION STUDIES
text: E.1 ABLATION STUDY ON CONSTRUCTING CORRELATED GRAPHS
In this part, we analyze three ways of constructing correlated graphs, i.e AttrMasking (Hu et al., 2019) (with 30% attribute masking rate), DropEdge (Rong et al., 2020b) (with 10% edges dropped) and GraphDiffusion (Klicpera et al., 2019) (with heat kernel to derive a denser adjacency matrix),
and evaluate them under the proposed GraphLoG framework. As shown in the first segment of Tab. 5, the AttrMasking strategy outperforms other two techniques with a clear margin, which is mainly ascribed to the fact that, compared with dropping or adding edges, masking node attributes can preserve the matching degree of correlated graph pairs to a greater extent (referring to the theoretical analysis in Sec. A).
E.2 ABLATION STUDY ON LOSS FORMAT
We investigate the effect of two loss formats, InfoNCE loss (van den Oord et al., 2018) and hingeloss-based contrastive loss (Hadsell et al., 2006), on our model. The conventional contrastive loss uses one negative sample for each positive pair and is in a hinge loss form, while the InfoNCE loss employs a large number of negative samples and is in the form of softmax. We modify the loss format in Eqs. 6, 7 and 13 to conduct the comparison. According to the second segment of Tab. 5, the InfoNCE loss marginally improve model’s performance, and both losses can achieve superior performance under the GraphLoG framework.
E.3 ABLATION STUDY ON CLUSTERING ALGORITHM
We employ three clustering algorithms to derive hierarchical prototypes in our method and evaluate their corresponding pre-trained models on downstream task. For K-means, in the prototype initialization stage, we perform clustering hierarchically as in Eqs. 9 and 10 and obtain three hierarchies of prototypes with fixed number M1 = 10, M2 = 30 and M3 = 100 for each hierarchy, respectively. Also, we design an adaptive variant of RPCL (Xu et al., 1993), named as Adaptive-RPCL, which is able to adjust the number of prototypes during training. Specifically, a counter is additionally maintained for each bottom layer prototype to record the number of iterations from the last time that the prototype is updated by graph embeddings. When a counter reaches threshold γ = 100, the corresponding bottom layer prototype is removed, and an upper layer prototype is removed if all the bottom layer prototypes in its corresponding tree are eliminated.
In the third segment of Tab. 5, the performance on biological downstream task is reported for the pre-trained models using different clustering algorithms. It can be observed that two RPCL-based clustering methods marginally outperform K-means, and their performance is comparable with each other. These results illustrate that the proposed GraphLoG model is not too sensitive to the selection of clustering algorithm.
E.4 ROBUSTNESS OF CLUSTERING ALGORITHM
In this experiment, we examine the robustness of RPCL clustering algorithm in the proposed GraphLoG model. Specifically, we conduct clustering-based hierarchical prototype initialization for six times and obtain six different self-supervised pre-training models based on distinct initialization. Fig. 4 plots the biological downstream task performance of these six models. We can observe that they perform comparably with each other, which demonstrates that the GraphLoG model is fairly robust to different clustering outputs.

heading: F SENSITIVITY ANALYSIS OF ATTRIBUTE MASKING
text: Setups. When varying the attribute masking rate to evaluate its sensitivity, other hyperparameters are fixed as the values depicted in Sec. 6.1. In specific, the hierarchical prototypes’ depth Lp is set as 3, and the exponential decay rate β equals to 0.95.
Results. In Fig. 5, we plot model’s performance on the downstream tasks of chemistry and biology domains under different masking rates. The highest test ROC-AUC is achieved when attribute masking rate is around 30%, which means that, under such settings, the constructed correlated graphs benefit the proposed learning scheme most.

heading: G TRAINING CURVES
text: In Fig. 6, we plot the training curves of four approaches, i.e. the random initialization baseline, context prediction (Hu et al., 2019), attribute masking (Hu et al., 2019) and the proposed GraphLoG method, on eight molecular property prediction tasks. From these line charts, we can observe that, through pre-training on a large-scale unlabeled dataset by GraphLoG, GNN model is able to converge at a higher ROC-AUC on the training set compared with other three methods.

Review summaries:
This paper proposes an unsupervised framework to perform graph representation learning. The local-instance structure is learned by first gets patch-level and graph-level representations for each graph, then maximize the mutual information between both correlated patches and correlated graphs, which are decided by attribute masking strategy. The global-semantic structure is maintained by leveraging RPCL to derive hierarchical prototypes of the representation and maximizing the mutual information between correlated graph representation and the searching path in the prototypes.

This paper proposed a method for self-supervised graph-level representation learning. The main idea is to enforce both the instance level smoothness embedding constraints, and a so-called global, semantic grouping structures across all instance graphs in the training data set.  To achieve this goal, the authors have adopted a global clustering framework to encourage the embedding of the graphs belonging to the same clusters to be close to each other, and by using a hierarchically organized set of prototypes. The proposed method is applied to pre-train GNN on massive unlabeled graphs, which is then fine-tuned to downstream learning tasks.