# iFlipper: Label Flipping for Individual Fairness

Hantian Zhang∗ Georgia Institute of Technology<EMAIL_ADDRESS>,
Ki Hyun Tae∗ KAIST<EMAIL_ADDRESS>,  Jaeyoung Park  KAIST
<EMAIL_ADDRESS>,  Xu Chu  Georgia Institute of Technology
<EMAIL_ADDRESS>and  Steven Euijong Whang  KAIST<EMAIL_ADDRESS>
###### Abstract.

As machine learning becomes prevalent, mitigating any unfairness present in
the training data becomes critical. Among the various notions of fairness,
this paper focuses on the well-known individual fairness where similar
individuals must be treated similarly. While individual fairness can be
improved when training a model (in-processing), we contend that fixing the
data before model training (pre-processing) is a more fundamental solution. In
particular, we show that label flipping is an effective pre-processing
technique for improving individual fairness. Our system iFlipper solves the
optimization problem of minimally flipping labels given a limit to the number
of individual fairness violations, where a violation occurs when two similar
examples in the training data have different labels. We first prove that the
problem is NP-hard. We then propose an approximate linear programming
algorithm and provide theoretical guarantees on how close its result is to the
optimal solution in terms of the number of label flips. We also propose
techniques for making the solution to the linear programming more optimal
without exceeding the violations limit. Experiments on real datasets show that
iFlipper significantly outperforms other pre-processing baselines in terms of
individual fairness and accuracy on unseen test sets. In addition, iFlipper
can be combined with in-processing techniques for even better results.

∗Equal contribution and co-first authors

PVLDB Reference Format:
Hantian Zhang, Ki Hyun Tae, Jaeyoung Park, Xu Chu, Steven Euijong Whang.
PVLDB, 14(1): XXX-XXX, 2020.
doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-NC-ND
4.0 International License. Visit https://creativecommons.org/licenses/by-nc-
nd/4.0/ to view a copy of this license. For any use beyond those covered by
this license, obtain permission by emailing<EMAIL_ADDRESS>Copyright is held
by the owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097.
doi:XX.XX/XXX.XX

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
https://github.com/khtae8250/iFlipper.

##  1\. Introduction

Machine learning (ML) impacts our everyday lives where applications include
recommendation systems (chaney2018algorithmic), job application
(dastin2018amazon), and face recognition (buolamwini2018gender).
Unfortunately, ML algorithms are also known to reflect or even reinforce bias
in the training data and thus make unfair decisions (barocas2016big;
whang2021responsible). This issue draws concerns from both the public and
research community, so algorithms have been proposed to mitigate bias in the
data and improve the fairness of ML models.

There are several prominent notions of fairness, and we focus on individual
fairness (dwork2012fairness), which states that similar individuals must be
treated similarly. Suppose that two applicants are applying to the same
school. If the two applicants have similar application materials, then it
makes sense for them to obtain the same or similar outcomes. Likewise if two
individuals are applying for a loan and have similar financial profiles, it is
fair for them to be accepted or rejected together as well. In addition to
individual fairness, the other prominent fairness notions include group
fairness and causal fairness. Group fairness (zafar2017fairness;
agarwal2018reductions; zhang2021omnifair) focuses on the parity between two
different sensitive groups (e.g., male versus female), and causal fairness
(kusner2017counterfactual) looks at fairness from a causal perspective (e.g.,
does gender affect an outcome?). These are orthogonal notations of fairness
and do not capture the individual fairness we focus on.

How can one improve a model’s individual fairness? There are largely three
possible approaches: fixing the data before model training (pre-processing),
changing the model training procedure itself (in-processing), or updating the
model predictions after training (post-processing). Among them, most of the
literature focuses on in-processing (DBLP:conf/iclr/YurochkinBS20;
yurochkin2021sensei; vargo2021individually) and more recently pre-processing
techniques (pmlr-v28-zemel13; ifair; pfr2019). We contend that pre-processing
is important because biased data is the root cause of unfairness, so fixing
the data is the more fundamental solution rather than having to cope with the
bias during or after model training. The downside of pre-processing is that
one cannot access the model and has to address the bias only using the
training data. Due to this challenge, only a few pre-processing techniques for
individual fairness have been proposed, which we will compare with in the
experiments.

We propose label flipping as a way to mitigate data bias for individual
fairness and assume a binary classification setting where labels have 0 or 1
values. Given a training set of examples, the idea is to change the labels of
some of the examples such that similar examples have the same labels as much
as possible. Which examples are considered similar is application dependent
and non-trivial and can be learned from input data (ilvento2020metric;
fairmetric; pmlr-v119-mukherjee20a) or obtained from annotators (e.g.,
humans). This topic is important for individual fairness, but not the focus of
this work where we assume the criteria is given as an input. For example, one
may compute the Euclidean distance between two examples and consider them
similar if the distance is within a certain threshold. As the training set
becomes more individually fair, the trained model becomes fairer as well (see
Section 4.2). Our label flipping approach is inspired by the robust training
literature of learning from noisy labels (DBLP:journals/corr/abs-2007-08199)
where the labeling itself may be imperfect. The standard approach for handling
such labels is to ignore or fix them (DBLP:conf/icml/SongK019). In our
setting, we consider any label that reduces individual fairness as biased and
would like to fix it.

We can use a graph representation to illustrate label flipping as shown in
Figure 1. Each node represents a training example, and its color indicates the
original label (black indicates label 1, and white indicates 0). Two similar
nodes (defined in Section 2.1) are connected with an edge, and a violation
occurs when an edge is connecting two nodes with different labels. In Figure
1, there are four nodes where only the nodes 1, 2, and 3 are similar to each
other. Each edge also has an associated weight, which reflects the similarity
of the two nodes. For simplicity, let us assume that all weights are 1. We can
see that there are two “violations” of fairness in this dataset: (1,2) and
(1,3) because there are edges between them, and they have different colors.
After flipping the label of node 1 from 1 to 0, we have no violations.

Figure 1. Label flipping example for individual fairness using a graph
representation. Two similar nodes have an edge, and color indicates the label.
By flipping the label of node 1, all pairs of similar nodes have the same
label, which is considered individually fair.

Our key contribution is in formulating and solving a constrained label
flipping problem for the purpose of individual fairness. Just like in a robust
training setup, we assume labelers can make labeling mistakes in a biased
fashion. Here the effective solution is to debias the labels by flipping them.
One consequence of label flipping is an accuracy-fairness trade-off where the
model’s accuracy may diminish. As an extreme example, if we simply flip all
the labels to be 0, then a trained model that only predicts 0 is certainly
fair, but inaccurate to say the least. Even if we carefully flip the labels,
we still observe a trade-off as we detail in Section 4.2. We thus formulate
the optimization problem where the objective is to minimize the number of
label flipping while limiting the total error, which is the total degree of
the individual fairness violations (see Definition 2). The optimization can be
formally stated as an instance of mixed-integer quadratic programming (MIQP)
problem, and we prove that it is NP-hard. We then transform the problem to an
approximate linear programming (LP) problem for efficient computation.
Interestingly, we show that our LP algorithm has theoretical guarantees on how
close its result is to the optimal solution in terms of the number of flips
performed. We then further optimize the solution given by the LP algorithm to
reduce the number of flips while ensuring the total error does not exceed the
given limit.

We call our approach iFlipper and empirically show how its label flipping
indeed results in individually-fair models and significantly outperforms other
pre-processing baselines on real datasets. In particular, the state-of-the-art
baselines (ifair; pfr2019) use representation learning to place similar
examples closer in a feature space. We show that iFlipper has better accuracy-
fairness trade-off curves and is also significantly more efficient. We also
compare iFlipper with baselines (e.g., greedy approach and k-means clustering)
for solving the optimization problem and show that iFlipper is superior.
Finally, we demonstrate how iFlipper can be integrated with in-processing
techniques (DBLP:conf/iclr/YurochkinBS20) for even better results. We release
our code as a community resource (github).

The rest of the paper is organized as follows.

  * $\bullet$

We formulate the label flipping optimization as an MIQP problem and prove that
it is NP-hard (Section 2).

  * $\bullet$

We propose iFlipper, which solves this problem by converting it into an
approximate LP algorithm that has theoretical guarantees and present an
additional optimization to further improve the solution given by the LP solver
(Section 3).

  * $\bullet$

We evaluate iFlipper on real datasets and show how it outperforms other pre-
processing baselines and can be integrated with in-processing techniques for
better results (Section 4).

##  2\. Problem Definition

###  2.1. Preliminaries

We focus on a _binary classification_ setting, and assume a training dataset
$\mathsf{D}$ = $\\{(x_{i},y_{i})\\}_{i=1}^{n}$ where $x_{i}$ is an example,
and $y_{i}$ is its label having a value of 0 or 1. A binary classifier $h$ can
be trained on $\mathsf{D}$, and its prediction on a test example $x$ is
$h(x)$.

Individual Fairness (dwork2012fairness) states that similar individuals must
be treated similarly. The criteria for determining if two examples are similar
depends on the application, and we assume it is given as input, though
research on how to automatically discover such similarity measures exists
(ilvento2020metric; fairmetric; pmlr-v119-mukherjee20a). For example, for each
$x$, we may consider all the examples within a certain distance to be similar.
Alternatively, we may consider the top-$k$ nearest examples to be similar. In
our work, we assume as input a given similarity measure, which can be applied
on the training set to produce a similarity matrix
$W_{ij}\in\mathbb{R}^{n\times n}$ where $W_{ij}>0$ if and only if $x_{i}$ and
$x_{j}$ are deemed similar according to the measure. If $W_{ij}>0$, we set it
to be the similarity of $x_{i}$ and $x_{j}$, although any other positive value
can be used as well. In order to satisfy individual fairness, we introduce the
notion of individual fairness violation as follows.

###### Definition 0.

Individual Fairness Violation. Given a similarity matrix $W$ on a training
set, an individual fairness violation occurs when $W_{ij}>0$, but $y_{i}\neq
y_{j}$. The magnitude of the violation is defined to be $W_{ij}$.

###### Definition 0.

Total Error. Given a similarity matrix $W$, the total error is the sum of all
$W_{ij}$ values where $y_{i}\neq y_{j}$.

Our goal is to reduce the total error to be within a maximum allowed amount.

###### Definition 0.

m-Individually Fair Dataset. Given a similarity matrix $W$, a dataset is
considered m-individually fair if the total error is at most $m$.

A smaller $m$ naturally translates to an m-individually fair dataset that is
likely to result in a more individually fair model on the unseen test set as
we demonstrate in Section 4.2.

##### Incomplete Similarity Matrix

If we only have partial knowledge of the similarities, iFlipper can be
naturally adapted to utilize or fix the partial data. The straightforward
solution is to treat the partial similarity as if it is complete information
where the pairs with unknown similarities are not included in our optimization
formulation. Another solution is to “extrapolate” the partial similarity
matrix to reconstruct the full similarity matrix. For example, one can learn
similarity functions using the partial data. In this case, iFlipper’s
performance will largely depend on how accurate the learned similarity
function is.

Evaluating the Fairness of a Trained Model $h$. To evaluate the final
individual fairness of a trained model $h$, we compute the widely-used
consistency score (pfr2019) of model predictions on an unseen test set as
defined below. Here $W_{ij}$ is the similarity matrix on the unseen test set.

$\text{\em{Consistency
Score}}=1-\frac{\sum_{i}\sum_{j}|h(x_{i})-h(x_{j})|\times
W_{ij}}{\sum_{i}\sum_{j}W_{ij}}$

Intuitively, if the model is trained on an individually-fair dataset, the
predictions on the test set between similar individuals tend to be the same,
so the consistency score on the test set increases. In the extreme case, a
consistency score of 1 indicates that all similar pairs of test examples get
the same predictions from the model.

Local Sensitive Hashing. We construct a similarity matrix $W$ using locality
sensitive hashing (LSH) (Andoni2015falconn) instead of materializing it
entirely and thus avoid performing $O(n^{2})$ comparisons. We exploit the fact
that $W$ is sparse, because most examples are dissimilar. This approach is
similar to blocking techniques in entity resolution
(DBLP:books/daglib/0030287).

###  2.2. Label Flipping Optimization Problem

We define the label flipping optimization problem for individual fairness.
Given a training dataset $\mathsf{D}$ and a limit $m$ of total error allowed,
our goal is to flip the minimum number of labels in $\mathsf{D}$ such that it
becomes _m-individually fair_. This statement can be formalized as a mixed-
integer quadratic programming (MIQP) problem:

(1)
$\begin{split}\text{(MIQP)}\quad\min\quad&\sum_{i=1}^{n}{(y_{i}-y_{i}^{\prime})^{2}}\\\
\text{s.t.}\quad&\sum_{i=1}^{n}\sum_{j=1}^{n}W_{ij}(y_{i}-y_{j})^{2}\leq m\\\
&y_{i}\in\text{\\{0,1\\}},\forall i\end{split}$

where $y_{i}$ indicates an output label, and $y_{i}^{\prime}$ is its original
value. Intuitively, we count the number of flips ($(y_{i}-y_{i}^{\prime})^{2}$
= 1) while ensuring that the total error ($(y_{i}-y_{j})^{2}$ = 1 and
$W_{ij}>0$) is within the limit $m$. We call a solution feasible if it
satisfies the error constraints in Equation 1, but may or may not be optimal.

MIQP is an NP-hard problem in general, and we prove that our specific instance
of the MIQP problem is also NP-hard.

###### Theorem 4.

The MIQP problem in Equation 1 is NP-hard.

The full proof for Theorem 4 can be found in our technical report
(iflippertr). The key idea is to reduce the well-known NP-hard at most
$k$-cardinality $s$-$t$ cut problem (DBLP:journals/dam/BruglieriME04) to our
MIQP problem.

###  2.3. Baseline Algorithms

Our key contribution is to propose algorithms for the label flipping problem
that not only scales to large datasets, but also provides feasible and high-
quality solutions. We present three naïve algorithms that are efficient, but
may fail to produce feasible solutions. In comparison, our method in Section 3
always produces feasible solutions with theoretical guarantees.

