Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes Fair Message Passing (FMP). It builds on Graph Signal Denoising, e.g., as described in (Ma et al., 2021b). The methods described in previous works are extended by adding an additional fairness term ($h_f$ in Eq. (1)) to the optimization problem that governs the feature aggregation step of the GNN. An efficient, iterative algorithm for solving this optimization problem is derived. The main motivation and promise of FMP is to explicitly uncover how sensitive attributes influence the model predictions and explicitly render sensitive attribute usage in the forward computation of the GNN. The authors dub this notion "transparency in fairness". FMP is compared to popular (fairness unaware) GNN baselines as well as adversarial debiasing and demographic regularization methods on 3 datasets (also used in prior work): Pokec-n, Pokec-z, and NBA.
strength_and_weaknesses: 
## Strengths

* The paper is clearly written and well-structured, which facilitates its understanding and readability.
* It concerns fairness in GNNs, which in my opinion is still relatively underexplored topic.
* The informally proposed "transparency in fairness" is conceptually nice and can potentially inspire further studies in the intersection between fairness and explainability.
* To the best of my understanding, the paper extends prior work in intuitive yet mathematically non-trivial way.

## Weaknesses, Questions and Concerns

My main concerns are about the motivation of this work and how it relates to the experimental evaluation. I also have questions about some of the technical details.

### Experiments

1. The paper suggests that the main experimental setup is similar to that of (Dai & Wang, 2021). If this is the case, then FairGCN and FairGAT (Table 3, Dai & Wang, 2021) seem to outperform FMP (Table 1 of this work) in terms of fairness while the accuracy stays similar or slightly lower. The difference in the results is especially large for the NBA dataset. This comparison is entirely missing from the current version of the paper. If the experimental setup in (Dai & Wang, 2021) differs from that of FMP, it is not made clear how, in what way and why.
2. In general, the cited references for the adversarial debiasing (Fisher et al., 2020) and regularization (Chuang & Mroueh, 2020) methods, which FMP is compared to, seem to not consider GNN fairness, i.e., they have been applied to other datasets and domains. I would rather see comparison to fairness aware methods which are more relevant and have been applied to the GNN fairness domain before. Obvious candidates for that are the aforementioned FairGCN and FairGAT from (Dai & Wang, 2021), but the authors also cite other GNN fairness works in the Related Works section.
3. According to the Introduction, a primary motivation of this work is "to make the process of achieving fair model via sensitive attribute informations white-box" such that "the maintainers and auditors both get benefits from model transparency". Moreover, the paper claims that "chasing explainability can help experts understand how the model provide prediction and convince users". Yet, there is no experimental evaluation how "transparent" FMP actually is, what information about the model it elucidates and how useful and convincing FMP is for the users or model designers.

### Motivation

4. The paper provides a "formal statement on transparency in fairness" in the Introduction, but to me it is rather high-level and informal. I am not aware of a formal mathematical framework or metric that evaluates how transparent a given model is.
5. A selling point of FMP is that it "uncovers how sensitive attributes influence final prediction" and that this is not possible for prior black-box models which "implicitly encode the sensitive attribute information in the well-trained model weight via backward propagation". However, there have been tools such as GNNExplainer (Ying et al., NeurIPS 2019), PGExplainer (Luo et al., NeurIPS 2020), etc., which aim in generating explanations for GNNs. Given the connection to explainability (as mentioned in the paper), I would be interested to know if these tools can be repurposed in the context of "Transparency in fairness" proposed by the authors, but discussion of that is also missing.
6. According to the introduction, "The biased node representation largely limits the application of GNNs in many high-stake tasks", but the provided citations (Mehrabi et al., 2021, Suresh & Guttag, 2019) do not make it clear how GNNs are currently being used in such tasks. In particular, it is not clear what kind of bias the authors aim to mitigate until the reader reaches the experimental section. Is it topology bias, is it representation bias, does the bias comes from the fact that the sensitive attributes are encoded/embedded/included in the input features or the learnt representations? I would suggest to make this more explicit and bring it up somewhere earlier in the paper.

### Technical Details

