Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper considers the problem of nodes classification with few labeled data and missing graph structures. The proposed solution is expected to infer unobserved graph structure as well as the parameters of the classification model. The main contribution of this paper is proposing adding a denoise autoencoder layer which provides more supervision to the learning. The model compares favorably with other states of art models in several benchmark graph data sets.

Concerns:
1. The experiments assume inputs only contain node features. The solution proposed seems to be incremental under this setting as the problem is a special case of few-shot learning where metric-learning based methods including GNN and denoise autoencoder all have been studied before. See [1], [2], [3]. Further discussion of related works is necessary.

2. The proposed method seems very heuristic driven without providing further theoretical analysis. It is unclear how and why the self-supervision might help the classification learning task. Figure 2 gives a negative example of the existing method but it does not explain why the proposed method could make a difference.

3. How does the proposed model compare with regular GNN/GCN models if edges are not entirely missing? The scope of the paper will be limited if it doesn’t work well when graph data is noisy but not entirely missing.

Reference
[1] https://arxiv.org/abs/1905.01102
[2] http://www.cs.toronto.edu/~gkoch/files/msc-thesis.pdf
[3] https://arxiv.org/abs/1711.04043

review_title: Official review

final_score: rating: 7: Good paper, accept
review_content: The paper proposes a way to use self-supervision with denoising autoencoders to improve learning of the graph structure for GNNs. The approach is compared with a number of recent approaches from the literature.

The approach addresses the highly relevant problem of learning graph structure with GNNs. The paper is well written, with clear motivation and an informative summary of similar prior works. The differences with respect to these approaches, primarily the self-supervised aspects, are clearly pointed out.

There are a few prior works covering self-supervision with GNNs that are all quite new [1-3]. It would strengthen the manuscript if these works were discussed in relation to this work. However, consider how new they all are it is not surprising that they were not mentioned.


Quality
- While the originality is perhaps not big, the work is thorough and well written. There is a substantial experimental comparison with relevant prior work and the conclusions seems to be substantiated.

Clarity
- The paper is well written and easy to understand. I would have liked a little more details and explanation on the MLP-kNN aspects.

Originality
- Self-supervision seems to be the topic of a lot of papers lately, so in that respect, this work is perhaps not the most original.

Significance
- I am not aware of similar works and the results are convincing, so I guess the approach could have reasonable influence on the field.

[1] Jin, Wei, et al. "Self-supervised learning on graphs: Deep insights and new direction." arXiv preprint arXiv:2006.10141 (2020).
[2] You, Yuning, et al. "When Does Self-Supervision Help Graph Convolutional Networks?." arXiv preprint arXiv:2006.09136 (2020).
[3] Zhu, Qikui, Bo Du, and Pingkun Yan. "Self-supervised Training of Graph Convolutional Networks." arXiv preprint arXiv:2006.02380 (2020)

review_title: Interesting work with convincing results.

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors propose a method for simultaneously learning the graph structure (or a graph generative model) and the parameters of a GNN for node classification. This is a topic of recent interest and highly relevant to the ICLR community. 

The authors propose two different ways for the graph generator. First, a fully parameterized method that outputs a continuous (weighted) adjacency matrix. The second computes a spare k-NN graph based on the input similarities. Using the word “graph generator” or “generative model” is a bit of a misnomer here because both methods are not probabilistic but deterministic. The adjacency matrices output by these “generators” are then made into symmetric and positive matrices (i.e., adjacency matrices for positively weighted undirected graphs). Finally, in addition to the typical supervised loss, the authors also propose an unsupervised loss based on a reconstruction loss. 

First, I like the idea of adding an unsupervised loss and also appreciate the experiments and the results as robust. 

I have a concern about the approach though and perhaps this could be clarified in a conversation here. When you don’t use the MLP-kNN “generator” then the adjacency matrix generated is not sparse at all. But what that means is that you are using (for each node) a fully connected layer. Do you think that the advantage of your method then is in the “adjacency processor step”? When you do use the MLP-kNN, how do you compute the gradients? Is it that you only compute gradients for the edges you selected? In this case you would have lots of edges without “supervision” as you call it. Or are you also obtaining gradients for the edges not selected? In this case, creating the kNN graph is a discrete operation and it is not clear to me how to differentiate through such an operation. Of course, recent proposals have been made for differentiating through kNN but I don’t see any reference or mention of what you are doing here. Could you please elaborate on that? 

