11institutetext: Moscow Institute of Physics and Technology, Moscow, Russia
22institutetext: Yandex, Moscow, Russia

# Local clustering coefficient in generalized preferential attachment
models††thanks: This is an extended version of the paper appeared in Proc.
WAW’15, LNCS 9479, pp. 15-28, 2015. ††thanks: This work is supported by
Russian Science Foundation (grant number 16-11-10014).

Alexander Krot 11 Liudmila Ostroumova Prokhorenkova 1122

###### Abstract

In this paper, we analyze the local clustering coefficient of preferential
attachment models. A general approach to preferential attachment was
introduced in [18], where a wide class of models (PA-class) was defined in
terms of constraints that are sufficient for the study of the degree
distribution and the clustering coefficient. It was previously shown that the
degree distribution in all models of the PA-class follows a power law. Also,
the global clustering coefficient was analyzed and a lower bound for the
average local clustering coefficient was obtained. We expand the results of
[18] by analyzing the local clustering coefficient for the PA-class of models.
Namely, we analyze the behavior of $C(d)$ which is the average local
clustering for the vertices of degree $d$.

Keywords: networks, random graph models, preferential attachment, clustering
coefficient.

##  1 Introduction

Nowadays there are a lot of practical problems connected with the analysis of
growing real-world networks, from Internet and society networks [1, 5, 8] to
biological networks [2]. Models of real-world networks are used in physics,
information retrieval, data mining, bioinformatics, etc. An extensive review
of real-world networks and their applications can be found elsewhere (e.g.,
see [1, 5, 6, 15]).

It turns out that many real-world networks of diverse nature have some typical
properties: small diameter, power-law degree distribution, high clustering,
and others [13, 16, 17, 23]. Probably the most extensively studied property of
networks is their vertex degree distribution. For the majority of studied
real-world networks, the portion of vertices with degree $d$ was observed to
decrease as $d^{-\gamma}$, usually with $2<\gamma<3$ [3, 4, 5, 9, 12].

Another important characteristic of a network is its clustering coefficient,
which has the following two most used versions: the global clustering
coefficient and the average local clustering coefficient (see Section 2.3 for
the definitions). It is believed that for many real-world networks both the
average local and the global clustering coefficients tend to non-zero limit as
the network becomes large. Indeed, in many observed networks the values of
both clustering coefficients are considerably high [17].

The most well-known approach to modeling complex networks is the preferential-
attachment idea. Many different models are based on this idea: LCD [7],
Buckley-Osthus [10], Holme-Kim [14], RAN [24], and many others. A general
approach to preferential attachment was introduced in [18], where a wide class
of models was defined in terms of constraints that are sufficient for the
study of the degree distribution (PA-class) and the clustering coefficient
(T-subclass of PA-class).

In this paper, we analyze the behavior of $C(d)$ — the average local
clustering coefficient for the vertices of degree $d$ — in the T-subclass. It
was previously shown that in real-world networks $C(d)$ usually decreases as
$d^{-\psi}$ with some parameter $\psi>0$ [11, 20, 22]. For some networks,
$C(d)$ scales as a power law $C(d)\sim d^{-1}$ [15, 19]. In the current paper,
we prove that in all models of the T-subclass the local clustering coefficient
$C(d)$ asymptotically behaves as $C\cdot d^{-1}$, where $C$ is some constant.
We also illustrated these results empirically. In addition, we suggested and
empirically verified (for $A\leq 0.75$) an approximation for the average local
clustering coefficient $C_{2}(n)$.

The remainder of the paper is organized as follows. In Section 2, we give a
formal definition of the PA-class and present some known results. Then, in
Section 3, we state new results on the behavior of local clustering $C(d)$. We
prove the theorems in Section 4. In Section 5 we make some simulations in
order to illustrate our results for $C(d)$ and to empirically analyze the
local clustering coefficient. Section 6 concludes the paper.

##  2 Generalized Preferential Attachment

###  2.1 Definition of the PA-class

In this section, we define the PA-class of models which was first suggested in
[18]. Let $G_{m}^{n}$ ($n\geq n_{0}$) be a graph with $n$ vertices
$\\{1,\ldots,n\\}$ and $mn$ edges obtained as a result of the following
process. We start at the time $n_{0}$ from an arbitrary graph $G_{m}^{n_{0}}$
with $n_{0}$ vertices and $mn_{0}$ edges. On the $(n+1)$-th step ($n\geq
n_{0}$), we make the graph $G_{m}^{n+1}$ from $G_{m}^{n}$ by adding a new
vertex $n+1$ and $m$ edges connecting this vertex to some $m$ vertices from
the set $\\{1,\ldots,n,n+1\\}$. Denote by $d_{v}^{n}$ the degree of a vertex
$v$ in $G_{m}^{n}$. If for some constants $A$ and $B$ the following conditions
are satisfied

$\mathsf{P}\left(d_{v}^{n+1}=d_{v}^{n}\mid
G_{m}^{n}\right)=1-A\frac{d_{v}^{n}}{n}-B\frac{1}{n}+O\left(\frac{\left(d_{v}^{n}\right)^{2}}{n^{2}}\right),\,\,1\leq
v\leq n\;,$ (1) $\mathsf{P}\left(d_{v}^{n+1}=d_{v}^{n}+1\mid
G_{m}^{n}\right)=A\frac{d_{v}^{n}}{n}+B\frac{1}{n}+O\left(\frac{\left(d_{v}^{n}\right)^{2}}{n^{2}}\right),\,\,1\leq
v\leq n\;,$ (2) $\mathsf{P}\left(d_{v}^{n+1}=d_{v}^{n}+j\mid
G_{m}^{n}\right)=O\left(\frac{\left(d_{v}^{n}\right)^{2}}{n^{2}}\right),\,\,2\leq
j\leq m,\,\,1\leq v\leq n\;,$ (3)
$\mathsf{P}(d_{n+1}^{n+1}=m+j)=O\left(\frac{1}{n}\right),\,\,1\leq j\leq m\;,$
(4)

then the random graph process $G_{m}^{n}$ is a model from the PA-class. Here,
as in [18], we require $2mA+B=m$ and $0\leq A\leq 1$.

As it is explained in [18], even fixing values of parameters $A$ and $m$ does
not specify a concrete procedure for constructing a network. There are a lot
of models possessing very different properties and satisfying the conditions
(1–4), e.g., the LCD, the Buckley–Osthus, the Holme–Kim, and the RAN models.

###  2.2 Power Law Degree Distribution

Let $N_{n}(d)$ be the number of vertices of degree $d$ in $G_{m}^{n}$. The
following theorems on the expectation of $N_{n}(d)$ and its concentration were
proved in [18].

###### Theorem 2.1

For every model in PA-class and for every $d\geq m$

$\mathsf{E}N_{n}(d)=c(m,d)\left(n+O\left(d^{2+\frac{1}{A}}\right)\right)\,,\vspace{-5pt}$

where

$c(m,d)=\frac{\mathsf{\Gamma}\left(d+\frac{B}{A}\right)\mathsf{\Gamma}\left(m+\frac{B+1}{A}\right)}{A\,\mathsf{\Gamma}\left(d+\frac{B+A+1}{A}\right)\mathsf{\Gamma}\left(m+\frac{B}{A}\right)}\mathrel{\overset{d\rightarrow\infty}{\scalebox{1.5}[1.0]{$\sim$}}}\frac{\mathsf{\Gamma}\left(m+\frac{B+1}{A}\right)d^{-1-\frac{1}{A}}}{A\,\mathsf{\Gamma}\left(m+\frac{B}{A}\right)}\vspace{-5pt}$

and $\mathsf{\Gamma}(x)$ is the gamma function.

###### Theorem 2.2

For every model from the PA-class and for every $d=d(n)$ we have

$\mathsf{P}\left(|N_{n}(d)-\mathsf{E}N_{n}(d)|\geq
d\,\sqrt{n}\,\log{n}\right)={n^{-\Omega(\log{n})}}.$

Therefore, for any $\delta>0$ there exists a function $\varphi(n)\in o(1)$
such that

$\lim_{n\to\infty}\mathsf{P}\left(\exists\,d\leq
n^{\frac{A-\delta}{4A+2}}:|N_{n}(d)-\mathsf{E}N_{n}(d)|\geq\varphi(n)\,\mathsf{E}N_{n}(d)\right)=0\;.$

These two theorems mean that the degree distribution follows (asymptotically)
the power law with the parameter $1+\frac{1}{A}$.

###  2.3 Clustering Coefficient

A T-subclass of the PA-class was introduced in [18]. In this case, the
following additional condition is required:

$\mathsf{P}\left(d_{i}^{n+1}=d_{i}^{n}+1,d_{j}^{n+1}=d_{j}^{n}+1\mid
G_{m}^{n}\right)=e_{ij}\frac{D}{mn}+O\left(\frac{d_{i}^{n}d_{j}^{n}}{n^{2}}\right)\;.\vspace{-3pt}$
(5)

Here $e_{ij}$ is the number of edges between vertices $i$ and $j$ in
$G_{m}^{n}$ and $D$ is a positive constant. Note that this property still does
not define the correlation between edges completely, but it is sufficient for
studying both global and average local clustering coefficients.

Let us now define the clustering coefficients. The _global clustering
coefficient_ $C_{1}(G)$ is the ratio of three times the number of triangles to
the number of pairs of adjacent edges in $G$. The _average local clustering
coefficient_ is defined as follows: $C_{2}(G)=\frac{1}{n}\sum_{i=1}^{n}C(i)$,
where $C(i)$ is the local clustering coefficient for a vertex $i$:
$C(i)=\frac{T^{i}}{P_{2}^{i}}$, where $T^{i}$ is the number of edges between
neighbors of the vertex $i$ and $P_{2}^{i}$ is the number of pairs of
neighbors. Note that both clustering coefficients are defined for graphs
without multiple edges.

The following theorem on the global clustering coefficient in the T-subclass
was proven in [18].

###### Theorem 2.3

Let $G_{m}^{n}$ belong to the T-subclass with $D>0$. Then, for any
$\varepsilon>0$

  * (1)

If $2A<1$, then whp $\frac{6(1-2A)D-\varepsilon}{m(4(A+B)+m-1)}\leq
C_{1}(G_{m}^{n})\leq\frac{6(1-2A)D+\varepsilon}{m(4(A+B)+m-1)}\;;$

  * (2)

If $2A=1$, then whp $\frac{6D-\varepsilon}{m(4(A+B)+m-1)\log n}\leq
C_{1}(G_{m}^{n})\leq\frac{6D+\varepsilon}{m(4(A+B)+m-1)\log n}\;;$

  * (3)

If $2A>1$, then whp $n^{1-2A-\varepsilon}\leq C_{1}(G_{m}^{n})\leq
n^{1-2A+\varepsilon}\;.$

Theorem 2.3 shows that in some cases ($2A\geq 1$) the global clustering
coefficient $C_{1}(G_{m}^{n})$ tends to zero as the number of vertices grows.

The average local clustering coefficient $C_{2}(G_{m}^{n})$ was not fully
analyzed previously, but it was shown in [18] that $C_{2}(G_{m}^{n})$ does not
tend to zero for the T-subclass with $D>0$. In the next section, we fully
analyze the behavior of the average local clustering coefficient for the
vertices of degree $d$.

##  3 The Average Local Clustering for the Vertices of Degree $d$

In this section, we analyze the asymptotic behavior of $C(d)$ — the average
local clustering for the vertices of degree $d$. Let $T_{n}(d)$ be the number
of triangles on the vertices of degree $d$ in $G_{m}^{n}$ (i.e., the number of
edges between the neighbors of the vertices of degree $d$). Then, $C(d)$ is
defined in the following way:

$C(d)=\frac{T_{n}(d)}{N_{n}(d){d\choose 2}}\,.\vspace{-3pt}$ (6)

In other words, $C(d)$ is the local clustering coefficient averaged over all
vertices of degree $d$. In order to estimate $C(d)$ we should first estimate
$T_{n}(d)$. After that, we can use Theorems 2.1 and 2.2 on the behavior of
$N_{n}(d)$.

We prove the following result on the expectation of $T_{n}(d)$.

###### Theorem 3.1

Let $G_{m}^{n}$ belong to the T-subclass of the PA-class with $D>0$. Then

  * (1)

if $2A<1$, then
$\mathsf{E}T_{n}(d)=K(d)\left(n+O\left(d^{2+\frac{1}{A}}\right)\right)$;

  * (2)