Greedy Algorithm. The greedy algorithm repeatedly flips labels of nodes that
reduce the total error the most. The algorithm terminates if the total error
is $m$ or smaller, or if we cannot reduce the error anymore. For example,
suppose we start from the graph in Figure 1 where there are initially two
violations (recall we assume that $W_{ij}=1$ for all edges for simplicity) and
set $m$ = 1. We need to determine which label leads to the largest reduction
in error when flipped. We can see that flipping node 1 will reduce the total
error by 2 while flipping the other nodes does not change the total error.
Hence, the greedy algorithm flips node 1 to reduce the total error to 0 and
then terminates. While the greedy approach seems to work for Figure 1, in
general it does not always find an optimal result and may fail to produce a
feasible solution even if one exists. Consider the example in Figure 2 where
there is one violation between nodes 2 and 3. Again, we assume that $W_{ij}=1$
for all edges for simplicity. If we set $m$ = 0, the feasible solution is to
flip nodes 1 and 2 or flip nodes 3 and 4 together. Unfortunately, the greedy
algorithm immediately terminates because it only flips one node at a time, and
no single flip can reduce the error.

Figure 2. A graph where the greedy algorithm fails to find a feasible solution
with zero violations.

The computational complexity of the greedy algorithm is $O(n^{2})$ because we
flip at most $O(n)$ labels, and each time a label is flipped, we update the
total error of each neighbor of the node.

Gradient Based Algorithm. The second naïve approach is to use a Lagrangian
multiplier to move the error constraint into the objective function and solve
the problem via gradient descent. This approach is common in machine learning,
and the following equation shows the problem setup:

(2) $\begin{split}\text{(Lagrangian) }\min\text{
}&\sum_{i=1}^{n}{(y_{i}-y_{i}^{\prime})^{2}}+\lambda\sum_{i=1}^{n}\sum_{j=1}^{n}W_{ij}(y_{i}-y_{j})^{2}\\\
&y_{i}\in\text{[0,1]},\forall i\end{split}$

where $\lambda$ is a hyperparameter that controls the trade-off between
fairness and accuracy. A higher $\lambda$ favors better fairness. Although
this gradient based algorithm is efficient, it shares the same problem as the
greedy algorithm where it may get stuck in a local minima and thus fail to
find a feasible solution.

Clustering Based Algorithm. The third approach is to use a clustering
algorithm for clustering examples and assigning the same label to each
cluster. We use k-means as a representative clustering algorithm. If $k=1$,
then all examples will have the same label, and we can simply choose the
majority label of the examples. If $k$ is set correctly, and the clustering is
perfect, then only the similar examples will be clustered together. However,
this approach is unsuitable for our problem, which is to flip the minimum
number of labels to have at most $m$ total error. Reducing the total error to
0 is not the primary goal as there may be a large degradation in accuracy. To
cluster for our purposes, one would have to adjust $k$ to find the clusters
with just the right amount of total error, but this fine-tuning is difficult
as we show in Section 4.4.

##  3\. iFlipper

We explain how iFlipper converts the MIQP problem into an approximate linear
program (LP) problem and produces a feasible solution with theoretical
guarantees. The conversion is done in two steps: from MIQP to an equivalent
integer linear program (ILP) using linear constraints (Section 3.1) and from
the ILP problem to an approximate LP problem (Section 3.2). We present
iFlipper’s algorithm to solve the approximate LP problem and show why its
result always leads to a feasible solution (Section 3.3). We then provide
theoretical guarantees on how far the result is from the optimal solution of
the ILP problem, and propose a reverse-greedy approach to further optimize the
solution (Section 3.4). Finally, we present iFlipper’s overall workflow with a
complexity analysis (Section 3.5).

###  3.1. From MIQP to Equivalent ILP

We convert the MIQP problem to an equivalent ILP problem. We first replace the
squared terms in Equation 1 to absolute terms:

(3) $\begin{split}\quad\min\quad&\sum_{i=1}^{n}{|y_{i}-y_{i}^{\prime}|}\\\
\text{s.t.}\quad&\sum_{i=1}^{n}\sum_{j=1}^{n}W_{ij}|y_{i}-y_{j}|\leq m\\\
&y_{i}\in\text{\\{0,1\\}},\forall i\end{split}$

The resulting formulation is equivalent to the original MIQP because $y_{i}$
and $y^{\prime}_{i}$ have binary values.

To convert this problem into an equivalent ILP problem, we replace each
absolute term with an XOR expression, which can be expressed as four linear
constraints. For two binary variables $x$ and $y$, one can easily see that
$|x-y|=x\text{ XOR }y$. Also, each expression $z=x\text{ XOR }y$ is known to
be equivalent to the following four linear constraints: $z\leq x+y$, $z\geq
y-x$, $z\geq x-y$, and $z\leq 2-x-y$. For example, if $x=1$ and $y=1$, $z$ is
bounded by $z\leq 2-x-y$ and is thus 0. For other combinations of $x$ and $y$,
$z$ will be bounded to its correct XOR value as well. We thus introduce the
auxiliary variables $z_{i}$ and $z_{ij}$ to represent $y_{i}\text{ XOR
}y^{\prime}_{i}$ and $y_{i}\text{ XOR }y_{j}$, respectively, and obtain the
following integer linear programming (ILP) problem:

(4) $\begin{split}\text{(ILP)}\quad\min\quad&\sum_{i=1}^{n}{z_{i}}\\\
\text{s.t.}\quad&\sum_{i=1}^{n}\sum_{j=1}^{n}W_{ij}z_{ij}\leq m\\\
&y_{i},z_{i}\in\text{\\{0,1\\}},\forall i,\quad
z_{ij}\in\text{\\{0,1\\}},\forall i,j\\\ &z_{i}-y_{i}\leq y^{\prime}_{i},\quad
z_{i}-y_{i}\geq-y^{\prime}_{i}\\\ &z_{i}+y_{i}\geq y^{\prime}_{i},\quad
z_{i}+y_{i}\leq 2-y^{\prime}_{i}\\\ &z_{ij}-y_{i}-y_{j}\leq 0,\quad
z_{ij}-y_{i}+y_{j}\geq 0\\\ &z_{ij}+y_{i}-y_{j}\geq 0,\quad
z_{ij}+y_{i}+y_{j}\leq 2\\\ \end{split}$

Since the ILP problem is equivalent to the MIQP problem, we know it is NP-hard
as well. In the next section, we convert the ILP problem to an approximate
linear program (LP), which can be solved efficiently.

###  3.2. From ILP to Approximate LP

We now relax the ILP problem to an approximate LP problem. At this point, one
may ask why we do not use existing solvers like CPLEX (cplex2009v12), MOSEK
(mosek), and Gurobi (gurobi), which also use LP relaxations. All these
approaches repeatedly solve LP problems using branch-and-bound methods and
have time complexities exponential to the number of variables in the worst
case. In Section 4.4, we demonstrate how slow the ILP solvers are. Our key
contribution is finding a near-exact solution to the original ILP problem by
solving the LP problem _only once_.

We first replace the integer constraints in Equation 4 with range constraints
to obtain the following LP problem:

(5) $\begin{split}\text{(LP)}\quad\min\quad&\sum_{i=1}^{n}{z_{i}}\\\
\text{s.t.}\quad&\sum_{i=1}^{n}\sum_{j=1}^{n}W_{ij}z_{ij}\leq m\\\
&y_{i},z_{i}\in\text{[0,1]},\forall i,\quad z_{ij}\in\text{[0,1]},\forall
i,j\\\ &z_{i}-y_{i}\leq y^{\prime}_{i},\quad z_{i}-y_{i}\geq-y^{\prime}_{i}\\\
&z_{i}+y_{i}\geq y^{\prime}_{i},\quad z_{i}+y_{i}\leq 2-y^{\prime}_{i}\\\
&z_{ij}-y_{i}-y_{j}\leq 0,\quad z_{ij}-y_{i}+y_{j}\geq 0\\\
&z_{ij}+y_{i}-y_{j}\geq 0,\quad z_{ij}+y_{i}+y_{j}\leq 2\\\ \end{split}$

Now the violation between two points becomes the product of the weight of the
edge $W_{ij}$ and the absolute difference between the two labels
$z_{ij}=|y_{i}-y_{j}|$. Although this problem can be solved more efficiently
than the ILP problem, its result cannot be used as is because of the
continuous values. Hence, we next convert the result into a binary solution
that is close to the optimal solution of the ILP problem. A naïve method is to
round the continuous values to their nearest integers, but this does not
guarantee a feasible solution.

###### Example 0.

Suppose we start from the graph in Figure 3a. Just like previous examples, we
again assume that $W_{ij}$ is 1 for simplicity. The total error in Figure 3a
is 4, and we set $m=2$. Solving the LP problem in Equation 5 can produce the
solution in Figure 3b where the labels of nodes 1 and 4 are flipped from 1 to
0.5 (gray color). One can intuitively see that the labels are minimally
flipped while the total error is exactly 2. However, rounding the labels
changes the two 0.5’s back to 1’s as shown in Figure 3c, resulting in an
infeasible solution, because the total error becomes 4 again.

Figure 3. Performing simple roundings on the optimal solution’s values of the
LP problem may result in an infeasible solution for the ILP problem.

###  3.3. Constructing a Feasible Solution

We now explain how to construct a feasible integer solution for the ILP
problem (Equation 4) from an optimal solution of the LP problem (Equation 5).
We first prove a surprising result that any optimal solution $y^{*}$ can be
converted to another optimal solution $\check{y}$ where all of its variables
have one of the three values: 0, 1, or some $\alpha\in(0,1)$. That is,
$\alpha$ is between 0 and 1, but not one of them. Next, we utilize this
property and propose an adaptive rounding algorithm that converts $\check{y}$
into a feasible solution whose values are only 0’s and 1’s.

Optimal Solution Conversion. We prove the following lemma for converting an
optimal solution to our desired form.

###### Lemma 2.

Given an optimal solution $y^{*}$ of Equation 5, we can always convert $y^{*}$
to a new solution $\check{y}$ where $\check{y}$ is also optimal and only has
0, 1, or a unique $\alpha\in(0,1)$ as its values.

###### Proof.

Suppose there are at least two distinct values $\alpha$ and $\beta$ that are
not 0 or 1 in $y^{*}$. We can combine all the $y^{*}$ nodes whose value is
$\alpha$ to one node while maintaining the same total error because an
$\alpha$-$\alpha$ edge has no violation (see Figure 4 for an illustration). We
call this collection an $\alpha$-cluster. Likewise, we can generate a
$\beta$-cluster.

Figure 4. Continuing from Figure 3, recall that the optimal LP solution has
nodes 1 and 4 with 0.5 labels. We can combine nodes 1 and 4 to construct a
0.5-cluster connected to nodes 2 and 3 with four edges as shown on the right.
The total error is still 2.

Without loss of generality, let us assume that 0 ¡ $\alpha$ ¡ $\beta$ ¡ 1, and
the sum of the pairwise node similarities between the two clusters is $E$.
Suppose an $\alpha$-cluster and a $\beta$-cluster have $A_{0}$ and $B_{0}$
nodes whose initial labels are 0, respectively, and $A_{1}$ and $B_{1}$ nodes
whose initial values are 1, respectively. Let $N_{\alpha}=A_{0}-A_{1}$ and
$N_{\beta}=B_{0}-B_{1}$. Now suppose there are $U$ nodes connected to the
$\alpha$-cluster by an edge $W_{a_{i}\alpha}$ and $V$ nodes connected to the
$\beta$-cluster by an edge $W_{b_{i}\beta}$, whose values satisfy

$\begin{split}&0\leq a_{1}\leq...\leq a_{k}<\alpha<a_{k+1}\leq...\leq
a_{U}\leq 1\text{ and }\\\ &0\leq b_{1}\leq...\leq
b_{l}<\beta<b_{l+1}\leq...\leq b_{V}\leq 1.\end{split}$

Note that there is no connected node with a value of $\alpha$ or $\beta$ by
construction. Let
$S_{\alpha}=\sum_{i=1}^{k}W_{a_{i}\alpha}-\sum_{i=k+1}^{U}W_{a_{i}\alpha}$ and
$S_{\beta}=\sum_{i=1}^{l}W_{b_{i}\beta}-\sum_{i=l+1}^{V}W_{b_{i}\beta}$. Let
us also add the following nodes for convenience: $a_{0}=0$, $a_{U+1}=1$,
$b_{0}=0$, and $b_{V+1}=1$. We can then reduce at least one unique non-0/1
value in $y^{*}$, by either changing $\alpha$ to $a_{k}$ or $a_{k+1}$, or
changing $\beta$ to $b_{l}$ or $b_{l+1}$, or changing both $\alpha$ and
$\beta$ to the same value, while keeping the solution optimal using the
following Lemmas 0.1 and 0.2. The key idea is that at least one of the
conversions allows the solution to have the same number of label flippings and
the same or even smaller amount of total error, keeping the solution optimal.
The conversion process only depends on $N_{\alpha}$, $S_{\alpha}$,
$N_{\beta}$, $S_{\beta}$, and $E$. The complete proof and detailed conditions
for each case are given in our technical report (iflippertr).

###### Lemma 0.1.

For an $\alpha$-cluster with $N_{\alpha}=0$ in the optimal solution, we can
always convert $\alpha$ to either $a_{k}$ or $a_{k+1}$ while maintaining an
optimal solution. As a result, we can reduce exactly one non-0/1 value in the
optimal solution.

###### Lemma 0.2.

For an $\alpha$-cluster with $N_{\alpha}\neq 0$ and a $\beta$-cluster with
$N_{\beta}\neq 0$ in the optimal solution, we can always convert
$(\alpha,\beta)$ to one of
$(a_{k},\beta+\frac{N_{\alpha}}{N_{\beta}}(a_{k}-\alpha))$,
$(a_{k+1},\beta-\frac{N_{\alpha}}{N_{\beta}}(a_{k+1}-\alpha))$,
$(\alpha+\frac{N_{\beta}}{N_{\alpha}}(\beta-b_{l}),b_{l})$,
$(\alpha-\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta),b_{l+1})$, or
$(\frac{\alpha N_{\alpha}+\beta N_{\beta}}{N_{\alpha}+N_{\beta}},\frac{\alpha
N_{\alpha}+\beta N_{\beta}}{N_{\alpha}+N_{\beta}})$, while maintaining an
optimal solution. As a result, we can reduce at least one non-0/1 value in the
optimal solution.

We can repeat this adjustment until the solution $\check{y}$ has at most one
unique value $\alpha$ that is neither 0 nor 1. ∎