Regarding the statements about LDS. First, you write that if two nodes v_i and v_j are not directly connected to any labeled nodes, then the RV between them (the edge) does not receive supervision. The statement (and the text following it) is somewhat misleading for two reasons. 

First, both of the nodes have to be not directly connected. But then in the next sentence you wrote that 80 and 89% of nodes are not directly connected to a labeled node for the standard benchmark graphs. The more appropriate analysis, however, would be to count the number of pairs of nodes where both nodes are not connected to a labelled node. This should also include the validation nodes used for the outer objective in LDS. Also note that LDS doesn’t always use the standard benchmark graphs (it either constructs a k-NN graph where k is a hyperparameter of the method or initializes with a subgraph of the given graph). 

Second, your statement is true for *one* sampled graph. Remember that LDS samples a set of graphs in each iteration. It can happen that, even if there is a pair of nodes where both nodes are not directly connected to a labelled node in one sampled graph, one of these nodes might be connected in a different sample. Indeed, if a sampled edge connecting either v_i or v_j directly to a labelled node leads to a reduction of the loss, the next time said edge is probably more likely to be sampled. This is not to say that self-supervision is not a good idea (I do like the idea) but I’m not sure if your statements about LDS are quite accurate. 

Overall, I think that this paper strength is the proposed self-supervised loss and the experimental evaluation. It is rather weak on the methodology, its presentation, and related  discussion. There are several questions I need to hear your response to. Once these are clarified I'm open to adjust my score accordingly. 

review_title: Self-supervised loss for simultaneously learning structure and parameters for GNN

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:  
This paper proposes to tackle jointly learning graph structures and GNN parameters without accessing the original graph structure. Specifically, the proposed method adopts a self-supervised auxiliary task, i.e., parallel training using the supervision of node labels and a self-supervised task using de-noised auto-encoding. The latent graph structure is generated through a fully-parameterized adjacency matrix or a KNN construction subsequent to passing node features to an MLP. Experimental results and corresponding analyses demonstrate the effectiveness of the proposed model.
  
Pros:  
1. Using self-supervision to guide graph structure learning sounds like an interesting and promising idea.   
2. Most claims are supported by experimental results. Specifically, comparisons with baselines show that the proposed model can alleviate the problems of previous works such as sensitivity to the similarity metric and high-quality initial graph structure, memory problems, etc. Datasets like Wine, 20news, etc., demonstrate the model's validity for tasks without graph structure. Parameter sensitivity and other ablation studies are also conducted.  
3. Overall, the paper is well written and easy to follow.   

Cons:  
1. Some model designs are not entirely clear. For example, based on my understanding, the KNN step is not differentiable, thus the model with MLP-kNN generator cannot be trained end-to-end. The authors may want to detail how to cope with this problem in the training process.  
2. I also have a question regarding the model design regarding the self-supervised loss. If neglecting the supervised part (i.e., GNNc and its loss in Figure 1), the self-supervised part basically tries to reconstruct the original feature from the noisy features using GNN_DAE. In that case, should KNN using initial features be the optimal solution (since GCN is essentially smoothing features and these nodes have the most similar features)? If that is true, I feel that the self-supervision may actually work like a regularizer to the MLP subsequent to KNN.  
3. The experiments show that the symmetrization step is very useful while lacking analysis of why it works. Could the authors provide further exploration in that aspect?  
4. It seems bizarre that only LDS is adopted as the baseline in Table 2 since the codes and datasets are ready. I suggest the authors at least add IDGL, the most competitive baseline in Table 1, into Table 2.   
4. There's little comparison of the learned graph structure with the original one (Figure 3.e only utilize node labels but not the original graph structure). Since the main goal of the paper is to learn GNN and graph structure simultaneously, the learned graph structure is important and should be analyzed empirically. For example, the authors may want to follow previous works to design certain metrics to compare the learned graph structure with the original one, provide some visualizations, or case studies in synthesis graphs.  

