Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies structural fairness on graph contrastive learning (GCL). The study is motivated by the finding that GCL is fairer to low degree nodes than GCN. Based on that, the authors first present theoretical analysis on such structural fairness for GCL through intra-community concentration theorem and inter-community scatter theorem. Guided by the theoretical analysis, the authors propose GRADE by enriching the neighborhood of tail nodes and purifying the neighborhood of head nodes. Experimental results on real-world datasets demonstrate the effectiveness of GRADE.
strengths_and_weaknesses: Strengths:
- The paper is well-motivated through empirical experiments.
- The design of the proposed method is inspired from theoretical analysis.
- The proposed method is effective in mitigating structural unfairness as shown by experimental results.

Weaknesses:
Please see below.

questions: - How correlated between the community assignment and the node labels? If there are high correlation between them, enhancing intra-community edges and purifying inter-community edges is an intuitive choice to debias.

- Related to the previous questions, does the theoretical analysis implicitly assume the graph to be of high homophily? What would be the performance on graphs with heterophily?

- For GCN in this paper, does it use the random walk graph Laplacian or the commonly used symmetrically normalized graph Laplacian? 

- How would the theoretical results change if we use the symmetric normalized graph Laplacian (as in original GCN) rather than random walk graph Laplacian?

- What is the \kappa in Theorem 1? 

- (Just some random thoughts) Rather than bringing high-level idea (enhancing intra-community edges and purifying inter-community edges) to methodology design, can we have more insights from the theoretical analysis? For example, is it possible that the bounds for intra-community concentration and inter-community scatter could help us identify what a good augmentation should look like? Then we can sample/augment edges guided by these bounds.

limitations: - More understanding on the performance for graphs with heterophily is needed. 

- There are too many notations in the paper. The authors may want to find a way to organize them so the readers won't need to check notations back and forth.

- The authors should make sure the theorems are self-contained.

- Significance test on the experimental results would be helpful to showcase the effectiveness of GRADE.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: GCN is primarily beneficial to high-degree nodes but biased against low-degree nodes, which causes a performance bottleneck. As a promising paradigm in the graph domain, GCL integrates the power of GCN and contrastive learning, displaying SOTA performance in a variety of tasks. This paper investigates the question of whether will GCL present the same degree of bias as GCN. They surprisingly find out that a smaller performance gap exists between tail nodes and head nodes in GCL methods than that of GCN.

They intuitively and theoretically analyze the reason for this interesting finding. Particularly, Intra-community Concentration Theorem and Inter-community Scatter Theorem prove that node representations learned by GCL conform to a clearer community structure, and establish the relation between graph augmentation and representation concentration. These analyses yield profound insights into solutions to this important degree-bias problem and imply that GCL is a promising direction.

Therefore, they further propose a GRAph contrastive learning for DEgree bias (GRADE) to concentrate augmented representations. Specifically, they enlarge limited neighbors of tail nodes to contain more nodes within the same community and purify head nodes by removing neighbors from a different community. Extensive experiments on various benchmark datasets and several evaluation protocols validate the effectiveness of GRADE.

strengths_and_weaknesses: The paper is well-written in general and their finding is exciting.
Weaknesses:
1.	How to get a small degree of bias from a clear community structure needs more explanations. Theorem 1 and 2 prove that GCL conforms to a clearer community structure via intra-community concentration and inter-community scatter, but its relationship with degree bias is not intuitive enough.
2.	There is some confusion in the theoretical analysis. Why is the supremum in Definition 1 \gamma(\frac{B}{\hat{d}_{\min}^k})^{\frac{1}{2}}? Based on this definition, how to prove that the proposed GRADE reduces this supremum?
3.	There is a lack of significance test in Table 1.
Despite the weaknesses mentioned above, I believe that this paper is worth publishing. They consider an important degree-bias problem in the graph domain, given that node degrees of real-world graphs often follow a long-tailed power-law distribution. And they show an exciting finding that GCL is more stable w.r.t. the degree bias, and give a preliminary explanation for the underlying mechanism. Although the improvement does not seem significant in Table 1, they may inspire more future research on this promising solution.

