Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a set of data augmentation approach to improve the fairness of GNNs. It first provides an upper bound on the correlation between the GNN node representations and a given sensitive attribute. Then it proposes three data augmentation tricks to respectively reduce three terms of the upper bound. The proposed method is evaluated on several benchmark datasets to show the effectiveness.
main_review: Strengths:

(1) This paper studies an interesting and important problem of GNN fairness. 

(2) The proposed method demonstrates effective empirical performance on several benchmark datasets.

(3) The proposed data augmentation tricks are easy to implement and potentially broadly applicable.

Weakness:

(1) The presentation of the analysis can be greatly improved.

    (1.1) The assumptions for Theorem 1 should be stated explicitly in the form of Assumptions. The current writing makes it difficult to check what exactly are being assumed in order to prove Theorem 1.

    (1.2) Some of the assumptions are questionable. For example, it seems that the GNN hidden representations $h_i$'s follow a uniform distribution. How is that possible? And how much does Theorem 1 rely on this assumption?

    (1.3) The intuitions of the analysis should be better explained. For example, $\gamma_2$ takes a very complicated form. What is the intuition of this term?

(2) The connection between the proposed augmentation tricks and the three terms in the upper bound is ambiguous. If the three terms are really important, why don't we directly augment the data by optimizing for those terms? For example, based on the definition of $\gamma_1$, it seems very easy to reduce it to 0 by rewiring the graph. What are the potential trade-offs for not fully optimizing those terms?

(3) In the appendix, it is shown that the proposed tricks can reduce the $\gamma$ values. Could you include an ablation study testing methods that directly optimize for these terms, as mentioned in (2).

(4) Quite a few missing literatures on GNN fairness:

1. A. Bose and W. Hamilton. Compositional fairness constraints for graph embeddings. 
2. M. Buyl and T. Bie. The kl-divergence between a graph model and its fair i-projection as a fairness regularizer.
3. Y. Dong, J. Kang, H. Tong, and J. Li. Individual fairness for graph neural networks: a ranking based approach.
4. C. Laclau, I. Redko, M. Choudhary, and C. Largeron. All of the fairness for edge prediction with optimal transport.
5. J. Ma, J. Deng, and Q. Mei. Subgroup generalization and fairness of graph neural networks.
6. Z. Zeng, R. Islam, K. Keya, J. Foulds, Y. Song, and S. Pan. Fair representation learning for heterogeneous information networks.



----------Post Author Response-----------------
I appreciate the author response and revision, which resolved most of my concerns. I therefore raise my evaluation to 6. The proposed method still seems somewhat ad-hoc but overall this work would be an interesting addition to the GNN fairness literature.
summary_of_the_review: This paper proposes a set of data augmentation tricks that demonstrate empirical gain on GNN fairness. However, the presentation of analysis and motivation is not convincing and can be largely improved.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper considers the problem of learning fair representations via graph neural networks. Concretely, the paper derives an upper bound on the correlation between sensitive attributes and representations and uses this bound to propose various graph augmentations that increase different group fairness metrics (e.g., statistical parity). The proposed augmentations are feature masking, node sampling, and connectivity augmentation. An experimental evaluation on different node classification, link prediction, and edge deletion tasks shows that the proposed method learns representations with higher group fairness while incurring minimal utility decreases.
main_review: I want to preface my review by stating that I am not very familiar with graph neural networks, and will thus be mostly evaluating the “fairness aspect” of the paper.

**Strengths**
- `The problem setting is relevant.` Fair representation learning for tabular data has been studied extensively in the literature. However, fair representation learning has not been considered yet for graphs, which is the problem that this paper investigates. As the paper empirically demonstrates, prior work on graph representation learning typically incurs group fairness violations, which need to be addressed. 
- `The method is novel and well-motivated.` The paper theoretically analyses the correlation between sensitive attributes and the graph representation and uses the analysis to propose different graph augmentation methods to reduce (intrinsic) bias of the representations.
- `The paper is clearly written.` Even as an outsider of the field of graph neural networks I was able to follow the paper as the ideas are well-motivated and clearly presented.

**Weaknesses**
- `The ablation study yields inconclusive results.` Depending on the task, different ablated versions of the proposed method (e.g., without edge deletion) significantly outperform the full method, which is not ideal. In my opinion, it would be better to tailor the approach to the different tasks (e.g., by removing the obsolete parts), rather than leaving the tuning to the practitioners interested in applying the method in practice.  

**Questions**
- How do the different graph augmentation strategies interact? The paper conducts an ablation study to compare the performance of different augmentation strategies, but it would be interesting to see if any theoretical conclusions can be made.
- The equation for $\gamma_2$ in theorem 1 and section 3.3.3 are inconsistent. Which is the correct one?
- Proposition 1 shows that in expectation, the proposed adaptive feature masking scheme results in a lower distribution difference compared to uniform feature masking. However, the uniform feature masking is not the baseline we care about (I think). Instead, we would like to know how the proposed masking scheme affects the distributions compared to no masking at all. Do you have any insight on this?

summary_of_the_review: The relevance of the problem setting, technical and empirical novelty, good presentation, and significant results warrant acceptance of the paper in my opinion.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the bias issue in the representation learned by GNN-based models. Some theoretical analysis is presented, and based on this analysis they propose several data augmentation techniques, such as feature masking, edge addition/deletion and node sampling. Experimental results demonstrate the effectiveness of these augmentation on multiple real-world graphs.
main_review: 
Strengths:
1. The proposed method improves fairness metrics on node classification and link prediction while maintaining decent performance on accuracy.
2. The proposed method is simple to implement and justified by the theoretical analysis on the upper bound.

