Post-processing for Individual Fairness
Authors: Felix Petersen
Debarghya Mukherjee
Yuekai Sun
Mikhail Yurochkin
Venue: NeurIPS 2021 Poster (2021)
Keywords: algorithmic fairness
graph Laplacian
post-processing
fairness
individual fairness

Abstract: Post-processing in algorithmic fairness is a versatile approach for correcting bias in ML systems that are already used in production. The main appeal of post-processing is that it avoids expensive retraining. In this work, we propose general post-processing algorithms for individual fairness (IF). We consider a setting where the learner only has access to the predictions of the original model and a similarity graph between individuals, guiding the desired fairness constraints. We cast the IF post-processing problem as a graph smoothing problem corresponding to graph Laplacian regularization that preserves the desired "treat similar individuals similarly" interpretation. Our theoretical results demonstrate the connection of the new objective function to a local relaxation of the original individual fairness. Empirically, our post-processing algorithms correct individual biases in large-scale NLP models such as BERT, while preserving accuracy.

Post-processing for Individual Fairness
Felix Petersen" University of Konstanz felix. www.reeeuuiiiii..... kn
Debarghya Mukherjee' University Michigan mdeb@umich ch. edu
Yuekai Sun
Mikhail Yurochkin
University of Michigan yuekai @umi ch. edu
IBM Research, MIT-IBM Watson AI Lab mikhail, yur.cckioiihin bm com
Abstract
Post-processing algorithmic fairness a versatile approach for correcting bias in ML systems that are already used in production. The main appeal of post- processing that it avoids expensive retraining. In this work, we propose general post-processing algorithms for individual fairness (IF). We consider a setting where the learner only has access the predictions of the original model and a similarity graph between individuals guiding the desired faimess constraints. We cast the processinss problem graph smoothing problem corresponding graph Laplacian regularization that preserves the desired "treat similar individuals similarly" interpretation. Our theoretical results demonstrate the connection of the new objective function to a local relaxation of the original individual fairness. Empirically, our pest-processing algorithms correct individual biases in large-scale NLP models such as BERT, while preserving accuracy.
Introduction
There are many instances of algorithmic bias in machine learning (ML) models [ 4 which has led to the development of methods for quantifying and correcting algorithmic bias. To quantify algorithmic bias, researchers have proposed numerous mathematical definitions of algorithmic fairness. Broadly speaking, these definitions fall into two categories: group fairness (5) and individual
fairness (6). The former formalizes the idea that ML system should treat certain groups individuals similarly, e.g., requiring the average loan approval rate for applicants of different ethnicities be similar (7). The latter asks for similar treatment of similar individuals, c.g., same outcome for applicants with resumes that differ only in names (8) Researchers have also developed many ways of correcting algorithmic bias. These fairness interventions broadly fall into three categories: pre-processing the data, enforcing fairness during model training (also known in-processing), and post-processing the outputs of a model.
While both group and individual fairness (IF) definitions have their benefits and drawbacks [5]. [6. (9.
the existing suite algorithmic fairness solutions mostly enforces group fairness. The few prior works on individual faimess are all in-processing methods [10 13 Although in-processing is arguably the most-effective type of intervention, has many practical limitations. For example, it requires training models from scratch. Nowadays, it is more common to fine-tune publicly available models (c.g.. language models such as BERT [14) and GPT-3 (15)) than to train models afresh, as many practitioners do not have the necessary computational resources. Even with enough computational resources, training large deep learning models has a significant environmental impact 44, [16].
"Equal Contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Tost-processing offers an easier path towards incorporating algorithmic faimess into deployed ML models, and has potential to reduce environmental harm from re-training with in-processing faimess techniques.
In this paper, we propose computationally efficient method for post-processing off-the-shelf models to be individually fair. We consider setting where we are given the outputs of a (possibly unfair) ML model on set of individuals, and side information about their similarity for the ML task at hand, which can either be obtained using a fair metric on the input space or from external (e.g.. human) annotations. Our starting point is post- poot-procsssing version of the algorithm by Dwork er al. [6] (see (2.3). Unfortunately, this method has two drawbacks: poor scalability and an unfavorable trade-off with accuracy. As we shall see, the sharp trade-off is due the restrictions imposed on dissimilar individuals by Dwork et al. [6's global Lipschitz continuity condition. By relaxing these restrictions on dissimilar individuals, we obtain a better trade-off between accuracy and fairness, while preserving the intuition of treating similar individuals similarly. This leads us to consider graph lignal-processe approach to IF post-processing that only enforces similar outputs between similar individuals. The nodes in the underlying graph correspond to individuals, edges (possibly weighted) indicate similarity, and the signal on the graph is the output of the model on the corresponding node-individuall. To enforce IF, we use Laplacian regularization be smooth on the graph. We illustrate this idea in Figure [T biased model decides whom to show a job ad for a Python programming job based on their CVs and chooses Charlic and Dave but excludes Alice. However, from the qualifi- cations, we can see that Alice, Charlie and Dave are similar because they all have experience in Python, which is the job requirement, and thus should be treated similarly. We represent all five candidates nodes in graph, where the node signal (checkmark or cross) is the model's 's de- cision for the corresponding candidate, and the edge weights are indicated by the thickness of the connecting line. Alice and Charlic have the same qualifications and are therefore connected with a large edge-weig weight. For the predictions to satisfy IF, the graph needs to be smooth, i.e., the similar / connected candidates should have similar node signals, which can be accomplished by also offering the job to Alice. In contrast, directly enforcing IF constraints [6) requires a certain degree of output similarity on all pairs of candidates, and not just on those which are connected and thus similar. Our main contributions summarized below.
which encourages the signal to
Alice
X
Eve JS
Bob
X
X
Dave
Charlie
Figure 1: IF graph.
1. We cast post-pree poot-procsssing for individual faimess graph smoothing problem and propose coordinate descent algorithm to scale the approach to large data sets.
2. We demonstrate theoretically and verify empirically that graph smoothing enforees individual fairness constraints locally, i.c., it guarantees similar treatment of similar individuals.
3. We empirically compare the Laplacian smoothing method to the post-processing adaptation of the algorithm by Dwork et al. (6) enforcing global Lipschitz continuity. The Laplacian smoothing method is not only computationally more efficient but is also more effective in redueing algorithmic bias while preserving accuracy of the original model.
4. We demonstrate the efficacy of Laplacian smoothing on two large-scale text data sets by reducing biases in fine-tuned BERT models.
2 Post-processing Problem Formulation
Let X' be the feature space, )' be the set of possible labels/targets, and h X' + y be a (possibly unfair) ML model trained for the task. Our goal is to post-process the outputs of h so that they are individually fair. Formally, the post-processor is provided with set of inputs {x:) and the outputs of ls on the inputs (ūr A h()r))] and its goal to produce (fi)/_ that is both individually fair
and similar to the T. ss. Recall that individual faimess of h is the Lipschitz continuity of h with respect

---

to fair metric dx on the input space:
dy(h(z).h<z')) S Ldx(xxz²) for all x, E X,
(2.1)
where L. > O is a Lipschitz constant. The fair metric encodes problem-spede intuition of which samples should be treated similarly by the ML model. It analogous to the knowledge of protected attributes in group faimess needed to define corresponding faimess constraints. Recent literature proposes several practical methods for learning fair metric from data [18]. [9]. processor is either given access to the fair metric (it can evaluate the fair distance on any pair of points in 2), or receives feedback on which inputs should be treated similarly. We encode this information in adjacency matrix W E R=x" of graph with individuals as nodes. If the post-processor is given the fair metric, then the entries of W are
We assume the post-
Wi = (o 0
expp 0dx(2,
dx ( xy) ST otherwise,
(2.2)
where is a scale parameter and r > 0 a threshold parameter. the post-processor is given an annotator's feedback. then W is binary matrix with Way if i and are considered to be treated similarly by the annotator and 0 otherwise. Extensions to multiple annotators are straightforward.
We start with a simple post-procsssing adaptation of the algorithm by Dwork et al. (6) for enforcing individual fairness, that projects the (possibly unfair) outputs of h onto a constraint set to enforce (2.1). In other words, the post-processor seeks the closest set of outputs to the D 's that satisfies individual fairness:
aigmin arg min fr.... Sn
E dy.( dy(Ji, s [dx(()));))
(fm E
(2.3)
subject
This objective function, though convex, scales poorly due to the order of n² constraints. Empirically, observe that (2.3) leads to post-processed outputs that are dissimilar to the ss, leading to poor performance in practice. The goal of our method is to improve performance and scalability, while preserving the IF desiderata of treating similar individual similarly. Before presenting method, we discuss other post-procsssing perspectives that differ in their applicability and input requirements.
2.1 Alternative Post-processing Formulations
We review three post-processing problem setups and the corresponding methods in the literature. First, one can fine-tune a model via an in-processing algorithm to reduce algorithmic biases. Yurochkin er al. [12 proposed an in-processing algorithm for IF and used it to train fair models for text classification using sentence BERT embeddings. This setting is the most demanding in terms of input and computational requirements: user needs access to the original model parameters, fair metric function, and train a predictor, e.g., a moderately deep fully connected neural network, with a non-trivial toimess-promoting objective function.
Second, it is possible to post-process by training additional models to correct the initial model's behavior. For example, Kim et al. (20) propose a boosting- based method for group fairness post- processing. This perspective can be adapted individual fairness; however, it implicitly assumes that we can train weak-learners to boost. Lohia er al. (21), (22) propose to train a bias detector to post-process for group fairness and a special, group based, notion of individual fairness. Such methods are challenging to apply to text data other non-tabular data types.
The third perspective is the most generie: a user has access to original model outputs only, and minimal additional feedback guiding faimess constraints. Wei et al. [23] consider such setting and propose method to satisfy group fairness constraints; however, is not applicable to individual fairness. Our problem formulation belongs to this post-processing setup. The main benefit of this approach is broad applicability and ease of deployment.
3 Graph Laplacian Individual Fairness
To formulate our method, we cast IF post-processing as graph smoothing problem. Using the fair metric or human annotations as discussed in Section [ we obtain an x n matrix W that we treat as an adjacency matrix. As elaborated earlier, the goal of post-processing is to obtain a model f that
3

---

is individually fair and accurate. The accuracy is achieved by minimizing the distance between the outputs of f and h, a pre-trained model assumed be accurate but possibly biased. Recall that we do not have access to the parameters of h, but can evaluate its predictions. Our method enforces fairness using a graph Laplacian quadratic form [2 regularizer:
arg min (x( arg min || 1--1122 A LLf,
(3.1)
where ý is the output of the model h. and f the vector of the post-processed outputs, i... ʃ; fx;,
for i = I.....P. n. The matrix L, E R is called graph Laplacian matrix and is a function W. There are multiple versions of Ln popularized in the graph literature (see, e.g., [25] or (26)) To
elucidate the connection to individual fairness, consider the unnormalized Laplacian Lun,n D W.
where Da ンド= Wij. Dig identity is:
0 for i + j is the degree matrix corresponding to W. Then known
f T = = Way (J: -5²)²
(3.2)
Hence, the Laplacian regularizer is small if the post-processed model outputs ft and fj (i.e., treatment) are similar for large Wiy (i.e., for similar individuals and j). This promotes the philosophy of individual fairness: "treat similar individuals similarly". This observation intuitively explains the motivation for minimizing the graph Laplacian quadratic form to achieve IF. In Section we present more formal discussion on the connections between the graph Laplacian regularization and IF.
Our post-processing problem (3.1 is easy solve: setting the gradient of ga implies that the optimal solution f is:
Ln
Len
1+
(3.3)
The Laplacian L,, is a positive semi-definite matrix ensuring that (3.1) is strongly convex and that 3.3 global minimum. In comparison the computationally expensive constraint optimization problem 2.3), this approach has simple closed-form expression.
Note that the symmetry of the unnormalized Laplacian Lewan simplifies (3.3): however, there also non-symmetric Laplacian variations. In this work, we also consider the normalized random walk Laplacian Lnrw.n (I - D- where W D D-1/2 is the normalized adjacency matrix and D is its degree matrix. We discuss its properties in the context IF in Section 4 Henceforth, we refer to our method as Graph Laplacian Individual Fairness (GLIF) when using the unnormalized Laplacian, and GLIF-NRW when using Normalized Random Walk Laplacian.
3.1 Prior Work on Graph Laplacians
Graph-based learning via a similarity matrix is prevalent in statistics and ML literature, specifically, in semi-supervised learning. The core idea is to gather information from similar unlabeled inputs to
improve prediction accuracy (e.g., see (27), 28 [29] and references therein). Laplacian regularization is widely used in science engineering. We refer Chapelle (17) for a survey.
We note that 30 31 also use graph Laplacian regularizers to enforce individual fairness. Our work builds their work by elucidating the key role played by the graph Laplacian in enforcing individual fairness. particular, we clarify the connection between the choice of the graph Laplacian and the exact notion of individual fairness the corresponding graph Laplacian regularizer enforces.
3.2
Extensions of the Basic Method
In this subsection, present four extensions of our method: multi-dimensional outputs, coordinate descent for large-scale data, an inductive setting, and alternative output space discrepancy measures.
3.2.1
Multi-dimensional Output
We presented our objective function 3.1 and post-processing procedure (3.3 for the case of uni- variate outputs. This covers regression and binary classification. Our method readily extends to output space, for example, in classification, ft, e R can represent logits, i.c.

---

softmax inputs, of the K classes. In this case, f and ý are n x K matrices, and the term f L,, is K x K matrix. We use the trace as regularizer. The optimization problem (3.I) then becomes:
= arg min ga (f) = arg min ||f 811 + x tr (f Ln
(3.4)
where || ||| is the Frobenius norm. Similar to the univariate output case, this yields:
I T
++
(3.5)
The solution the same as 33. however, now accounts for mulli-dimenssonall outputs.
3.2.2 Coordinate Descent for Large-Scale Data
Although our method has a closed form solution, it is not immediately scalable, as we have to invert matrix obtain the optimal solution. We propose coordinate descent variant of our method that readily scales to any data size. The idea stems primarily from the gradient of equation (3.4). where we solve:
+ In
y
f f= =0
(3.6)
2
Fixing (f}}ott can solve (3.6) for fú:
81 E jztt (Ln.s + Lmneffff
(3.7)
Almm,
This gives rise to the coordinate descent algorithm. We perform asynchronous updates over randomly selected coordinate batches until convergence. We refer the reader to Wright (32) and the references therein for the convergence properties of (asynchronous) coordinate descent.
3.2.3 Extension to the Inductive Setting
This coordinate descent update is key to extending approach to the inductive setting. To handle new unseen points, we assume we have a set test points on which we have already post-processed the outputs of the ML model. To post-process new unseen points, simply fix the outputs of the other test points and perform a single coordinate descent step with respect to the output of the new point. Similar strategies are often employed extend transductive graph-based algorithms to the inductive setting
3.2.4 Alternative Discrepancy Measures on the Output Space
So far, we have considered the squared Euclidean distance measure of discrepancy between outputs. This is a natural choice for post-processing models with continuous-valued outputs. For models that output probability distribution discrepancy measures on the output space. It is possible to replace the squared Euclidean distance with Bregman divergence with very little change to the algorithm in the of the unnormalized Laplacian. Below, we work through the details for the KL divergence as a demonstration of the idea. result for the general Bregman divergence be found in Appendix B.3 (see Theorem B.4).
the possible classes, consider alternative
Suppose the output of the pre-trained model h is 0 A where ú (e Ek=1 e 1y=1 K- dimensional probability vector corresponding to K class classification problem (for,) is the output of the penultimate layer of the pre-trained model and ÿ, is obtained by passing it through softmax) } is the probability simplex in R Let P, denote the
and A K {x E R x;; 2 0, EK multinomial distribution with success probabilities v for any E A Define n) E R k- (resp. m)) as the natural parameter corresponding 9. (resp. f(), i.c.. fh.j = log (fr,)/ f0..//i.K 1 j < K - 1. The (unnormalized) Laplacian smoothing problem with the KI divergence is
Oi, o, k for
(j,,.., mn) = arg min
(KL
A
Σ J=1,
WirkL (Pril1 )}}}
}}} (3.8)
21 p1..... Mi. EAK
coordinate descent approach for solving the above equation is:
Ú = =arg min
(KL ( + Ej Wi (P,lIPb))}
(3.9)
5

---

The following theorem establishes that (3.5) solves the above problem in the logit space, or equiva- lently in the space of the corresponding natural parameters (see Appendix B for the proof): Theorem 3.1. Consider the following optimization problem the space of natural parameters:
i arg min, [17 [
1 Woyll 7
(3.10)
Then, the minimizer it of equation 3.10 is the natural parameter corresponding to the minimizer ys
of
3.8
4 Local IF and Graph Laplacian Regularization
In this section, we provide theoretical insights into why the graph Laplacian regularizer enforces individual fairness. As pointed out in Section enforcing IF globally is expensive and often reduces a significant amount of accuracy of the final classifier. Here, we establish that solving (3.1) is tantamount to enforcing localized version of individual fairness, namely Local Individual Fairness, which is defined below:
Definition 4.1 (Local Individual Fairness). An ML model is said to be locally individually fair if satisfies:
dy(k(z),Max')
limsup d'
$ IL
(4.1)
dx(x,x))
For practical purposes, this means that h is locally individually fair with constants and satisfies
(y(((r),h(x))) & (d, x²) for all x, E X where dx(x,, S'
S
(4.2)
analogy to equation (2.I). Equation (4.2) a relaxation of traditional IF, where we only care about the sunschitz-coostrainn for all pairs of points with small fair distances, i.e., where is less than some user-defined threshold e.
Example 4.2. For our theoretical analysis, need to specify functional form of the fair metric. A popular choice is a Mahalanobis fair metric proposed by (19, which is defined as:
(x (x=x))''(x==)
(4.3)
where a dispersion matrix that puts lower weight the directions of sensitive attributes and higher weight in the directions of relevant attributes. [19] also proposed several algorithms to learn such a fair metric from the data. If we further assume dy(y1. y2) 1y/1 V2l, then a simple application of Lagrange's 's mean value theorem yields:
11(x:) - ((x)))(x')
lim sup of ddy (2,
|/-1/2//(z)]-
(4.4)
dx(x,²))
This immediately implies:
dy(M(z),)(x'))
Egprr lim d'dx(x,=")L0 dx(xxx²)
(4.5)
i.e. h satisfies local individual faimess constraint as long as E/IE=-//V/(=)]I < xx On the other hand, the global IF constraint necessitates sup [|>)\/2\((²)] < co, ie., h is Lipschitz continuous with respect to the Mahalanobis distance.
The main advantage of this local notion of IF over its global counterpart is that the local definition concentrates on the input pairs with smaller fair distance and ignores those with larger distance. For example, in Figure I the edge-weights among Alice, Charlie, and Dave are much larger than among any other pairs (which have a weight of 0); therefore, our local notion enforces faimness constraint on the corresponding similar pairs, while ignoring (or being less stringent on) others. This prevents ovor-shno and consequently preserves accuracy while enforcing fairness as is evident from our real data experiments in Section
We now present our main theorem, which establishes that, under certain assumptions on the underlying hypothesis class and the distribution of inputs, the graph Laplacian regularizers (both unnormalized

---

and normalized random walk) enforce the local IF constraint (as defined in Definition in the limit. For our theory, we work with dx as the Mahalanobis distance introduced in Example in equation (2.2) along with 0 = 1/(20²) (ar is a bandwidth parameter which goes to 0 at an appropriate rate as + 00) and r = cc. All our results will be thorough for any finite 7 but with more tedious technical analysis. Therefore, our weight matrix W becomes:
E////
Wij (2 exp (- 20
(T (2, xxy) xy)" (x, (x)))))))))))))
(4.6)
The constant [2) od) for the normalization purpose and can absorbed into the penalty parameter A. We start by listing our assumptions:
Assumption 4.3 (Assumption on the domain). The domain of the inputs X a compact subset of Fd where d is the underlying dimension.
Assumption 4.4 (Assumption on the hypothesis). All functions f E F of the hypothesis class satisfy the following:
1. The tth derivative f()) is uniformly bounded over the domain X of inputs for E (0,
fou (x) 0 for all 0X, where 0X denotes the boundary of X.
Assumption 4.5 (Assumption on the density of inputs). The density p of the input random variable the domain X satisfies the following:
There exists Pmax < Do and Pmin > 0 such that, for all x E X, we have Puin S <p(x)= S Pmax- 1.2 of the density p are uniformly bounded on the domain X. The derivatives ]i0,112
Discussion on the assumptions Most of our assumptions (e.g., compactness of the domain, bounded derivatives of f or p) are for technical simplicity and are fairly common for the asymptotic analysis of graph regularization (see, e.g., Hein et al. [25] 33 and references therein). It is possible to relax some of the assumptions: for example, if the domain of inputs is unbounded, then the target function f and the density p should decay certain rate that observations far away will not be able to affect the convergence (e.g., sub-exponential tails). Part (2.) of Assumption (..4ioon[[4eeee [..4 can be relaxed if assume p(x) is 0 at boundary. However, do pursue these extensions further in this manuseript, as they are purely technical and do not add anything of significance to the main intuition of the result.
Theorem 4.6. Under Assumptions 4.3
4.5
we have:
1. If the sequence of bandwidths = On + such that no? - oo and Lunna is unnormalized Laplacian matrix, then
2
Lu - Exeo (f(x))
p(x)]
(4.7)
n²g²"
2. If the sequence of bandwidths = =o + such that (nod+4)/ (1/a)) cc and Lanw, is the normalized random walk Laplacian matrix, then:
P Unnemmn Ex ( V((x))
(4.8)
no?
where f = [f=)))]= Consequently, both Laplacian regularizers asymptotically enforce local IF,
The proof of the above theorem can be found in Appendix When we use a normalized random walk graph Laplacian matrix Larw,, regularizer, the regularizer does (asymptotically) penalize =
E [ the local IF constraint. Similarly, the un-normalized Laplacian matrix Lun.ny also enforces the same under Assumption 4.5 as:
E 10201/25[(()11 which, by Example 4.2 is equivalent to enforcing
E [1E-1//V
L (f(()
p(x)], where Pmin
inf p(x). p()).
(4.9)
Pmin
=Ex
Although both the Laplacian matrices enforce local IF, the primary difference between them is that the limit of the unnormalized Laplacian involves the density p(z), i.e., it upweights the high-density region (consequently stringent imposition of fairesss constraint), whereas it down-weights the under- represented/low density region. On the other hand, the limit corresponding to the normalized random walk Laplacian matrix does not depend on p(x) and enforces fairness constraint with equal intensity on the entire input space. We used both regularizers our experiments, comparing and contrasting their performance several practical ML problems.
7

---

Experiments
The goals of our experiments are threefold:
1. Exploring the trade-offs between post-processing for local IF with GLIF and post-processing with (global) IF constraints using our adaptation of the algorithm by Dwork al. (6) described in (2. Studying practical implications of theoretical differences between GLIF and GLIF-NRW, i.e., different graph Laplacians, presented in Section
3. Evaluating the effectiveness of GLIF in its main application, i.e., computationally light debiasing of large deep learning models such BERT.
The implementation of this work available at
5.1 Comparing GLIF and Global IF-constraints
For our first experiment, consider the sentiment prediction task [34] where goal is to classify words as having a positive or negative sentiment. The baseline model is a neural network trained with GloVe word embeddings [35]. Following Yurochkin al. [TT]. evaluate the model set of names and observe that it assigns varying sentiments to names. An individually fair model should assign similar sentiment scores to all names. Further, we observe that there is gap between average sentiments of names typical for Caucasian and African-American ethnic groups [36]. which violating group fairness. Yurochkin al. (IT) propose a fair metric learning procedure for this task using a side data set of names, and an in- processing technique for achieving individual fairness. We use their method obtain the fair metric and compare post-processing of the baseline model with GLIF, GLIF-NRW and the global IF-constraints method. The test set comprises 663 words from the original task and 94 names. For post-processing, no problem specific knowledge used. The resulting post-processed predictions for the original test set are used to evaluate accuracy, and the predictions on the names are used for evaluating fairness metrics. Even for this small problem, the global IF-constraints method, i.e., CVXPY (37] implementation of (2.3) takes 7 minutes to run. Due to the poor scalability of the global IF-constraints method, we can use it only for the study of this smaller data set and can not consider it for the large language model experiments in Section 5.2 For GLIF(-NRW) we implement the closed-for form solution (3.3) that takes less than a tenth of a second to run. See Appendix A for additional experimental details and runtime analysis.
We evaluate the fairness accurrcyy trade-oft's for a range of threshold parameters 7 (for GL.F and GLIF-NRW) and for range of Lipschitt-conntaatss I. (for IF-constraints) in Figure Figure (left) shows the standard deviation of the post-processed outputs on all names as a function of test accuracy on the original sentiment task. Lower standard deviations imply that all names received similar predictions, which is the goal individual fairness. Figure (center) visualizes group fairness and accuracy, i.e., difference in average name sentiment scores for the two ethnic groups. In this problem, individual fairness a stronger notion of fairness: achieving similar predictions for all names implies similar group averages, but not vice versa. Therefore, for this task, post-processing for individual fairness also corrects group disparities.
F-constraints
X
.ocosttriinss
X
violations
GUF
GUF GLF-NRW baseline
0.8
Names
Logit stc.
pace BOP
GUF violations for names
baseline
0.4
2
0.80
0.85
0.90
0.95
0.0
Test Accuracy
Test Accuracy
Fair distance
Figure 2: Sentiment experiment. Left: Trade-off between standard deviations of logits of names (measuring individual fairness) and accuracy. Center: Trade-off between race gap (measuring group fairness) and accuracy. Right: Frequencies of violations of the global IF constraints after applying GLIF, constraints corresponding to names, and GLIF's globall IF constraint violations for names.

---

In both settings, GLIF and GLIF-NRW achieve substantially better faireess metrics for the same levels of test accuracy in comparison to the IF-constraints method. To understand the reason for this, we study which global IF constraints are violated after applying the GLIF method in Figure 2 (right). Corresponding to the unique pairs of words our test set, there are n(n 1)/2 unique constraints in (2.3), and the global IF-constraints method satisfies all of them by design. Each constraint (i.e., each pair words) corresponds to a fair distance, which is small for (under the fair metric) similar words and large for dissimilar words. We bin the constraints by fair distance and present the proportion of global IF constraints violated after applying the GLIF method for each bin in the histogram in Figure (right). Here, set the Lipschitz-constant L in 2.3 to L 2.25 corresponding to a 89.4% accuracy of the IF-constraints method and show global IF constraint violations of GLIF corresponding to 95% accuracy in blue. This means that use strong global IF constraints and use a setting of the GLIF method which maintains most of the accuracy, which would not be possible using the IF-constraints method. GLIF does violate any constraints corresponding to small fair distances, i.e., it satisfies IF on similar individuals, while violating many large fair distance constraints. This can be seen basically all constraint violations (blue) distances of greater or equal 6. This demonstrates the effect of enforcing local individual fairness from our theoretical analysis in Section 4 At the same time, we display frequency of constraints that correspond to pairs of names in orange, where we can see that almost all constraints corresponding names occur at small fair distances of smaller or equal to This is expected in this task because we consider all names similar, so fair distances between them should be small. We can see that the distributions of constraint violations after applying GLIF (blue, right) and names (orange, left) are almost disjoint. We mark all global IF constraint violations after applying GLIF that correspond to names in green, and observe that there are none. Summarizing, GLIF ignores unnecessary (in the context of this problem) constraints allowing it to achieve higher accuracy, while satisfying the more relevant local IF constraints leading improved fairness.
large fair
Regarding the practical differences between GLIF and GLIF-NRW, in Figure 2 (left) GLIF has smaller standard deviations on the name outputs, but in in Figure 2 (center) GLIW-NRW achieves lower race gap. In Theorem 4.6 we showed that GLIF penalizes fairesss violations in high density data regions stronger. As a result, GLIF may favor enforeing similar outputs in the high density region causing lower standard deviation, while leaving outputs nearly unchanged in the lower density region, resulting in larger race gaps. GLIF-NRW weights all data density regions equally, i.c. is less likely to miss a small subset of names, but is less stringent in the high density regions.
5.2 Post-processing for Debiasing Large Language Models
Large language models have achieved impressive results on many tasks: however, there is also significant evidence demonstrating that they are prone to biases (4), (38). [39]. Debiasing these models remains largely an open problem: most in-processing algorithms are not applicable or computationally prohibitive due to large and highly complex model architectures, and challenges in handling text inputs. Even if an appropriate in processssing algorithm arises, significant environmental impact due to re-training unavoidable (4). (16). In our experiments, we evaluate effectiveness of GLIF as simple post-processing technique to debias BERT-based models for text classification. Another possible solution to fine-tune BERT with an in-processing technique as was done by Yurochkin al. [2]. The two approaches are not directly comparable: fine-tuning with SenSel [12] requires knowledge of the model parameters, alleviates only part of the computational burden, and
1.00
1.0
Prediction Canolaencyy
Prodiction Consietency
0.9
GLIF
0.8
GUF
GLIF-NRW SenSel
GUF-ARW
0.7
SenSel
Baselino
Baseline
0.50
0.55
0.60
0.65
0.70
0.75
0.80
0.85
0.50
0.55
0.60
0.65
0.70
0.75
0.80
Balanced Test Accuracy
Balanced Test Accuracy
Figure 3: Accuracy-Consisteney trade-off's for Bios (left) and Toxicity (right).

---

Table 1: Results for the Bios task.
Table 2: Results for the Toxicity task.
Method
Test Acc.
Pred. Consist.
Method
Test Acc.
Pred. Consist.
Baseline
0.846 0.003
0.942 + 0.002
Baseline
0.809 + 0.004
0.614 + 0.013
GLIF
0.830 + 0.004
0.986 + 0.002
GLIF
0.803 + 0.003
0.835 + 0.012
GLIF-NRW
0.834 + 0.003
0.988 + 0.002
GLIF-NRW
0.803 0.003
0.844 + 0.013
SenSEI
0.843 + 0.003
0.977 + 0.001
SenSEI
0.791 + 0.005
0.773 + 0.043
has more stringent requirements on the fair metric, while post-processing with GLIF is transductive, ie., it requires access to unlabeled test data (see extended discussion in Section 2.1
We replicate the experiments of Yurochkin et al. [12) on Bios [40] and Toxicity data sets They use the approach of Mukherjee et al. [19] for fair metric learning which we reproduce. We refer to the Appendix B. I of [12] for details. In both tasks, following [12), we quantify performance with balaneed accuracy due to class imbalance, and measure individual fairness via prediction consistency, i.e. the fraction of test points where the prediction remains unchanged when performing task-specific input modifications. For implementation details, see Appendix A. In Appendix A.4, we analyze the runtime and distinguish between the closed-form and coordinate descent variants of GLIF.
In Bios, the goal predict the occupation person based on their textual biography. Such models can be useful for recruiting purposes. However, due to historical gender bias in some occupations, the baseline BERT model learns to associate gender pronouns and names with the corresponding occupations. Individual fairness is measured with prediction consistency with respect to gender pronouns and names alterations. prediction is considered consistent it is the same after swapping the gender pronouns and names. We present the fairnes--accuran trade-off in Figure 3 (left) (left) for range of threshold parameters т, and compare performance based on hyperparameter values selected with validation data in Table Both GLIF and GLIF-NRW noticeably improve individual fairness measured with prediction consistency, while retaining most of the accuracy.
In Toxicity, the task is to identify toxic comments-on an important tool for facilitating inclusive discussions online. The baseline BERT model learns associate certain identity words with toxicity (e.g., "gay") because they are often abused in online conversations. The prediction consistency is measured with respect changes to identity words in the inputs. There are 50 identity words, e.g.. "gay". "muslim", "asian", etc. and prediction is considered consistent if it is the same for all 50 identities. We present the trade-off plots in Figure 3 (right) and compare performance in Table P (right). Our methods reduce individual biases in BERT predictions. We note that in both Toxicity and Bios experiments, we observe no practical differences between GLIF and GLIF-NRW.
Summary and Discussion
We studied post-processee proteesocesng methods for enforcing individual fairness. The methods provably enforce a local form of and scale readily to large data sets. We hope this broadens the appeal of IF by (i) alleviating the computational costs of operationalizing IF and (ii) allowing practitioners to use off-the-shelf models for standard ML tasks. We also note that it is possible to use our objective for in-processing.
We conclude with two warnings: First, enforcing any algorithmic fairness definition does not guarantee complete fairness from the perspective of the user. The problem-specific meaning of fairness is often hard to encode exactly with mathematical fairness definition. Second, while local individual fairness is reasonable choice in many applications, this choice should be understood and verified by the practitioner depending on the situation.
BBased the Kaggle "Toxic Comment Classification Challenge".
10

---

Acknowledgments and Disclosure of Funding
This note is based upon work supported by the National Science Foundation (NSF) under grants no. 1916271, 2027737, and 2113373 and supported by the German Research Foundation (DFG) under Germany's s Excellence Strategy EXC-2117-390829877 recommendations expressed in this note are those of the authors and do not necessarily reflect the views of the NSF nor the DFG.
Any opinions, findings, and conclusions or
References
[1] S. Barocas and A. D. Selbst, "Big data's disparate impact," Calif. L. Rev. vol. 104, p. 671, 2016.
[2] J. Larson, J. Angwin, L. Kirchner, and S. Mattu, "Howw we examined racial discrimination in auto insurance prices." " ProPublica, 2017.
[3] J. Buolamwini and T. Gebru, "Gender shades: Intersectional accuracy disparities in commercial gender classification," in Conference on faimess, accountability and transparency, PMLR, 2018, pp. 77-91.
[4] E. M. Bender, T. Gebru, A. McMiilan-Major and S. Shmitchell, "On the dangers of stochastic par- Can language models be too big?" In Proceedings of the 2021 ACM Conference Fairness, Accountabiliry, and Transparency, 2021, pp. 610-623.
[5] A. Chouldechova and A. Roth, "A snapshot of the frontiers of fairness in machine learning," Communi- cations of the ACM, vol. 63, no. 5. pp. 82 89, 2020.
[6] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel, "Fairness through awareness," Proceedings
of the 3rd innovations in theoretical computer science conference, 2012. pp. 214-226.
[7]
D. C. Hsia, "Credit scoring and the equal credit opportunity act," Hastings LJ, vol. 30, p. 371, 1978.
[8] Bertrand and S. Mullainathan. "Are emily and greg more employable than lakisha and jamal? a field experiment on labor market discrimination," American Economic Review, vol. 94, no. 4, pp. 991-1013, 2004.
[9] W. Fleisher, "What's fair about individual fairness?" Available at SSRN 3819799, 2021.
[10] C. Jung, M. Kearns, S. Neel, A. Roth, L. Stapleton, and Z. S. Wu, "An algorithmic framework for faimess elicitation," arXiv preprint arXiv: 10660, 2019.
[11] M. Yurochkin, A. Bower, and Y. Sun, "Training individually fair ML models with sensitive subspace robustness," in International Conference on Learning Representations (ICLR), 2020.
[12] M. Yurochkin and Y. Sun, "Sensei: Sensitive set invariance for enforcing individual fairness," " in Interna-
tional Conference on Learning Representations (ICLR), 2021.
[13] A. Vargo, F. Zhang, M. Yurochkin, and Y. Sun, "Individually fair gradient boosting," in International Conference Learning Representations (ICIR), 2021.
[14] J. Devlin, M.W. Chang, K. Lee, and K. Toutanova, "BERT: Pre-training of deep bidirectional trans- formers for language understanding, arxiv," in Proc. Conference the North American Chapter of the Association for Computational Linguistics (ACL), 2018.
[15] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al., "Language models are few-shot learners," " arXiv preprint S.di::2005.1166. 2020.
[16] E. Strubell, A. Ganesh, and A. McCallum, "Energy and policy considerations for deep learning in nip."
in 57th Annual Meeting of the Association for Computational Linguistics, 2019.
[17] O. Chapelle, B. Schölkopf, and A. Zien, Eds., Semi- Supi--Sperr Learning. Cambridge, Mass: MIT Press, 2006.
[18] C. IIvento, "Metric Learning for Individual Fairness," in 1t Symposium on Foundations of Responsible Computing (FORC 2020), Leibniz International Proceedings in Informatics (LIPles), vol. 156, Dagstuhl, Germany: Schloss Dagstuhl- -eituulll--einiz---i ZZntrru für Informatik, 2020.
[19] D. Mukherjee, M. Yurochkin, M. Banerjee, and Y. Sun, "Two simple ways to learn individual fairness metrics from data," in International Conference on Machine Learning (ICML), 2020.
[20] M. P. Kim, A. Ghorbani, and J. Zou, "Multiaccuracy: Black-box post-processing for faimess in classifica- tion," in Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, 2019.
[21] P. K. Lohia, K. N. Ramamurthy, M. Bhide, D. Saha. K. R. Varshney, and R. Puri. "Bias mitigation post- post-processing for individual and group faimess,"" " in IEFE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2019, pp. 2847-2851.
[22] P. Lohia, "Priority- -ased prot-procs bias mitigation for individual and group fairness." arXiv preprint
arXiv:2102.000 22221022..0112222 2021.
[23] D. Wei, K. N. Ramamurthy, and P. Calmon, "Optimized score transformation for fair classification," in International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
11

---

[24]
D. Spielman. "Spectral graph theory." Combinatorial scientific computing, no. 18, 2012.
[25] M. Hein, J.-Y. Audibert, and U. v. Luxburg, "Graph laplacians and their convergence on random neighhorhood graphs.," Journal of Machine Learning Research, vol. 8, no. 6, 2007.
[26]
R. R. Coifman and S. Lafon, "Diffusion maps." Applied and computational harmonic analysis, vol. 21,
no. 2006.
[27]
D. Zhou and B. Schölkopf, "A regularization framework for learning from graph data," in ICML 2004 Workshop on Statistical Relational Learning and Its Connections Other Fields (SRL 2004), 2004,
pp. 132 137.
[28] M. Belkin, I. Matvoeva, and Niyogi, "Regularization and semi-supervised learning large graphs." in International Conference on Computational Learning Theory, Springer, 2004, pp. 624-638.
[29]
Smola and R. Kondor, "Kernels and regularization on graphs." Learning theory and kernel machines, Springer, 2003,
[30] P. Lahoti, P. Gummadi, and Weikum, "Ifair: Learning individually fair data representations for algorithmic decision making," in 2019 ieee 35th international conference on data engineering (icde), IEEE, 2019, pp. 1334-1345.
[31] J. Kang, J. He, R. Maciejewski, and H. Tong, "Inform: Individual fairness on graph mining," in Pruceed- ings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020,
pp. 379-3799359 -899.
[32]
S. J. Wright, "Coordinate descent algorithms," Mathematical Progranming, 2015.
[33] M. Hein, J.-Y. Audibert, and U. Von Luxburg. "From graphs to manifolds-weak and strong pointwise consistency of graph laplacians," in International Conference Computational Learning Theory,
Springer, 2005.
[34] M. Hu and B. Liu, "Mining and summarizing customer reviews." in Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, 2004.
[35] J. Pennington, Sacher, and C. D. Manning, "Glove: Global vectors for word representation," in Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), 2014, pp- 1532-1543.
[36] A. Caliskan, J. J. Bryson, and A. Narayanan, "Semantics derived automatically from language corpora contain human-like biases," Science, 2017.
[37] S. Diamond and S. Boyd, "Cvxpy: A python-embeddded modeling language for convex optimization," "
The Journal of Machine Learning Research, vol. 17, no. 1, pp. 2909-2909990 2913,991, 2016.
[38] K. Kurita, N. Vyas, A. Parcek, A. W. Black, and Y. Tsvetkov, "Measuring bias in contextualized word representations." in First Workshop on Gender Bius in Natural Language Processing. 2019.
[39] M. Nadeem, A. Bethke, and S. Reddy, "Stercoset: Mcasuring stereotypical bias in pretrained language models," arXiv preprint ar 200:44004 200400940000 2020.
[40] M. De-Arteaga, A. Romanov, H. Wallach, J. Chayes, C. Borgs, A. Chouldechova, S. Geyik, K. Kenthapadi, and A. T. Kalai, "Bias bios: A case study of semantic representation bias in high-stakes setting." in Proceedings of the Conference on Fairness, Accountability, and Transparency (ACM FAceT), 2019.
[41] L. Dixon, J. Li, J. Sorensen, N. Thain, and L. Vasserman, "Measuring and mitigating unintended bias in text classification," " in Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, 2018.
[42] B. Sen, A gentle introduction empirical process theory and applications, 2018 8.
12


Reviews:
[{"review_id": "uuB3bhZihn1", "reviewer": "Reviewer_9cRG", "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.\n\nIn 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. \n\nIn line 72, the experiments are conducted to reduce bias of fine-tuned Bert. Is there any assumption that the fine-tuned Bert is biased?  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "See above.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "YcMVozxCWgj", "reviewer": "Reviewer_bTqy", "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. \n\nThe 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). \n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nAlthough 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). \n\nAnother 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. \n\n-----------\nUpdate: 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately discuss the societal impact of this work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "M1MOIa1tJ0", "reviewer": "Reviewer_LaWU", "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n(1) This paper considers a practical scenario and is well-organized.\n(2) This paper is well-motivated, and utilizing graph Laplacian to promote individual fairness is a reasonable way despite the lack of novelty.\n(3) Compared to the chosen baselines, the proposed GLIF achieves better performance in different ways.\n\nWeaknesses:\n(1) Some techniques proposed in this paper lack novelty and motivation.\n(2) This paper lacks the study on related work, which should have been included to enrich the baselines for a comprehensive investigation.\n(3) Some potential limitations are not well considered and presented.\n\nDetails:\nIn 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:\n(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?\n(2) What is the exact definition of the bandwidth here? In the paper, is $h$ a function or a bandwidth parameter?\n\n[1] Lahoti, P., Gummadi, K. P., & Weikum, G. (2019). Operationalizing individual fairness with pairwise fair representations. arXiv preprint arXiv:1907.01439.\n\n[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).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Did not see any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5 hours."}, "extra_text": {}}, {"review_id": "5XFpKNCH7pk", "reviewer": "Reviewer_63Qx", "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nA few questions:\n\n(1) What is the impact of the parameters theta and tau on the behavior of the method?\n\n(2) What is the conceptual relation of the Laplacian method to the alternate definition of individual fairness proposed in [36]? \n\n(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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}]

Author rebuttal:

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)