if $2A=1$, then
$\mathsf{E}T_{n}(d)=K(d)\left(n+O\left(d^{2+\frac{1}{A}}\cdot\log(n)\right)\right)$;

  * (3)

if $2A>1$, then $\mathsf{E}T_{n}(d)=K(d)\left(n+O\left(d^{2+\frac{1}{A}}\cdot
n^{2A-1}\right)\right)$;

where
$K(d)=c(m,d)\left(D+\frac{D}{m}\cdot\sum_{i=m}^{d-1}\frac{i}{Ai+B}\right)\mathrel{\overset{d\rightarrow\infty}{\scalebox{1.5}[1.0]{$\sim$}}}\frac{D}{A\,m}\cdot\frac{\mathsf{\Gamma}\left(m+\frac{B+1}{A}\right)}{A\,\mathsf{\Gamma}\left(m+\frac{B}{A}\right)}\cdot
d^{-\frac{1}{A}}$.

Second, we show that the number of triangles on the vertices of degree $d$ is
highly concentrated around its expectation.

###### Theorem 3.2

Let $G_{m}^{n}$ belong to the T-subclass of the PA-class with $D>0$. Then for
every $d=d(n)$

  * (1)

if $2A<1$: $\mathsf{P}\left(|T_{n}(d)-\mathsf{E}T_{n}(d)|\geq
d^{2}\,\sqrt{n}\,\log{n}\right)={n^{-\Omega(\log{n})}}$;

  * (2)

if $2A=1$: $\mathsf{P}\left(|T_{n}(d)-\mathsf{E}T_{n}(d)|\geq
d^{2}\,\sqrt{n}\,\log^{2}{n}\right)={n^{-\Omega(\log{n})}}$;

  * (3)

if $2A>1$: $\mathsf{P}\left(|T_{n}(d)-\mathsf{E}T_{n}(d)|\geq
d^{2}\,n^{2A-\frac{1}{2}}\,\log{n}\right)={n^{-\Omega(\log{n})}}$.

Consequently, for any $\delta>0$ there exists a function $\varphi(n)=o(1)$
such that

  * (1)

if $2A\leq 1$: $\lim_{n\to\infty}\mathsf{P}\left(\exists\,d\leq
n^{\frac{A-\delta}{4A+2}}:|T_{n}(d)-\mathsf{E}T_{n}(d)|\geq\varphi(n)\,\mathsf{E}T_{n}(d)\right)=0$;

  * (2)

if $2A>1$:
$\lim_{n\to\infty}\mathsf{P}\left(\exists\,d\leq
n^{\frac{A(3-4A)-\delta}{4A+2}}:|T_{n}(d)-\mathsf{E}T_{n}(d)|\geq\varphi(n)\,\mathsf{E}T_{n}(d)\right)=0$.

As a consequence of Theorems 2.1, 2.2, 3.1, and 3.2, we get the following
result on the average local clustering coefficient $C(d)$ for the vertices of
degree $d$ in $G_{m}^{n}$.

###### Theorem 3.3

Let $G_{m}^{n}$ belong to the T-subclass of the PA-class. Then for any
$\delta>0$ there exists a function $\varphi(n)=o(1)$ such that

  * (1)

if $2A\leq 1$: $\lim_{n\to\infty}\mathsf{P}\left(\exists\,d\leq
n^{\frac{A-\delta}{4A+2}}:\left|C(d)-\frac{K(d)}{{d\choose
2}\,c(m,d)}\right|\geq\frac{\varphi(n)}{d}\right)=0$;

  * (2)

if $2A>1$: $\lim_{n\to\infty}\mathsf{P}\left(\exists\,d\leq
n^{\frac{A(3-4A)-\delta}{4A+2}}:\left|C(d)-\frac{K(d)}{{d\choose
2}\,c(m,d)}\right|\geq\frac{\varphi(n)}{d}\right)=0$.

Note that $\frac{K(d)}{{d\choose
2}\,c(m,d)}=\frac{2D}{d\,(d-1)\,m}\left(m+\sum_{i=m}^{d-1}\frac{i}{Ai+B}\right)\mathrel{\overset{d\rightarrow\infty}{\scalebox{1.5}[1.0]{$\sim$}}}\frac{2D}{mA}\cdot
d^{-1}$.

It is important to note that Theorems 3.2 and 3.3 are informative only for
$A<\frac{3}{4}$, since only in this case the value
$n^{\frac{A(3-4A)-\delta}{4A+2}}$ grows. This restriction seems technical,
i.e., one may think that more accurate estimation of error terms may fill the
gap between $\frac{3}{4}$ and 1. However, as we discuss in Section 5, it seems
that for $A>\frac{3}{4}$ the error terms can make a significant contribution
to $C(d)$ and the obtained asymptotic may not work. This means that it is
probably impossible to estimate $C(d)$ in the whole T-subclass for
$A>\frac{3}{4}$ and additional constraints are needed.

In the next section, we first prove Theorem 3.1. Then, using the
Azuma–Hoeffding inequality, we prove Theorem 3.2. Theorem 3.3 is a corollary
of Theorems 2.1, 2.2, 3.1, and 3.2.

##  4 Proofs

In all the proofs we use the notation $\theta(\cdot)$ for error terms. By
$\theta(X)$ we denote an arbitrary function such that $|\theta(X)|<X$.

###  4.1 Proof of Theorem 3.1

We need the following auxiliary theorem.

###### Theorem 4.1

Let $W_{n}$ be the sum of the squares of the degrees of all vertices in a
model from the PA-class. Then

  * (1)

if $2A<1$, then $\mathsf{E}W_{n}=O(n),$

  * (2)

if $2A=1$, then $\mathsf{E}W_{n}=O(n\cdot\log(n)),$

  * (3)

if $2A>1$, then $\mathsf{E}W_{n}=O(n^{2A})$.

This statement is mentioned in [18] and it can be proved by induction. Also,
let $S(n,d)$ be the sum of the degrees of all the neighbors of all vertices of
degree $d$. Note that $S(n,d)$ is not greater than the sum of the degrees of
the neighbors of all vertices. The last is equal to $W_{n}$, because each
vertex of degree $d$ adds $d^{2}$ to the sum of the degrees of the neighbors
of all vertices. So, for any $d$ we have

$\mathsf{E}S(n,d)\leq\mathsf{E}W_{n}.$ (7)

Now we can prove Theorem 3.1. Note that we do not take into account the
multiplicities of edges when we calculate the number of triangles, since the
clustering coefficient is defined for graphs without multiple edges. This does
not affect the final result since the number of multiple edges is small for
graphs constructed according to the model [6].

We prove the statement of Theorem 4 by induction on $d$. Also, for each $d$ we
use induction on $n$. First, consider the case $d=m$. The expected number of
triangles on any vertex $t$ of degree $m$ is equal to
$\mathsf{E}\sum_{(i,j)\in
E(G_{m}^{t})}{\left(e_{ij}\frac{D}{mt}+O\left(\frac{d_{i}^{t}d_{j}^{t}}{t^{2}}\right)\right)}$
(see (5)). As $G_{m}^{t}$ has exactly $mt$ edges, we get
$\mathsf{E}\sum_{(i,j)\in
E(G_{m}^{t})}{\left(e_{ij}\frac{D}{mt}+O\left(\frac{d_{i}^{t}d_{j}^{t}}{t^{2}}\right)\right)}\\\
=D+o(1)$. The fact that $\mathsf{E}\sum_{(i,j)\in
E(G_{m}^{t})}O\left(\frac{d_{i}d_{j}}{t^{2}}\right)=O\left(\frac{\mathsf{E}W_{t}}{t^{2}}\right)=o(1)$
can be shown by induction using the conditions (1-4). We also know (see
Theorem 2.1) that $\mathsf{E}N_{n}(m)=c(m,m)\,n+O\left(1\right)$. So,
$\mathsf{E}T_{n}(m)=\left(D+o(1)\right)\,\left(c(m,m)\,n+O\left(1\right)\right)\\\
=K(m)\left(n+O\left(1\right)\right)$. This concludes the proof for the case
$d=m$ for all values of $A$ ($2A<1$, $2A=1$ and $2A>1$).

Consider the case $d>m$. Note that the number of triangles on a vertex of
degree $d$ is $O\left(d\right)$, since this number is $O(1)$ when this vertex
appears plus at each step we get a triangle only if we hit both the vertex
under consideration and a neighbor of this vertex, and our vertex degree
equals $d$, therefore we get at most $d\,m$ triangles. Also,
$\mathsf{E}N_{n}(d)=c(m,d)\,\left(n+O\left(d^{2+\frac{1}{A}}\right)\right)$.
So we have
$\mathsf{E}T_{n}(d)=O(d)\,c(m,d)\,\left(n+O\left(d^{2+\frac{1}{A}}\right)\right)$.
In particular, for $n\leq Q\cdot d^{2}$ (where the constant $Q$ depends only
on $A$ and $m$ and will be defined later) we have
$\mathsf{E}T_{n}(d)=O\left(c(m,d)\,d^{3+\frac{1}{A}}\right)=O\left(d^{2}\right)=K(d)\cdot
O\left(d^{2+\frac{1}{A}}\right)$. This concludes the proof for the case $d>m$,
$n\leq Qd^{2}$ for all values of $A$.

Now, consider the case $d>m$, $n>Q\,d^{2}$. Once we add a vertex $n+1$ and $m$
edges, we have the following possibilities.

1\. At least one edge hits a vertex of degree $d$. Then $T_{n}(d)$ is
decreased by the number of triangles on this vertex (because this vertex is a
vertex of degree $d+1$ now). The probability to hit a vertex of degree $d$ is
$\frac{A\,d+B}{n}+O\left(\frac{d^{2}}{n^{2}}\right)$. Summing over all
vertices of degree $d$ we obtain that $\mathsf{E}T_{n}(d)$ is decreased by:

$\left(\frac{Ad+B}{n}+O\left(\frac{d^{2}}{n^{2}}\right)\right)\cdot\mathsf{E}T_{n}(d)\,.$
(8)

2\. Exactly one edge hits a vertex of degree $d-1$. Then $T_{n}(d)$ is
increased by the number of triangles on this vertex. The probability to hit a
vertex of degree $d-1$ once is equal to
$\frac{A\,(d-1)+B}{n}+O\left(\frac{d^{2}}{n^{2}}\right)$. Summing over all
vertices of degree $d-1$ we obtain that the value $\mathsf{E}T_{n}(d)$ is
increased by:

$\left(\frac{A(d-1)+B}{n}+O\left(\frac{d^{2}}{n^{2}}\right)\right)\cdot\mathsf{E}T_{n}(d-1)\,.$
(9)

3\. Exactly one edge hits a vertex of degree $d-1$ and another edge hits its
neighbor. Then, in addition to (9), $T_{n}(d)$ is increased by $1$. The
probability to hit a vertex of degree $d-1$ and its neighbor is equal to
$\frac{D}{mn}+O\left(\frac{(d-1)\,d_{i}}{n^{2}}\right)$, where $d_{i}$ is the
degree of this neighbor. Summing over the neighbors of a given vertex of
degree $d-1$ and summing then over all vertices of degree $d-1$ we obtain that
$\mathsf{E}T_{n}(d)$ is increased by:

$(d-1)\,\mathsf{E}N_{n}(d-1)\,\frac{D}{mn}+O\left(\frac{d\cdot\mathsf{E}\sum_{\begin{subarray}{c}i:i\text{
is a neighbor }\\\ \text{ of a vertex of degree
$d-1$}\end{subarray}}d_{i}}{n^{2}}\right)\\\
=(d-1)\,\mathsf{E}N_{n}(d-1)\,\frac{D}{mn}+O\left(\frac{d\,\mathsf{E}S(n,d)}{n^{2}}\right)\,.$
(10)

4\. Exactly $i$ edges hit a vertex of degree $d-i$, where $i$ is between $2$
and $m$. If no edges hit the neighbors of this vertex, then $T_{n}(d)$ is
increased only by the number of triangles on this vertex. The probability to
hit a vertex of degree $d-i$ exactly $i$ times is equal to
$O\left(\frac{d^{2}}{n^{2}}\right)$. If we also hit its neighbors, then
$T_{n}(d)$ is additionally increased by $1$ for each neighbor. The probability
to hit a vertex of degree $d-i$ exactly $i$ times and hit some its neighbor
is, obviously, $O\left(\frac{d^{2}}{n^{2}}\right)$. Summing over all vertices
of degree $d-i$ and then summing over all $i$ from $2$ to $m$, we obtain that
$\mathsf{E}T_{n}(d)$ is increased by:

