Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Paper Summary

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


Positives:
* 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 
* Experimental design to evaluate the framework is well thought too to specifically test the different pieces and components. 
* 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. 
* 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. 


Concerns
* 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. 
* 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 
* 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 ? 

review_title: Review for Paper 2787

final_score: rating: 5: Marginally below acceptance threshold
review_content: Overall:
This paper proposes an interesting framework 
+ It extracts subgraph(s) for each graph from node affinity matrix and spectral clustering, together with the help of motifs.
+ It learns the motifs by clustering the subgraphs.
+ It applies contrastive self-supervised learning on the graph-subgraph pair.
+ It overcomes the combinatorial problem by learning the motifs on the continuous representation space.

Strengths:
+ The idea is novel and seems promising.
+ This paper is technically correct.
+ Nice visualization of the learned motifs.

Weaknesses:
+ This paper is not well written, especially the notations. I list the main concerns here, and hope the authors can help clarify them later.
1. S3, N is not defined, and M is defined as #graph. But some following sections are implying N as #graph and M as #subgraph.
2. S3.2, should be '... we can extract M subgraphs …'
3. S3.2, according to 'sampling a subgraph from a graph', does this mean each graph has one and only one subgraph?
4. S3.2, ‘... apply the subgraph index as a mask to its subgraph embedding …’ I can understand the following equation but not this sentence.
5. S3.2, should be '{..., m_K}'
6. 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.
7. 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.
8. In Eq 5, not sure if softmax_s matches with the description above. 
9. In Eq 6, it would be better to add ‘1 \le k \le K’ in the last term.
+ Experiments, authors can consider adding more baselines.
1. GROVER [1] is the SOTA, where it randomly masks a subgraph, which is highly relevant to this paper.
2. GNNExplainer [2] is learning the motif in an end-to-end way, the authors could also consider comparing with it.

Recommendation:
Considering 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.

Questions:
+ 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].
+ 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.
+ 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].
+ 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.
+ 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?
+ Figure 3 to 6 are blurry.


[1] https://arxiv.org/abs/2007.02835

[2] https://arxiv.org/abs/1903.03894

[3] https://arxiv.org/abs/2005.00687

[4] https://arxiv.org/abs/1905.12265


review_title: Review of MICRO

final_score: rating: 5: Marginally below acceptance threshold
review_content: ==========Summary==========

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

==========Reason for the rating==========

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

==========Strong points==========

1. The authors investigate the problem of graph learning from a unique angle of motif discovery.

2. The authors propose the MICRO-Graph framework that enables simultaneous motif discovery and graph representation learning.

3. From multiple public benchmark datasets, the empirical results suggest the proposed technique could be promising in graph classification tasks.

==========Weak points==========

1. My major concern is on the technical quality of this paper. 
    - 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.
    - 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.  
    - 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.
    - 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.
    - In section 4.1.1, the term "fine-tune" is mentioned. Could the authors provide more details on fine-tuning?  

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

3. The empirical evaluation could be stronger. 
    - For the evaluation in Table 1, "direct supervised learning" should consider existing GNN techniques, such as GraphSage, GAT, GIN, and so on.
    - For the assumed node embedding system, the authors may evaluate how different node embedding systems impact the proposed method.

In addition, the symbol usage in the presentation makes the paper hard to read.

==========Questions during rebuttal period==========

Please address and clarify the weak points above. 

==========Post rebuttal==========

I 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.
review_title: Review comments to Paper 2787

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

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

The 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. 
Under (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?

In (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?     

In Figure~2, what is meant by the blue and red markers (like + and -)?

Experimental 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!  

review_title: useful idea but with confusing notations and abnormal experimental results

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