Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper proposes a post-processing approach to promote individual fairness of the outcome of any machine learning model. Based on the problem formulation, a basic approach together with several variants utilizing graph Laplacian to enforce individual fairness (GLIF) are presented. In the experiments, GLIF shows better efficiency, fairness metrics, and balance between test accuracy and prediction consistency. Generally, this paper is with limited technical novelty and lacks baselines for a comprehensive comparison. However, making trails to enforce individual fairness in different realms, such as debiasing the output of language models, is always encouraged.
main_review: Strengths:
(1) This paper considers a practical scenario and is well-organized.
(2) This paper is well-motivated, and utilizing graph Laplacian to promote individual fairness is a reasonable way despite the lack of novelty.
(3) Compared to the chosen baselines, the proposed GLIF achieves better performance in different ways.

Weaknesses:
(1) Some techniques proposed in this paper lack novelty and motivation.
(2) This paper lacks the study on related work, which should have been included to enrich the baselines for a comprehensive investigation.
(3) Some potential limitations are not well considered and presented.

Details:
In this paper, a post-processing approach based on graph Laplacian to promote individual fairness is proposed. On the one hand, this paper considers a practical scenario, which is the post-processing stage, to promote individual fairness. Generally, this paper is well-motivated and well-organized. Experiments also verify GLIF’s better performance on efficiency, fairness metrics, and balance between test accuracy and prediction consistency. Nevertheless, on the other hand, the drawbacks of this paper are also obvious. Firstly, some techniques proposed in this paper lacks novelty. For example, this paper lacks a survey on related works, which should have been included to notify the audience that similar approaches have been proposed and adopted in various previous works, such as [1, 2]. Also, although enforcing individual fairness based on graph Laplacian is already a widely adopted approach, what would be the specific motivation in this paper? Secondly, some techniques in this paper also lack motivation. For example, what would be the advantage of making use of alternative discrepancy measures on the output space compared with your approach in section 3.2.1? Both of the outputs here can be regarded as a distribution. Also, if KL Divergence is adopted here, do we need to explicitly assign the distribution? If the answer is positive, would you believe that this can also be a limitation of the approach in section 3.2.4? Can you provide a theoretical analysis on what is the main motivation and advantage of the alternative discrepancy measure? Thirdly, some potential limitation is not well considered. Beyond the limitation we mentioned above, why should we base on sensitive attributes to promote individual fairness in Example 4.2? What if there is no sensitive attribute assignment? What is the definition of the mentioned sensitive attribute here? Also, does the dispersion matrix only have the ability to reflect linear relationships? Will this be another limitation? Beyond the problems I mentioned above, I would still have the following concerns:
(1) For inductive settings, only performing a single coordinate descent step could be far from optimal, and the step length can be hard to specify. How could you tackle such problem?
(2) What is the exact definition of the bandwidth here? In the paper, is $h$ a function or a bandwidth parameter?

[1] Lahoti, P., Gummadi, K. P., & Weikum, G. (2019). Operationalizing individual fairness with pairwise fair representations. arXiv preprint arXiv:1907.01439.

[2] Kang, J., He, J., Maciejewski, R., & Tong, H. (2020, August). Inform: Individual fairness on graph mining. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (pp. 379-389).

limitations_and_societal_impact: Did not see any potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors proposed a post-processing algorithm for individual fairness. The algorithm get access of the predictions of the original model and a similarity graph between individuals, and solves the IF post-processing problem as a graph smoothing problem. The motivation to reduce bias of fine-tuned model is interesting. The paper is well written. However, I have some concerns about the effectiveness of the proposed method.

In Figure 1, the node signals of Alice and Bob are different, cross for Alice and tick for Bob. After connecting the node Alice and node Bob which enjoy the same qualities, their signals should be the same. I wonder what the signal should be. The experimental results on "Table 1: Results for the Bios task" and "Table 2: Results for the Toxicity task" show that the difference of the proposed method and the baseline is trivial is in terms of test accuracy and the prediction consistency. But if there are bias of the algorithm's prediction as shown in Figure 1, the difference between the test accuracy of the proposed method and the baseline should be significant. If the algorithm is biased but the proposed method in this work does not connect similar nodes in the graph, it tends to yield similar predictions as the baseline. 