$\sum_{i=2}^{m}{\left(\mathsf{E}T_{n}(d-i)\cdot
O\left(\frac{d^{2}}{n^{2}}\right)+O\left(\frac{d^{2}}{n^{2}}\right)\cdot(d-i)\cdot\mathsf{E}N_{n}(d-i)\right)}\\\
=O\left(\frac{d^{2}}{n^{2}}\right)\,\mathsf{E}T_{n}(d)+O\left(\frac{d^{3}}{n^{2}}\right)\,\mathsf{E}N_{n}(d)\,.$
(11)

Finally, using (8)-(11) and the linearity of the expectation, we get

$\mathsf{E}T_{n+1}(d)=\mathsf{E}T_{n}(d)-\left(\frac{Ad+B}{n}+O\left(\frac{d^{2}}{n^{2}}\right)\right)\,\mathsf{E}T_{n}(d)\\\
+\left(\frac{A(d-1)+B}{n}+O\left(\frac{d^{2}}{n^{2}}\right)\right)\,\mathsf{E}T_{n}(d-1)+(d-1)\,\mathsf{E}N_{n}(d-1)\,\frac{D}{mn}\\\
+O\left(\frac{d\,\mathsf{E}S(n,d)}{n^{2}}\right)+O\left(\frac{d^{2}}{n^{2}}\right)\,\mathsf{E}T_{n}(d)+O\left(\frac{d^{3}}{n^{2}}\right)\,\mathsf{E}N_{n}(d)\\\
=\left(1-\frac{Ad+B}{n}\right)\,\mathsf{E}T_{n}(d)+\frac{A(d-1)+B}{n}\,\mathsf{E}T_{n}(d-1)\\\
+O\left(\frac{d^{2}}{n^{2}}\right)\,\left(\mathsf{E}T_{n}(d)+\mathsf{E}T_{n}(d-1)\right)+O\left(\frac{d^{3}}{n^{2}}\right)\,\mathsf{E}N_{n}(d)\\\
+\frac{D}{mn}\,(d-1)\,\mathsf{E}N_{n}(d-1)+O\left(\frac{d\cdot\mathsf{E}S(n,d)}{n^{2}}\right)\,.$
(12)

Consider the case $2A<1$ (the cases $2A=1$ and $2A>1$ will be analyzed
similarly). We prove by induction on $d$ and $n$ that

$\mathsf{E}T_{n}(d)=K(d)\,\left(n+\theta\left(C\cdot
d^{2+\frac{1}{A}}\right)\right)$ (13)

for some constant $C>0$. Let us assume that
$\mathsf{E}T_{i}(\tilde{d})=K(\tilde{d})\,\left(i+\theta\left(C\cdot\tilde{d}^{2+\frac{1}{A}}\right)\right)$
for $\tilde{d}<d$ and all $i$ and for $\tilde{d}=d$ and $i<n+1$.

Recall that
$K(d)=c(m,d)\left(D+\frac{D}{m}\cdot\sum_{i=m}^{d-1}\frac{i}{Ai+B}\right)$ and
$\mathsf{E}N_{n}(d)=c(m,d)\cdot\left(n+O\left(d^{2+\frac{1}{A}}\right)\right)$.
If $2A<1$, then from (7) and Theorem 7 we get $\mathsf{E}S(n,d)=O(n)$ and we
obtain:

$\mathsf{E}T_{n+1}(d)=\left(1-\frac{Ad+B}{n}\right)\,K(d)\,\left(n+\theta\left(Cd^{2+\frac{1}{A}}\right)\right)\\\
+\frac{A(d-1)+B}{n}\,K(d-1)\,\left(n+\theta\left(C(d-1)^{2+\frac{1}{A}}\right)\right)\\\
+O\left(\frac{d^{2}}{n^{2}}\right)\,\left(K(d)\,\left(n+\theta\left(Cd^{2+\frac{1}{A}}\right)\right)+K(d-1)\,\left(n+\theta\left(C(d-1)^{2+\frac{1}{A}}\right)\right)\right)\\\
+O\left(\frac{d^{3}}{n^{2}}\right)\,c(m,d)\,\left(n+O\left(d^{2+\frac{1}{A}}\right)\right)\\\
+\frac{D}{mn}\,(d-1)\,c(m,d-1)\,\left(n+O\left(d^{2+\frac{1}{A}}\right)\right)+O\left(\frac{d}{n}\right)\,.$

Note that
$K(d)=\frac{A(d-1)+B}{Ad+B+1}\,K(d-1)+\frac{D(d-1)}{m\left(Ad+B+1\right)}\,c(m,d-1)$.
Therefore, we obtain:

$\mathsf{E}T_{n+1}(d)=K(d)\,(n+1)+K(d)\,\left(1-\frac{Ad+B}{n}\right)\,\theta\left(C\,d^{2+\frac{1}{A}}\right)\\\
+K(d-1)\,\frac{A(d-1)+B}{n}\,\theta\left(C\,(d-1)^{2+\frac{1}{A}}\right)\\\
+\frac{D(d-1)}{mn}\,c(m,d)\,O\left(d^{2+\frac{1}{A}}\right)+O\left(\frac{d}{n}\right)+O\left(\frac{d^{2}}{n^{2}}\right)\,\left(K(d)\,n\right.\\\
\left.+K(d)\,\theta\left(C\,d^{2+\frac{1}{A}}\right)+K(d-1)\,n+K(d-1)\,\theta\left(C\,(d-1)^{2+\frac{1}{A}}\right)\right)\\\
+O\left(\frac{d^{3}}{n^{2}}\right)\,\left(c(m,d)\,n+c(m,d)\,O\left(d^{2+\frac{1}{A}}\right)\right)\,.$

In order to show (13), it remains to prove that for some large enough $C$:

$K(d)\,\left(\frac{Ad+B}{n}\right)\,C\,d^{2+\frac{1}{A}}\geq
K(d-1)\,\frac{A(d-1)+B}{n}\,C\,(d-1)^{2+\frac{1}{A}}\\\
+O\left(\frac{d^{2}}{n}\right)+O\left(C\,\frac{d^{4}}{n^{2}}\right)+O\left(\frac{d^{4}}{n^{2}}\right)\,.$
(14)

First, we analyze the following difference:

$K(d)\,\left(\frac{Ad+B}{n}\right)\,d^{2+\frac{1}{A}}-K(d-1)\,\frac{A(d-1)+B}{n}\,(d-1)^{2+\frac{1}{A}}\\\
=\frac{Ad+B}{n}\,d^{2+\frac{1}{A}}\,\left(\frac{A(d-1)+B}{Ad+B+1}\,K(d-1)+\frac{D(d-1)}{m(Ad+B+1)}\,c(m,d-1)\right)\\\
-\frac{A(d-1)+B}{n}\,K(d-1)\,(d-1)^{2+\frac{1}{A}}=\frac{(Ad+B)D(d-1)}{mn(Ad+B+1)}\,c(m,d-1)\,d^{2+\frac{1}{A}}\\\
+K(d-1)\,\frac{A(d-1)+B}{n}\,\left(\frac{Ad+B}{Ad+B+1}d^{2+\frac{1}{A}}-(d-1)^{2+\frac{1}{A}}\right)\\\
\geq\frac{(Ad+B)D(d-1)}{mn(Ad+B+1)}\,c(m,d-1)\,d^{2+\frac{1}{A}}\\\
+(d-1)^{2+\frac{1}{A}}\,K(d-1)\,\frac{A(d-1)+B}{n}\cdot\frac{2A^{2}d+2AB+B}{Ad(Ad+B+1)}\\\
\geq\frac{(Ad+B)D(d-1)}{mn(Ad+B+1)}\,c(m,d-1)\,d^{2+\frac{1}{A}}\,.$

Therefore, Equation (14) becomes:

$C\,\frac{(Ad+B)D(d-1)}{mn(Ad+B+1)}\,c(m,d-1)\,d^{2+\frac{1}{A}}\geq
O\left(\frac{d^{2}}{n}\right)+O\left(C\,\frac{d^{4}}{n^{2}}\right)+O\left(\frac{d^{4}}{n^{2}}\right)\,.$

In the case $2A=1$ this inequality will be:

$C\,\frac{(Ad+B)D(d-1)}{mn(Ad+B+1)}\,c(m,d-1)\,d^{2+\frac{1}{A}}\,\log(n)\\\
\geq
O\left(\frac{d^{2}}{n}\right)+O\left(C\,\frac{d^{4}\cdot\log(n)}{n^{2}}\right)+O\left(\frac{d^{4}}{n^{2}}\right)+O\left(\frac{d\,\log(n)}{n}\right).$

In the case $2A>1$ this inequality will be:

$C\,\frac{(Ad+B)D(d-1)}{mn(Ad+B+1)}\,c(m,d-1)\,d^{2+\frac{1}{A}}\,n^{2A-1}\\\
\geq
O\left(\frac{d^{2}}{n}\right)+O\left(C\,\frac{d^{4}\,n^{2A-1}}{n^{2}}\right)+O\left(\frac{d^{4}}{n^{2}}\right)+O\left(\frac{d\,n^{2A}}{n^{2}}\right).$

It is easy to see that for $n\geq Q\cdot d^{2}$ (for some large $Q$ which
depends only on the parameters of the model) these three inequalities are
satisfied. This concludes the proof of the theorem.

###  4.2 Proof of Theorem 3.2

This theorem is proved similarly to the concentration theorem from [18]. We
also need the following notation (introduced in [18]):

$\displaystyle p_{n}(d)=\mathsf{P}\left(d_{v}^{n+1}=d\mid
d_{v}^{n}=d\right)=1-A\frac{d}{n}-B\frac{1}{n}+O\left(\frac{d^{2}}{n^{2}}\right)\,,$
$\displaystyle p_{n}^{1}(d):=\mathsf{P}\left(d_{v}^{n+1}=d+1\mid
d_{v}^{n}=d\right)=A\frac{d}{n}+B\frac{1}{n}+O\left(\frac{d^{2}}{n^{2}}\right)\,,$
$\displaystyle p_{n}^{j}(d):=\mathsf{P}\left(d_{v}^{n+1}=d+j\mid
d_{v}^{n}=d\right)=O\left(\frac{d^{2}}{n^{2}}\right),\,\,2\leq j\leq m\,,$
$\displaystyle
p_{n}:=\sum_{k=1}^{m}\mathsf{P}(d_{n+1}^{n+1}=m+k)=O\left(\frac{1}{n}\right)\;.$

To prove Theorem 3.2 we also need the Azuma–Hoeffding inequality:

######  Theorem 4.2 (Azuma, Hoeffding)

Let $(X_{i})_{i=0}^{n}$ be a martingale such that $|X_{i}-X_{i-1}|\leq c_{i}$
for any $1\leq i\leq n$. Then $\mathsf{P}\left(|X_{n}-X_{0}|\geq x\right)\leq
2e^{-\frac{x^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}}$ for any $x>0$.

Consider the random variables $X_{i}(d)=\mathsf{E}(T_{n}(d)\mid G_{m}^{i})$,
$i=0,\ldots,n$. Note that $X_{0}(d)=\mathsf{E}T_{n}(d)$ and
$X_{n}(d)=T_{n}(d)$. It is easy to see that $X_{n}(d)$ is a martingale.

We will prove below that for any $i=0,\ldots,n-1$

  * (1)

if $2A<1$, then $|X_{i+1}(d)-X_{i}(d)|\leq Md^{2},$

  * (2)

if $2A=1$, then $|X_{i+1}(d)-X_{i}(d)|\leq Md^{2}\log(n),$

  * (2)

if $1<2A<\frac{3}{2}$, then $|X_{i+1}(d)-X_{i}(d)|\leq Md^{2}n^{2A-1}$,

where $M>0$ is some constant. The theorem follows from this statement
immediately. Indeed, consider the case $2A<1$. Put $c_{i}=Md^{2}$ for all $i$.
Then from Azuma–Hoeffding inequality it follows that

$\mathsf{P}\left(|T_{n}(d)-\mathsf{E}T_{n}(d)|\geq
d^{2}\,\sqrt{n}\,\log{n}\right)\leq
2\exp\left\\{-\frac{n\,d^{4}\,\log^{2}{n}}{2\,n\,M^{2}d^{4}}\right\\}={n^{-\Omega(\log{n})}}\,.\vspace{-0.2cm}$

