Year: 2022

Abstract:
This work aims to generalize demographic parity to continuous sensitive attributes while preserving tractable computation. Current fairness metrics for continuous sensitive attributes largely rely on intractable statistical independence between variables, such as Hirschfeld-Gebelein-Renyi (HGR) and mutual information. Statistical fairness metrics estimation relying on either tractable bounds or neural network approximation, however, are not sufficiently trustful to rank algorithms prediction bias due to lack of estimation accuracy guarantee. To make fairness metrics trustable, we propose Generalized Demographic Parity (GDP), a group fairness metric for continuous and discrete attributes. We show the understanding of GDP from the probability perspective and theoretically reveal the connection between GDP regularizer and adversarial debiasing. To estimate GDP, we adopt hard and soft group strategies via the one-hot or the soft group indicator, representing the membership of each sample in different groups of the sensitive attribute. We provably and numerically show that the soft group strategy achieves a faster estimation error convergence rate. Experiments show the better bias mitigation performance of GDP regularizer, compared with adversarial debiasing, for regression and classification tasks in tabular and graph benchmarks.

heading: 1 INTRODUCTION
text: Fairness problem has attracted increasing attention in many high-stakes applications, such as credit rating, insurance pricing and college admission (Mehrabi et al., 2021; Du et al., 2020; Bellamy et al., 2018), the adopted machine learning models encode and even amplify societal biases toward the group with different sensitive attributes. The majority of existing fairness metrics, such as demographic parity (DP) (Feldman et al., 2015), equal odds (EO) (Hardt et al., 2016), presumably consider discrete sensitive variables such as gender and race. In many real-world applications including urban studies and mobility predictions (Tessum et al., 2021), however, individuals’ sensitive attributes are unavailable due to privacy constraints. Instead, only aggregated attributes presenting in continuous distributions are available, and thus fairness requires unbiased prediction over neighborhood or region-level objects. Additionally, the sensitive attributes, such as age and weight, are inherently continuous (Mary et al., 2019; Grari et al., IJCAI’20). The widely existing continuous sensitive attributes stimulate further fairness metrics definition and bias mitigation methods.
Existing fairness metrics on continuous sensitive attributes rely on the statistical measurement of independence, such as Hirschfeld-Gebelein-Renyi (HGR) maximal correlation coefficient (Mary et al., 2019) and mutual information (Jha et al., 2021; Creager et al., 2019), which are computationintractable due to the involved functional optimization. Note that the mutual information involves the ratio of probability density function, it is intractable to directly estimate mutual information via probability density function estimation due to the sensitivity over probability density function, especially for the low probability density value. Previous works (Roh et al., 2020; Lowy et al., 2021; Cho et al., 2020) adopting mutual information or variations as regularizer, however, rely on tractable bound, or computationally complex singular value decomposition operation (Mary et al., 2019), or training-needed neural network approximation (Belghazi et al., 2018), such as Donsker-Varadhan representation (Belghazi et al., 2018), variational bounds (Poole et al., 2019). Nevertheless, it is unreliable to adopt the mathematical bound of fairness metric to evaluate different algorithms since lower metrics bound does not necessarily imply lower prediction bias. A question is raised:
and generalized demographic parity for continuous sensitive attribute. Markers represent average prediction among specific discrete sensitive attributes, Red dashed line and blue solid line
represent prediction average among all data and that with specific sensitive attribute. TV (·, ·) represents weighted total variation distance.
Can we extend DP for continuous attributes while preserving tractable computation?
In this work, we provide positive answers via proposing generalized demographic parity (GDP) from regression perspective. Figure 1 provides an illustrative example for DP and GDP. The local prediction average (blue solid curve ) and the global prediction average (red dashed line ) represent the average prediction value given sensitive attributes and the whole data samples, respectively. The local and global prediction average should be consistent at any specific continuous sensitive attributes. Therefore, we define GDP, via the weighted total variation distance, to measure the distance between the local and global prediction average, where the weight is the probability density of continuous sensitive attributes. We also theoretically demonstrate the equivalence of GDP and DP for binary sensitive attributes, provide an understanding of GDP from probability perspective, and reveal the bias mitigation methods connection between GDP regularizer and adversarial debiasing.
Although GDP is clearly defined on the unknown underlying joint distribution of prediction and sensitive attributes, only data samples, in practice, are available. To this end, we propose two GDP estimation methods, named histogram estimation (hard group strategy) and kernel estimation (soft group strategy) methods, where kernel estimation is provable with faster estimation error convergence rate w.r.t. data sample size. Specifically, histogram estimation manually divides continuous sensitive attributes into several disjointed and complementary sensitive attributes bins, and then each sample only belongs to one specific bin containing the sensitive attribute of the sample. In other words, the group indicator of the sample is one-hot. As for kernel estimation, instead of quantizing continuous sensitive attributes as several groups, the group indicator of the sample is treated as a kernel function. In other words, to calculate the mean prediction value given specific sensitive attributes, group smoothing strategy is adopted via a soft indicator determined by the sensitive attribute distance between the sample sensitive attribute with target-specific sensitive attribute.
In short, the contributions of this paper are:
• We develop a tractable group fairness metric GDP for continuous sensitive attributes. We theoretically justify GDP via demonstrating the equivalence with DP for binary sensitive attributes, providing GDP understanding from probability perspective, and revealing the connection between GDP regularizer and adversarial debiasing.
• We propose histogram and kernel GDP estimation and provably demonstrate the superiority of kernel GDP estimation method with faster estimation error convergence rate w.r.t. sample size.
• We experimentally evaluate the effectiveness and expansibility of GDP on different domain benchmarks (e.g., tabular, graph, and temporal graph data), tasks (e.g, classification and regression tasks), and compositional sensitive attributes.

heading: 2 RELATED WORK
text: Machine Learning Fairness Fair machine learning targets bias mitigation for automated decisionmaking systems. Various fairness definitions, such as group fairness and individual fairness, have been proposed (Zemel et al., 2013). Group metrics, such as DP and EO, measure prediction difference between the groups with different sensitive attributes such as gender, age (Louizos et al., 2016; Hardt et al., 2016). While pre- and post-processing methods have been proposed for fairness boosting, these methods can still lead to higher prediction bias (Barocas et al., 2017) compared with
in-processing methods, such as adding regularizer, adversarial debiasing and data augmentation. For example, the covariance between the predictions and sensitive attributes regularization are imposed to boost the independence in (Woodworth et al., 2017). (Zafar et al., 2017) constrains the decision boundaries of classifier to minimize prediction disparity between different groups. Adversarial training has been originally proposed for deep generative modeling (Goodfellow et al., 2014)and has been introduced for prediction debias in representation learning (Zhao et al., 2020; Beutel et al., 2017; Louppe et al., 2017) and transfer learning (Madras et al., 2018). Data augmentation, such as fair mixup (Chuang & Mroueh, 2020), can improve the generalization ability for fairness. Representation neutralization is proposed to boost fairness without sensitive attribute (Du et al., 2021).
Kernel Density Estimation and Kernel Regression Kernel density estimation (KDE) is a nonparametric method to estimate the continuous probability density function of a random variable (Davis et al., 2011; Parzen, 1962). Given finite data samples, KDE smoothly estimate the probability function via weighted summation, where the weight is determined via kernel function (Epanechnikov, 1969). Kernel regression is a non-parametric technique to estimate the conditional expectation of a random variable (Nadaraya, 1964). Nadaraya-Watson Kernel regression function estimator is proposed for regression via locally normalized weighted average in (Bierens, 1988), where the sample weight is determined by kernel function.