Based on Lemma 2, Algorithm 1 shows how to convert the optimal LP solution
$y^{*}$ to another optimal solution $\check{y}$ whose values are in {0,
$\alpha$, 1}. We first obtain all the unique non-0/1 values in $y^{*}$ and for
each value $v$ construct a $v$-cluster. We then pick a cluster (say the
$\alpha$-cluster) with $N_{\alpha}=0$ and change $\alpha$ using the
TransformWithOneCluster function, which implements the converting process of
Lemma 0.1 (see our technical report (iflippertr) for details) until there are
no more such clusters (Lines 4–7). Among the rest of the clusters, we choose
two (say the $\alpha$-cluster and $\beta$-cluster) and transform them using
the TransformWithTwoClusters function, which implements the combining process
of Lemma 0.2 described in our technical report (iflippertr) (Lines 8–11). We
repeat these steps until there is at most one non-0/1 value in $\check{y}$.
The details of the TransformWithOneCluster and TransformWithTwoClusters
functions are shown in Algorithm 2.

Input: Optimal solution $y^{*}$ for the LP problem, similarity matrix $W$

Output : Transformed optimal solution $\check{y}$ where each value is one of
{0, $\alpha$, 1}

1

2$\check{y}$ = $y^{*}$;

// There are T unique non-0/1 values in $y^{*}$

3 $T$ = GetNumClusters($y^{*}$);

4 while  _$T >1$_ do

5 $ZeroClusterList$ = GetZeroClusters($\check{y}$);

6 for  _$\alpha$ in $ZeroClusterList$_ do

// Details are in Algorithm 2

7 TransformWithOneCluster($\check{y}$, $\alpha$, $W$);

8 $T$ = $T$ \- 1;

9

10 if  _$T >1$_ then

11 $\alpha$, $\beta$ = GetNonZeroTwoClusters($\check{y}$);

// Details are in Algorithm 2

12 TransformWithTwoClusters($\check{y}$, $\alpha$, $\beta$, $W$);

13 $T$ = GetNumClusters($\check{y}$);

14

// There is at most one unique non-0/1 value in $\check{y}$

15 return $\check{y}$;

16

Algorithm 1 iFlipper’s LP solution conversion algorithm.

1

2Function  _TransformWithOneCluster(_$y$ , $\alpha$, $W$_)_:

3

// Replace all $\alpha$ with $\alpha_{new}$ to reduce one unique non-0/1 value

4

5 $a_{k}$, $a_{k+1}$, $S_{\alpha}$ = GetOneClusterInfo($y$, $\alpha$, $W$);

6

7 if  _$S_{\alpha}\leq 0$_ then

8 $\alpha\leftarrow{}a_{k+1}$;

9 else

10 $\alpha\leftarrow{}a_{k}$;

// Now $\alpha\in\\{a_{k},a_{k+1}\\}$

11

12Function  _TransformWithTwoClusters(_$y$ , $\alpha$, $\beta$, $W$_)_:

// Replace all ($\alpha$, $\beta$) with ($\alpha_{new}$, $\beta_{new}$) using
one of the five cases in Lemma 0.2 to reduce at least one unique non-0/1 value

13

14 $a_{k}$, $a_{k+1}$, $N_{\alpha}$, $S_{\alpha}$, $b_{l}$, $b_{l+1}$,
$N_{\beta}$, $S_{\beta}$, $E$ = GetTwoClustersInfo($y$, $\alpha$, $\beta$,
$W$);

15

16 $X$, $Y$ = $\frac{N_{\alpha}}{N_{\beta}}$,
$\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}$;

17

// Details are in our technical report (iflippertr)

18

19 if  _$X <0$, $Y\leq 0$_ then

20 if  _$X+1\leq 0$_ then

21
$\alpha\leftarrow{}\alpha+min(a_{k+1}-\alpha,-\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta))$;

22 else

23
$\alpha\leftarrow{}\alpha+min(a_{k+1}-\alpha,-\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta),\frac{N_{\beta}(\beta-\alpha)}{N_{\alpha}+N_{\beta}})\;$

24 $\beta\leftarrow{}\beta-\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$;

25

26 else if  _$X <0$, $Y>0$_ then

27 if  _$X+1\geq 0$_ then

28 $\alpha\leftarrow{}\alpha-min(\alpha-
a_{k},-\frac{N_{\beta}}{N_{\alpha}}(\beta-b_{l}))$;

29

30 else

31 $\alpha\leftarrow{}\alpha-min(\alpha-
a_{k},-\frac{N_{\beta}}{N_{\alpha}}(\beta-
b_{l}),-\frac{N_{\beta}(\beta-\alpha)}{N_{\alpha}+N_{\beta}})$;

32 $\beta\leftarrow{}\beta+\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$;

33

34 else if  _$X >0$, $Y\leq 0$_ then

35
$\alpha\leftarrow{}\alpha+min(a_{k+1}-\alpha,\frac{N_{\beta}}{N_{\alpha}}(\beta-
b_{l}),\frac{N_{\beta}(\beta-\alpha)}{N_{\alpha}+N_{\beta}})$;

36 $\beta\leftarrow{}\beta-\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$;

37

38 else if  _$X >0$, $Y>0$_ then

39 $\alpha\leftarrow{}\alpha-min(\alpha-
a_{k},\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta))$;

40 $\beta\leftarrow{}\beta+\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$;

41

// Now $(\alpha,\beta)$ is one of the cases in Lemma 0.2

42

Algorithm 2 Transformation functions in Algorithm 1.

###### Example 0.

To illustrate Algorithm 1, consider Figure 3a again where $m=2$. Say we obtain
an optimal solution from an LP solver as shown in Figure 5a where nodes 1 and
4 have the labels $\alpha=0.1$ and $\beta=0.9$, respectively, while the other
nodes have 0 labels. This solution uses one flip and has a total error of 2.
We first construct an $\alpha$-cluster and a $\beta$-cluster where each
cluster only contains a single node, and there is no edge between them as
shown in Figure 5b. We then convert ($\alpha$, $\beta$) using the
TransformWithTwoClusters. As a result, we set ($\alpha$, $\beta$) to (0.5,
0.5) and reduce one non-0/1 unique value in the solution. The solution now has
only one non-0/1 value (i.e., 0.5) and still has a total error of 2 while
using one flip.

Figure 5. Cluster construction example for Algorithm 1.

Adaptive Rounding into a Binary Solution. We now convert $\check{y}$ into a
feasible integer solution with only 0’s and 1’s. If we use simple rounding to
change $\alpha$ to 0 or 1 as in the naïve method in Section 3.2, the resulting
integer solution may not be feasible like the example in Figure 3c.
Fortunately, the fact that we only have three possible values allows us to
propose an adaptive rounding algorithm (Algorithm 3) that guarantees
feasibility. We first denote $M_{ab}$ as the sum of similarity values of
($a$-$b$) label pairs with edges. For example, $M_{0\alpha}$ is the sum of
similarities of similar node pairs whose labels are 0 and $\alpha$,
respectively. Then the key idea is to round $\alpha$ to 1 if the (1-$\alpha$)
label pairs have a higher similarity sum than that of the (0-$\alpha$) label
pairs (i.e., $M_{0\alpha}\leq M_{1\alpha}$), and round $\alpha$ to 0
otherwise. For example, consider Figure 3b again. Here $\alpha=0.5$,
$M_{0\alpha}=4$, and $M_{1\alpha}=0$. We have $M_{0\alpha}>M_{1\alpha}$, so
rounding $\alpha$ to 0 will result in a feasible solution with zero
violations.

Input: Transformed optimal solution $\check{y}$ for the LP problem whose
values are in {0, $\alpha$, 1}, similarity matrix $W$

Output : Feasible binary integer solution $\overline{y}$

// Get the total similarity values of ($0$-$\alpha$) and ($1$-$\alpha$) label
pairs

1 $M_{0\alpha},M_{1\alpha}$ = GetSimilaritySumOfPairs($\check{y}$, $W$);

2 if  _$M_{0\alpha}\leq M_{1\alpha}$_ then

3 $\overline{\alpha}\leftarrow{}1$;

4

5else

6 $\overline{\alpha}\leftarrow{}0$;

7

// Replace $\alpha$ with $\overline{\alpha}\in\\{0,1\\}$

8 $\overline{y}$ = ApplyRounding($\check{y},\overline{\alpha}$);

9 return $\overline{y}$;

10

Algorithm 3 iFlipper’s adaptive rounding algorithm.

We prove the correctness of Algorithm 3 in Lemma 4.

###### Lemma 4.

Given an optimal solution $\check{y}$ of Equation 5 where each value is one of
{0, $\alpha$, 1}, applying adaptive rounding (Algorithm 3) always results in a
feasible solution.

###### Proof.

The total error in $\check{y}$ can be expressed as a function of $\alpha$:

(6) $\begin{split}\text{Total
Error}&=\sum_{i=1}^{n}\sum_{j=1}^{n}W_{ij}\check{z}_{ij}=\sum_{i=1}^{n}\sum_{j=1}^{n}W_{ij}|\check{y}_{i}-\check{y}_{j}|\\\
&=f(\alpha)=M_{01}+\alpha M_{0\alpha}+(1-\alpha)M_{1\alpha}\leq m\\\
\end{split}$

In addition, the error constraint in Equation 5 is satisfied because
$\check{y}$ is an optimal solution.

We now want to round $\alpha$ to either 0 or 1 while satisfying the error
constraint. If $M_{0\alpha}\leq M_{1\alpha}$, we have
$f(1)=M_{01}+M_{0\alpha}\leq M_{01}+\alpha
M_{0\alpha}+(1-\alpha)M_{1\alpha}\leq m$ $(\because 0<\alpha<1)$, so setting
$\alpha=1$ guarantees a feasible solution. On the other hand, if
$M_{1\alpha}<M_{0\alpha}$, we have $f(0)=M_{01}+M_{1\alpha}<M_{01}+\alpha
M_{0\alpha}+(1-\alpha)M_{1\alpha}\leq m$ $(\because 0<\alpha<1)$, so setting
$\alpha=0$ ensures feasibility. ∎

Lemma 4 shows that the rounding choice of $\alpha$ depends on how
$M_{0\alpha}$ and $M_{1\alpha}$ compare instead of $\alpha$’s value itself.
This result explains why simple rounding as in the naïve method does not
necessarily lead to a feasible solution.

In the next section, we analyze how accurate the rounded solution is compared
to the optimal solution of the ILP problem and investigate whether it can be
further improved.

###  3.4. Optimality and Improvement

We analyze the optimality of Algorithm 3 and propose a technique called
reverse greedy for further optimizing it without exceeding the total error
limit.

Optimality Analysis. We prove the theoretical bounds of Algorithm 3 in Lemma
5:

###### Lemma 5.

For a given optimal solution $\check{y}$ of Equation 5, let us denote $N_{ab}$
as the number of nodes in $\check{y}$ where the label $a$ was flipped to $b$.
Then the objective value of the output $\overline{y}$ from Algorithm 3 is at
most $C$ more than the optimal objective value of the original ILP problem
where the value of $C$ depends on $\alpha$:

(7)
$\begin{split}&\alpha=1\rightarrow{}C=(1-\alpha)(N_{0\alpha}-N_{1\alpha})\\\
&\alpha=0\rightarrow{}C=\alpha(N_{1\alpha}-N_{0\alpha})\\\ \end{split}$

###### Proof.

Since the optimal solution of the ILP problem is always one of the feasible
solutions of the LP problem, the optimal objective values ($OPT$) of the two
optimization problems should satisfy:

(8) $\begin{split}OPT_{LP}\leq OPT_{ILP}\\\ \end{split}$

The objective value of $\check{y}$ can then be expressed as follows:

(9)
$\begin{split}OPT_{LP}(\check{y})&=\sum_{i=1}^{n}\check{z}_{ij}=(N_{01}+N_{10})+\alpha
N_{0\alpha}+(1-\alpha)N_{1\alpha}\\\ \end{split}$

We first consider the case where $\alpha=1$. Here the objective value of
$\overline{y}$ is $OPT_{LP}(\overline{y})=(N_{01}+N_{10})+N_{0\alpha}$. We can
then derive the bound on $OPT_{LP}(\overline{y})$ from Equation 8 and Equation
9 as follows:

(10) $\begin{split}&OPT_{LP}(\check{y})-OPT_{LP}(\overline{y})\leq
OPT_{ILP}-OPT_{LP}(\overline{y})\\\ &(1-\alpha)(N_{1\alpha}-N_{0\alpha})\leq
OPT_{ILP}-OPT_{LP}(\overline{y})\\\ &OPT_{LP}(\overline{y})\leq
OPT_{ILP}+(1-\alpha)(N_{0\alpha}-N_{1\alpha})\\\ \end{split}$

We note that $(1-\alpha)(N_{0\alpha}-N_{1\alpha})$ is always non-negative
because $\check{y}$ is an optimal solution, i.e., $OPT_{LP}(\check{y})\leq
OPT_{LP}(\overline{y})$.

Similarly, if $\alpha=0$, we can obtain the objective value bound of
$\alpha(N_{1\alpha}-N_{0\alpha})$. ∎

Reverse Greedy Algorithm. Lemma 5 shows that the bound may sometimes be loose
because it depends on $\alpha$ and the number of nodes whose labels are
flipped to $\alpha$. There is a possibility that Algorithm 3 flips nodes
unnecessarily, which results in a total error smaller than $m$ (see Section
4.5 for empirical results). Hence, we propose an algorithm called reverse
greedy (Algorithm 4), which unflips flipped labels as long as the total error
does not exceed $m$. As the name suggests, we run the greedy algorithm in
Section 2.2 in the reverse direction where for each iteration, we unflip nodes
that increase the error the least to recover the original labels as much as
possible. Thus, reverse greedy can only improve the optimality of Algorithm 3.

Input: Feasible binary integer solution $\overline{x}$, total error limit $m$

Output : Improved binary integer solution $\tilde{x}$

1

2$\tilde{x}$ = $\overline{x}$;

3 $flipped\\_labels$ = GetFlippedLabel($\tilde{x}$);

4 $total\\_error$ = GetTotalError($\tilde{x}$);

5 while  _$total\\_error\leq m$_ do

// Unflip flipped labels of the nodes so that the total error is increased the
least

6 $\tilde{x}$ = FlipLabelLeastViolation($\tilde{x}$, $flipped\\_labels$);