Therefore, for the case $2A<1$ the first statement of the theorem is
satisfied. If $d\leq n^{\frac{A-\delta}{4A+2}}$, then the value $n\,d^{-1/A}$
is considerably greater than $d^{2}\,\log{n}\,\sqrt{n}$. From this the second
statement of the theorem follows. The cases $2A=1$ and $2A>1$ can be
considered similarly. It remains to estimate $|X_{i+1}(d)-X_{i}(d)|$.

Fix $0\leq i\leq n-1$ and some graph $G_{m}^{i}$. Note that

$\left|\mathsf{E}\left(T_{n}(d)\mid
G_{m}^{i+1}\right)-\mathsf{E}\left(T_{n}(d)\mid G_{m}^{i}\right)\right|\leq\\\
\leq\max_{\tilde{G}_{m}^{i+1}\supset
G_{m}^{i}}\left\\{\mathsf{E}\left(T_{n}(d)\mid\tilde{G}_{m}^{i+1}\right)\right\\}-\min_{\tilde{G}_{m}^{i+1}\supset
G_{m}^{i}}\left\\{\mathsf{E}\left(T_{n}(d)\mid\tilde{G}_{m}^{i+1}\right)\right\\}.\vspace{-0.1cm}$

Put $\hat{G}_{m}^{i+1}=\arg\max\mathsf{E}(T_{n}(d)\mid\tilde{G}_{m}^{i+1})$,
$\bar{G}_{m}^{i+1}=\arg\min\mathsf{E}(T_{n}(d)\mid\tilde{G}_{m}^{i+1})$. It is
sufficient to estimate the difference
$\mathsf{E}(T_{n}(d)\mid\hat{G}_{m}^{i+1})-\mathsf{E}(T_{n}(d)\mid\bar{G}_{m}^{i+1})$.

For $i+1\leq t\leq n$ put

$\delta_{t}^{i}(d)=\mathsf{E}(T_{t}(d)\mid\hat{G}_{m}^{i+1})-\mathsf{E}(T_{t}(d)\mid\bar{G}_{m}^{i+1}).\vspace{-0.2cm}$

First, let us note that for $n\leq W\cdot d^{2}$ (the value of constant $W$
will be defined later) we have
$\delta_{n}^{i}(d)\leq\frac{2mn}{d}\cdot\left(\frac{m(m-1)}{2}+d\,m\right)\leq
4m^{2}n\leq Md^{2}\leq Md^{2}\log(n)\leq Md^{2}n^{2A-1}$ (since we have at
most $\frac{2mn}{d}$ vertices of degree $d$, and each vertex of degree $d$ has
at most $\frac{m(m-1)}{2}$ triangles when this vertex appears plus at each
step we get a triangle only if we hit both the vertex under consideration and
a neighbor of this vertex, and our vertex degree is equal to $d$, therefore we
get at most $d\,m$ triangles) for some constant $M$ which depends only on $W$
and $m$.

It remains to estimate $\delta_{n}^{i}(d)$ for $n>Wd^{2}$. Consider the case
$2A<1$. We want to prove that $\delta^{i}_{n}(d)\leq Md^{2}$ for $n>Wd^{2}$ by
induction. Suppose that $n=i+1$. Fix $G_{m}^{i}$. Graphs $\hat{G}_{m}^{i+1}$
and $\bar{G}_{m}^{i+1}$ are obtained from the graph $G_{m}^{i}$ by adding the
vertex $i+1$ and $m$ edges. These $m$ edges can affect the number of triangles
on at most $m$ previous vertices. For example, they can be drown to at most
$m$ vertices of degree $d$ and decrease $T_{i}(d)$ by at most
$\frac{m\,d\,(d-1)}{2}$. Such reasonings finally lead to the estimate
$\delta^{i}_{i+1}(d)\leq Md^{2}$ for some $M$.

Now let us use the induction. Consider $t$: $i+1\leq t\leq n-1$, $t>W\,d^{2}$
(note that the smaller values of $t$ were already considered). Using similar
reasonings as in the proof of Theorem 3.1 we get:

$\delta^{i}_{t+1}(m)=\delta^{i}_{t}(m)\left(1-p_{t}(m)\right)+O\left(\frac{1}{t}\right),\vspace{-0.3cm}$
$\delta^{i}_{t+1}(d)=\delta^{i}_{t}(d)\left(1-p_{t}(d)\right)+\delta^{i}_{t}(d-1)\,p_{t}^{1}(d-1)\\\
+(d-1)\cdot\left(\mathsf{E}(N_{t}(d-1)\mid\hat{G}_{m}^{i})-\mathsf{E}(N_{t}(d-1)\mid\bar{G}_{m}^{i})\right)\cdot\frac{D}{mt}\\\
+O\left(\frac{d\cdot\mathsf{E}S(t,d-1)}{t^{2}}\right)+O\left(\frac{\mathsf{E}T_{t}(d)\cdot
d^{2}}{t^{2}}\right)+O\left(\frac{\mathsf{E}N_{t}(d)\cdot
d^{3}}{t^{2}}\right)\,.\vspace{-0.2cm}$

Note that
$\mathsf{E}(N_{t}(d)\mid\hat{G}_{m}^{i+1})-\mathsf{E}(N_{t}(d)\mid\bar{G}_{m}^{i+1})=O\left(d\right)$
(see [18]) and $\mathsf{E}S(t,d-1)=O\left(t\right)$. From this recurrent
relations it is easy to obtain by induction that $\delta^{i}_{n}(d)\leq
Md^{2}$ for some $M$. Indeed,

$\delta^{i}_{t+1}(m)\leq Mm^{2}\left(1-p_{t}(m)\right)+\frac{C_{1}}{t}\leq
Mm^{2}\left(1-\frac{Am+B}{t}+\frac{C_{2}}{t^{2}}\right)+\frac{C_{1}}{t}\leq
Mm^{2}$

for sufficiently large $M$. By $C_{i}$, $i=1,2,\ldots$, we denote some
positive constants. For $d>m$ we get

$\delta^{i}_{t+1}(d)\leq
Md^{2}(1-p_{t}(d))+M(d-1)^{2}p_{t}^{1}(d-1)+C_{3}\frac{d^{2}}{t}+C_{4}\frac{d^{4}}{t^{2}}\\\
\leq
Md^{2}\left(1-\frac{Ad+B}{t}+C_{5}\frac{d^{2}}{t^{2}}\right)+M(d-1)^{2}\left(\frac{A(d-1)+B}{t}+C_{6}\frac{d^{2}}{t^{2}}\right)+C_{3}\frac{d^{2}}{t}\\\
+C_{4}\frac{d^{4}}{t^{2}}\leq
Md^{2}+\frac{M}{t}\left(A(-3d^{2}+3d-1)+B(-2d+1)+C_{7}\frac{d^{4}}{t}+C_{3}\frac{d^{2}}{M}\right.\\\
\left.+C_{4}\frac{d^{4}}{Mt}\right)\leq
Md^{2}+\frac{M}{t}\left(\left(-3A+C_{7}\frac{d^{2}}{t}+\frac{C_{3}}{M}+C_{4}\frac{d^{2}}{Mt}\right)\cdot
d^{2}\right.\\\ +\left.\left(3A-2B\right)\cdot d+(B-A)\right)\leq Md^{2}\;.$

for sufficiently large $W$ and $M$.

In the case $2A=1$ we have $\mathsf{E}S(t,d-1)=O\left(t\log(t)\right)$ and we
get the following inequalities:

$\delta^{i}_{t+1}(m)\leq
Mm^{2}\log(t)\left(1-p_{t}(m)\right)+\frac{C_{1}\log(t)}{t}\leq
Mm^{2}\log(t+1),$ $\delta^{i}_{t+1}(d)\leq
Md^{2}\log(t)(1-p_{t}(d))+M(d-1)^{2}\log(t)\,p_{t}^{1}(d-1)\\\
+C_{2}\frac{d^{2}}{t}+C_{3}\frac{d\log(t)}{t}+C_{4}\frac{d^{4}\log(t)}{t^{2}}\leq
Md^{2}\log(t+1)\;.$

In the case $2A>1$ we have $\mathsf{E}S(t,d-1)=O\left(t^{2A}\right)$ and we
get the following inequalities:

$\delta^{i}_{t+1}(m)\leq
Mm^{2}t^{2A-1}\left(1-p_{t}(m)\right)+\frac{C_{1}t^{2A-1}}{t}\leq
Mm^{2}(t+1)^{2A-1},$ $\delta^{i}_{t+1}(d)\leq
Md^{2}t^{2A-1}(1-p_{t}(d))+M(d-1)^{2}\,t^{2A-1}p_{t}^{1}(d-1)\\\
+C_{2}\frac{d^{2}}{t}+C_{3}\frac{d\cdot
t^{2A-1}}{t}+C_{4}\frac{d^{4}t^{2A-1}}{t^{2}}\leq Md^{2}(t+1)^{2A-1}\;.$

This concludes the proof of Theorem 3.2.

##  5 Experiments

In this section, we choose a three-parameter model from the family of
polynomial graph models defined in [18] and analyze the local clustering
coefficients $C(d)$ and $C_{2}(n)$. First, we illustrate our results on $C(d)$
which we proved in the previous section. In addition, we consider the case
$A>\frac{3}{4}$, for which we do not have a theoretical proof. In this case,
our approximation of $C(d)$ slightly deviates from the experiment. Finally, we
discuss how the average local clustering coefficient $C_{2}(n)$ can be
approximated.

###  5.1 Local Clustering Coefficient $C(d)$

(a) $A=0.25$

(b) $A=0.5$

(c) $A=0.7$

(d) $A=0.8$

Figure 1: The behavior of $C(d)$

First, we generated three polynomial graphs with $n=10^{6}$, $m=2$, $D=0.3$
and different values of $A$. In other words, we fixed the probability of a
triangle formation and vary the parameter of the power-law degree
distribution. Detailed graph generation process is described in [18]. We
choose $A$ to be 0.25, 0.5 and 0.7, which corresponds to the three cases of
Theorems 3.1 and 3.2. Also these cases correspond to three different types of
a power-law degree distribution: with a finite variance, with infinite
variance and the border case with $\gamma=3$. Figure 1 illustrates our main
result (Theorem 3.3). Here the theoretical value of $C(d)$ is equal to
$\frac{K(d)}{{d\choose
2}\,c(m,d)}=\frac{2D}{d\,(d-1)\,m}\left(m+\sum_{i=m}^{d-1}\frac{i}{Ai+B}\right)$
according to Theorem 3.3. We have also considered the case $A=0.8$ for which
we do not have a theoretical proof. In this case, the experimental result is
also close to the theoretical approximation. However, one can observe that our
approximation slightly underestimates $C(d)$ even for small values of $d$
(see, e.g., $d=2$ on Figure 1(d)). This means that for $A>\frac{3}{4}$ the
error terms can make a significant contribution to the value of $C(d)$ and it
is probably impossible to get the accurate approximation for the whole
T-subclass for such $A$. So, our restriction $A<\frac{3}{4}$ is essential. In
all four cases, the difference for large $d$ can be explained by the error
term.

###  5.2 Average Local Clustering Coefficient

In this section we empirically analyze the average local clustering
coefficient for the PA-class of models. Recall that the average local
clustering coefficient is defined as:
$C_{2}(n)=\frac{1}{n}\sum_{i=1}^{n}{C(i)}$, where $C(i)$ is the local
clustering coefficient for a vertex $i$: $C(i)=\frac{T^{i}}{P_{2}^{i}}$,
$T^{i}$ is the number of triangles on the vertex $i$ and $P_{2}^{i}$ is the
number of pairs of neighbors. Also $C_{2}(n)$ can be represented in the
following form:
$C_{2}(n)=\frac{1}{n}\cdot\sum_{d=m}^{\infty}{\frac{T_{n}(d)}{\frac{d(d-1)}{2}}}$.

Using Theorem 3.1 we can approximate the expectation of $C_{2}(n)$:

$\mathsf{E}C_{2}(n)=\frac{1}{n}\cdot\sum_{d=m}^{\infty}{\frac{\mathsf{E}T_{n}(d)}{\frac{d(d-1)}{2}}}=\\\
=\sum_{d=m}^{\infty}{\frac{2D}{d(d-1)}\left[1+\frac{1}{m}\sum_{i=m}^{d-1}{\frac{i}{Ai+B}}\right]\cdot}\\\
\cdot{\frac{\mathsf{\Gamma}\left(m+\frac{B+1}{A}\right)\mathsf{\Gamma}\left(d+\frac{B}{A}\right)}{A\mathsf{\Gamma}\left(m+\frac{B}{A}\right)\mathsf{\Gamma}\left(d+\frac{(B+A+1)}{A}\right)}\cdot\left[1+O\left(\frac{X}{n}\right)\right]}=\sum_{d=m}^{\infty}{f(d)\cdot\left[1+O\left(\frac{X}{n}\right)\right]},$
(15)