heading: 3 GENERALIZED DEMOGRAPHIC PARITY
text: Without loss of generality, we consider a binary classification task to predict the output variable Y given the input variable X , while avoiding prediction bias for sensitive attribute S. Define the input X ∈ X ⊂ Rd, labels Y ∈ {0, 1}, and machine learning model f : Rd → [0, 1] provides prediction score Ŷ = f(X). Fairness requires predictor Ŷ to be independent of sensitive attribute S, regardless of continuous or discrete, i.e., P (Ŷ = ŷ) = P (Ŷ = ŷ|S = s) for any support value y and s (Beutel et al., 2017). Since the independent constraint is difficult to optimize, the relaxed demographic parity (DP) (Madras et al., 2018) metrics are proposed to quantitatively measure the predictor bias for binary sensitive attribute S ∈ {0, 1}. Formally, the demographic parity is defined as ∆DP = |EŶ [Ŷ |S = 0] − EŶ [Ŷ |S = 1]|, where E[·] represents variable expectation. For categorical sensitive attribute S ∈ S , work (Cho et al., 2020) introduces a fairness metric, named difference w.r.t. demographic parity (DDP) ∆DDP = ∑ s∈S |EŶ [Ŷ |S = s]− EŶ [Ŷ ]|.
Although DP has been widely used to evaluate the prediction bias, it is still inapplicable for continuous sensitive attributes since the data samples cannot be directly divided into several distinctive groups based on the sensitive attributes. Without loss of generality, we assume continuous sensitive attributes S ∈ [0, 1] and propose GDP to extend tractable DP for continuous sensitive attributes. Assume the joint distribution of tuple (S, Ŷ ) is PS,Ŷ (s, ŷ), the local prediction average and global prediction average are defined as the prediction expectation given sensitive attribute S = s and without any sensitive attribute condition, i.e., local prediction average m(s) △ = E[Ŷ |S = s] and global prediction average mavg △ = ES [m(S)] = E[Ŷ ], respectively. Then, we adopt weighted total variation distance on local prediction average and global prediction average, where the weight is specified by the probability density function of the sensitive attribute. The formal definition of the discrepancy demographic parity for continuous sensitive attributes is as follows:
∆GDP = ∫ 1 0 ∣∣∣m(s)−mavg∣∣∣PS(S = s)ds = ES [|m(S)−mavg|], (1) We also provide the connection of GDP and DP for binary sensitive attributes, which implies that GDP is equivalent to DP for binary sensitive attributes, as follows:
Theorem 1 (Connection between DP and GDP). For binary sensitive attribute S ∈ {0, 1}, GPD and DP are equivalent except the coefficient only dependent on datasets. Specifically, the relation of ∆GDP and ∆DP satisfies ∆GDP = 2PS(S = 1) · PS(S = 0) ·∆DP .
The proof of Theorem 1 is presented in Appendix A. For categorical sensitive attributes, it is easy to obtain that ∆GDP = ∑ s∈S PS(S = s)|EŶ [Ŷ |S = s] − EŶ [Ŷ ]|, i.e., GDP is weighted DDP for categorical sensitive attributes. In a nutshell, GDP is a natural fairness metric extension for binary
and categorical sensitive attributes. Since the independence between prediction Ŷ and sensitive attribute S implies that the joint distribution PS,Ŷ (s, ŷ) and product marginal distribution PS(s)PŶ (ŷ) are the same, the bias can be measured by the distance of the joint distribution and product marginal distribution. Subsequently, we show the connection of GDP and prediction-weighted total variation distance between these two distributions as follows: Theorem 2 (Probability View of GDP). Assume the joint distribution of (Ŷ , S) with support [0, 1]2 is PS,Ŷ (s, ŷ). Define the prediction-weighted total variation distance as TVpred(P
1, P 2) △ =∫ 1
0 ∫ 1 0 ŷ|P 1(ŷ, s) − P 2(ŷ, s)|dŷds. Then the proposed fairness for continuous senstive attribute is upper bounded by prediction- weighted total variation distance between the joint distribution and product marginal distribution:
∆GDP = ∫ 1 0 ∫ 1 0 ∣∣∣ŷ[PS,Ŷ (s, ŷ)− PS(s)PŶ (ŷ)]∣∣∣dŷds ≤ TVpred(PS,Ŷ (s, ŷ), PS(s)PŶ (ŷ)). The proof of Theorem 2 is presented in Appendix B. Theorem 2 demonstrates that GDP is actually a lower bound for prediction-weighted total variation distance between these two distributions and implies the necessity of GDP for bias measurement.

heading: 4 GDP ESTIMATION
text: GDP is defined based on the underlying joint distribution PS,Ŷ (s, ŷ) of tuple (S, Ŷ ), where S, Ŷ ∈ [0, 1]. The underlying joint distribution, however, is unknown. Thus, we aim to estimate GDP given samples {(sn, ŷn), n ∈ [N ]}, where [N ] △ = {1, · · · , N}. To bridge this gap, we propose histogram GDP estimation and kernel GDP estimation methods based on different group strategies. Specifically, histogram GDP estimation hardly groups data samples via creating consecutive, nonoverlapping intervals bins, and the local prediction average is estimated by the average prediction among the data samples in the bin. As for kernel GDP estimation, a soft group indicator, determined by the kernel function and sensitive attribute distance, is adopted to provide group smoothing strategy. Specifically, the local prediction average for target sensitive attribute is calculated via weighted prediction, where the sample with sensitive attribute close to the target sensitive attribute possesses large weight.
Histogram GDP Estimation A histogram is originally an approximate representation of the underlying data probability distribution via creating several consecutive, non-overlapping intervals or bins with, usually but not required, equal bandwidth. In this paper, we assume all bins with equal bandwidth h and the number of bins Nh △ = 1h is an integer. In other words, the data tuples can be divided into Nh groups, and the bin intervals are given by B1 = [0, h), B2 = [h, 2h), · · · , BNh = [(Nh − 1)h, 1]. Define indicator function I(A) as 1 if event A happens, otherwise is 0. Thereby, the group indicator wh(n, i) of sample (sn, ŷn) for i− th bin is given by I(sn ∈ Bi). Note that all bin intervals are complementary; each sample belongs one and only one bin, i.e., the indicator vectors wh(n) = [wh(n, 1), · · · , wh(n,Nh)] for sample n is one-hot, which formally define the hard group strategy. The local prediction average and probability of sensitive attribute can be point-wisely estimated based on the empirical expectation and distribution. Specifically, for s ∈ Bi, the local and global prediction average are given by
m̂h ( s ∈ Bi ) = N∑ n=1 I(sn ∈ Bi)ŷi, for i ∈ [Nh]; m̂havg = N∑ n=1 ŷi. (2)
Similarly, the probability of sensitive attribute is given by P̂hS (s ∈ Bi) = ∑N n=1 I(sn∈Bi) N . Finally, we combine all estimations to calculate prediction bias as follows:
∆̂GDP (h) = Nh∑ i=1 ∣∣∣m̂h(s ∈ Bi)− m̂havg∣∣∣P̂hS (s ∈ Bi). (3) Kernel GDP Estimation Histogram GDP estimation provides a hard group strategy via creating several bins. However, a tiny sensitive attribute permutation can lead to different group indicators
and thus histogram estimation is not robust on sensitive attribute. On the other hand, a data tuple not necessarily belongs to one group for continuous attributes. For example, the data sample with s = 0.5 may have the same probability belonging to target sensitive attributes s = 0.4 and s = 0.6.
Based on these observations, we propose kernel GDP estimation via group smoothing. Intuitively, when calculating local prediction average or probability density function for target sensitive attribute, the tuple with more close attribute is entrusted higher weight. Specifically, we introduce a symmetric one-dimensional smoothing kernel function K(s) ≥ 0 satisfying normalized condition∫ K(s)ds = 1, symmetry condition ∫ sK(s)ds = 0 and finite variance σ2K △ = ∫ s2K(s)ds > 0. Define h > 0 as the kernel bandwidth. For target sensitive attribute s, the tuple weight for sample with sensitive attribute sn is given by w(sn, s) △ = 1hK( |sn−s| h ). In short, kernel function provides the group smoothing strategy based on sensitive attribute distance of tuple pair.
Given the smoothing kernel function K(s), the local and global prediction average can be obtained via normalized weighted average (Nadaraya–Watson kernel estimator) as follows:
m̃h(s) =
∑N n=1 ŷnK(
sn−s h )∑N
n=1 K( sn−s h ) , m̃havg =
∑N n=1 ŷn N . (4)
Similarly, the probability of sensitive attribute is given by p̃hS(s) = 1 Nh ∑N n=1 K( sn−s h ). Finally, we combine all estimations to calculate kernel GDP estimation as follows:
∆̃GDP (h) = ∫ 1 0 ∣∣∣m̃h(s)− m̃havg∣∣∣p̃hS(s)ds. (5) Estimation Error Analysis We provide the theoretical analysis on GDP estimation error and prove the superiority of kernel GDP estimation. Assume that each data sample is independent and identically distributed random variables. Therefore, the estimated GDP is still a random variable, and we adopt the expectation of the mean squared error (MSE) to quantify the accuracy of the estimation method. Formally, the error of histogram estimation and kernel estimation are given by
Errhist = E[|∆̂GDP −∆GDP |2]; Errkernel = E[|∆̃GDP −∆GDP |2]. (6)
where the expectation is taken across N tuples. Here, we provide an asymptotic analysis on estimation error and show the superiority of kernel GDP estimation in the following:
Theorem 3 (Estimation Error Convergence Rate). Assume that the mean prediction function m(s), given sensitive attribute s, is smooth and satisfies L- Lipschitz condition 1 on local average |m(s)− m(s ′ )| ≤ L|s− s′ | for any s, s′ . the optimal bandwidth choice for histogram and kernel estimation methods are h∗hist = O(N − 13 ) and h∗kernel = O(N
− 15 ). Additionally, the estimation error satisfy Errhist = O(N − 23 ) and Errkernel = O(N− 4 5 ), where O(·) is big O notation.
The proof of Theorem 3 is presented in Appendix C. The proof sketch is to separately provide upper bounds for the estimation error of local average and sensitive attribute probability density estimation. Finally, we combine these two estimations to obtain the estimation error for GDP.
Computation Complexity Analysis Since GDP calculation involves in integral operations, the approximated numerical integration is usually adopted with M probing sensitive attribute. The complexity to calculate local prediction average and probability density at M probing sensitive attributes are O(MN) and thus, the complexity for histogram and kernel estimation both are O(MN). In (Mary et al., 2019), intractable HGR coefficient equals second large singular value of distribution ratio matrix or can be upper bounded by tractable chi-square distance between the joint distribution and marginal product distribution. Assume that there are M probing prediction, the complexity for two-dimensional probability density function estimation and SVD is O(M2N) and O(M3), and that of the chi-square distance is O(M2N). Therefore, the computation complexity for HGR is O(M2(M + N)). As for the neural based approximation for HGR or mutual information, the complexity for training is quite large compared with directly computation.
1Lipschitz condition requires bounded gradient w.r.t. sensitive attribute and guarantees the rationale local average estimation based on neighbor data samples.