7. Without reading prior works (I referred to (Ma et al., 2021b) for a general background), it is not clear that the model solves the optimization problem in Eq. (1) for every GNN layer (to the best of my understanding). It is not entirely obvious what $\mathbf{F}$ denotes and at times sections 2 and 3 can be a bit confusing in sense that it is not clear what is plugged when and where in the model.
8. The authors experiment with GNNs with maximum 2 layers. If my assumption from above is correct that Eq. (1) is solved for every GNN layer, it is not obvious to me why the fairness term $h_f$ should be integrated in every layer of the GNN and not only in the last one which provides the predictions. If we talk about solving Eq. (1) for the intermediate layers, I don't understand why we would take the softmax $SF(\mathbf{F})$ of them. There seems to be some possible confusion arising here for me.
9. To the best of my understanding, the FMP method described in Section 3 is only concerned with the _aggregation_ step of the GNN model. However, hypothetically, it should be possible that some bias and unfairness can also arise from the feature transformation steps, but these are not discussed or mentioned in the paper. Thus, it is hard for me to judge the generality and the applicability of FMP.
10. In particular, the end of Section 3 says that "the propagation and debiasing forward in a white-box manner and there is not any trainable weight during forwarding phrase" and I don't understand why this is the case (e.g., if there is feature transformation involved, see $\mathbf{W}$ in Algorithm 1 of (Ma et al., 2021b)).
11. Section 3.2 says that "directly computing the gradient of the fairness term makes the closed-form gradient complicated since the gradient of $l_1$ norm involves the sign of elements in the vector". The gradient of the $l_1$ norm can be tractably computed and I don't entirely understand why the closed-form is absolutely required. E.g., how does it affect the optimization problem if we also try to optimize it with gradient descent (esp. given that $\text{sign}(\mathbf{u})$ is used in Eq. (5))?

### Minor

Some typos, the optimization problem for GAT in App. G seems to be missing and there are some other minor issues related to the paper readability.
clarity,_quality,_novelty_and_reproducibility: * The paper is relatively clear and readable
* My understanding is that it is technically/mathematically a novel and non-trivial extension of prior work, but I am not entirely convinced by the motivation and am not sure if the solution proposed by the paper is necessary.
* The authors provide link to their source code, so I believe the work should be reproducible to a reasonable extent.
summary_of_the_review: In summary, it seems to me that the paper presents some technical contributions, but I don't find them very well-motivated and am not sure if the evaluation is convincing and thorough enough. I also have minor concerns about some elements of the paper exposition (esp. in Section 3).
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper follows two separate trains of thought.
The first is on advocating for the idea of transparency w.r.t. how a given model produces fair predictions. The authors define transparency as explicitly using the sensitive attribute in forward propagation.
The second, and main point, is the development of a Fair Message Passing (FMP) method. According to the paper's results, FMP seems to outperform the chosen baselines on every point of the fairness-accuracy trade-off.
strength_and_weaknesses: _Strengths_

- The FMP method outperforms the chosen baselines;
- Literature on fair representation learning specifically for GNNs is scarce, therefore the paper tackles an arguably under-explored field;


_Weaknesses_

- The concept of _transparency_ is somewhat arbitrary and not fully clear. The authors claim a "formal definition" in page 1, but what follows is arguably subjective.
    - Is it just that a model is "transparent" if it uses sensitive attribute information in its decision-making process? Usually the opposite condition (not explicitly using the sensitive attribute) is targeted in methods from the literature. It's known that sensitive attribute information is redundantly encoded on any sufficiently-rich real-world dataset. Using this information explicitly or not is not novel, and its not clear which choice is best (it actually depends heavily on the specific real-world task and context). A significative part of the paper is dedicated to this concept of transparency which seems quite trivial.
    - In the context of deep learning, even by explicitly using sensitive attribute information in the forward pass, this in no way brings us closer to understanding exactly _how_ the sensitive attribute information is used to produce predictions in a human-understandable manner.