where:

$f(d)=\frac{2D}{d(d-1)}\left[1+\frac{1}{m}\sum_{i=m}^{d-1}{\frac{i}{Ai+B}}\right]\cdot\frac{\mathsf{\Gamma}\left(m+\frac{B+1}{A}\right)\mathsf{\Gamma}\left(d+\frac{B}{A}\right)}{A\mathsf{\Gamma}\left(m+\frac{B}{A}\right)\mathsf{\Gamma}\left(d+\frac{(B+A+1)}{A}\right)}$

and

  * (1)

if $2A<1$, then $X=d^{2+\frac{1}{A}}$,

  * (2)

if $2A=1$, then $X=d^{2+\frac{1}{A}}\cdot\log(n)$,

  * (2)

if $2A>1$, then $X=d^{2+\frac{1}{A}}\cdot\log(n^{2A})$.

It is hard to compute $\sum_{d=m}^{\infty}{f(d)}$ analytically. Moreover, it
is impossible to prove that the error term $\sum_{d=m}^{\infty}{f(d)\cdot
O\left(\frac{X}{n}\right)}$ behaves as $o(1)$, since this series does not
converge. Therefore, in this section we empirically analyze how well
$\sum_{d=m}^{\infty}{f(d)}$ approximates the clustering coefficient
$C_{2}(n)$. Further in this section we consider the behavior of $C_{2}(n)$
depending on $A$ and on $D$.

Average Local Clustering Coefficient $C_{2}(n)$ depending on $A$. We generated
polynomial graphs with $n=10^{6}$, $m=2$, and $D=0.3$, assigning
$A\in[0.15,0.8]$. For each value of $A$ we generate 10 graphs and average the
obtained values of $C_{2}(n)$ (see Figure 2). For $A\leq 0.75$ the theoretical
value $\sum_{d=m}^{\infty}{f(d)}$ is extremely close to the experiment and
only for $A=0.8$ we observe a small error. This is consistent with Figure 1,
where we demonstrated that our approximation of $C(d)$ does not work for
$A>\frac{3}{4}$.

Figure 2: The behavior of $C_{2}(n)$ as a function of $A$ for $n=10^{6}$,
$m=2$, $D=0.3$

Average Local Clustering Coefficient $C_{2}(n)$ depending on $D$. We also
generated polynomial graphs with $n=10^{6}$, $m=2$, and $A=0.5$, assigning
$D\in[0.05,1]$. Again, we average $C_{2}(n)$ over 10 graphs (see Figure 3).
For all $D$ the theoretical value $\sum_{d=m}^{\infty}{f(d)}$ is extremely
close to the experiment. Also, it follows from Equation (15) that $C_{2}(d)$
should depend linearly on $D$ and our experiment confirmed it.

Figure 3: The behavior of $C_{2}(n)$ as a function of $D$ for $n=10^{6}$,
$m=2$, $A=0.5$

Thus, our experiments suggest that for polynomial models we can approximate
the local clustering coefficient $C_{2}(n)$ by $\sum_{d=m}^{\infty}{f(d)}$ for
$A\leq\frac{3}{4}$.

##  6 Conclusion

In this paper, we study the local clustering coefficient $C(d)$ for the
vertices of degree $d$ in the T-subclass of the PA-class of models. Despite
the fact that the T-subclass generalizes many different models, we are able to
analyze the local clustering coefficient for all these models. Namely, we
proved that $C(d)$ asymptotically decreases as $\frac{2D}{Am}\cdot d^{-1}$. In
particular, this result implies that one cannot change the exponent $-1$ by
varying the parameters $A,D$, and $m$. This basically means that preferential
attachment models in general are not flexible enough to model $C(d)\sim
d^{-\psi}$ with $\psi\neq 1$. In addition, we suggested and empirically
verified (for $A\leq 0.75$) an approximation for the local clustering
coefficient $C_{2}(n)$.

We would also like to mention the connection between the obtained behavior of
$C(d)$ and the notion of weak and strong transitivity introduced in [20]. It
was shown in [21] that percolation properties of a network are defined by the
type (weak or strong) of its connectivity. Interestingly, a model from the
T-subclass can belong to either weak or strong transitivity class: if $2D<Am$,
then we obtain the weak transitivity; if $2D>Am$, then we obtain the strong
transitivity.

## References

  * [1] R. Albert, A.-L. Barabási, Statistical mechanics of complex networks, Reviews of modern physics, vol. 74, pp. 47–97 (2002)
  * [2] S. Bansal, S. Khandelwal, L.A. Meyers, Exploring biological network structure with clustered random networks, BMC Bioinformatics, 10:405 (2009)
  * [3] A.-L. Barabási, R. Albert, Emergence of scaling in random networks, Science 286, pp. 509-512 (1999)
  * [4] A.-L. Barabási, R. Albert, H. Jeong, Mean-field theory for scale-free random networks, Physica A 272, pp. 173-187 (1999)
  * [5] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang, Complex networks: Structure and dynamics, Physics reports, vol. 424(45), pp. 175-308 (2006)
  * [6] B. Bollobás, O.M. Riordan, Mathematical results on scale-free random graphs, Handbook of Graphs and Networks: From the Genome to the Internet, pp.1-34 (2003)
  * [7] B. Bollobás, O.M. Riordan, J. Spencer, G. Tusnády, The degree sequence of a scale-free random graph process, Random Structures and Algorithms, vol. 18(3), pp. 279-290 (2001)
  * [8] C. Borgs, M. Brautbar, J. Chayes, S. Khanna, B. Lucier, The power of local information in social networks, preprint (2012)
  * [9] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener, Graph structure in the web, Computer Networks, vol. 33(16), pp. 309-320 (2000)
  * [10] P.G. Buckley, D. Osthus, Popularity based random graph models leading to a scale-free degree sequence, Discrete Mathematics, vol. 282, pp. 53-63 (2004)
  * [11] M. Catanzaro, G. Caldarelli, and L. Pietronero, Phys. Rev. E 70, 037101 (2004)
  * [12] M. Faloutsos, P. Faloutsos, Ch. Faloutsos, On power-law relationships of the Internet topology, Proc. SIGCOMM’99 (1999)
  * [13] M. Girvan and M. E. Newman, Community structure in social and biological networks, Proceedings of the National Academy of Sciences, 99(12):7821-7826 (2002)
  * [14] P. Holme, B.J. Kim, Growing scale-free networks with tunable clustering, Phys. Rev. E, vol. 65(2), 026107 (2002)
  * [15] J. Leskovec, Dynamics of Large Networks, ProQuest, 2008.
  * [16] M.E.J. Newman, Power laws, Pareto distributions and Zipf’s law, Contemporary Physics, 46, N5, 323-351 (2005)
  * [17] M.E.J. Newman, The structure and function of complex networks, SIAM review, 45(2):167-256 (2003)
  * [18] L. Ostroumova, A. Ryabchenko, E. Samosvat, Generalized Preferential Attachment: Tunable Power-Law Degree Distribution and Clustering Coefficient, Proc. WAW’13, Lecture Notes in Computer Science, vol. 8305, pp. 185–202 (2013)
  * [19] E. Ravasz and A.-L. Barabási. Hierarchical organization in complex networks. Physical Review E, 67(2) (2003)
  * [20] M. A. Serrano and M. Boguñá, Clustering in complex networks. I. General formalism, Phys. Rev. E 74, 056114 (2006)
  * [21] M. A. Serrano and M. Boguñá, Clustering in complex networks. II. Percolation properties, Phys. Rev. E 74, 056115 (2006)
  * [22] A. Vázquez, R. Pastor-Satorras, and A. Vespignani, Large-scale topological and dynamical properties of the Internet, Phys. Rev. E 65, 066130 (2002)
  * [23] D. J. Watts and S. H. Strogatz, Collective dynamics of ’small-world’ networks, Nature 393, pp. 440–442 (1998)
  * [24] T. Zhou, G. Yan and B.-H. Wang, Maximal planar networks with large clustering coefficient and power-law degree distribution, Phys. Rev. E, vol. 71(4) (2005)


# Bias Mitigation Framework for Intersectional Subgroups in Neural Networks

Narine Kokhlikyan
Meta AI
<EMAIL_ADDRESS>
&Bilal Alsallakh
Meta AI
<EMAIL_ADDRESS>
&Fulton Wang
Meta AI
<EMAIL_ADDRESS>
Vivek Miglani
Meta AI
<EMAIL_ADDRESS>
&Oliver Aobo Yang
Meta AI
<EMAIL_ADDRESS>
&David Adkins
Meta AI
<EMAIL_ADDRESS>

###### Abstract

We propose a fairness-aware learning framework that mitigates intersectional
subgroup bias associated with protected attributes. Prior research has
primarily focused on mitigating one kind of bias by incorporating complex
fairness-driven constraints into optimization objectives or designing
additional layers that focus on specific protected attributes. We introduce a
simple and generic bias mitigation approach that prevents models from learning
relationships between protected attributes and output variable by reducing
mutual information between them. We demonstrate that our approach is effective
in reducing bias with little or no drop in accuracy. We also show that the
models trained with our learning framework become causally fair and
insensitive to the values of protected attributes. Finally, we validate our
approach by studying feature interactions between protected and non-protected
attributes. We demonstrate that these interactions are significantly reduced
when applying our bias mitigation.

##  1 Introduction

The unprecedented adoption of Machine Learning (ML) in critical sectors such
as finance, healthcare and education has made fairness-related bias detection
and mitigation a crucial part of ML systems. It is important that ML models do
not discriminate against individuals based on protected attributes such as
race, gender or skin color when making predictions. Fairness research has
typically focused on detecting and mitigating bias for a single protected
attribute. With such detection and mitigation, the fairness gap for
_intersectional subgroups_ such as Female and Black might still be high. This
phenomenon is called Fairness Gerrymandering (Ghosh et al., 2021; Kearns et
al., 2018; Buolamwini and Gebru, 2018). Several works (Kearns et al., 2018;
Yang et al., 2020; Kang et al., 2021; Morina et al., 2019) proposed techniques
to address fairness gerrymandering, which require predetermining fairness
violation metrics. Nevertheless, a recent survey (Du et al., 2021) highlights
the scarcity of research in detecting and mitigating intersectional bias. One
of the key challenges of this research is the limited access to protected
attributes and their _unknown correlations_ with other attributes in the
dataset. These limitations are common due to privacy or data restrictions.
Another key challenge of fairness research is reducing the bias across groups
and _intersectional subgroups_ without a significant drop in accuracy.

In this paper we propose a generic and simple fairness-aware learning
framework that addresses the intersectional subgroup bias problem without
requiring specific fairness metrics to be predetermined. It learns latent
representations without relying on protected attributes and their interactions
with other attributes in the dataset. Previous work (Cho et al., 2020; Song et
al., 2018) shows that reducing the mutual information between a protected
attribute and output variable plays a significant role in reducing the bias
associated with that protected attribute. We propose a generic framework that
reduces the mutual information not only between a single protected attribute
and the output variable, but also between any subset of protected attributes
and the output variable. Experimentally, we show that this approach debiases
the model significantly with little or no drop in accuracy. Furthermore, we
also show that the models trained with our framework become insensitive to the
values of protected attributes. This shows that our models are causally fair
according to the definitions of causal fairness by (Kusner et al., 2017a).

#### Motivating example:

Table 1 illustrates accuracy and TPR gap between two subpopulations,
$\texttt{Male}\cap\texttt{White}$ and $\texttt{Female}\cap\texttt{Black}$ for
the Law School Admissions Council (LSAC) dataset (Wightman and Council, 1998).
TPR is an important metric in this specific example since it measures the
advantaged outcome. We compare our fairness-aware framework with three other
baseline models: 1) the original model without mitigation, 2) a baseline model
which is trained without Gender and Race attributes and 3) a baseline model
which is trained after upsampling minority subgroups. We observe a significant
TPR gap between two populations in the original model. Two of the baseline
models reduce the fairness gap. However, they are less effective compared to
our approach. Our approach learns latent representations that do not rely on
protected attributes and their relationship to output variable, and thus
reduces the fairness gap significantly.