heading: 5 ANALYSIS ON GDP REGULARIZER AND ADVERSARIAL DEBIASING
text: With GDP bias measurement for continuous sensitive attributes, it is natural to add GDP regularizer to enforce fairness. Another bias mitigation is adversarial debiasing, a two-player framework for predictor and adversary with regression task. We establish the connection between GDP regularizer and adversarial debiasing, and demonstrate that adversarial debiasing with specific adversary regression objective is actually minimizing GDP implicitly.
GDP Regularizer: As a reminder, our goal is to learn a predictor Ŷ = f(X) that approximates the label Y for each input while reducing the prediction bias ∆GDP w.r.t. continuous sensitive attributes S. It is natural to add GDP regularization to enforce fairness. Given the prediction loss Lpred, the fairness-enforcing objective function is min
f Lpred
( f(X), Y ) +λ∆GDP , where L could
be regression or classification task loss and λ is the hyperparameter to control the trade-off between the prediction performance and prediction bias reduction.
Adversarial Debiasing: Adversarial debiasing is another natural method to ensure fair prediction via a two-player game between predictor and adversary. Specifically, the predictor f yields prediction Ŷ , and given prediction Ŷ , the adversary g tries to predict continuous sensitive attributes Ŝ = g(Ŷ ) in regression task. Similar to adversarial debiasing (Louppe et al., 2017), we adopt the same classifier and adversary structure, where the input of adversary is the output of the classifier. For objective function of adversary, we adopted the utility function proposed in (Madras et al., 2018) 2 to represent sensitive attribute prediction accuracy. In this case, the predictor aims to generate accurate prediction and fool the adversarial simultaneously, while adversary targets high utility for accurate sensitive attribute prediction. Let Lpred denote the prediction loss and Ladv represent the adversarial utility. Then adversarial debiasing is trained following the min-max procedure min
f max g Lpred
( f(X), Y ) +λLadv ( g ( f(X) ) , S ) . Define g∗ = argmin
g Ladv
( g ( f(X) ) , S ) as the optimal adversarial given predictor f , the min-max procedure is simplified to the objective function min
f Lpred
( f(X), Y ) + λLadv ( g∗ ( f(X) ) , S ) .
Theoretical Connection: We provide an inherent connection between GDP regularizer and adversarial debiasing. Specifically, we demonstrate that the optimal adversarial utility Ladv ( g∗ ( f(X) ) , S ) is actually the upper bound of GDP ∆GDP as long as the utility function
in adversary is Ladv(Ŝ, S) = 1− |Ŝ − S| in the following theorem:
Theorem 4 (GDP and Adversarial Debiasing Connection). Considering a predictor Ŷ = f(X) and adversary Ŝ = g(Ŷ ), given adversary utility Ladv(Ŝ, S) = 1− |Ŝ − S| and optimal adversary g∗, then GDP ∆GDP is bounded by the utility function Ladv ( g∗ ( f(X) ) , S ) with optimal adversary,
i.e., Ladv ( g∗ ( f(X) ) , S ) ≥ ∆GDP .
The proof of Theorem 4 is presented in Appendix E. Intuitively, a fair classifier aims to minimize the adversary utility to make prediction fair, and thus induces lower GDP metric. Theorem 4 reveals the inherent connection between GDP regularizer and adversarial debiasing: adversarial debiasing behaviors like predictor loss optimization with GDP regularization, as long as the adversary is optimal. Additionally, such connection not only holds for underlying data distribution, but also for empirical data distribution. The proof sketch is similar via replacing underlying data distribution as empirical data distribution in the expectation operation. In practice, the alternative optimization is usually adopted in adversarial debiasing via alternatively updating either predictor or adversary at each training step while keeping the other one fixed.
2Work (Madras et al., 2018) adopts encoder-decoder structure for transferable representation learning. We only adopt utility function to connect GDP and adversarial debiasing (Louppe et al., 2017).

heading: 6 EXPERIMENTS
text: We evaluate the effectiveness and expansibility of GDP. First, we show the lower GDP estimation error for kernel GDP estimation 3 with group smoothing, compared to that of histogram, via two synthetic experiments. We empirically evaluate the effectiveness and expansibility of kernel estimation for multiple prediction tasks, including classification and regression tasks, and multiple domain real-world datasets, including tabular, graph and temporal graph data (See Appendix H.1). Moreover, the kernel estimation is also applicable for compositional continuous sensitive attributes. For a fair comparison, we compare our method kernel, adding kernel GDP estimation as regularization, with (a) vanilla: training with empirical risk minimization (ERM) without any regularization; (b) histogram: histogram estimation with continuous sensitive attribute; (c) adv: adversarial debiasing (Louppe et al., 2017); (d) adv-bn: adversarial debiasing with binary-quantized sensitive attribute; (e) hgr: the upper bound of HGR as regularizer (Mary et al., 2019); and (f)hgr-bn: the upper bound of HGR as regularizer with binary-quantized sensitive attribute. Specifically, we demonstrate the trade-off between prediction performance and GDP by varying the hyper-parameter λ. In particular, we adopt accuracy (Acc) for classification task and mean absolute error (MAE) for regression task. Details about the baselines and experimental setups for each dataset can be found in Appendix H.2.