7 $flipped\\_labels$ = GetFlippedLabel($\tilde{x}$);

8 $total\\_error$ = GetTotalError($\tilde{x}$);

9

10return $\tilde{x}$;

11

Algorithm 4 iFlipper’s reverse greedy algorithm.

###### Example 0.

Continuing from our example using Figure 3 and $m=2$, suppose we run Algorithm
3 on Figure 3b and round the 0.5 labels to 0 to obtain the feasible solution
in Figure 6a. A total of two flips are performed compared to the initial graph
Figure 3a. However, there exists an optimal solution like Figure 6b where only
one flip is necessary. Running Algorithm 4 will unflip nodes 1 or 4, and
unflipping node 1 produces this solution.

Figure 6. The reverse greedy algorithm can further optimize a rounded solution
from Algorithm 3.

The time complexity of reverse greedy is the same as the greedy algorithm,
i.e., $O(n^{2})$, but in practice requires fewer iterations than greedy
because the total error is relatively close to $m$.

###  3.5. Putting Everything Together

We now describe the overall workflow of iFlipper. For a given ILP problem, we
first convert it into an approximate LP problem. We then solve the approximate
LP problem and convert its optimal solution to another optimal solution that
only has values in {0, $\alpha$, 1} using Algorithm 1. We then apply adaptive
rounding using Algorithm 3. Finally, we possibly improve the rounded solution
by unflipping labels using Algorithm 4.

Complexity Analysis. iFlipper consists of four parts: solving the approximate
LP problem, the converting algorithm, the adaptive rounding algorithm, and the
reverse-greedy algorithm. The interior-points algorithm for solving LP has a
time complexity of $O(n^{2+\varepsilon})$, where $\varepsilon$ is smaller than
1. The converting algorithm has a time complexity of $O(n^{2})$: in the worst
case, we may need to combine clusters $n$ times, and for each combining
process, we need to check all neighbors of a particular cluster, which is up
to $n$ points. For the adaptive rounding algorithm, the time complexity is
also $O(n^{2})$, because we need to count the number of $(1,\alpha)$ edges and
$(0,\alpha)$ edges, which is $O(n^{2})$ in the worst case. The reverse greedy
algorithm, as analyzed in Section 3.4, is $O(n^{2})$. Overall, the complexity
is bounded by the LP solver, which is $O(n^{2+\varepsilon})$. This result may
look worse than the greedy algorithm, but iFlipper runs much faster than
greedy in practice. The reason is that we use efficient LP solvers, and the
empirical running times of the adaptive rounding and reverse greedy algorithms
are much faster than their theoretical worst case complexities. We show the
empirical runtimes in Section 4.

##  4\. Experiments

In this section, we evaluate iFlipper on real datasets and address the
following key questions:

  * •

Is there an accuracy-fairness trade-off for iFlipper?

  * •

How does iFlipper compare with various baselines in terms of model accuracy,
individual fairness, and efficiency?

  * •

How useful is each component of iFlipper?

  * •

Does the LP solution conversion run correctly?

  * •

Can iFlipper be integrated with in-processing techniques?

We implement iFlipper in Python and use Scikit-learn (scikit-learn) and
PyTorch (NEURIPS2019_9015) libraries for model training. For performing
optimization, we use two software packages: CPLEX (cplex2009v12) and MOSEK
(mosek). We run all experiments on Intel Xeon Gold 5115 CPUs.

###  4.1. Setting

##### Datasets

We experiment on the following three popular datasets in the fairness
literature. We randomly split each dataset into training, test, and validation
sets. We then use the same feature pre-processing as in IBM’s AI Fairness 360
toolkit (DBLP:journals/corr/abs-1810-01943) where examples with missing values
are discarded. See Table 1 for more details.

  * •

COMPAS (machinebias): Contains 6,167 people examples and is used to predict
criminal recidivism rates. The features include gender, race, and criminal
history.

  * •

AdultCensus (DBLP:conf/kdd/Kohavi96): Contains 45,222 people examples and is
used to predict whether an individual’s income exceeds $50K per year. The
features include gender, age, and occupation.

  * •

Credit (Dua:2019): Contains 1,000 examples and is used to predict an
individual’s credit risk. The features contain race, credit amount, and credit
history.

  * •

Synthetic (pmlr-v54-zafar17a): We generate 200,000 samples with two attributes
($x_{1}$, $x_{2}$) and a binary label $y$ following a process introduced in
(pmlr-v54-zafar17a). Tuples with a positive label ($x_{1}$, $x_{2}$, $y=1$)
are drawn from a Gaussian distribution and, tuples with a negative label
($x_{1}$, $x_{2}$, $y=0$) are drawn from another Gaussian distribution.

We also considered two additional fairness datasets: Bank (bankdataset) and
LSAC (lsacdataset). However, these datasets exhibit fewer individual fairness
issues as shown in our technical report (iflippertr). Hence, we do not include
them in our main experiments because the fairness improvements are not as
significant.

##### Similarity Matrices

We consider two similarity matrices using Euclidean distance (i.e.,
$d(x_{i},x_{j})=\|x_{i}-x_{j}\|^{2}$). When measuring distances, we follow
previous approaches (ifair; pmlr-v28-zemel13) and exclude sensitive attributes
like gender and race. The rationale is that individuals who have similar
information other than the sensitive attributes values must be treated
similarly. We quantify the similarity as $W_{ij}=e^{-\theta d(x_{i},x_{j})}$
where $\theta>0$ is a scale parameter. Our design follows a related work on
individual fairness that also uses similarity matrices (petersen2021post). See
Table 1 for the configurations.

  * •

kNN-based: Considers $(x_{i},x_{j})$ as a similar pair if $x_{i}$ is one of
$x_{j}$’s nearest neighbors or vice versa:

$W_{ij}=\begin{cases}e^{-\theta d(x_{i},x_{j})}&\text{if $x_{i}\in
NN_{k}(x_{j})$ or $x_{j}\in NN_{k}(x_{i})$}\\\ 0&\text{otherwise}\end{cases}$

where $NN_{k}(x_{j})$ denotes the set of $k$ nearest examples of $x_{j}$ in a
Euclidean space.

  * •

threshold-based: Considers $(x_{i},x_{j})$ as a similar pair if their distance
is smaller than a threshold $T$:

$W_{ij}=\begin{cases}e^{-\theta d(x_{i},x_{j})}&\text{if $d(x_{i},x_{j})\leq
T$}\\\ 0&\text{otherwise}\end{cases}$

We use the FALCONN LSH library (Andoni2015falconn) to efficiently construct
both similarity matrices. For all datasets, we set the LSH hyperparameters
(number of hash functions and number of hash tables) to achieve a success
probability of 0.98 on a validation set where 98% of similar pairs of examples
are in the same buckets.

Dataset | # Train | # Test | # Valid | Sen. Attr | $k$ | $T$ | $\theta$
---|---|---|---|---|---|---|---
COMPAS | 3,700 | 1,850 | 617 | gender | 20 | 3 | 0.05
AdultCensus | 27,133 | 13,566 | 4,523 | gender | 20 | 3 | 0.1
Credit | 700 | 201 | 199 | age | 20 | 7 | 0.05
Synthetic |  100,000 |  60,000 |  40,000 |  N/A111There is no sensitive attribute to exclude when measuring distances. |  20 |  3 |  0.05
Table 1. Settings for the four datasets.

##### Measures

We evaluate a model’s accuracy by computing the portion of correctly-predicted
data points. We evaluate individual fairness using the consistency score
(pfr2019) defined in Section 2.1, which measures the consistency of
predictions on the test set between similar individuals. For both scores,
higher values are better. We report mean values over five trials for all
measures.

##### Hyperparameter Tuning

iFlipper provides a total error limit hyperparameter $m$, which impacts the
trade-off between the model accuracy and fairness where a lower $m$ results in
better fairness, but worse accuracy (see Section 4.3.1). Given a desired
consistency score, we can use binary search to adjust $m$ by comparing the
consistency score of the trained model with the desired score.

##### Methods Compared

We compare iFlipper with the following existing pre-processing algorithms for
individual fairness:

  * •

LFR (pmlr-v28-zemel13): A fair representation learning algorithm that
optimizes between accuracy, group fairness, and individual fairness in terms
of data reconstruction loss.

  * •

iFair (ifair): A fair representation learning algorithm that optimizes
accuracy and individual fairness. Compared to LFR, iFair does not optimize
group fairness, which enables the classifier to have better individual
fairness. If two data points are close to each other in the input space, iFair
aims to map them close to each other in the feature space as well.

  * •

PFR (pfr2019): A fair representation learning algorithm that tries to learn an
embedding of the fairness graph. The fairness graph used in PFR is similar to
the one used in iFlipper. Similar to iFair, PFR optimizes individual fairness
while preserving the original data by mapping similar individuals to nearby
points in the learned representation. Among the three baselines, only PFR is
able to support a general similarity matrix. PFR uses an efficient trace
optimization algorithm, which can learn representations much faster than
iFair.

For all baselines, there are multiple hyperparameters that can balance the
competing objectives. We start with the same sets of hyperparameters as
described in their papers, and tune them to provide the best results.

##### Optimization Solutions Compared.

We compare iFlipper with the following optimization baselines described in
Sections 2.3 and 3.1.

  * •

Greedy: Flips labels that reduce the total error the most.

  * •

Gradient: Solves an unconstrained optimization problem.

  * •

kMeans: Applies k-means clustering and, for each cluster, make its examples
have the majority label.

  * •

ILP Solver: Solves the ILP problem exactly using CPLEX (cplex2009v12), which
is a state-of-the-art solver.

For Gradient and KMeans, we tune $\lambda$ and $k$, respectively, to satisfy
the total error limit. We use CPLEX to solve ILP problems as it is faster than
MOSEK. When solving LP problems in iFlipper, however, CPLEX turns out to be
much slower than MOSEK due to its long construction time, so we use MOSEK
instead.

An interesting behavior of MOSEK is that empirically all of its optimal
solutions only contain values in $\\{0,\alpha,1\\}$ without having to run our
Algorithm 1. Note that this behavior is limited to the label flipping problems
we are solving and does not necessarily occur for other LP problems. We
suspect that MOSEK’s algorithm effectively contains the functionality of
Algorithm 1. We also make the same observations when using CPLEX for our LP
problems. We find these results encouraging because it means that Algorithm 1
is not a significant runtime overhead and can even be tightly integrated with
the LP solving code. A detailed analysis of MOSEK’s code is an interesting
future work. For any other solver that does not have this behavior, one can
always run Algorithm 1 on its solutions. Hence to make sure our Algorithm 1 is
correct, we separately evaluate it in Section 4.6.

##### Model Setup

We use logistic regression (LR), random forest (RF), and neural network (NN)
models for our experiments. We tune the model hyperparameters (e.g., learning
rate and maximum depth of the tree) such that the model has the highest
validation accuracy. Our goal is to pre-process the training data to make
these models train fairly.

###  4.2. Accuracy and Fairness Trade-off

Figure 7 shows the trade-off between fairness and accuracy for the COMPAS
dataset when running iFlipper with different allowed amounts of total error.
The x-axis is accuracy, and the y-axis is the consistency score. There are two
curves, which correspond to two different similarity matrices: kNN-based and
threshold-based. Each data point on the curve has two other results: (total
error after repairing, number of flips). As we flip more labels, there is less
total error in the repaired dataset, and the resulting model has a higher
consistency score on the test set, which means it has better individual
fairness. However, the accuracy drops as we flip more labels. The trade-off
curves of the other datasets are similar and can be found in our technical
report (iflippertr).

Figure 7. Accuracy-fairness trade-off curves for iFlipper. For each data
point, we also show the total error after repairing and the number of flips in
parentheses.

(a) COMPAS-kNN

(b) AdultCensus-kNN

(c) Credit-kNN

(d) COMPAS-threshold

(e) AdultCensus-threshold

(f) Credit-threshold

Figure 8. Accuracy-fairness trade-offs of logistic regression on the three
datasets using the two similarity matrices. In addition to the four methods
LFR, iFair, PFR, and iFlipper, we add the result of model training without any
pre-processing and call it “Original.” As a result, only iFlipper shows a
clear accuracy and fairness trade-off.

###  4.3. Performance and Runtime Results

We now compare iFlipper with other baselines using the three datasets and two
similarity matrices.

####  4.3.1. Accuracy and Fairness Comparison

We first compare the accuracy and fairness results of iFlipper with the other
methods. Figure 8 shows the trade-off results with logistic regression where
the x-axis is the accuracy, and the y-axis is the consistency score on a test
set. Original is where we train a model on the original data with no data pre-
processing. For LFR, iFair, and PFR, we employ 20, 45, and 15 different
hyperparameter sets, respectively, as described in their papers. For iFlipper,
we use 10–11 different $m$ values to control accuracy and fairness. For a
clear visualization, we omit some points in the bottom left region of the
graph for methods other than iFlipper. As a result, iFlipper significantly
outperforms the baselines in terms of both test accuracy and consistency score
for all cases, which demonstrates that our label flipping approach is
effective in improving individual fairness while maintaining high accuracy. We
also observe that iFlipper performs better than the three baselines on both
similarity matrices. This result is important because the similarity matrix
may vary depending on the application. The results for a random forest and
neural network are in our technical report (iflippertr), and the key trends
are similar to Figure 8 where iFlipper shows a better trade-off than the
baselines. We note that the advantage of iFlipper compared to the baselines is
relatively less clear on the Credit dataset mainly because the data is small,
making the variance of the results higher.

Dataset | Adult-kNN | Adult-threshold
---|---|---
Model | LR | RF | NN | LR | RF | NN
(C. Score) | (0.94) | (0.90) | (0.90) | (0.95) | (0.83) | (0.95)
LFR | .815 | .827 | .806 | .821 | .827 | .806
iFair | .797 | .820 | .805 | .798 | .820 | .806
PFR | .826 | .808 | .844 | .826 | .808 | .829
iFlipper | .844 | .851 | .848 | .845 | .850 | .845
Table 2. Accuracy comparison of methods with similar individual fairness on
different models. In order to align the individual fairness, for each model we
make the methods have similar consistency scores on the validation data (C.
Score) by tuning their hyperparameters.