Table 1: Accuracy and True Positive Rate (TPR) for two subpopulations, computed for the original model, our model trained using fairness-aware framework and two baseline models.  | Accuracy | TPR
---|---|---
| $\texttt{Male}\cap\texttt{White}$ | $\texttt{Female}\cap\texttt{Black}$
Original model | 0.87 | 0.96 | 0.77
Removed protected attributes | 0.86 | 0.96 | 0.83
Upsampled minority groups | 0.86 | 0.88 | 0.82
Our fairness-aware framework | 0.86 | 0.94 | 0.90

The main contributions of this paper are as follows:

  * •

We introduce a novel bias mitigation framework that aims to reduce the mutual
information between intersectional subgroups and the output variable.

  * •

We show empirically that our approach reduces the equality and demographic
parity gaps significantly and surpasses state-of-the-art approaches.

  * •

We study the sensitivity of the debiased model to the presence of protected
attributes and the effectiveness of our approach when non-protected attributes
are correlated with the protected ones.

  * •

We demonstrate that feature interactions between protected and non-protected
attributes reduce significantly when the models are trained using our bias
mitigation framework.

##  2 Related Work

Fairness literature offers numerous definitions of fairness (Narayanan, 2018),
its measurement and mitigation. We base our fairness definition and
measurement on the work of (Hardt et al., 2016) and three well-known metrics:
Demographic Parity (Feldman et al., 2015; Dwork et al., 2012; Kusner et al.,
2017b), Equalized Odds and Equality of Opportunity (Hardt et al., 2016).
Demographic Parity compares the average prediction score across different
subgroups. Equality of Opportunity, in addition to that, takes the label
distribution into account and measures the TPR gap among different groups.
Equalized Odds (Hardt et al., 2016) measures both the TPR and False Positive
Rate (FPR) gaps among different groups. Specific metrics have been developed
for intersectional subgroups such as the min-max ratio (Ghosh et al., 2021)
and differential fairness metric (Foulds et al., 2020). In this paper we focus
on measuring the commonly used Demographic Parity and Equalized Odds for
intersectional subgroups, which facilitate comparisons with previous work.

Bias mitigation techniques reduce the disparities among the groups and
intersectional subgroups measured by the aforementioned metrics. Three types
of mitigation techniques have been proposed to combat fairness bias (Du et
al., 2021):

Postprocessing techniques aim to reduce fairness bias during model inference.
Those approaches enforce model predictions to follow the same distribution
observed during training (Zhao et al., 2017), transforming model predictions
to follow a specific fairness measure. These techniques, however, require
access to protected attributes during inference, which is not always available
due to data scarcity or privacy reasons.

Dataset preprocessing techniques such as balancing the distribution of data
labels, downsampling and sample re-weighing (Kamiran and Calders, 2011)
alleviate modelling bias to a certain extent. However, Wang et al. (2019)
shows that data preprocessing and balancing datasets often have limited
effect, compared with training inherently unbiased models. Apart from data
balancing, one can also delete protected attributes from the training set or
mask them. However, this is not sufficient, since protected attributes are
often correlated with other attributes in the data.

Train-time techniques aim to combat fairness bias during model training. This
can be accomplished using constraints based on adversarial loss (Beutel et
al., 2017; Zhang et al., 2018; Wang et al., 2019), feature importance (Liu and
Avci, 2019; Du et al., 2019; Ross et al., 2017), fairness measurement (Agarwal
et al., 2018), decision boundary (Zafar et al., 2019) or statistical
dependence (Kamishima et al., 2012). Adversarial loss requires defining
additional heads or constraints for a specific protected attribute. It
maximizes the primary objective of a specific task while minimizing the
model’s ability to predict specific protected attributes. Constraints based on
feature importance, on the other hand, heavily rely on the feature
contribution score (Liu and Avci, 2019; Du et al., 2019), which is not always
reliable (Hooker et al., 2019). Yang et al. (2020) propose Bayes-optimal
classification framework for intersectional group fairness which is also tied
to fairness metric constraints. Kang et al. (2021) propose a framework based
on mutual information minimization for intersectional subgroups. This
framework, however, requires two estimators and two additional predictors
which makes the mitigation process complex.

In contrast, we propose a simple and generic training-time fairness-aware
framework that doesn’t rely on specific fairness metrics, or architectural
modifications such as adversarial heads. It accounts for intersectional
fairness of any subsets of input features and is straightforward to implement.

##  3 Preliminaries

In this section we formalize the problem, introduce preliminary notations and
concepts that are used later in the paper. The goal is to learn a fair Neural
Network (NN) model that mitigates the fairness gap for intersectional
subgroups formed by multiple protected attributes. We seek to reach this goal
with minimal impact on accuracy. During inference, no information about the
protected attributes is necessary.

###  3.1 Notation

We consider a typical ML model, $f:R^{M}\rightarrow R^{C}$, that is trained on
a dataset $D=\\{(x_{1},y_{1}),...,(x_{N},y_{N})\\}$, where each sample $x_{i}$
consists of a set of $M$ features
$x_{i}=\\{x_{i}^{1},x_{i}^{2}...,x_{i}^{M}\\}$ where $x_{i}^{j}\in R$
represents the $j^{\texttt{th}}$ feature in the $i^{\texttt{th}}$ sample.
$y_{i}\in[1,...,C]$ is the label corresponding to sample $x_{i}$. Let
$x^{\prime j}\in R$ denote a shared baseline across all samples for input
feature $j$. It indicates the absence of signal or feature value in the input.
Traditionally, the zero value is used to indicate the absence of signal but
for certain features zero value might represent a meaning. For example, $0$
and $1$ might indicate male and female for the gender feature in some
datasets.

#### Protected Attribute Notation.

Let $A_{k}\subseteq\\{1,2,...,M\\}$ be a subset of features that are known to
be protected. For example, $A_{k}$ may correspond to $\\{race\\}$ or
$\\{gender,race\\}$. Let also $\mathcal{A}$ denote a set of subsets of
$A_{k}$. For example, $\mathcal{A}$ may correspond to
$\mathcal{A}=\\{\\{gender\\},\\{race\\},\\{gender,race\\}\\}$.

Finally, let also $\mathcal{S}(x_{i},x^{\prime},A_{k})$ denote a substitution
function that replaces the features that aren’t in $A_{k}$ with values from
baseline $x^{\prime}$.

