Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces a MH-style data augmentation to boost the generalization ability of the existing GNNs by generating sequence of augmented graphs. The generation is proven to be converging to the desired target distribution. The experimental results shows a promising result for applying augmented graph during the GNN training. 
main_review: Strength:
1. The paper is easy to follow and proposed methods are both theoretically and empirical sound from the results.

Weakness & Questions:
1. What's the difference of w/o and w/ Reg? Is the only difference on whether have two terms in equation 9? For the DropEdge and AdaEdge baseline, why do you call them "supervision"?
2. What's the main intuition behind the given target distribution at Equation (2)?

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new data augmentation method for Graph Neural Networks based on Markov Chain Monte Carlo sampling and in particular the Metropolis-Hastings algorithm in the context of semi-supervised learning. The main intuition of the paper is to define a target distribution for the whole graph which is representative of the changes in the number of messages that are exchanged in the k-hop neighborhood of each node and then apply the Metropolis-Hastings algorithm for obtaining samples that are representative of this distribution. The experimental section compares the proposed method (MH-Aug) to other recent data augmentation methods showing favorable results w.r.t. the baselines.
main_review: The paper proposes an interesting idea for data augmentation for graph structured data. To the best of my knowledge, this is the first time that the Metropolis-Hastings algorithm is used for sampling variations of an input graph, whose strength can be controlled via hyper-parameters for improving performance of graph neural networks. The experimental section of the paper shows good results for the proposed method, which outperforms the selected baselines in all the considered prediction tasks. 

While I believe the idea presented in the paper is intriguing (and the task for sure of relevance to the community), the paper itself is not particularly well written. The introduction on the Metropolis-Hastings algorithm is rather short and high level and assumes that the reader is already familiar with the details of the method (e.g. the acceptance score of equation 7 is not explained in the paper and it’s given for granted that the reader is knowledgeable of the algorithm). Throughout the paper I personally found confusing the continuous jumps between changes of measures defined at an ego-network and graph level (e.g. equations 2 and 3 are defined for the whole graph G in terms of variations of the ego networks of the nodes of G which are presented after the equations themselves; the sampling function Q of equation 6 is instead defined resorting to the variations of the number of edges / nodes of whole G, which are presented before equation 2 and 3 - reading this section personally felt like reading spaghetti code, where I had to continuously go back and forth to clarify the intent of the authors). Additionally, there are a number of missing definitions that make the understanding of the whole paper rather difficult, in particular:

1) Lines 128/130, this is very unclear, the entropy of the prediction is a scalar at node i, what do the authors mean with standard deviation of the entropy of a target node here?

2) In equation 2 the expected variation is defined wrt the entropy \epsilon_i of the predictions of node i, but this is not defined in the text, what do the authors mean here?

3) Line 164, a and b I believe represent the extremes of the truncated gaussian, however this is not defined at all in the main paper (there are details of this in the supplementary material, but I believe the authors should not rely on that for these sort of fundamental definitions that build the main message of the paper).

4) Lines 177/178, the whole framework is targeted towards semi-supervised learning as the whole graph is modified by equation 6 instead of the single independent ego networks (unless I’m mistaken). Referring to two different training settings, one of which is named “supervised” in the paper is confusing and I would encourage the authors to refactor those lines accordingly.

5) In Figure 3 it’s unclear the meaning of E(\Delta G_i), I believe the authors might intend with this the expected value of \Delta G_i over all possible nodes of the ego network, however this is not detailed in the paper (and if this is correct, I would encourage them to use the classic notation E[.]).

6) Line 237, the meaning of MH-Aug (w/o Reg) is unclear from the paper. Are the authors training on the augmented samples as if they were the original graph here? Please clarify.

7) Lines 253/254, the authors mention the edge drop probabilities are computed from equation 2, however equation 2 determines the similarity of the ego networks w.r.t. the desired variation rather than the probability of an edge being dropped. I would ask the authors to provide more details on this and clarify the computation of those probabilities in the rebuttal.

8) Lines 275/282, the references to Figure 5a and 5b should be swapped.

In light of this, I’m weakly in favor of the acceptance of the paper and I would ask the authors to clarify all the doubts addressed above and refactor the paper accordingly to improve readability.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a data augmentation method for GNNs based on Metropolis-Hastings (MH) sampling  algorithm. The technical method is novel and shown to be effective empirically.
main_review: 
Based on MH algorithm, this paper provides a data augmentation method for training GNNs under semi-supervised setting. Overall, the technical contribution is clear and the empirical study can demonstrate the effectiveness of the proposal.


#######

Pros:

(1) This work forms the data augmentation for graphs as a MCMC sampling process, which is new and potentially insightful to the community.

(2) To utilize MH algorithm for sampling, this work defines reasonable target distribution and proposal distribution, which are the key points that make the proposal work.

(3) The experimental results can show the effectiveness of the proposed data augmentation method. The ablation studies and the visualizations are pretty good for understanding.

########

Cons:

(1) The proposed method is a MCMC-based method, which is assumed to be time-consuming. However, there is no theoretical or/and empirical analysis of the efficiency of the proposed method.

(2) The proposed regularizer terms, especially the term $L_u$, are quite interesting. But the description for this is very limited. For example, since $L_u$ includes model output from both $t$ and $t+1$ steps, more explanation on how to do optimization/back-propagation is necessary.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper proposed to do graph data augmentation with a carefully designed target distribution and the corresponding proposal distribution. The experiments show that the proposed augmentation method can be more effective than existing baselines. During the rebuttal period, all the reviewers found that the authors have effectively resolved their concerns, and are generally positive about the paper. Personally I also like the design of the target distribution which is the key insight of the paper. However none of us are super excited about the outcome, partially due to the significance of the contribution and the potential implication for more general settings. Nevertheless, this paper is a sound contribution in the current scope. No matter of the outcome, we highly encourage the authors to incorporate the additional experiments and clarifications in to the revision of the paper to make it more solid.
Decision: Accept (Poster)