Motif-Driven Contrastive Learning of Graph Representations
Authors: Shichang Zhang
Ziniu Hu
Arjun Subramonian
Yizhou Sun
Venue:  (2021)
Keywords: graph neural network
self-supervised learning
contrastive learning
graph motif learning

Abstract: Graph motifs are significant subgraph patterns occurring frequently in graphs, and they play important roles in representing the whole graph characteristics. For example, in the chemical domain, functional groups are motifs that can determine molecule properties. Mining and utilizing motifs, however, is a non-trivial task for large graph datasets. Traditional motif discovery approaches mostly rely on exact counting or statistical estimation, which are hard to scale for a large number of graphs with continuous and high-dimension features. In light of the significance and challenges of motif mining, we propose : MICRO-Graph: a framework for \underline{M}ot\underline{I}f-driven \underline{C}ontrastive lea\underline{R}ning \underline{O}f \underline{G}raph representations to: 1) pre-train Graph Neural Networks (GNNs) in a self-supervised manner to automatically extract graph motifs from large graph datasets; 2) leverage learned motifs to guide the contrastive learning of graph representations, which further benefit various graph downstream tasks. Specifically, given a graph dataset, a motif learner cluster similar and significant subgraphs into corresponding motif slots. Based on the learned motifs, a motif-guided subgraph segmenter is trained to generate more informative subgraphs, which are used to conduct graph-to-subgraph contrastive learning of GNNs. Our discovering strategy is to simutaneously do clustering and contrastive learning on dynamically sampled subgraphs. The clustering part pull together similar subgraphs across different whole graphs, as the contrastive part push away dissimilar ones. Meanwhile, our learnable sampler will generate subgraph samples better aligned with the discoverying procedure. By pre-training on ogbn-molhiv molecule dataset with our proposed MICRO-Graph, the pre-trained GNN model can enhance various chemical property prediction downstream tasks with scarce label by 2.0%, and significantly higher than other state-of-the-art self-supervised learning baselines. 


Under review as a conference paper at ICLR 2021
MOTIF-DRIVEN CONTRASTIVE LEARNING OF GRAPH REPRESENTATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph motifs significant subgraph patterns occurring frequently in graphs, and they play important roles in representing the whole graph characteristics. For example, in chemical domain, functional groups are motifs that can determine molecule properties. Mining and utilizing motifs, however, is non-trivial task for large graph datasets. Traditional motif discovery approaches rely on exact counting or statistical estimation, which are hard to scale for large datasets with continuous and high-dimension features. In light of the significance and chal- lenges of motif mining. we propose MICRO- Grrp:: framework for Motff-driven Contrastive leaRning Of Graph representations to: 1) pre-train Graph Neural Net- works (GNNs) in self-supervised manner to automatically extract motifs from large graph datasets; 2) leverage learned motifs to guide the contrastive learning of graph representations, which further benefit various downstream tasks. Specif- ically, given a graph dataset, a motif learner cluster similar and significant sub- graphs into corresponding motif slots. Based the learned motifs, motif-guided subgraph segmenter is trained to generate more informative subgraphs, which are used conduct training on ogbg-molhiv molecule dataset with our proposed MICRO-Graph the pre-trained GNN model can enhance various chemical property prediction down- stream tasks with scarce label by 2.0%, which is significantly higher than other state-of-the-an self-supervised learning baselines.
contrastive learning of GNNs. By pre-
INTRODUCTION
Graph-structured data, such molecules and social networks, is ubiquitous in many scientific search areas and real-world applications. To represent graph characteristics, graph motifss were proposed in Milo et al. (2002) significant subgraph patterns occurring frequently in graphs and uncovering graph structural principles. For example, functional groups are important motifs that can determine molecule properties. Like the hydroxide (-OHf) usually implies higher water solubility, and for proteins, Zif268 can mediate protein-protein interactions in sequence-specific DNA-binding proteins. (Pabo et al. 200T)
Graph motif's has been studied for years. Mcaningful motifs can benefit many important applications like quantum chemistry and drug discovery (Ramsundar et al. 2019). However, extracting motifs from large graph datasets remains challenging question. Traditional motif discovery approaches (Milo et al. 2002 Kashtan et al.) 2004, Chen et al. 2006; Wernicke (006) rely on discrete counting or statistical estimation, which are hard to generalize to large-scale graph datasets with continuous and high-dimension features, as often the case in real-world applications.
Recently, Graph Neural Networks (GNNs) have shown great expressive power for learning graph representations without explicit feature engineering (Kipf Welling 2016 Hamilton et al., 2017 Veličković al.
Xu et al.) 2018). In addition, GNNs can be trained in a self-supervised manner without human annotations to capture important graph structural and semantic properties Veličkovié al. 2018 Hu al. 2020c Qiu al. 2020; Bai et al., 2019 Navarin et al. 2018
2017
Wang et al., 2020 Sun et al.] 2019 Hu et al. 2020b). This motivates us to rethink about motifs as more general representations than exact structure matches and ask the following research questions:
Can we use GNNs to automatically extract graph motifs from large graph datasets?
Can we leverage the learned graph motif to benefit self-supervised GNN learning?

---

Under review as a conference paper at ICLR 2021
In this paper, we propose MICRO- Graph: framework for Motlf-driven Contrastive leaRning Of Graph representations. The key idea of this framework is to learn graph motifs as prototypical cluster centers of subgraph embeddings encoded by GNNs. In this way, the discrete counting problem is transfered to a fully-differentiable framework that can generalize to large-scale graph datasets with continuous and high-dimensional features. In addition, the learned motifs can help generate more informative subgraphs for graph-to-subgraph contrastive learning. The motif learning and contrastive learning are mutually reinforced to pre-train more generalizable GNN encoder.
For motif learning, given a graph dataset, a motif-guided subgraph segmenter generates subgraphs from each graph. and GNN encoder turns these subgraphs into vector representations. We then learn graph motifs through clustering, where we keep the K prototypical cluster centers as represen- tations of motifs. Similar and significant subgraphs are assigned the same motif and become closer to their corresponding motif representation. We train our model in an Expectation-Maximiiii (EM) fashion to update both the motif assignment of each subgraph and the motif representations.
For leveraging learned motifs, we propose a graph-to-subgraph contrastive learning framework for GNN pre-training. One of the key components for contrastive learning is to generate semantically meaningful views of each instance. For example, a continuous span within a sentence (Joshi et al.) 2020) or a random crop of an image (Chen et al., 2020). For graph data, previous approaches leverage node-level views, which is not sufficient to capture high-level graph structural information Sun et al. (019)). As motifs can represent the key graph properties by its nature, we propose to leverage the learned motifs generate more informative subgraph views. For example, alpha helix and beta sheet can come together as a simple 33ax fold to form a zinc finger protein with unique properties. By learning such subgraph co-occurrence via contrastive learning, the pre-trained GNN can capture higher-level information of the graph that node-level contrastive can't 't capture.
The pre-trained GNN using MICRO-Graph on the ogbg-molhiv molhiv molecule dataset can successfully learn meaningful motifs, including Benzene rings, nitro, acetate, and etc. Mcanwhile, fine-tune this GNN on seven chemical property prediction benchmarks yielding 2.0% average improvement over non-pretrrn con-pretrained GNNs and outperforming other self-suupr pre-training baselines. Also, extensive ablation studies show the significance of the learned motifs for the contrastive learning.
2 RELATED WORK
The goal of self-supervised learning is to train a model to capture significant characteristics of data without human annotations. This paper studies whether we can use such approach to automatically extract graph motifs, i.e. the significant subgraph patterns, and leverage the learned motifs to benefit self-supervised learning. In the following, we first review graph motifs especially challenges for motif mining, and then discuss approaches for pre-training GNNs in a self-supervised manner.
Graph motifs are building blocks of complex graphs. They reveal the interconnections of graphs and represent graph characteristics. Mining motifs can benefit many tasks from exploratory analysis to transfer learning (Henderson et al. 2012). For many years, various motif mining algorithms have categories, either exact counting as in Milo et al. (2002);
been proposed. There are generally Kashtan et al.] (2004); [Schreiber & Schwöhhermeyer (2005); Chen et al. (2006). or sampling and statistical estimation as Wernicke (2006). However, both approaches cannot scale large graph datasets with high-dimension and continuous features, which is common in real-world applications. In this paper, we proposes turn the discrete motif mining problem into GNN-based differentiable cluster learning problem that can generalize to scage datasets. Another GNNNbaser work re- lated to graph motifs the GNNExplainer, which focuses on post-process model interpretation (Ying) et al. 2019). It can identify substructures that are important for graph property prediciton, e.g. mo- tifs. The difference between GNNExplainer and MICRO-Graph single graph level, and the later learns motifs across the whole dataset.
that the former identify motifs at
Contrastive learning is one of the state-of-the-art self-supervised representation learning algo- rithms. It achieves great results for visual representation learning (Chen et al.) 2020 He et al.) 2019). Contrastive learning forces views generated from the same instance (e.g. different crops of the same image) to become closer, while views from different instances apart. One key component in contrastive learning is to generate informative and diverse views from each data instance. In com- puter vision, researchers use various techniques, including cropping, color distortion, and Gaussian
2