questions: Q1: How to get a small degree of bias from a clear community structure?
Q2: Why is the supremum in Definition 1 \gamma(\frac{B}{\hat{d}_{\min}^k})^{\frac{1}{2}}? Based on this definition, how to prove that the proposed GRADE reduces this supremum?
Q3: There is a lack of significant test results in Table 1.


limitations: A learnable augmentation is an interesting direction for improvement.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper investigates the great potential of graph contrastive learning to solve the degree-bias problem, and proposes a new graph augmentation for further improvement.
strengths_and_weaknesses: The motivation of this paper is clear. They discover that node representations obtained by GCL methods are fairer to degree bias than those learned by GCN, and explore the underlying cause of this phenomenon. Based on the theoretical analysis, they further propose a novel GCL model targeting the degree bias. Experimental results clearly show the merit of the proposed model, and the source code is attached (I have not run it though).

Concerns:
1. This paper focuses on semi-supervised GCN to motivate their investigation. Do other semi-supervised GNNs suffer from the same severe degree-bias problem? In other words, I doubt the finding is limited.
2. Some simplifications have been made in the theoretical analysis. For example, they only consider the topology augmentation. Does it affect the analysis results?
3. There is only one train-test split in Section 2, but two in Section 5.
4. The complexity of the proposed model.

questions: 1. Do other semi-supervised GNNs suffer from the same severe degree-bias problem?
2. Some simplifications have been made in the theoretical analysis. For example, they only consider topology augmentation. Does it affect the analysis results?
3. There is only one train-test split in Section 2, but two in Section 5.
4. The complexity of the proposed model.

limitations: The authors have pointed out the limitations of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Node degrees of real-world graphs follow a long-tailed distribution, but GCN exhibits a performance disparity between high-degree nodes and low-degree nodes, i.e., degree bias. This paper discovers an interesting phenomenon that graph contrastive learning methods have already a smaller degree bias.  Based on this discovery, this paper theoretically analyzes the reason and proposes a tailored contrastive learning method GRADE. Experiments validate the effectiveness of the proposed method.

strengths_and_weaknesses: Strength:
1.	The finding is interesting and may inspire a new paradigm for alleviating degree bias.
2.	The paper is well-written and the conclusion is clear.
Weakness:
1.	The conclusion seems to be only for GCN. I wonder GAT[1] may exhibit a smaller degree bias, even smaller than graph contrastive learning methods.
2.	From Figure 6 in Appendix A, the advantage of graph contrastive learning methods over GCN on Photo dataset is not obvious. The numerical values of their slopes are close.
3.	There is a small gap between degree bias and theoretical analysis of clear community structure.
4.	The improvement of the proposed method in Table 1 does not seem statistically significant because of high variance.
5.	There are some related works designed for degree bias, such as SL-DSGCN[2]. But these methods are not set as baselines in the experimental comparison.

[1] Veličković P, Cucurull G, Casanova A, et al. Graph Attention Networks[C]//International Conference on Learning Representations. 2018.
[2] Tang X, Yao H, Sun Y, et al. Investigating and mitigating degree-related biases in graph convoltuional networks[C]//Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020: 1435-1444.

questions: 1. Is the conclusion only suitable for GCN? I wonder GAT may exhibit a smaller degree bias, even smaller than graph contrastive learning methods.
2. From Figure 6 in Appendix A, the advantage of graph contrastive learning methods over GCN on Photo dataset is not obvious.
3. How does a clear community structure lead to a smaller degree bias?
4. The improvement of the proposed method in Table 1 does not seem statistically significant because of high variance. And the related works designed for degree bias are not set as baselines in the experimental comparison.

limitations: In addition to the limitations mentioned in the paper, the generalization of the conclusion should be taken into consideration.
review_title: null

Meta-review: metareview: This paper identifies a fairness problem in graph contrastive learning (GCL), i.e., GCN often performs bad for low-degree nodes. The key to solve this problem is the observation that GCL can offer more fair representation for both low and high degree nodes. Authors also support their claims with theoretical analysis. 

All reviewers appreciate the contributions made by this submission. It is suggested that to simplify notations and make the theorems are self-contained in the final version.
confidence: Certain
Decision: Accept