Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper exploring neighborhood memorization problem and proposes a neighbor-aware data augmentation method for node classification task.
main_review: Representation learning for node classification usually has class-imbalance issue. Some labels might cover a few number nodes. This work empirically indicates out that the learned node representations will be influenced by the neighbor label distribution. In particular, those nodes with minor class can have the neighbor memorization problem, that is, the target node's embedding might mainly represent the neighbor nodes but not itself. Empirical analysis in this work supports this claim clearly. Then a data augmentation method based on this observation is proposed. Experiments with class-imbalance setting are conducted to demonstrate the superiority of the proposed augmentation method.

Concerns:
 1. The notations in this work are not easy to follow. Authors use many kinds of symbols like minor, target, seen, or unseen to represent the types of nodes. However, it's very difficult to tell their difference in the manuscript. Could you please explain what's the target node and its difference to the nodes with class? Should the minor nodes be the target nodes? Please check the manuscript again and consider to present the types of nodes in alternative way.

2. It's difficult to draw connection between the proposed method and the solution to address the neighbor memorization problem. We can only see an augmented data by mixing up the node feature and neighbor nodes. Could please explain how to created virtual label for the synthesized node, and why the augmentation method can solve the neighbor memorization problem?

3. Could you please consider baselines which can deal with heterophily network [1]? The neighbor memorization seems to be similar with the definition of heterophily, where the target usually has different labels from the neighbors.

References:
[1] Jiong Zhu et al., Graph neural networks with heterophily, AAAI 2021.
 


summary_of_the_review: This work studies an interesting problem, but the presentation is not clear expressing the motivation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper addresses the class imbalance problem for node classification in a graph and points out some issues faced by existing GNNs and  methods to address the same. It nicely depicts the problem of overfitting to minor classes and neighborhood memorization problem for class imbalance through experiments. It proposes n approach GraphENS which can work with any message passing GNN to resolve the problem of class imbalance for node classification. Experimental results show the merit of the proposed algorithm working with multiple GNNs (GCN, GraphSAGE and GAT) on both synthetically imbalanced dataset and real-world imbalanced dataset for node classification.
main_review: The paper has multiple strong points and few weak points.

Strong points:

1. The paper motivates the problem very well. The experiments in Section 3 show the gap that existing / conventional approaches for class imbalance problem fail to address for graphs. Thus, it shows very well why graph-specific solutions for class imbalance problem are needed.

2. The related work and baselines used for experiments are quite exhaustive to the best of my knowledge.

3. Experimental results are quite promising. They clearly show the merit of the algorithm and its components for imbalanced node classification.

4. The source code is attached (I have not run it though).


Weak Points / Need Clarifications:

1. Though I appreciated the motivation and problem formulation of the paper, the proposed algorithm GraphENS is very heuristic in nature. Different steps of the algorithm, i.e., Neighbor Smapling and Node Mixing do not have a strong objective. I agree that these steps are simple and also intuitive. But what (and how) advantage it is gaining for node classification objective is not clear. It would have been great if some objective / cost function can be formulated and these steps could have been deduced by solving that. At least, authors should give more justification on their need for node classification.

2. Table 1 shows improvement on the manually imbalanced citation datasets. I am curious to see the performance of GraphENS on the original citation datasets. It would be great if authors can compare the performance using GCN, GAT and GraphSAGE with / without GraphENS.

3. What is the training, validation and test size for supervised and semi-supervised learning setup? I also think that "Supervised Learning" task is also a semi-supervised one as it is a GNN based node-level task on a graph. Can authors please clarify that?

4. Figure 1b shows that the gap of performance between all classes and the minor class (around epoch 200) is almost the same for all the algorithms. The training accuracy is also very similar for all classes and the minor class from Figure 1a. Does it mean that overfitting to minor classes is not resolved in graphENS? On a similar note, the gap between blue bar and red bar is almost the same for all the algorithms in Figure 1c. However, GraphENS is doing really well to minimize the gap between blue bar and red bar for the neighbor-replacing experiment in Figure 1d. Can authors comment on this and throw some light on the actual reason for the superior performance of graphENS.
summary_of_the_review: I am still voting for acceptance since the problem motivation and formulation is done very nicely and experimental section is also strong. The proposed algorithm is simple and intuitive, but not that rigorous.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes an imbalanced classification strategy for GNNs. Unlike traditional imbalanced classification, nodes on a graph are dependent on its neighbors, and simply over-sampling/re-weighting the minor class instances would not work. In particular, the authors recognize and analyze the severity of the "neighbor memorization" problem, which is identified as the key cause of overfitting in GNNs.
The proposed method alleviates the neighbor memorization problem by synthesizing ego networks. Extensive experiments are conducted to evaluate the proposed method.
main_review: Strong points:

1. The proposed model is intuitive and technically sound. Neighbour sampling is important in graphs given the neighborhood memorization problem.

2. I like the preliminary analysis on the importance of neighbour sampling, putting the neighbor memorization problem in a quantitative manner (i.e. section 3)

3. Experiments are extensive with strong empirical results.

I only have one main concern:

The target node is picked from a distribution based on the log of the number of nodes in the class, but not much rationale is offered on why this particular distribution is chosen. Is there any guiding principle? Would the model benefit from more elaborately designed distributions?


summary_of_the_review: The paper is well written and technical sound, with strong results.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper investigates the problem of class-imbalanced node classification on graph. To address this, the authors first conduct a case study on a dataset to analyze the underlying reason for inferior performance on minor class nodes. Then a model named GraphENS, which consists of two key components, is proposed to deal with the imbalance issue. Experiments on several datasets show that the proposed model can outperform the baselines.
main_review: However, there are several major concerns in the paper.

1. A case study is conducted to prove the hypothesis that "we hypothesize that it is in fact more serious to overfitting to neighbors of minor nodes than to overfitting to the node feature itself". And this study fundamentally lays the foundation for the following part of this paper. However, there are several issues in this case study.

- (1.1) A benchmark dataset Pubmed is employed to conduct the case study. However, on different datasets, node representations calculated by GNNs may be influenced differently by the node-self features and the neighboring information, due to the distinct characteristics of datasets. Therefore, only employing one dataset here cannot demonstrate the existence of this phenomenon on different datasets with different distributions.

- (1.2) Two traditional baselines are utilized, namely re-weighting and oversampling approaches. However, many advanced approaches are proposed recently to deal with this problem. Only comparing with the most conventional approaches is less convincing to prove this hypothesis. 

- (1.3) In the section of "Overfitting to minor classes", based on Figure 1, a claim is provided that "This result implies that the existing approaches are prone to memorize minor class nodes". However, this conclusion is not quite reasonable. Firstly, the case study only resorts to two conventional approaches, and they cannot represent all the existing approaches (for this problem). Secondly, from Figure 1, we can only observe that "the existing approaches are prone to overfit on minor classes, and the performance (on test) of them on minor classes is not good compared to the proposed GraphENS". Thus, the conclusion is over-claimed to some extent.

- (1.4) In summary of the case study, we can achieve a conclusion that: for a minor node, its neighboring information might provide a larger influence on the performance than its own features. However, it is hard to say: the neighboring information is the key factor to impair the performance of minor nodes. 
Therefore, it seems that the case study cannot comprehensively provide the fundamental basis for the proposed model.


2. In the Introduction, a claim is presented that "Nevertheless, GNNs trained with GraphSMOTE still suffer from neighbor memorization when the number of minor nodes is limited". Why it still suffers from neighbor memorization? More details should be given.


3. The proposed model GraphENS contains two key components, namely neighbors sampling and saliency masking on features. From the main contribution of this paper, we can see that "the neighboring information is the key reason that impairs the performance of minor nodes". However, from the ablation study (Sect 5.4), we can see that, these two components generally have a comparable influence on the performance. The authors should give more explanations.


4. The illustration of Sect 4.1 is a bit confusing, especially the utilized notations. For example, is v_{minor} (or v_{target}) an example node or a group of nodes? 


5. In the Experiments, in order to generate the imbalanced settings on the citation networks, for the minor classes, only two labeled nodes are available for training. The extreme scarcity of minor classes is not a reasonable setting and might import high bias or uncertainty into the experiments, which may damage the persuasiveness of the experiments accordingly, and even the case study.
summary_of_the_review: 1. The case study is not convincing enough to lay the foundation for the model.
2. More details should be given for some confusing points.
review_title: null

Meta-review: Although reviews were initially a little polarized, they trend toward accepting the paper after rebuttal and discussion.

The most negative review raised issues of datasets, baselines, and experiments, and various details that they find confusing. These concerns were not shared by the other reviewers for the most part. Following a detailed rebuttal the most negative reviewer ended up siding with the more positive reviewers.
Decision: Accept (Poster)