In line 72, the experiments are conducted to reduce bias of fine-tuned Bert. Is there any assumption that the fine-tuned Bert is biased?  
main_review: See above.
limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a method for post-processing a model for guaranteeing individual fairness properties based on graph Laplacian regularization. Their main result is that this method achieves a weakened definition of individual fairness (under certain assumptions). The authors also evaluate this method on text datasets for fine-tuned BERT models. 

The method takes as input a graph consists of pairs which are close according to the similarity metric and solves an optimization problem using a graph Laplacian quadratic form regularizer to achieve fairness conditions. The fairness guarantee is that in expectation, the function is Lipschitz on sufficiently small distances (a sufficient condition for Mahalanobis distance is that the derivative is bounded in expectation). 

main_review: The authors describe two problems with the classical post-processing approach (Dwork et al): (1) it is computationally inefficient since it requires solving an optimization problem with O(n^2) constraints, and (2) global individual fairness can be in tension with accuracy. The idea of designing a post-processing method that achieves more desirable guarantees in practice is well-motivated and interesting. The paper is generally well-written. 

Although the main result (Theorem 4.6) appears technically sound, it does not seem particularly surprising that the graph Laplacian approach guarantees local individual fairness. In particular, the graph Laplacian regularization term can be written as the sum of the squares of distances between pairs weighted appropriately by the similarity metric distance (as shown in equation 3.2). 

Another weakness is that the authors provide a limited comparison of local individual fairness definition and the typical individual fairness definition. First, the empirical results in Section 5.1 are fairly limited and do not offer a thorough the fairness-accuracy tradeoffs for these two definitions. Second, since the local individual fairness is permitted to violate the Lipschitz constraint for large distances, it would be natural to also compare with a global individual fairness with respect to an adapted metric d’ where d’(u, v) = $\infty$ if d(u,v) > \tau and d’(u,v) = d(u,v)  otherwise. 

-----------
Update: Thanks to the authors for their detailed responses (and for correcting the mistake in my definition of $d'$). However, I am still not entirely convinced by the proposed fairness definition, which seems to be a significant relaxation of IF. Thus, I have decided to maintain my score. 

limitations_and_societal_impact: The authors adequately discuss the societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper attempts to instantiate the individual fairness solution concept of Dwork et al in a manner which relaxes some of the stringency of a global Lipschitz constraint. The proposed formulation applies a graph Laplacian smoothing technique to post-process the predictions of an arbitrary model. The graph is chosen so that edge weights decay exponentially with decreasing similarity (wrt the "fairness" metric), with a cutoff to 0 at some point. Under some assumptions, this regularizer is shown to enforce a much more local version of individual fairness. Experimental results show that this results in a better tradeoff with accuracy than the original notion, and similar or better performance compared to a recently proposed method.

main_review: The main strength of this paper is to propose an alternate way of instantiating individual fairness which is easy to apply and which appears to provide a better tradeoff between fairness and accuracy. The Laplacian method is well-motivated in terms of a connection to a local notion of fairness. This method does not address the (often prohibitive) challenge of identifying a suitable metric with which to define individual fairness. However, given that such a method can be identified, it proposes a nice way of enforcing it. 

A few questions:

(1) What is the impact of the parameters theta and tau on the behavior of the method?

(2) What is the conceptual relation of the Laplacian method to the alternate definition of individual fairness proposed in [36]? 

(3) How does the method relate to alternate proposals to use a graph structure to instantiate individual fairness such as http://www.vldb.org/pvldb/vol13/p506-lahoti.pdf or https://dl.acm.org/doi/abs/10.1145/3394486.3403080?

limitations_and_societal_impact: yes
review_title: null

Meta-review: Thank you for your submission. This paper gives a new post-processing technique for obtaining a relaxation of the individual fairness criterion. While the paper contributes to the literature on individual fairness, we felt that there was a lack of motivation or justification of why such local relaxation of individual fairness is a meaningful criterion. In particular, it seems that the relaxed individual fairness notion was proposed since it is satisfied by the Laplacian method. Thus, the paper can be strengthened if the authors could provide more exposition around their definition.
Decision: Accept (Poster)