Table 2 shows a more detailed comparison with the baselines using the
AdultCensus dataset. For each ML model, we fix the consistency score (denoted
as “C. Score”) to be some value as shown below each model name in Table 2 in
parentheses. Then for each method, we report the test accuracy when we tune
its hyperparameter such that the trained model has the highest validation
accuracy while achieving the fixed consistency score on the validation set. As
a result, iFlipper consistently shows the highest test accuracy compared to
the other baselines for all models.

In comparison to the other baselines, iFlipper’s accuracy-fairness trade-off
is also much cleaner as shown in Figure 8 where the other baselines have noisy
trade-offs and even overlapping results for different hyperparameter sets. The
benefit of having a clean trade-off is that iFlipper can easily balance
between accuracy and fairness to obtain a desired fairness by varying the
total error limit $m$. In Figure 8, we also observe that iFlipper is flexible
and can obtain a wide range of test consistency scores, all the way up to
nearly 1.0.

Datasets | Sim. Matrix | Avg. Runtime (sec)
---|---|---
|  | LFR | iFair | PFR | iFlipper
COMPAS | kNN | 786 | 29,930 | 0.41 | 5.70
threshold | 786 | 29,930 | 0.35 | 8.69
Adult- Census | kNN | 700 | 21,321$\dagger$ | 15.62 | 140
threshold | 700 | 21,321$\dagger$ | 14.98 | 685
Credit | kNN | 22.78 | 394 | 0.01 | 1.74
threshold | 22.78 | 394 | 0.01 | 0.68
Table 3. Runtime results of LFR, iFair, PFR, and iFlipper on the COMPAS,
AdultCensus, and Credit datasets. For each method, we show the average runtime
for all experiments in Figure 8. The symbol $\dagger$ indicates that we reduce
the size of the training data for better efficiency. Figure 9. Runtime results
of iFlipper on synthetic datasets.

(a) Total error

(b) Number of flips

(c) Runtime (sec)

Figure 10. A detailed comparison of iFlipper against the three naïve
optimization solutions (Greedy, Gradient, and KMeans) and ILP solver on the
AdultCensus dataset where we use the kNN-based similarity matrix. Here the
initial amount of total error is 65,742.5. We show the results for three
different total error limits ($m$).

####  4.3.2. Runtime Comparison

We evaluate the efficiency of iFlipper and the three baselines in Table 3. For
each method, we show the average runtime for all experiments in Figure 8. We
note that the runtimes of LFR and iFair do not depend on the similarity
matrix. For the iFair experiments on the AdultCensus dataset, we lower the
training data using uniform sampling to fit iFair because fitting iFair on the
entire data takes more than 24 hours. We confirm that this relaxation does not
hurt the original performance reported in the iFair paper (ifair). As a
result, iFlipper is much faster than LFR and iFair for all cases. Although PFR
seems to be the fastest, it performs much worse than iFlipper in terms of
accuracy and fairness as shown in Figure 8.

Another observation is that as the dataset size increases, iFlipper’s runtime
increases following the time complexity analysis in Section 3.5. For a
detailed evaluation, we conduct the experiment using random subsets of the
synthetic dataset. For each experiment, we set the total error limit $m$ to
20% of the initial amount of total error. Figure 9 shows runtime results of
iFlipper on datasets of different sizes. As a result, we observe a quadratic
increase in running time as the size of the training data increases, which is
consistent with our theoretical analysis.

###  4.4. Optimization Solution Comparison

We now compare iFlipper with other optimization solutions: Greedy, Gradient,
KMeans, and an ILP solver. Figure 10 makes a comparison in terms of optimality
and efficiency on the AdultCensus dataset where we use the kNN-based
similarity matrix. We set the total error limit $m$ to three different values
for a detailed comparison. Note that all three subfigures within Figure 10 use
the same legends.

We first compare the resulting total error of the methods in Figure 10(a).
Obviously, the optimal solution from the ILP solver is the closest to the
total error limit. We observe that iFlipper never exceeds the target. On the
other hand, both Greedy and Gradient are unable to find a feasible solution in
some cases. For example, Greedy and Gradient cannot reduce the total error to
less than 4,576.4 and 34,053.8, respectively. This result is expected because
these methods may fall into local minima as we explained in Section 2.3. Also,
KMeans does find feasible solutions, but flips too many labels unnecessarily.
For example, for $m$ = 100 and $m$ = 1,000, KMeans has zero violations using
more flips than iFlipper, which defeats the purpose of the optimization
altogether.

We also compare the number of flips in Figure 10(b). As a result, iFlipper
produces solutions that are close to the optimal ones. When $m$ = 100 and
1,000, Greedy shows the fewest number of label flips because it fails to find
a feasible solution. Gradient has the largest number of flips. We suspect this
poor performance is due to the fact that Gradient (1) solves an unconstrained
optimization problem that makes it hard to satisfy the limit on total error,
and (2) provides continuous values, which introduces rounding errors. KMeans
also performs worse than iFlipper because its clustering cannot be fine-tuned
to have close to $m$ total error.

Finally, we compare the average runtimes (i.e., wall clock times in seconds)
of each method in Figure 10(c). As a result, iFlipper is much faster than the
ILP solver as it solves an approximate LP problem only once. In addition,
Greedy and KMeans are slower than iFlipper because they use many iterations to
reduce the total error and adjust the number of clusters, respectively.
Gradient is the most efficient, but the result is not meaningful because the
total error and the numbers of flips are even worse than Greedy.

We also perform the above experiments on the COMPAS dataset, and the results
are similar (see our technical report (iflippertr)).

###  4.5. Ablation Study

We perform an ablation study in Figure 11 to demonstrate the effectiveness of
each component in iFlipper using the AdultCensus dataset and kNN-based
similarity matrix. The results for the COMPAS dataset are similar and shown in
our technical report (iflippertr). As we explained in Section 4.1, MOSEK
always produces an optimal LP solution that only has values in {0, $\alpha$,
1}, so we do not have an ablation study without the LP solution conversion.
Instead, we separately evaluate the conversion algorithm in Section 4.6.
Again, the fact that MOSEK effectively contains the conversion functionality
indicates that the conversion overhead is not significant and that a tight
integration with the LP solving is possible. We thus compare iFlipper (LP
solver with both adaptive rounding and reverse greedy algorithms) with the
following variants: (1) LP solver with simple rounding (LP-SR); and (2) LP
solver with adaptive rounding (LP-AR). We also consider an optimal solution
from the ILP solver to compare the optimality of each solution.

Figure 11(a) shows that the adaptive rounding algorithm always provides a
feasible solution while simple rounding to a fractional optimal solution
results in an infeasible solution as we discussed in Lemma 3. However, the
rounding algorithm does flip more labels than the optimal solution as shown in
Figure 11(b), resulting in an unintended fairness improvement and accuracy
drop. In this case, the reverse greedy algorithm in iFlipper is used to reduce
the optimality gap with the optimal solution by recovering as many original
labels as possible without exceeding the total error limit.

(a) Total error

(b) Number of flips

Figure 11. Ablation study for iFlipper on the AdultCensus dataset and kNN-
based similarity matrix.

Table 4 shows the average runtime of each component (LP solver, adaptive
rounding, and reverse greedy) in iFlipper in Figure 11. As a result, the
runtime for solving the LP problem is dominant, which demonstrates that
iFlipper is able to provide a near-exact solution with minimal time overhead.

Method | Avg. Runtime (sec)
---|---
LP Solver (effectively includes Alg. 1) | 153.61
\+ Adaptive Rounding (Alg. 3) | 0.48
\+ Reverse Greedy (Alg. 4) | 13.26
Table 4. Avg. runtimes of iFlipper’s components in Figure 11.

###  4.6. Algorithm 1 Evaluation

We now evaluate the LP solution conversion (Algorithm 1) separately using the
three datasets and kNN-based similarity matrices. For all datasets, we start
with an LP problem solution by assigning random values and perform the
conversion. As a result, we successfully convert random solutions to new
solutions whose values are in {0, $\alpha$, 1} where the exact value of
$\alpha$ for each dataset is shown in Table 5. In addition, each converted
solution always has the same number of label flips and a smaller total error.
This result is consistent with Lemma 2, which says the conversion maintains
the optimality of the original solution. Finally, the conversion is much
faster than the overall runtime of iFlipper (see Table 3) even in this worst-
case scenario where the labels are randomly initialized.

|  | Before Conv. | After Conv. |
---|---|---|---|---
Dataset | $\boldsymbol{\alpha}$ | Tot. Err. | # Flips | Tot. Err. | # Flips | Time(s)
COMPAS | 0.471 | 12645.1 | 1,838 | 1038.2 | 1,838 | 2.47
AdultCensus | 0.494 | 93519.7 | 13,514 | 3164.4 | 13,514 | 93.63
Credit | 0.448 | 2447.0 | 361 | 128.7 | 361 | 0.25
Table 5. iFlipper’s conversion algorithm (Algorithm 1) on LP problem solutions
that have random labels.

###  4.7. Compatibility with In-processing Method

In this section, we demonstrate how iFlipper can be combined with an in-
processing algorithm to further improve individual fairness. We evaluate
iFlipper with SenSR (DBLP:conf/iclr/YurochkinBS20), which is an in-processing
fair training algorithm that is robust to sensitive perturbations to the
inputs, on the AdultCensus dataset. For iFlipper, we use the same distance
function in SenSR, which computes the distance using the features that are not
correlated to sensitive attributes and use the threshold $T$ = 2 to construct
the similarity matrix. For a fair comparison, we report both our consistency
score and the GR-Con. (gender and race consistency) / S-Con. (spouse
consistency) metrics used by SenSR to evaluate the individual fairness. Here
Con. measures the consistency between $h(x_{i})$ and $h(x_{i})$ when $x_{i}$
and $x_{j}$ are the same except the sensitive attributes. To evaluate Con., we
use the same method in SenSR where the test data examples are duplicated, but
assigned different sensitive attribute values. As a result, Table 6 shows that
using both methods gives the best individual fairness for both metrics while
having little accuracy drop. Thus, iFlipper complements in-processing
algorithms by removing the bias inherent in the data during the pre-processing
step.

Dataset | Method | Test Acc. | Con. Score | GR/S-Con.
---|---|---|---|---
Adult- Census | Original | 0.855 | 0.917 | 0.919 / 0.867
iFlipper | 0.853 | 0.955 | 0.931 / 0.907
SenSR | 0.836 | 0.953 | 0.990 / 0.945
Both | 0.829 | 0.960 |  0.992 / 0.984
Table 6. Using iFlipper, SenSR, or both on the AdultCensus dataset.

##  5\. Related Work

Various fairness measures have been proposed to capture legal and social
issues (narayanan2018translation). The prominent measures include individual
fairness (dwork2012fairness), group fairness (zafar2017fairness;
agarwal2018reductions; zhang2021omnifair), and causal fairness
(kusner2017counterfactual). Individual fairness captures the notion that
similar individuals should be treated similarly. Group fairness measures like
equal opportunity (DBLP:conf/nips/HardtPNS16), equalized odds
(DBLP:conf/nips/HardtPNS16), and demographic parity
(DBLP:conf/kdd/FeldmanFMSV15) ensure that two sensitive groups have similar
statistics. Causal fairness identifies causal relationships among attributes.
Although optimizing for a different objective function, the causality-based
methods are often used to improve group or individual fairness as well. All
these measures complement each other, and there is a known conflict between
group fairness and individual fairness (binns2020apparent;
friedler2021possibility) that they cannot be satisfied at the same time
because of their different assumptions. Our primary focus is on individual
fairness.

Recently, many unfairness mitigation techniques for individual fairness
(DBLP:journals/corr/abs-1810-01943) have been proposed where they can be
categorized into pre-processing (pmlr-v28-zemel13; ifair; pfr2019), in-
processing (DBLP:conf/iclr/YurochkinBS20; yurochkin2021sensei;
vargo2021individually), and post-processing (petersen2021post) techniques
depending on whether the fix occurs before, during, or after model training,
respectively. Among the categories, we focus on pre-processing because fixing
the data can solve the root cause of unfairness.

The recent pre-processing works LFR (pmlr-v28-zemel13), iFair (ifair), and PFR
(pfr2019) all propose fair representation learning algorithms that optimize
accuracy and individual fairness. Using an adjacency matrix that represents a
fairness graph, the goal is to optimize for a combined objective function with
reconstruction loss and individual fairness loss based on the fairness graph.
In comparison, iFlipper takes the alternative approach of flipping labels to
fix bias, which results in better accuracy-fairness trade-offs and efficiency.

It is also important to understand the in-processing and post-processing
techniques. SenSR (DBLP:conf/iclr/YurochkinBS20) enforces the model to be
invariant under certain sensitive perturbations to the inputs using
adversarial learning. Several extensions have been proposed as well. SenSeI
(yurochkin2021sensei) enforces invariance on certain sensitive sets and uses a
regularization-based approach for jointly optimizing accuracy and fairness,
and BuDRO (vargo2021individually) extends the fairness loss used in SenSR to
use gradient boosting. For post-processing, GLIF (petersen2021post) formulates
a graph smoothening problem and uses Laplacian regularization to enforce
individual fairness. In comparison, iFlipper can complement all these
techniques as we demonstrated with SenSR.

Pre-processing techniques for other fairness measures have been proposed as
well. For group fairness, Kamiran et al. (kamiran2012data) and Calmon et al.
(calmon2017optimized) change features of the training data to remove
dependencies between the sensitive attribute and label and thus achieve
statistical parity. It is worth noting that Kamiran et al. (kamiran2012data)
also proposed label flipping (called massaging) to reduce bias in the data for
group fairness, but not for individual fairness, which is our focus. There is
also a possibility of extending iFlipper to support group fairness. However,
we do not believe iFlipper can directly support group fairness with the
current optimization objective, so an interesting direction is to develop new
label flipping techniques that can support group fairness notions beyond
statistical parity by formulating the right optimization problems.

For causal fairness, Capuchin (salimi2019interventional) makes a connection
between multivalued dependencies (MVDs) and causal fairness, and proposes a
data repair algorithm for MVDs using tuple inserts and deletes that also
ensures causal fairness.

##  6\. Conclusion and Future Work