- Baselines are limited. Arguably the simplest fairness intervention you can use is that of [Hardt et al. (2016)](https://proceedings.neurips.cc/paper/2016/file/9d2682367c3935defcb1f9e247a97c0d-Paper.pdf). Adding this thresholding-based post-processing step to the GNN baselines would be an easy-to-obtain baseline for comparison with the more complex method presented here.
    - Usually there is a clear fairness-performance trade-off in every task/dataset. If FMP achieves the best fairness, I find it hard to believe that it would achieve the best performance as well. This signals baselines weren't properly selected (e.g., using a simple GNN + thresholding post-processing or other fairness interventions).
- Experiments were repeated 5 times and the final results averaged, which is a positive. However variance is not shown in Figure 2, and it is not used to compute whether differences in fairness/performance are statistically significative.
    - For instance, the NBA dataset is quite small, and large variance between experiment runs is expected;

_Other notes_
- Table 1, the bold on the FMP method is not correct as it does not achieve the highest performance;
    - Bold on EO of FMP on the NBA dataset is also not correct;
- The formula given for DP and EO is the absolute difference in probabilities; as such the y-axis of the plots in Figure 2 should be between 0 and 1; if it is in percentage than this should be explained in the legend or caption;
- Figure 2 caption has a footnote "6" that I cannot find in the paper;
clarity,_quality,_novelty_and_reproducibility: - Paper is not particularly clear in its presentation. Reasoning is sometimes hard to follow and English writing is not perfect. Grammar and syntax errors can be found several times per page.

summary_of_the_review: Overall, some non-trivial modifications are needed for the paper to be ready for publication, namely: honing down focus and presentation efforts on the FMP method, adding well-known baselines from the fairness literature, and correcting English writing.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the fairness problem from a new perspective, named transparency, i.e., the influence of sensitive attribute should be easily probed by the public, and propose a novel method named FMP to achieve fairness with transparency via using sensitive attribute information in message passing. To accelerate the training process, the paper proposed an accelerated method to reduce gradient computational complexity with theoretical and empirical validation.
strength_and_weaknesses: Strength:

1. Consider the fairness problem from a new perspective, and develop a transparent method named FMP to learn fair node representations while preserving prediction performance, which has generalization.

2. The code is available, and the results can be reproduced.

3. The model is effective according to to reduce gradient computational complexity with theoretical and empirical validation.

Weakness:

1. This paper compares some classic methods such as APPAP, SGC, etc., but lacks some comparisons of SOTA methods.

2. If more general datasets could be compared such as Cora, citeseer, etc. It would be better. 

3. The scale of NBA datasets is small, with only 400 nodes. The performance improvement on NBA datasets cannot provide enough experimental support.

4. Limited performance improvement. In table 1, the experimental results of marking black are not the best performance. For example, under datasets pokec-z, although the other two indicators improved, GCN has the best AUC.  If possible, please offer the statistical significance test of your model.
clarity,_quality,_novelty_and_reproducibility: 1.{Evaluation: Novelty} The paper contributes some new ideas or represents incremental advances.

2.{Evaluation: Quality}The paper has some technical flaws. For example, the performance experimental evaluation fails to adequately support the main claims.

3.{Evaluation: Clarity} The paper is well organized.

4. (Evaluation: Reproducibility)Key resources are available and sufficient details are described such that it could be able to reproduce the main results.

summary_of_the_review: It is good to work with great novelty, but experiments should be more sufficient.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose to study the problem of fair node classification on graphs through the angle of “transparency”. They characterize transparency as the ability to verify models - (i) by quantifying the influence of the sensitive attribute in model prediction and (ii) obtaining such quantification using the trained model and test data samples. They point out critical flaws in the existing graph fairness methods in that such models encode the fairness property implicitly in the trained model weights and therefore don’t trivially adhere to the second aforementioned property. They propose a two-step framework that accounts for both graph aggregation and debiasing, to optimize for eq 1. To ensure the aggregation procedure over the graph, they leverage the connection between aggregation in certain GNNs and one-step gradient descent to minimize a particular function stated in section 2.2. To ensure fairness, they leverage the Fenchel conjugate of the fairness objective function. Eventually, this converts the problem into a Bi-level optimization which is solved using alternating optimization given by the fixed-point equations in eq 3. A closed-form operation for the proximal operator is provided which finally converts the optimization procedure into the proposed FMP scheme provided on page 5. A gradient acceleration trick is also suggested to compute the partial derivative of $<p,u>$ w.r.t $F$. Experiments on popular graph fairness datasets suggest that the proposed scheme is indeed better as compared to GNN baselines (without any fairness objectives) as well as to previously proposed SOTA graph fairness methods.

strength_and_weaknesses: 1. The results provided in table 1 and figure 2 are indeed strong. The proposed FMP scheme clearly outperforms all the baselines.
2. The runtime comparison results are quite convincing. The proposed method indeed holds value in that the runtime vs performance tradeoff is good.
3. There are various typos in the text writeup as well as in some equations. I strongly encourage the authors to thoroughly read the paper again.
4. If the authors are talking about the proximal operator commonly used in optimization, then the definition of proximal operator in the first paragraph of page 5 is incorrect. It should be ${h^*}_{f}(y)$. Based on this, the proof of proposition 1 seems to have some flaws. Also, the projection in eq 5 seems “into” the ball rather than “onto”.
5. The authors mention that - “directly computing the gradient of the fairness term makes the closed-form gradient complicated since the gradient of $l_1$ norm involves the sign of elements in the vector”. This is the rationale behind the proposed bi-level optimization framework. Perhaps, some experiment to compare their method against the standard $l_1$ norm gradient computation, will be helpful to verify the efficacy of their method.

clarity,_quality,_novelty_and_reproducibility: The paper has various typos and some flaws based on the definitions provided. The hyperparameter details along with the empirical evidence presented suggest that the results are likely to be reproducible. The technical novelty of the work is reasonable in that they propose to study the fairness problem through the angle of “transparency” and suggest an interesting solution.

summary_of_the_review: Based on the questions, comments and concerns raised in the previous sections, I lean towards weak acceptance of the work.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a method for fair message passing in a transparent way via explicitly using sensitive attributes in the forward propagation. 
Reviewers appreciated the novelty of the method and that it tackles an under-explored topic, i.e. Fairness in GNNs
However, reviewers pointed out the experiments as a part that can be improved substantially; with lack of comparisons to standard baselines which would be required to convincingly validate the method. This was the key reason for rejection.
justification_for_why_not_higher_score: Lack of baseline experimental comparisons.
Decision: Reject