---

Under review as a conference paper at ICLR 2021
blurs to generate views. However, when it comes to graphs, constructing informative view of graph a challenging task. In our framework, we utilize the learned motifs, which are significant subgraph patterns, guide view (subgraph) generation, and conduct graph-to -oap--tt-uubraphh contrastive learning.
Self-supervised learning for GNNs also draws many attention recently. For graphs, representa- tions can be different levels, e.g. node level and (sub)graph level. Veličković et al.) (2018): Hu
et al. (2020c): QQu et al. (2020) mainly focus on node-level representation learning in a single large graph, as opposed to the focus of this paper, which is representation learning of whole graphs. Hu et al. (2020b) provides a systematic analysis of pre-training strategies on graphs for both node-level and graph-level. However, only the node-level learning is suff-supervised, and annotated labels are utilized for supervised learning at the graph level. For graph level self-supervised representation learning, [unn et al. (2019) proposed contrastive framework, InfoGraph, maximize the mutual information between graph representations and node representations. In [Rong et al.] (2020), the discrete
GROVER model and motif based self-supervised learning task was proposed, where motifs are first extracted using professional software, and then these motif's are used as prediction labels for pre-training the model. The difference between motifs GROVER and in MICRO-Graph is that GROVER uses discrete structures, but MICRO-Graph uses continuous vector embeddings To alleviate these issues, we propose graph-to-subgrapp view self-supervised contrastive learning, and the subgraph generation is guided by the learned motifs.
METHODOLOGY
The goal of this paper is to train GNN encoder that can automatically extract graph motifs, i.e. sig- nificant subgraph patterns. Motif discovery discrete graph structures is combinatorial problem, and it hard to generalize to large datasets with continuous features. We thus propose to formalize this problem learning. In this section, we formalize the problem and introduce the overall framework of MICRO- Graph in Section 3.1 and then describe each module in details in the following sections.
differentiable clustering learning problem and solve it via self supervuuee GNN
4) Learn motifs via clustering and then train segmenter.
Motif Learner
GNN Encoder
Motif-guided Segmenter
Pooling
Contrastive Learner
2) Get node embeddings for each graph
3) Get subgraphs via node segmentations, then get subgraph embeddings through pooling.
5) contrastive learning between graph and subgraphs
Take input batch graphs, e.g. malecules
Figure 1: Overall framework of MIChO-Graph. A GNN trained in self-supervised manner to automatically extract motifs. The learned motifs are leveraged to generate informative subgraphs for graph-to-subgraph contrastive learning.
3.1 THE OVERALL FRAMEWORK OF MICRO-Graph
the differentiable clustering learning problem is meant to learn two things. One is GNN-based graph encoder E(.) that maps input (sub)graphs an embedding vector. The other is a K-slot embedding table {mi, mk J. where each slot is motif vector corresponding to a cluster center of embeddings of frequently occurred subgraphs. To tackle this problem, we introduce the MICRO-Grapy framework which consists three modules: 1) snrif- Segmenter extract important subgraphs; 2) Motif--Larmn to cluster sampled subgraphs and identify motifs; 3) a constrastive learning module for graph-to-subgrapy contrastive learning. The overall framework is shown in Figure We describe details of each module in the
Given a dataset with M graphs G
3

---

