Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of fairness-aware learning on graphs from the perspective of graph topology. According to the authors, this is the first work that theoretically understands the different roles graph statistical information played in the node representation bias amplification during message passing. Then a graph refinement method FairGR is proposed based on the theoretical results to reduce the sensitive homophily accordingly. 
Experiments on both synthetic and real-world datasets show the effectiveness of FairGR by achieving better tradeoff performance over three representative baselines.

strength_and_weaknesses: Strengths:
* The investigation of fairness-aware message-passing from the topology view is interesting.
* The theoretical foundations on node representation bias amplification are concrete with insights. Experiments are carefully designed and are conducted on both synthetic and real-world graph datasets.
* The paper is generally well-written (though with typos and grammar errors) and almost clear everywhere. 

Weaknesses:
* Some typos appear as I walk through the manuscript. For example, by that fact -> by the fact, the last section on page 1; many enhance -> may enhance, the last section on page 5. I suggest the authors do thorough proofreading during the rebuttal.

* The scalability of the proposed FairGR is not demonstrated and the optimization strategy is briefly described without computational analysis, which is important to employ in practical scenarios for graphs with massive nodes. Meanwhile, the sensitivity analysis of hyperparameters $\alpha$ and $\beta$ is suggested to be included for better demonstrating the contributions of label homophily coefficient and graph topology perturbation during learning.

* Synthetic experiments from Figure 2 are somehow vague and confusing. Since it shows the DP difference during message passing with respect to the sensitive homophily coefficient, what is the instantiation of GNNs used here for the message-passing process? Does MLP also show similar behavior regarding DP difference and sensitivity homophily here?

clarity,_quality,_novelty_and_reproducibility: Clarity: Most of the paper is clear except for some experimental setups that are a little vague.

Quality: The theoretical analysis is concrete but the writing can be further improved.

Novelty: The idea of theoretically analyzing the fairness-aware graph learning approaches has novelty and merits.

Reproducibility: The reproducibility is relatively weak with no codes provided.

summary_of_the_review: In summary, my concerns are mainly from two aspects:
* The scalability of FairGR could be further demonstrated through complexity analysis. The sensitivity of hyperparameters should be addressed.
* The details of experimental setups could be further explained for more convincing empirical support to the theoretical foundations.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this article, the authors propose to study and improve fairness in graph neural networks. More precisely, they provide conditions under which the graph aggregation steps increase prediction biases, and they propose an optimization problem that allows to find an optimal graph topology that reduces biases while preserving topology information. They finally demonstrate the efficiency of their approach on several experiments.
strength_and_weaknesses: Strengths:
---The paper is overall well written but a bit hard to follow
---To my knowledge, it addresses an interesting problem about graph neural nets
---The experiments are convincing