We proposed iFlipper, which flips labels in the training data to improve the
individual fairness of trained binary classification models. iFlipper uses
pairwise similarity information and minimizes the number of flipped labels to
limit the total error to be within a threshold. We proved that this MIQP
optimization problem is NP-hard. We then converted the problem to an
approximate LP problem, which can be solved efficiently. Our key finding is
that the proposed LP algorithm has theoretical guarantees on how close its
result is to the optimal solution in terms of the number of label flips. In
addition, we further optimized the algorithm without exceeding the total error
limit. We demonstrated on real datasets that iFlipper outperforms pre-
processing unfairness mitigation baselines in terms of fairness and accuracy,
and can complement existing in-processing techniques for better results.

In the future, we would like to support multi-class classification and
regression tasks. For multi-class classification, we can group the labels to
favorable and unfavorable labels and make the problem a binary classification
one. Alternatively, we can solve a one-vs-all problem for each class (binary
classification) and use a softmax to calculate the final label. For
regression, the action becomes changing the label instead of flipping it.
Since the current optimization problem can be extended to support continuous
labels, we plan to change the optimization setup to support regression
problems.

## Acknowledgments

Ki Hyun Tae, Jaeyoung Park, and Steven Euijong Whang were supported by a
Google Research Award and by the National Research Foundation of Korea(NRF)
grant funded by the Korea government(MSIT) (No. NRF-2018R1A5A1059921 and
NRF-2022R1A2C2004382).

##  Appendix A Proof for Theorem 4

We continue from Section 2.2 and provide a full proof for Theorem 4.

Theorem 1. The MIQP problem in Equation 1 is NP-hard.

###### Proof.

We prove that the MIQP problem in Equation 1 is NP-hard by showing its sub-
problem where $W_{ij}$ is binary ($W_{ij}\in\\{0,1\\}^{n\times n}$) is NP-
hard. We prove the sub-problem is NP-hard by reducing it from the well-known
at most $k$-cardinality $s$-$t$ cut problem. Given an undirected graph
$G=(V,E)$, the at most $k$-cardinality minimum $s$-$t$ cut problem is to find
the minimum sum of edge weights in the cut edge set $C$ to divide the vertex
set $V$ into two sets $V_{1}$ and $V_{2}$, where $s\in V_{1}$ and $t\in
V_{2}$, and the cut edge set $C=\\{(v_{1},v_{2})\in E:v_{1}\in V_{1},v_{2}\in
V_{2}\\}$ has at most $k$ edges. This problem is known to be NP-hard even if
all the edge weights are 1 [DBLP:journals/dam/BruglieriME04, kim2021solving,
kratsch2020multi]. Furthermore, the existence of at most $k$-cardinality
$s$-$t$ cut problem is also known to be NP-hard
[DBLP:journals/dam/BruglieriME04].

We will show the reduction as a three-step approach. First, given an instance
of the at most $k$-cardinality $s$-$t$ cut problem on $G=(V,E)$ with all edge
weights equal to 1, we show how to create $k+1$ label flipping problems in
Equation 1 accordingly. Second, we show how a solution to any of the $k+1$
MIQP problems represents an $s$-$t$ cut to the original graph cut problem.
Third, we establish that if there exists an at most $k$-cardinality $s$-$t$
cut, it must be one of the $k+1$ $s$-$t$ cuts obtained in the previous step.

Step 1: We show how to create MIQP problems for a given at most
$k$-cardinality $s$-$t$ cut problem on $G=(V,E)$. We create a variable $y_{i}$
for each $v_{i}\in V-\\{s,t\\}$. We make $W_{ij}=1$ for each edge $(i,j)\in E$
in the graph, and $W_{ij}=0$ for other pairs of $(i,j)$. If a node $v_{i}$ is
only connected to $s$ ($t$), we make $y_{i}^{\prime}=1(0)$ and add
$(y_{i}-y_{i}^{\prime})^{2}$ to the objective function. That is, we set the
initial label of nodes directly connected to $s$ ($t$) as 1 (0). If a node
$v_{i}$ is directly connected to both $s$ and $t$, we add two terms to the
objective function for this node, one with $y_{i}^{\prime}=0$ and the other
one with $y_{i}^{\prime}=1$. If a node $v_{i}$ is not directly connected to
$s$ or $t$, we do not add any terms to the objective. Now that we have defined
all $y_{i}$, their initial assignments $y_{i}^{\prime}$, and the weight
$W_{ij}$, we vary $m$ from 0 to $k$ to create $k+1$ instances of MIQP problems
with different allowed amounts of total error as the constraints.

The intuition for the above process of creating $k+1$ MIQP problem is that an
$s$-$t$ cut is a binary partition of a graph and can be viewed as a binary-
valued labeling process. The nodes that are connected to the source $s$ have
label 1 and the nodes that are connected to sink $t$ have label 0. A cut
consists of two types of edges: $e_{f}$ and $e_{v}$. A flip edge
$e_{f}:(v_{1},v_{2}):v_{1}\in\\{s,t\\},v_{2}\in V-\\{s,t\\}$ is an edge
between $s$ ($t$) and other nodes. If an $e_{f}$ edge exists in a cut, that
means a node which was connected to $s$ ($t$) is no longer in the same
partition as $s$ ($t$), which can be represented as a flip of label. See the
$(s,1)$ edge in Figure 12 as an example for flip edges. A violation edge
$e_{v}:(v_{1},v_{2}):v_{1}\in V-\\{s,t\\},v_{2}\in V-\\{s,t\\}$ is an edge
between two nodes that are not $s$ or $t$. If an $e_{v}$ edge exists in a cut,
that means two nodes that are supposed to be similar and have the same label
ended up in two different partitions, which can be represented as a violation.
See the $(1,2)$ edge in Figure 12 as an example for violation edges. The
cardinality of the cut equals to the sum of the counts of the two types of
edges, which equals to the number of flips and the total error in the MIQP
solution. Our mapping from graph cutting to label flipping is inspired by a
similar process used in image segmentation [kolmogorov2004energy] that aims at
using graph cutting to split an image into foreground and background.

Step 2: We show how a solution to any of the $k+1$ MIQP problems can be mapped
to an $s$-$t$ cut. After solving a corresponding MIQP, we put all nodes with
$y_{i}=1$ in $V_{1}$ and $y_{i}=0$ in $V_{2}$ as the resulting $s$-$t$ cut.
The cardinality of the cut equals to the sum of the number of label flips and
the total error in the label flipping problem.

Figure 12. An example for the $s$-$t$ cut. The cut represented by the blue
dashed line consists of one $e_{f}$ edge, and the cut represented by the red
dotted line consists of two $e_{v}$ edges.

In Figure 12, after removing $s$ and $t$, we get the same graph representation
as Figure 1. By solving the label flipping problem with $m$ equal to 0 or 1,
the resulting label assignment is $y_{4}=1$ and $y_{1}=y_{2}=y_{3}=0$. The
corresponding cut is shown as the blue dashed line in Figure 12. The cut is
$V_{1}=\\{s,4\\},V_{2}=\\{1,2,3,t\\},\text{ and }C=\\{(s,1)\\}$. This label
assignment has one flip (node 1 flips to label 0) and zero violations. This
flip is represented as an $e_{f}$ edge (s,1) in the cut. If we solve the
problem with $m=2$, the result is $y_{1}=y_{4}=1$ and $y_{2}=y_{3}=0$. The
corresponding cut is shown as the red dotted line in Figure 12. The cut is
$V_{1}=\\{s,1,4\\},V_{2}=\\{2,3,t\\},\text{ and }C=\\{(1,2),(1,3)\\}$. This
label assignment has zero flips and a total error of 2, represented by two
$e_{v}$ edges in the cut: (1,2) and (1,3).

Step 3: Since the cardinality of the cut equals to the sum of the number of
label flips and the total error in the label flipping problem, finding an at
most $k$-cardinality $s$-$t$ cut can be solved by finding a label assignment
where the sum of flips and the total error equals to at most $k$. To find such
a label assignment, we can repeatedly solve the MIQP problem $k+1$ times, for
all $m$ values in {0, $\ldots$, $k$}, and check if the sum of label flips and
the total error is less than or equal to $k$. The $k$-cardinality minimum
$s$-$t$ cut, if exists, must equal to the result of the MIQP problem with at
least one of the possible $m$ values. Therefore, if the label flipping MIQP
problem is not NP-hard, then the $k$-cardinality minimum $s$-$t$ cut problem
would also not be NP-hard, which contradicts the known results.

∎

##  Appendix B Proof for Lemma 0.1

We continue from Section 3.3 and provide a full proof for Lemma 0.1. Here we
restate Lemma 0.1 with the problem setup:

Lemma 2.1. Suppose an $\alpha$-cluster has $A_{0}$ points whose initial labels
are 0 and $A_{1}$ points whose initial values are 1. Let
$N_{\alpha}=A_{0}-A_{1}$. Now suppose there are $U$ nodes connected to the
$\alpha$-cluster (shown in Figure 13) by an edge $W_{a_{i}\alpha}$ satisfying

$\begin{split}&0\leq a_{1}\leq...\leq a_{k}<\alpha<a_{k+1}\leq...\leq
a_{U}\leq 1.\end{split}$

Note that there is no connected node with a value of $\alpha$ by construction.
Let
$S_{\alpha}=\sum_{i=1}^{k}W_{a_{i}\alpha}-\sum_{i=k+1}^{U}W_{a_{i}\alpha}$.
Let us also add the following nodes for convenience: $a_{0}=0$ and
$a_{U+1}=1$. For an $\alpha$-cluster with $N_{\alpha}=0$ in the optimal
solution, we can always convert $\alpha$ to either $a_{k}$ or $a_{k+1}$ while
maintaining an optimal solution. As a result, we can reduce exactly one
non-0/1 value in the optimal solution.

Figure 13. Problem setup for Lemma 0.1.

###### Proof.

We compute the initial number of flips and total error in Figure 13 as
follows:

(11) $\begin{split}&\\#\text{ Flips}=\alpha A_{0}+(1-\alpha)A_{1}=A_{1}+\alpha
N_{\alpha}=A_{1}(\because N_{\alpha}=0)\\\ &\text{Total
Error}=\sum_{i=1}^{U}W_{a_{i}\alpha}|a_{i}-\alpha|=S_{\alpha}\alpha+C\\\
&\qquad\qquad\quad(C=-\sum_{i=1}^{k}W_{a_{i}\alpha}a_{i}+\sum_{i=k+1}^{U}W_{a_{i}\alpha}a_{i})\\\
\end{split}$

We first observe that the number of flips is independent of the $\alpha$
value. Hence, even if we change $\alpha$ to an arbitrary value, the solution
still has the same objective value.

Now consider a small positive value $\epsilon_{\alpha}$. Suppose we change
$\alpha$ by $\epsilon_{\alpha}$ such that

(12) $0\leq a_{1}\leq...\leq a_{k}\leq\alpha+\epsilon_{\alpha}\leq
a_{k+1}\leq...\leq a_{U}\leq 1\\\ $

Similarly, we also change $\alpha$ by $-\epsilon_{\alpha}$ such that

(13) $0\leq a_{1}\leq...\leq a_{k}\leq\alpha-\epsilon_{\alpha}\leq
a_{k+1}\leq...\leq a_{U}\leq 1\\\ $

Note that such $\epsilon_{\alpha}$ always exists because
$a_{k}<\alpha<a_{k+1}$. If we change $\alpha$ to $\alpha+\epsilon_{\alpha}$
while satisfying Equation 12, the total error becomes
$S_{\alpha}(\alpha+\epsilon_{\alpha})+C$. Similarly, if we change $\alpha$ to
$\alpha-\epsilon_{\alpha}$ while satisfying Equation 13, the total error
becomes $S_{\alpha}(\alpha-\epsilon_{\alpha})+C$. Hence, the change in the
total error for each case can be computed as follows:

(14) $\begin{split}&\alpha+\epsilon_{\alpha}\rightarrow{}\Delta(\text{Total
Error})=S_{\alpha}\epsilon_{\alpha}\\\
&\alpha-\epsilon_{\alpha}\rightarrow{}\Delta(\text{Total
Error})=-S_{\alpha}\epsilon_{\alpha}\\\ \end{split}$

From Equation 14, we observe that one of the transformations always maintains
or even reduces the total error according to the sign of $S_{\alpha}$, i.e.,
the solution is feasible. Specifically, if $S_{\alpha}\leq 0$, we change
$\alpha$ to $a_{k+1}$ by setting $\epsilon_{\alpha}=a_{k+1}-\alpha$, otherwise
we change $\alpha$ to $a_{k}$ by setting $\epsilon_{\alpha}=\alpha-a_{k}$. As
a result, we can remove one non-0/1 value $\alpha$ while maintaining an
optimal solution.

∎

##  Appendix C Proof for Lemma 0.2

We continue from Section 3.3 and provide a full proof for Lemma 0.2. Here we
restate Lemma 0.2 with the problem setup:

Lemma 2.2.  Let us assume that 0 ¡ $\alpha$ ¡ $\beta$ ¡ 1, and the sum of the
pairwise node similarities between the two clusters between the two clusters
is $E$. Suppose an $\alpha$-cluster and a $\beta$-cluster have $A_{0}$ and
$B_{0}$ points whose initial labels are 0, respectively, and $A_{1}$ and
$B_{1}$ points whose initial values are 1, respectively. Let
$N_{\alpha}=A_{0}-A_{1}$ and $N_{\beta}=B_{0}-B_{1}$. Now suppose there are
$U$ nodes connected to the $\alpha$-cluster by an edge $W_{a_{i}\alpha}$ and
$V$ nodes connected to the $\beta$-cluster by an edge $W_{b_{i}\beta}$
satisfying

$\begin{split}&0\leq a_{1}\leq...\leq a_{k}<\alpha<a_{k+1}\leq...\leq
a_{U}\leq 1\text{ and }\\\ &0\leq b_{1}\leq...\leq
b_{l}<\beta<b_{l+1}\leq...\leq b_{V}\leq 1.\end{split}$