Under review as a conference paper at ICLR 2021
following sections. The Motif Learner is introduced first in Section 3.2 and then the Motif-guided Segmenter and the constrastive learning module in Section 3.3 and 3.4 respectively.
3.2 MOTIF LEARNER VIA EM CLUSTERING
The Motif Learner learns motifs by applying Expectation-Mxxiizatton (EM) style cluster- ing algorithm on sampled subgraphs. To start clustering, the Motif-guided Segmenter first ex- tracts N subgraphs {/ from the input whole graphs. For each subgraph Jj. generate its embedding ej E(g;) and calculate the cosine similarity between ej and each of the K motif vectors (m1,.... mx We denote the similarity between ej and the kth motif vector as Sk,, = 6(m²) o(e,) D In vector notation, the K-dimensional vector of similarities between 9j and all K motif vectors denoted 8j, and the K-by-N-dimensionall matrix is denoted as S, where the j-th column of S is 8j and the entry (k, j) of S is Sk.j
motif-to-subgraph similarity
E-Step. The goal of the E-step is come up with motif-hased cluster assignments for subgraph embeddings {e,) {e,) The assignments can be represented by a K-by-N-dimensional matrix Q = [q...... qvl. where the j-th column Q contains the probabilities of assigning the j-th subgraph to each of the K motifs. Each qy can be one-hot vector for hard clustering or a probability vector with all the entries sum up to one for soft-clustering. This vanilla version clustering problem boils down to maximizing the objective Tr(Q"S), 5). which corresponds to an assignment Q that maximizes similarities between embeddings and its assigned motif. This objective works fine for traditional EM clustering algorithm when embeddings are fixed. However, since representations will change when doing representation learning, this vanilla objective in the E-step can lead to degenerate solution, i.c. all representations collapse to a single cluster center. To avoid this issue, we follow YM. al. (2020) introduce an entropy term and equal-size constraint Q for clusters to have similar sizes. Our final objective is:
1 1(Q) max TT S)+
max
(1)
QE
where H(Q) = - Qig log Qi is the entropy function, and the constraint set Q requires the marginal projection of onto its columns and rows be uniform.
K.N Q1N Q (Q E R
1K K
Q1k
1N
where 1n and 1 are all one vectors. This constraint optimization problem turns out to be an optimal transportation problem with closed-form solution as (3) and can be solved efficiently using a fast Sinkhorn- Sinkhorn-Knopp algorithm.
Q' diag(u) exp(AS) diag(v)
Here u and v are normalization vectors. The derivations can be found in Cuturi 2013
M-Step. The goal of the M-step is to maximize the log-likelihood of data given the clus- ter assignment matrix Q estimated in the E-step. We update parameters in the GNN encoder and the motif embedding table through the M-step. This step is equivalent classification problem with labels Q and prediction scores S. Thus, we first apply a columnwise softmax normalization with temperature Tg to S convert all entries of 5 to probabilities, i.. Sky = softmax (Sp./Ta). Then we use the negative likelihood as the loss function.
supervised K-class
C.
Qua log Sk.j
3.3 MOTIF-GUIDED SUBGRAPH SEGMENTER
Sampling informative subgraphs is crucial for both the Motif-Learner and the contrastive learning module. Traditional heuristic approaches such as random walk and k-hop neighbour sampling can- not guarantee to generate semantically reasonable and informative subgraphs. For example, heuris- tically sampled molecule subgraphs are likely to be a chain carbons, which doesn't contain much
For notation simplicity, we denote L-2 normalization operator oi-) such that d(x) ||//|2-
4

---

Under review as a conference paper at ICLR 2021
information about the original molecule, or it can be a fragment of a meaningful chemical structure, which loses the original chemical property. Since motifs are by nature informative subgraph pat- terns, we propose to leverage the learned graph motif's to design the porif-guuded segmenter, which will learn to segment a given graph into several subgraphs that are close to some discovered motifs.
Subgraph Sampling via Segmentation. To generate subgraphs from graph G. via segmentation, we first generate node affinity matrix A A and then do segmentation based on A Specifically, given the graph G, with n nodes, we use the GNN encoder E--) to generate the D-dimensional node of all nodes in Gt. After that, compute the n-by-n --dimension node affinity matrix A by first computing pairwise cosine similarities between node embeddings, and then applying row-wise softmax normalization with temperature Tn to the cosine similarity matrix. This normalization step is important because it transforms all the affinity scores to be in the range (0.1) and make the affinity scores of node pairs with high cosine similarities further stand out. The formula for computing the affinity score between node and node in graph Ge i.e. the entry (s. L) of A (9) is the following.
embeddings i,...... .... T2,
softmax, (o( ((n))/TT) (d(m)))((ma)TTT)
Afterwards, treat this affinity matrix A (+) complete graph with nodes and affinity scores as edge weights. Applying spectral clustering on this complete graph segments nodes into differ- ent groups. Within these groups, the connected components that have more than three nodes are collected as our sampled subgraphs. Multiple subgraphs may be sampled from the whole graph Gr. For particular subgraph gy. its embedding e, will be generated by indexing and aggre- gating the node embeddings generated when computing the affinity matrix. For example, if is the indices of the nodes forming the subgraph 9j selected by the Motif-guided segmenter, then ej Aggregate( ((n,, n., } [T]). The aggregate operation can be any order-invariant operation over a set of vectors, e.g. mean, sum, or elementwise max. our experiment, we follow the start- of-the-art result from previous works and use the mean. Collecting subgraphs from all M whole graphs result in the total set of subgraphs و mentioned above.
Motif-guided Training. To train the segmenter to produce subgraphs close to motifs, the motif- to-subgraph similarity matrix is used as the guidance. For a subgraph gj sampled from a whole graph G, whose node affinity matrix is A At) If the similarity between gj and any motif is higher than threshold, make the affinity values among all the nodes within Jj increase, and the affinity value between these nodes and other nodes not in gj to decrease. The loss function is as below.
N
C. =
Σ
1[3k SKJ > Me V1
< k K
(6)
N
(s.1)Eg;
Here Me is the threshold used to decide whether a subgraph is similar enough to the learned mofit k, and it is dynamically computed. In each iteration, we set 77 to select the top 10% most similar subgraphs to motif k. The intuition is that if the subgraph Øj is considered similar to a motif, then update the embeddings of its nodes to become similar. By optimizing this loss, during the next sampling round, nodes produced motif-like subgraphs are more likely to be segmented together, which leads to more subgraph samples align with the motifs.
3.4 CONTRASTIVE LEARNING BETWEEN GRAPHS AND SUBGRAPHS
An expressive GNN encoder E(-) is essential for capturing graph properties and accurately iden- tifying motifs. We thus introduce a constrastive learning module to help the GNN learning. This module and the Motif Learner will mutually enhance each other to train better GNN.
Contrastive learning is one of the state-of-the-ar self-supervised learning methods. One key compo- nent in contrastive learning is to generate informative and diverse views of data instances. Previous contrastive methods on graphs utilized either nodes or whole graphs as views, which do not very well capture the micro-structure of graphs. To alleviate this issue in our constrastive learning mod- ule, we use the subgraph generated by our Morif guided segmenter as one view of the graph, and the whole graph another view.
5

---

Under review as a conference paper at ICLR 2021
Similarly to how generate the subgraph embeddings, the whole graph embedding h; of graph G3 is generated by aggregating node embeddings output by the GNN encoder E(.), h; = Aggregate( [TI,.... .... n2 ity matrix W, which is cosine similarity between each graph-subgraph pair followed by a row-wise softmax normalization with temperature Tg-
I. Then construct the M-by-N dimensional sraph-to-subgrppe similar-
WiS (attmax;(((h))) (((;))/
For the whole graph 9s subgraphs sampled from it are considered positive pairs to it, and subgraphs sampled from other graphs are considered as negative pairs to it. Then the contrastive objective function is the following:
M
N Wis 1(gs E 9i}
C. = M
ΣV
Σ
(8)
ContextPred: Node-to-Subgraph
InfoGraph: Node-to-Graph
MICRO-Graph (Ours): Subgraph-to-Grant
Contest
Graph Pooling
Graph Pooling
Figure 2: (Figure updated) Different ways generate views for graph data. Context Prediction uses one node and one context graph as views. InfoGraph uses one node and the whole graph as views. Our method uses higher-level subgraph as one view and the whole graph as another; thus the GNN can capture more global contextual information.
We show the diew-generation difference between our framework and other existing methods in Figure [ Existing contrastive learning methods rely on node-node views or node-graph views. Researchers in computer vision domain have found that conducting contrastive learning on more flexible views, e.g. arbitrary-sized image crops, leads to better representations, especially much better than lower pixel-level views (Chen al. 2020). our framework, the contrastive learning on graph-subgraph views is similar to this intuition from computer vision. It can capture higher-level information the node views cannot capture, and thus produce more meaningful representations.
Note that the subgraphs we utilize is generated by our Motif-guided Segmenter. In section we sys- tematically study the influence of subgraph sampling methods. Experiment results show that simple heuristic sampling methods lead to bad generalization performance. This shows the significance of leveraging the learned graph motifs to generate more informative views of graph-structured data.
3.5
JOINT TRAINING
The overall objective of Araph is a weighted sum of all three loss terms described above.
L == Am Lm + Xgh, + Ache
(9)
With the proper constraints introduced to the E-step of the Motif-Learner (equation (I) and (2)), the whole framework can be trained end-to-end without worrying about degenerate solutions.
MICRO-Graph can simultaneously train an expressive GNN encoder and learn motifs of the given graph dataset. Moreover, the motif learning and contrastive learning better GNN produces more accurate subgraph embeddings and thus help motif mining, while better motifs help generate more informative traph-to-subgrapp views and benefit contrastive learning.
mutually reinforced:
We show the the pseudocode of our approach in Algorithm I First, initialize the motif vectors and GNN encoder (line 2 3). For each batch of graphs G, our segmenter will calculate the node-nod affinity matrices A and extract subgraphs based on the affinity scores (line 5 - 6). After that, we apply GNN message passing whole graphs get the node embeddings and aggregate them for

---

Under review as a conference paper at ICLR 2021
both graph and subgraph embeddings (line 7 9). The next step is compute the motif-to-subgraan similarity matrix S. Using S we compute both the threshold 1 and cluster assignment matrix Q (line 11 - 13). With all these values, the three loss terms and the final joint loss introduced above can be computed (line 15 - 20)..
Algorithm Pseudocode MICRO-Graph in PyTorch Style, full version in Appendix
tempereture parameters: tau_g, tauL,, weight parematers: 1amb m, lamb_e, Lamb_s madel Motif largs) # modal contains all motif vactora, model.motise encoder = GNN (arge) it GNN eacedes for pre-training
loader:
$T: node Index of subgraph, Ar affinity matrices, nun_subs: + of subgrapha graph I, aun_suba, & segmenter encodex)
encoder
8
=ggregate (h, 8) x
=aggregate (n, T) x
10
S = blaaviie_cossnn__simmmmeee with torch.no_grad():
el $ 8
12
eta topK_thresholdds) 1 take the topk similarity scores Q #iakhora use the Sinkhora Kzopp to solve for Q
13
15
loas_a compler_losske cta)
S_tilde torch.so"tmaxx
tau_g, 61m=0) K
17
loss__ motif_ $_tilda)
torch.softmax (pst (ps1 rwise www.seeooatnneeeeee poaine__im(h,, e)/tau_5 dim=1)
losa_e snverastive_lssee num_subs) $ need nua_subs Irom segaenter
loss lamb_amlcss_n lamb_cvloss__ Lamb_saloss_s
4 EXPERIMENTS
We evaluate the effectiveness of MICRO-Gras Graph from two perspective: 1) Whether the self- supervised framework can learn better GNNs that generalize well on graph classification tasks; 2)
whether the learned motifs reasonable and truly benefit contrastive learning.
We mainly focus on chemical property prediction tasks. Specifically, we pre-train GNNs using MICRO-Graph on the ogbg-molhiv dataset from Open Graph Benchmark (OGB) (Hu et al. 2020a).. This dataset contains 40K molecules. We test our pre-trained model on smaller molecule graph classification datasets. For more details of the datasets, please see Appendix E
4.1 EVALUATION PROTOCOLS
We evaluate the effectiveness of pre-training using the following two evaluation protocols.
Transfer Learning Setting: we fine-tune tune the pre-trained GNN model with small portion of labels on downstream tasks. We adopt the same train-test and model selection procedure as in Yanardag
& VVishaanathan (2055): Zhang et al. (2018); ; Xu et al. (2018), where we perform 10-fold cross- validation and select the epoch with the best cross- validation performance averaged over the 10 folds. The evaluation metric is ROC-AUC score.
Feature Extraction Setting: the setting is almost the same as transfer learning. Except that we fix the pre-trained GNN, use it as feature extractor to get graph representations of all the data in downstream tasks, and then train a linear classifiers on top.
4.2 BASELINES AND MODEL CONFIGURATION
We consider five baselines, including non- con-pretrain (direct supervised learning) and four state-of-the- art GNN self-supervised learning (SSL.) methods.
InfoGraph (Sun et al. 2019) maximizes the mutual information between the representations of the whole graphs and the representations of its substructures different granularity.
Context prediction (Hu et al. 2020b) predicts surrounding graph structures of each node, so nodes appearing in similar structural contexts will be mapped nearby representations.