$\mathcal{S}(x_{i},x^{\prime},A_{k})=\left\\{\begin{array}[]{rcl}x_{i}^{j},&j\in
A_{k}\\\ x^{\prime j},&\text{otherwise}\\\ \end{array}\right.\forall j\in[M]$
(1)

We denote by $x^{A_{k}}$ the subset of features in $x$ corresponding to
protected features $A_{k}$. Analogously, $x^{\setminus A_{k}}$ denotes a
subset of features that excludes protected attributes $A_{k}$.

###  3.2 Information Theory

We briefly revisit information theory in order to analyse the relationship
between a subset of protected attributes $A_{k}$ and dependant output variable
$y$. This analysis explains the reasoning behind our bias mitigation approach.
The entropy $H(X)$ measures the average uncertainty (Cover and Thomas, 2006)
of a random variable $X$. Mutual Information (MI) uses the entropy to measure
the shared information between two random variables. In our case, the mutual
information between an input feature $x^{j}$ and the output variable $y$ can
be measured as $MI(x^{j};y)=H(x^{j})-H(x^{j}|y)$. During bias mitigation, we
aim to reduce the $MI$ between the protected attributes $x^{A_{k}}$ and $y$.
Reducing $MI(x^{A_{k}};y)$ implies increasing the uncertainty
$H(x^{A_{k}}|y)$. We increase that uncertainty by associating protected
attributes with a uniformly distributed random output variable $Unif(1,C)$. We
propose a proxy metric that associates $x^{A_{k}}$ with random labels
independent of the values in $x^{\setminus A_{k}}$. The new examples generated
by $\mathcal{S}(x_{i},x^{\prime},A_{k})$ reduce overall mutual information
between $x^{A_{k}}$ and the protected attributes in the dataset. The proxy
measure aims to reduce the distance between
$\mathcal{S}(x_{i},x^{\prime},A_{k})$ and $Unif(1,C)$ which can be represented
as a regularization term in the optimization objective. Table 2 shows how the
mutual information between protected attributes Gender and Race reduces as we
augment the data with samples that associate intersectional subgroups of
protected attributes with random guesses. In the next section we describe how
we incorporate this regularization term into the model’s optimization
objective.

Table 2: MI between protected attributes Gender and Race and output variable Passed Bar before and after MI constraint-based data augmentation for the LSAC and Adult datasets. | Passed Bar (Before Mitigation) | Passed Bar (After Mitigation)
---|---|---
| LSAC | Adult | LSAC | Adult
Gender | 0.00101 | 0.043532 | 0.00029 | 0.011177
Race | 0.02265 | 0.010469 | 0.004876 | 0.0010130

##  4 Fairness-Aware Learning Algorithm

The learning algorithm we propose is similar in spirit to the ones which
incorporate predetermined constraints into optimization objective as
regularization terms. It is more generic in its nature and does not use EO, DP
or adversarial heads as a proxy for the minimization of the mutual information
(Cho et al., 2020; Song et al., 2018) between the protected attributes and the
output variable. We give a formal definition of the objective function
starting from the definition of the proxy constraint for mutual information.

######  Definition 4.1.

Given a subset of protected attributes $A_{k}\in\mathcal{A}$, an input example
$x_{i}$, a uniformly random chosen label $y_{rand}$ and a baseline
$x^{\prime}$, the proxy constraint for the mutual information is defined as
follow:

$L^{\mathcal{A}}(x_{i},x^{\prime},\mathcal{A},y_{rand})=-\sum_{A_{k}\in\mathcal{A}}\sum_{c\in
C}\mathbbm{1}(y_{rand}=c)\cdot\log(f_{c}(\mathcal{S}(x_{i},x^{\prime},A_{k})))$
(2)

where $c\in C$ are possible prediction classes and $y_{rand}=Unif(1,C)$ is a
label drawn uniformly random from $C$ and $f_{c}$ is the NN’s output for class
$c$. The first summation over the subsets of protected attributes $A_{k}$
helps us to address bias mitigation for multiple subsets of protected
attributes. The joint objective of a multiclass classification problem is the
following.

$L_{combined}=\sum_{(x_{i},y_{i})\in
D}L(x_{i},y_{i})+\alpha\cdot\sum_{(x_{i},x^{\prime})\in
D^{\prime}}L^{A}(x_{i},x^{\prime},\mathcal{A},Unif(1,C))$ (3)

In our setup we use a classification loss but other loss definitions can be
used instead. $L(x_{i},y_{i})$ represents the loss for the original model. The
hyperparameter $\alpha$ is used to balance the amount of regularization that
we incorporate into the loss.
$D^{\prime}=\\{(x_{1},x^{\prime}),...,(x_{N},x^{\prime})\\}$ represents the
dataset with a set of baseline values $x^{\prime}=\\{x^{\prime
j}\\}_{j=1}^{j=M}$ for each feature $j$. $Unif(1,C)$ chooses a label uniformly
at random from $[1,...,C]$. Sturmfels et al. (2020); Barenstein (2019a)
discuss different strategies for baseline selection. In a general case we can
also choose different baselines for a feature and aggregate their impact on
the overall loss. Algorithm 1 illustrates an example of how our proposed loss
can be computed during training using Gradient Descent (GD) algorithm. Our
method is not limited to GD and can be trained with other optimization
algorithms as well. The proxy constraint plays a role of weighted data
augmentation that helps the model to learn associations between protected
attributes and randomly guessed labels.

Input: Training Datasets $D=\\{(x_{i},y_{i})\\}_{i=1}^{i=N}$, Validation
dataset $D^{\text{valid}}=\\{(x_{i},y_{i})\\}_{i=1}^{i=F}$, Baseline
$x^{\prime}=\\{x^{\prime j}\\}_{j=1}^{j=M}$, A set of subsets of protected
attributes $\mathcal{A}$, hyperparameter $\alpha$, learning rate $\eta$,
$max\\_epochs$.

Output: $W_{\text{best}}$ for the best accuracy of the model $f$ on
$D^{\text{valid}}$

1 Initialize the model parameters $W_{0}$, set epoch=0;

2

3while  _$epoch <max\\_epochs$_ do

4 $L_{\text{initial}}$ =
$\frac{1}{N}\cdot\sum_{i=1}^{i=N}\sum_{c=1}^{C}\mathbbm{-1}(y_{i}=c)\cdot
log(f_{c}(x_{i}))$;

$y_{\text{rand}}=uniform\\_rand(C)$ ;

// Uniformly at random chooses class in $[1,C]$ for each example

5 $L^{\mathcal{A}}$ =
$\frac{1}{N}\sum_{i=1}^{i=N}\sum_{k=1}^{|\mathcal{A}|}\sum_{c=1}^{C}\mathbbm{-1}(y_{i}=c)\cdot
log(f_{c}(\mathcal{S}(x_{i},x^{\prime},A_{k})))$ ;

6 $L_{\text{combined}}=L_{\text{initial}}+\alpha\cdot L^{\mathcal{A}}$

7 $\text{epoch}=\text{epoch}+1$ ;

$W_{\text{epoch}}=Optimizer(L_{\text{combined}},\eta)$;

// Optimizer can be Adam, for example

8 Update $W_{\text{best}}$ based on the highest accuracy measures on
$D^{\text{valid}}$ so far.

Algorithm 1 Fairness-Aware Learning Algorithm

##  5 Experiments

In this section we present experimental results of our fairness-aware learning
framework and a number of state-of-the-art approaches. We also describe
experimental setup and discuss empirical results.

###  5.1 Experimental Setup

The UCI Adult dataset (Dua and Graff, 2017) and the Law School Admissions
Council (LSAC) dataset (Wightman and Council, 1998) are two highly unbalanced
datasets used in our experiments. Appendix A.1 provides additional details
about those datasets. For these two datasets we built a 2-layer RELU-
BatchNorm-Linear NN models similar to the one demonstrated in the literature
(Beutel et al., 2017). The first linear layer contains 128, the second 64 and
the last output layer only a single neuron. The models are trained using
approximately 100 epochs with Adam optimizer, $0.001$ learning rate and binary
cross entropy logit loss as the baseline model’s loss, $L(x_{i},y_{i})$. As
bias mitigation constraint, $L^{\mathcal{A}}$, we used squared distance
between model’s output and provided label instead of cross entropy loss since
it is commonly used for these dataset. Cross entropy defined in equation 3 is
more generic and provides similar results to squared distance. We chose
baseline values $x^{\prime}$ carefully, $-1$ and $-2$ to indicate missingness
of the attributes in the dataset. We compared our method with the well known
GerryFair (Kearns et al., 2018) and a mutual information reduction-based
approach (Cho et al., 2020) adopted for intersectional fairness. GerryFair
performs a zero-sum optimization between a fairness auditor and a classifier
subject to the auditor’s constraints. On the other hand, (Cho et al., 2020;
Song et al., 2018; Louppe et al., 2017) show that mutual information
reduction-based approaches can be formulated as generative adversarial
optimization problems. Here the classifier plays the role of the generator and
the discriminator aims to reduce the mutual information between the protected
attributes and the output of the classifier. Inspired by (Song et al., 2018;
Louppe et al., 2017) we implemented an adversarial network with two 2-layer
RELU-BatchNorm-Linear NNs. One of those networks serves as a generator and the
other one as a discriminator.

###  5.2 Evaluation metrics

As fairness measurement metrics we adopted Equalized Odds (EO) (Hardt et al.,
2016; Beutel et al., 2017) and Demographic Parity (DP) (Dwork et al., 2012;
Kusner et al., 2017b) metrics to measure model’s intersectional subgroup
biases. Inspired by (Beutel et al., 2017) and (Ghosh et al., 2021) we measure
EO as the differences between minimum and maximum TPR and FPR scores across
all subgroups formed by a given subset of protected attributes. Let $G$ denote
the set of different combinatorial options formed by the subgroups of
protected attributes in the set $A_{k}\in\mathcal{A}$. For example
$G=\\{(Male,White),(Male,Black),(Male,Asian),(Female,White),(Female,Black),\\\
(Female,Asian),...\\}$. The values in $G$ are then denoted by $G_{i}\in G$. EO
based on TPR and FPR are then defined as
$EO_{G}^{TPR}=|max(TPR(G_{i}))-min(TPR(G_{j}))|$ and
$EO_{G}^{FPR}=|max(FPR(G_{i}))-min(FPR(G_{j}))|,G_{i}\in G,G_{j}\in G$
accordingly. Similarly, demographic parity is measured as
$DP_{G}=|max(DP(G_{i}))-min(DP(G_{j}))|,G_{i}\in G,G_{j}\in G$.

###  5.3 Experimental Results

In order to better understand the accuracy vs fairness gap relationship, we
run multiple experiments by varying the weight of the fairness component from
zero to a large number both for our approach and two baseline approaches. We
compare our approach against GerryFair (Kearns et al., 2018) and a mutual
information-based approach (Cho et al., 2020) in terms of Accuracy vs TPR, FPR
and DP gaps. As described in section 5.1 mutual information based fairness
mitigation is performed based on adversarial training. Our experimental
results depicted on figure 1 reveal that our method results in higher accuracy
when reducing TPR gap from 0.5 to 0.2 for LSAC and from 0.46 to 0.23 for Adult
datasets. All three methods exhibit similar accuracy when the TPR gap is
further reduced from approximately 0.2 to 0.0. We examine similar patterns for
Accuracy vs FPR and DP gap measurements as well. We observe that the
adversarially trained approach slightly underperforms two other approaches in
terms of accuracy. We hypothesize that generator-discriminator based
approaches are more effective for binary protected attributes as also shown in
(Louppe et al., 2017). When dealing with multiple non-binary protected
attributes, generator-discriminator based networks become less effective and
might require further fine tuning. We conclude that our method can be
beneficial especially when the goal is to reduce fairness gaps substantially
without hurting the accuracy too much. Appendix A.2 provides additional
results for the COMPAS (Barenstein, 2019b) dataset.

Figure 1: Our method, GerryFair and adversarially trained approaches compared
on accuracy vs fairness metrics (TPR, FPR and DP gaps) for LSAC (top) and
Adult (bottom) datasets. Best viewed in color.

Furthermore, we compare our method with the original and two additional
baseline models. One of the baselines represents a model trained without
protected attributes. In this case we removed Gender and Race attributes from
the dataset. The second baseline model is trained on a dataset where examples
for all underrepresented intersectional subgroups of Gender and Race are
upsampled. Figure 2 summarizes Accuracy, TPR, FPR and DP gaps across all
baselines and our approach for LSAC and Adult datasets. We observe that our
method is comparable or better in reducing the fairness gap for almost the
same accuracy trade-off.

Figure 2: Our method ($\alpha=0.5$) vs original model, removed Gender and Race
attributes and upsampled for underrepresented subgroups. Best viewed in color.

In order to validate the effectiveness of our approach we perform two
additional studies. We aim to understand how inference time masking of
protected attributes and the presence of attributes strongly correlated with
protected attributes, change the accuracy, TPR, FPR and DP gaps.

#### Masking protected attributes:

We mask protected attributes in the test dataset and compare model accuracy
and fairness metrics before and after masking. This validates the hypothesis
that fairness gap changes will remain changed before and after protected
attributes are masked in the test dataset, if our method is effective in
mitigating bias and is causally fair (Kusner et al., 2017a). Table 3 showcases
the high sensitivity of the original model’s accuracy, TPR, FPR and DP gaps
when protected attributes are masked. In contrast to the original model, our
model is almost insensitive to the masking of protected attributes showing its
robustness to the presence of protected attributes. This also shows that
privacy-preserving inference is possible since protected attributes are not
required to be present at inference time. Appendix A.2 demonstrates the
results of the same experiment for Adult dataset.

Table 3: Test Accuracy, TPR, FPR and DP Passed Bar gaps for the Original and Our Models ($\alpha=0.5$) with and without masking of protected attributes applied on LSAC dataset.  | Accuracy | TPR | FPR | DP passed
---|---|---|---|---
Original model | 0.87 | 0.55 | 0.14 | 0.23
Original model w/masked $A^{(Gender,Race)}$ | 0.85 | 0.53 | 0.05 | 0.15
Our model | 0.86 | 0.28 | 0.06 | 0.11
Our model w/masked $A^{(Gender,Race)}$ | 0.86 | 0.28 | 0.06 | 0.10
Table 4: Accuracy and TPR computed for the original model, a baseline model trained without Gender and Race, and our approach. The dataset contains an additional attribute Race1 for which mitigation is intentionally not performed.  | Accuracy | TPR
---|---|---
| $\texttt{Male}\cap\texttt{White}$ | $\texttt{Female}\cap\texttt{Black}$
Original model | 0.87 | 0.99 | 0.76
Removed protected attributes | 0.86 | 0.96 | 0.77
Our model ($\alpha=0.5$) | 0.86 | 0.96 | 0.90

#### Studying the effects of strongly correlated features with protected
attributes:

In order to understand the effectiveness of our approach in the presence of
features strongly correlated with protected attributes we use two race related
features Race1 and Race. Race1 is a coarse-grained representation of the Race
attribute. We apply bias mitigation only to fields Gender and Race. No
mitigation for field Race1 is carried out. Table 4 shows that our approach is
still effective in mitigating the bias in underrepresented groups such as
$\texttt{Female}\cap\texttt{Black}$. It is not as effective as in the absence
of Race1 field 1, however, it is more effective than removing Gender and Race
from the dataset.

#### Feature interaction effects:

In addition to accuracy, TPR, FPR and DP gaps, we also analyse pairwise
feature interaction effects of protected attributes based on Tsang et al.
(2020). We validate the hypothesis that pairwise feature interaction of
protected attributes with non-protected ones drops significantly for the
unbiased model. Furthermore, our experiments reveal that the decline of
feature interaction scores for protected attributes leads to the emergence of
stronger interaction patterns between other attributes. Figure 3 visualizes
aggregated pairwise feature interaction heatmaps for the original, biased
model, at the top and unbiased model, based on our approach, at the bottom of
the diagram. The results suggest that feature interaction effects for Male and
Female look very similar. We also observe that the protected attribute gender
has a relatively strong interaction pattern with the age attribute and race
with the fulltime in the biased model. The unbiased model, however, exhibits
no distinct and strong feature interaction patterns for gender and race with
age and fulltime respectively. On the other hand, we discern stronger emerging
interaction patterns between parttime and zgpa, fulltime and zgpa. This helps
us better understand how feature interaction patterns are impacted when the
models are trained with bias mitigation constraints. These findings can serve
as sanity checks and facilitate better understanding of bias mitigation
techniques.

Figure 3: Aggregated pairwise feature interaction heatmaps before (top) and
after (bottom) bias mitigation for both Male and Female based on LSAC test
dataset. Best viewed in color.

##  6 Conclusion and Future Work

In this paper, we propose a framework to mitigate modeling bias in
intersectional subgroups independent of the type of the protected attributes.
The framework incorporates a generic proxy constraint into the optimization
objective which reduces the mutual information between protected attributes
and the output variable. We study accuracy vs TPR, FPR and DP gap trade-offs
both with respect to state of the art approaches as well as data pre-
processing techniques such as upsampling and removing protected attributes. We
show empirically, that our approach surpasses GerryFair and adversarially
trained approaches when reducing the fairness gaps. Furthermore, we show,
empirically, that our approach is still effective when other features are
correlated with protected attributes and protected attributes are not
available during inference time. Lastly, our experiments reveal that bias
removal reduces the interaction effects between protected attributes and other
attributes in the dataset.

In the future, we plan to analyse the effects of different types of bias
mitigation constraints on a specific ML task of interest. This type of
research can help better understand what kind of constraints might work better
for a specific problem space and why. In addition to that it is also valuable
to investigate techniques for estimating the optimal hyperparameter value for
the weight of bias mitigation term, instead of a grid search approach.

## References

  * (1)
  * Agarwal et al. (2018) Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. 2018\.  A Reductions Approach to Fair Classification. In _International Conference on Machine Learning (ICML)_.  arXiv:1803.02453
  * Barenstein (2019a) Matias Barenstein. 2019a.  ProPublica’s COMPAS Data Revisited.  https://doi.org/10.48550/ARXIV.1906.04711
  * Barenstein (2019b) Matias Barenstein. 2019b.  ProPublica’s COMPAS Data Revisited.  https://doi.org/10.48550/ARXIV.1906.04711
  * Beutel et al. (2017) Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi. 2017\.  Data decisions and theoretical implications when adversarially learning fair representations.  _arXiv preprint arXiv:1707.00075_ (2017).
  * Buolamwini and Gebru (2018) Joy Buolamwini and Timnit Gebru. 2018.  Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification. In _Proceedings of the 1st Conference on Fairness, Accountability and Transparency_ _(Proceedings of Machine Learning Research, Vol. 81)_ , Sorelle A. Friedler and Christo Wilson (Eds.). PMLR, 77–91.  https://proceedings.mlr.press/v81/buolamwini18a.html
  * Cho et al. (2020) Jaewoong Cho, Gyeongjo Hwang, and Changho Suh. 2020\.  A Fair Classifier Using Mutual Information. In _2020 IEEE International Symposium on Information Theory (ISIT)_. 2521–2526.  https://doi.org/10.1109/ISIT44484.2020.9174293
  * Cover and Thomas (2006) Thomas M. Cover and Joy A. Thomas. 2006.  _Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)_.  Wiley-Interscience, USA.
  * Du et al. (2019) Mengnan Du, Ninghao Liu, Fan Yang, and Xia Hu. 2019\.  Learning Credible Deep Neural Networks with Rationale Regularization.  _IEEE International Conference on Data Mining (ICDM)_ (2019), 150–159.
  * Du et al. (2021) Mengnan Du, Fan Yang, Na Zou, and Xia Hu. 2021\.  Fairness in Deep Learning: A Computational Perspective.  _IEEE Intelligent Systems_ 36, 4 (2021), 25–34.  https://doi.org/10.1109/MIS.2020.3000681
  * Dua and Graff (2017) Dheeru Dua and Casey Graff. 2017.  UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml
  * Dwork et al. (2012) Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012.  Fairness through Awareness. In _Innovations in Theoretical Computer Science Conference_ (Cambridge, Massachusetts) _(ITCS ’12)_. Association for Computing Machinery, New York, NY, USA, 214–226.  https://doi.org/10.1145/2090236.2090255
  * Feldman et al. (2015) Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. 2015.  Certifying and Removing Disparate Impact. In _ACM SIGKDD international conference on knowledge discovery and data mining_. Association for Computing Machinery, 259–268.  https://doi.org/10.1145/2783258.2783311
  * Foulds et al. (2020) James R. Foulds, Rashidul Islam, Kamrun Naher Keya, and Shimei Pan. 2020.  An Intersectional Definition of Fairness. In _2020 IEEE 36th International Conference on Data Engineering (ICDE)_. 1918–1921.  https://doi.org/10.1109/ICDE48307.2020.00203
  * Ghosh et al. (2021) Avijit Ghosh, Lea Genuit, and Mary Reagan. 2021.  Characterizing Intersectional Group Fairness with Worst-Case Comparisons.  arXiv:2101.01673 [cs.LG]
  * Hardt et al. (2016) Moritz Hardt, Eric Price, and Nathan Srebro. 2016.  Equality of Opportunity in Supervised Learning. In _Advances in Neural Information Processing Systems (NeurIPS)_.
  * Hooker et al. (2019) Sara Hooker, D. Erhan, Pieter-Jan Kindermans, and Been Kim. 2019\.  A Benchmark for Interpretability Methods in Deep Neural Networks. In _Advances in Neural Information Processing Systems (NeurIPS)_.
  * Kamiran and Calders (2011) Faisal Kamiran and Toon Calders. 2011.  Data preprocessing techniques for classification without discrimination.  _Knowledge and Information Systems_ 33 (2011), 1–33.
  * Kamishima et al. (2012) Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. 2012.  Fairness-Aware Classifier with Prejudice Remover Regularizer. In _Machine Learning and Knowledge Discovery in Databases_ , Peter A. Flach, Tijl De Bie, and Nello Cristianini (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 35–50.
  * Kang et al. (2021) Jian Kang, Tiankai Xie, Xintao Wu, Ross Maciejewski, and Hanghang Tong. 2021.  MultiFair: Multi-Group Fairness in Machine Learning.  _ArXiv_ abs/2105.11069 (2021).
  * Kearns et al. (2018) Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. 2018.  Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness. In _International Conference on Machine Learning (ICML)_ _(Proceedings of Machine Learning Research, Vol. 80)_ , Jennifer Dy and Andreas Krause (Eds.). PMLR, 2564–2572.  https://proceedings.mlr.press/v80/kearns18a.html
  * Kusner et al. (2017a) Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. 2017a.  Counterfactual Fairness. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2017/file/a486cd07e4ac3d270571622f4f316ec5-Paper.pdf
  * Kusner et al. (2017b) Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. 2017b.  Counterfactual Fairness. In _Advances in Neural Information Processing Systems (NeurIPS)_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2017/file/a486cd07e4ac3d270571622f4f316ec5-Paper.pdf
  * Liu and Avci (2019) Frederick Liu and Besim Avci. 2019.  Incorporating Priors with Feature Attribution on Text Classification. In _Annual Meeting of the Association for Computational Linguistics_.
  * Louppe et al. (2017) Gilles Louppe, Michael Kagan, and Kyle Cranmer. 2017\.  Learning to Pivot with Adversarial Networks. In _NIPS_.
  * Morina et al. (2019) Giulio Morina, Viktor Mykhailovych Oliinyk, Julian Waton, Ines Marusic, and Konstantinos Georgatzis. 2019.  Auditing and Achieving Intersectional Fairness in Classification Problems.  _ArXiv_ abs/1911.01468 (2019).
  * Narayanan (2018) Arvind Narayanan. 2018\.  Translation tutorial: 21 fairness definitions and their politics.
  * Ross et al. (2017) Andrew Slavin Ross, Michael C. Hughes, and Finale Doshi-Velez. 2017.  Right for the Right Reasons: Training Differentiable Models by Constraining their Explanations. In _International Joint Conference on Artificial Intelligence (IJCAI)_. 2662–2670.  https://doi.org/10.24963/ijcai.2017/371
  * Song et al. (2018) Jiaming Song, , Aditya Grover, Shengjia Zhao, and Stefano Ermon. 2018.  Learning Controllable Fair Representations.  _arXiv preprint arXiv:1812.04218_ (2018).
  * Sturmfels et al. (2020) Pascal Sturmfels, Scott Lundberg, and Su-In Lee. 2020\.  Visualizing the Impact of Feature Attribution Baselines.  _Distill_ (2020).  https://doi.org/10.23915/distill.00022 https://distill.pub/2020/attribution-baselines.
  * Tsang et al. (2020) Michael Tsang, Sirisha Rambhatla, and Yan Liu. 2020\.  How does This Interaction Affect Me? Interpretable Attribution for Feature Interactions. In _Advances in Neural Information Processing Systems (NeurIPS)_.  https://proceedings.neurips.cc/paper/2020/hash/443dec3062d0286986e21dc0631734c9-Abstract.html
  * Wang et al. (2019) T. Wang, J. Zhao, M. Yatskar, K. Chang, and V. Ordonez. 2019.  Balanced Datasets Are Not Enough: Estimating and Mitigating Gender Bias in Deep Image Representations. In _2019 IEEE/CVF International Conference on Computer Vision (ICCV)_. IEEE Computer Society, Los Alamitos, CA, USA, 5309–5318.  https://doi.org/10.1109/ICCV.2019.00541
  * Wightman and Council (1998) L.F. Wightman and Law School Admission Council. 1998.  _LSAC National Longitudinal Bar Passage Study_.  Law School Admission Council.  https://books.google.com/books?id=O9A7AQAAIAAJ
  * Yang et al. (2020) Forest Yang, Moustapha Cisse, and Sanmi Koyejo. 2020\.  Fairness with overlapping groups.  _Advances in Neural Information Processing Systems_ 2020-December (2020).  Publisher Copyright: © 2020 Neural information processing systems foundation. All rights reserved.; 34th Conference on Neural Information Processing Systems, NeurIPS 2020 ; Conference date: 06-12-2020 Through 12-12-2020.
  * Zafar et al. (2019) Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. 2019.  Fairness Constraints: A Flexible Approach for Fair Classification.  _Journal of Machine Learning Research_ 20, 75 (2019), 1–42.  http://jmlr.org/papers/v20/18-262.html
  * Zhang et al. (2018) B. Zhang, Blake Lemoine, and Margaret Mitchell. 2018.  Mitigating Unwanted Biases with Adversarial Learning. In _AAAI/ACM Conference on AI, Ethics, and Society_.
  * Zhao et al. (2017) Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. 2017.  Men Also Like Shopping: Reducing Gender Bias Amplification using Corpus-level Constraints. In _Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, Copenhagen, Denmark, 2979–2989.  https://doi.org/10.18653/v1/D17-1323

##  Appendix A Appendix

###  A.1 Dataset

In this section we describe LSAC and UCI Adult datasets in detail. Both
datasets have a highly unbalanced distribution over their protected attributes
such as race and gender. Approximately $84\%$ of all samples in the LSAC
dataset have White as race, while only 1.8% have Other as race. Likewise,
there are more examples for Male than for Female gender. The labels have
skewed distributions as well; with approximately 94% samples labelled as
Passed while only 6% are labeled as Not Passed. The full breakdown of LSAC
dataset is presented in Table 5. We observe similar data distribution patterns
for the Adult dataset. Approximately $86\%$ of all samples in the Adult
dataset are associated with White race, with only $0.7\%$ with $other$ race.
There are more samples for Male than for Female and more sample for <=50K
salary range than for >50K. The full breakdown of Adult dataset is presented
in the table 6. Similar to LSAC and Adult dataset we observe uneven
distribution of samples across Gender and Race intersectional subgroups 7. We
observe that, specifically, the number of examples with recidivism label for
Male and Not Caucasian subgroup surpass the number of examples with no
recidivism label for the same subgroup. This is not the case for any other
subgroup formed by Gender and Race attributes.

Table 5: LSAC dataset breakdown by gender, race and dataset label (Bar Pass and Bar Not Pass) | Black | Hispanic | Asian | White | Other
---|---|---|---|---|---
Male ( Not Pass / Pass ) | 99 / 352 | 64 / 443 | 33 / 363 | 311 / 9622 | 17 / 197
Female ( Not Pass / Pass ) | 167 / 580 | 51 / 368 | 27 / 367 | 249 / 6957 | 20 / 140
Table 6: Adult dataset breakdown by gender, race and income category | Black | Asian-Pac-Isl | Amer-Ind-Esk | White | Other
---|---|---|---|---|---
Male($<=$50k/$>$50k) | 1736 / 408 | 563 / 304 | 230 / 39 | 18268 / 8752 | 191 / 36
Female($<=$50k/$>$50k) | 1958 / 126 | 371 / 65 | 152 / 14 | 10428 / 1455 | 117 / 9
Table 7: COMPAS dataset breakdown by gender, race and recidivism label | Caucasian | Not Caucasian
---|---|---
Male(No recid. / Did recid.) | 968 / 652 | 1630 / 1744
Female(No recid. / Did recid.) | 310 / 170 | 450 / 230

###  A.2 Additional Experiments

Similar to LSAC dataset, we perform additional experiments on the Adult
dataset when protected attributes Gender and Race are masked in the test
dataset. We observe that after masking those attributes, Accuracy, TPR, FPR
and DP Passed gaps do not change much. This validates the hypothesis that our
method learns latent representations that do not rely on protected attributes.

Table 8: Test Accuracy, TPR, FPR and DP Passed Bar gaps for the original and our models ($\alpha=0.5$) with and without masking of protected attributes applied on Adult dataset.  | Accuracy | TPR | FPR | DP Passed
---|---|---|---|---
Original model | 0.81 | 0.46 | 0.08 | 0.24
Original model w/masked $A^{(Gender,Race)}$ | 0.80 | 0.40 | 0.06 | 0.19
Our model | 0.80 | 0.23 | 0.06 | 0.19
Our model w/masked $A^{(Gender,Race)}$ | 0.80 | 0.22 | 0.06 | 0.19

Similar to LSAC and Adult datasets, we perform additional experiments with
COMPAS dataset in order to further support our findings and empirical
evidence. Figure 4 compares our method against GerryFair and adversarially-
trained methods when mitigating the intersectional subgroup bias for Gender
and Race protected attributes. We observe that our approach outperforms
GerryFair and adversarially trained methods in terms of reducing Accuracy vs
TPR, FPR and DP gap tradeoffs.

Figure 4: Our method, GerryFair and adversarially trained approaches compared
on accuracy vs fairness metrics (TPR, FPR and DP gaps) for COMPAS dataset.
Best viewed in color.