Note that there is no connected node with a value of $\alpha$ or $\beta$ by
construction. Let
$S_{\alpha}=\sum_{i=1}^{k}W_{a_{i}\alpha}-\sum_{i=k+1}^{U}W_{a_{i}\alpha}$ and
$S_{\beta}=\sum_{i=1}^{l}W_{b_{i}\beta}-\sum_{i=l+1}^{V}W_{b_{i}\beta}$. Let
us also add the following nodes for convenience: $a_{0}=0$, $a_{U+1}=1$,
$b_{0}=0$, and $b_{V+1}=1$. For an $\alpha$-cluster with $N_{\alpha}\neq 0$
and a $\beta$-cluster with $N_{\beta}\neq 0$ in the optimal solution, we can
always convert $(\alpha,\beta)$ to one of
$(a_{k},\beta+\frac{N_{\alpha}}{N_{\beta}}(a_{k}-\alpha))$,
$(a_{k+1},\beta-\frac{N_{\alpha}}{N_{\beta}}(a_{k+1}-\alpha))$,
$(\alpha+\frac{N_{\beta}}{N_{\alpha}}(\beta-b_{l}),b_{l})$,
$(\alpha-\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta),b_{l+1})$, or
$(\frac{\alpha N_{\alpha}+\beta N_{\beta}}{N_{\alpha}+N_{\beta}},\frac{\alpha
N_{\alpha}+\beta N_{\beta}}{N_{\alpha}+N_{\beta}})$, while maintaining an
optimal solution. As a result, we can reduce at least one non-0/1 value in the
optimal solution.

Figure 14. Problem setup for Lemma 0.2.

###### Proof.

We compute the initial number of flips and total error in Figure 14 as
follows:

(15) $\begin{split}&\\#\text{ Flips}=\alpha A_{0}+(1-\alpha)A_{1}+\beta
B_{0}+(1-\beta)B_{1}=A_{1}+B_{1}+\alpha N_{\alpha}+\beta N_{\beta}\\\
&\text{Total
Error}=\sum_{i=1}^{U}W_{a_{i}\alpha}|a_{i}-\alpha|+\sum_{i=1}^{V}W_{b_{i}\beta}|b_{i}-\beta|+E(\beta-\alpha)\\\
&\qquad\qquad\qquad\;=(S_{\alpha}-E)\alpha+(S_{\beta}+E)\beta+C\\\
&\quad(C=-\sum_{i=1}^{k}W_{a_{i}\alpha}a_{i}+\sum_{i=k+1}^{U}W_{a_{i}\alpha}a_{i}-\sum_{i=1}^{l}W_{b_{i}\beta}b_{i}+\sum_{i=l+1}^{V}W_{b_{i}\beta}b_{i})\\\
\end{split}$

Now consider two small positive values $\epsilon_{\alpha}$ and
$\epsilon_{\beta}$. Both $N_{\alpha}$ and $N_{\beta}$ are non-zero, so we have
only two cases: $\frac{N_{\alpha}}{N_{\beta}}<0$ and
$\frac{N_{\alpha}}{N_{\beta}}>0$.

Case 1 $\frac{N_{\alpha}}{N_{\beta}}<0$: Suppose we change $\alpha$ by
$\epsilon_{\alpha}$ and $\beta$ by $\epsilon_{\beta}$, respectively, such that

(16) $\begin{gathered}0\leq a_{1}\leq...\leq
a_{k}\leq\alpha+\epsilon_{\alpha}\leq a_{k+1}\leq...\leq a_{U}\leq 1\\\ 0\leq
b_{1}\leq...\leq b_{l}\leq\beta+\epsilon_{\beta}\leq b_{l+1}\leq...\leq
b_{V}\leq 1\\\ \alpha+\epsilon_{\alpha}\leq\beta+\epsilon_{\beta}\\\
\end{gathered}$

We then compute the number of flips for
$(\alpha+\epsilon_{\alpha},\beta+\epsilon_{\beta})$ as
$A_{1}+B_{1}+(\alpha+\epsilon_{\alpha})N_{\alpha}+(\beta+\epsilon_{\beta})N_{\beta}$.
In order to have the same number of flips as the initial value in Equation 15,
($\epsilon_{\alpha}$, $\epsilon_{\beta}$) should satisfy
$\epsilon_{\alpha}N_{\alpha}+\epsilon_{\beta}N_{\beta}=0$.

Similarly, we also change $\alpha$ by $-\epsilon_{\alpha}$ and $\beta$ by
$-\epsilon_{\beta}$, respectively, such that

(17) $\begin{gathered}0\leq a_{1}\leq...\leq
a_{k}\leq\alpha-\epsilon_{\alpha}\leq a_{k+1}\leq...\leq a_{U}\leq 1\\\ 0\leq
b_{1}\leq...\leq b_{l}\leq\beta-\epsilon_{\beta}\leq b_{l+1}\leq...\leq
b_{V}\leq 1\\\ \alpha-\epsilon_{\alpha}\leq\beta-\epsilon_{\beta}\\\
\end{gathered}$

In this case, $(\alpha-\epsilon_{\alpha},\beta-\epsilon_{\beta})$ also
maintains the same number of label flips if
$\epsilon_{\alpha}N_{\alpha}+\epsilon_{\beta}N_{\beta}=0$.

From now, we consider ($\epsilon_{\alpha}$, $\epsilon_{\beta}$) that also
satisfies $\epsilon_{\alpha}N_{\alpha}+\epsilon_{\beta}N_{\beta}=0$, i.e.,
$\epsilon_{\beta}=-\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$. Note that
such $\epsilon_{\alpha}$ and $\epsilon_{\beta}$ always exist because
$a_{k}<\alpha<a_{k+1}$, $b_{l}<\beta<b_{l+1}$, and
$\frac{N_{\alpha}}{N_{\beta}}<0$. Therefore, both
$(\alpha+\epsilon_{\alpha},\beta+\epsilon_{\beta})$ and
$(\alpha-\epsilon_{\alpha},\beta-\epsilon_{\beta})$ have the same number of
label flipping as the initial number.

If we change $(\alpha,\beta)$ to
$(\alpha+\epsilon_{\alpha},\beta+\epsilon_{\beta})$ while satisfying Equation
16 and $\epsilon_{\alpha}N_{\alpha}+\epsilon_{\beta}N_{\beta}=0$, the total
error becomes
$(S_{\alpha}-E)(\alpha+\epsilon_{\alpha})+(S_{\beta}+E)(\beta+\epsilon_{\beta})+C$.
Similarly, if we change $(\alpha,\beta)$ to
$(\alpha-\epsilon_{\alpha},\beta-\epsilon_{\beta})$ while satisfying Equation
17 and $\epsilon_{\alpha}N_{\alpha}+\epsilon_{\beta}N_{\beta}=0$, the total
error becomes
$(S_{\alpha}-E)(\alpha-\epsilon_{\alpha})+(S_{\beta}+E)(\beta-\epsilon_{\beta})+C$.
Hence, the change in the total error for each case can be computed as follows:

(18)
$\begin{split}(\alpha+\epsilon_{\alpha},\beta+\epsilon_{\beta})\rightarrow{}&\Delta(\text{Total
Error})=(S_{\alpha}-E)\epsilon_{\alpha}+(S_{\beta}+E)\epsilon_{\beta}\\\
&=\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}\\\
(\alpha-\epsilon_{\alpha},\beta-\epsilon_{\beta})\rightarrow{}&\Delta(\text{Total
Error})=-(S_{\alpha}-E)\epsilon_{\alpha}-(S_{\beta}+E)\epsilon_{\beta}\\\
&=-\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}\\\
\end{split}$

From Equation 18, we observe that one of the transformations always maintains
or even reduces the total error according to the sign of
$\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}$, i.e., the
solution is feasible.

  * •

If $\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}\leq 0$,
we change $(\alpha,\beta)$ to
$(\alpha+\epsilon_{\alpha},\beta+\epsilon_{\beta})$ so that the solution is
still optimal. Recall $(\epsilon_{\alpha},\epsilon_{\beta})$ satisfies the
three inequalities and one condition: $\alpha+\epsilon_{\alpha}\leq a_{k+1}$,
$\beta+\epsilon_{\beta}\leq b_{l+1}$,
$\alpha+\epsilon_{\alpha}\leq\beta+\epsilon_{\beta}$, and
$\epsilon_{\alpha}N_{\alpha}+\epsilon_{\beta}N_{\beta}=0$. Among the possible
$(\epsilon_{\alpha},\epsilon_{\beta})$, we choose the upper bound of
$\epsilon_{\alpha}$ and the corresponding $\epsilon_{\beta}$
($\epsilon_{\beta}=-\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$). To get an
upper bound of $\epsilon_{\alpha}$, we find the equality conditions for each
inequality and take the smallest value among them. If
$1+\frac{N_{\alpha}}{N_{\beta}}\leq 0$, the last inequality
($\alpha+\epsilon_{\alpha}\leq\beta+\epsilon_{\beta}$) always hold because
$\epsilon_{\alpha}\leq\epsilon_{\beta}$. Hence, we consider only the first two
inequalities and set $\epsilon_{\alpha}$ to
$min(a_{k+1}-\alpha,-\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta)$. On the
other hand, if $1+\frac{N_{\alpha}}{N_{\beta}}>0$, we set $\epsilon_{\alpha}$
to
$min(a_{k+1}-\alpha,-\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta),\frac{N_{\beta}(\beta-\alpha)}{N_{\alpha}+N_{\beta}})$
from the three inequalities. As a result, we can convert $(\alpha,\beta)$ to
$(a_{k+1},\beta-\frac{N_{\alpha}}{N_{\beta}}(a_{k+1}-\alpha))$,
$(\alpha-\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta),b_{l+1})$, or
$(\frac{\alpha N_{\alpha}+\beta N_{\beta}}{N_{\alpha}+N_{\beta}},\frac{\alpha
N_{\alpha}+\beta N_{\beta}}{N_{\alpha}+N_{\beta}})$, which is one of the cases
in Lemma 0.2.

  * •

If $\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}>0$, we
change $(\alpha,\beta)$ to $(\alpha-\epsilon_{\alpha},\beta-\epsilon_{\beta})$
so that the solution is still optimal. Recall
$(\epsilon_{\alpha},\epsilon_{\beta})$ satisfies the three inequalities and
one condition: $a_{k}\leq\alpha-\epsilon_{\alpha}$,
$b_{l}\leq\beta-\epsilon_{\beta}$,
$\alpha-\epsilon_{\alpha}\leq\beta-\epsilon_{\beta}$, and
$\epsilon_{\alpha}N_{\alpha}+\epsilon_{\beta}N_{\beta}=0$. Among the possible
$(\epsilon_{\alpha},\epsilon_{\beta})$, we choose the upper bound of
$\epsilon_{\alpha}$ and the corresponding $\epsilon_{\beta}$
($\epsilon_{\beta}=-\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$). To get an
upper bound of $\epsilon_{\alpha}$, we find the equality conditions for each
inequality and take the smallest value among them. If
$1+\frac{N_{\alpha}}{N_{\beta}}\geq 0$, the last inequality
($\alpha-\epsilon_{\alpha}\leq\beta-\epsilon_{\beta}$) always holds because
$\epsilon_{\alpha}\geq\epsilon_{\beta}$. Hence, we consider only the first two
inequalities and set $\epsilon_{\alpha}$ to $min(\alpha-
a_{k},-\frac{N_{\beta}}{N_{\alpha}}(\beta-b_{l})$. On the other hand, if
$1+\frac{N_{\alpha}}{N_{\beta}}<0$, we set $\epsilon_{\alpha}$ to $min(\alpha-
a_{k},-\frac{N_{\beta}}{N_{\alpha}}(\beta-
b_{l}),-\frac{N_{\beta}(\beta-\alpha)}{N_{\alpha}+N_{\beta}})$ from the three
inequalities. As a result, we can convert $(\alpha,\beta)$ to
$(a_{k},\beta+\frac{N_{\alpha}}{N_{\beta}}(\alpha-a_{k}))$,
$(\alpha+\frac{N_{\beta}}{N_{\alpha}}(\beta-b_{l}),b_{l})$, or $(\frac{\alpha
N_{\alpha}+\beta N_{\beta}}{N_{\alpha}+N_{\beta}},\frac{\alpha
N_{\alpha}+\beta N_{\beta}}{N_{\alpha}+N_{\beta}})$, which is one of the cases
in Lemma 0.2.

Case 2: $\frac{N_{\alpha}}{N_{\beta}}>0$: The proof is similar to the proof
for Case 1 except that we consider
$(\alpha+\epsilon_{\alpha},\beta-\epsilon_{\beta})$ and
$(\alpha-\epsilon_{\alpha},\beta+\epsilon_{\beta})$ instead of
$(\alpha+\epsilon_{\alpha},\beta+\epsilon_{\beta})$ and
$(\alpha-\epsilon_{\alpha},\beta-\epsilon_{\beta})$. We now write the full
proof for Case 2 for completeness.

Suppose we change $\alpha$ by $\epsilon_{\alpha}$ and $\beta$ by
$-\epsilon_{\beta}$, respectively, such that

(19) $\begin{gathered}0\leq a_{1}\leq...\leq
a_{k}\leq\alpha+\epsilon_{\alpha}\leq a_{k+1}\leq...\leq a_{U}\leq 1\\\ 0\leq
b_{1}\leq...\leq b_{l}\leq\beta-\epsilon_{\beta}\leq b_{l+1}\leq...\leq
b_{V}\leq 1\\\ \alpha+\epsilon_{\alpha}\leq\beta-\epsilon_{\beta}\\\
\end{gathered}$

We then compute the number of flips for
$(\alpha+\epsilon_{\alpha},\beta-\epsilon_{\beta})$ as
$A_{1}+B_{1}+(\alpha+\epsilon_{\alpha})N_{\alpha}+(\beta-\epsilon_{\beta})N_{\beta}$.
In order to have the same number of flips as the initial value in Equation 15,
($\epsilon_{\alpha}$, $\epsilon_{\beta}$) should satisfy
$\epsilon_{\alpha}N_{\alpha}-\epsilon_{\beta}N_{\beta}=0$.

Similarly, we also change $\alpha$ by $-\epsilon_{\alpha}$ and $\beta$ by
$\epsilon_{\beta}$, respectively, such that

(20) $\begin{gathered}0\leq a_{1}\leq...\leq
a_{k}\leq\alpha-\epsilon_{\alpha}\leq a_{k+1}\leq...\leq a_{U}\leq 1\\\ 0\leq
b_{1}\leq...\leq b_{l}\leq\beta+\epsilon_{\beta}\leq b_{l+1}\leq...\leq
b_{V}\leq 1\\\ \alpha-\epsilon_{\alpha}\leq\beta+\epsilon_{\beta}\\\
\end{gathered}$

In this case, $(\alpha-\epsilon_{\alpha},\beta+\epsilon_{\beta})$ also
maintains the same number of label flips if
$\epsilon_{\alpha}N_{\alpha}-\epsilon_{\beta}N_{\beta}=0$.

From now, we consider ($\epsilon_{\alpha}$, $\epsilon_{\beta}$) that also
satisfies $\epsilon_{\alpha}N_{\alpha}-\epsilon_{\beta}N_{\beta}=0$, i.e.,
$\epsilon_{\beta}=\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$. Note that
such ($\epsilon_{\alpha}$ and $\epsilon_{\beta}$) always exist because
$a_{k}<\alpha<a_{k+1}$, $b_{l}<\beta<b_{l+1}$, and
$\frac{N_{\alpha}}{N_{\beta}}>0$. Therefore, both
$(\alpha+\epsilon_{\alpha},\beta-\epsilon_{\beta})$ and
$(\alpha-\epsilon_{\alpha},\beta+\epsilon_{\beta})$ have the same number of
label flipping as the initial number.

If we change $(\alpha,\beta)$ to
$(\alpha+\epsilon_{\alpha},\beta-\epsilon_{\beta})$ while satisfying Equation
19 and $\epsilon_{\alpha}N_{\alpha}-\epsilon_{\beta}N_{\beta}=0$, the total
error becomes
$(S_{\alpha}-E)(\alpha+\epsilon_{\alpha})+(S_{\beta}+E)(\beta-\epsilon_{\beta})+C$.
Similarly, if we change $(\alpha,\beta)$ to
$(\alpha-\epsilon_{\alpha},\beta+\epsilon_{\beta})$ while satisfying Equation
20 and $\epsilon_{\alpha}N_{\alpha}-\epsilon_{\beta}N_{\beta}=0$, the total
error becomes
$(S_{\alpha}-E)(\alpha-\epsilon_{\alpha})+(S_{\beta}+E)(\beta+\epsilon_{\beta})+C$.
Hence, the change in the total error for each case can be computed as follows:

(21)
$\begin{split}(\alpha+\epsilon_{\alpha},\beta-\epsilon_{\beta})\rightarrow{}&\Delta(\text{Total
Error})=(S_{\alpha}-E)\epsilon_{\alpha}-(S_{\beta}+E)\epsilon_{\beta}\\\
&=\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}\\\
(\alpha-\epsilon_{\alpha},\beta+\epsilon_{\beta})\rightarrow{}&\Delta(\text{Total
Error})=-(S_{\alpha}-E)\epsilon_{\alpha}+(S_{\beta}+E)\epsilon_{\beta}\\\
&=-\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}\\\
\end{split}$