Weaknesses:
1. The hyperparameters for data augmentation provided in appendix (A.7) seem to be a bit like magic numbers. How do the author determine to use these values rather than other values? Also, the sensitivity of the proposed methods w.r.t the hyperparameters should be investigated.
2. The effect of each data augmentation technique might interfere with each other. How to specify the right amount of augmentation for each type is not well studied.
3. Some case study on the real-world dataset or even toy dataset can be helpful for readers to better understand these data augmentation techniques in a more intuitive manner.


summary_of_the_review: Overall the proposed technique following the analysis on the theoretical upper bound, is simple and effective in improving fairness metrics. Experiments could be made stronger though, such as by including sensitivity analysis on the hyperparameters.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper investigates the problem of fairness learning on graphs. To address this, the authors first give a theoretical analysis on the sources of bias in node representations achieved by GNNs, then propose several data augmentation methods for fair node representation learning. Experiments on several datasets demonstrate the effectiveness of the proposed model.
main_review: Several main concerns should be well-addressed by the authors.

1. In the Introduction, the motivation is not clear.
Why the "augmentation method" can well address this problem? It seems that the authors find that "augmentation has not been employed for fairness learning on graph, so we do".
Besides, many related studies have been proposed for fair node representations. Can they deal with this problem? The authors do not illustrate how and why the proposed model is better than theirs.

2. In the section of Related Work, the related studies are not sufficiently surveyed, and several recent related studies such as [1,2,3] are missed. 
Besides, in the last sentence of page 2, the authors claim "it is not adaptive to the graph structure". What does it mean? And why? The authors should give more explanations.
Furthermore, the authors do not provide the drawbacks of these related studies compared to the proposed model.

3. At the end of page 3, the authors give an equation to depict the calculation of correlation between the sensitive attributes and the aggregated representations. 
However, this equation is a bit confusing. In particular, in the numerator of this equation, what does "n" in the sum operator mean? 
Besides, in the following paragraph, why "it is assumed that these distributions have the same maximal deviation ∆"? 

4. In the first paragraph of section 3.3.1, the authors claim that "for the first layer of GNN without losing significant information that the features provide". However, there is no content to demonstrate the proposed model can fulfill the goal of "without losing significant information". Both the features and the structures are modified to train the GNN model (such as by feature mask, as well as edge addition and deletion), thus much important information could be lost. So how to guarantee this claim?

5. In the first paragraph of section 3.3.3, there are two confusing equations |E_x|<=|E_o| and |E_x|>=|E_o|.

6. With the proposed model, some augmented graphs can be achieved. However, the authors do not give the details that how to use these graphs for contrastive training. To maximize their agreement?
Generally, contrastive learning usually aims to learn representations with better generalizability, transferability and robustness. So why this kind of contrastive learning, though with the proposed augmentations, can address the fairness issue?

7. In experiments, the authors employ citation networks Cora, Citeseer and Pubmed for fairness evaluation, and utilize the category of the articles as their sensitive attributes. However, this kind of utilization is not reasonable. Sensitive attributes are the inherent attributes of instances, and can involve some kind of discrimination. However, here the category of articles is not an inherent attribute but is summarized by humans. Would they involve any discrimination in the articles? I don't think so.
For the fairness evaluation of node representations, the authors employ two widely used metrics, namely statistical parity and equal opportunity. For example, for nodes with different genders, the gender might influence their labels. However, for the fairness evaluation of edges, the proposed metrics are not well-motivated. In particular, for edges belonging to different groups (E^X or E^W), do this kind of sensitive attributes (i.e., the groups) influence their existence? Besides, why the generation of fair node representations, can generate fair edges?

8. In experiments, most of the fairness learning approaches are not employed as the baselines for comparison, such as the related studies in section 2, as well as [1,2]. Thus, the experiments are not convincing.


[1] Compositional fairness constraints for graph embeddings. ICML 2019

[2] Debayes: a bayesian method for debiasing network embeddings. ICML 2020

[3] Debiasing knowledge graph embeddings. EMNLP 2020
summary_of_the_review: 1. The motivation of the paper is not clear enough.
2. Several claims are not well-demonstrated.
3. The experimental settings are not quite reasonable, and the experiments are not convincing enough.
review_title: null

Meta-review: This paper studies augmentation-based methods to improve GNN fairness. 
Specifically, based on upper bounds, they propose augmentation tricks to reduce such bounds, empirically validated from benchmark datasets.

Before rebuttal, there was a negative consensus that evaluation results are inconclusive and important state-of-the-arts are not discussed. 
Authors have significantly revised to address the concerns of some reviewers (gszb and LHQM), though some concerns still remain that the scheme is rather ad-hoc. 
Meanwhile, reviewer xMz4 did not find rebuttal sufficient, as some valid comments were not fully discussed.
First, datasets where sensitive attributes are the inherent attributes of instances are more suitable for evaluation, which has not been properly addressed by authors.
Second, important baselines were mentioned by xMz4, but they were only mentioned briefly in the new section of related work in the revised work.
For example, (Agarwal et al 2021) is mentioned as dealing with counterfactual fairness only, but statistic parity studied in this paper is highly related to this concept.
Similarly, this work can be viewed as an ad-hoc extension for fairness of GCA, without in-depth discussions to compare/contrast with these work, and to better highlight novelty/distinction.

Summing up reviewer discussions, we conclude this paper is not ready yet as an ICLR publication.
Decision: Reject