---

Under review as a conference paper at ICLR 2021
GPT-GNN (Hu et al. 2020c) predicts masked edges and masked node attributes. The edge pre- diction makes node representations to be close when there are edges between them. The attribute prediction captures how node attributes are distributed over all graphs
GROVER (Rong et al. 2020p first uses professional software, e.g. RDKit RDKit Landrum et al. 2006), to extract functional groups (motifs) from whole dataset. Using these motifs as a label set, each molecule is assigned a label representing which motif shows up in and which doesn't, 't. The model then pre-trained by predicting this motif label as a multi-class classificaiton problem.
The state-of-the-art GNN model, Deeper Graph Convolutional Networks (DeeperGCNs) proposed Ln al. (2020), is used as the base GNN encoder for MICRO- Graph and all baselines. We use the same hyperparameters for all experiments. Details about hyperparameters and model configurations are in Appendix F
4.3 EVALUATION RESULT
The evaluation results under transfer learning setting and feature extraction setting is illustrated in Table D and Table 2 For both setting, the proposed MICRO-Gruph outperforms all baselines on average performance and achieves the highest results on most datasets. For transfer learning setting, we gain about 2.0% performance enhancement against non non-pretrain baseline. This shows the effectiveness of our supe-supe learning framework for pre- rre-trainin GNNs.
SSL methods
bace
bbbp
clintox
hiv
sider
tox21
toxcast
Average
Pon-Pretrain
72,80
2.12
82.13 + 1.69
74.98
3.59
73.38
0.92
55.65
1.35
76. + 0.58
63.34 = 0:75
71.19
ContextPred
73.02 + 2.59
80.94 + 2.55
74.57
3.05
73.85
1.38
54.15 = 1.54
74.85 + 1,28
63.19 = 0.94
70.65 ( (-0.54)
InfoGriph
76.09
78.36
76.12
(+0.93)
GPT-GNN
75.56 + 2.49
83.35 = 1.70
74.84
+ 3.45
74.82
: 0.99
55.59
= 1.58
76.34
+ 0.68
64.76 = 0.62
72.18 (+0.99)
GROVER
75.22
83.16
1.44
76.8
+ 3.29
74.46
1.06
56.63
1.54
76.77
0.81
64.43
+ 0.8
72.5
MICRO-Graph
76.16 + 2.51
83.78 1.77
77.50
+ 3.35
75.31
0.67
57.28
1.09
76.68 + 0.36 65.42 0.62 73.19 (+2.0)
Table 1: Transfer learning performance (ROC-AUC) of MICRO-Graph compared with other self- supervised learning (SSL) baselines on molecule property prediction benchmarks. Pre-train GNNs on ogbg-molhiv dataset, fine-tune the pre-trained model on each downstream task for 10 times.
SSL methods
hace
bhhp
clintox
hiv
sider
lax21
loxcast
Average
ContextPred
53.09 =
55.51
0.08
40.73
0.02
53.31 +
52.28 0.08
35.31
0.25
47.06 0.06
48,18
InfoGmah
66.06 = 0.82
75.34 - 0.51
75.71
0.53
61.45
0.74
54.7 0.24
63.95
0.24
52.69 + 0.07
64.27
GPT-GNN
59.43
71.58
0.54
62.78
0.58
64.08
$4.67
57.06
62.53
GROVER
65.67 = 0.38
78.47 + 0.36
53.19
+ 0.68
69.03
+ 0.23
54.94 0.12
67.63
0.13
57.28 + 0.05
63.74
MICRO-Graph
69.54
81.07 0.42 63.69
0.56 72.74 1
55.39 0.26
0.12
61.04
68.05
Table 2: Feature extraction performance (ROC-AUC) of MICRO-Grape compared with other self- supervised learning (SSL) baselines on molecule property prediction benchmarks. Use pre-trained models to extract graph representations for each data and train linear classifiers on top. Run each experiment times.
4.4 ABLATION STUDY
We conduct series of ablation studies systematically analyze how the motif learning can benefit the contrastive learning.
4.4.1 WHETHER MOTIF IS HIELPFUL FOR SUBGRAPI SAMPLING?
As previously discussed, the main difference of our contrastive framework with existing works is that we leverage the graph-to-subgrap views for contrastive learning. We first study whether our proposed motif- motif-guided guided subgraph segmenter can indeed help contrastive learning. We implement two more widely adopted heuristic subgraph sampling baselines: random walk (RW) and K-hop neigh- bours (K- (K-hop). We replace our Motif suided Segmenter (MS) component with these two heuristic sampling algorithm for the transfer learning experiments. All the other settings stay the same.
8

---

Under review as a conference paper at ICLR 2021
Sampler
hace
hhhp
clintox
hiv
sider
lox21
toxcasi
Average
RW
73.61 2.53
82.24 1.99
75.63 2.86
73.06
1.29
55.88 + 1.69
0.56
63.44 0.76
71.42
K-hop
73.24 = 2.65
82.65 + 1.78
76.76 +: 3.88
73.48 1.41
55.67 + 1.51
76.01 =: 0.69
63.34 = 0.94
71.59 (+0.4)
65.42
(+2.0)
Table 3: Ablation study: analyzing the influence of subgraph sampler.
Motif
bbbp
clintox
texcast
Average
5
75.81 +: 2.18
82.65 = 1.97
76.95 4: 2.44
74,53 +: 1.12
56.78
1.64
77.01 1: 0.89
64.45 1: 0.59
72.59 (+1.4)
83.78
75.51
57.28
65.42
(+2.0)
100
75.98
2.36
83.68
1.62
76.91
+ 2.57
75.06
+: 0.92
57.32
1.12
76.98
0.55
65.39 +: 0.69
73.04 (+1.85)
Table 4: Ablation study: analyzing the influence of different motif numbers.
As shown in Table 3 replacing MS with heuristic subgraph samplers will significantly influence the performance. With random walk or k-hop sampling, graph-to-subgraph contrastive learning can only bring in 0.2-0.4% average performance enhancement against non non-pretrain, which are far less than MS. This shows that the key for the overall performance enhancement of MICRO-Graph not only the traph-to-subgrapp views, but also the informative motif-guided subgraphs. For the details of each sampling strategy and the corresponding subgraphs examples, please refer to Appendix D
4.4.2 WHETHER MOTIF NUMBER WILL INFLUENCE CONTRASTIVE LEARNING?
Number of motif slots, K, is important hyperparameter in motif learning framework. We thus conduct ablation study with three different K values, 5, 20, and 100. As illustrated in Table with different K values, MICRO- MICRO-Graph can consistently enhance the transfer performance by large margin. Among the three numbers used, the middle one (20) gives the best result on average.
4
4.5 VISUALIZATION OF THE LEARNED MOTIFS
We further show learned motifs by collecting the closest subgraphs them. As illustrated in Figure 3 MICRO-Grun Graphh automatically learns motifs that are similar to meaningful functional groups in molecule domain, such Benzene rings and acetate. This shows that MICRO-Grape reasonable and meaningful motifs. A complete list of the learned motifs is shown in Appendix C
learn
NH3
OH2
OH2
OH2
OH2
H2C
OH2
Figure 3: (Figure updated to higher resolution) Top-6 frequently occurred motifs, represented by their closest subgraph.
CONCLUSION
In this paper, we propose SICRO-Graph to pre-train GNN in self-supervised manner to auto- matically extract graph motifs from large-scale graph datasets. In addition, the learned motifs can guide the generation of more informative subgraphs, and help to conduct graph-to-subgraph con- trastive learning. The motif learning and contrastive learning are mutually reinforced, and eventually help pre-train generalizable GNN encoder. By pre-training MICRO- Graph, we can learn meaningful motifs that align with existing molecular functional groups. Mcanwhile, fine-tune the pre-trained GNN on seven chemical property prediction benchmarks yield- ing 2.0% average improvement over non non-pretrained GNNs and outperforming other sup-rsueee pre-training baselines.
ogbg-molhiv molecule dataset with

---

Under review as a conference paper at ICLR 2021
REFERENCES
Yunsheng Bai, Hao Ding, Yang Qiao, Agustin Marinovic, Ken Gu, Ting Chen, Yizhou Sun, and Wei Wang. Unsupervised inductive graph-level representation learning via graph-graph proximity, 2019.
Jin Chen, Wynne Hsu, Mong Li Lee, and See-Kiong Ng. Nemofinder: Dissecting genome-wide protein-protein interactions with meso-scale network motifs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 106-115, 2006.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations, 2020.
Marco Cuturi. Sinkhorn distances: 2013.
Lightspeed computation of optimal transportation distances,
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances neural information processing systems, pp. 1024-1034, 2017.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. arXiv preprint arX1v:1911.05522, 2019.
Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. Rolx: structural role extraction mining in large graphs. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge dis- covery and data mining, pp. 1231-1239, 2012.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005. 200000005.0087. 2020a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representations, 2020b. URL https::/openreviiet net net/forumiid
HJ [UIWKSSFD
Ziniu Hu, Yuxiao Dong, Kuansan Wang. Kai- Wei Chang, and Yizhou Sun. Gpt-gnn: Generative pre-traiming of graph neural networks. Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2020c.
Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S. Weld, Luke Zettlemoyer, and Omer Levy. Spanbert: Improving pre-training by representing and predicting spans. Trans. Assoc. Comput, Linguistics, 8:64-77, 2020. URL https::/ttrassac:
article/view/1Ba
Nadav Kashtan, Shalev Itzkovitz, Ron Milo, and Uri Alon. Efficient sampling algorithm for estimat- ing subgraph concentrations and detecting network motifs. Bioinformatics, 20(11): 2004.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.00709 2016.
Greg Landrum al. Rdkit: Open-source cheminformatics. 2006.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train
deeper gens, 2020.
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Net- work motifs: simple building blocks of complex networks. Science, 298(5594)8224 827, 2002.
Nicolò Navarin, Dinh V. Tran, and Alessandro Sperduti. Pre-training graph neural networks with kernels, 2018.
Carl O Pabo, Ezra Peisach, and Robert A Grant. Design and selection of novel cys2his2 zinc finger proteins. Annual review of biochemistry, 70(1):313-340 2001.
10

---

Under review as a conference paper at ICLR 2021
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Graph contrastive coding for graph neural network pre-training. In KDD, 2020.
Bharath Ramsundar, Peter Eastman, Patrick Walters, Vijay Pande, Karl Leswing, and Zhengin Wu. Deep Learning for the Life Sciences. O'Reilly Media, 2019. https: //www. amaz com/ Deep Learning Li fe Sciences Mi Microscppy dp ppp14p/20000 1492039837
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data, 2020.
Falk Schreiber and Henning Schwöbbermeyer. Frequency concepts and pattern detection for the analysis of motifs in networks. In Transactions computational systems biology III, pp. 89- 104. Springer, 2005.
Fan- Yun Sun, Jordan Hoffmaann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization, 2019.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Petar Veličkovié, William Fedus, William L. Hamilton, Pietro Liö, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax, 2018.
Lichen Wang, Bo Zong, Qianqian Ma, Wei Cheng, Jingchao Ni, Wenchao Yu, Yanchi Liu, Dongjin Song, Haifeng Chen, and Yun Fu. Inductive and unsupervised representation learning on graph structured objects. In International Conference on Learning Representations, 2020. URL
https://epeerevieee net lttee/orrrmmimieeeeeemeeeeee
Sebastian Wernicke. Efficient detection of network motifs. IEEE/ACM transactions on computa-
tional biology and bioinformatics, 3(4):347-359, 2006.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arKiv preprint arXiv:1810.00822, 2018.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374, 2015.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Gen- erating explanations for graph neural networks, 2019.
Asano YM., Rupprecht C., and Vedaldi A. Self-labelling via simultaneous clustering and represen- tation learning. In International Conference Learning Representations (ICLR), 2020.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.

---

Under review as a conference paper at ICLR 2021
A PSEUDOCODE OF THE MAIN ALGORITHM
temparature parameters: tau tau
2 # weight parameters: lamb_", lamo_s, Tamb_s
model Mot! f (arga) à modell concafin a'l motif vectors, model, .ootiife encoder GNNiarge) A GNN encodez for pretzaining
7 for in loader:
sampla subgrapha from each whole graph and the node Indices of these subgrapha =>
9
been sampled retuzn many subgraphs
whole graph => nun sum_subs
12
compute the node nede affinity matrix & return the of affinity of nodes within each subgraph sum_A E: list of len N, nun_aubs: M 4, aun_A: 8 num_auba, sun_A segnenter (G, encodar)
16
encode input graph get embeddings encoder (S)
18
pool all node enbeddings together for the whole graph embedding zggregate (n, 5) M.X.X
23
pool nodes belong to the subgraph for the aubgraph enbedding aggregate (n, 5,
compute motif-subgraph similarity
28
with gorch.no_gradd):
30
compute similaricy threshold eta as the top 108 for each motie S_top10, - tk 10.1 s.shape dim=l1 + eta s_top10(:, -1] K 1
32
q sinkhorn (8) use the Sinkhorn-Kropp algorithm to solve for 0,
35
Identy whether subgraph is similar enough to moti?
S_aask etal sum (dim=00)
37
compute sampler loas los8_a sum_A[S_mask)
40
normal
42
S_tilde torch, (8 Lau_g, din=0) # K
44
compute notif learning loss
loas_m (0 l_ti log (..sm.smmm (étmm=))) mean I)
compute pairwise similarities between each
graph enbeddings subgraph enbeddings
49
K terch.softmas (psirvise_cosine__eee coseess__ooieeesmth #)/ Lau_g, dim-1)
compute the contrastiva loss
blocks [torch. (1, int (n) for n. num_subs]
R_aask terch.
loss_e (K mask
1o (1) (om .eman))
56
final loss Lamb_melesa.. lamb_cvloss_c iamb
58
def Begmenter encodez):
with torch.no_grad(j)
63
num_subs = !]
sum []
for G_ in 6:
F encode the input gzaph get node enbeddings ee_))
68
affinity matrix A tarch. wpwirwise_cocsieeeeooooeeeeeeeee
compute
70
n) tau_a, dim=l)
é apply spectral clustering and find connected componenta
f to segment subgraphs, I_ is a list
wlw.tleessstttteneeee (A_i)
75
node indices subgraphs
I +2 1
12