From Equation 21, we observe that one of the transformations always maintains
or reduces the total error according to the sign of
$\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}$, i.e., the
solution is feasible.

  * •

If $\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}\leq 0$,
we can change $(\alpha,\beta)$ to
$(\alpha+\epsilon_{\alpha},\beta-\epsilon_{\beta})$ so that the solution is
still optimal. Recall $(\epsilon_{\alpha},\epsilon_{\beta})$ satisfies the
three inequalities and one condition: $\alpha+\epsilon_{\alpha}\leq a_{k+1}$,
$b_{l+1}\leq\beta-\epsilon_{\beta}$,
$\alpha+\epsilon_{\alpha}\leq\beta+\epsilon_{\beta}$, and
$\epsilon_{\alpha}N_{\alpha}-\epsilon_{\beta}N_{\beta}=0$. Among the possible
$(\epsilon_{\alpha},\epsilon_{\beta})$, we choose the upper bound of
$\epsilon_{\alpha}$ and the corresponding $\epsilon_{\beta}$
($\epsilon_{\beta}=\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$). To get an
upper bound of $\epsilon_{\alpha}$, we find the equality conditions for each
inequality and take the smallest value among them. Specifically, we set
$\epsilon_{\alpha}$ to $min(a_{k+1}-\alpha,\frac{N_{\beta}}{N_{\alpha}}(\beta-
b_{l}),\frac{N_{\beta}(\beta-\alpha)}{N_{\alpha}+N_{\beta}})$ and
$\epsilon_{\beta}$. As a result, we can convert $(\alpha,\beta)$ to
$(a_{k+1},\beta-\frac{N_{\alpha}}{N_{\beta}}(a_{k+1}-\alpha))$,
$(\alpha+\frac{N_{\beta}}{N_{\alpha}}(\beta-b_{l}),b_{l})$, or $(\frac{\alpha
N_{\alpha}+\beta N_{\beta}}{N_{\alpha}+N_{\beta}},\frac{\alpha
N_{\alpha}+\beta N_{\beta}}{N_{\alpha}+N_{\beta}})$, which is one of the cases
in Lemma 0.2.

  * •

If $\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}>0$, we
can change $(\alpha,\beta)$ to
$(\alpha-\epsilon_{\alpha},\beta+\epsilon_{\beta})$ so that the solution is
still optimal. Recall $(\epsilon_{\alpha},\epsilon_{\beta})$ satisfies the
three inequalities and one condition: $a_{k}\leq\alpha-\epsilon_{\alpha}$,
$\beta+\epsilon_{\beta}\leq b_{l+1}$,
$\alpha-\epsilon_{\alpha}\leq\beta+\epsilon_{\beta}$, and
$\epsilon_{\alpha}N_{\alpha}-\epsilon_{\beta}N_{\beta}=0$. Among the possible
$(\epsilon_{\alpha},\epsilon_{\beta})$, we choose the upper bound of
$\epsilon_{\alpha}$ and the corresponding $\epsilon_{\beta}$
($\epsilon_{\beta}=\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$). To get an
upper bound of $\epsilon_{\alpha}$, we find the equality conditions for each
inequality and take the smallest value among them. In this case, the last
inequality ($\alpha-\epsilon_{\alpha}\leq\beta+\epsilon_{\beta}$) always hold.
Hence, we consider only the first two conditions and set $\epsilon_{\alpha}$
to $min(\alpha-a_{k},\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta))$. As a
result, we can convert $(\alpha,\beta)$ to either
$(a_{k},\beta+\frac{N_{\alpha}}{N_{\beta}}(a_{k}-\alpha))$ or
$(\alpha-\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta),b_{l+1})$, which is one
of the cases in Lemma 0.2.

We summarize the main results for each case below and conclude that
$(\alpha,\beta)$ can be transformed into one of the five cases in Lemma 0.2
while maintaining an optimal optimal. As a result, we remove at least one of
$\alpha$ and $\beta$. If both converted values already exist in the solution,
we can even reduce two non-0/1 values.

  * •

If ($\frac{N_{\alpha}}{N_{\beta}}<0$,
$\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}\leq 0$,
$1+\frac{N_{\alpha}}{N_{\beta}}\leq 0$), we convert $(\alpha,\beta)$ to
$(\alpha+\epsilon_{\alpha},\beta+\epsilon_{\beta})$ where
$\epsilon_{\alpha}=min(a_{k+1}-\alpha,-\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta)$
and $\epsilon_{\beta}=-\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$.

  * •

If ($\frac{N_{\alpha}}{N_{\beta}}<0$,
$\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}\leq 0$,
$1+\frac{N_{\alpha}}{N_{\beta}}>0$), we convert $(\alpha,\beta)$ to
$(\alpha+\epsilon_{\alpha},\beta+\epsilon_{\beta})$ where
$\epsilon_{\alpha}=min(a_{k+1}-\alpha,-\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta),\frac{N_{\beta}(\beta-\alpha)}{N_{\alpha}+N_{\beta}})$
and $\epsilon_{\beta}=-\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$.

  * •

If ($\frac{N_{\alpha}}{N_{\beta}}<0$,
$\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}>0$,
$1+\frac{N_{\alpha}}{N_{\beta}}\geq 0$), we convert $(\alpha,\beta)$ to
$(\alpha-\epsilon_{\alpha},\beta-\epsilon_{\beta})$ where
$\epsilon_{\alpha}=min(\alpha-a_{k},-\frac{N_{\beta}}{N_{\alpha}}(\beta-
b_{l})$ and $\epsilon_{\beta}=-\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$.

  * •

If ($\frac{N_{\alpha}}{N_{\beta}}<0$,
$\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}>0$,
$1+\frac{N_{\alpha}}{N_{\beta}}<0$), we convert $(\alpha,\beta)$ to
$(\alpha-\epsilon_{\alpha},\beta-\epsilon_{\beta})$ where
$\epsilon_{\alpha}=min(\alpha-a_{k},-\frac{N_{\beta}}{N_{\alpha}}(\beta-
b_{l}),-\frac{N_{\beta}(\beta-\alpha)}{N_{\alpha}+N_{\beta}})$ and
$\epsilon_{\beta}=-\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$.

  * •

If ($\frac{N_{\alpha}}{N_{\beta}}>0$,
$\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}\leq 0$), we
convert $(\alpha,\beta)$ to
$(\alpha+\epsilon_{\alpha},\beta-\epsilon_{\beta})$ where
$\epsilon_{\alpha}=min(a_{k+1}-\alpha,\frac{N_{\beta}}{N_{\alpha}}(\beta-
b_{l}),\frac{N_{\beta}(\beta-\alpha)}{N_{\alpha}+N_{\beta}})$ and
$\epsilon_{\beta}=\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$.

  * •

If ($\frac{N_{\alpha}}{N_{\beta}}>0$,
$\frac{(S_{\alpha}-E)N_{\beta}-(S_{\beta}+E)N_{\alpha}}{N_{\beta}}>0$), we
convert $(\alpha,\beta)$ to
$(\alpha-\epsilon_{\alpha},\beta+\epsilon_{\beta})$ where
$\epsilon_{\alpha}=min(\alpha-
a_{k},\frac{N_{\beta}}{N_{\alpha}}(b_{l+1}-\beta))$ and
$\epsilon_{\beta}=\frac{N_{\alpha}}{N_{\beta}}\epsilon_{\alpha}$.

∎

##  Appendix D Trade-off for other datasets

We continue from Section 4.2 and show the trade-off results on the AdultCensus
and Credit datasets in Figure 15. The results are similar to the COMPAS
dataset in Figure 7 where there is a clear trade-off between accuracy and
fairness.

(a) AdultCensus

(b) Credit

Figure 15. Trade-off curves on the AdultCensus and Credit datasets.

##  Appendix E Bank and LSAC Datasets Results

We continue from Section 4.1 and show experimental results on the Bank and
LSAC datasets when training a logistic regression model. Table 7 shows
consistency scores with respect to the threshold-based similarity matrix. As a
result, both datasets have almost 1.0 consistency scores, which means that
they are already inherently fair in terms of individual fairness. The reason
is that these datasets have much smaller total errors compared to other
fairness datasets.

Dataset | Test Accuracy | Consistency Score
---|---|---
Bank | 0.956 | 0.997
LSAC | 0.825 | 0.986
Table 7. Accuracy and fairness results using logistic regression on the Bank
and LSAC datasets.

##  Appendix F Optimization Solutions for COMPAS

We continue from Section 4.4 and perform the same experiments on the COMPAS
dataset where we use the kNN-based similarity matrix. In Figure 16, the key
trends are still similar to Figure 10 where iFlipper (1) always satisfies the
total error limit while Greedy and Gradient result in infeasible solutions for
some cases while KMeans returns feasible solutions, but flips too many labels
(Figure 16(a)), (2) provides the solution closest to the optimal in terms the
number of label flips (Figure 16(b)), and (3) is much faster than other
optimization solutions (Figure 16(c)). Compared to the AdultCensus results in
Figure 10, iFlipper is the most efficient because the COMPAS dataset is
relatively small and has a smaller total error.

(a) Total error

(b) Number of flips

(c) Runtime (sec)

Figure 16. A detailed comparison of iFlipper against three naïve solutions
(Greedy, Gradient, and KMeans) and ILP solver on the COMPAS dataset where we
use the kNN-based similarity matrix. Here the initial amount of total error is
16,454.0. We show the results for three different total error limits ($m$).
All three subfigures use the same legends.

##  Appendix G Ablation Study for COMPAS dataset

We continue from Section 4.5 and provide the ablation study for the COMPAS
dataset where we use the kNN-based similarity matrix in Figure 17. The
observations are similar to those of Figure 11 where both adaptive rounding
and reverse greedy algorithms are necessary for iFlipper to provide a near-
exact solution. In addition, Table 8 shows the average runtime of each
component in iFlipper in Figure 17 and the results are similar to Table 4
where the proposed algorithms are efficient in practice.

(a) Total error

(b) Number of flips

Figure 17. Ablation study for iFlipper on the COMPAS dataset and the kNN-based similarity matrix. Method | Avg. Runtime (sec)
---|---
LP Solver (effectively includes Alg. 1) | 5.87
\+ Adaptive Rounding (Alg. 3) | 0.09
\+ Reverse Greedy (Alg. 4) | 2.19
Table 8. Avg. runtimes of iFlipper’s components in Figure 17.

##  Appendix H Comparison with other ML models

In Section 4.3, we compared iFlipper with the baselines using logistic
regression. In this section, we perform the same experiments using random
forest and neural network models. Figure 18 and Figure 19 are the trade-off
results using the random forest and neural network, respectively. The key
trends are still similar to Figure 8 where iFlipper consistently outperforms
the baselines in terms of accuracy and fairness. The results clearly
demonstrate that how iFlipper’s pre-processing algorithm benefits various ML
models.

(a) COMPAS-kNN

(b) AdultCensus-kNN

(c) Credit-kNN

(d) COMPAS-threshold

(e) AdultCensus-threshold

(f) Credit-threshold

Figure 18. Accuracy-fairness trade-offs of random forest on the three datasets
using the two similarity matrices. In addition to the four methods LFR, iFair,
PFR, and iFlipper, we add the result of model training without any pre-
processing and call it “Original.” As a result, only iFlipper shows a clear
accuracy and fairness trade-off.

(a) COMPAS-kNN

(b) AdultCensus-kNN

(c) Credit-kNN

(d) COMPAS-threshold

(e) AdultCensus-threshold

(f) Credit-threshold

Figure 19. Accuracy-fairness trade-offs of neural network on the three
datasets using the two similarity matrices. In addition to the four methods
LFR, iFair, PFR, and iFlipper, we add the result of model training without any
pre-processing and call it “Original.” As a result, only iFlipper shows a
clear accuracy and fairness trade-off.