Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
In this work the authors start from the following basic observation, that I will state in terms of binary classification.  In an ideal setting where there exist two labels, the graph structure should be two distinct connected components, and according to the author(s) the most natural choice is that the each component is a clique. However, when one performs semi-supervised learning, edges going across communities over smooth the labels, and especially in the absence of many labeled points this causes big issues in node classification. For this reason the authors assume that the graph is actually a noisy version of some latent graph. They incorporate a variational approach to GCNs, as a novel architecture that iteratively refines the node labels and the graph. Figure 2 nicely summarizes how  the proposed architecture enhances the community structure. Some comments to the authors follow. 


- Could the authors discuss alternative choices to l2 minimization such as the paper Algorithms for Lipschitz Learning on Graphs by Rasmus Kyng et al. at uses Lp-norm minimization as means to avoid over smoothing in a different but super relevant context of label propagation? 
- The authors discuss drop edge. While this is an issue of the DropEdge method, wouldn't it make sense to remove edges that have higher effective resistance instead of random sampling? The latter is more likely to kill intra-edges, instead of the inter-edges that cause the oversmoothing? It would be nice to include such a baseline in the experiments. 
- What happens when instead of having in the ideal setting two connected components that are cliques, there are two bipartite cliques instead?  This would capture a notion of 'heterophily' instead of 'homophile' that naturally creates a clique. Can your method be extended to this case? 
- Can you prove that when the input graph is stochastic block model your method provably results in the right classification? It seems such a claim could be plausible to prove analytically, at least when the gap of intra- vs inter-community edges is large enough. 

review_title: Jointly learning graph and labels

final_score: rating: 6: Marginally above acceptance threshold
review_content: A brief summary of the paper.
This paper proposed a novel architecture termed VEM-GCN to address the over-smoothing problem of GNNs in the node classification task. The main idea is to optimize the graph topology by removing the inter-class edges as well as adding the intra-class edges, and then the noise information would not pass between nodes with different categories. The framework learns with two alternating steps: E-step optimizes the topology while M-step improves the performance of GCN. The experimental results show that the proposed VEM-GCN achieves higher classification accuracy than baseline methods.

Main contributions of the paper.
1.	This paper proposes a joint learning framework for GNN classification model and graph topology, which leverages variational EM as a learning framework.
2.	This paper presents a graph topology learning algorithm based on SBM and neural networks, which employs the node embedding and labels to optimize the topology.
3.	Extensive experiments to demonstrate the performance superior of the proposed method.

Strengths
The strengths of this paper are summarized below,
1.	The proposed method is clearly introduced. Concretely, the theoretical background and the algorithm details are both well defined and written in a clear way. 
2.	The paper is well-organised and well-written.
3.	Extensive experiments are conducted and results analysis are given. The visualization result is intuitive to demonstrate the property of the proposed method.

Weaknesses
The weaknesses of this paper are summarized below,
1.	The main hesitation with this paper is the novelty of the proposed method. Actually, optimizing the graph topology is a hot research direction, and a variety of works are presented about this topic recently. In addition to the AdaEdge, LDS and TO-GCN mentioned in the paper, other works, e.g., "Graph-Revised Convolutional Network" (ECML-PKDD 2020, arxiv: 1911.07123), "Deep Iterative and Adaptive Learning for Graph Neural Networks" (arxiv: 1912.07832), and "Graph Structure Learning for Robust Graph Neural Networks" (arxiv: 2005.10203), also study the same problem. Among them, DIAL-GNN also leverages an iterative and alternating framework to learn GNN and topology, which is similar to this paper. The differences between LDS/AdaEdge and this work are also minor. GRCN and TO-GCN optimize topology and GNN simultaneously in an end-to-end way, which seems more efficient than this work. In summary, the novelty of the presented VEM-GNN is a little bit minor.
2.	A minor concern is about the motivation of this paper. The authors claim that "over-smoothing is caused by "indistinguishable features of nodes in different classes produced by the message passing along inter-class edges", so "adding intra-class edges and removing inter-class edges are helpful to suppress over-smoothing". However, I have a different understanding about the over-smoothing problem. A more common definition (by Li et al., 2018) about over-smoothing is "if a GCN is deep with many convolutional layers, the output features may be oversmoothed and vertices from different clusters may become indistinguishable." In my opinion, the over-smoothing is caused by the depth (or receptive field) of GNN and the message passing manner, but irrelevant to the graph topology. Assuming that we remove all the inter-class edges and connect all the intra-class edges in the graph. In such a situation, when the GNN goes deep, the output embeddings of each node with the same class still become indistinguishable (the embeddings of nodes in the same class will converge to an identical embedding). Maybe we can obtain a perfect classification model by this way, but the embeddings are still failed to represent the property of each node, and they are useless to be applied to other tasks (e.g., anomaly detection). In summary, I agree that topology optimization is beneficial to enhance the node classification performance, but its effect on surpassing over-smoothing is suspicious. 
3.	The impact of each module/design in the proposed framework is not clearly stated. Specifically, a probability matrix $\bar{q}_{\phi}$ is acquired by the learned adjacency matrix <${q}_{\phi}$>, and then the adjacency matrix for GCN is sampled by <$\bar{q}_{\phi}$>. The question is: why don't we define $p=1$ directly to obtain a definite adjacency matrix? Such a design can be viewed as a "DropEdge", so is that the main contribution term for restraining over-smoothing? Authors should add more ablation study to demonstrate the impact of "learned topology" and "probability matrix" respectively.