---

Under review as a conference paper at ICLR 2021
many subgrapha are sampled mun_auba += [1en [T_]
graph
80
the of affinity values of nodes within each subgraph SuR + MAL [index] [ty Index]].ee s) for index in 1_11
85
return T, num_subs, aum_A
87
der sinkhozn nun_iters=,, 1amb=20);
1mp ementetion of the sinkhorn function adopted from
https://gtthub.com
92
torch.no_graat
torch.ene exp .3).t.)
/- terch. sum (Q)
torch. wQ..aapeep)) [31) .0o (Q.device))
97
torch. shape (0]) to (Q.devica) / s.shape (0]
torch.ones @has [1]) (o. c. O.
99
curr_sum
(Q, dim=1)
101
Ioz it in range inun_itss::
102
u. cuzr_sum
/ .unsqueeze
104
0 (a / torch. (O, dim=C)) .unssueeeue (0)
curr_aum
din-1)
106
return (2 / torch. torch.aun(Q. dim=O, kespdim=Tuue) .t. .
13

---

Under review as a conference paper at ICLR 2021
B
NOTATION SUMMARY
Below, we summary the important notations and symbols used paper in the order they appeared.
Graph level
M
Total number whole graphs
Gi
Whole graphs Whole graph embeddings
h;
Subgraph level
N
Total number of subgraphs Subgraphs Subgraph embeddings
9j
Cj
Node level
74
Node embedding
A
Node affinity matrix, n-by-n dimensional for whole graph with nodes Node affinity between node and node in a graph
A(
I
Indices of nodes forming a subgraph selected by the Motif guided Segmenter
Motifs
K
Number of motifs
m, my
Motif vectors
s
Similarities between all K motifs and all N subgraphs, K-by-N dimensional
Similarities between all motifs and the subgraph j. K-by-1 dimensional
Sk.
Similarity between the motif k and the subgraph j. scalar Normalized similarity between the motif k and the subgraph j Motif-based cluster assignment matrix, K-by-N dimensional Motif-based cluster assignment of subgraph j. I-by-N dimensional Threshold for deciding whether subgraph similar enough to motif
5kJ
Q
gi
Contrastive
W
Normalized similarities between M graphs and N subgraphs, M-by-N dimensional Normalized similarities between graph and subgraph
Wij
Others
Tn
Temperature for the softmax normalization of node-node similarity Temperature for the softmax of motif-subgrap and graph-subgrape similarity
Tg
E(-)
GNN encoder used to generate node embeddings and (sub)graph embeddings Dimension of node embeddings, (sub)graph embeddings, and motif vectors
D
C
TOP K CLOSESET SUBGRAPHS TO LEARNED MOTIFS
Examples of first 10 learned motifs of the ogbg-molhiv dataset shown in Figure and
14

---

Under review as a conference paper at ICLR 2021
OHZ
GH2
0H2
H2C
0H2
H2O
NHH
H20
oRe
NIB
5H2
GH2
MB
Ne-3
180
2020022
CH2
OH2
Figure 4: (Figure updated to higher resolution) Motif 1-3, represented by top k closest subgraphs the learned motif representations. Each row represents a motif, represented by some subgraphs that is closest to these motifs. Three columns indicates top I, top 2, and top 3 most similar subgraph respectively.
1P0
OH2
N++2
OH2
OH2
NHH
CH
CH
OH2
NH3
NH3
OH2
OHZ
NH3- NHH
H2O
NHD
AH3
NP-3
1813
Figure 5: (Figure updated to higher resolution) Motif 6-10. represented by top k closest subgraphs to the learned motif representations. Each row represents a motif, represented by some subgraphs that is closest these motifs. Three columns indicates top top 2, and top most similar subgraph respectively.
15

---

Under review as a conference paper at ICLR 2021
D SAMPLING STRATEGIES AND SAMPLED SUBGRAPHS
Here describe the details of our heuristic sampling strategies.
For random walk, we use random walk length uniform [10, 40). Starting from a randomly selected seed node, randomly select its neighborhood next hop, until reaching the walk length threshold.
For K K-hop neighbors, pick hop number & to be or 2 with equal probability. Starting randomly selected seed node, we collect the neighbors within & hop as the sampled subgraph.
We also shows some subgraph examples generated by these two heuristic strategies and our proposed motif-guided subgraph segmenter in Figure From the sampled subgraphs, we can see that random walk is more likely generate chains, while k-hop sampling more likely to generate half part of a Benzene ring. Neither of these two heuristic approaches can successfully generate a complete and clean functional group, and the generated subgraphs are not that meaningful. On the contrary, our motif-guided sampler can succssfully generate a complete benzene ring and two other molecule substructures. This intuitively explains why the graph-to-subgraph contrastive learning can only work with our proposed subgraph segmenter.
Motif-guided samples
N+2
Original whole graph
BHH
H2D
Random walk samples
NH1
HBr
K-hop neighbor samples
1843
Figure 6: (Figure updated to higher resolution) Comparison between different sampling strategies. The original graph is shown the left. Samples produced by three different sampling strategies shown on the right. The top row shows the samples by our motif motif-guided guided segmenter. The following two rows corresponding random walk samples and k-hop samples.
E CHEMICAL PROPERTY PREDICTION BENCHMARKS
In experiments, evaluated model performance seven Open Graph Benchmark (OGB) molecule property prediction datasets. We provide a synopsis of each downstream task dataset from Hu et al. (2020b below:
bace: Qualitative binding results for set of inhibitors of human 3-secretase 1.
bbbp: Blood-brain barrier penetration (membrane permeability).
clintox: Qualitative data classifying drugs approved by the FDA and those that have failed clinical trials for toxicity reasons.
hiv: Experimentally measured abilities inhibit HIV replication.
16

---

Under review as a conference paper at ICLR 2021
Dataset
bace
bbbp
clintox
hiv
sider
tox21
toxcast
graphs
1513
2039
1477
41127
1427
7831
8576
nodes
51577
49068
38637
1049163
48006
145459
161088
edges
111536
105842
82372
2259376
100912
302190
161088
# tasks
2
27
12
617
Table 5: Statistics number of graphs, nodes, edges, and tasks in each OGB molecule dataset.
sider:
Database of marketed drugs and adverse drug reactions (ADR), grouped into 27 system organ classes.
tox21:
Toxicity data on 12 biological targets, including nuclear receptors and stress sponse pathways.
toxcast: Toxicology measurements based on over 600 in vitro high-throughput screenings.
Table summarizes important statisties of the OGB molecule datasets related to the number of graphs, the size of graphs, and number of properties that require prediction for each molecule. For these datasets, there are 9-dimensional node features including atomic number, chirality, and etc. There are also 3-dimensional edge features including bond type, bond stereochemistry, and an additional bond feature indicating whether the bond conjugated. For further information on the OGB datasets, please refer to Hu et al. (2020b) and Hu et al. (2020a).
F HYPERPARAMETERS AND MODEL CONFIGURATION
we used for running our experiments. We use the same hyperparame- ters, hidden layers and 300 hidden dimension, recommended in Li al, (2020) for all DeeperGCN models. We pre-train our model using Adam optimizer for 100 epochs, with batch size (number of graphs per batch) 512. For fine-tuning, train the model for 100 epochs with batch size 32. We lect model with highest validation result and report its test result. Corresponding experiment results are shown in Section
We show the
The parameters for running context prediction baseline is shown in Table 6 experiments of ContextPred with different parameters in Table
We show additional
Context represent mode
cbow
Context pooling
mean
Negative sample ratio
1
Context size
3
rl
4
r2
7
Table 6: Hyper-paramettrs of the context prediction pretraining
bace 73.55 4 2.5
bbbp
chintox
hiv
sider
tox21
toxcast
Average
rl=2, 12-5
81.7 + 2.84
75.82 4.11
73.79 0.9
54.98
1.48
75.6 + 0.78
63,88 + 0.76
71.33
r133, 12=4
2.32
63.53
70.55
Table 7:
Additional experiments for ContextPred with different parameters r. Note: results shown in Section are with rl = and r2 =
G MOTIF CLUSTER SIZE DISTRIBUTION
In Figure 7 we show the distribution cluster sizes of all the learned motifs, Although with the equal-size constraint, the distribution is not completely uniform.
17

---

Under review as a conference paper at ICLR 2021
Normalized Cluters Sizes of The Learned Motifs
cor
Cluster Sizes
Mobif
Figure 7: Distribution of cluster sizes of all the learned motifs
H VISUALIZING SIMILARITIES
In this section, we visualize the similarity scores between the learned graph and subgraph represen- tations. In particular, we consider whole graph G1 within batch of graphs {G..... GD ). and three different subgraphs 91, and 93 sampled from G1.
we visualize the distribution of pairwise cosine similarity between all graph-motif- assignment vectors dj, Here each a, is associated with a graph G; with N, subgraphs . NN,, It K-dimensional vector representing which motif the graph 93 contains. We compute a; by aggregating the corresponding normalized subgr-h similarities S as the following.
In Figure 8
Σ
$.
(10)
N
EG.
This distribution in Figure 8 is over the pairwise cosine similarities of all aj's in the batch. In this case, only 8.7% of these pairwise cosine similarities are higher than 0.5, and only 1.7% higher than 0.9, which shows the graph dataset is well distributed and contains diverse whole graphs. It is relatively uncommon for whole graphs to share many subgraphs.
In Figure sampled from the whole batch of graphs {GI,.., GB). We see that the distribution is centered around O, with maximum roughly equal 0.6.
visualize the distribution of similarity scores between G1 and all the subgraphs
In Figure 10 we visualize similarity scores between Gi and 9l, 92. and g3, and we zoom in to each dimension. The similarity score scores are 0.6026, 0.6020, and 0.4786 respectively. which are significantly higher than subgraphs sampled from other whole graphs as shown in Figure g To figure out how we got these high scores, we can zoom into each dimension. In other words, we check the elementwise product of the 300-dimensional graph and subgraph representation vectors, without summing these 300 number together. We find that the three distribution corresponding to these subgraphs look very different, which indicates these three subgraph representations activate different dimensions of the multi-view whole graph representation. In other words, they are only similar to the projection of the whole graph representation on different basis.
is cosine similarity. In this case, the cosine similarity
In Figure we further show that pairwise similarity scores between these three subgraphs ø1 92. and g3. which are not very high. This verifies our claim in Figure I0
In Figure 12 we show the pairwise similarity scores between the first 30 subgraphs sampled from (G1..., BBF- We see that even though these subgraphs are listed in order, i.e. 91. Is are from G1 I1. 95 from G2, ...9 are from G3. and etc, similarity scores roughly uniform. In other words, this heat matrix is not strictly block diagonal, indicating subgraphs from the same whole graph do not necessarily have high similarities among them.
18

---

Under review as a conference paper at ICLR 2021
35
20
5-
02
0.4
0.6
0.8
10
Figure 8: Pairwise similarity scores of all graph-motti-assiggment vectors 01,-.. aB
35
3.0
25
20
15
05
0.0
-0.4
-0.2
0.0
0.2
0.4
0.6
Figure 9: Distribution of similarity scores between the whole graph G and all the subgraphs
I LINEAR EVALUATION IN ACCURACY
We show the linear evaluation result in accuracy of our model and the baselines in Table ??. Note that the results tables in Section are in AUC-ROC rather than accuracy.
SSL methods
bace
hbbp
clintox
hiv
sider
tox21
loxcast
Average
ContextPred
57.13 0.55
80.58 1. 0.21
93.03
0.00
96.49
0.00
75.35
0.08
92.21 1 0.01
83.68 1 0.02
82.64
InfoGraph
GPT-GNN
59.33 0.26
73.82
2.06
93.01 + 0.07
94,16
3.06
70.86 86
0.34
88.60
+ 0.26
81.20
0.12
80.14
MIcRO-Graph
76.49 0.25 85.44 0.20 93.01
0.05
94.49
0.00
75.82 0.00 92.74
0.00 84.24
0.05
86.32
Table 8: Feature extraction performance (ACC) of MICRO-Graph compared with other self- supervised learning (SSL) baselines molecule property prediction benchmarks. Use pre- trainedmodels to extract graph representations for each data and train linear classifiers on top. Run eachexperiment 5 times
J A SYNTHETIC DATASET TO STUDY MOTIF LEARNING
In addition to studying the pre- pre-training in chemical domain, also construct synthetic dataset to that align with our assumptions to verify the effectiveness of the propose method. We assume there exist K graph motifs, and each whole graph be representated by certain combinations of
19

---

Under review as a conference paper at ICLR 2021
graph-subgraph similarit
0.6026
m
Mt
sul
A
U.dda M
0.6020
L.
1ul qta. R.y
1.
siillry
50
100
150
200
250
300
Mb,
0.4786
100
150
dimension
Figure 10: Similarity between the whole graph &1 and three subgraphs I1. 92, and gs. zoom to each dimension. For each row, x-axis is the dimension slot 1 to 300, and y-axis is the similarity scores between corresponding dimensions of the whole graph representation and each subgraph representation. We indicate the top 20 scores in orange. We can that these three subgraphs have very different similarity score distributions, though summing over all 300 dimensions give alike high scores.
DH
0.12
0.19
0.12
1
0.016
0.19
0.016
Figure 11: Pairwise similarity scores between subgraphs Ø1, G2. and gs
these motifs. Following this rule, we first select some graph structures motifs, and randomly sample some combinations, and generate graphs (as is illustrated in Figure [3] by combining the motifs, with some randomly added deleted nodes and edges. Each graph will also be assigned a corresponding one-hot vector label, whose dimension the total number combinations we generated for the dataset. Eight subgraph templates and examples of generated whole graphs shown below. As is illustrated Figure 14 our MICRO-Graph can successfully learn the underlying graph motifs and templates without any annotations.
The advantage of constructing such synthetic dataset is that we can know the underlying ground- truth of graph motifs and combination rules. We believe top of this toy dataset, more complex
20

---

Under review as a conference paper at ICLR 2021
0.75
-050
0.5
Figure 12: Pairwise similarity scores between the first 30 subgraphs sampled from
syntax and semantic knowledge can be incorporated for automatic motif and even rule mining com- munities.
1
2
Figure 13: Example of synthetic graph. The upper 8 graphs are the base motifs, and we generate this graph with combination [2, 4, 7J. Different colors represent different node features.
21

---

Under review as a conference paper at ICLR 2021
Eight motifs
Subgraphs closest to the ten learned motif representations
Figure 14: Comparison of the eight motifs used to generate the synthetic dataset and subgraphs closest to the ten learned motif representations
22


Reviews:
[{"review_id": "yLFufmHivc9", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "==========Summary==========\n\nIn this work, the authors study how to leverage motif discovery to learn graph representations. MICRO-Graph is proposed to enable simultaneous motif discovery and graph representation learning. Empirical results on public benchmark datasets suggest the effectiveness of the proposed method.\n\n==========Reason for the rating==========\n\nAt this moment, I am leaning to reject. Overall, the technical quality is my main concern. This paper's presentation also makes its technical details confusing. Hopefully, the authors could address my concern in the rebuttal.  \n\n==========Strong points==========\n\n1. The authors investigate the problem of graph learning from a unique angle of motif discovery.\n\n2. The authors propose the MICRO-Graph framework that enables simultaneous motif discovery and graph representation learning.\n\n3. From multiple public benchmark datasets, the empirical results suggest the proposed technique could be promising in graph classification tasks.\n\n==========Weak points==========\n\n1. My major concern is on the technical quality of this paper. \n    - Graph representations generated by a node embedding system may not be comparable across different graphs. A node embedding system is assumed to be available in MICRO-Graph. In most cases, a node embedding system is trained in an unsupervised manner. The generated node representations usually only work in a transductive setting such that the learned model may not be able to be generalized for unseen graphs. In other words, node embedding from different graphs may not be comparable in a meaningful way, although they are vectors of numerical values. For the input node representations, the authors may need to clarify how the node representations are obtained, and why they are comparable across different graphs.\n    - The authors may need to clarify whether MICRO-Graph could tune the parameters in the assumed node embedding system. If the parameters in the embedding system are trainable, the authors may need to discuss more on the assumed embedding system and how the parameters impact node representations. If the parameters in the embedding system are fixed, the subgraph segmenter basically generates fixed subgraphs by spectral clustering, and it is difficult to see the point of Equation (6). In sum, without clarification, the technical discussion is confusing.  \n    - For the motif discovery discussed in 3.2, it seems to be a typical clustering problem. The authors may need to clarify what the unique aspect is in the proposed method.\n    - For the discussion in 3.4, it is hard to see why it is reasonable to use subgraph relations to define positive/negative sets, as the difference between a graph and its subgraph could be significant in many cases.\n    - In section 4.1.1, the term \"fine-tune\" is mentioned. Could the authors provide more details on fine-tuning?  \n\n2. It is still unclear how motif discovery impacts graph representations. As graph representations are the mean over node representations, the coupling between motif discovery and graph representations seems to be weak. \n\n3. The empirical evaluation could be stronger. \n    - For the evaluation in Table 1, \"direct supervised learning\" should consider existing GNN techniques, such as GraphSage, GAT, GIN, and so on.\n    - For the assumed node embedding system, the authors may evaluate how different node embedding systems impact the proposed method.\n\nIn addition, the symbol usage in the presentation makes the paper hard to read.\n\n==========Questions during rebuttal period==========\n\nPlease address and clarify the weak points above. \n\n==========Post rebuttal==========\n\nI appreciate the authors' great effort on answering my questions. The response clears many confusing points from the original draft. Meanwhile, I still have concerns on how the idea of contrastive learning is handled in this paper, which could have been better shaped. In sum, I have increased the rating accordingly.", "extra_scores": {}, "extra_text": {}}, {"review_id": "vjTvAwFoJCb", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Paper Summary\n\nThe paper describes a self-supervised framework to extract graph motifs and use them as input for downstream contrastive learning. The framework contains three components: (a) motif guided segmenter to derive node subgraphs, (b) a motif learning - a clustering task among the subgraphs to identify concrete graph motifs and (c) contrastive learner for downstream graph tasks. The global objective is defined as the sum of the likelihoods of the three components.  The framework is evaluated using from a large scale chemical compound graph dataset. The evaluation is performed for both transfer learning and utility of extracted features and outperforms the tested competing methods. \n\n\nPositives:\n* The framework presented to identity graph motifs and then use of learned motifs in contrastive learning for graph representations is very interesting and does lead to substantial gains in performance at least in the datasets tested \n* Experimental design to evaluate the framework is well thought too to specifically test the different pieces and components. \n* The results with synthetic dataset was a nice addition and a more thorough treatment with quantification of results, particularly recovery of true motifs would be a good addition. \n* The paper is generally well written. An algorithm/pseudo-code in the supplement would have made it even easier to follow given the many moving pieces. \n\n\nConcerns\n* A concern is that the motif learner enforces all clusters to be have similar size. I do not think this is a very realistic assumption in real world datasets. \n* The authors should provide some commentary on how the number of clusters used for spectral clustering and what their impact is on downstream results are \n* The whole graph embedding on Page 5 uses an average of all node embeddings for the graph. Does this put a limit on the size of the graph itself for the framework to work? If the graph is large, the average node embedding is probably not an accurate representation for the graph ? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "XjCArg7jnUa", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall:\nThis paper proposes an interesting framework \n+ It extracts subgraph(s) for each graph from node affinity matrix and spectral clustering, together with the help of motifs.\n+ It learns the motifs by clustering the subgraphs.\n+ It applies contrastive self-supervised learning on the graph-subgraph pair.\n+ It overcomes the combinatorial problem by learning the motifs on the continuous representation space.\n\nStrengths:\n+ The idea is novel and seems promising.\n+ This paper is technically correct.\n+ Nice visualization of the learned motifs.\n\nWeaknesses:\n+ This paper is not well written, especially the notations. I list the main concerns here, and hope the authors can help clarify them later.\n1. S3, N is not defined, and M is defined as #graph. But some following sections are implying N as #graph and M as #subgraph.\n2. S3.2, should be '... we can extract M subgraphs …'\n3. S3.2, according to 'sampling a subgraph from a graph', does this mean each graph has one and only one subgraph?\n4. S3.2, ‘... apply the subgraph index as a mask to its subgraph embedding …’ I can understand the following equation but not this sentence.\n5. S3.2, should be '{..., m_K}'\n6. Actually without clarifying the above detailed notations, it’s a little hard to follow the remaining (sub)sections. e.g., what are S and Q? Because M is #subgraph, and it should be [..., S_M] and [..., q_M] according to the descriptions.\n7. S3.3, {g_{i,j}}_{j=1}^M, I guess this is saying each graph can have multiple groups/subgraphs and such mapping is represented in the N*M binary matrix. Then it contradicts with the (3) mentioned above, with 1-1 mapping between the two views.\n8. In Eq 5, not sure if softmax_s matches with the description above. \n9. In Eq 6, it would be better to add ‘1 \\le k \\le K’ in the last term.\n+ Experiments, authors can consider adding more baselines.\n1. GROVER [1] is the SOTA, where it randomly masks a subgraph, which is highly relevant to this paper.\n2. GNNExplainer [2] is learning the motif in an end-to-end way, the authors could also consider comparing with it.\n\nRecommendation:\nConsidering the notation issues listed above and lack of baselines, I would encourage the authors to polish up this paper. It has the potential to be a much better paper. For now, I would reject the current version.\n\nQuestions:\n+ OGB[3] was first released in May 2020, and GROVER[1] was released one month after that. So I think at least the authors should cite [1].\n+ In S1, ‘Previous approaches, such as …’ Deep Graph Informax and InforGraph, in the last layer it is indeed node-to-graph views, but if we take it under the GNN setting, where each node representation in the last layer actually encodes a K-hop neighborhood around that node, then it is subgraph-to-graph views.\n+ The ContextPred in Figure 2 is not correct: it should be contrasting the k-hop neighborhood and pre-defined context graph. Check Figure 2 in [4].\n+ In Table 1, the ContextPred is the worst, which is not expected based on my own experience, any reason why? I couldn’t find it in the supplementary files.\n+ Comparing Table 1 and 2, the frozen pre-trained GNN seems to be much better to the fine-tuning ones. Can authors discuss this further?\n+ Figure 3 to 6 are blurry.\n\n\n[1] https://arxiv.org/abs/2007.02835\n\n[2] https://arxiv.org/abs/1903.03894\n\n[3] https://arxiv.org/abs/2005.00687\n\n[4] https://arxiv.org/abs/1905.12265\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "I2JdYsSoOYA", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to learn the sub-graph patterns from a collection of training graphs. The key idea is to partition each graph into segments and enforce a global clustering of the subgraphs. The partitioning is also guided through contrastive learning, i.e., subgraphs should have a larger similarity with the graph it is drawn from, compared with other graphs. The learned GNN (that generates node embedding) will then be used to some downstream learning tasks with or without further fine-tuning. \n\nThe notation of the paper is very hard to follow. For example, no where is N defined, which I assume is the number of sug-graphs. Capital latters S_i’s represent vector (not sure if my guess is correct), as lower-case letter q_j’s, which somewhat affects the reading. Also the definition of n_i, and n_{i,s} is not quite following the custom of matrices. Furthermore, what is the relation between s_i and S_i (both board), and what is the difference between S (bold) and S (not bold)? The h_i is defined but not used, and in equation (7) g_i is used, which I assume is the summary embedding vector for graph G_i; in (7) s_i seems to be subgraph embedding vector, and this makes me more confused about the s_{j,k} appearing in the beginning of section 3.2 which is defined as the cosine similarity between subgraph j and motif k. The E[G_i] is with bold E somewhere and non-bold letter E elsewhere. Altogether, there are S (bold), S(not bold), s_{j,k} (bold) that seems to be a similarity measure, and s_i (bold) which seems to represent subgraph vector. It’s quite confusing to me. Can authors clearly define these symbols when they are used, and make sure they are consistent throughout the paper, and explicitly mark their dimensionality to avoid confusion? Usually upper-case letters are for matrices and lower-case bold letters for vectors.  \n\nThe idea of partitioning graphs into sub-graphs are a useful idea in breaking the complexity of graph-structured objects and exploring the potential hierarchical organizations of the graph. Using contrastive learning as a self-supervision may further improve the partitioning of each graph. However, the grouping part and the contrastive part may conflict with each other in that some sub-graphs are shared among different graphs, which can be quite common in chemical compounds. \nUnder (5), it is mentioned that spectral clustering is used to partition the graphs; is it done end-to-end and if so where is the loss function corresponding to this operation?\n\nIn (6), (s,t) in g(i,j): What is g(i,j) in particular? a threshold eta is used in the indicator function and how to choose eta (considering that it is used directly on a set of variables)? Is (6) end-to-end optimizable?     \n\nIn Figure~2, what is meant by the blue and red markers (like + and -)?\n\nExperimental results are quite strange in that the transfer learning setting (which further finetunes the learned GNN based on a small set of labels, as in Table 1) leads to even worse performance than the feature extraction setting (in which no fine-tuning is performance, as shown in Table2) and the gap can be as huge as 15% in accuracy!  \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a pre-training strategy for learning graph representations using a graph-to-subgraph contrastive learning objective that also simultaneously discovers motifs. Pre-training for graph representation learning is an important research topic and this work presents a unique solution leveraging the fact that graphs sharing a lot of motifs should be similar to one another. The approach is novel and interesting, the ability to simultaneously identify motifs are highly desirable. The results are promising showing that the proposed approach, when pretrained on the ogbn-molhiv molecule dataset, worked well for several downstream chemical property prediction tasks. 

However, the paper is not without weaknesses and the reviewers noticed several of them. There are many parts of the system, the graph segmenter, which relies on spectral clustering (on the affinity matrix), the EM style clustering component to extract the motifs based on the subgraphs,  the sampling loss based on the subgraph-to-motif similarity, and the graph-to-subgraph contrastive learning loss. These parts are tied together through different mechanisms and the training procedure becomes very confusing. It is unclear which parts are updated on the backpropagation path from which loss, and what choices are decided offline (i.e., not integrated into the backpropagation).  This presents great difficulty in understanding and probably using /building-on the method. The paper has improved some aspects of its presentation during the review/discussion process, but the training/optimization procedure of the current version still appears quite opaque, and the reviewers heavily relied on the back and forth discussion to understand what is really going on. 

Another concern is that the intuition behind some aspects of the approach and the connections between different components of the approach are a bit difficult to get/digest at places.  The intuition behind graph to subgraph contrastive learning appeared weak to the reviewer. It would be desirable to see a directly comparison to the subgraph-to-subgraph version. The connection between the motif discovery and the representation learning can be somewhat lost as we try to keep the many moving parts straight in the mind.   For these reasons, the paper, in its current form, cannot be accepted.
Decision: Reject