Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary:  The issue of imbalance is a very critical problem in ML, especially in a realistic setting. In general, imbalance is quantitative, but this paper points out topological imbalance as a graph-specific problem. As a solution to topological imbalance, a method of reweighting called ReNode is proposed and its effectiveness is verified.
main_review:  The problem of imbalance is a very real and important issue. The problem of imbalance for graphs has also been studied extensively in recent years. When we talk about imbalance issues, most of us consider quantitative imbalance, but the authors point out the problem of toplological imbalance. This is a very thought-provoking point, and I think it may become an important topic in the future. The authors state that this is a problem specific to graphs, but there may be similar issues with general data in the form of sampling imbalance. The idea of ReNode is relatively simple and the validation is experimental, but I think the results shown are good enough. I think ReNode is affected by the quantitative imbalance and the position of the labeled nodes, but are there any cases where ReNode might make things worse?  It seems to me that if we can see the bounds that the model shows during training, we will be able to adjust the weights better. Is it possible to adjust the weighting during training?
limitations_and_societal_impact: I do not believe that this paper will have any negative impact on society.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studied the problem of imbalanced classification on graphs, by proposing to unify the quantity imbalance and topology imbalance together. The authors develop a label propagation algorithm that locates the topological position of the labeled nodes, and then re-weight nodes to alleviate the imbalanced data distribution. Experimental results on various benchmark datasets show the performance of the proposed model. 
main_review: The paper is easy-to-follow and well-organized. The approach and the solution to the problem are very well handled. Despite this, there lacks some insightful analysis about the proposed approach, and the empirical studies should be further improved. Here are the detailed comments:

[Related work] The idea of using label propagation for imbalance classification on graphs is not novel, such as [1]. The authors may want to re-conduct the literature review in the context of imbalanced classification and discuss the difference between this paper and the previous work.  
[1] https://dl.acm.org/doi/10.1145/3219819.3219968

[Clarity] The authors stated that the imbalance classification problem “roots from the unequal quantity of labeled examples”, which is misleading and vulnerable. In general, in the setting of imbalanced classification, both the labeled set and the unlabeled set exhibit highly skewed data distribution. 

[Technical contribution] The technical contribution of this paper is unclear – both the idea of label propagation and node-reweighting scheme are not novel in the setting of imbalance classification. The authors may want to provide more discussion to show the technical contribution of this paper. 

[Evaluation] In Tab.1, the comparison experiments are conducted on CORA, Citeseer and PubMed, which are standard (balanced) node classification benchmark datasets. I don’t see any reasons why they are considered for imbalanced node classification. Moreover, all of the baselines (GCN, GAT, SGC, SAGE, CHEB) are not designed for imbalanced classification. With these, I doubt the comparison results in Tab.1 are unfair and do not stand. 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper first points out the topology-imbalance problem of node representation learning on graph-structured data. To address the problem (which is denoted as Topology-Imbalance Node Representation Learning, TINL), this paper presents a conflict detection-based metric (named Totoro) based on label propagation algorithm and Personalized PageRank matrix. Then, the authors introduce the ReNode algorithm that considers the Totoro of each node in semi-supervised training of GNN models. The ample experimental results show the superiority of ReNode in addressing the TINL problem. 
main_review: Originality: This paper introduces a novel research problem of semi-supervised node classification on graphs: the topology-imbalance problem. A minor concern is that the proposed solution mostly relies on the existing techniques (label propagation, PPR, and weighted training loss), although the combination of them is reasonable. 

Quality: The paper has good quality. The proposed problem is critical and meaningful in real-world model training. The proposed Totoro metric is highly related to the research problem. The proposed ReNode algorithm is flexible and easy to apply. The experimental results can well evaluate the effectiveness of the proposed method.

Clarity: The paper is well-organized and has a good writing style. The motivation, proposed method, experiments, and analysis are all introduced clearly in the paper. There are some minor problems, e.g. in Equation (3), the definition of P_v is not given very clearly in the paper.

Significance: This paper addresses the topology-imbalance problem in semi-supervised node classification, which is different from most existing works addressing the quantity-imbalance problem. I believe that pointing out this new research problem is significant to the community. The proposed method can well handle the problem, which is proved by the empirical results. 

Problems: I have two further concerns about this paper:
1.Although the performance of the proposed method is validated by experiments, the method lacks a theoretical explanation or boundary to prove its effectiveness. Concretely, the designs of Totoro metric and ReNode method seem experience-based but do not have enough theory to support them.
2.The computation of Totoro and node weights is based on the known labelled nodes, while these labels themselves may be biased due to the topology-imbalance problem. Hence, how to prove that the biased labels would generate unbiased node weights?

Post Rebuttal:
The responses answer my questions, and the authors have revised the paper according to my previous opinions. I do not have further questions. Based on the quality I will remain my rating. 

limitations_and_societal_impact: The authors have addressed the limitation and potential negative societal impact of the paper.
review_title: null

Meta-review: This paper points out and investigates the "topology-imbalance" problem of node representation learning on graph-structured data. Unlike the "quantity-imbalance" problem, the topology imbalance is caused by the topological properties of the labeled nodes, i.e., the locations of the labeled nodes on the graph can influence how information is spread over the entire graph. As it involves the graph topology, the topology imbalance is much harder to quantify than the quantity imbalance. In this work, the authors demonstrate how this issue can impact the semi-supervised node classification based on graph neural networks (GNN). The authors then propose a simple proxy to measure the topology imbalance and re-weighting based method to correct for this imbalance. 

As pointed out by Reviewer 9Atj and t36c, this paper introduces a novel research problem of semi-supervised node classification on graphs, which I consider as a positive aspect of this paper. On the other hand, there are a couple of criticisms on the simplicity of the proposed method and lack of theoretical guarantees (Reviewer 1Cph and t36c). As this problem is previously unknown to the community and the task of solving topology imbalance is non-trivial due to the asymmetry and complexity of the graph topology, I can understand the point that the authors raise in their response: "the main purpose of this work is to reveal the topology imbalance issue to the community". Hence, the simplicity of the proposed method stems from the need to effectively communicate to the community that the problem does exist and the proposed method can be used to solve this problem to certain extent. However, several challenges remain to be addressed to fully alleviate this problem.   

Based on my own evaluation of the paper and reviews of the expert reviewers, I view the introduction of a novel research problem as a major contribution of this paper that will stimulate subsequent works in this direction. Hence, I recommend this paper for acceptance as a poster at NeurIPS2021.
Decision: Accept (Poster)