Minor:  
1. The complete parameter sensitivity could be added to the supplementary material. For example, I am interested to see how the sensitivity of parameter k for kNN behaves across different datasets with different scales.  
2. Some related works are missing, e.g., [1-3].  

[1] Adaptive Graph Convolutional Neural Networks, AAAI 2018.  
[2] Topology Optimization based Graph Convolutional Network, IJCAI 2019.  
[3] Graph Structure Learning for Robust Graph Neural Networks, KDD 2020.  

Overall, though I like the paper in general, I believe the paper could be further improved and thus vote for weakly rejection. I am happy to increase my scores if the authors can address my above concerns.   

review_title: Learning graph structures with SSL sounds interesting in general, but some clarifications of the model design are needed

final_score: rating: 5: Marginally below acceptance threshold
review_content: Graph neural networks (GNNs) have become de facto methods for integrating the input graph structure and node features to learn effective node representations. However, in some domains (such as brain signals, particle reconstruction, etc.), there is access to only node features (but not the underlying graph structure). Motivated by the fact that GNNs tend to perform poorly in the absence of the graph structure, the paper
1) proposes a self-supervised framework for generating the graph structure,
2) explores the design space of the framework by comparing different graph generation methods,
3) demonstrates the framework's effectiveness on node classification datasets.



##  Pros
+ [Motivation] A strength of the paper is the motivation of the problem. It is well-known that the performance of GNNs is highly sensitive to the quality of the input graph structure. Hence, in domains such as brain signals, particle reconstruction, etc., it is necessary to generate a high-quality graph structure so that GNNs could be effectively leveraged. 
+ [Presentation] The high-level ideas of the paper are easy to read with clear figures and notation.
+ [Relevance] The topic of GNNs has gained increasing attention recently such that a significant portion of the ICLR community should be interested.



## Cons
The main weaknesses of the paper are along the axis of the significance of the contributions. The paper requires thorough discussions / positioning / comparisons with many existing publications in GNN literature. The detailed comments are as follows.
- [Self Supervision] The framework proposed in the paper can be seen as an instance of a general framework for self-supervision proposed in SS-GCN (When Does Self-Supervision Help Graph Convolutional Networks?, In ICML'20). 
- [Self Training] A closely related idea for self-supervision is self-training. The basic idea of self-training is to add high-confident predictions to the training set to increase supervision. The paper should be positioned with (and empirically compare against) self-training-based approaches such as (but not limited to)
i) GAM (Graph Agreement Models for Semi-Supervised Learning, In NeurIPS'19) that can also handle noisy / learn graph structures, 
ii) AdaEdge (Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View, In AAAI'20).
- [Quality] Regarding experiments, the dataset domains (such as citation networks) considered in the paper are those in which the graph structure is known. So, it would be more convincing if the adjacency of the dataset was used as the initial adjacency matrix in the proposed framework. The baselines to compare against would then be models such as SS-GCN, GAM, etc.  
- [Soundness] It is unclear why datasets from domains discussed in the introduction section were not considered in the experiments. These domains include, as listed in the paper, brain signal classification, computer-aided diagnosis, analysis of computer programs, and particle reconstruction.  
- [Clarity] Though the high-level ideas were easy to read, the paper should clearly discuss finer details. In particular, in section 4.1 (paragraph preceding 4.2), the details of adjacency initialisation are hastily mentioned, and it feels like the discussion mixes adjacency and weight matrices up. 
- [Metric Learning] An idea for learning graph structures for GNNs is to learn the underlying similarity metric (rather than use a chosen one). This idea has been used in certain domains of computer vision and natural language processing. The paper should be positioned with relevant publications (albeit for small graphs) including (but not limited to)
i) Few-Shot Learning with Graph Neural Networks, In ICLR'18
ii) Graph Neural Networks with Generated Parameters for Relation Extraction, In ACL'19
review_title: Important problem; contributions are of limited significance

Meta-review: The paper received 5 reviews, one of which had positive feedback. Although there are merits associated with the paper, several concerns raised in the reviews and the discussion period that prevents the paper to be accepted. It appears that experiments on noisy graphs are not properly done and competitive baselines are not used for validations. The quality of the learned graph structure is not adequately analyzed. and the experimental setup was not clearly explained. All these indicate that there is a need for a major revision before the paper can be considered for acceptance.
Decision: Reject