heading: 6.1 SYNTHETIC EXPERIMENTS
text: We test GDP estimation error and investigate the robustness for histogram and kernel estimation via two synthetic experiments. The goal is to investigate the effect of bandwidth choice and number of samples on GDP estimation error. For data generation, we first generate bivariate Gaussian distribution N (µ,Σ) for samples (S, Ŷ ), where expectation µ = [0.5, 1.0] and covariance matrix
Σ = [ 1 0.5 0.5 2.0 ] . Additionally, we generate the samples based on pS,Ŷ (s, ŷ) = s+ ŷ if 0 ≤ s, ŷ ≤
1, via acceptance-rejection method (Wells et al., 2004). For estimation, we select two typical kernel functions (tricube and Aitchison-Aitken kernel (Mussa, 2013)) for local prediction average, and two kernel functions (linear and cosine kernel functions) for probability density function estimation.
Figure 2 shows the GDP estimation error w.r.t. bandwidth h and number of samples N for bivariate Gaussian distribution and second synthetic bivariate distribution, respectively. We observe that histogram GDP estimation error is highly sensitive to bandwidth choice, while kernel estimation is robust to bandwidth and kernel function choice due to the flexibility of group smoothing. As for error rate with number of samples, our experiments show the error rate curve for histogram and kernel estimation. It is seen that kernel estimation can achieve the fast error convergence rate if searching the optimal bandwidth for each method. In addition, the estimation error result is almost the same for different kernel functions, which supports the theoretical results in Theorem 3.

heading: 6.2 EXPERIMENTS ON TABULAR DATA
text: Dataset:We consider two benchmark tabular datasets, UCI Adult and Crimes, to evaluate the effectiveness of kernel estimation for classification and regression tasks. UCI Adult dataset 4 contains more than 40, 000 individual information from 1994 US Census. The classification task is to predict
3Since there is not ground truth on underlying data distribution, we adopt reliable kernel-based estimated GDP as fairness metric in real-world datasets.
4https://archive.ics.uci.edu/ml/datasets/adult
whether a person’s income exceeds $50k/yr (KOHAVI, 1996). We consider normalized age 5 sensitive attribute to measure the fairness of algorithms. The Crime dataset 6 includes 128 attributes for 1, 994 samples from communities in the US. The regression task is to predict the number of violent crimes per population in US communities. We adopt the black group ratio as continuous sensitive attribute. Model: We adopt two-layer selu networks model (Klambauer et al., 2017) with hidden size 50 and report the mean prediction performance and GDP with 5 running times.
Results: We compare the bias mitigation performance, i.e., the tradeoff between prediction performance and GDP, of kernel estimation with other baselines for the two tabular datasets in Figure 3. The hyper-parameter λ in Eq. (5) controls the tradeoff between prediction performance and GDP. Specifically, we choose accuracy metric for classification task in Adult dataset, and MAE metric for regression task in Crimes datset. For adversarial debiasing, we vary the regularization weights to obtain the tradeoff curve. Overall, we make the following observations: (a) kernel estimation outperforms all other baseline methods in terms of performance-fairness tradeoff curve for Adult and Crimes datasets. Specifically, kernel estimation can achieve more than 1% accuracy improvement if GDP is lower than 0.02 for adult dataset, and more than 2% MAE reduction for Crimes dataset; (b) kernel estimation has lower computation complexity compared with adversarial debiasing. Kernel estimation and histogram decrease more than 50% running time on an average across all tabular dataset, which makes kernel and histogram estimation readily usable for large scale realworld datasets; (c) The histogram estimation and binary-quatized sensitive attribute would lead to mitigation performance drop for kernel estimation, adversarial debiasing and HGR. This fact implies the importance of order information in continuous sensitive attributes for bias mitigation. In addition, we observe adversarial debiasing training and HGR are not stable and large hyper-parameter unnecessarily leads to bias mitigation.

heading: 6.3 EXPERIMENTS ON GRAPH DATA
text: Dataset: We consider two real-world graph datasets, Pokec-z and Pokec-n, sampled from a larger one Facebook-like social network Pokec in Slovakia. User profiles contain gender, age, interest, education, working field and etc. We treat the normalized age as the continuous sensitive attributes and the node classification task is to predict the working field of the users. Model: We use three graph neural network backbones, graph convolutional networks (GCN) (Kipf & Welling, 2017), graph attention networks (GAT) (Veličković et al., 2018) and Simplifying graph convolutional networks (SGC) (Wu et al., 2019) with 64 feature dimensions. We train GNN with 200 epochs with 5 running times and report the average accuracy and GDP. In each trial, the dataset is randomly split into a training, validation, and test set with 50%, 25%, and 25% partition, respectively.
Results: We compare the mitigation performance of kernel estimation with other baselines for two datasets with three backbones in Figure 4. Similarly, kernel estimation consistently outperforms the other baselines by a large margin and binary-quantized sensitive attributes inevitably deteriorate the mitigation performance. Another observation is that GDP can be reduced at least 80% at the cost
5The biggest difference between continuous and discrete sensitive attribute falls in the existence of order information (Mary et al., 2019) for attribute values.
6https://archive.ics.uci.edu/ml/datasets/communities+and+crime
of 2% accuracy for kernel estimation in two datasets and three backbones, while results in larger accuracy drop for other baselines. Additionally, adversarial debiasing and HGR are also unstable during training and higher hyper-parameter may lead to larger GDP.

heading: GCN GAT SGC

heading: 6.4 EXPERIMENTS ON COMPOSITIONAL CONTINUOUS SENSITIVE ATTRIBUTES
text: Dataset: Similarly, the same two benchmark tabular datasets are adopted to evaluate the effectiveness of kernel estimation for compositional continuous sensitive attributes. Specifically, we treat the normalized age and education number for UCI dataset, and black group ratio and normalized age for Crimes dataset as compositional continuous sensitive attributes. to evaluate bias mitigation performance. Model: We also adopt two-layer selu networks model with hidden size 50 with 5 running times and report the average mean prediction performance and GDP.
Results: Figure 5 shows bias mitigation performance between prediction performance and GDP. Again, kernel estimation consistently achieves a better tradeoff compared with all other baselines, and binary-quantized compositional sensitive attribute leads to mitigation performance drop.

heading: 7 CONCLUSION
text: We generalize demographic parity fairness metric, named GDP, to continuous sensitive attributes while preserving tractable computation. We theoretically justify the unification of proposed GDP for continuous and discrete sensitive attributes, and show the necessity of GDP via demonstrating the connection with joint and product margin distributions distance. We also propose two GDP estimation methods, named histogram and kernel, with linear computation complexity via hard and soft group strategies, and provide corresponding estimation error analysis. For the superiority of kernel estimation, we provably demonstrate the faster estimation error convergence rate compared with histogram estimation, and experimentally show better bias mitigation performances in multiple domains, multiple tasks and compositional sensitive attributes.

heading: A PROOF OF THEOREM 1
text: For binary sensitive attribute S ∈ {0, 1}, the probability of sensitive attribute follows Bernoulli distribution ( PS(S = 0), PS(S = 1) ) . Therefore, the global prediction average is given by mavg =
PS(S = 0)m(0) + PS(S = 1)m(1) and GDP is ∆GDP = PS(S = 0) ∣∣∣m(0)−mavg∣∣∣+ PS(S = 1)∣∣∣m(1)−mavg∣∣∣
= PS(S = 0) ∣∣∣m(0)− PS(S = 0)m(0)− PS(S = 1)m(1)∣∣∣
+PS(S = 1) ∣∣∣PS(S = 0)m(0) + PS(S = 1)m(1)−m(1)∣∣∣
= 2PS(S = 0)PS(S = 1)|m(0)−m(1)| = 2PS(S = 0)PS(S = 1)∆DP.
where the coefficient 2PS(S = 0)PS(S = 1) only depends on data. This fact demonstrates the applicability of GDP for categorical sensitive attribute with discrete measure choice for sensitive attributes, and it is equivalent to demographic parity for binary sensitive attribute.