Weaknesses:
---Some parts of the method have a little bit of a heuristic feeling; for instance, I am wondering if other models could be used (instead of gaussian mixtures) for random graphs? Is there a reason (other than mathematical computations) for using such random models?
---Similarly, there is no discussion about the optimization properties of (2). Would it be possible to show some kind of convergence results, or to prove anything concerning the limit point?
---Graph topology is often characterized with persistent homology. Are there links between the proposed optimization scheme and recent papers about topology optimization based on persistence diagrams? (see for instance http://proceedings.mlr.press/v139/carriere21a.html) It would be nice to add some discussion on this point.

clarity,_quality,_novelty_and_reproducibility: I am not very knowledgeable in graph neural networks, but the proposed approach looks quite original and easy to reproduce to me.
summary_of_the_review: Overall, the paper looks good to me, even though I am no expert in graph neural networks.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies prediction bias amplification of graph neural networks using contextualized stochastic block model. Specifically, their analysis utilizes a distribution distance as bias measurement and discusses when $\Delta$ bias is enhanced regarding homophily edge ratio, graph size and density. Based on it, the author proposes a regularization framework FairGR to rewire the graph structure and reduce the representation bias. Experiment shows FairGR achieves both good accuracy and low bias. 
strength_and_weaknesses: Strength:
1. The analysis is theoretically sound with appropriate discussion and remarks.
2. The proposed FairGR coupled with proposed representation bias closely.

Weakness:
1. The motivation of FairGR is unclear. From Table 1, we observe GNN is just on par or slight better than MLP while the fairness measure is a lot worse. Does that mean Fair learning on GNN is not necessary on these datasets ? Furthermore, whether the proposed FairGR can reduce $\Delta_\text{DP}$ and $\Delta_\text{EO}$ to the level of MLP in Table 1.
2. A lot of notations in the paper are not clear or assuming readers with relevant knowledge. For example, in definition 2, "random graph sampled from ()", after reading the whole paper, I realize the generalization process is exact the contextual stochastic block model (CSBM), it is very confusing in this definition about how A and X are generated. 
3. The novelty is limited. Based on my understanding, if we treat sensitive feature as the only node feature, the paper's contribution is not that different from [1][2], which both talks about GNN's concentration property. 
[1] IS HOMOPHILY A NECESSITY FOR GRAPH NEURAL NETWORKS? ICLR 22'
[2] Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization ICML 21'
clarity,_quality,_novelty_and_reproducibility: I think the paper can be greatly improved on clarity. The main analysis is also similar with existing work.
summary_of_the_review: Overall, the idea of the paper is clear and proposed method is straightforward. My main concern is around the novelty and experiments. First of all, the representation bias is not that different with other homophily understanding on GNNs. Second, the selected datasets cannot convince that proposed method is significant for fairness learning: (1) GNN is not better than MLP on accuracy (2) I suspect the bias of FairGR is still larger than MLP.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a way to solve the problem that GNNs tend to increase Bias. First, the authors give a mathematical interpretation of why GNNs increase Bias. Based on the causes obtained from this interpretation, we propose a method to suppress the increase in bias that occurs during message passing. Experimental results showing the effectiveness of the method are also presented.
strength_and_weaknesses: Weakness
- The biggest problem is that the content is not complete, especially after Section.4. This makes the evaluation of the proposed methodology difficult. If we try to interpret and understand what is written in a favorable manner, we can assume that the claims are probably correct, but we cannot accept them as being of publishable quality. I think the assignment settings and methods are interesting and should be evaluated carefully after they are completed.
- Specifically, the major problems are as follows
	- I'm not sure what equation (2) means, but since it seems to be an optimization problem, perhaps
$$\min L s.t.\tilde{A}={ij}\in\{0,1\}$$
where $L=H1+\alpha H2+\beta H3$?
	- Regarding Table 1, it says "To validate the effect of bias enhancement of GNNs," but it is not a comparison with the proposed method. The intent may be to confirm the current status, but in that case the text is confusing, and furthermore, there should be a separate comparison with the proposed method.
	- Figure. 6 is reffered, but it is not appropriate to refer the figure in the suppliment. Figure.3 may be correct instead of Figure.6. It seems that a comparison with the proposed method may be more appropriate for the content in one piece. Therefore, it may be appropriate and intended to publish Fig. 6 in the main body. However, even in that Fig. 6, two of the three are compared to the proposed method, but the quality of the remaining one is poor, with no comparison.
	- It may not be required, but it is not reader friendly to have RELATED WORK at the end.
clarity,_quality,_novelty_and_reproducibility: The proposed method is simple, but the fact that it uses an analysis of why Bias increases as a basis for its proposal is an originality novelty. However, the quality is poor and unclear at the stage of showing the effect of the proposed method.
summary_of_the_review: Issues related to Bias are important issues in AI operations, and the fact that GNNs tend to increase Bias is problematic, and it is a very important task to analyze these factors and then present improvement methods. The analysis of the causes of GNNs increasing Bias seems justified, and the improvement methods are highly convincing.

On the other hand, since the quality of the structure since the proposal of the methodology is in a low state and the information to evaluate the methodology is unclear, the text should first be refined and the evaluation of the methodology should be clarified. We believe this will result in something that can be made public.

**Conclusion following discussion with the authors**

The problems with the sentence structure that were hindering my understanding have been largely remedied. As noted before, the value of the methodology itself is positive. For this reason, I am raising the score.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: __Summary.__ This paper considers the problem of bias amplification with Graph Neural Networks. More specifically, the authors consider the case of binary “sensitive features”. It is a known fact that in many homophilic networks, similar nodes tend to connect to one another (homophily)--- and in particular, nodes with similar sensitive features are more likely to be connected (a fact that the authors call topology bias). This, the authors argue, is detrimental to the fairness of GNNs, as it yields “representational bias" --- we note here that this phenomenon is not mathematically characterized in the paper.

From a theoretical perspective, the authors propose the analysis of a stochastic block model with two communities to show the effect of this special type of homophily. This allows them to establish conditions regarding the number of nodes and the properties of the stochastic block mode and the “reduction coefficient” of the distance between mean nodes. The authors then proceed to propose a pre-processing step to solve this issue. The pre-processing step is basically a rewiring of the adjacency matrix, obtained by solving an optimization problem that roughly, finds the closest approximation of the original adjacency $A$ that diminishes homophily on the sensitive attributes while preserving the homophily on the labels. The authors subsequently perform one synthetic experiment, that confirms their theorems, and experiments on 3 real datasets to show improved fairness metrics that their method brings.

__Summary of the reviews.__ The reviewers (and the Area Chair) seem mildly enthusiastic about this submission --- more specifically, three reviewers vote for weak acceptance (one of these reviewers being quite foreign from the field of GNNs, as they state). One reviewers votes for strong rejection (3). Although the authors dispute this reviewer's comments, I have to concur that the reviewer's feedback is pertinent.  The arguments brought forward by the reviewers were as follows:

 __1. Scalability of the method and sensitivity of the hyperparameters:__
 The reviewers questioned in particular the scalability and sensitivity of hyperparameters of FairGR – a question that was adequately addressed by the authors during the rebuttal. The method, as per the authors response, scales quadratically with the number of training samples. This, the authors argue, is not optimal --- but theirs is a “pilot” study, and therefore should be taken as a proof of concept (the method should thus not entirely be judged on its inefficiency) .

 __2. Lack of experiments:__ Several reviewers expressed the wish to see further evaluation of the method on real datasets. The authors argue that this is difficult, due to the lack of access to “sensitive” data in real datasets. This might be a fundamental limit to the authors’ ability to assess the method. However, I would like to highlight that this could warrant using more synthetic experiments to prove their claim.

 __3. Lack of novelty.__ The reviewer voting against the acceptance of the paper raises the issue that the work is not entirely novel. Indeed, the theoretical analysis of the authors is done in the case where the features are all sensitive features. In that case, the analysis is the same as what has been performed in previous work. While the authors responded to this claim in the negative, their response is unsatisfactory for  the following reasons. The authors contend that the sensitive features are usual not taken into account in GNNs  (they are unobserved --- which was not clear from the main text). I assume that this means that the sensitive features explains the connectivity patterns more than the "normal" features alone. This is not consistent with their  theoretical analysis, in which sensitive features are linked with node and label attributes --- which, here, as the reviewer highlights, is a fairly standard setting. The analysis is therefore not novel,

 __4. Unclear notations and writing (somehow alleviated after the rebuttal) noted by at least two reviewers.__ The authors seem to have considerably improved the main text though after the rebuttal. Yet, some ambiguities persist. The description of the Gaussian mixture model remains unclear: What does $\mathbb{E}_i[\mathbb{P}[s_i =1]$ mean? On what random variable is the expectation? The captions should also include the definition of the metrics used.


justification_for_why_not_higher_score: Overall, the paper lacks significantly in clarity, as denoted by the reviewers in area chair, and as denoted by the new content introduced in the responses to comments (where we learn for instance that the sensitive features are not observed or used for classification). The analysis provided by the authors does not match the setting that they intend to study. Perhaps, as a side note, the problem is that the problem is not mathematically justified: the authors do not state what the "bias" is, nor do they provide  a mathematical characterization of the problem in terms of confounding variables,  unobserved variables or else --- this is perhaps what induces confusion in the reviewer strongly opposed to the rejection (and to some extent, myself) and led the authors to choose what seems to be an inappropriate theoretical analysis.
Decision: Reject