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, yurocckioiih1n1 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( 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 (dx
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 W.y 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:
argmin 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. 0 for i + j is the degree matrix corresponding to W. Then known
where Da ンド= Wij. Dig identity is:
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-dimeessonall 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../Di.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==)
(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) Zy)" (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 [.44 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 GUF-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 processssinng 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- -hgstuhl-Leibniz--- Leibniz-iiiiiie 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 2004.0940000 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": "xWYlhTRYvPY", "reviewer": "Reviewer_YBcz", "summary": "This paper proposes a post-processing method GLIF in enforcing individual fairness. The key idea is to build a similarity graph based on an oracle fair metric and then apply laplacian regularization on model output and the similarity graph. The optimization problem is strongly convex and reveals a linear equation in obtaining global minima. Coordinate descent is use to scale up the computations. Moreover, the paper introduces extenstion to the inductive setting, as well as theoretical analysis on guarantees of enforcing individual fairness.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "This paper proposes a post-processing method GLIF in enforcing individual fairness. The key idea is to build a similarity graph based on an oracle fair metric and then apply laplacian regularization on model output and the similarity graph. The optimization problem is strongly convex and reveals a linear equation in obtaining global minima. Coordinate descent is use to scale up the computations. Moreover, the paper introduces extenstion to the inductive setting, as well as theoretical analysis on guarantees of enforcing individual fairness. Please see my concerns below.\n\n- Limited novelty in methodology. Laplcian regularization is not a new technique in enforcing individual fairness (see [1] and [2]). Moreover, the technical content before section 3.2.2 is almost identical to the 'debiasing the mining result' method described in [2]. I would say the main differences between method in [2] and GLIF lie in the different strategy of building similarity graph and the different solver for the linear equation (coordinate descent vs. conjugate gradient). The novelty of this paper is more in the exntension of inductive setting and theoretical analysis.\n\n- For inductive setting, is the unseen point included in the similarity graph? If so, is it still a good way to call it inductive setting (since we already have this node in the similarity graph)? If not, how much does it cost to append the graph with the new unseen point?\n\n- The authors mention that GLIF can scale up to large pretrained LM like BERT. What is the running time of debiasing such large LM? It should be a key part to support section 3.2.2.\n\nOverall, I think the theoretical analysis of GLIF is interesting but the current version is not ready for a publication due to limited novelty in methodology as well as some missing details.\n\n[1] Lahoti, Preethi, Krishna P. Gummadi, and Gerhard Weikum. \"Operationalizing individual fairness with pairwise fair representations.\" arXiv preprint arXiv:1907.01439 (2019).\n\n[2] Kang, Jian, Jingrui He, Ross Maciejewski, and Hanghang Tong. \"Inform: Individual fairness on graph mining.\" In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 379-389. 2020.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "qkmpGW52qtE", "reviewer": "Reviewer_3BRp", "summary": "The paper proposes to relax the notion of individual fairness to a notion of \"local\" individual fairness, in which similar outcomes are enforced for pairs of instances whose similarity exceeds a given threshold. The authors propose to achieve this using graph Laplacian regularization and provide several extensions of this method, such as to the multiclass setting.  The experiments provide good support to the proposed method compared to the traditional notion of individual fairness.", "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 paper proposes to relax the notion of individual fairness to a notion of \"local\" individual fairness, in which similar outcomes are enforced for pairs of instances whose similarity exceeds a given threshold. Note that by contrast, individual fairness by itself is often defined using Lipschitz continuity over the entire domain of instances. Because of this thresholding rule, the authors encode similarity as a graph over instances and propose to achieve individual fairness by forcing the predictions to be smooth within the graph (i.e. nearby nodes receive similar predictions). This is achieved using graph Laplacian regularization. The authors motivate the choice of the regularization in two ways: (1) by computing it exactly for the unnormalized Laplacian matrix and showing that it corresponds to the intuitive notion of individual fairness (Equation 3.2), and (2) by proving that when the similarity/distance is measured using the Mahalanobis metric, enforcing Laplacian regularization leads to a limiting form of local individual fairness. \n\nOverall, the paper is well-written and the authors have studied several extensions of the proposed method, such as by solving it using coordinate descent and the multiclass setting. The experiments also provide good support to the proposed method compared to the traditional notion of individual fairness by showing that it yields better accuracy subject to the same level of fairness. They also demonstrate that this improvement comes from relaxing the fairness constraints for dissimilar instances. \n\nThe only major downside that I could see is that the algorithm does not operate naturally in the inductive setting. The authors mention that one can use standard techniques that transform transductive methods to inductive, but I think they are not well-motivated. For example, does the predictor need to keep track of all instances that are observed to ensure that similar instances continue to receive similar outcomes in the future? If yes, this is quite expensive. If not, individual fairness may not be guaranteed. However, given that this is a post-processing approach that works well in the transductive setting, I think it is a worthwhile contribution to the community. \n\nSome minor comments:\n- The captions should be sufficient to understand the tables and figures. In the present form, they do not provide any information whatsoever besides being points to what is mentioned in the main text. \n- In Definition 4.1, y and X are both instances. Is this correct? If yes, please use similar symbols (e.g. x1 and x2) to avoid confusion. \n- Typo in line 165: \"is not immediately scalable\" --> \"it is not immediately scalable\". \n\n\n============= \nPost Rebuttal:\nI am fine with the author response and will keep my score as is. In light of the other reviews and the discussion, I suggest that the authors add the missing references highlighted by reviewer YBcz with a discussion of similarities/differences and adding a bit more discussion on how to control complexity in the inductive setting.\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": "3"}, "extra_text": {}}, {"review_id": "bbwWL4E17Ht", "reviewer": "Reviewer_q7wC", "summary": "The paper explores individual fairness post-processing as a graph smoothing problem. Specifically, the paper considers an atypical \"local\" individual fairness constrain (locally Lipschitz) and uses graph Laplacian regularization in the minimization objective to account for individual fairness.\n\nMain Contributions:\n - Introduces a minimization problem with graph Laplacian regularization for local individual fairness, for Euclidean + KL Bregman generalization.\n - Proposes coordinate descent to optimize the minimization problem.\n - Thm 4.6: Proves that under assumptions, the specified Laplacian regularizer(s) asymptotically enforce weak local individual fairness.\n - Experiments to compare the normalized/un-normalized regularizers and baselines.", "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": "Overall, the paper is of good quality with an interesting exploration of the relaxation of the typical individual fairness problem. There are only minor issues regarding the clarity of the writing.\n\nOriginality & Significance:\nThe paper provides a novel outlook into the individual fairness problem through a logical weakening of the typical constraint, and then provides an algorithm for their optimization problem. The experiments provided further shows that weakening of the constraints and their method provides a useful alternative than prior work.\n\nQuality & Clarity: The theoretical and experimental results seem technically sound. The paper is mostly clear, except for parts of Sec 3 (see below).\n\nStrengths:\n - The introduced local individual fairness constraint is well motivated.\n - The method of coordinate descent + graph Laplacian regularization (and the KL/Bregman generalization)\n - Thm 4.6 identifying the changes caused by normalization is very nice.\n\nSuggestions/Weaknesses/Questions:\n - Sec 2.1's title and initial text says post-processing, but in-processing algorithms are also discussed.\n - Sec 3.2.4: there seems to be ambiguity with $ y $ in (3.8). Especially with the last subscript $ y_{j} $ (which I believe should be $ \\tilde{y}_{j} $ ?). Relabelling would help to make this clearer.\n - $ \\tau $ ambiguity. It would be worth changing $ \\tau $ in (2.2) or in Sec 3.2.4\n - There also seems be a bit of mixed notation regarding double indices subscripts, i.e., \"ij\" vs \"i,j\" (the SI also seems to be the opposite of that presented in Sec 3.2.4).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and societal impact adequately addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Jm0veiSq-Q0", "reviewer": "Reviewer_yCJc", "summary": "In this paper, the authors consider the problem of enforcing individual fairness via post-processing. In particular, the authors characterize the post-processing of individual fairness into a graph smoothing problem and propose a novel individual fairness notion (Definition 4.1 Local Individual Fairness), as well ways to achieve it (graph Laplacian regularizers, GLIF and GLIF-NRW). Theoretical and empirical studies are also presented.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 post-processing way of achieving individual fairness is an interesting topic. Overall, the paper is relatively well-written and the assumptions, as well as results, are clearly presented. It would be better if the authors can further clarify the following points:\n\n1. What is the exact difference between \"global\" and \"local\" individual fairness constraints?\n\n  I understand the fact that Dwork et al. (2011) is enforcing the Lipschitz condition with one single parameter $L$ (which I would assume is the \"global\" sense of IF). As mentioned in the paper, this way of projecting the prediction is sub-optimal. If I understand correctly, the proposed GLIF regularizer (as in Equation 3.1) is in essence a weighted sum of the pairwise difference between new outputs. Some additional intuitions/insights into the advantage of the proposed method would be really helpful. What exactly is the localness the paper is mentioning? Why local IF is better than global IF in terms of the two drawbacks of Dwork et al. (2011)?\n\n2. Notation in Definition 4.1\n\n  The notation is quite confusing. Based on the intuition of the definition, $y$ here is not target, but another instance in $\\mathcal{X}$ (if I understand correctly). Please kindly comment on this to avoid misunderstanding.\n\n---\n### Post-rebuttal\n\nIn the rebuttal, the authors resolved my concern. In light of this, I update my evaluation from 5 to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The applicability of local IF (which can be viewed as a relaxation of IF) really depends on the problem setting, which, just like mentioned in the paper, should always be considered by the practitioners.\n\nMinor typo: line 210, Figure 2 --> Figure 1.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a post-processing method for enforcing individual fairness via graph-based smoothness. All four reviewers ultimately recommended acceptance. The main concern was novelty, which was partially (but not completely) addressed in the author response, but was not deemed significant enough to prevent acceptance.

Please be sure to make any changes that have been promised to the reviewers, and seriously consider attempting to address any other issues that they might have raised, in particular YBcz's novelty concern (by being careful with citations and the relationship to prior work).
Decision: Accept (Poster)