heading: B PROOF OF THEOREM 2
text: Notice that the fairness constraint ideally requires the independence of prediction Ŷ and sensitive attribute S, i.e., the joint distribution and product margin distribution equals: PŶ ,S(ŷ, s) = PS(s)PŶ (ŷ). Aiming to measure independence deviation, a natural intuition is to quantify the probability deviation via the distance between the joint distribution and product margin distribution. We show the connection between the proposed GDP and prediction-weighted total variation distance of these two distributions. Recall the definition of GDP, it is easy to obtain
∆GDP = ∫ 1 0 ∣∣∣m(s)−mavg∣∣∣PS(S = s)ds =
∫ 1 0 ∣∣∣ ∫ 1 0 ŷPŶ |S(y|s)dŷ − ∫ 1 0 ŷPŶ (y)dŷ ∣∣∣PS(S = s)ds
= ∫ 1 0 ∣∣∣ ∫ 1 0 ŷ ( PŶ ,S(y, s)− PS(s)PŶ (ŷ) ) dŷ ∣∣∣dŷds ≤
∫ 1 0 ∫ 1 0 ŷ ∣∣∣PŶ ,S(y, s)− PS(s)PŶ (ŷ)∣∣∣dŷds
= TVŷ(PŶ ,S(ŷ, s), PS(s)PŶ (ŷ).
which completes the proof.

heading: C PROOF OF THEOREM 3
text: Notice that histogram and kernel estimation require local prediction average and probability density function estimation for sensitive attributes, we start with the analysis on local prediction average and probability density function estimation, and then provide the proof of GDP error analysis.

heading: C.1 PROOF FOR HISTOGRAM ESTIMATION
text: Recall that the number of bins is Nh with same bandwidth h, and bins interval are given by B1 = [0, h), B2 = [h, 2h), · · · , BNh = [(Nh − 1)h, 1]. Firstly, we will separately analyze the error for local prediction average and sensitive attribute probability. Next, these two estimation error results can be combined for GDP estimation error.
Since the continuous sensitive attributes is considered, we defined the probability density function of sensitive attribute S as pS(s). The estimated probability density function is given by:
p̂hS(s) = 1
h P̂hS (s ∈ Bi) =
1
Nh N∑ n=1 I(sn ∈ Bi) for s ∈ Bi; (7)
Subsequently, we define the pointwise MSE error MSEpdfhist(s) to measure probability density function estimation error given sensitive attribute s as follows:
MSEpdfhist(s) = E[|p̂ h S(s)− pS(s)|2], (8)
where the expectation is took across N samples. Then we have following Lemma 1 on optimal pointwise MSE error for probability density function: Lemma 1. Assume the mean prediction function m(s), given sensitive attribute s, is smooth and satisfies L-Lipschitz condition |m(s) − m(s′)| ≤ L|s − s′ | for any s, s′ . Given N i.i.d. samples {(ŷn, sn), n ∈ [N ]}, then the optimal MSE error min
h MSEpdfhist(s) is O(N − 23 ), where the optimal
bandwidth satisfies h∗ = O(N− 1 3 ) for any sensitive attribute s.
As for the local prediction average, similarly, we have the estimated local prediction average as follows:
m̂(s) = ∑N n=1 I(sn ∈ Bi)ŷn∑N n=1 I(sn ∈ Bi) for s ∈ Bi; (9)
Subsequently, we also define the pointwise MSE error MSEreghist(s) to measure local prediction average estimation error given sensitive attribute s as follows:
MSEreghist(s) = E[|m̂ h(s)−m(s)|2], (10)
where the expectation is took across N samples. Then we have following Lemma 2 on optimal pointwise MSE error for local prediction average: Lemma 2. Assume the mean prediction function m(s), given sensitive attribute s, is smooth and satisfies L-Lipschitz condition |m(s) − m(s′)| ≤ L|s − s′ | for any s, s′ . Define the bounded prediction variance σ2(s) ≤ σ2, given sensitive attribute s, as σ2(s) △= EŶ |S [(Ŷ − m(s))2|S = s]. Given N i.i.d. samples {(ŷn, sn), n ∈ [N ]}, then the optimal MSE error min
h MSEreghist(s) is
O(N− 2 3 ), where the optimal bandwidth satisfies h∗ = O(N− 1 3 ) for any sensitive attribute s.
Proof for histogram estimation: Based on the definition of MSE error in Eq. (6), we have
Errhist = E[|∆̂GDP −∆GDP |2] (a) ≤ E [{∫ 1
0 ∣∣∣|m̂h(s)− m̂avg|p̂hS(s)− |m(s)−mavg|pS(s)∣∣∣ds}2] (b)
≤ E [{∫ 1
0 ∣∣∣|m̂h(s)− m̂avg| · |p̂hS(s)− pS(s)| − |m(s)−mavg − m̂h(s) + m̂avg| · pS(s)∣∣∣ds}2] (c)
≤ 2E [ ∫ 1
0
|m̂h(s)− m̂avg|2ds ] · E [ ∫ 1 0 |p̂hS(s)− pS(s)|2ds ]
+2 ∗ 2 { E [ ∫ 1
0
|m̂h(s)−m(s)|2pS(s)ds+ E [ ∫ 1
0
|m̂havg −mavg|2pS(s)ds ]}
(d) ≤ 2 ∗O(N− 23 ) + 4 ∗O(N− 23 ) + 4 ∗N−1 = O(N− 23 ).
where inequality (a) holds due to absolute value inequality, inequality (b) holds due to |a1b1 − a2b2| ≤ |a1||b1 − b2| + |a1 − a2||b2|, inequality (c) holds based on (a + b)2 ≤ 2(a2 + b2) and Cauchy–Schwarz inequality, inequality (d) holds based on Lemmas (1) and (2). Note that the order of the optimal bandwidth are the same in Lemmas (1) and (2), the optimal bandwidth for minimizing GDP MSE is O(N− 1 3 ).

heading: C.2 KERNEL ESTIMATION
text: Recall that we assume that kernel function satisfies normalized condition ∫ K(s)ds = 1, symmetry∫
sK(s)ds = 1 and finite variance σ2K △ = ∫ s2K(s)ds > 0. We also define σ̃2K = ∫ K2(y)dy. Similarly, the probability density function of sensitive attribute is given by pS(s). The estimated probability density function is given by:
p̃hS = 1
Nh N∑ n=1 K( sn − s h ), (11)
Subsequently, we define the pointwise MSE error MSEpdfkernel(s) to measure probability density function estimation error given sensitive attribute s as follows:
MSEpdfhist(s) = E[|p̃ h S(s)− pS(s)|2], (12)
where the expectation is took across N samples. Then we have following Lemma 3 on optimal pointwise MSE error for probability density function: Lemma 3. Given N i.i.d. samples {(ŷn, sn), n ∈ [N ]}, then the optimal MSE error min h MSEpdfkernel(s) is O(N − 45 ), where the optimal bandwidth satisfies h∗ = O(N− 1 5 ) for any sensitive attribute s.
As for the local prediction average, similarly, we have local prediction average estimation as follows:
m̃(s) =
∑N n=1 K(
sn−s h )ŷn∑N
n=1 K( sn−s h ) , (13)
Subsequently, we also define pointwise MSE error MSEregkernel(s) to measure local prediction average estimation error given sensitive attribute s as follows:
MSEregkernel(s) = E[|m̂ h(s)−m(s)|2], (14)
where the expectation is took across N samples. Then we have following Lemma 4 on optimal pointwise MSE error for local prediction average: Lemma 4. Define the bounded prediction variance σ2(s) ≤ σ2, given sensitive attribute s, as σ2(s)
△ = EŶ |S [(Ŷ −m(s))2|S = s]. Given N i.i.d. samples {(ŷn, sn), n ∈ [N ]}, then the optimal
MSE error min h
MSEregkernel(s) is O(N − 45 ), where the optimal bandwidth satisfies h∗ = O(N− 1 5 )
for any sensitive attribute s.
Proof for kernel estimation: Based on the definition of MSE error in Eq. (6), we have
Errkernel = E[|∆̃GDP −∆GDP |2] (e) ≤ E [{∫ 1
0 ∣∣∣|m̃h(s)− m̃avg|p̃hS(s)− |m(s)−mavg|pS(s)∣∣∣ds}2] (f)
≤ E [{∫ 1
0 ∣∣∣|m̃h(s)− m̃avg| · |p̃hS(s)− pS(s)| − |m(s)−mavg − m̃h(s) + m̃avg| · pS(s)∣∣∣ds}2] (g)
≤ 2E [ ∫ 1
0
|m̃h(s)− m̃avg|2ds ] · E [ ∫ 1 0 |p̃hS(s)− pS(s)|2ds ]
+2 ∗ 2 { E [ ∫ 1
0
|m̃h(s)−m(s)|2pS(s)ds+ E [ ∫ 1
0
|m̃havg −mavg|2pS(s)ds ]}
(h)
≤ 2 ∗O(N− 45 ) + 4 ∗O(N− 45 ) + 4 ∗N−1 = O(N− 45 ). where inequality (e) holds due to absolute value inequality, inequality (f) holds due to |a1b1 − a2b2| ≤ |a1||b1 − b2| + |a1 − a2||b2|, inequality (g) holds based on (a + b)2 ≤ 2(a2 + b2) and Cauchy–Schwarz inequality, inequality (h) holds based on Lemmas (3) and (4). Note that the order of the optimal bandwidth are the same in Lemmas (3) and (4), the optimal bandwidth for minimizing GDP MSE is O(N− 1 5 ).

heading: D PROOF OF LEMMAS

heading: D.1 PROOF OF LEMMA 1
text: Proof. Note that there exists bias-variance tradeoff for MSEpdfhist(s), i.e.,
MSEpdfhist(s) = E[|p̂ h S(s)− pS(s)|2] = ∣∣∣E[p̂hS(s)]− pS(s)∣∣∣2︸ ︷︷ ︸
Biaspdfhist(s)
+E[ ∣∣∣p̂hS(s)− E[p̂hS(s)]∣∣∣2]︸ ︷︷ ︸
V arpdfhist(s)
,
Next we analyze the bias and variance for probability density function MSE. For the bias part, note that, for s ∈ Bi, the expectation of estimated probability density function satisfies:
E[p̂hS(s)] = 1
h P (sn ∈ Bi) =
∫ ih (i−1)h pS(s)ds
h = pS(s
∗), s∗ ∈ Bi;
where the last equality holds by the mean value theorem. Therefore, the bias satisfies Biaspdfhist(s) = ∣∣∣E[p̂hS(s)]− pS(s)∣∣∣
≤ L|s∗ − s| ≤ Lh. As for variance part, note that the variance of Bernoulli distribution with parameter p is p(1 − p), for s ∈ Bi, we have the variance as follows,
V arpdfhist(s) = 1
h2 D[
1
N N∑ n=1 I(s ∈ Bi)] = P (sn ∈ Bi)[1− P (sn ∈ Bi)] Nh2
≤ hpS(s ∗)
Nh2 =
pS(s ∗)
Nh ;
Combining the bias and variance part, we have
MSEpdfhist(s) = [Bias pdf hist(s)] 2 + V arpdfhist(s) ≤ L 2h2 +
pS(s ∗)
Nh , (15)
It is easy to obtain the optimal bandwidth h∗ = [pS(s ∗)
2L2N ] 1 3 = O(N− 1 3 ), and the minimized MSE is
lower than [Lps(s ∗)
2N ] 2 3 = O(N− 2 3 ).

heading: D.2 PROOF OF LEMMA 2
text: Proof. Note that the local prediction average by histogram, for s ∈ Bi, is given by m̂(s) =∑N n=1 I(sn∈Bi)Yn∑N n=1 I(sn∈Bi) . Define the normalized weight as wn(sn) = I(sn∈Bi)∑N n=1 I(sn∈Bi) , then local prediction
average is given by m̂(s) = ∑N
n=1 wn(sn)m(sn). Similarly, we can obtain the bias and variance tradeoff for local prediction average error MSEreghist(s) as follows,
MSEreghist(s) = E[|m̂ h(s)−m(s)|2] = ∣∣∣E[m̂h(s)]−m(s)∣∣∣2︸ ︷︷ ︸
Biashistreg (s)
+E[ ∣∣∣m̂h(s)− E[m̂h(s)]∣∣∣2]︸ ︷︷ ︸
V arhistreg (s)
,
For the bias part, based on Lipschitz condition on the mean prediction function, note that∑N n=1 wn(sn) = 1, we have
Biashistreg (s) = ∣∣∣E[m̂h(s)]−m(s)∣∣∣ = ∣∣∣ N∑
n=1
wn(sn)[m(sn)−m(s)] ∣∣∣
≤ N∑
n=1
wn(sn) ∣∣∣[m(sn)−m(s)]∣∣∣ ≤ N∑
n=1
wn(sn)Lh = Lh. (16)
For the variance part, we have variance for local prediction average as follows,
V arhistreg (s) = D[ N∑
n=1
wn(sn)ŷn] = E [ [ ∑N n=1 I(sn ∈ Bi)(Yn −m(sn))∑N n=1 I(sn ∈ Bi) ]2 ]
≤ N∑
n=1
E [ I(sn ∈ Bi)σ2(∑N n=1 I(sn ∈ Bi) )2 ] ≤ Nσ2/Nh(N/Nh)2 = σ 2 Nh (17)
Combining the bias and variance part, we have
MSEreghist(s) = [Bias reg hist(s)] 2 + V arreghist(s) ≤ L 2h2 +
σ2
Nh , (18)
It is easy to obtain the optimal bandwidth h∗ = [ σ 2 2L2N ] 1 3 = O(N− 1 3 ), and the minimized MSE is lower than [Lσ 2
2N ] 2 3 = O(N− 2 3 ).

heading: D.3 PROOF OF LEMMA 3
text: Proof. Note that there exists bias-variance tradeoff for MSEpdfkernel(s), i.e.,
MSEpdfkernel(s) = E[|p̂ h S(s)− pS(s)|2] = ∣∣∣E[p̂hS(s)]− pS(s)∣∣∣2︸ ︷︷ ︸
Biaspdfkernel(s)
+E[ ∣∣∣p̂hS(s)− E[p̂hS(s)]∣∣∣2]︸ ︷︷ ︸
V arpdfkernel(s)
,
Next we analyze the bias and variance for probability density function MSE. For the bias part, the expectation of estimated probability density function satisfies:
E[p̃hS(s)]− p̃hS(s) = E[ 1
Nh N∑ n=1 K( sn − s h )]− p̃hS(s)
= 1
h E[K( sn − s h )]− p̃hS(s)
= 1
h
∫ K(
sn − s h )pS(sn)dsn − p̃hS(s)
= ∫ K(y)pS(s+ hy)dy − p̃hS(s). (19)
where the last equality holds by adopting transformation y = sn−sh . By Taylor expansion, when h is small, we have
pS(s+ hy) = pS(s) + hyp ′ S(s) + h2y2
2 p
′′ S(s) + o(h 2) (20)
Based ob Eqs. (19) and (20), we have
Biaspdfkernel(s) = |E[p̃ h S(s)]− p̃hS(s)|
= pS(s)
∫ K(y)dy + hp ′
S(s)
∫ yK(y)dy + h2
2 p
′′ S(s) ∫ y2K(y)dy + o(h2)− pS(s)
= h2σ2K 2 p ′′ S(s); (21)
As for the variance part, we have
V arpdfkernel(s) = D[ 1
Nh N∑ n=1 K( sn − s h )] = 1 Nh2 D[K( sn − s h )] ≤ 1 Nh2 E[K2( sn − s h )]
= 1
Nh2
∫ K2(
sn − s h )pS(sn)dsn = 1 Nh
∫ K2(y)pS(s+ hy)dy
= 1
Nh
∫ K2(y)[pS(s) + hyp ′ S(s) + o(h)]dy = pS(s)
Nh
∫ K2(y)dy + o(h)
= pS(s)σ̃
2 K
Nh + o(
1
N ) (22)
Combining the bias and variance part, we have
MSEpdfkernel(s) = [Bias pdf kernel(s)] 2 + V arpdfkernel(s)
≤ h 4|p′′S(s)|2σ4
4 +
pS(s)σ̃ 2 K
Nh + o(h4) + o(
1
N )
= O(h4) +O( 1
Nh ), (23)
It is easy to obtain that the optimal bandwidth h∗ = O(N− 1 5 ), and thus, the minimized MSE is lower than O(N− 4 5 ).

heading: D.4 PROOF OF LEMMA 4
text: Proof. Recall that the mean prediction conditioned on sensitive attribute s is given by m(s) = E[Ŷ |S = s], we rewrite prediction as Ŷ = m(S) + e, where e is the regression noise and satisfies E[e] = 0 and E[e2|S = s] = σ2(s). Note that the prediction Y = m(s) + [m(S)−m(s)] + e, we have:
1
Nh N∑ n=1 K( sn − s h )ŷn =
1
Nh N∑ n=1 K( sn − s h )m(s) + 1 Nh N∑ n=1 K( sn − s h )[m(sn)−m(s)]
+ 1
Nh N∑ n=1 K( sn − s h )en
= p̂S(s)m(s) + m̃1(s) + m̃2(s).
Based on Eq. (13), we have
m̃(s) = m(s) + m̃1(s)
p̂S(s) +
m̃2(s) p̂S(s) . (24)
Since E[e|S = s] = 0, we have the expectation of E[m̃2(s)] = 0 since E[K( sn−sh )e] = E[K( sn−sh )E[e|S = sn]] = 0. As for the variance of m̃2(s), we have
D[m̃2(s)] = 1
Nh2 E[K( sn − s h )e2] = 1 Nh2 E[K( sn − s h )σ2(sn)]
= 1
Nh2
∫ K(
sn − s h )σ2(sn)pS(sn)dsn
= 1
Nh
∫ K(y)σ2(s+ yh)pS(s+ yh)dsn
= σ̃2Kσ 2(s)pS(s)
Nh + o(
1
Nh ); (25)
Subsequently, we consider the expectation and variance of m̃1(s). Specifically, for expectation, we have
E[m̃1(s)] = 1 h E [ K( sn − s h ) ( m(sn)−m(s) )] = 1
h
∫ K(
sn − s h
) ( m(sn)−m(s) ) pS(sn)dsn
= ∫ K(y) ( m(s+ hy)−m(s) ) pS(s+ hy)dy
= ∫ K(y) ( hym ′ (s) + y2h2
2 m
′′ (s) )( pS(s) + hyp ′ S(s) ) + o(h2)dy
= σ2Kh 2 (m′′(s)pS(s)
2 +m
′ (s)p ′ S(s) ) + o(h2). (26)
As for the variance of m̃1(s), we have
D[m̃1(s)] = 1 Nh2 D [ K( sn − s h ) ( m(sn)−m(s) )] = 1
Nh2
∫ { K(
sn − s h
) ( m(sn)−m(s) ) − E[m̃(s)] }2 pS(sn)dsn
= 1
Nh
∫ [ K(y)hym ′ (s)− E[m̃(s)] ]2( pS(s) + yhp ′ S(s) ) dsn
= σ2(s)σ2K PS(s)Nh + o( 1 Nh ) = O( 1 Nh ).
Combining the bias and variance part, we have
MSEregkernel(s) = [Bias reg kernel(s)] 2 + V arregkernel(s) ≤ L 2h2 +
σ2
Nh ≤ O(h4) +O( 1 Nh ), (27)
Based on the inequality of arithmetic and geometric means, it is easy to obtain the optimal bandwidth h∗ = O(N− 1 5 ), and the minimized MSE is lower than O(N− 4 5 ).

heading: E PROOF OF THEOREM 4
text: Given predictor Ŷ = f(X), adversary Ŝ = g(Ŷ ), and adversary utility Ladv(Ŝ, S) = 1− |Ŝ − S|, GDP and adversary utility are given by
∆GDP = ES [∣∣∣EX|S [f(X)]− EX [f(X)]∣∣∣]; Ladv = ES[EX|S[1− ∣∣S − g(f(X))∣∣]].
Intuitively, higher model prediction implies larger sensitive attribute if mean prediction function m(s) is more close to s compared with 1− s and vice versa. Therefore, we construct adversary g as follows:
g# ( f(X) ) = { f(X), if ES [|S −m(S)|] ≤ ES [ ∣∣S − (1−m(S))∣∣]; 1− f(X), Otherwise.
Suppose without loss of generality (WLOG) that ES [|S − m(S)|] ≤ ES [ ∣∣S − (1 − m(S))∣∣], i.e., higher model prediction implies larger sensitive attribute. Then adversary utility is given by
Ladv ( g# ( f(X) ) , S ) = ES [ EX|S [ 1− ∣∣S − f(X)∣∣]] ≤ ES[[1− ∣∣S − EX|S [f(X)]∣∣]] = ES [ 1−
∣∣S −m(S)∣∣] where the inequality holds due to Jensen’s inequality and convex function |x − t| for any constant t. Next we show, under the constructive adversary g, the adversarial utility Ladv ≥ 12 ≥ ∆GDP . Firstly, notice that, for any function m(S) ∈ [0, 1] and S ∈ [0, 1], we have
|S −m(S)|+ ∣∣S − (1−m(S))∣∣ ≤ max{|1−m(S)|+ ∣∣1− (1−m(S))∣∣,
|0−m(S)|+ ∣∣0− (1−m(S))∣∣} = 1,
which implies that ES [ 1− ∣∣S −m(S)∣∣] ≤ 1 2 ( ES [|S −m(S)|] + ES [ ∣∣S − (1−m(S))∣∣]) = 1
2
( ES [ |S −m(S)|+ ∣∣S − (1−m(S))∣∣]) ≤ 1 2 .
As for the analysis on GDP, we consider the worst case of mean prediction function m(s) since GDP satisfies ∆GDP = ES [ ∣∣m(S)− ES [m(S)]∣∣]. Note that function |x| is strictly convex and the solution to maximize a strictly convex function over all finite support given first moment is achieved by a distribution of two mass extreme points, GDP can achieve maximal value when m(S) is 0 or 1. Define ppos = ES [ P ( m(S) = 1 )] , then ES [m(S)] = ppos and ∆GDP = ppos ( 1− ppos ) + (1−
ppos)ppos ≤ 12 . Therefore, for the optimal adversary g ∗, we have Ladv ( g∗ ( f(X) ) , S ) ≥ Ladv ( g# ( f(X) ) , S ) ≥ ∆GDP. (28)

heading: F DATA STATISTICS
text: For fair comparision with previous work, we perform the classification and regression task on five datasets, including Crimes, Adult, Pokec-n, Pokec-z and Harris dataset. The first four dataset have been widely adopted to study the fairness problem in tabular data and graph data, while Harris dataset is collected by ourself for temporal graph data. Table 1 presents additional information on the real-world tabular, graph and temporal graph datasets. For task type column, “Reg” and “Clf” represents regression task and classification task, respectively.

heading: G MORE DETAILS ON SYNTHETIC EXPERIMENTS

heading: G.1 GDP CALCULATION
text: We firstly provide ground truth analysis in synthetic experiments so that we can evaluate propsoed two GDP estimation methods error. Considering bivariate Gaussian distribution with mean µ = [µ1, µ2] and covariance matrix Σ = [ σ11 σ12 σ21 σ22 ] and note that covariance matrix is positive definite
matrix, it is easy to obtain inverse covariance matrix Σ−1 = [ λ11 λ12 λ21 λ22 ] , where λ22 = σ11|Σ| and
λ12 = −σ12|Σ| . The joint distribution of (S, Ŷ ) follows pS,Ŷ (s, ŷ) = 1√
2π|Σ| exp
( − 12λ11(s−µ1)
2− 1 2λ22(s − µ2) 2 + λ12(s − µ1)(ŷ − µ2) )
. Based on probability theory, we can have the condition function pŶ |S(ŷ|s) as follows:
pŶ |S(ŷ|s) = pS,Ŷ (s, ŷ)
pS(s) = 1√ 2π λ22
exp ( − λ22 ( ŷ − λ22µ2+λ12s−λ12µ1λ22 )2 2 )
∼ N (σ11µ2 + σ12(s− µ1)
σ11 , |Σ| σ11
) .
which means the mean prediction function m(s) = σ11µ2+σ12(s−µ1)σ11 . Notice that the probability density function of sensitive attribute is also Guassian with N (µ1, σ11), therefore, the GDP is
∆GDP = ∫ |m(s)− µ2|pS(s)ds
= ∫ ∣∣∣σ12(s− µ1) σ11 ∣∣∣ 1√ 2πσ11 exp ( − (s− µ1) 2 2σ11 ) ds = 2σ12√ 2πσ11 .
Next, we calculate GDP for the second synthetic probability density function pS,Ŷ (s, ŷ) = s + ŷ if 0 ≤ s, ŷ ≤ 1. It is easy to obtain the conditional probability pŶ |S(ŷ|s) =
s+ŷ s+ 12 if 0 ≤ s, ŷ ≤ 1
and thus the mean prediction function m(s) = E[Ŷ |S = s] = 1 2 s+ 1 3
s+ 12 . Similarly, the probability of
sensitive attribute is pS(s) = s+ 12 if 0 ≤ s, ŷ ≤ 1. Thus, the GDP satisfies
∆GDP = ∫ ∣∣∣m(s)− E[m(S)]∣∣∣pS(s)ds = ∫ 1 0 ∣∣∣ 12s+ 13 s+ 12 − 7 12 ∣∣∣(s+ 1 2 )ds = 1 48 .

heading: G.2 MORE SYNTHETIC EXPERIMENT RESULTS ON ESTIMATION ERROR
text: Figure 6 shows local prediction average and sensitive attribute probability density function estimation results for different kernel function choice. The top two subfigures show the local prediction average estimation error w.r.t. bandwidth choice. It is seen that the tricube and aitchison aitken kernel function achieve better and robust local prediction average estimation compared with Gaussian kernel function. The mid subfigures show the local prediction average result for different sensitive attribute and bottom two subfigures shows probability density function estimation results with different kernel and histogram choice. It is seen that kernel estimation possesses more smooth and accurate probability density function estimation.

heading: G.3 MORE SYNTHETIC EXPERIMENT RESULTS ON ROBUSTNESS
text: In this subsection, we aim to investigate the robustness of GDP estimation error over different mean and covariance parameters. Note that only the parameters expectation µ = [µ1, µ2] = [0.5, 1.0] and covariance matrix Σ = [ σ11 σ12 σ12 σ22 ] = [ 1 0.5 0.5 2.0 ] are adopted on synthetic experiments, we adopt these parameters as default and only modify the one parameter to inspect GDP estimation error. Figures 7 and 8 show the GDP estimation error with mean parameters µ1 and µ2, and covariance parameters σ11, σ12, and σ22 given the same data size 1000. We have two observations: (1) kernel-based GDP estimation methods consistently achieves lower estimation errors than histogrambased counterpart for any Gaussian distribution parameter, which further validates the superiority of kernel-based method. (2) kernel-based GDP estimation error is almost the same for any kernel function pair choice, which validates our theoretical analysis in Theorem. 3.

heading: H MORE DETAILS ON REAL-WORLD EXPERIMENTAL RESULTS

heading: H.1 MITIGATION PERFORMANCE FOR TEMPORAL GRAPH DATA
text: The temporal graph data, provided by data intelligence company Cuebiq (Cuebiq, 2021), is collected from anonymous human movement activities, including the coordinates and time of mobile devices at stop points, during August 2017 in Harris County (Houston) Texas, USA. To generate the temporal graph, we first divide the Harris County into several grid cells with equal size approximately 1km× 1km. Each grid cell is treated as a graph node, and temporal link between two nodes represents at least one user movement in hourly basis duration. The node features are generated from socio-demographic data of the American Community Survey (ACS) 2014–2018 (5-year) data by the U.S. Census Bureau (Bureau, 2021). In the experiment, the white race ratio is treated as continuous sensitive attributes and our task is to predict whether the income of each node is high or low. We adopt temporal graph attention (TGAT) (da Xu et al., 2020)7 with map and product attention mechanism to efficiently aggregate temporal-topological neighborhood features and report the mean prediction performance and GDP with 5 running times.
7https://github.com/StatsDLMathsRecomSys/Inductive-representation-learning-on-temporal-graphs
We compare the mitigation performance of kernel estimation and other baselines for private Harris dataset with two backbones in Figure 9. Simialrly, the hyper-parameter λ control the tradeoff between accuracy and GDP. Again, kernel estimation consistently outperforms the other baselines by a large margin and binary-quantized sensitive attributes inevitably deteriorate the mitigation performance.

heading: H.2 PREDICTION PERFORMANCE AND GDP TRADEOFF CURVE DURING TRAINING
text: Training curve on tabular data: Aiming to inspect the dynamic prediction performance and GDP during model training, we provide prediction performance and GDP tradeoff curve for Adult and Crimes dataset in Figure 10. The left and right y-axis represent the prediction performance and GDP metric, respectively. It is seen that, for kernel or histogram as regularization, the hyperparameter can control the prediction performance and GDP tradeoff, while the training is highly unstable with large variance for adversarial debiasing. Additionally, kernel estimation as regularization possesses better bias mitigation performance for Adult and Crimes dataset.
Training curve on graph data: Figures 11 and 12 demonstrates prediction performance and GDP tradeoff curve for Pokec-n and Pokec-z datasets using GCN and GAT model. It is seen that, for kernel or histogram as regularization, the hyperparameter can control the prediction performance and GDP tradeoff, while the training is highly unstable with large variance for adversarial debiasing. Additionally, kernel estimation as regularization possesses better bias mitigation performance for Pokec-n and Pokec-z datasets in GCN and GAT model.
Training curve on temporal graph data: Figure 13 demonstrates prediction performance and GDP tradeoff curve for Harris datasets using TGAT with map and product attention mechanism. It is seen that, for kernel or histogram as regularization, the hyperparameter can control the prediction performance and GDP tradeoff, while the training is highly unstable with large variance for adversarial debiasing. Additionally, kernel estimation as regularization possesses better bias mitigation performance for TGAT with map and product attention mechanism.
Training curve on compositional sensitive attribute: Figure 14 demonstrates prediction performance and GDP tradeoff curve for Adult and Crimes dataset. It is seen that, for kernel or histogram as regularization, the hyperparameter can control the prediction performance and GDP tradeoff, while the training is highly unstable with large variance for adversarial debiasing. Additionally, kernel estimation as regularization possesses better bias mitigation performance for Adult and Crimes dataset.

heading: I FUTURE WORKS
text: There are several interesting future work related to proposed GDP:(1)Extend other fairness metrics, such as Equal Odds (EO), for continuous and discrete sensitive attributes. The connection between extended fairness metric and adversarial debiasing is also interesting. (2) Provide a more fine-
grained analysis on estimation error, including the exact optimal bandwidth and estimation error expression, the lower bound of the estimation error for histogram and kernel GDP estimation over all data distribution and model prediction, the estimation error analysis over compositional sensitive attributes. (3)Investigate the better GDP estimation method with faster convergence guarantee.

Review summaries:
This paper proposes a generalized demographic parity for group fairness which is computationally feasible for both continuous and discrete protected attributes. Two estimations, histogram and kernel, are proposed for efficient estimation and the kernel estimation has faster estimation error governance. The connection between the GDP regularization and adversarial debiasing is built. The experiments on syntehtic/tabular/graph datasets show the effectiveness and efficiency of the GDP kernel estimation.

The paper is motivated by the need to account for continuous attributes in fair Machine Learning. In particular, it proposes a Generalized Demographic Parity metric (GDP), i.e., a group fairness metric that can work with both continuous and discrete variables. A key challenge in doing so is preserving tractable computation.   Theoretically, GDP is defined via the weighted total variation distance and measures the distance between the local and global prediction average, where the weight corresponds to the pdf of the continuous sensitive attributes. Since the joint distribution between model prediction and sensitive attributes might not be available in practice, the paper also proposes two estimation methods: histogram estimation and kernel estimation. The former quantizes the continuous sensitive attributes into bins, whereas in the latter method the group indicator of the sample is treated as a kernel function. The kernel method leads to faster estimation error convergence rate in terms of sample size. The paper provides an extensive evaluation with tabular, graph and temporal graph data, synthetic experiments, and classification and regression tasks. It is demonstrated experimentally that the kernel method has better bias mitigation performance.  

This paper proposes a new extension of demographic parity when the sensitive attribute is continuous. It proposes two techniques to estimate this quantity from data. The authors also consider adding this quantity as a regularization term to control discrimination while designing machine learning models.