Correctness and Clarity
The claims and method are well written without significant errors. The paper is well-organised and written in a logical way.

Additional Comments
Here are some additional comments for the authors,
1.	More baselines considering topology optimization should be included, such as GRCN, DIAL-GNN, Pro-GNN (the papers of these methods are mentioned in Weaknesses Section).
2.	It is better to demonstrate how much edges are added/removed since sparsity is an important factor affecting the efficiency of GCN.

review_title: Novelty is limited

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a method to alleviate the over-smoothing problem of GNNs. The key idea is to generate a latent graph structure via leveraging stochastic block model to approximate the observed graph structure and label information. The learned latent graph is expected to have a clear community structure with dense intra-class edges and sparse inter-class edges, so that labels of unlabeled nodes are better predicted based on the latent structure. The whole framework is well designed as an MLE problem, with EBLO solved by an alternate EM style algorithm. Both E-step and M-step are assumed to enhance each other's performance, but this point is not clearly validated in the experiments. Also, it is good to see some discussions on the relationship between the proposed framework and dropedge and adaedge methods. Overall, the idea makes sense in terms of joint topology optimization (via SBM) and node classification. The methodology is designed well as an MLE problem. The paper writes well and the experimental results demonstrate effectiveness to some extent.

The following are some weak points regarding the paper.
1. The method is designed to only handle semi-supervised node classification problem, which may not be flexible enough to be associated with various GNNs for different downstream tasks.
2. The idea of joint topology optimization and node classification is not new. For example, the following work
Zheng et al. Robust Graph Representation Learning via Neural Sparsification. ICML 2020.
deals with a similar problem, and is flexible to different tasks. It is better to compare with it in the experiments. Thus the novelty of the proposed method lies in its incorporation of SBM and community optimization, which is good but not very substantial.
3. Because of the pairwise node link generation via SBM, the complexity of the method may be high. From the paper and the appendix, this point seems not discussed in detail. It is better to provide a clearer comparison between the complexity of the proposed method and some other recent topology optimization methods.
4. It seems the proposed method has many hyperparameters, such as p, epsilon in Eq. (9), S in Eq. (11). It is better to provide a summary about these parameters and how to select them in the experiments.
5. From experimental results table 1, the performance gain of the proposed method is around 1-2% accuracy compared to vanilla GCN. This seems not very significant, especially considering the practice whether it is necessary to cost more computations to achieve such a performance gain. Meanwhile, how much extra time to run the proposed method compared to pure GCN is not clear. Also, it is better to show variance to help understand the statistical significance.
6. From table 2, the accuracy improvement is slightly better than table 1 in the scarce-label setting. But table 3 tells if adding a small amount of labels, the difference between GCN and the proposed method becomes small again, which draws a similar question as toward the results in table 1.

review_title: The paper introduces a method for alleviating the over-smoothing problem of GNNs, which is theoretically designed well but has some practical limitations.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary:

The authors present a method for tackling the problem of over-smoothing in graph convolutional networks. Specifically, this is achieved by explicitly modelling a latent graph which, ideally, would be a graph which connects an observation to all other observations of the same class and no observations of a different class. In practice, there is only an uncertain picture of this latent graph as in many applications the labels must be estimated for unlabelled observations. The authors present an EM variational algorithm for approximating both this latent graph and using it to improve the estimation of a GCN. The authors demonstrate that the proposed method performs favourably on a battery of test against an array of existing methods for solving the node classification problem. 

Strengths:

The paper tackles an important question in the GCN literature, which is how to deal with situations in which the graph is unobserved or the observed graph structure is only a fraction of the true graph. The method proposed, modelling and optimising a latent graph, makes sense and is well justified.  The authors position the paper well in terms of its contributions in relation to previous work. This includes empirical comparisons to a wide array of existing competing methods. The paper is well written and clearly describes the proposed method. 

Weaknesses:
The main weakness of the paper is in the empirical section. Specifically, I would like to seen an expanded Table 2 to include more comparisons with existing methods. From Table 1, I am convinced that VEM-GCN achieves similar performance to existing methods, even if the magnitude of the performance increase is not very large. However, I think the main contribution of the paper in the empirical section is Table 2 and should be the main focus. It clearly demonstrates that the proposed method reduces over-smoothing relative to a vanilla GCN as expected, especially as the depth of the model increases, but I wonder what a similar comparison to the other models in Table 1 would show. Could the authors provide the results of a similar analysis, at least for the models for which this is possible?

Reasons for score:

I vote for accepting the paper. It is a solid, clear, and novel contribution to the literature on GCNs that directly addresses an important consideration in these models that is often overlooked. 

Questions for the rebuttal period:

Please refer to the questions in the weaknesses section. 

review_title: Review of VEM-GCN: Accept

Meta-review: The authors propose a new approach to topology optimization to address over-smoothing in GCNs. This is a borderline paper. Topology optimization is clearly important and relevant and the approach tries to optimize the topology (add/delete edges) by viewing the problem as a latent variable model and aiming to optimize the graph together with the GCN parameters to maximize the likelihood of observed node labels. A number of related joint topology optimization approaches exist, however, as discussed in the reviews and the responses. The proposed methodology is termed variational EM but is a bit heuristic in the sense that E and M steps do not follow a consistent criterion (the direction of KL is flipped between the steps). A number of comparisons are provided with consistent gains though the gains appear relatively small. No error bars are provided despite request to add them to better assess the significance of these results. It remains unclear whether the gains are worth the added complexity. 

Decision: Reject